reverse（R,0,n-1）;//将全部数据逆置
reverse（R,0,n-p-1）;//将前n-p个元素逆置
reverse（R,n-p,n-1）;//将后p个元素逆置
}
}
（3）说明算法的复杂性：
上述算法的时间复杂度为O（n），算法的空间复杂度为O
（1）。
解析：
无
14
试编写一个尽可能高效的算法，实现在带头结点的单链表中删除（一个）最小值结点。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
∙参考答案是：
【解答】
（1）算法的基本设计思想：
本题要求在单链表中删除最小值结点。
单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。
而“最小值结点”是在遍历整个链表后才能知道。
所以算法应首先遍历链表，求得最小值结点及其前驱。
遍历结束后再执行删除操作。
（2）用C语言算法描述如下：
voiddelete（Linklist&L）{
LNode*p=L->next；∥假定链表非空，p为工作指针，指向待处理的结点。
LNode*pre=L；∥pre指向最小值结点的前驱
LNode*q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点
while（p->next!
=NULL）{
if（p->next->datadata）{∥查最小值结点
pre=p；
q=p->next；
}
p=p->next；∥指针后移
}
pre->next=q->next；∥从链表上删除最小值结点
freeq；∥释放最小值结点空间
}
解析：
无
15
设计一个在时间和空间上尽可能高效的算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释
∙；
∙参考答案是：
【解答】
（1）算法的基本设计思想：
本题要求将链表中数据域值最小的结点移到链表的最前面。
首先要查找最小值结点，将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），在插入到链表的最前面。
（2）用C语言算法描述如下：
voiddelinsert（LinkList&L）{
LNode*p=L->next;//p是链表的工作指针
LNode*pre=L;//pre指向链表中数据域最小值结点的前驱
LNode*q=p;//q指向数据域最小值结点，初始假定是第一结点
while（p->next!
=NULL）{
if（p->next->datadata）{//找到新的最小值结点
pre=p;
q=p->next;
}
p=p->next;
}
if（q!
=L->next）{//若最小值是第一元素结点，则不需再操作
pre->next=q->next;//将最小值结点从链表上摘下
q->next=L->next;//将q结点插到链表最前面
L->next=q;
}
}
解析：
无
16
编写一个算法，设有两个无头结点的单链表,头指针分别为ha,hb,两个链表的数据都按递增序存放。
现要求将hb表归到ha表中,且归并后ha仍递增序,在归并中对于ha表中已有的数据若hb中也有,则hb中的这部分数据不归并到ha中,hb的链表在算法中不允许破坏。
∙参考答案是：
【分析】本题与“将两个按元素值递增次序排列的线性表，归并为一个按元素值非递增次序排列的单链表”问题类似，不同之处在于：
一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。
【解答】用C语言算法描述如下：
voidUnion（LinkList&ha,LinkListhb）｛
LinkListla;
la=（LinkList）malloc（sizeof（LNode））;
la->next=ha;∥申请头结点以便操作
LNode*pa=ha;∥pa是ha链表的工作指针
LNode*pb=hb;∥pb是hb链表的工作指针
LNode*pre=la;∥pre指向当前待合并结点的前驱
while（pa&&pb）
if（pa->datadata）{∥处理ha中数据
pre->next=pa;
pre=pa;
pa=pa->next;
}
elseif（pa->data>pb->data）{∥处理hb中数据。
r=（LinkList）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;∥将两链表中剩余部分链入结果链表
elsepre->next=pb;
freela;∥释放头结点，ha、hb指针未被破坏
}
解析：
无
17
已知不带头结点的线性链表list，请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。
要求链接过程中不得使用除该链表以外的任何链结点空间。
∙参考答案是：
【分析】本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链结点空间”。
链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。
【解答】用C语言算法描述如下：
LinkListLinkListSort（LinkList&list）{//list是不带头结点的线性链表
LNode*p=list->next;∥p是工作指针，指向待排序的当前元素
list->next=NULL;∥假定第一个元素有序，即链表中现在只有一个结点
while（p!
=NULL）{
r=p->next;∥r是p的后继
q=list;
if（q->data>p->data）{∥处理待排序结点p比第一个元素结点小的情况
p->next=list;
list=p;∥链表指针指向最小元素
}
else{∥查找元素值最小的结点
while（q->next!
=NULL&&q->next->datadata）
q=q->next;
p->next=q->next;∥将当前排序结点链入有序链表中
q->next=p;
}
p=r;∥p指向下个待排序结点
}
}
算法时间复杂度的分析与用顺序存储结构时的情况相同。
但顺序存储结构将第i（i>1）个元素插入到前面第1至第i-1个元素的有序表时，是将第i个元素先与第i-1个元素比较。
而在链表最佳情况均是和第一元素比较。
两种存储结构下最佳和最差情况的比较次数相同，在链表情况下，不移动元素，而是修改结点指针。
另外，本题中线性链表list不带头结点，而且要求“不得使用除该链表以外的任何链结点空间”，所以处理复杂，需要考虑当前结点元素值比有序链表第一结点的元素值还小的情况，这时要修改链表指针list。
如果list是头结点的指针，则相应处理要简单些，其算法如下：
LinkListLinkListSort（LinkList&list）{//list是带头结点的线性链表
LNode*p=list->next;∥p指向第一元素结点
list->next=NULL;∥有序链表初始化为空
while（p!
=NULL）{
r=p->next;∥保存后继
q=list;
while（q->next!
=NULL&&q->next->datadata）
q=q->next;
p->next=q->next;
q->next=p;
q=r;
}
}
解析：
无
18
设单链表的表头指针为h，链表中结点构造为（data，next），其中data域为字符型。
编写算法判断该链表的前n个字符是否中心对称。
例如xyx,xyyx都是中心对称。
∙参考答案是：
【分析】判断链表中数据是否中心对称，通常使用栈。
将链表的前一半元素依次进栈。
在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。
这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。
【解答】用C语言算法描述如下：
intdc（LinkListh，intn）{
chars[];inti=1；∥i记结点个数，s字符栈
LNode*p=h->next；∥p是链表的工作指针，指向待处理的当前元素。
for（i=1；i<=n/2；i++）{∥链表前一半元素进栈。
s[i]=p->data；
p=p->next；
}
i--;∥恢复最后的i值
if（n%2==1）p=p->next；∥若n是奇数，后移过中心结点
while（p!
=NULL&&s[i]==p->data）{∥测试是否中心对称
i--；
p=p->next；
}
if（p==NULL）return1；∥链表中心对称
elsereturn0；∥链表不中心对称
}
算法中先将“链表的前一半”元素（字符）进栈。
当n为偶数时，前一半和后一半的个数相同；当n为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。
比较过程中遇到不相等时，立即退出while循环，不再进行比较。
解析：
无
19
设有一个带头结点的循环双链表，所有元素值均为整数，设计一个算法输出其倒数第k个结点的值。
∙参考答案是：
【分析】通过头结点的prior域查找到尾结点，再沿prior域向前查找k-1次，即找到倒数第k个结点。
【解答】用C语言算法描述如下：
intfindk（DuLinkListL,intk）{
inti=1;
DuLNode*p=L->prior;//p指向尾结点，i置为1
while（p!
=L&&ii++;
p=p->prior;
}
if（p==L）//未找到则返回0
return0;
else{//找到倒数第k个结点，输出其值并返回1
printf（”%d\n”,p->data）;
return1;
}
}
解析：
无
20
已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。
∙参考答案是：
【分析】在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。
这时继续查到A的尾结点，以便插入B链表使用。
这时也得到了删除元素后的A链表。
再查B链表的第j个元素，将A链表插入之。
插入和删除中应注意前驱后继关系，不能使链表“断链”。
另外，算法中应判断i，len和j的合法性。
【解答】用C语言算法描述如下：
LinkListDelInsert（LinkListheada，headb，inti，j，len）{
if（i<1||len<1||j<1）{
printf（“参数错误\n”）；
exit（0）；∥参数错则退出算法
}
p=heada；/*p为链表A的工作指针，初始化为A的头指针，查到第i个元素时，p指向第i-1个元素*/
k=0；∥计数
while（p!
=NULL&&kk++；
p=p->next；
}
if（p==NULL）{
printf（“给的%d太大\n”,i）；
exit（0）；∥i太大，退出算法
}
q=p->next；∥q为工作指针，初始指向A链表第一个被删结点
k=0；
while（q!
=NULL&&kk++；
u=q;
q=q->next；
free（u）；
}
if（kprintf（“给的%d太大\n”,len）；
exit（0）；∥ken太大，退出算法
}
p->next=q；∥A链表删除了len个元素
if（heada->next!
=NULL）{/*若heada->next=NULL说明链表中结点均已删除，无需往B表插入*/
while（p->next!
=NULL）∥找A的尾结点
p=p->next；
q=headb；∥q为链表B的工作指针
k=0；∥计数
while（q!
=NULL&&kk++；
q=q->next；∥查找成功时，q指向第j-1个结点
}
if（q==NULL）{
printf（“给的%d太大\n”,j）；
exit（0）；∥j太大，退出算法
}
p->next=q->next；∥将A链表链入
q->next=heada->next；∥A的第一元素结点链在B的第j-1个结点之后
}
free（heada）；∥释放A表头结点。
}
解析：
无
重点回顾
1.线性表的逻辑结构
注：
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：
（a1，a2，…ai-1，ai，ai+1，…an）其中n为表长，n＝0时称为空表。
需要说明的是：
ai为序号为i的数据元素（i=1,2,…,n）。
2.线性
升级会员 