《数据结构》课程教学资源（试卷习题）数据结构考研试题集锦（共十一章，含参考答案）

第2章线性表 ∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha中的数据合并到ha中， 合并中不能破坏 LinkedL.ist h h=LinkedL ist)m albc(sizeofLN ode)): nex仁ha∥由请头结占，以便操作 pa=ha; ∥pa是ha链表的工作指针 pb=hb: ∥pb是hb链表 e指向当前特合指 并结点的前驱。 (pa-> pb->daa)∥处理ha中数据 eke ifpa>dat>pb->daa)∥处理hb中数据 =LinkedList0maoc(sizeof0Node):∥申请空间 r>data=pb->data:pre->nextr: pc=r:∥将新结点链入结果链表。 pb=pb->next∥hb链表中工作指针后移 eke∥处理par>dat=pb->daa ne next两结点数据相等时，只将ha的数据链入。 fpa上nuIDpre>nex卡pa:∥将两链表中剩余部分链入结果链表」 头结点，hahb指针未被破坏。 ②)本题与上面两题类似，要求结果指针为上，其核心语句段如下： k=(LinkedList)m albc(sizeofLN ode)): pcc:∥pc是结果链表中当前结点的前驱 whil(pa pb) if(pa->datpb->data) hexepapc-pap pb pc=pbo pa>next: pb->next: if(pa)p 0):释放原来两链表的头结点 算法时间复杂度为0(m+n) 其中m和n分别为链表h和b的长度。 [题目分析]本组题有6个，本质上都是链表的合并操作，合并中有各种条件。与前组题不同的是，叙述上是用线性表代表集 而操作则是求集 合的并、交、差(AUB,AnB, A-B 上面 (2) 1链表 递减有序” (可能包含相等元素)，本题是元素“递增有 中合并时，如有元素值相等元素，则应刷掉一个。 性去A和代 以特式存储结均存储 元素递增有序。ha和hb分别是其链表的头指针。本算法求A和B 的并集AUB,仍用线性表表 结果链表元素也是递增有序。 {pa-ha->nextpb=hb>next∥设工作指针pa和pb。 pc=ha∥pc为结果链表当前结点的前驱指针。 whie(pa&&pb】 if(pa->data<pb->data) pb-> e处 -P ob->next ->nex pa >next u=pb pb=pb->nextfice (u) fa)pc->next-pa:∥若ha表未空，则链入结果表 eepc->nex卡pb;∥若hb表未空，则链入结果表。 firee(hb):∥释放hb头结点 retum (ha)

第2章 线性表 ∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏 hb链表。 ｛LinkedList la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha;∥申请头结点，以便操作。 pa=ha; ∥pa是ha链表的工作指针 pb=hb; ∥pb是hb链表的工作指针 pre=la; ∥pre指向当前待合并结点的前驱。 while(pa&&pb) if(pa->data<pb->data)∥处理ha中数据 {pre->next=pa;pre=pa;pa=pa->next;} else if(pa->data>pb->data)∥处理hb中数据。 {r=(LinkedList)malloc(sizeof(LNode));∥申请空间 r->data=pb->data; pre->next=r; pre=r;∥将新结点链入结果链表。 pb=pb->next;∥hb链表中工作指针后移。 } else∥处理pa->data=pb->data; {pre->next=pa; pre=pa; pa=pa->next;∥两结点数据相等时，只将ha的数据链入。 pb=pb->next;∥不要hb的相等数据 } if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。 else pre->next=pb; free(la);∥释放头结点.ha,hb指针未被破坏。 }∥算法nion结束。 (2)本题与上面两题类似，要求结果指针为lc，其核心语句段如下： pa=la->next;pb=hb->next; lc=(LinkedList )malloc(sizeof(LNode)); pc=lc;∥pc是结果链表中当前结点的前驱 while(pa&&pb) if(pa->data<pb->data) {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);∥释放原来两链表的头结点。 算法时间复杂度为O（m+n），其中m和n分别为链表la和lb的长度。 2．[题目分析]本组题有6个，本质上都是链表的合并操作，合并中有各种条件。与前组题不同的是，叙述上是用线性表代表集 合，而操作则是求集合的并、交、差（A∪B，A∩B，A-B）等。 本题与上面1．（2）基本相同，不同之处1．（2）中链表是“非递减有序”，（可能包含相等元素），本题是元素“递增有 序”（不准有相同元素）。因此两表中合并时，如有元素值相等元素，则应删掉一个。 LinkedList Union(LinkedList ha,hb) ∥线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分别是其链表的头指针。本算法求A和B 的并集A∪B，仍用线性表表示，结果链表元素也是递增有序。 { pa=ha->next;pb=hb->next;∥设工作指针pa和pb。 pc=ha;∥pc为结果链表当前结点的前驱指针。 while(pa&&pb) if(pa->data<pb->data) {pc->next=pa;pc=pa;pa=pa->next;} else if(pa->data>pb->data) {pc->next=pb;pc=pb;pb=pb->next;} else∥处理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); http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 5／24 页）2010-4-15 11:01:08

第2章线性表 l∥算法nnn结束 与本题类似的其它几个题解答如下： )解答完全同上2 ②)本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下： pa〉nextpb=b>next∥政L作指pa和pb 表中当前合并结点的前驱的指针。 pb if(pa b->da)∥交集并入结果表中。 hmh=n eke if(pa>dat pb->data)u=papa=pa>nextfiree(u) eke u=pb:pb=pb->next;fiee(u) wh业pa){u=pa:pa-pa->next:free(u)}/∥释放 结点空 whie (pb)u=pb:pb nex ee仙)∥释放结点空间 对B表不作释放空间的处理 基本与 2)相同，但要求无重复元素 故在算法中，待合并结点数据要与其前驱比较，只有在与前驱数据不同时才并 入链表。其核心语句段如下。 pFL1->nextpb=L2->next∥pa、pb是两链表的工作指针。 pc=L1:∥L1作结果链表的头指针。 w hie (pa&pb) if(pa->data<pb-> a)u=papa-pa>next.fice(@)小∥别除Ll表多余元素 aa)pb=pb->next∥pb指针后移 if(pe 个的元 ke if(pc ∥重复元素不进入L1表。 ee{pc>nex卡papc=papa=pa->next∥交集元素并入结果表。 ∥whe whie(pa)u=papa=pa next.firee(u)}∥删Ll表剩余元素 pe-nexnul 置结 本法 的处玉 C5)分析本题首先求B和C的交集 果表要 中有元素，再与A求并集，同时制除重复元素，以保持结果 ∥AB和C均是带头结点的递增有序的单链表，本算法实现A=AU(B∩C),使求解结构保持递增有序 paFA->nextpba=B->nextpc=C->next/设置三个工作指针。 p=A;∥p指向结果链表中当前待合并结点的前驱。 foar>daa<pb>datalpa->daa<pc>da)∥A中第一个元素为结果表的第一元素。 eC表中第 个公共元素。 fipb->d dat)pb pb->nex ke hmak ∥找到B表和C表的共同元素就退出whk循环。 fbk&pc)∥因共同元素而非B表或C表空而退出上面wh正循环。 pa>da>pb->daa)∥A表当前元素值大于B表和C表的公共元素，先将B表元素 链入 pre-pb pb=pb->nextpo=pc->next 结T钻果表中第素的确定 Whi正pak&pbk&pc) whipbw&pc) if(pb->dat<pc->data)pb=pb->next eke ifpb->data>pc->data)pc=pc->next eke break:∥B表和C表有公共元素。 &pa>dat<pb->data pbpre=pb pb=pb->nextpc=pe->next p/.bjliong.com /ca/ka nAan02h每（第6/24页）2010-4-15110108

