计算机考研资料-算法设计题.pdf

《计算机考研资料-算法设计题.pdf》由会员分享，可在线阅读，更多相关《计算机考研资料-算法设计题.pdf（189页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录 线性表算法设计题答案.1 栈和队列算法设计题答案.40 串算法设计题答案.55 数组和广义表算法设计题答案.65 树和二叉树算法设计题答案.80 图算法设计题答案.124 集合算法设计题答案.151 排序算法设计题答案.171彼 性 装 算法设计题答案L 题目分析 因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。LinkedList Union(LinkedList la,lb)/71a,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列

2、，本算法将两链表合并成一个按元素值递减次序排列的单链表。pa=la-next;pb=lb-next;/pa,pb 分别是链表 la 和 1b 的工作指针la-next=null;1a 作结果链表的头指针，先将结果链表初始化为空。while(pa!=null&pb!=null)当两链表均不为空时作if(pa-datadata)r=pa-next;将p a 的后继结点暂存于r。pa-next=la-next;将pa结点链于结果表中，同时逆置。la-next=pa;pa=r;恢复p a 为当前待比较结点。elser=pb-next;/将 p b 的后继结点暂存于r。pb-next=la-next;将

3、pb结点链于结果表中，同时逆置。la-next=pb;pb=r;恢复p b 为当前待比较结点。)while(pa!=null)将la表的剩余部分链入结果表，并逆置。r=pa-next;pa-next=la-next;la-next=pa;pa=r;while(pb!=null)r=pb-next;pb-next=la-next;la-next=pb;pb=r;/算法Union结束。算法讨论上面两链表均不为空的表达式也可简写为while(pa&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个

4、，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。与本题类似的其它题解答如下：(1)问题分析与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三 是 hb链表不能被破坏，即将h b 的结点合并到结果链表时，要生成新结点。LinkedList Union(LinkedList ha,hb)ha和 hb是两个无头结点的数据域值递增有序的单链表，本算法将h b 中并不出现在h a 中的数据合并到ha中，合并中不能破坏hb链表。LinkedList la;la=(Linked

5、List)malloc(sizeof(LNode);la-next=ha;/申请头结点，以便操作。pa=ha;pa是 ha链表的工作指针pb=hb;pb是 hb链表的工作指针pre=la;/pre指向当前待合并结点的前驱。while(pa&pb)if(pa-datadata)/处理 ha 中数据pre-next=pa;pre=pa;pa=pa-next;else if(pa-datapb-data)处理 hb 中数据。r=(LinkedList)malloc(sizeof(LNode);/申请空间r-data=pb-data;pre-next=r;pre=r;将新结点链入结果链表。pb=pb-

6、next;hb链表中工作指针后移。else/处理 pa-data=pb-data;pre-next=pa;pre=pa;pa=pa-next;两结点数据相等时，只将ha的数据链入。pb=pb-next;不要h b 的相等数据if(pa!=null)pre-next=pa;将两链表中剩余部分链入结果链表。else pre-next=pb;free(la);释放头结点.ha,hb指针未被破坏。算法nion结束。(2)本题与上面两题类似，要求结果指针为1c,其核心语句段如下：pa=la-next;pb=hb-next;lc=(LinkedList)malloc(sizeof(LNode);pc=lc

7、;pc是结果链表中当前结点的前驱while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;if(pa)pc-next=pa;else pc-next=pb;free(la);free(lb);释放原来两链表的头结点。算法时间复杂度为0(m+n),其中m 和 n 分别为链表la和 1b的长度。2.题目分析 本组题有6 个，本质上都是链表的合并操作，合并中有各种条件。与前组题不同的是，叙述上是用线性表代表集合，而操作则是求集合的并、交、差(AUB,AAB,A-B)等。本题与上面1.

8、(2)基本相同，不同之处1.(2)中链表是“非递减有序”，(可能包含相等元素)，本题是元 素“递增有序”(不准有相同元素)。因此两表中合并时，如有元素值相等元素，则应删掉一个。LinkedList Union(LinkedList ha,hb)线性表A 和 B 代表两个集合，以链式存储结构存储，元素递增有序。ha和 hb分别是其链表的头指针。本算法求A 和 B 的并集A U B,仍用线性表表示，结果链表元素也是递增有序。pa=ha-next;pb=hb-next;设工作指针 pa 和 pb。pc=ha;pc为结果链表当前结点的前驱指针。while(pa&pb)if(pa-datadata)pc

9、-next=pa;pc=pa;pa=pa-next;else if(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-next;else/7处理 pa-data=pb-data.pc-next=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;free(u);if(pa)pc-next=pa;/若 ha表未空，则链入结果表。else pc-next=pb;若hb表未空，则链入结果表。free(hb);释放hb头结点return(ha);算法Union结束。与本题类似的其它几个题解答如下：(1)解答完全同上2。(2)本题是求交集，即只有同时出现在两

10、集合中的元素才出现在结果表中。其核心语句段如下：pa=la-next;pb=lb-next;设工作指针 pa 和 pb；pc=la;结果表中当前合并结点的前驱的指针。while(pa&pb)if(pa-data=pb-data)交集并入结果表中。pc-next=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;free(u);else if(pa-datadata)u=pa;pa=pa-next;free(u);else u=pb;pb=pb-next;free(u);while(pa)u=pa;pa=pa-next;free(u);/释放结点空间while(pb)u=p

11、b;pb=pb-next;f ree(u);释放结点空间pc-next=null;置链表尾标记。free(1b);注：本算法中也可对B 表不作释放空间的处理(3)本题基本与(2)相同，但要求无重复元素，故在算法中，待合并结点数据要与其前驱比较，只有在与前驱数据不同时才并入链表。其核心语句段如下。pa=Ll-next;pb=L2-next;pa、pb 是两链表的工作指针。pc=Ll;/L1作结果链表的头指针。while(pa&pb)if(pa-datadata)u=pa;pa=pa-next;free(u);/册!j 除 LI 表多余元素else if(pa-datapb-data)pb=pb-

12、next;pb 指针后移else 处理交集元素if(pc=Ll)pc-next=pa;pc=pa;pa=pa-next;处理第一个相等的元素。else if(pc-data=pa-data)u=pa;pa=pa-next;free(u);重复元素不进入LI表。else pc-next=pa;pc=pa;pa=pa-next;交集元素并入结果表。/whilewhile(pa)u=pa;pa=pa-next;free(u);/册 LI 表乘余元素pc-next=null;/置结果链表尾。注：本算法中对L2表未作释放空间的处理。(4)本题与上面(3)算法相同，只是结果表要另辟空间。(5)题目分析 本

13、题首先求B 和 C 的交集，即求B 和 C 中共有元素，再与A 求并集，同时删除重复元素，以保持结果A 递增。LinkedList union(LinkedList A,B,C)A,B和 C 均是带头结点的递增有序的单链表，本算法实现A=AU(BPC),使求解结构保持递增有序。pa=A-next;pb=B-next;pc=C-next;/设置三个工作指针。pre=A;/pre指向结果链表中当前待合并结点的前驱。if(pa-datadata I I pa-datadata)A 中第一个元素为结果表的第一元素。pre-next=pa;pre=pa;pa=pa-next;else jwhile(pb

14、&pc)找B 表和C 表中第一个公共元素。i f(pb-datadata)pb=pb-next;else i f(pb-datapc-data)pc=pc-next;else break;找至I B 表 和 C 表的共同元素就退出while循环。if(pb&pc)/因共同元素而非B 表或C 表空而退出匕面while循环。if(pa-datapb-data)A 表当前元素值大于B 表和C 表的公共元素，先将B 表元素链入。pre-next=pb;pre=pb;pb=pb-next;pc=pc-next;B,C 公共兀素为结果表第一兀素。结束了结果表中第一元素的确定while(pa&pb&pc)w

15、hile(pb&pc)if(pb-datadata)pb=pb-next;else if(pb-datapc-data)pc=pc-next;else break;B 表和C 表有公共元素。if(pb&pc)while(pa&pa-datadata)/先将A 中小于B,C 公共元素部分链入。pre-next=pa;pre=pa;pa=pa-next;if(pre-data!=pb-data)pre-next=pb;pre=pb;pb=pb-next;pc=pc-next;elsepb=pb-next;pc=pc-next;/若 A 中已有.B,C 公共元素，则不再存入结果表。/while(pa

16、&pb&pc)if(pa)pre-next=pa;当B,C 无公共元素(即一个表已空)，将 A 中剩余链入。算法Union结束 算法讨论 本算法先找结果链表的第个元素，这是因为题目要求结果表要递增有序(即删除重复元素)。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A(头结点的头指针)，这时的data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。当然，不要这样作，而直接进入下面循环也可以,但在链入结点时，必须先判断pre是否等于A,这占用了过多的时间。因此先将第一结点链入是可取的。算法中的第二个问题是要求时间复杂度为O(|A|+|B|+|C|)。这就要求各个表的

17、工作指针只能后移(即不能每次都从头指针开始查找)。本算法满足这一要求。最后一个问题是，当 B,C 有一表为空(即B 和 C 已无公共元素时)，要将A 的剩余部分链入结果表。3.题目分析 循环单链表L1和 L2数据结点个数分别为m 和 n,将二者合成一个循环单链表时，需要将个循环链表的结点(从第一元素结点到最后个结点)插入到另一-循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。LinkedList Union(LinkedList LIf L2;int m,n)L1和 L2分别是两循环单链表的头结点的指针，m 和 n 分别是L1和 L2的长度。

18、本算法用最快速度将L1和 L2合并成个循环单链表。if(m0|n0)printf(“表长输入错误n)；exit(0);)if(mn)若mnext!=L1)p=p-next;查最后一个元素结点。p-next=L2-next;将L1循环单链表的元素结点插入到L2的第一元素结点前。L2-next=Ll-next;free(LI);释放无用头结点。处理完m n 情况e l s e 下面处理L2长度小于等于L1的情况 if(n=0)return(LI);/L2 为空表。elsep=L2;while(p-next!=L2)p=p-next;查最后元素结点。p-next=Ll-next;将L2的元素结点插入

19、到L1循环单链表的第一元素结点前。Ll-next=L2-next;free(L2);释放无用头结点。算法结束。类似本题叙述的其它题解答如F：(1)题目分析 本题将线性表1a和 1b连接，要求时间复杂度为0(1),且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。LinkedList Union(LinkedList la,lb)la和 lb是两个无头结点的循环单链表的尾指针，本算法将1b接 在 la后，成为一个单循环链表。q=la-next;q 指 向 la的第一个元素结点。la-next=lb-next;将1b的最后元素结点接到1b的第一元素。lb-next=q;将1b指 向 la的第一

20、元素结点，实现了 1b接 在 la后。return(1b);返回结果单循环链表的尾指针1b。算法结束。算法讨论 若循环单链表带有头结点，则相应算法片段如下：q=lb-next;q 指向1b的头结点；lb-next=la-next;/71b的后继结点为la的头结点。la-next=q-next;la的后继结点为1b的第一元素结点。free(q);释放lb的头结点return(1b);返回结果单循环链表的尾指针lb(2)题目分析 本题要求将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入

21、到单向链表第一元素之前即可。其核心算法片段如下(设两链表均有头结点)q=hb-next;单向循环链表的表头指针hb-next=ha-next;将循环单链表最后元素结点接在ha第一元素前。ha-next=q-next;将指向原单链表第一元素的指针指向循环单链表第一结点free(q);释放循环链表头结点。若两链表均不带头结点，则算法片段如下：q=hb-next;q 指向h b 首元结点。hb-next=ha;hb尾结点的后继是ha第一元素结点。ha=q;头指针指向hb的首元结点。4.题目分析 顺序存储结构的线性表的插入，其时间复杂度为0(n),平均移动近一半的元素。线性表L A 和 L B 合并时

22、，若从第个元素开始，一定会造成元素后移，这不符合本题“高效算法”的要求。另外，题中叙述“线性表空间足够大”也暗示出另外合并方式，即应从线性表的最后一个元素开始比较，大者放到最终位置上。设两线性表的长度各为m 和 n,则结果表的最后一个元素应在m+n位置上。这样从后向前，直到第 个元素为止。PROC Union(VAR LA:SeqList;LB:SeqList)LA和 LB是顺序存储的非递减有序线性表，本算法将LB合并到LA中，元素仍非递减有序。m:=LA.last;n:=LB.last;/m,n 分别为线性表 LA 和 LB 的长度。k:=m+n;k 为结果线性表的工作指针(下标)。i:=m

23、;j :=n;/i,j 分别为线性表LA和 LB的工作指针(下标)。WHILE(i0)AND(j0)DOIF LA.elem i=LB.elem jTHENLA.elemk:=LA.elemi;k:=k-l;i:=i-l;ELSELA.elemk:=LB.elemj;k:=k-l;j:=j-1;WHILE(j0)DO LA.elemk:=LB.elemj;k:=k-l;j:=j-l;LA.last:=m+n;ENDP;算法讨论 算法中数据移动是主要操作。在最佳情况下(LB的最小元素大于LA的最大元素)，仅将LB的n 个元素移(拷贝)到LA中，时间复杂度为0(n),最差情况，LA的所有元素都要移

24、动，时间复杂度为0(m+n)。因数据合并到LA中，所以在退出第一个WHILE循环后，只需要一个WHILE循环，处理L B 中剩余元素。第二个循环只有在LB有剩余元素时才执行，而 在 L A 有剩余元素时不执行。本算法利用了题目中“线性表空间足够大”的条件，“最大限度的避免移动元素”，是“种高效算法”。5.题目分析本题实质上是一个排序问题，要求 不得使用除该链表结点以外的任何链结点空间”。链表.上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。LinkedList LinkListSort(LinkedList l

25、ist)list是不带头结点的线性链表，链表结点构造为data和 link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。p=list-link;p 是工作指针，指向待排序的当前元素。list-link=null;假定第一个元素有序，即链表中现只有一个结点。while(p!=null)r=p-link;r 是 p 的后继。q=list;if(q-datap-data)处理待排序结点p 比第个元素结点小的情况。p-link=list;list=p;链表指针指向最小元素。else 查找元素值最小的结点。while(q-link!=null&q-l

26、ink-datadata)q=q-link;p-link=q-link;将当前排序结点链入有序链表中。q-link=p;p=r;p 指向下个待排序结点。)算法讨论 算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将第i (i l)个元素插入到前面第1至 第 i-l 个元素的有序表时，是将第i个元素先与第i-l 个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比较次数相同，在链表情况下，不移动元素，而是修改结点指针。另一说明是，本题中线性链表l i s t 不带头结点，而且要求“不得使用除该链表以外的任何链结点空间”，所以处理复杂，需要考虑当前结点元

27、素值比有序链表第一结点的元素值还小的情况，这时要修改链表指针l i s t。如 果 l i s t 是头结点的指针，则相应处理要简单些，其算法片段如下：p=l i s t-l i n k;/p指向第一元素结点。l i s t-l i n k=n u l l;有序链表初始化为空while(p!=n u l l)r=p-l i n k;/保存后继q=l i s t;while(q-l i n k!=n u l l&q-l i n k-d a t a d a t a)q=q-l i n k;p-l i n k=q-l i n k;q-l i n k=p;q=r;)6.题目分析 本题明确指出单链表带头

28、结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释，将各结点依次插入到有序链表中。L i n k ed L i s t L i n k L i s t I n s er t S o r t(L i n k ed L i s t l a)l a 是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成递增的有序链表。if(l a-n ex t!=n u l l)/链表不为空表。p=l a-n ex t-n ex t;/p指向第一结点的后继。l a-n ex t-n ex t=n u l l;直接插入原则认为第一元素有序，然后从第

29、二元素起依次插入。while(p!=n u l l)r=p-n ex t;暂存p的后继。q=l a;while(q-n ex t!=n u l l&q-n ex t-d a t a c i a t a)q=q-n ex t;/查找插入位置。p-n ex t=q-n ex t;将p结点链入链表。q-n ex t=p;P=r;与本题有类似叙述的题的解答：(1)本题也是链表排序问题，虽没象上题那样明确要求“利用直接插入的原则”来排序，仍可用上述算法求解,这里不再赘述。7.题目分析 本题要求将个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用NEW过程申请空间，这就是要利用原链表空间，随

30、着原链表的分解，新建链表随之排序。PROC d iscreat(V A R lis th e a d,P,Q:lin k e d lis t)l i s t h e a d是单链表的头指针，链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表l i s t h e a d分解成奇数链表和偶数链表，分解由P和Q指向，且P和Q链表是有序的。P:=N IL;Q:=N IL;P和Q链表初始化为空表。s:=lis th e a d;WHILE(sNIL)DO r:=sA.NEXT;暂存s的后继。IF sA.DATA DIV 2=0 处理偶数。THEN IF P=NIL THEN P:=s

31、;PA.NEXT:=NIL；第一个偶数链结点。ELSEp re:=P;IF p r eA.DATAsA.DATA THENIs7 1.N EX T:=pre;P:=s;插入当前最小值结点修改头指针ELSE WHILE p reA.NEXTONIL DOIF p r eA.NEXTA.DATAsA.DATA THEN .NEXT:=p re;Q:=s;修改头指针。ELSE WHILE p re A.NEXTONIL DO 查找插入位置。IF p r eA.NEXT.DATA next=null/Z初始化为空表。p=A-next;p 为工作指针。B-n ex t=n u ll;B 表初始化。w h

32、 ile(p!=null)r=p-n ex t;暂存p 的后继。i f (p-datanext=B-next;B-next=p;将小于 0 的结点链入 B 表。e ls e p-next=C-next;C-next=p;p=r;p 指向新的待处理结点。)算法结束。算法讨论 因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面(即第一元素之前)。(2)本题同上面第7 题，除个别叙述不同外，本质上完全相同，故不再另作解答。(3)题目分析 本题中的链表有头结点，分解成表A 和表B,均带头结点。分解后的A 表含有原表中序号为奇数的元素，B 表含有原A 表中序号为偶

33、数的元素。由于要求分解后两表中元素结点的相对顺序不变，故采用在链表尾插入比较方便，这使用一指向表尾的指针即可方便实现。void DisCreat3(LinkedList A)人是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A 表中含原表中序号为奇数的结点，B 表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。i=0;1 记链表中结点的序号。B=(LinkedList)malloc(sizeof(LNode);仓 U建 B 表表头B-next=null;B 表的初始化。LinkedList raz rb;ra和 rb将分别指向将创建的A 表和B 表的尾结点。ra=A;rb=

34、B;p=A-next;p 为链表工作指针，指向待分解的结点。A-next=null;置空新的A 表while(p!=null)r=p-next;暂存p 的后继。i+；if(i%2=0)处理原序号为偶数的链表结点。p-next=rb-next;在B 表尾插入新结点；rb-next=p;rb=p;/rb指向新的尾结点；)else 处理原序号为奇数的结点。p-next=ra-next;ra-next=p;ra=p;p=r;将p 恢复为指向新的待处理结点。算法结束8.题目分析 题目要求重排n 个元素且以顺序存储结构存储的线性表，使得所有值为负数的元素移到正数元素的前面。这可采用快速排序的思想来实现，只

35、是提出暂存的第一个元素(枢轴)并不作为以后的比较标准，比较的标准是元素是否为负数。int Rearrange(SeqList a;int n)是具有n 个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线性表a,使所有值为负数的元素移到所有值为正数的数的前面。i =0;j=n-l;i,j 为工作指针(下标)，初始指向线性表a的第1个和第n个元素。t=a O ;暂存枢轴元素。while(i j)while(i =0)j ;/若当前元素为大于等于零，则指针前移。if(i j )a i =a j ;i +;/将负数前移。while(i j&a i 0)i+;/当前元素为负数忖指针后移

36、。if(i j )a j-=a i ;正数后移。)a i =t;将原第一元素放到最终位置。算法讨论 本算法时间复杂度为0 (n)。算法只是按题目要求把正负数分开，如要求统计负数和大于等于零的个数，则最后以t来定。如 t为负数，则 0至 i共 i+1 个负数，n-1-i 个正数(包括零)。另外，题目并未提及零的问题，笔者将零放到正数一边。对此问题的扩充是若元素包含正数、负数和零，并要求按负数、零、正数的顺序重排线性表，统计负数、零、正数的个数。请读者利用上面解题思想自行解答。类似本题的选了 5个题，其解答如下：(1)与上面第8题不同的是，这里要求以a.为参考元素，将线性表分成左右两部分。左半部分

