Java数据结构和算法

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 )就是包括在花括号Z内用逗号分开的表达 式的列表。逗号分开了数组元素的值。Java会门动地分配一个足够大的空间來 保存你指定的初始化元素的个数，而不必使用运算符newoJava严格地检査以保证你不会总外地公存储或引用在数组范圉以外的值。 Java的运行系统会检査以确保所有的数组下标都在正确的范F科以内(在这方面,Java与C/

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

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

5、记最左 边未排序的数据，然后使用IN标记第1个数据，依次与MIN进行比较，如果比 MIN小，则将该数据标记为MIN,当第一轮比较完后，最终的MIN与OUT标记 数据交换，依次类推：选择排序的java代码：Public void selectSort()Int in,out,min;For(out=0;out<nElems-l;out+)Min=out;For(in=out+l;i n<n Elems;in+)lf(ain<amin)Min=in;Swapjoumin);选择排序的效率：0 (NN),比较N*N/2,交换VN；选择排序与冒泡排序比 较，比较次数没有明显改变，但交

6、换次数明显减少了很多；3. 插入排序的思想:插入排序是在部分数据有序的悄况下，使用OUT标记第一个无序的数据，将 其提取保存到一个屮间变暈temp小去，使用IN标记空位置，依次比较temp屮 的值与INJ的值,如果IN值大T temp的值，则后移,直到遇到第一个比temp 小的值，在其下一个位置插入；插入排序的java代码：Public void lnsertionSort()Int in,out;For(out=l;out vn Elems;out+)Long temp=aoutln=out;While(in>0&& ain-l>temp)Ain=ain-1;-i

7、n;Ain=temp;插入排序的效率:O(N*N),比较N*N/4,复制N*N/4；插入排序在随机数的 情况下，比冒泡快一倍，比选择稍快：在基本有序的数组屮，插入排序儿乎只需 要0 (N)；在逆序悄况下，并不比冒泡快；二、栈与队列1、栈的定义栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。(1) 通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。(2) 当表中没有元索时称为空栈:(3) 栈为后进先出(Last In First Out)的线性表,简称为UFO表。栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中" 最新"的元

8、素，即最后插入(进栈)的元素，而最先插入的是被放在栈的底部， 农到最后才能删除。出栈栈顶栈底栈示意图【示例】元素是以al, a2, , an的顺序进栈，退栈的次序却是an, an-1, ,31 o2、栈的基本运算(1) InitStack (S)构造一个空栈S。(2) StackEmpty (S)判栈空。若S为空栈，则返回TRUE,否则返回FALSEo(3) StaukFull (S)判栈满。若S为满栈,则返回TRUE,否则返回FALSEo注意：该运算只适用丁栈的顺序存储结构。(4) Push (S» x)进栈。若栈S不满，则将元素x插入S的栈顶。(5) Pop (S)退栈。若栈S非

9、空，则将S的栈顶元素删去，并返回该元素。(6) StackTop (S)取栈顶元素。若栈S非空，则返冋栈顶元素，但不改变栈的状态。队列的定义及基本运算1、定义队列（Queue）是只允许在一端进行插入，而任另一端进行删除的运算受入队限的线杵表ai 82队头队甩队列示怠图（1）允许删除的一端称为队头（Front） o（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有元索时称为空队列。（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO 表。队列的修改是依先进先出的原则进行的。新來的成员总是加入队尾（即不 允许"加塞"，每次离开的成员

10、总是队列头上的（不允许中途离队），即当前" 最老的"成员离队。【例】在队列中依次加入元素a” a:,，a=之后，內是队头元素，a=是队尾 元素。退出队列的次序只能是a“ a：,念。2、队列的基本逻辑运算（1）InitQueue （Q）置空队。构造一个空队列Q。（2）QueueEmpty （Q）判队空。若队列Q为空，则返回真值，否则返回假值。（3）QueueFull （Q）判队满。若队列Q为满，则返回真值，否则返回假值。注意：此操作只适用J：队列的顺序存储结构。（4）EnQueue （Q, x）若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。（5）DeQueue （Q）

