Java数据结构和算法

1、Java数据结构和算法、数绀r简中抟序1二、栈与队列4三n7Fmn22£哈絲25六，25七、二乂树25八' 红一261.堆36I. 、带权阌39一、数组于简单排序数组数组(array)是相同类型变量的集合，可以使用共同的名字引用它。数组可 被定义为任何类制，可以足一维或多维。数组屮的一个特別耍疾是通过下标宋汸 问它。数组捉供丫一种将冇联系的信息分组的便利方法。一维数组一维数组(one-dimensional array )实质I.是相冋类型变燉列表。要创建一 个数饥.你必须|vf先记义数组殳hi:所耑的类吧.通川的一维数饥的戶叫格式足: type var name|);获W个

2、数组亦要2步。第一步，你必须定义变锿所脔的类型。第二步，你 必®使川运？Z符new來力数组所逛存储的数据分ftl内存，井把它们分妃给数组 变K。这样java中的数组被动态地分配。如果动态分妃的概念对你昭生，别担 心，它将在木书的后而详细讨论。数组的磯化(array initializer )就足包括介:花W号之内川逗号分开的表达 八的列衣。逗3分丌f数组元紊的伉。Java公|'|动地分配-个足够大的空间來 保介:你衍定的初始化冗东的个数.卵小必使用运好符new。Java严格地检査以保证你不会意外地人存储成引用在数组范Ifl以外的值。Java的运行系统会检杏以确W所打的数组下标

3、邡住正确的范IH以内(迮这力Ifri.Java与C/C+从根木h不同，C/C+不提供运行边界检ft)。 多维数组在Java中，多维数组(multidimensional arrays )实际上是数组的数组。你 4能期，这些数组形式上和行动上和一股的多维数组一样。然而，你将fl到. 有一些微妙的差別。定义多维数纽变14钽将毎个维数放在它们各n的方括9屮。 例如，下而语句定义了一个名为twoD的二维数组变鼠。 int twoD(| = new int|4(5);简单排序简巾.抹序中包括了: 0泡抹序、选择排序、插入排序:1. R泡排序的思想:假没有N个数据耑恕排序，则从第0个数幵始，依次比较第0和

4、第1个数据, 如果第0个人r笫1个则两荇交换，否则什么动作都不做，继续比较第1个笫2 个，这样依次类推，直至所有数据都“冒泡”到数据顶上。V?泡排序的的java代码： Public void bubbleSort() int in,out; for(out=nElems-l;out>0;out-) for(in=0;in<out;in+) lf(ain>ain+l) Swap(in,in+1); )J法的个变性：作多灯法屮，冇些条件迮烊让执行过ft!屮始终足小变的。这些 条件被称为算法的不变性，如果不变性不为真了，则标记出错了:H泡棑序的效率0 (N*N),比较N*N/2.交

5、换N*N/4；2. 选择排序的思恕：假S釘N条数据，则wn.标记笫0个数据为MIN(Ai小)，使用0UT标记W左 边未排序的数椐，然后使用IN标记第1个数据，依次与MIN进行比较，如果比 MIN小.则将该数枞标记为MIN. 笫一轮比较义后，敁终的MIN与OUT标i己 数据交换，依次类推：选择排序的java代码：Public void selectSort()Int in'out'min;For(out=0;out<nElems-l;out+)Min=out;For(in=out+l;in<nElems;in+)lf(ain<a(min)Min=in;Swap(

6、out,min);J)选择样序的效率:0 (N*N).比较N*N/2.交换<N;选择抹序与It泡撐序比 较，比较次数没介叫坫改变，M交换次数明敁减少丫很多：3. 插入排序的思想:插入排序是介:部分数裾有序的估况下，使用OUT标id第一个无序的数掂，将 其提取保存到一个屮间变置temp中去，使用IN标记空位置，依次比较temp屮 的值与IN1的值，如果IN-值大丁 temp的值，则后移，/£到遇到第一个比temp 小的值，在其卜一个位背插入：插入抹序的java代码:Public void lnsertionSort()Int in,out;For(out=l;out<nEl

7、ems;out+)Long temp=a|outln=out;While(in>0&& ain-l>temp)Ain=a|in-1; -in;)Ain 卜 temp;)插入排序的效率:0 (N*N),比较N*N/4,箋制N*N/4：插入排序在随机数的 W况下.比H泡快一倍，比选择稍快：在杜本有序的数组屮.描入排序儿乎只志 S：0 (N)；在逆序惜况下.并+比H泡快；二、栈与队列1、栈的定义找(Stack)足限制仪在农的端进行插入和删除运灯的线性农。(1) 通常称捕入、删除的这一端为栈顶(Top), 端称为栈底(Bottom)，(2) 3衣屮没打兀紊时称为空栈。(3)