37、的元素都小于等于a 0，右半部分的元素都大于a。，a。位于分界位置上。其算法主要片段语句如下：i=l；j=n;t=a n;暂存参考元素。while(i j)(while(i j&a i =t)i+;当前元素不大于参考元素时，指 针 i后移。if(i j)a j =a i;将大于参考元素的元素后移。while(i t)j-;当前元素大于参考元素时指针前移。if(i j)a i+=a j;将小于参考元素的当前元素前移。a i=t;参考元素置于分界位置。(2)题目分析本题要求将线性表A分成B和 C两个表，表 B和表C不另占空间，而是利用表A的空间，其算法与第8题相同。这里仅把表B和表C另设空间的算法

38、解答如下：void R e a r r a n g e 2(int A fB ,C )线性表A有 n个整型元素，顺序存储。本算法将A拆成B和 C两个表，B中存放大于等于零的元素，C中存放小于零的元素。i=0;i,j,k 是工作指针，分别指向A、B 和 C 表的当前元素。j=k=-l;/j,k 初始化为-1。while(in)if(Ai0)C+k=Ai+;将小于零的元素放入C 表。else B+j=Ai+;将大于零的元素放入B 表。算法讨论本题用维数组存储线性表，结果线性表B 和 C 中分别有j +1 和 k+1个元素。若采用教材中的线性表,则元素的表示作相应改变，例如A.elemi,而最后B

39、和 C 表应置上表的长度，如 B.length=j和 C.length=k(3)本 题 与 第 8 题本质上相同，第 8 题要求分开正数和负数，这里要求分开奇数和偶数，判别方式是ai%2=0,满足时为偶数，反之为奇数。(4)本题与第8 题相同，只是叙述不同。(5)本题与第8 题基本相同，不同之处在于这里的分界元素是整数19(链表中并不要求一定有19)。本题要求用标准pascal描述算法，如下所示。TYPE arr=ARRAYl.1000 OF integer；VAR a：arr；PROCEDURE Rearranges(VAR a：arr)；/a是 n(设 n=1000)个整数组成的线性表，用

40、一维数组存储。本算法将n 个元素中所有大于等于19的整数放在所有小于19的整数之后。VAR i,j,t：integer；BEGINi:=1;j :=n；t:=a 1；i,j 指示顺序表的首尾元素的下标，t 暂存分界元素WHILE(ij)DOBEGINWHILE(i=19)DO j:=j-l；IF(ij)THEN BEGIN A i :=Aj;i:=i+l END：WHILE(ij)AND(a i 19)DO i:=i+l；IF(inext；p 为工作指针。指向待处理的结点。假定链表非空。pre=L；/pre指向最小值结点的前驱。q=p；q 指向最小值结点，初始假定第一元素结点是最小值结点。wh

41、ile(p-next!=null)if(p-next-datadata)pre=p；q=p-next；查最小值结点p=p-next；指针后移。pre-next=q-next；从链表上删除最小值结点free(q)；释放最小值结点空间 结束算法deleteo 算法讨论算法中函数头是按本教材类C 描述语言书写的。原题中void delete(linklist&L),是按C+的“引用”来写的，目的是实现变量的“传址”，克服了 C 语言函数传递只是“值传递”的缺点。10.题目分析本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下(不

42、是删除并回收空间)，再插入到链表的最前面。LinkedList delinsert(LinkedList list)list是非空线性链表，链结点结构是(data,link),data是数据域，link是链域。本算法将链表中数据域值最小的那个结点移到链表的最前面。p=list-link；/p 是链表的工作指针pre=list；pre指向链表中数据域最小值结点的前驱。q=p；q 指向数据域最小值结点，初始假定是第一结点while(p-link!=null)if(p-link-datadata)pre=p；q=p-link；)找至新的最小值结点；p=p-link；)if(q!=list-link)

