Java数据结构和算法精品资料.docx

《Java数据结构和算法精品资料.docx》由会员分享，可在线阅读，更多相关《Java数据结构和算法精品资料.docx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Java数据结构和算法一、数组于简单排序1二、栈与队列4三、链表7四、递归22五、哈希表25六、高级排序25七、二叉树25八、红黑树26九、堆36十、带权图39一、数组于简单排序数组数组（array）是相同类型变量的集合，可以使用共同的名字引用它。数组可被定义为任何类型，可以是一维或多维。数组中的一个特别要素是通过下标来访问它。数组提供了一种将有联系的信息分组的便利方法。一维数组一维数组（one-dimensional array ）实质上是相同类型变量列表。要创建一个数组，你必须首先定义数组变量所需的类型。通用的一维数组的声明格式是：type var-name ; 获得一个数组需要2步。第一

2、步，你必须定义变量所需的类型。第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。这样Java 中的数组被动态地分配。如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。数组的初始化（array initializer ）就是包括在花括号之内用逗号分开的表达式的列表。逗号分开了数组元素的值。Java 会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。Java 严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。Java 的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面，Java 与C/C+ 从

3、根本上不同，C/C+ 不提供运行边界检查）。多维数组在Java 中，多维数组（multidimensional arrays ）实际上是数组的数组。你可能期望，这些数组形式上和行动上和一般的多维数组一样。然而，你将看到，有一些微妙的差别。定义多维数组变量要将每个维数放在它们各自的方括号中。例如，下面语句定义了一个名为twoD 的二维数组变量。int twoD = new int45; 简单排序简单排序中包括了：冒泡排序、选择排序、插入排序；1.冒泡排序的思想：假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第

4、2个，这样依次类推，直至所有数据都“冒泡”到数据顶上。冒泡排序的的java代码：Public void bubbleSort()int in,out;for(out=nElems-1;out0;out-) for(in=0;inain+1) Swap(in,in+1);算法的不变性：许多算法中，有些条件在算法执行过程中始终是不变的。这些条件被称 为算法的不变性，如果不变性不为真了，则标记出错了；冒泡排序的效率O（N*N），比较N*N/2，交换N*N/4；2. 选择排序的思想：假设有N条数据，则暂且标记第0个数据为MIN（最小），使用OUT标记最左边未排序的数据，然后使用IN标记第1个数据，依次

5、与MIN进行比较，如果比MIN小，则将该数据标记为MIN，当第一轮比较完后，最终的MIN与OUT标记数据交换，依次类推；选择排序的java代码：Public void selectSort()Int in,out,min;For(out=0;outnElems-1;out+) Min=out;For(in=out+1;innElems;in+) If(ainamin) Min=in;Swap(out,min);选择排序的效率：O（N*N），比较N*N/2，交换N； 选择排序与冒泡排序比较，比较次数没有明显改变，但交换次数明显减少了很多；3. 插入排序的思想：插入排序是在部分数据有序的情况下，使

6、用OUT标记第一个无序的数据，将其提取保存到一个中间变量temp中去，使用IN标记空位置，依次比较temp中的值与IN-1的值，如果IN-值大于temp的值，则后移，直到遇到第一个比temp小的值，在其下一个位置插入；插入排序的java代码：Public void InsertionSort() Int in,out; For(out=1;out0& ain-1temp) Ain=ain-1; - -in;Ain=temp;插入排序的效率：O（N*N）, 比较N*N/4，复制N*N/4；插入排序在随机数的情况下，比冒泡快一倍，比选择稍快；在基本有序的数组中，插入排序几乎只需要O（N）；在逆序情

7、况下，并不比冒泡快；二、栈与队列1、栈的定义 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。 【示例】元素是以a1，a2，an的顺序进栈，退栈的次序却是an，an-1，a1。2、栈的基本运算（1）InitStack（S） 构造一个空栈S。

8、（2）StackEmpty（S） 判栈空。若S为空栈，则返回TRUE，否则返回FALSE。（3）StackFull（S） 判栈满。若S为满栈，则返回TRUE，否则返回FALSE。注意： 该运算只适用于栈的顺序存储结构。（4）Push（S，x） 进栈。若栈S不满，则将元素x插入S的栈顶。（5）Pop（S） 退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。（6）StackTop（S） 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。队列的定义及基本运算1、定义 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表 （1）允许删除的一端称为队头（Front）