8、 栈为后进先出(Last In First Out)的线性表，简称为LIFO表。 找的修改足按后进先出的吩则进行。毎次刪除(退栈)的总足与前栈屮'最新的元素，即最后插入(进栈)的元素，而垃先插入的足被放迮找的底部. 迆刊敁 d 能刪除。出找栈顶栈底进找【示例】元素是以al, a2,，an的顾序进栈，退栈的次序却是an, an-1,， al o2、栈的基本运算< 1) InitStack (S)构造一个空栈So(2) StackEmpty (S)判栈空。若S为空栈，则返0TRUE.否则返回FALSE。(3) StackFull (S)判栈满。Z：:S为满栈，则返回TRIE.否则返回

9、FALSE。注总：该运兑只适用丁找的顺序存fifi结构。(4) Push (S，x)进找。W找S不满，则将元素x插入S的栈顶。(5) Pop (S)退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。<6) StackTop (S)取栈顶元素，艺栈S非空，则返回栈顶元素，但不改变栈的状态.队列的定义及基本运算1、定义队列（Queue）是只允许/|: _端进行插入，而在另一端进行删除的运W受 限的线性表队1示怠阁（1）允许删除的一端称为队头（Front）。（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有兀桌时称为空队列。（4）队列亦称作宄进先出（First In First

10、Out）的线性表，简称为PIFO 表。队列的修改足依先进先出的Ki则进忭的。新米的成W总足加入队M （即小 允许'加塞'，每次离开的成员总是队列头上的（不允许中途离队），即当前* W老的'成M离队。【例】在队列中依次加入元索a:，a:，as之后，a:是队头元素，是队尾 元素。退出队列的次序只能是a:，a：,，2、队列的基本逻辑运算< 1） I nit Queue （Q）a空队。构造一个空队列i（2）QueueEmpty （Q）判队空。若队列Q为空，则返回處值，否则返回假值。（3）QueueFull （Q）判队满。微列Q为满，则返回真值，否则返回假值。注意:此操作只

11、适用于队列的顾序存储结构。(4) EnQueue (Q. x)苦队列Q非满.则将元素x捕入Q的队尾。此操作简称入队，(5 ) DeQueue (Q)矜队列Q非空，则刪iQ的队头元素，井返回该元素。此操作简称出队。 < 6 ) QueueFront (Q)打队列Q非空，则返回队尖元紊，但不改变队列Q的状态。三、链表1. 链结点A屮，毎个数IK项W披包穴介：点“屮，一个点足K个类的对».这个类可认叫做 LINK，W为一个链表屮有许多类似的链结点，所以有必嬰用一个小M r链农的类米衣达 链结点。毎个LINK对象屮都fl含一个对卜一个点引用的字段(通常叫做next)但足本 身的对象屮有

12、一个字段衍向对第一个链结点的引用单链表川一组地址f r怠的 <储'V* 7G介放线性表屮的麵/lA *以元糸(数据元蒺的映象)+衍针(衍示后淋乂蒺存储位？i)=结点(衣承数据九名 成 数据允么的映紮)以'钴点的序列'表示线性表称作线性链衣(甲链衣)一中链S玷一种顺序存取的结构.为找第i个数裾元索.必须先找到第i-1个数 据元索。因此，卉找第i个数据乂蒺的堪本操作为：移动指针，比较j和i1. 链接存储方法链接方式介fifi的线性衣簡称为链衣(Linked List)。链农的W体存储农示为： 用一纽任惫的行储中九来存放线性表的结点(这组存储中.沁既4以足连续的， 也4