第2章 线性表 }∥算法Union结束。 与本题类似的其它几个题解答如下： (1) 解答完全同上2。 (2) 本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下： 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->data<pb->data) {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=pb; pb=pb->next; free(u);}∥释放结点空间 pc->next=null;∥置链表尾标记。 free(lb); ∥注： 本算法中也可对B表不作释放空间的处理 （3）本题基本与（2）相同，但要求无重复元素，故在算法中，待合并结点数据要与其前驱比较，只有在与前驱数据不同时才并 入链表。其核心语句段如下。 pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。 pc=L1;∥L1作结果链表的头指针。 while(pa&&pb) if(pa->data<pb->data) {u=pa;pa=pa->next;free(u);}∥删除L1表多余元素 else if (pa->data>pb->data) pb=pb->next; ∥pb指针后移 else ∥处理交集元素 {if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元素。 else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元素不进入L1表。 else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。 } ∥while while(pa) {u=pa;pa=pa->next;free(u);} ∥ 删L1表剩余元素 pc->next=null; ∥置结果链表尾。 注： 本算法中对L2表未作释放空间的处理。 （4） 本题与上面（3）算法相同，只是结果表要另辟空间。 （5） [题目分析]本题首先求B和C的交集，即求B和C中共有元素，再与A求并集，同时删除重复元素，以保持结果A递增。 LinkedList union(LinkedList A,B,C) ∥A,B和C均是带头结点的递增有序的单链表，本算法实现A= A∪（B∩C），使求解结构保持递增有序。 {pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。 pre=A; ∥pre指向结果链表中当前待合并结点的前驱。 if(pa->data<pb->data||pa->data<pc->data)∥A中第一个元素为结果表的第一元素。 {pre->next=pa;pre=pa;pa=pa->next;} else{while(pb&&pc) ∥找B表和C表中第一个公共元素。 if(pb->data<pc->data)pb=pb->next; else if(pb->data>pc->data)pc=pc->next; else break; ∥找到B表和C表的共同元素就退出while循环。 if(pb&&pc)∥ 因共同元素而非B表或C表空而退出上面while循环。 if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素，先将B表元素 链入。 {pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;} ∥ B，C公共元素为结果表第一元素。 }∥结束了结果表中第一元素的确定 while(pa&&pb&&pc) {while(pb&&pc) if(pb->data<pc->data) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; ∥B表和C表有公共元素。 if(pb&&pc) {while(pa&&pa->data<pb->data) ∥先将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;} http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 6／24 页）2010-4-15 11:01:08

第2章线性表 eeob=pb->nextpc=-pc>nexd∥若A中已有B,C公共元素，则不再存入结果表 }∥while(pas&nh&&nc fna)pe>nex卡pa:∥当B,C无公共元素（即一个表已空），将A中剩余链入。 }∥算法知nDn结束 [算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即别除重复元素）。这就要求当前待合 并到结果表的元素要与 由于 peFA 或无意义，不能与后继比较元素大小，因此 就指多 样作， 木算法满足这是要 求时间复杂度为 取 AB+D。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始 查找 最后一个问题是， 当B,C有一表为空（即B和C己无公共元素时） 要将A的剩余部分链入结果表 3.[题目分析]循环单链表L1和L2数据结点个数分别为加和，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第 元素结点到最后一个结点)插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点 个数少的链表查其尾结点。 kedl istL1,12:intm n) 算法 用最快速度 成 林日：分是1和长度。 资错误n”) ,则查L1循环单链表的最后一个结点。 (fm=0)etum4,2):/L1为空表。 ekep=Ll; wh正p>next-L1)p=p>next∥查最后一个元素结点 p>nex卡L2>next∥将L1循环单链表的元素结点插入到L2的第一元素结点前。 0》释放无用头结点。 }∥处理完m《n情况 ee∥下面处理L2长度小于等于L1的情况 {f血==0)eum41):∥L2为空表。 eke(p=L2: h->nextL2)p=p->next∥查最后 元素结点 >nxt∥将L2的元素结点插入到L1循环单链表的第一元素结点前。 成无头结点。 }∥算法结束 类似本题叙述的其它题解答如下： )[题目分析]本题将线性表和b连接，要求时间复杂度为0(1)，且占用辅助空间尽量小。应该使用只设尾指针的单循环链 表。 的循环单表的指针本算法将接在h后，成为一个单循环链表 >next b一>nex∥将b的最后元素结点接到b的第一元素。 b->nex卡q: ∥将b指向h的第一元素结点，实现了b接在h后。 retum(b) ∥返回结果单循环链表的尾指针b。 算法结束。 [算法讨论]若循环单链表带有头结点，则相应算法片段如下： L 继结点为的头结 点 /释放b的头结点 后继结点为b的第一元素结 etum):∥返回结果单循环链表的尾指针b。 (2)[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带 尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入到单向链表第一元素之前即可。 其核心算法片段如下 (设两链表均有头结点 ∥单向循 >nexhanex七∥将盾 单表素结点接在第一元素前。 mau0 cun02h年（第7/2页）20104-511010

第2章 线性表 else{pb=pb->next;pc=pc->next;}∥ 若A中已有B，C公共元素，则不再存入结果表。 } }∥ while(pa&&pb&&pc) if(pa) pre->next=pa; ∥当B，C无公共元素（即一个表已空），将A中剩余链入。 }∥算法Union结束 [算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。这就要求当前待合 并到结果表的元素要与其前驱比较。由于初始pre=A（头结点的头指针），这时的data域无意义，不能与后继比较元素大小，因此 就需要确定第一个元素。当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于A，这占用 了过多的时间。因此先将第一结点链入是可取的。 算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始 查找）。本算法满足这一要求。 最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。 3．[题目分析]循环单链表L1和L2数据结点个数分别为m和n ，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第 一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点 个数少的链表查其尾结点。 LinkedList Union(LinkedList L1,L2;int m,n) ∥L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。 ∥本算法用最快速度将L1和L2合并成一个循环单链表。 {if(m<0||n<0) {printf(“表长输入错误\n”)；exit(0);} if(m<n) ∥若m<n，则查L1循环单链表的最后一个结点。 {if(m==0)return(L2);∥L1为空表。 else{p=L1; while(p->next!=L1) p=p->next;∥查最后一个元素结点。 p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。 L2->next=L1->next; free(L1);∥释放无用头结点。 } }∥处理完m<n情况 else∥ 下面处理L2长度小于等于L1的情况 {if(n==0)return(L1);∥L2为空表。 else{p=L2; while(p->next!=L2) p=p->next;∥查最后元素结点。 p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。 L1->next=L2->next; free(L2);∥释放无用头结点。 } }∥算法结束。 类似本题叙述的其它题解答如下： （1）[题目分析]本题将线性表la和lb连接，要求时间复杂度为O（1），且占用辅助空间尽量小。应该使用只设尾指针的单循环链 表。 LinkedList Union(LinkedList la,lb) ∥la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为一个单循环链表。 { q=la->next; ∥q指向la的第一个元素结点。 la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。 lb->next=q; ∥将lb指向la的第一元素结点，实现了lb接在la后。 return(lb); ∥返回结果单循环链表的尾指针lb。 }∥算法结束。 [算法讨论]若循环单链表带有头结点，则相应算法片段如下： q=lb->next; ∥q指向lb的头结点； lb->next=la->next; ∥lb的后继结点为la的头结点。 la->next=q->next; ∥la的后继结点为lb的第一元素结点。 free(q); ∥释放lb的头结点 return(lb); ∥返回结果单循环链表的尾指针lb。 （2）[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带 尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入到单向链表第一元素之前即可。 其核心算法片段如下（设两链表均有头结点） q=hb->next; ∥单向循环链表的表头指针 hb->next=ha->next; ∥将循环单链表最后元素结点接在ha第一元素前。 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 7／24 页）2010-4-15 11:01:08

第2章线性表 ha->nex=q->nex ∥将指向原单链表第一元素的指针指向循环单链表第一结点 la) 川释放循环链表头结点 若两链表均不带头结点，则算法片段如下： q=hb->next: ∥a指向hb首元结点 hb->next=ha: hb尾结点的后继是ha第一元素结点。 十猫回hb的自元 ]顺序 指 的不架 其时回复杂度 0 平均移动近一半的 大并时 若从 要 个元素开始比 大著到最终位置上：设两线性表的长度各为加和 元素应在m+位置上。这样从后向前，直到第一个元素为止。 足结果表的最后 PROC Inion AR LA Seal istibseal ist) ∥LA和LB是顺序存储的非递减有序线性表，本算法将LB合并到LA中，元素仍非递减有序。 m中：公为结果线别为线性表 m =LA.hstn=LB.hst://m A和LB的长度。 线性表LA和LB的工作指针（下标）。 [il>=LB.ekm [i TH EN CLA.ekm [k]=LA.ekem [ilk=k-1:i=i13] ELSE[LA.ekm [k]=LB.elem [i*=k-1:i=j1] W H ILE(0)D0 [LA.ekm [k]=LB.ekem [jk=k-1:=Hj LA.ast=m+n; 算法过论算 移动 LA的 情况 LB的最 的最大元素） 拷贝 到 E循环月 时不 题目分析]本题实质上是一个排序问题， 要求“不得使用除该链表结点以外的任何链结点空间”。链表上的排序采用直接插入 排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 LnkedL istL nkL stSortL nkedL ist hst s是 带头结 性链表，链表结点构造为daa和mk两个域，daa是数据域，k是指针域。本算法将该链表按结点数据域 的值的大 F指 个结占 =p>k:∥r是p的后继 =list fq->da>p->dan)∥处理待排序结点p比第一个元素结点小的情况。 tp:∥链表指针指向最小元素 ee∥查找元素值最小的结点 h ink: p>mk=q>mk/将当前排序结点链入有序链表中。 a->link=p: p=r:∥p指向下个待排序结点。 [算法讨论]算法时间 朵度的 与用顺序存储结构 的情 生情况均是 存储结 素 另一说明是，本题中线性链表不带头结点， 而是修改结息不得伟用除该链表以外的任何链结空间“，所以处理有办 虑当前结点元素值比有序链表第一结点的元素值还小的情况，这时要修改链表指针s。如果是头结点的指针，则相应处理要简 单些，其算法片段如下： D=t〉mk∥D指问第 一元素结点 有序鞋表初始化 htpww.biliong.co■/a/oya/iooya/u2hm(第8/24页)20104H511010g