9、。（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。【例】在队列中依次加入元素a1，a2，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，an。2、队列的基本逻辑运算（1）InitQueue（Q） 置空队。构造一个空队列Q。（2）QueueEmpty（Q） 判队空。若队列Q为空，则返回真值，否则返回假值。

10、（3） QueueFull（Q） 判队满。若队列Q为满，则返回真值，否则返回假值。 注意：此操作只适用于队列的顺序存储结构。（4） EnQueue（Q，x） 若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。（5） DeQueue（Q） 若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。（6） QueueFront（Q） 若队列Q非空，则返回队头元素，但不改变队列Q的状态。 三、链表1 链结点在链表中，每个数据项都被包含在点“中，一个点是某个类的对象，这个类可认叫做LINK。因为一个链表中有许多类似的链结点，所以有必要用一个不同于链表的类来表达链结点。每个LINK对象中都包含

11、一个对下一个点引用的字段（通常叫做next）但是本身的对象中有一个字段指向对第一个链结点的引用单链表用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置)= 结点(表示数据元素 或 数据元素的映象)以“结点的序列”表示线性表 称作线性链表（单链表）单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 1、链接存储方法链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存

12、储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构datanext data域-存放结点值的数据域next域-存放结点的直接后继的地址（位置）的指针域（链域）注意：链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。每个结点只有一个链域的链表称为单链表（Single Linked List

13、）。【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。注意：链表由头指针唯一确定，单链表可以用头指针的名字来命名。【例】头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULL。4、单链表的一般图示法由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可

14、以表示为下图形式。5、单链表类型描述typedef char DataType; /假设结点的数据域类型为字符typedef struct node /结点类型定义DataType data; /结点的数据域struct node *next;/结点的指针域ListNodetypedef ListNode *LinkList;ListNode *p;LinkList head;注意：*LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确）*LinkList类型的指针变量head表示它是单链表的头指针ListNode类型的指针变量p表示它是指向某一结点的指针

15、6、指针变量和结点变量 指针变量结点变量 定义 在变量说明部分显式定义 在程序执行时，通过标准 函数malloc生成 取值 非空时，存放某类型结点 实际存放结点各域内容 的地址 操作方式 通过指针变量名访问 通过指针生成、访问和释放 生成结点变量的标准函数p=( ListNode *)malloc(sizeof(ListNode)；/函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数 free(p)；/释放p所指的结点变量空间结点分量的访问 利用结点变量的名字*p访问结点分量方法一：(*p).data和(*p).next方法二

16、：p-data和p-next指针变量p和结点变量*p的关系 指针变量p的值结点地址结点变量*p的值结点内容(*p).data的值p指针所指结点的data域的值(*p).next的值*p后继结点的地址*(*p).next)*p后继结点注意： 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。 有关指针类型的意义和说明方式的详细解释可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。因此，在单链表中第 i 个结点之前进行插入的基本操作为:找到线性表中第i-1

17、个结点，然后修改其指向后继的指针。双端链表双端链表与传统的链表非常相似，但是它有一个新增的特性：即对最后一个链结点的引用，就像对第一个链结点的引用一样。对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样一个情况。下

18、面是一个双端链表的例子。class Link3 public long dData; public Link3 next; /. public Link3(long d) dData=d; /. public void displayLink() System.out.print(dData+ ); /class FirstLastList private Link3 first; private Link3 last; /. public FirstLastList() first=null; last=null; /. public boolean isEmpty() return fir