13、以足不连续的 链衣中结点的逻辑次序和物理次序不一定相h4.为了能正确表示结点间的逻 讯又系.在存储捋个纺点仉的M时，还必须ff储诣zrUt后继点的地址(或RK)(H 总(称为衍计(pointer)成链(link)注总：链式存储是最常用的存储方式之一*它不仅可用来表示线性表,而且可用来表示 什种非线性的数烟结构。2、链农的結点结构| data | next|data 存放结点ftt的数椐域next域-存放结点的11接后继的地址(位W)的ttitl域(链域 注意: 链发通过甸个纺点的®域将线性及的n个姑点按R:逻钔_序链接在、起的. 每个结点只17 个链域的琏农称为单K衣(Single

14、Linked List)【例】线性表(bat. cat. eat. fat. hat，jat. lat. mat)的单链表示如示意M3. iffi针head和终端结点桁针域的农示中链5屮每个结点的存储地址足存放在宂前朽结点next域屮，而开始结点无前 钓.故应没头指针had衔向开始结点，注怠：链表由头指针唯一确定，中.链表"r以用尖柑针的名'?來命名。【例】火指fl名足head的链5可称为S head.终端结点无后继.故终端结点的衍计域为空，即NULLo4. 妒链农的一般ra示法山F我们常常只注1KW点W的逻SH顺#.个又心埒个W点的实牀位K，叫以川箭 头来表示»域

15、屮的折针，线性农(bat, cat, fat. hat，jat, lat. mat)的单链R就可 以农示为下阁形式。5. 屮链衣类喂描述typedef char DataType,结点的数招域炎型为7符typedef struct node /结点类型定义 DataType data; /结点的数据域struct node *nxt;"结点的街针域JListNodetypedef ListNode *LinkList;ListNode *p; LinkList head;注意: -LinkLiSt和ListNode是不网名字的M个栴针炎型(命名的不叫是为了 Ift念 上更明确) &#

16、39;LinkUst类叩的指针变量head表示它是取链表的尖措针 ListNode类咽的指针变量p表示它S指向坫一结点的拘针6. 衔针变量和结点变量衍针变頃|结点变S |IIIIIII| *义丨在变hl说明部分显式记义|在W序执行吋.通过标准| | | |涵数malloc生成|II1III1|取tfi | IK空时，存放K炎点|劣存放纪点ft域A界| | |的地址| |11111t1|操作方式丨通过衍针变R名W问|通过衍针生成、W问和杼放IIIII 生成结点变R的杯袱函数p=( ListNode *)malloc(sizeof(ListNode)：/嘁数malloc分S!-个类喂为ListNo

17、de的结点变员的空问，并将Jt打地址放入指 针变® P屮 释放W点变空M的W准函数free(p)： /W放p所指的W点变尕空问 结点分砑的访问利用钴点变景的名字.p访问钴点分W方法一:(*p).data 和(*p).nxt方法二:p- > data W p- > next 衍i I 变51 P和结>.*.(变* p的关系栴针变® p的侦一结点地址结点变的位一一结点内容(p) data的tfip指针所指结点的data域的fft('p).next的tfi*p后继结点的地址(Cp) next)"p G继结点注意: 打指针变Rp的位为空(NULL

18、),则它不指向点。此时，通过*p 來W问结点就怠味问一个不存在的变Hb从ifuJI起ft!序的错W. 打关桁计类燉的S义和说明方式的洋细解Wfir见.在链衣中捕入结点只爾要修改疳针但同吋，农要在第i个结点之曲摘 入元桌，修改的足笫i-1个钴点的衍针.w此.在中a农屮第i个w点之前逊行插入的咕木採怍为: 找到线性农中第i-i个律点，然后修改其描向后經的指针。 双端链表双端链农1J传统的链农II:常扣似，(LIS它G个新増的特性：即对E/fi 个链结点的 引用.就像对第一个琏结点的引用一样。利个链结点的引川允许像在衣尖-忭，在衣接插入-个链结点。当然.仍 然可以在代通的中链衣的农化插入一个链结点，

19、方让足遍历整个链农II到到达SJd, 但足这种方法效率很低。对KG -个链结点的引用允11像在衣尖-忭.在衣接插入一个链结点。、然.仍 然呵以在&通的荦链衣的？dd捕入一个a钴点，Zfi人足历®个链衣££到到込衣Jd. 01足这种方法效率很低。像农义一样沁问农W的W性，使«链发出适介F叫作通链农小介迚操作的场 介，队列的实现就G这样一个估况、卜_而足一个双端链农的例子。class Link3public long dData; public Link3 next, "public Link3(long d)dData-d, "

20、public void displayLink() System.out.print(dData+_ M);class FirstLastListprivate Link3 first; private Link3 last; /public FirstLastList()first=null;last=null;public boolean isEmpty() return first=null;public void insertFirst(long dd) Link3 newLink=new Link3(dd); if(isEmpty()last=newLink;newLink.next

21、=first; first=newLink;"public void insertLast(long dd)( Link3 newLink=new Link3(dd); if(isEmpty()first=newLink;elselast.next=newLinkllast=newLink,/public long deleteFirst() long temp=first dData; if(first next=null)last 二 null;first=first.next;return temp; /public void displayList() System out

22、print("List (first->last):"); Link3 current=first;while(current!=null) current.displayLink(); current=current. next， )Syst m.out.printing);)/ public class FirstLastApp public static void main(StringO args) FirstLastList theList=new FirstLastList();theList insertFirst(22); theList.insert

23、First(44); theList. insertFirst(66); theList.insertLast(11); theList insertLast(33); theList insertLast(55); theList.displayList(); theList.deleteFirst(), theList deleteFirst(); theList displayList(); 为了简申起兇，在这个程序屮，把毎个a结点屮的数裾宇段个数从网个缩到-个. 这史容W以示铤结点的内容。(C住，在-个正人的EFp屮，可能会打II常多的数据 字段，或片对另外一个对象的引用，那个对象也包

24、介很多数据7段.>这个R序在衣尖和农祕插入三个链点，显示插入G的链衣。然C删除孓两个链结点. 再次显示*注怠在农又正兒捕入操作公触例涟结点进入的顾序.而在衣化的入则保待链W 点进入的_序。双期链表类叫做FirstLastList.它有两个項，first和last.-个抱向链表中的第-个 链结点*另一个析时最后一个链结点*如果链表中只有一个链结点，first和last就都 指向它.如果没介链结点.两S部为Null (ft。这个炎-个新的/法insertLast().这个Zf法在插入个新的链结点，这个过 程B先改变last.next，使其梅向新生成的链结点，然后改变last,使其折仰新的链结

25、 点W入和刪除方法和ff通链衣的相应部分炎似。然iftj. 个捕入方法邢從芩虑一种特殊 情况即插入前链表是空的.如果isEmpty()是真,那么insertFirst()必须把last衔向 新的链结点，insertLast()也必须把first衍何新的链结点.如果用insertFirst()力让i:现在表头插入.first就術向新的链结点，用insertLast()方 法实现在农圮捕入.last就桁叫新的链结点。如K6L农只灯-个链结那么多衣A 析除也是一神特殊愤况：last必須被赋值为null值.不幸的是，用双端链表也不能有助rm除最后一个链钴点，因为没ff个引用抱向倒 数弟二个链结点.如果

26、WG 个链W点被删除，倒第二个链钴点的Next 7段hV汝 变l& Null ffi。为了乃'使的删除WS7 个链结点，況® -个双叫链农。(，然，也4以 iHWffi个琏衣找到个链结点.(11足那托做效率小足很品。有序链表在餅键表屮，数裾是按照关键偵打序排列的。备序链表的劚除常常足只限于删除在 链衣头部的最小链结点。不过.有时也用F_方法和Dlei)方法在整个链衣中搜 索某一特定点。一般.在人多数嬰使用有序数组的场介也可以使用有序链农。有序链衣优r有序数 组的地乃足捕入的速度，另外链衣紂以扩展到全部打效的使川内介，Ifli数组只能AJ限 f个ra定的人小屮。但足，介

27、序链衣实现起來比a序数组史困难一些。后而将<1到一个釘序链表的应用:为数累排序.有序链表也可以用F实现优先级队 尽竹堆足史常用的丈现方法，在打序链衣屮插入一个数据项的Java代码为/在一个印链农屮插入数据项.！7法必须打先拽索链衣，到找到介适的位W: 它恰4f在第-个比它人的数椐项的前而。3锌法找到r®插入的位迓，用通帘的方式捕入数裾項:把新链结点的Next字段很 问卜一个链结点，然后把前一个链结点的Next '/段改为指M新的链结点.然而.X 虑一些特殊情况:键钴点有司1以捕在表头，或者锔在表尾看一下这微代码: Public void insert(long key)

28、Link newLink=new Link(key);Link previous=null; Link current=first; While(current!=null && key>current.dData) P_ous=current; Current=current.next; ) lf(previous=null) First=newLink; Else Previous.next=newLink,newLink next=current; 在链表上移动时.3;要用一个previous引用.这样才能把前一个链结点的Next字段 指M新的链结点.创让新链结点后

29、，把current变歃没为first.准S搜索IE确的插入 点，这时也把previous没为Null俏，这步操作很氓逛，W为后曲要用这个Null俏判 断&否仍在表尖While (Ifi环和以前叫來拽索插入点的代吗炎似.倒是介一个附加的条件。如果当前检 «的链结点的关键tfi不再小f待袖入的链结点的关仉，则循环结束:这足最常见的 w况，即新关aww在铤农屮部的x个地然ifij .如！ current力Null俏，while循环也公伶ik*这种怙况发肀在成/J链 表为空时 如果current在衣头或?5链衣为空，previous将为Nullffi：所以让first析向新的链结 点

30、.否则current处在链农屮部或结叱，就使previous的next 7段衍向新的链绾点。 不论嗎种情况、部让析链结点的Next 7段指向current, ftl果在衣尾，current为Nu II ft，则新链结点的Next 7段也本戍该3为这个tfi (Null) * brfnffifj序链表的W序SortedList java 程序实现了一个 SortedList 类，它拥有 insert()、remove()和 display ListO方法.只有insert()方法与无序链表中的insert()方法不同。package 17序链衣；class Linkpublic long dDa

31、ta; public Link next; public Lmk(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=nu

32、ll; Link current=first; whil(currntl=null && key>current dData) previous=current;current=current next,) if(previous=null)first=newLinkfelseprevious. next=newLink; newLink.next=current;public Link remove()Link temp=first;first=first.next; return temp; /public void displayList()Systm.out pr

33、int(”List (first->last): _): Link current=first;while(current!=null) current.displayLink();current=current.next,) System.out pnntln(WH);) public class SortedLmkApp public static void main(Stnng| args) SortedLisI theSortedList=new SortedList(); theSortedList.insert(20);theSortedList.insert(40);the

34、SortedList displayList();theSortedList.insert(IO);theSortedList.insert(30);theSortedList Jnsert(50);theSortedList displayList();theSortedList remove();theSortedList displayList();System exit(O);在MainOZZ法屮.插入衍为20和40的两个链结点然后丙插入三个链结点，分别 S 10. 30和50u这三个侦分别插在表1、表屮和衣尼。这说明insert()方法iE确地 处理了特殊情况.后刪除了一个链结点，表

35、现出刪除操作总从表尖进行。毎一步 变化后.都显示®个涟衣.双向链表双向链衣也叫双链衣.足链衣的一种，它的每个数据结点屮都fl两个指针.分別指向 直接后继和H接前驱*所以，从双向链农中的任意-个结点幵始，都可以很方便地访M它的前职结点和G继结点 一般我们都构造双W循环链去*/线性表的双W链表介储钴构/ typedef struct DuLNodeElemType data,struct DuLNode "prior,*next;)DuLNode,"DuLinkList;/*带头结点的双向循环链表的*本操作<14个)/void lnitList(DuLinkLi

36、st *L) /"产生空的双向術环链表L 7ftL=(DuLinkList)malloc(sizeof(DuLNode);(L)->next=(*L)->prior=*L;elseexit(OVERFLOW);)void DestroyList(DuLinkList *L> /操作结果：消毁双叫循坏链衣L 7DuLinkList q，p=(*L)->next, /* p fit t>第一个结点 */while(pl=L) P p没到表头7q=p->next;free(p);P=Q.)free(-L);L=NULL;void ClearList(Du

37、LinkList L) /不改变 L */ /初始条件：L b/r在。揀怍纺果：将LifiK为空衣vDuLinkList q,p=L->next; /* p 攢向第一个结点/while(p!=L) /p没到农火7q=p->next;free(p);P=q;L->next=L->prior=L; /头结点的两个指针域均柑向自身/ )Status ListEmpty(DuLinkList L) / W始条件：线件农LC存ft,操作结果：打L为空衣，则返Id TRUE,否则 idM FALSE 7if(L->next=L&&L->prior=L)r

38、eturn TRUE;elsereturn FALSE;int ListLength(DuLinkList L) r初始条件：L己存在。操作结果：返冋L屮数据元蒺个数”int i=0;DuLinkList p=L->next; / p 指向第一个结点/while(p!=L) / p 没到表头 7 i*；p=p->next;return i;Status GetElem(DuLinkList L.int i.ElemType *e) /-当第i个蒺存在时，Kfrt赋给e并返回OK.否则返回ERROR 7 int j=1; /j为计数器/DuLinkList p=L->next;

39、 / p 柑向第一个结点/while(p!=L&&jnext;j+；if(p=L|j>i) r第i个元素不存在7return ERROR;e=p->data; /* 収第 i 个元索/return OK;)int LocateElem(DuLinkList L.EIemType e.StatusCompareXEIemType.Elem Type) P初始条件：L己存在，compare()是数W元索判定函数/r操作结尖：返回L屮第1个与e满足关系compare()的数据元索的位序.7 / 这样的数据元索不存在，則返回衍为0 ，int i=0;DuLinkList p

40、=L->next; /* p 推向第 1 个元素/while(pl=L)i+:if(compare(p->data,e) /找到这的数裾九尜/return i;p=p->next;return 0;)Status PriorElem(DuLinkList L.EIemType cur_e,ElemType *pre_e) /操怍结果：r.: cur_e & L的数据元桌.IL不足第一个.则用pre_e返冋它的 前驱，Vr否则探作失败，pre_e无定义/DuLinkList p=L->next->next; / p 析句第 2 个元麻/while(pl=L)

41、 / p 没到表头/if(p->data=cur_e)pre _e=p->prior->dat a;return TRUE,p 二 p->next;)return FALSE; )Status NsxtEIm(DuLinkList L.EIemTyp cur_,ElmType wnext_e) /探怍结果：cur_ eEL的数裾元痪，fl不-个，则用next_e返冋 它的后继，/r否则操作失败,nxt_无定义/DuLinkList p=L->next->next; / p 衍向第 2 个元索 */while(p!=L) / p 没到农 i 7 if(p-&g

42、t;prior->data=cur_e)"next_e=p->data, return TRUE;p=p->next;)return FALSE; JDuLinkList GetElemP(DuLinkList L,mt i) ' W 加/ r在双向链衣L屮返M第i个元蒺的地址.i为0.返|ul尖幼点的地址。打第i 个元索不存在.*/返l"l NULL /int j； DuLinkList p=L; /p折向头结点7if(i<O|i>ListLength(L) / i 值不合法/return NULL;for(j=1;j<=i;j

43、+)p=p->next;return p; JStatus Listlnsert(DuLinkList L.int i.ElemType e) /- A带尖结点的双链循环线性5L屮第i个之前插入A蒺e.i的介法ffi为 1<i<?< 长+1 /r改进172 18.缶则无法在第衣IC+1个结点之前插入冗桌/DuLinkList p,s;if(i<1|i>ListLength(L)+1) /* iffi不合法 7 return ERROR;p=GetElemP(L,i-1);"在L中确定第i个元素前®的位S柑针p 7 if(1p) r p=N

44、ULL,即第i个元素的前驱不存在(设Jk结点为第1个元索的前驱/ return ERROR;s=(DuLinkList)malloc(sizeof(DuLNodG);if(return OVERFLOW;s>data=e;s->prior=p; P在第卜1个九S之后描入/ s->n ext二p->n ext; p->next->prior=s;p->next=s;return OK;Status ListDelete(DuLinkList LJnt i，ElemType e> r删除带1结点的双链循环线性衣l的® i个元蕤，i的介法仿为

45、农松/ DuLinkList p;/* i值不介法7return ERROR;p=GetElemP(L,i); /在L中确定第i个元隶的位®拊针p/ if('p) P p=NULL,即第i个元素不存在/ return ERROR;=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return OK;void ListTravers(DuLinkList L,void(*visit)(ElemType) !.巾双链淅坏线性农L的交结AHI发.正序对毎个数裾冗蒺

46、调用函数visit() DuLinkList p=L->next; /* p 侑向久结点 */while(pl=L)visit(p->data);p=p->next,printf("n");)void ListTraverseBack(DuLinkList L,void(*visit)(ElemType) /'由双®抛坏线性的火结点出发，逆序对每个数据元东调用凼数visit(). W加!DuLinkList p=L->prior; /* p JdWi 点 7while(p!=L)visit(p->data);p=p->p

47、rior; printf("n");迭代器迭代器足一种对象，它能够用來遍历STL容器屮的部分成全部i蒺，每个迭代器对 象代衣容器屮的确定的地址.迭代器修改了常规指针的接丨I，所m选代器足种槪念 上的抽象:那些行为上象迭代器的东西都苛以叫做迭代器。然而迭代器打很多不同的 能力，它吋以把抽象容器和通用算法有机的统 起來.迭代器捉供一些坫本怏作符：、+、=、!=，=这些视作和C/CW找作array元 素时的柑针接口一致。不M之处在J.-，迭代器是个所谓的smart pointers,只有遇历 y杂数裾结构的能力。WFS运行扒制取决rjt所历的数裾结构，冈此.« .种料

48、器吧別都必须捉供n己的迭代器，少实上甸-种矜器都将u迭代器以嵌套的力式定义 r内部.因此各种迭代器的接11相M，型别却不M.这££接导出了泛型程序设计的槪 念:所有操作行为都使用相同接U，里然它们的墩別不同。功能选代器使开发人员能够在类或纺构屮支持foreach迭代,而不必整个实现lEnumerab le或？MEnumerator接丨I。只耑捉供-个迭代器.即可遍历炎屮的数裾结构。3编i子 器检薄到迭代器时将门动生成lEnumerable接【I或者lEnumerator接口的Current.MoveNext 和 Dispose 力法.特点1. 迭代器是可以返回相同类型值的有

49、序序列的-段代码;2. 迭代器可用作A法、运汀符成get访问器的代W体：3. 迭代器代码使JT yield return通句依次返回每个元索.yield break将终止迭代:4. 可以在类中实现多个迭代器,毎个迭代器都必须像任何类成员，样有惟.的名 称.并且可以在foreach语句中披客户端代码调用:5. 迭代器的返回类艰必须为lEnumerable和lEnumerator屮的任意一种：6. 迭代器S产生仇的打序序列的一个块，不同r打一个 或多个yield 存 在的常规讲块；7迭代器不忡成员，它八实现ffl数成员的方式.理解这一点£很呎贽的. 个通过a代器实现的成w.可以妓it他可

50、能或小可能通过迭代器丈现的成ws溫和 腿:8.迭代器块在c#ifi法屮不足独特的它们在几个方而受到限制，并nt® 作用在函败成M声明的语义上，它们在诮法上只是语句块而己:、递归雄妇是番数调用白身的种特殊的编程技术.其应用主要在以卜儿个方面:阶乘ft java 屮的柚木形AW: Public void mothed «intn)/'l，i满足某条件时: Mothed (n-1 )：递归二分査找Java二分6找实现，欢迎大家提出交流意见.广 名称:Binarysearch功能:实现了折字&找(二分査找)的递#1和非递H算法. 说明：1、要求所査找的数组己有序，并

51、且其中元素己实现Comparable<T>接口，如 nteger、String 等.2> 北递iHfi:找使川 search();，递找HfHl searchRecursively();本®序仅供编学习参冷author: Wmtydate:2008-8-11email: emailwintys/emailclass BinarySearch<T extends Comparable<T» private T data:/要作序的数据public BinarySearch(T data) this.data = data;public int s

52、earch(T key) int low,int high; int mid;if(data = null)return -1,low = 0;high = data.length - 1;while(low <= high)mid = (low + high) / 2;System.out println("mid + mid + mid value:” + datamid);/ if(pareTo(datamid|) < 0)high = mid - 1; else if(key compareTo(datamid) > 0)( low = mid * 1； e

53、lse if(key compareTo(datamid) = 0) return mid, >return -1; private int doSearchRecursively(int low , int high , T key) int mid; int result;if(low <= high) mid = (low + high) / 2; re suit = key compareTo(data|mid|);System.out println(mid + mid + mid value " + datamid|);/ if(result < 0)r

54、eturn doSearchRecursively(low，mid - 1，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)return -1;return doSearchRecursively(0 . data.length - 1 ，key);public static void main(StringO arg

55、s)Integerf data = 1 ,4 ,5 ,8 ,15 ,33 ,48 ,77 .96;BinarySearch<lnteger> bmSearch = new BinarySearch<lnteger>(data); /System.out pnntln(MKy index:” + binSearch search(33);System.out.pnntln(RKey index * + binSearch searchRecursively(3);/String | dataStr = _A_，_C_ /F_，_L_，_N_ /T" /Bmary

56、Search<String> binSearch = new BmarySearch<String>(dataSt 0；/System.out println("Key index+ binSearch search("A"); )递归排序K实在数组的全找序屮完全吋以使用史加易惮简便的写认一一for循环，但足通过 for循环编写数扣今排序耑®打一个先决条件一知道数饥个排序的个数.因为打 n个数裾全梓序就痛®写n个嵌套for循环.因此在写全梓序时一般使用递H方 法.这是我的第一个关F递浦序的见解递W拌序可以无耑C知I徘序数

57、组 的长度，即排序个数！Jt二，不管是使用递归进行数组排序还是使用tor循环进行数组的排序，它们都 S木质都£使用枚举，冈此以出这样一个结论:枚準"I以确保找出埒一种"J*能 的序规则！Jt-2.枚举足列出所介的方法并找出符介耍求的W法，W此Jt灯法效半一定比较 的低.況耍对w进行优化.1能込到较好的效果(递yi的时候jit除所打不吋能的 方案)消除递归消除递yi的祛本思路足用栈來模拟系统的函数调用从而消除递in* 法木上嬰做一卜_三件出：传递参数(包括返回地址)并转到函数入i-i:获得参数 并处理参数：根据传入的返M地址返1"1五、哈希表一般的线性表、M中，记录在结构中的相对位置是随机的即和记呆的关键字之问 小存在确定的关系.在结构屮ft找记氽时芯进行一系列和关键字的比较。这一类 杏找旅进立在"比较”的础上.杏找的效率与比较次数密