第2章 线性表 ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结点 free(q); ∥释放循环链表头结点。 若两链表均不带头结点，则算法片段如下： q=hb->next; ∥q指向hb首元结点。 hb->next=ha; ∥hb尾结点的后继是ha第一元素结点。 ha=q; ∥头指针指向hb的首元结点。 4．[题目分析]顺序存储结构的线性表的插入，其时间复杂度为O（n），平均移动近一半的元素。线性表LA和LB合并时，若从 第一个元素开始，一定会造成元素后移，这不符合本题“高效算法”的要求。另外，题中叙述“线性表空间足够大”也暗示出另 外合并方式，即应从线性表的最后一个元素开始比较，大者放到最终位置上。设两线性表的长度各为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;j:=n; ∥i，j分别为线性表LA和LB的工作指针（下标）。 WHILE(i>0)AND(j>0)DO IF LA.elem[i]>=LB.elem[j] THEN[LA.elem[k]:=LA.elem[i];k:=k-1;i:=i-1;] ELSE[LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] WHILE(j>0) DO [LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] LA.last:=m+n; ENDP; [算法讨论]算法中数据移动是主要操作。在最佳情况下（LB的最小元素大于LA的最大元素），仅将LB的n个元素移（拷贝）到LA 中，时间复杂度为O（n），最差情况，LA的所有元素都要移动，时间复杂度为O（m+n）。因数据合并到LA中，所以在退出第一 个WHILE循环后，只需要一个WHILE循环，处理LB中剩余元素。第二个循环只有在LB有剩余元素时才执行，而在LA有剩余元素 时不执行。本算法利用了题目中“线性表空间足够大”的条件，“最大限度的避免移动元素”，是“一种高效算法”。 5．[题目分析]本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链结点空间”。链表上的排序采用直接插入 排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 LinkedList LinkListSort(LinkedList list) ∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域 的值的大小，从小到大重新链接。 {p=list->link; ∥p是工作指针，指向待排序的当前元素。 list->link=null;∥假定第一个元素有序，即链表中现只有一个结点。 while(p!=null) {r=p->link; ∥r是p的后继。 q=list; if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况。 {p->link=list; list=p;∥链表指针指向最小元素。 } else∥查找元素值最小的结点。 {while(q->link!=null&&q->link->data<p->data)q=q->link; p->link=q->link;∥将当前排序结点链入有序链表中。 q->link=p; } p=r;∥p指向下个待排序结点。 } } [算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将第i(i>1)个元素插入到前面第1至第i-1个元素 的有序表时，是将第i个元素先与第i-1个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比 较次数相同，在链表情况下，不移动元素，而是修改结点指针。 另一说明是，本题中线性链表list不带头结点，而且要求“不得使用除该链表以外的任何链结点空间“，所以处理复杂，需要考 虑当前结点元素值比有序链表第一结点的元素值还小的情况，这时要修改链表指针list。如果list是头结点的指针，则相应处理要简 单些，其算法片段如下： p=list->link;∥p指向第一元素结点。 list->link=null;∥有序链表初始化为空 while(p!=null) {r=p->link;∥保存后继 q=list; http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 8／24 页）2010-4-15 11:01:08

第2章线性表 whib(-lik=n q-r: 6。[题目分析]本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链 表。这就要求从第二结点开释，将各结点依次插入到有序链表中。 带头 点的 据城是正整数。本算法利用直接插入原则将链表整理成递增的有序表 结占的后继 a>next>nex Enul正直接插入原则认为第 一元素有序，然后从第二元素起依次插入。 whie(p=nuD eD->next:∥新存D的后继。 g=a: whi止g>next长nul&q next >c p>daa)q=q>next∥查找插入位置。 q>next∥将p结点链入链 q->nexEp p-r 与本题有类似叙述的题的解答： ()本题也是链表排序问题，虽没象上题那样明确要求“利用直接插入的原则”来排序，仍可用上述算法求解，这里不再赘述。 题目分析本题要求 链表分解成两个链衣 间，随着原链表的分解，新建链表随之排序。 ~链表都要有序，两链表建立过程中不得使用NEW过程申请空间，这就 PRoC di :m 数链表 一个整数域DATA和指针域NEXT组成。本算法将链表shad分解成奇数链表和偶 是有序 P=N1Q=N1:P和Q链表初始化为空表。 s=listhead W H LLE (SK>N L)DO r=s .NEXT; ∥暂存s的后继 DATA DIV 2= 处理偶 FP=N I TH EN [P=sP"NEXT=NLJ∥第一个偶数链结点。 eP=s:∥插入当前最小值结点修改头指针] IF pre.NEXTDATA<sDATA TH EN Dre=pre".NEXT:∥查找插入位置。 s.NEXT=pre'.N EXT:∥链入此结点。 pre N EXT=s: TH EN [Q=sa.NEXT=NL]∥第一奇数链结点。 ELSE (P IFpre".DATA>SDATA TH EN [S NEXT=pE:Q=]∥修改头指针。 ELSE [W H ILE pre".N EXT<>NLDO∥查找插入位置。 IF pre'.N EXT"DATA<s'.DATA TH EN pre=pre".NEXT: s .NEXT =pre".NEXT:∥链入此结点。 pre".NEXT=s; ]∥结束奇数链结点 指向新的待 占 /结束HLE6>1D0 ENDP:∥结束整个算法。 [算法讨论]由于算法要求“不得使用NEW过程申请空间，也没明确指出链表具有头结点，所以上述算法复杂些，它可能需要在 个结点前插入新结 点情况，算法会 是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0(DATADN2=O)判断的。 类似本题的其它题解答如下：

第2章 线性表 while(q->link!=null && q->link->data<p->data)q=q->link; p->link=q->link; q->link=p; q=r; } 6．[题目分析]本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链 表。这就要求从第二结点开释，将各结点依次插入到有序链表中。 LinkedList LinkListInsertSort(LinkedList la) ∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成递增的有序链表。 {if(la->next!=null)∥链表不为空表。 {p=la->next->next;∥p指向第一结点的后继。 la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插入。 while(p!=null) {r=p->next;∥暂存p的后继。 q=la; while(q->next!=null&&q->next->data<p->data)q=q->next;∥查找插入位置。 p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; } 与本题有类似叙述的题的解答： （1）本题也是链表排序问题，虽没象上题那样明确要求“利用直接插入的原则”来排序，仍可用上述算法求解，这里不再赘述。 7．[题目分析]本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用NEW过程申请空间，这就 是要利用原链表空间，随着原链表的分解，新建链表随之排序。 PROC discreat(VAR listhead,P,Q:linkedlist) ∥listhead是单链表的头指针，链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表listhead分解成奇数链表和偶 数链表，分解由P和Q指向，且P和Q链表是有序的。 P:=NIL;Q:=NIL;∥P和Q链表初始化为空表。 s:=listhead; WHILE(s<>NIL)DO [r:=s^.NEXT; ∥暂存s的后继。 IF s^.DATA DIV 2=0 ∥处理偶数。 THEN IF P=NIL THEN[P:=s;P^.NEXT:=NIL;] ∥第一个偶数链结点。 ELSE[pre:=P; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre;P:=s;∥插入当前最小值结点修改头指针] ELSE[WHILE pre^.NEXT<>NIL DO IF pre^.NEXT^.DATA<s^.DATA THEN pre:=pre^.NEXT;∥查找插入位置。 s^.NEXT:=pre^.NEXT; ∥链入此结点。 pre^.NEXT:=s; ] ] ELSE∥处理奇数链。 IF Q=NIL THEN[Q:=s;Q^.NEXT:=NIL;] ∥第一奇数链结点。 ELSE[pre:=Q; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre; Q:=s; ]∥修改头指针。 ELSE[WHILE pre^.NEXT<>NIL DO ∥查找插入位置。 IF pre^.NEXT^.DATA<s^.DATA THEN pre:=pre^.NEXT; s^.NEXT:=pre^.NEXT;∥链入此结点。 pre^.NEXT:=s; ] ]∥结束奇数链结点 s:=r;∥s指向新的待排序结点。 ]∥结束“WHILE(s<>NIL)DO” ENDP；∥结束整个算法。 [算法讨论]由于算法要求“不得使用NEW过程申请空间，也没明确指出链表具有头结点，所以上述算法复杂些，它可能需要在 第一个结点前插入新结点，即链表的头指针会发生变化。如有头结点，算法不必单独处理在第一个结点前插入结点情况，算法会 规范统一，下面的（1）是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0（DATA DIV 2=0）判断的。 类似本题的其它题解答如下： http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 9／24 页）2010-4-15 11:01:08