11、若队列Q非空，则删公Q的队头元素，并返回该元素。此操作简称出队:（6）QueueFront （Q）若队列Q非空，则返回队头元素，但不改变队列Q的状态。三、链表1. 链结点在链表中，每个数据项都被包含在'点“中，一个点是某个类的对象，这个类可认叫做 UNKo因为一个链表屮仔许命类似的链结点，所以有必耍用一个不同链表的类来表达 链结点。每个LINK对象中都包含一个对下个点引用的字段（通常叫做next）但是本 身的対彖中有一个字段指向对第一个链结点的引用单链表用一组地址任意的存储单元存放线性表中的数据尤素。以元素（数据元素的映彖）+指针（指示后继元素存储位置）二结点（表示数据元索或数据元素的

12、映彖）以“结点的序列”表示线性表称作线性链表（单链表）一单链表是一种顺序存取的结构，为找第i个数据尤素，必须先找到第i-1个数 据元素。因此，弈找第i个数据元素的基木操作为：移动指针，比较j和i1、链接存储方法链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为： 用一组任意的存储单元來存放线性表的结点（这组存储单尤既可以是连续的， 也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻 辑关系，在存储每个结点值的同时，还必须存储指示Jt后继结点的地址(或位置)信 息(称为指针(pointer)或链(link)注意：链式存储是最常用的存

13、储方式之一，它不仅可用來表示线性表，而且可用來表示 齐种非线性的数据结构。2、链表的结点结构| data| next|data域存放结点侑的数据域next域疗放结点的直接后继的地址(位置)的指针域(链域)注意： 链衷通过每个结点的链域将线性农的n个结点按其逻辑顺序链接在一起的。 每个结点只冇一个链域的链衷称为单链表(Single Linked List)。【例】线性表(bat, cat, eat, fat, hat, jat, lat, mat)的单链表示如示意图3、头指针head和终端结点指针域的表示唯链表中每个结点的存储地址是存放在It前趋结点next域中，而开始结点无前 趋，故应设头指针

14、head向开始结点。注意：链衷由头指针唯一确定，单链衷可以用头指什的名字來命名。【例】头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULLo4、单链衷的一般图示法由我们常常只注HL纟占点间的逻辑顺序，不关心毎个结点的实际位迓，可以用箭 头来表示链域中的指针,线性表(bat, cat, fat, hat, jat, lat, mat)的单链表就可 以表示为下图形式。5、单链衷类型描述typedef char DataType; 假设结点的数据域类型为字符typedef struct node 结点类型定义DataType data; 结点的数据域struc

15、t node *next;/结点的指针域JListNodetypedef ListNode *LinkList;ListNode *p;LinkList head;注意： PnkList和ListNode是不同名字的同一个指针类型(命名的不同是为了概念 上更明确) LinkList类型的指针变量head表示它是单链表的头指针 ListNode类醴的指针变就p表示它是指向某一结点的拆针6、指针变量和结点变量|指针变最|结点变帚|IJIII1IIII1 1|定义|在变届说明部分显式定义|在程序执行时，通过标准| | | |函数malloc生成|1-J1 1II1 11 1II|取值|非空时，存放某

16、类型结点|实际存放结点各域内容| | |的地址| |I-JIIIIIIIIII|操作方式|通过指针变届名访问|通过指针生成、访问和释放 生成结点变鼠的标准函数p=( ListNode *)malloc(sizeof(ListNode)；函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指 针变量p中 释放结点变起空间的标准函数free(p)； 释放p所指的结点变量空间 结点分量的访问利用结点变届的乳字S访问结点分吊力法一：(*p).data 和Cp).next方法二：p- > data 和 p > next 指针变屉P和结点变吊"P的关系指针

17、变鼠p的值一结点地址结点变m!：*p的值结点内容(*p).data的值p指针所指结点的data域的值(*p).next的值*p后继结点的地址*(*p).next)*p 后继结点注意： 卄指针变量p的值为空(NULL),则它不指向任何结点。此时，若通过S 來访问结点就意味着访问一个不存在的变鼠，从而引起程序的错谋。 仃关指针类型的意义和说明方式的详细斛释可见，在链表中插入结点只需要修改折针。但同时，若耍在第i个结点之前插 入元素，修改的是第i-1个结点的指针。因此，在单链表屮第i个结点之前进行插入的甚本操作为：找到线性表中第PI个结点，然后修改其指向后继的指针。双端链表双端链表与传统的链衣II巾

