发布时间 : 星期四 文章最完整的数据结构1800题含答案更新完毕开始阅读
影响，插入、删
除时间复杂度为O（1）。
（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。
2．链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。
3．采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。
4．线性表 栈 队列 串 顺序存储结构和链式存储结构。 顺序存储结构的定义是：
CONST maxlen=线性表可能达到的最大长度； TYPE sqlisttp=RECORD
elem:ARRAY[1..maxlen] OF ElemType; last:0..maxlen; END; 链式存储结构的定义是： TYPE pointer=↑nodetype; nodetype=RECORD
data:ElemType; next:pointer; END;
linklisttp=pointer; 5.顺序映射时，ai与ai+1的物理位置相邻；链表表示时ai与ai+1的物理位置不要求相邻。 6．在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。
7．见上题6。
8．(1)将next域变为两个域: pre和next，其值域均为0..maxsize。初始化时，头结点（下标为0的元素）其next域值为1，其pre域值为n（设n是元素个数，且n 9. 在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。 10．本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。 11．该算法的功能是判断链表L是否是非递减有序，若是则返回“true”；否则返回“false“。pre指向当前结点，p指向pre的后继。 12．q=p->next; p->next=q->next; free(q); 13. 设单链表的头结点的头指针为head,且pre=head； while(pre->next!=p) pre=pre->next; s->next=p; pre->next=s; 14.设单链表带头结点，工作指针p初始化为p=H->next; (1) while(p!=null && p->data!=X) p=p->next; if(p= =null) return(null);∥查找失败 else return(p);∥查找成功 (2) while(p!=null && p->data if(p==null || p->data>X) return(null);∥查找失败 else return(p); (3) while(p!=null && p->data>X) p=p->next; if(p==null || p->data 15.本程序段功能是将pa和pb链表中的值相同的结点保留在pa链表中（pa中与pb中不同结点删除），pa是结果链表的头指针。链表中结点值与从前逆序。S1记结果链表中结点个数（即pa与pb中相等的元素个数）。S2记原pa链表中删除的结点个数。 16．设 q:=p^.llink; 则 q^.rlink:=p^.rlink; p^.rlink^.llink:=q; p^.llink:=q^.llink; q^.llink^.rlink:=p; p^.rlink:=q; q^.llink:=p 17.(1)前两个语句改为： p.llink^.rlink<- p^.rlink; p^.rlink^.llink<- p^.llink; (2)后三个语句序列应改为： q^.rlink<- p^.rlink;∥以下三句的顺序不能变 p^.rlink^.llink<- q; p^.rlink<- q; 18．mp是一个过程，其内嵌套有过程subp。 subp(s,q)的作用是构造从s到q的循环链表。 subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。 subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环 链表中）构造为循环链表。 总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。 19．在指针p所指结点前插入结点s的语句如下： s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s; 20．(A) f1<>NIL并且f2<>NIL (B) f1↑.data < f2↑.data (C) f2↑.data (E) f1<- f1↑.link 或f2=f2↑.link; 21. 1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向循环链表。 2）(1)r->prior=q->prior;∥将q结点摘下，以便插入到适当位置。 (2)p->next->prior=q;∥（2）（3）将q结点插入 (3)p->next=q; (4)r=r->next;或r=q->next;∥后移指针，再将新结点插入到适当位置。 五、 算法设计题 1．[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 LinkedList Union(LinkedList la,lb) ∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法 将两链表合并成一个按元素值递减次序排列的单链表。 { pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针 la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。 while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; ∥将pa 的后继结点暂存于r。 pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; ∥恢复pa为当前待比较结点。 } else {r=pb->next;∥ 将pb 的后继结点暂存于r。 pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; ∥恢复pb为当前待比较结点。 } 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语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 与本题类似的其它题解答如下： （１）［问题分析］与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。 LinkedList Union(LinkedList ha, hb) ∥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 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 {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。