43、若最小值是第一元素结点，则不需再操作pre-link=q-link；将最小值结点从链表上摘卜；q-link=list-link；将q 结点插到链表最前面。list-link=q；)算法结束 算法讨论算法中假定list带有头结点，否则，插入操作变为q-link=list；list=qo1L 题目分析 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点(p 结点，前驱结点，前驱的前驱结点，后继结点)六条链。void Exchange(LinkedList p)p 是双向循环链表中的一个结点，本算法将p 所指结点与其前驱结点交换。q=p-llink；q-llink-rlink=p；p 的前驱的前

44、驱之后继为pp-llink=q-llink；p 的前驱指向其前驱的前驱。q-rlink=p-rlink；p 的前驱的后继为p 的后继。q-llink=p；/p 与其前驱交换p-rlink-llink=q；p 的后继的前驱指向原p 的前驱p-rlink=q；p 的后继指向其原来的前驱 算法exchange结束。12.题目分析顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x 的元素”，这里应使用折半查找方法。void SearchExchangeInsert(ElemType a ；ElemType x)a 是具有n个元素的递增有序线性表，顺序存储。本

45、算法在表中查找数值为x 的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序。low=0；high=n-l；while(low=high)mid=(low+high)/2；if(amid=x)break；else if(a mid high)查找失败，插入数据元素x for(i=n-l；ihigh；i-)a i+1 =a i；后移元素。a i+1 =x；插入 x。)结束插入 结束本算法。算法讨论 首先是线性表的描述。算法中使用一维数组a 表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体,对元素的引用应使用a.elemi。另外元素类型就假定是El