18、相似，但是它有一个新增的特性：即对垠后一个链结点的 引用，就像对第一个链结点的引用一样。对彊后一个链结点的引用允许像在衷头-样，在表尾直接插入一个链结点。当然，仍 然可以在普通的单链衣的表尾插入-个链结点，方法足遍历整个链衷直到到达农足, 但是这种方法效率很低。对彊后一个链结点的引用允许像在表头-样，在表尾直接插入一个链结点。当然，仍 然可以在普通的单链农的衣尾插入一个链结点，方法足遍历整个链衷12到到达农足, 但是这种方法效率很低。像访问农头样访问农尾的特性，使双端谜农更适合 些普通谜农不方便操作的场 介，队列的实现就是这样一个情况。卜面是一个双端链表的例子。class Link3publi

19、c long dData;public Link3 next;IIpublic Link3(long d)dData=d;IIpublic void displayLink()System out print(dData+M M);/class FirstLastListprivate Link3 first;private Link3 last;IIpublic FirstLastList()first 二 n ull;last=null;public boolean isEmpty() return first二二null;IIIIpublic void insertFirst(long

20、dd)Link3 newLink=new Link3(dd); if(isEmpty() last 二 n ewLink;newLink.next 二 first;first 二 newLink;/public void insertLast(long dd)Link3 newLink=new Link3(dd); if(isEmpty() first二newLink;elselast.next 二 newLi nk;last 二n ewLink;/public long deleteFirst() long temp二first dData; if(first.next=二 null) la

21、st 二 n ull;first 二 first, next; return temp;/public void displayList()System.out.print("List (first->last):");Link3 current二first; while(curre nt!二 n ull) curre nt.displayLi nk(); current=curre nt. next;System.out.println(,IR);lllllllllllllllllllllllllllllllllllll public class FirstLast

22、App public static void 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.di

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

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

25、疋插入，last就指向新的链结点。如果链衷只仃一个链结点，那么多衷头 删除也是-种特殊情况:last必须被赋值为null值。不幸的是，用双端链农也不能仃助J删除厳后一个链结点，因为没仃一个引用指向倒 数笫二个链结点。如來最后个链结点被删除，倒数第二个链结点的Next字段应该 变成Null值。为了方便的删除址后一个链结点，需要一个双向链表。(当然，也可以 遍历整个链表找到最后一个链结点，但是那样做效率不是很高。)有序链表在有序链表中,数据是按照关键值有序排列的。有序链表的删除常常是只限FJM除在 链表头部的最小链结点。不过，有时也用Find()方法和Delete()方法在整个链表中搜 索某一特定

26、点。一般，在犬多数需要使用有序数组的场合也可以便用有序链表。有序链表优于有序数 组的地方是插入的速度,另外链表可以扩展到全部有效的使用内存，而数组只能局限 一个固定的人小中。但是，有序链表实现起來比有序数组更困难一些。后而将看到一个有序链表的应用：为数据排序。有序链表也可以用实现优先级队列, 尽管堆是更常用的实现方法。在勺序链表中插入一个数据项的Java代码为了在一个令用链表中插入数据项，算法必须首先捜索懺表，苴到找到合适的位置: 它恰好在第一个比它人的数据项的前向。当算法找到了耍插入的位置，用通常的方式插入数据项：把新链结点的Next字段指 向卜一个链结点，然后把前一个链结点的Next字段改

27、为指向新的链结点。然而，需 要考虑一些特殊情况：锻结点令可以插在表头，或者插在表尾。看一卜这段代码： Public void insert(long key)Link newLink=new Link(key);Link previous=null;Link current二first;While(current!=null && key>current.dData)Previous=curre nt;Current=current.next;lf(provious=null)First=newLink;ElsePrevious.next=newLink;n ewLink

28、.next=curre nt;在链表上移动时，需要用一个previous引用，这样才能把前一个链结点的Next字段 指向新的链结点。创建新链结点后，把current变杲设为first,准备搜索止确的插入 点。这时也把previous设为Null值,这步操作很重要，因为后面要用这个Null值判 断是否仍在表头。While循环和以前用来搜索插入点的代码类似，但是冇一个附加的条件。如果当前检 件的链结点的关键值不再小待插入的链结点的关键值，则循环结束：这是最常见的 情况，即新关键值插在徒表中部的某个地方。然而，如果current为Null值，while循环也会停止。这种情况发生在表尾，或者链 表为空

29、时。如果current在表头或者链表为空,previous将为Null值;所以让first指向新的链结 点。否则current处在链衣中部或结尼，就使previous的next字段扌旨向新的链结点。 不论哪种情况、都让新链结点的Next字段指向currento如眾在表尼，current为Nu II值，则新链结点的Next字段也本应该设为这个值(Null) o下面是有序链表的程序SortedList.java 程序实现了一个 SortedList 类,它拥有 insert。、remove()和 display List()方法。只有insert()方法与无序链表中的insert()方浓不同。pa

30、ckage有序链表;class Linkpublic long dData;public Link next;public Link(long dd)dData=dd;/public void displayLink()System.out.print(dData+M n);llllllllllllllllllllllllllllllllllllllllclass SortedListprivate Link first;/public SortedList()first 二 null;/public boolean isEmpty()return (first二二null);/public

31、void insert(long key)Link newLink=new Link(key);Link previous二null;Link current二first;while(current!二null && key>current.dData)prcvious=curront;current=current. next;if(previous=null) first二newLink;elseprevious.next=newLink; newLink. next 二 current;/public Link remove()Link temp二first;fir

32、st 二 first.next; return temp;/public void displayList()System.out.printC'List (first->last):");Link current=first; while(current!=nu ll) current.displayLi nk(); current 二 current, next;System.out.println(MM);public class SortedLinkApp public static void main(String args) SortedList theSo

33、rtedList二new SortedList(); theSortedList.insert(20);theSortedList. insert(40); theSortedList.displayList();theSortedList. insert( 10);theSortedList.i nsert(30);theSortedList.! nset(50); theSortedList.displayList(); theSortedList.remove();theSortedList.displayList();System.exit(0);在Main()方法中，插入值为20和4

34、0的两个链结点。然后再插入三个链结点，分别 是10、30和50。这三个值分别插在表头、表中和表尼。这说明insert()方法正确地 处理了特殊情况。最厉删除了一个链结点，表现出删除操作总是从表头进行。每一步 变化后，都显示整个链表。双向链表双向链表也叫双链表,是链表的一种，它的每个数据结点中都有两个指针,分别指向 直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访 问它的前驱结点和后继结点。一般我们都构造双向循坏链表。/*线性表的双向傩表存储结构Ttypedef struct DuLNodeElemType data;struct DuLNode *priorf*nex

35、t;DuLNode,*DuLinkList;厂带头结点的双向循坏链表的基本操作(14个)*/void lnitList(DuLinkList *L) P产生空的双向循环链表L */*L=(DuLinkList)malloc(sizeof(DuLNode);(*L)->next=(*L)->prior=*L;elsecxit(OVERFLOW);void DestroyList(DuLinkList *L) r操作结果：销毁双向循环链表L /DuLinkList q,p=(*L)->next; /* p 指向第一个结点 */while(pl=*L) /* p 没到表头/q=p-

36、>next;free(p);P=q；free(-L);*L=NULL;void ClearList(DuLinkList L) /* 不改变 L 7 /*初始条件：L已存在。操作结果：将L亜置为空表7DuLinkList q,p=L->next; /* p 指向第一个结点 T while(p!=L) /* p 没到表头 */q=p->next;free(p);P 二 q；L->next=L->prior=L; /*头结点的两个指针域均指向自身*/Status ListEmpty(DuLinkList L) /*初始条件：线性表Li2存在。操作结果：弟L为空衷，则返

37、回TRUE,否则 返回 FALSE */if(L->next=L&&L->prior=L)return TRUE;elsereturn FALSE;int ListLength(DuLinkList L) /*初始条件：L已存在。操作结果：返回L中数据兀索个数7int i=0;DuLinkList p=L->next; /* p 指向第一个结点 */while(p!=L) / p 没到表头 Ti+;p=p->n ext;return i;Status GetElem(DuLinkList L.int i.ElemType *e) P当第i个元素存在时，其

38、值赋给e并返回OK,否则返回ERROR */ int j=1; /* j为计数器TDuLinkList p=L->next; /* p 指向第一个结点 Twhile(p!=L&&jnext;j+；if(p=L|j>i) /*第i个元索不存在Treturn ERROR;*e=p->data; /* 取第 i 个元素 */return OK;int LocateElem(DuLinkList L.EIemType e,Status(*compare)(ElemType,Elem Type) /*初始条件：L已存在，compare()是数据元素判定函数TP操作结果：

39、返回L中第1个与e满足关系compare()的数据元素的位序。*/*若这样的数据元素不存在，则返回值为0 */int i=0;DuLinkList p=L->next; /* p 指向第 1 个元素 Twhile(p!=L)i+；if(compare(p->data,e) /*找到这样的数据元素*/return i;p=p->next;return 0;Status PriorElem(DuLinkList L.EIemType cur_e,ElemType *pre_e) /*操作结果：Zf cur_e是L的数据元素，JI不是第一个，则用pre_e返回它的 前驱，7/否则操

40、作失败，pe_e无定义TDuLinkList p=L->next->next; /* p 指向第 2 个元素 */while(p!=L) r p 没到农头 Tif(p->data=cur_e)*pre_e=p->prior->data;return TRUEp=p->n ext;return FALSE;Status NextElem(DuLinkList L.EIemType cur_e,ElemType *next_e) /*操作结果：若cur_e是L的数据元素，£1不是址后一个，则用next_e返回 它的后继，T/*否则操作失败，next_e

41、无定义7DuLinkList 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) /* 另加 T r在双向链表L中返回第i个元素的地址。i为0,返回头结点的地址。若第i 个元素不存在，"/* 返回 NULL 7int j；DuLinkList p=L; /*

42、p 指向头结点 */ if(i<O|i>ListLength(L) /* i ffi不合法 */ return NULL;forG=1;j<=i;j+)p=p->next;return p;Status Listlnsert(DuLinkList L,int i.ElemType e) /*在带头结点的双链循环线性表L中第i个位置Z前插入尤素e, i的介法值为 1<i<3< 长+1 */*改进算法2J&否则无法在第表长+ 1个结点Z前插入元素TDuLinkList p.s;if(i<1|i>ListLength(L)+1)广 i 值

43、不合法 */return ERROR;p=GetElemP(L,i-1); /*在L中确定第i个元素前驱的位置指针p */if(!p) P p二NULL,即第i个九索的前驱不存在(设头结点为笫1个尤索的前驱)7 return ERROR;s=(DuLinkList)malloc (sizeof(DuLNode);if(!s)return OVERFLOW;s->data=e;s->prior=p; /*在第/个元素之后插入*/s>n ext=p >next;p>n ext->prior=s;p>n ext=s;return OK;Status List

44、Delete(DuLinkList L,int i.ElemType *e) /*删除带头结点的双链循环线性表L的第i个元素，i的合法值为农长/DuLinkList p;if(i<1)广i值不合法7return ERROR;p=GetElemP(L,i); /在L中确定第i个元素的位置指针p /if(!p) r P二NULL,即第i个元素不存在Treturn ERROR;*e=p->data;p >prior>next 二 p>n ext;p>n ext->prior 二 p >pior;free(p);return OK;void ListTr

45、averse(DuLinkList L,void(*visit)(ElemType) /*由双链循环线性衷L的头结点出发，正序对每个数据尤索调用函数visit() */DuLinkList p=L->next; /* p 指向头结点 */while(p!=L)visit(p->data);p=p->n ext;printf("n");void ListTraverseBack(DuLinkList L,void(*visit)(ElemType) /*宙双链循环线性农L的头结点出发，逆序对每个数据尤索调用函数visit()o 另加*/DuLinkList

46、p=L->prior; /* p 指向尾结点 */whilo(p!=L)visit(p->data); p=p->prior; printf("n");迭代器迭代器是一种对彖，它能够用來遍历STL容器中的部分或全部元索，每个迭代器对 象代表容器中的确定的地址。迭代器修改了常规指针的接口,所谓迭代器是一种概念 上的抽象:那些行为上彖迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的 能力，它可以把抽彖容器和通用算法有机的统一起來。迭代器提供一些基本操作符：*、+、=二、！二、=o这些操作和C/C+"操作array元 索”时的指针接1丨一致。不同Z

47、处在J：,迭代器是个所谓的smart pointers, II仃遍历 复杂数据结构的能力。其卜层运行机制取决其所遍历的数据结构。因此，每一种容 器型别都必须提供口C的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义 J内部。因此各种迭代器的接II相同，型别却不同。这口接导出了泛型程序设计的概 念：所有操作行为都使用相同接口，虽然它们的型别不同。功能迭代器使开发人员能够在类或结构中支持foreach迭代，而不必整个实现lEnumerab le或（Enumerator接口.只需提供一个迭代器,即可遍历类中的数据结构。当编译 器检测到迭代器时，将自动生成（Enumerable接丨I或者（Enum

48、erator接11的Current, MoveNext 和 Dispose 方広。特点1.迭代器是可以返冋相同类空值的有序序列的一段代码；2迭代器可用作方法、运算符或get访问器的代码体；3. 迭代器代码使用yield return语句依次返回每个元素,yield break将终止迭代：4可以在类中实现多个迭代器，每个迭代器都必须像任何类成员一样冇惟一的名 称，并且可以在foreach语句中被客户端代码调用：5. 迭代器的返回类型必须为（Enumerable和lEnumerator 'I1的任意一种;6. 迭代器是产生值的有序序列的一个语句块，不同冇一个 或多个yield语句存 在的常

49、规语句块；7. 迭代器不是一种成员，它只是实现怖数成员的方式，理解这一点是很觅要的， 一个通过迭代器实现的成员，可以被梵他可能或不可能通过迭代器实现的成员厦盂和 重载；8. 迭代器块在C#语法屮不是独特的尤素，它们在儿个方而受到限制，并且主耍 作用在函数成员声明的语义上，它们在语法上只是语句块而己；I、递归递归是函数调用自身的一种特殊的编程技术，其应用主要在以卜儿个方面：阶乘在java为中的某木形式是：Public void mothed (int n) /半满足某条件时：Mothed (n-1 )：递归二分查找Java二分先找实现，欢迎人家提出交流意见./*名称:BinarySearch.功

50、能:实现了折半査找(二分査找)的递归和非递归算法.r兑明：* 1、要求所資找的数组已有序,并且其中元素己实现Comparable<T>接丨I,如 Integer、String 等.* 2、非递归査找使用search();,递归査找便用searchRecursively();"本程序仅供编程学习参考*author: Wintywdate:2000-8-11*email: emailwintys/email/class BinarySearch<T extends Comparable<T>> private T data;/要排序的数据public

51、BinarySearch(T data)this.data = data;public int search(T key)int low;int high;int mid;if(data 二二 null)return -1;low = 0;high = dataength 1;while(low <= high)mid = (low + high) / 2;System.out.println(Mmid M + mid + M mid value:11 + datamid);/if(pareTo(datamid) < 0)high = mid - 1;else if(pareTo(

52、datamid) > 0)low = mid + 1;else if(pareTo(datamid) = 0)return mid;returnprivate int doSearchRecursively(int low , int high r T key)int mid;int result;if(low <= high)mid = (low + high) / 2;result = pareTo(datamid):System.out.printlnC'mid " + mid + " mid value:" + datamid);/if

53、(result < 0)return doSearchRecursively(low f mid 1 t key);else if(result > 0)return doSearchRecursively(mid + 1 , high , key);else if(result = 0)return mid;return -1;public int searchRecursively(T key)if(data =null)returnreturn doSearchRecursively(0 , dataength 1 , key);public static void main

54、(String args)lnteger data = 1 ,4 ,5 ,8 ,15 ,33 ,48 ,77 ,96;BinarySearch<lnteger> binSearch = new BinarySearch<lnteger>(data); /System.out.pri ntln ("Key in dex:H + bin Search.search(33);System.out.println(wKey index，+ binSearch.searchRecursively(3);/String dataStr = "A”，”C”，“F”

55、，”J" ,"L"，”N” ,T;/BinarySearch<String> binSearch 二 new BinarySearch<String>(dataSt 0；/System.out.println("Key index:" + binSearch.search("A");递归排序氏实在数组的全排序屮完全可以使用更加易懂简便的写広for循环，但是通过 fo循环编写数组全排序盂要冇一个先决条件一知道数组全排序的个数，因为有 n个数据全排序就需要写n个恢套for循环。因此在写全排序时一般使用递归方 法。这就是我的第一个关于递归排序的见解递归排序可以无需已知排序数组 的长度,即排序个数!其二,不管是使用递归进行数组排序还是使用for循环进行数组的排序,它们都 是本质都是使用枚举，因此可以得出这样一个结论:枚举可以确保找出每一种可能 的排序规则！其三，枚举是列出所有的方法并找出符合耍求的算法，因此其算法效率一定比较 的低，需要対其进行优化，才能达到较好的效果(递归的时候排除所有不町能的 方案)消除递归消除递归的基本思路是用栈来模拟系统的函数调用从而消除递归。基本上要做一卜三件事：传递参数(池括返回地址)并转到两数入