单链表、双链表、循环链表和静态链表的习题
一、单项选择题
1.关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。
Ⅰ.线性表的顺序存储结构优于其链式存储结构
Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构
Ⅲ.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构
Ⅳ.顺序存储结构和链式存储结构都可以进行顺序存取
A. Ⅰ、Ⅱ、Ⅲ B. Ⅱ、Ⅳ C. Ⅱ、Ⅲ D. Ⅲ、Ⅳ
2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A.顺序存储方式 B.链式存储方式 C.散列存储方式 D.以上均可以
3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应该是（）。
A.将n个元素从小到大排序 B.删除第i个元素（1<i<n）
C.改变第i个元素的值（1<=i<=n） D.在第i个元素后插入一个新元素（1<=i<=n）
4.下列关于线性表说法正确的是（ ）。
Ⅰ.顺序存储方式只能用于存储线性结构
Ⅱ.取线性表的第i个元素的时间同i的大小有关
Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素
Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)
Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表
A. Ⅰ、Ⅱ B.Ⅰ、Ⅲ、Ⅳ、Ⅴ C. Ⅳ、Ⅴ D. Ⅲ、Ⅳ、Ⅴ
5.设线性表中有2n个元素，（ ）在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-l个元素的值(i=0,…, n-1)
6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（ ）。
A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;
C. q->next=s;s->next=p; D. p->next=s;s->next=q;
7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ）。
A. O(1) B. O(n) C. O(n2-------) D. O(nlog2------n)
8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度用大O形式表示应该是（ ）。
A. O(1) B. O(n) C. O(m) D. O(n+m)
9.单链表中，增加一个头结点的目的是为了（ ）。
A.使单链表至少有一个结点 B.标识表结点中首结点的位置
C.方便运算的实现 D.说明单链表是线性表的链式存储
10.在一个长度为n的带头结点的单链表h上，设有尾指计r，则执行（ ）操作与链表的表长有关。
A.删除单链表中的第一个元素
B.删除单链表中最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）； 对于不带头结点的单链表，则判定空表的条件为（ ）。
A .head==NULL B .head->next=NULL
C. head->next==head D. head!=NULL
12.下面关于线性表的一些说法中，正确的是（ ）。
A .对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关
B.线性表中每个元素都有一个直接前趋和一个直接后继
C.为了方便插入和删除数据，可以使用双链表存放数据
D.取线性表第i个元素的时间同i的大小有关
13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则用（ ）存储方式最省时间。
A.单链表 B.仅有头指针的单循环链表
C.双链表 D.仅有尾指针的单循环链表
14.在双链表中向p所指的结点之前插入一个结点q的操作为（ ）。
A. p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;
B .q->prior=p->prior;p->prior->next=q;q->next=p;p->priop=q->next;
C. q->next=p;p->next=q;q->prior->next=q;q->next=p;
D .p->prior->next=q; q->next=p; q->prior=p->prior;p->prior=q;
15.在双向链表存储结构中，删除p所指的结点时必须修改指针（ ）。
A .p->llink->rlink=p->rlink; p->rlink->llink=p->llink;
B.p->llink=p->llink->llink;p->llink->rlink=p;
C.p->rlink->llink=p; p->rlink = p->rlink->rlink;
D .p->rlink=p->llink->llink;p->llink=p->rlink->rlink;
16.在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（ ）。
A. O(1) B. O(n) C.O(n2---------) D. O(nlog2--------n)
17.与单链表相比，双链表的优点之一是（ ）。
A.插入、删除操作更方便 B.可以进行随机访问
C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活
18.带头结点的双循环链表L为空的条件是（ ）。
A. L->prior==L&&L->next==NULL
B. L->prior==NULL&&L->next==NULL
C. L->prior==NULL&&L->next==L
D. L->prior==L&&L->next==L
19. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（ ）最节省时间。
A.带头结点的双循环链表 B.单循环链表
C.带尾指针的单循环链表 D.单链表
20.设对n(n>1)个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素； 在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（ ）。
A.只有尾结点指计没有头结点指针的循环单链表
B.只有尾结点指针没有头结点指针的非循环双链表
C.只有头结点指针没有尾结点指针的循环双链表
D.既有头结点指针也有尾结点指针的循环单链表
21.—个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（ ）最节省时间。
A.不带头结点的单循环链表 B.双链表
C.不带头结点且有尾指针的单循环链表 D.单链表
22.静态链表中指针表示的是（ ）。
A.下一元素的地址 B.内存储器地址
C.下一个元素在数组中的位置 D.左链或右链指向的元素的地址
23.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。
A.单链表 B.静态链表 C.顺序表 D.双链表
二、综合应用题
1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。
2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。
3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。
5.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)。
6.有一个带头结点的单链表L，设计一个算法使其元素递增有序。
7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有大于最小值小于最大值的元素（若存在)。
8.给定两个单链表，编写算法找出两个链表的公共结点。
9.给定一个带表头结点的单链表，设head为头指针，结点的结构为(data, next)，data 为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。
10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
11.设C={a1, b1, a2, b2, …, an, bn}为线性表，用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1, a2,…, an}, B={bn, …, b2, b1}
12.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变作(7, 10, 21, 30, 42, 51, 70)。
13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
14.设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C，要求不破坏A、B的结点。
15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B 的交集，并存放于A链表中。
16.两个整数序列A=a1, a2, a3,…, am和B=b1, b2, b3,…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。
17.设计一个算法用于判断带头结点的循环双链表是否对称。
18.有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。
19.设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。
20.设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令元素值为x的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L, x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
21.【2009年计算机联考真题】已知一个带有表头结点的单链表，结点结构为
假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data域的值，并返回1；否则，只返回0。要求：
1)描述算法的基本设计思想。
2)描述算法的详细实现步骤。
3)根据设计思想和实现步骤，用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。
22.【2012年计算机联考真题】假定用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。
设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置 (如图中字符i所在结点的位置p)。要求：
1)给出算法的基本设计思想。
2)根据设计思想，用C或C++或Java语言描述算法，关键之处给出注释。
3)说明你所设计算法的时间复杂度。
答案与解析
一、单项选择题
1. B
两种存储结构有不同的适用场合，不能简单地说谁好谁坏，Ⅰ错误。链式存储用指针表示逻辑结构，而指针的设置是任意的，故可以很方便地表示各种逻辑结构；顺序存储则只能用物理上的邻接关系来表示逻辑结构，Ⅱ正确。在顺序存储中，插入和删除结点需要大量的移动元素，效率较低，Ⅲ的描述刚好相反。顺序存储结构既可以随机存取也能顺序存取，而链式结构只能进行顺序存取，Ⅳ正确。
2. B
要求较快速地插入和删除，排除A、D。散列存储通过散列函数映射到物理空间，不能反映数据之间的逻辑关系，排除C。链式存储中的静态链表满足这一要求。
3. C
对n个元素进行排序的时间复杂度最快也要O(n)(初始有序)，通常是O(nlog2---------n)或O(n2------)。在顺序表中删除第i个元素，或在第i个元素之后插入一个新元素，如想保持其它元素原来的顺序，时间复杂度为O(n)，因此A、B、D均错误。在顺序存储的线性表中更改第i个元素的值，直接用下标访问并重新赋值即可，时间复杂度为O(1)。
4. D
顺序存储方式同样适合图和树的存储，如满二叉树的顺序存储，Ⅰ错误。若线性表用顺序存储方式，则取其第i个元素的时间与i的大小无关，Ⅱ错误。Ⅲ是静态链表的特有性质。单链表只能顺序查找插入位置，时间复杂度为O(n)，若为顺序表，可用折半查找，时间复杂度可降至O(log2-------n), Ⅳ正确。队列需要在表头删除元素，表尾插入元素，故用带尾指针的循环单链表较为方便，插入和删除的时间复杂度都是O(1)，Ⅴ正确。
5. A
A中对于单链表和顺序表上实现的时间复杂度都为O(n)，但后者要移动很多元素，所以在单链表上实现效率更高。B和D效率刚好相反，C无区别。
6. C
s插入后，q成为s的前驱，而p成为s的后继，选项C满足此条件。
7. D
若先建立链表，然后依次直接插入建立有序表，则每插入一个元素就需遍历链表寻找插入位置，此即链表的插入排序，时间复杂度为O(n2-----)。若先将数组排好序，然后建立链表，建立链表的时间复杂度为O(n)，而数组排序的最少时间复杂度为O(nlog2-----------n)，故时间复杂度为O(nlog2----------n)。本题问最少时间复杂度，故选D。
8. C
先遍历长度为m的单链表，找到这个长度为m的单链表的尾结点，然后将其next域置为另一个单链表的首结点，其时间复杂度为O(m)。
9. C
单链表设置头结点的目的是为了方便运算的实现，主要好处体现在：第一，有头结点后，插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素；第二，不论链表是否为空，链表指针不变。
10. B
删除单链表的最后一个结点需要置其前驱结点的指针域为NULL，故需要的时间为O(n)，与表长有关。其他操作均与表长无关，读者可以自行模拟。
11. B
A在带头结点的单链表中，头指针head指向头结点，头结点的next域指向第1个元素结点，head->next==NULL表示该单链表为空。在不带头结点的单链表中，head直接指向第1 个元素结点，head==NULL表示该单链表为空。
12. C
双链表能很方便地访问前驱和后继，故删除和插入数据较为方便。A显然错误。B表中第一个元素和最后一个元素不满足题设要求。D未考虑顺序存储的情况。B、C、D在删除尾结点时，都需要先查找其前驱结点，时间复杂度为O(n)。
13. D
在最后一个元素之后插入元素，需要先找到最后一个元素，故A、B和C的时间复杂度均为O(n)。B因为没有特殊的指针指示头结点或尾结点，故需从某一结点向固定的方向顺序依次搜索插入和删除的位置，时间复杂度也为O(n)。D的两种算法的时间复杂度都是O(1)，如下图所示。
14. D
为了在p之前插入结点q，可以将p的前一个结点的next域指向q，将q的next域指向 p，将q的prior域指向p的前一个结点，将p的prior域指向q。仅D满足条件。
15. A
与上一题的分析基本类似，只不过这里是删除一个结点，注意将p的前、后两结点链接起来。注，请读者仔细对比上述两题，弄清双链表的插入和删除的方法。
16. B
假设单链表递增有序（递减的情况同理），在插入数据为x的结点之前，先要在单链表中找到第一个大于x的结点的直接前驱p，在p之后插入该结点。查找过程的时间复杂度为O(n)，插入过程的时间复杂度为O(1)，因此时间复杂度为O(n)。
17. D
在双链表中可以快速访问任何一个结点的前后相邻结点，而在单链表中只能快速访问任何一个结点的后继结点。
18. D
循环单链表L判空的条件是头结点（头指针）的prior和next域都指向它自身。
19. A
在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。而寻找尾结点以及尾结点的前驱结点，只有带头结点的双循环链表所需要的时间最少。
20. C
对于A，删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O(n)。对于B，删除首结点*p时，需要找到*p结点，这里没有直接给出头结点指针，而通过尾结点的prior 指针找到*p结点的时间复杂度为O(n)。对于D，删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O(n)。对于C，执行这4种算法的时间复杂度均为O(1)。
21. C
对于A，在最后一个元素之后插入一个元素的情况与普通单链表相同，时间复杂度为 O(n)；而删除表中第一个元素时，为保持单循环链表的性质(尾结点的指计指向第一个结点)，需要首先遍历整个链表找到尾结点，然后再执行删除操作，时间复杂度也为O(n)。对于B，双链表的情况与单链表的相同，一个是O(n)，一个是O(1)。对于C，与A的分析对比，因为已经知道了尾结点的位置，省去了遍历链表的过程，因此插入和删除的时间复杂度均为 O(1)。对于D，要在最后一个元素之后插入一个元素，需要遍历整个链表才能找到插入位置，时间复杂度为O(n)；删除第一个元素的时间复杂度为O(1)。
22. C
静态链表中的指针又称游标，指示下一个元素在数组中的下标。
23. B
静态链表用数组表示，因此需要预先分配较大的连续空间，静态链表同时还具有一般链表的特点，即插入和删除不需要移动元素。
二、综合应用题
1.解答：
设f(L，x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点，则显然有 f(L->next, x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。由此，可以推出递归模型如下：
终止条件：
f(L, x) ≡ 不做任何事情; 若L为空表或只有一个结点
f(L, x)≡删除*L 结点;f(L->next, x); 若 L->data==x
递归主体：
f(L, x)≡f(L->next, x);
其他情况本题代码如下：
void Del_X_3 (Linklist &L, ElemType x) {
//递归实现在单链表L中删除值为x的结点
LNode *p; //p指向待删除结点
if (L==NULL) //递归出口
return;
if (L->data==x) { //若L所指结点的值为x
p=L; //删除*L,并让L指向下一结点
L=L->next;
free(p);
Del_X_3(L,x) ; //递归调用
}else //若L所指结点的值不为x
Del_X_3 (L->next, x) ; //递归调用
}
算法需要借助一个递归工作栈，深度为O(n)，时间复杂度为O(n)。有读者认为直接free掉p结点会造成断链，实际上因为L为引用，是直接对原链表进行操作，因此不会断链。
2.解答：
解法一：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。本题代码如F ：
void Del_X_1(Linklist &L, ElemType x){
//L为带头的单链表，本算法删除L中所有值为x的结点
LNode *p=L->next, *pre=L, *q; //置 p 和 pre 的初始值
while(p!=NULL){
if(p->data==x){
q=p; //q指向该结点
p=p->next;
pre->next=p; //删除*q 结点
free(q); //释放 *q结点的空间
}else{ //否则，pre和p同步后移
pre=p;
p=p->next;
} //else
} //while
}
本算法是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为x。实际上，这个条件是可以任意指定的，只要修改if条件即可，比如，我们要求删除值介于 mink和maxk之间的所有结点，则只需将if语句修改为if(p->data>mink &&p->data<maxk)。
解法二：用尾插法建立单链表。用p指针扫描L的所有结点，当其值不为x时将其链接到L之后，否则将其释放。本题代码如下：
void Del_X_2(Linklist &L, ElemType x){
//L为带头的单链表，本算法删除L中所有值为x的结点
LNode *p=3->next, *r=L, *q; //r指向尾结点，其切值为头结点
while(p!=NULL){
if (p->data!=x) { //*p结点值不为x时将其链接到L尾部
r->next=p;
r=p;
p=p->next; //继续扫描
}else{ //*p结点值为x时将其释放
q=p;
p=p->next; //继续扫描
free(q); //释放空间
}
}//while
r->next=NULL; //插入结束后置尾结点指针为NULL
}
上述两个算法扫描一遍链表，时间复杂度为O(n)，空间复杂度为O(1)。
3.解答：
考虑到从头到尾输出比较简单，本题的思路很自然地联系到借助上题链表逆置的方法来实现，改变链表的方向，然后就可以从头到尾实现反向输出了。
此外，本题还可以借助一个栈来实现，每经过一个结点时，将该结点放入栈中。在遍历完整个链表后，再从栈顶开始输出结点值即可。
既然能用栈的思想解决，也就很自然地联想到了用递归来实现，每当访问一个结点时，先递归输出它后面的结点，再输出该结点自身，这样链表就反向输出了。如下图所示：
本题代码如下：
void R_Print(LinkList L){
//从尾至头输出单链表L中每个结点的值
if(L->next!=NULL){
R_Print (L->next) ; //递归
} //if
print (L->data) ; //输出函数
}
4.解答：
算法思想：用p从头至尾扫描单链表，pre指向*p结点的前驱，用minp保存值最小的结点指针（初值为p），minpre指向*minp结点的前驱（初值为pre）。一边扫描，一边比较，若p->dafa小于minp->dara，则将p、pre分别赋值给minp、minpre,如下图所示。当p扫描完毕，minp指向最小值结点，minpre指向最小值结点的前驱结点，再将minp所指结点删除即可。
本题代码如下：
LinkList Delete_Min(LinkList &L){
//L是带头结点的单链表，本算法删除其最小值结点
LNode *pre = L, *p=pre->next; //p 为工作指针，pre 指向其前驱
LNode *minpre=pre, *minp=p; //保存最小值结点及其前驱
while(p!=NULL){
if(p->data<minp->data){
minp=p; //找到比之前找到的最小值结点更小的结点
minpre=pre;
}
pre=p; //继续扫描下一个结点
p=p->next;
}
minpre->next=minp->next; //删除最小值结点
free(minp);
return L;
}
算法需要从头至尾扫描链表，时间复杂度为O(n)，空间复杂度为O(1)。
若本题改为不带头结点的单链表，则实现上会有所不同，留给读者自行思考。
5.解答：
解法一：将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法建立单链表)，直到最后一个结点为止，则实现了链表的逆置，如下图所示。
本题代码如下：
LinkList Reverse_l(LinkList &L){
//L是带头结点的单链表，本算法将L就地逆置
p=L->next; //p为工作指针，从第一个元素结点开始
L->next = NULL; //先将头结点L的next域置为NULL
while (p!=NULL) { //依次将元素结点摘下
r=p->next; //暂存p的后继
p->next=L->next; //将p结点插入到头结点之后
L->next=p;
p=r;
}
return L;
}
解法二：大部分辅导书都只介绍解法一，这对读者的理解和思维是不利的。为了将调整指针这个复杂的过程分析清楚，我们借助图形来进行直观的分析。
假设pre、p和r指向3个相邻的结点，如下图所示。假设经过若千操作，*pre之前的结点的指针都已调整完毕，它们的next都指向其原前驱结点。现在令*p结点的next域指向*pre 结点，注意到一旦调整指针的指向后，*p的后继结点的链就断开了，为此需要用r来指向原 *p的后继结点。处理时需要注意两点：一是在处理第一个结点时，应将其next域置为NULL，而不是指向头结点（因为它将作为新表的尾结点）；二是在处理完最后一个结点后，需要将头结点的指针指向它。
本题代妈如下：
LinkList Reverse_2(LinkList &L){
//依次遍历线性表L,并将结点指针反转
LNode *pre,*p=L->next,*r=p->next;
p->next=NULL; //处理第一个结点
while(r!=NULL) { //r为空，则说明p为最后一个结点
pre=p; //依次继续遍历
p=r;
r=r->next;
p->next=pre; //指针反转
}
L->next=p; //处理最后一个结点
return L;
}
上述两个算法的时间复杂度为O(n)，空间复杂度为O(1)。
6.解答：
算法思想：用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点*p (直至p==NULL为止)，在有序表中通过比较查找插入 *p的前驱结点*pre，然后将*p插入到*pre之后，如下图所示。
本题代码如下：
void Sort(LinkList &L){
//本算法实现将单链表L的结点重排，使其递增有序
LNode *p=L->next, *pre;
LNode *r=p->next; //r保持*p后继结点指针，以保证不断链
p->next=NULL; //构造只含一个数据结点的有序表
p=r;
while(p!=NULL){
r=p->next; //保存*p的后继结点指针
pre=L;
while (pre->next!=NULL && pre->next->data<p->data)
pre=pre->next; //在有序表中查找插入的前驱结点*pre
p->next=pre->next; //将*p 插入到*pre 之后
pre->next=p;
p=r； //扫描原单链表中剩下的结点
}
}
7.解答：
因为链表是无序的，所以只能逐个结点进行检查，执行删除。本题代码如下：
void RangeDelete(LinkList &L, int min,int max){
LNode *pr = L, *p=L->link; //p 是检测指针，pr 是其前驱
while(p!=NULL)
if (p->data>min&&p->data<max) { //寻找到被删结点，删除
pr->link=p->link;
free(p);
p=pr->link;
}else{ //否则继续寻找被删结点
pr=p；
p=p->link;
}
}
8.解答：
两个单链表有公共结点，也就是说两个链表从某一结点开始，它们的next都指向同一个结点。由于每个单链表结点只有一个next域，因此从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。所以，两个有公共结点而部分重合的单链表，拓扑形状看起来像Y，而不可能像X。
本题极容易联想到“蛮”方法：在第一个链表上顺序遍历每个结点，每遍历一个结点，在第二个链表上顺序遍历所有结点，如果找到两个相同的结点，于是就找到了它们的公共结点。显然，该算法的时间复杂度为O(len1*len2)。
接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化：如何判断两个单向链表有没有公共结点？应注意到这样一个事实：如果两个链表有一个公共结点，那么该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一个结点。如果两个尾结点是一样的，说明它们有公共结点，否则两个链表没有公共的结点。
然而，在上面的思路中，顺序遍历两个链表到尾结点的时候，并不能保证在两个链表上同时到达尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点了。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的。因此，它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。
在这个思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为O(len1+len2)。
本题代码如下：
LinkList Search_1st_Common(LinkList Ll, LinkList L2){
//本算法实现在线性的时间内找到两个单链表的第一个公共结点
int len1 = Length(L1), len2 = Length (L2) ; //计算两个链表的表长
LinkList longList, shortList; //分别指向表长较长和较短的链表
if (len1>len2) { //L1 表长较长
longList = Ll->next; shortList=L2->next;
dist=len1-len2; //表长之差
}else{ //L2表长较长
longList=L2->next; shortList=L1->next;
dist=len2 - lenl; //表长之差
}
while(dist--) //表长的链表先遍历到第dist个结点，然后同步
longList=longList->next;
while (longList!=NULL) { //同步寻找共同结点
if(longList==shortList) //找到第一个公共结点
return longList;
else{ //继续同步寻找
longList=longList->next;
shortList=shortList->next;
}
} //while
return NULL;
}
9.解答：
算法思想：对链表进行遍历，在每趟遍历中查找出整个链表的最小值元素，输出并释放结点所占空间；再查找次小值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间，该算法的时间复杂度为O(n2)。
void Min_Delete(LinkList &head){
//head是带头结点的单键表的头指针，本算法按递增顺序输出单链表
while(head->next!=NULL) { //循环到仅剩头结点
pre=head; //pre为元素最小值结点的前驱结点的指针
p=pre->next; //p为工作指针
while (p->next!=NULL) {
if(p->next->data<pre->next->data)
pre=p; //记住当前最小值结点的前驱
p=p->next;
}
print(pre->next->data); //输出元素最小值结点的数据
u=pre->next; //删除元素值最小的结点，释放结点空间
pre->next=u->next;
free(u);
}//while
free (head); //释放头结点
}
若题设不限制数组辅助空间的使用，则可先将链表的数据复制在数组里，再用时间复杂度为O(nlog2n)的排序算法进行排序，然后将数组元素输出，时间复杂度为O(nlog2n)。
10.解答：
算法思想：设置一个访问序号变量（初值为0），每访问一个结点序号自动加1，然后根据序号的奇偶性将结点插入到A表或B表中。重复以上操作直到表尾。
LinkList DisCreat_1(LinkList &A){
//将表A中结点按序号的奇偶性分解到表A或表B中
i=0; //i记录表A中结点的序号
B= (LinkList) malloc (sizeof (LNode) ); //创建 B 表表头
B->next=NULL; //B 表的初始化
LNode *ra = A, *rb=B; //ra和rb将分别指向将创建的A表和B表的尾结点
p=A->next; //p为链表工作指针，指向待分解的结点
A->next=NULL; //置空新的 A 表
while (p!=NULL) {
i++; //序号加 1
if (i%2==0) { //处理序号为偶数的链表结点
rb->next=p; // 若B表尾描入新结点
rb=p; //rb指向新的尾结点
}else{ //处理原序号为奇数的结点
ra->next=p; //在A表尾插入新结点
ra=p;
}
p=p->next; //将p恢复为指向新的待处理结点
} //while 结束
ra->next=NULL;
rb->next=NULL;
return B;
}
为了保持原来结点中的顺序，本题用尾插法建立单链表。此外，本算法完全可以不用设置序号变量。while循环中的代码改为将结点插入到表A中和将下一结点插入到表B中，这样while中第一处理的结点就是奇数号结点，第二处理的结点就是偶数号结点。
11.解答：
算法思想：用上题的思路，不设序号变量。二者的差别仅在于对B，表的建立不采用尾插法，而是用头插法。
LinkList DisCreat_2(LinkList &A){
LinkList B= (LinkList)malloc(sizeof(LNode)) ; //创建B 表表头
B->next=NULL; //B 表的初始化
LNode *p=A->next, *q; //p 为工作指针
LNode *ra=A; //ra始终指向A的尾结点
while(p!=NULL){
ra->next=p; ra=p; //将*p 链到 A 的表尾
p=p->next;
q=p->next; //头插后，将断链，因此用q记忆*p的后继
p->next=B->next; //将插入到 B 的前端
B->next=p;
p=q
}
ra->next=NULL; //A尾结点的next域置空
return B;
}
该算法特别需要注意的是，用头插法插入结点后，*p的指针域已改变，如果不设变量保存其后继结点会引起断链，从而导致算法出错。
12.解答：
算法思想：由于是有序表，所有相同值域的结点都是相邻的。用p扫描递增单链表L，若*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点。
void Del_Same(LinkList &L) {
//L是递增有序的单链表，本算法删除表中数值相同的元素
LNode *p=L->next, *q; //p 为扫描工作指针
while (p->next!=NULL) {
q=p->next; //q指向 *p 的后继结点
if (p->data==q->data) { //找到重复值的结点
p->next=q->next; //释放*q 结点
free(q); //释放相同元素值的结点
}else
p = p->next;
}
}
本算法的时间复杂度为O(n)，空间复杂度为O(1)。
13.解答：
算法思想：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将小的结点链入链表中，同时后移工作指针。该问题要求结果链表按元素值递减次序排列，故新链表的建立应该用头插法。比较结束后，可能会有一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。
void MergeList(LinkList &La,LinkList &Lb) {
//合并两个递增有序链表（带头结点)，并使合并后的链表递减排列
LNode *r, *pa=La->next, *pb=Lb->next; //分别是表 La 和 Lb 的工作指针
La->next = NULL; //La作为结果链表的头指针，先将结果链表初始化为空
while(pa&&pb) //当两链表均不为空时，循环
if(pa->data<=pb->data){
r=pa->next; //r暂存pa的后继结点指针
pa->next=La->next;
La->next=pa; //将pa结点链于结果表中，同时逆置(头插法）
pa=r; //恢复pa为当前待比较结点
}else{
r=pb->next; //r暂存pb的后继结点指针
pb->next=La—>next;
La->next=pb; //将pb结点链于结果表中，同时逆置(头插法）
pb=r; //恢复pb为当前待比较结点
}
if(pa)
pb=pa; //通常情况下会剩一个链表非空，处理剩下的部分
while(pb){ //处理剩下的一个非空链表
r=pb->next; //依次插入到La中（头插法）
pb->next = La->next;
La->next = pb;
pb=r;
}
free(Lb);
}
14.解答：
算法思想：尾插法建立单链表C,由于算法要求不破坏A、B的结点，所以，需要通过比较复制的方式产生单链表C。
void Get_Common (LinkList A, linkList B) {
//本算法产生单链表A和B的公共元素的单链表C
LNode *p=A->next,*q=B->next,*r,*s;
LinkList C=(LinkList)malloc(sizeof(LNode)) ; //建立表 C
r=C; //r始终指向C的尾结点
while (p!=NULL && q!=NULL) { //循环跳出条件
if(p->data<q->data)
p=p->next; //若A的当前元素较小，后移指针
else if(p->data>q->data)
q=q->next; //若B的当前元素较小，后移指针
else{ //找到公共元素结点
s=(LNode *)malloc(sizeof(LNode));
s->data=p->data; // 复制产生结点 * s
r->next=s; r=s; //将*s链接到C上（尾插法）
p=p->next; //表A和B继续向后扫描
q=q->next;
}
}
r->next=NULL; //置C尾结点指针为空
}
15.解答：
算法思想：用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。
LinkList Union(LinkList &la,LinkList &lb) {
pa=la->next; //设工作指针分别为pa和pb
pb=lb->next;
pc=la; //结果表中当前合并结点的前驱指针
while(pa&&pb){
if(pa->data==pb->data) { //交集并入结果表中
pc->next=pa; //A中结点链接到结果表
pc=pa;
pa=pa->next;
u=pb; //B中结点释放
pb=pb->next;
free(u);
}
else if (pa->data<pb->data) { //若A中当前结点值小于B中当前结点值
u=pa;
pa=pa->next; //后移指针
free(u) ; //释放A中当前结点
}else{ //若B中当前结点值小于A中当前结点值
u=pb;
pb=pb->next; //后移指针
free (u) ; //释放B中当前结点
}
} //while 结束
while(pa){ //B已遍历完，A未完
u=pa;
pa=pa->next;
free (u) ; //释放A中剩余结点
}
while(pb){ //A已遍历完，B未完
u=pb;
pb=pb->next;
free(u) ; //释放B中剩余结点
}
pc->next=NULL; //置结果链表尾指针为NULL
free (lb) ; //释放B表的头结点
return la;
}
链表归并类型的题在各学校历年真题中出现的频率很高，故应扎实掌握此类问题的思想。该算法的时间复杂度为O(len1+len2)，空间复杂度为O(1)。
16.解答：
算法思想：因为两个整数序列已存入两个链表中，操作从两个链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一个结点开始比较，直到B链表到尾表示匹配成功。A链表到尾而B 链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。
int Pattern(LinkList A, LinkList B){
//A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列
LNode *p=A; //p为A链表的工作指针，本题假定A和B均无头结点
LNode *pre = p; //pre记住每趟比较中A链表的开始结点
LNode *q=B; //q是B链表的工作指针
while (p&&q)
if (p->data==q->data) { //结点值相同
p=p->next;
q=q->next;
}else{
pre=pre->next;
p=pre; //A链表新的开始比较结点
q=B; //q从B链表第一个结点开始
}
if (q==NULL) //B已经比较结束
return 1; //说明B是A的子序列
else
return 0; //B不是A的子序列
}
17.解答：
算法思想：让p从左向右扫描，q从右向左扫描，直到它们指向同一结点（p==q，当循环双链表中结点个数为奇数时）或相邻（p->next=q或q->prior=p，当循环双链表中结点个数为偶数时）为止，若它们所指结点值相同，则继续进行下去，否则返回0。若比较全部相等，则返回1。
int Symmetry(DLinkList L){
//本算法从两头扫描循环双链表，以判断链表是否对称
DNode *p=L->next, *q=L->prior; //两头工作指针
while (p! =q&&q->next! =p) //循环跳出条件
if (p->data==q->data) { //所指结点值相同则继续比较
p=p->next; q=q->prior;
}else //否则，返回0
return 0;
return 1; //比较结束后返回1
}
18.解答：
算法思想：先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，再使之成为循环的。
LinkList Link(LinkList &h1,LinkList &h2){
//将循环链表h2链接到循环链表h1之后，使之仍保持循环链表的形式
LNode *p, *q; //分别指向两个链表的尾结点
p=h1;
while (p->next!=h1) //寻找 h1 的尾结点
p=p->next;
q=h2;
while (q->next!=h2) //寻找 h2 的尾结点
q=q->next;
p->next=h2; //将h2链接到h1之后
q->next=h1; //令h2的尾结点指向h1
return h1;
}
19.解答：
对于循环单链表L，在不空时循环：每循环一次查找一个最小结点（由minp指向最小值结点，minpre指向其前驱结点）并删除它。最后释放头结点。
void Del_All(LinkList &L){
// 本算法实现每次删除循环单链表中的最小元素，直到链表空为止
LNode *p, *pre, *minp, *minpre;
while(L->next!=L){ //表不空，循环
p=L->next; pre=L; //p为工作指针，pre指向其前驱
minp=p; minpre=pre; //minp 指向最小值结点
while(p!=L){ //循环一趟，查找最小值结点
if(p->data<minp->data){
minp=p; //找到值更小的结点
minpre=pre;
}
pre=p; //查找下一个结点
p=p->next;
}
printf ("%d", minp->data); //输出最小值结点元素
minpre->next=minp->next; //最小值结点从表中“断”开
free(minp) ; //释放空间
}
free (L) ; //释放头结点
}
20.解答：
此题主要考查双链表的查找、删除和插入算法。
算法思想：首先在双向链表中查找数据值为X的结点，查到后，将结点从链表上摘下，然后再顺着结点的前驱链查找该结点的插入位置。（频度递减，且排在同频度的第一个），并插入到该位置。
DLinkList Locate(DLinkList &L,ElemType x){
//本算法先查找数据x,查找成功时结点的访问频度域增1
//最后将该结点按频度递减插入链表中适当位置（同频度最近访问的在前面）
DNode *p=L->next,*q; //p为工作指针，q为p的前驱，用于查找插入位置
while (p&&p->data!=x)
p = p->>next; //查找值为x的结点
if(!p){
printf ("不存在值为x的结点\n");
exit(0);
}else {
p->freq++; //令元素值为x的结点的freq域加1
p->next->pred=p->pred;
p->pred->next=p->next; //将p结点从链表上摘下
q=p->pred; //以下查找p结点的插入位置
while (q!=L && q->freq<=p->freq)
q=q->pred;
p->next=q->next;
q->next->pred=p; //将p结点插入，一定是排在同频率的第一个
p->pred=q;
q->next=p;
}
return p ; //返回值为x的结点的指针
}
21.解答：
1)算法的基本设计思想如下：
问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想是：定义两个指针变量p和q,初始时均指向头结点的下一个结点（链表的第一个结点），p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与P指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。
2)算法的详细实现步骤如下：
①count=0，p和q指向链表表头结点的下一个结点。
②若p为空，转⑤。
③若count等于k,则q指向下一个结点；否则，count=count+1。
④p指向下一个结点，转②。
⑤若count等于k，则查找成功，输出该结点的data域的值，返回1;否则，说明k值超过了线性表的长度，查找失败，返回0。
⑥算法结束。
3)算法实现
typedef int ElemType; //链表数据的类型定义
typedef struct LNode{ //链表结点的结构定义
ElemType data; //结点数据
struct Lnode *link; //结点链接指针
}LNode, *LinkList;
int Search_k(LinkList list,int k) {
//查找链表list倒数第k个结点，并输出该结点data域的值
LNode *p = list->link, *q=list->link; //指计；p、q 指示第一个结点
int count=0;
while (p!=NULL) { //遍历链表直到最后一个结点
if (count<k) count++; //计数，若 count<k 只移动 p
else q=q->link;
p-p->link; //之后让p、q同步移动
} //while
if(count<k)
return 0; //查找失败返回0
else{ //否则打印并返回1
printf("%d", q->data);
return 1;
}
} //Search_k
注意：若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若采用两遍或多遍扫描才能得到正确结果的，最高分为10分。若采用递归算法得到正确结果的，最高给10分；若实现算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分。
22.解答：
本题的结构体是单链表，用双指针法。用指针p、q分别扫描str1和str2，当p、q指向同一个地址时，即找到共同后缀的起始位置。
1)算法的基本设计思想如下：
①分别求出str1和str2所指的两个链表的长度m和n。
②将两个链表以表尾对齐：令指针p、q分别指向strl和str2的头结点，若m>=n，则指针P先走，使p指向链表中的第m-n+1个结点；若m<n,则使q指向链表中的第n-m+1 个结点，即使指针p和q所指的结点到表尾的长度相等。
③反复将指针p和q同步向后移动，当p、q指向同一位置时停止，即为共同后缀的其实位置，算法结束。
2)本题代码如下：
typedef struct Node{
char data;
struct Node *next;
}SNode;
/*求链表长度的函数*/
int listlen(SNode *head){
int len=0;
while(head->next!=NULL){
len++;
head=head->next;
}
return len;
}
/*找出共同后缀的起始地址*/
SNode* find_addr(SNode *strl,SNode *str2){
int m,n;
SNode *p, *q;
m=listlen (strl) ; //求 strl 的长度
n=listlen (str2) ; //求 str2 的长度
for (p=str1;m>n;m--) //若m>n，使p指向链表中的第m-n+1个结点
p=p->next;
for (q=str2;m<n;n--) //若m<n,使q指向链表中的第n-m+l个结点
q=q->next;
while (p->next !=NULL && p->next!=q->next) {
//将指针 p 和 q 同步向后移动
p=p->next;
q=q->next;
}//while
return p->next; //返回共同后缀的起始地址
}
湘公网安备 43102202000103号