46、emType,未指明具体类型。其次，C 中一维数组下标从0 开始，若说有n 个元素的一维数组，其最后一个元素的下标应是n-lo第三，本算法可以写成三个函数，查找函数，交换后继函数与插入函数。写成三个函数显得逻辑清晰，易读。13.题目分析 判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。int de(Linked

47、List h,int n)/h 是带头结点的n 个元素单链表，链表中结点的数据域是字符。本算法判断链表是否是中心对称。char s ;int i=l；i 记结点个数，s 字符栈p=h-next;p 是链表的工作指针，指向待处理的当前元素。for(i=l；idata；p=p-next；i ;恢复最后的i 值if(n%2=l)p=p-next;若n 是奇数，后移过中心结点。while(p!=null&s i =p-data)i-；p=p-next；测试是否中心对称。if(p=null)return(1)；链表中心对称else return(0)；链表不中心对称 算法结束。算法讨论算法中先将“链表的

48、前一半”元素(字符)进栈。当n为偶数时，前一半和后一半的个数相同；当 n 为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出while循环，不再进行比较。14.题目分析 在单链表中删除自第i 个元素起的共len个元素，应从第1 个元素起开始计数，记到第i 个时开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A 链表中删除自第i个起的len个结点。这时应继续查到A 的尾结点，得到删除元素后的A 链表。再查B 链表的第j个元素，将 A链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i,

49、len和 j 的合法性。LinkedList Dellnsert(LinkedList heada,headb,int i,j,len)heada和 headb均是带头结点的单链表。本算法删除heada链表中自第i 个元素起的共len个元素，然后将单链表heada插入到headb的第j 个元素之前。if(il I I lenl|jl)printf(参数错误n)；exit(0)；参数错，退出算法。P=heada；p 为链表A 的工作指针，初始化为A 的头指针，查到第i 个元素时，p 指向第i-l个元素k=0；计数while(p!=null&knext；if(p=null)printf(给的1 太

50、大n，i)；exit(0)；i 太大，退出算法q=p-next；q 为工作指针，初始指向A 链表第一个被删结点。k=0;while(q!=null&knext；free(u);删除结点，后移指针。if(klen)printf(给的next=q；A 链表删除了 len个元素。if(heada-next!=null)/7heada-next=null说明链表中结点均已删除，无需往B 表插入while(p-next!=null)p=p-next；找 A 的尾结点。q=headb；q 为链表B 的工作指针。k=0；计数while(q!=null&knext;查找成功时，q 指向第j-1个结点if(q=