19、st=null; /. public void insertFirst(long dd) Link3 newLink=new Link3(dd); if(isEmpty() last=newLink; newLink.next=first; first=newLink; /. public void insertLast(long dd) Link3 newLink=new Link3(dd); if(isEmpty() first=newLink; else last.next=newLink; last=newLink; /. public long deleteFirst() long

20、temp=first.dData; if(first.next=null) last=null; first=first.next; return temp; /. public void displayList() System.out.print(List (first-last): ); Link3 current=first; while(current!=null) current.displayLink(); current=current.next; System.out.println(); /public class FirstLastApp public static vo

21、id main(String args) FirstLastList theList=new FirstLastList(); theList.insertFirst(22); theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11); theList.insertLast(33); theList.insertLast(55); theList.displayList(); theList.deleteFirst(); theList.deleteFirst(); theList.displayList(

22、); 为了简单起见，在这个程序中，把每个链结点中的数据字段个数从两个压缩到一个。这更容易显示链结点的内容。（记住，在一个正式的程序中，可能会有非常多的数据字段，或者对另外一个对象的引用，那个对象也包含很多数据字段。）这个程序在表头和表尾各插入三个链点，显示插入后的链表。然后删除头两个链结点，再次显示。注意在表头重复插入操作会颠倒链结点进入的顺序，而在表尾的重复插入则保持链结点进入的顺序。双端链表类叫做FirstLastList。它有两个项，first和last，一个指向链表中的第一个链结点，另一个指向最后一个链结点。如果链表中只有一个链结点，first和last就都指向它，如果没有链结点，两者

23、都为Null值。这个类有一个新的方法insertLast()，这个方法在表尾插入一个新的链结点。这个过程首先改变last.next，使其指向新生成的链结点，然后改变last，使其指向新的链结点。插入和删除方法和普通链表的相应部分类似。然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的。如果isEmpty()是真，那么insertFirst()必须把last指向新的链结点，insertLast()也必须把first指向新的链结点。如果用insertFirst()方法实现在表头插入，first就指向新的链结点，用insertLast()方法实现在表尾插入，last就指向新的链结点。如果链表

24、只有一个链结点，那么多表头删除也是一种特殊情况：last必须被赋值为null值。不幸的是，用双端链表也不能有助于删除最后一个链结点，因为没有一个引用指向倒数第二个链结点。如果最后一个链结点被删除，倒数第二个链结点的Next字段应该变成Null值。为了方便的删除最后一个链结点，需要一个双向链表。（当然，也可以遍历整个链表找到最后一个链结点，但是那样做效率不是很高。）有序链表在有序链表中，数据是按照关键值有序排列的。有序链表的删除常常是只限于删除在链表头部的最小链结点。不过，有时也用Find()方法和Delete()方法在整个链表中搜索某一特定点。一般，在大多数需要使用有序数组的场合也可以使用有序

25、链表。有序链表优于有序数组的地方是插入的速度，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。但是，有序链表实现起来比有序数组更困难一些。后而将看到一个有序链表的应用：为数据排序。有序链表也可以用于实现优先级队列，尽管堆是更常用的实现方法。在有序链表中插入一个数据项的Java代码为了在一个有序链表中插入数据项，算法必须首先搜索链表，直到找到合适的位置：它恰好在第一个比它大的数据项的前面。当算法找到了要插入的位置，用通常的方式插入数据项：把新链结点的Next字段指向下一个链结点，然后把前一个链结点的Next字段改为指向新的链结点。然而，需要考虑一些特殊情况：链结点有可以插

26、在表头，或者插在表尾。看一下这段代码：Public void insert(long key)Link newLink=new Link(key);Link previous=null;Link current=first;While(current!=null & keycurrent.dData)Previous=current;Current=current.next;If(previous=null)First=newLink;ElsePrevious.next=newLink;newLink.next=current;在链表上移动时，需要用一个previous引用，这样才能把前一个链

27、结点的Next字段指向新的链结点。创建新链结点后，把current变量设为first，准备搜索正确的插入点。这时也把previous设为Null值，这步操作很重要，因为后面要用这个Null值判断是否仍在表头。While循环和以前用来搜索插入点的代码类似，但是有一个附加的条件。如果当前检查的链结点的关键值不再小于待插入的链结点的关键值，则循环结束；这是最常见的情况，即新关键值插在链表中部的某个地方。然而，如果current为Null值，while循环也会停止。这种情况发生在表尾，或者链表为空时。如果current在表头或者链表为空，previous将为Null值；所以让first指向新的链结点。

28、否则current处在链表中部或结尾，就使previous的next字段指向新的链结点。不论哪种情况、都让新链结点的Next字段指向current。如果在表尾，current为Null值，则新链结点的Next字段也本应该设为这个值（Null）。下面是有序链表的程序SortedList.java程序实现了一个SortedList类，它拥有insert()、remove()和displayList()方法。只有insert()方法与无序链表中的insert()方法不同。package 有序链表;class Linkpublic long dData;public Link next;public

29、Link(long dd)dData=dd;/.public void displayLink()System.out.print(dData+ );/class SortedListprivate Link first;/.public SortedList()first=null;/.public boolean isEmpty()return (first=null);/.public void insert(long key)Link newLink=new Link(key);Link previous=null;Link current=first;while(current!=n

30、ull & keycurrent.dData)previous=current;current=current.next;if(previous=null)first=newLink;elseprevious.next=newLink;newLink.next=current;/.public Link remove()Link temp=first;first=first.next;return temp;/.public void displayList()System.out.print(List (first-last): );Link current=first;while(curr

31、ent!=null)current.displayLink();current=current.next;System.out.println();public class SortedLinkApp public static void main(String args) SortedList theSortedList=new SortedList();theSortedList.insert(20);theSortedList.insert(40);theSortedList.displayList();theSortedList.insert(10);theSortedList.ins

32、ert(30);theSortedList.insert(50);theSortedList.displayList();theSortedList.remove();theSortedList.displayList();System.exit(0);在Main()方法中，插入值为20和40的两个链结点。然后再插入三个链结点，分别是10、30和50。这三个值分别插在表头、表中和表尾。这说明insert()方法正确地处理了特殊情况。最后删除了一个链结点，表现出删除操作总是从表头进行。每一步变化后，都显示整个链表。双向链表双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向

33、直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。/* 线性表的双向链表存储结构 */typedef struct DuLNodeElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;/*带头结点的双向循环链表的基本操作(14个) */void InitList(DuLinkList *L) /* 产生空的双向循环链表L */*L=(DuLinkList)malloc(sizeof(DuLNode);if(*L)(*L)-next=(*L)-pri

34、or=*L;elseexit(OVERFLOW);void DestroyList(DuLinkList *L) /* 操作结果：销毁双向循环链表L */DuLinkList q,p=(*L)-next; /* p指向第一个结点 */while(p!=*L) /* p没到表头 */q=p-next;free(p);p=q;free(*L);*L=NULL;void ClearList(DuLinkList L) /* 不改变L */ /* 初始条件：L已存在。操作结果：将L重置为空表 */DuLinkList q,p=L-next; /* p指向第一个结点 */while(p!=L) /* p

35、没到表头 */q=p-next;free(p);p=q;L-next=L-prior=L; /* 头结点的两个指针域均指向自身 */Status ListEmpty(DuLinkList L) /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */if(L-next=L&L-prior=L)return TRUE;elsereturn FALSE;int ListLength(DuLinkList L) /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */int i=0;DuLinkList p=L-next; /* p指向第一个结点 */wh

36、ile(p!=L) /* p没到表头 */i+;p=p-next;return i;Status GetElem(DuLinkList L,int i,ElemType *e) /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */int j=1; /* j为计数器 */DuLinkList p=L-next; /* p指向第一个结点 */while(p!=L&jnext;j+;if(p=L|ji) /* 第i个元素不存在 */return ERROR;*e=p-data; /* 取第i个元素 */return OK;int LocateElem(DuLinkList L,E

37、lemType e,Status(*compare)(ElemType,ElemType) /* 初始条件：L已存在，compare()是数据元素判定函数 */* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */* 若这样的数据元素不存在，则返回值为0 */int i=0;DuLinkList p=L-next; /* p指向第1个元素 */while(p!=L)i+;if(compare(p-data,e) /* 找到这样的数据元素 */return i;p=p-next;return 0;Status PriorElem(DuLinkList L,ElemTy

38、pe cur_e,ElemType *pre_e) /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */* 否则操作失败，pre_e无定义 */DuLinkList p=L-next-next; /* p指向第2个元素 */while(p!=L) /* p没到表头 */if(p-data=cur_e)*pre_e=p-prior-data;return TRUE;p=p-next;return FALSE;Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e) /* 操作结果：若cur_

39、e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */* 否则操作失败，next_e无定义 */DuLinkList p=L-next-next; /* p指向第2个元素 */while(p!=L) /* p没到表头 */if(p-prior-data=cur_e)*next_e=p-data;return TRUE;p=p-next;return FALSE;DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */ /* 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，*/* 返回NULL */int j;DuLinkList p=L; /* p指向头结点 */if(iListLength(L) /* i值不合法 */return NULL;for(j=1;jnext;return p;Status ListInsert(DuLinkList L,int i,ElemType e) /* 在带头结点的双链