2.2 强化习题详解
【基础知识题】
1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
答：首元结点：链表中存储第一个数据元素a1的结点。
头结点：在单链表的第一个结点之前附设一个结点，这个结点的数据域可以不存储任何信息，也可以存储线性表的长度等。
头指针：指向链表中第一个结点的指针。若链表中附设头结点，则不管线性表是否为空表，头指针皆不为空，否则表示空表的链表的头指针为空。
2填空题。
（1）在顺序表中插入或删除一个元素，需要平均移动______元素，具体移动的元素个数与______有关。
（2）顺序表中逻辑上相邻的元素的物理位置______紧邻。单链表中逻辑上相邻的元素的物理位置______紧邻。
（3）在单链表中，除了首元结点外，任一结点的存储位置由______指示。
（4）在单链表中设置头结点的作用是______。
答：（1）表中一半；待删除元素在表中的位置
（2）必定；不一定
（3）其前驱结点的指针域的值
（4）插入和删除首元结点时不用进行特殊处理
3在什么情况下用顺序表比链表好？
答：顺序表中逻辑关系上相邻的两个元素在物理位置上也相邻，因此当数据元素在物理位置上是连续存储的时候，或者需要对数据元素进行随机存储时，用顺序表比用链表好。
4对以下单链表分别执行下列各程序段，并画出结果示意图。
图2-9 4题图
（1）Q=P->next;
（2）L=P->next;
（3）R->data=P->data;
（4）R->data=P->next->data;
（5）P->next->next->next->data=P->data;
（6）
T=P;
While(T!=NULL)
{
T->data=T->data*2;
T=T->next;
}
（7）
T=P;
While(T->next!=NULL)
{
T->data=T->data*2;
T=T->next;
}
答：结果示意图分别如图2-10～图2-16所示。
（1）
图2-10 结果示意图（1）
（2）
图2-11 结果示意图（2）
（3）
图2-12 结果示意图（3）
（4）
图2-13 结果示意图（4）
（5）
图2-14 结果示意图（5）
（6）
图2-15 结果示意图（6）
（7）
图2-16 结果示意图（7）
【注意】（6）、（7）问实则不同，由于题设中S节点后续还有其他的节点，所以两题结果相同。但是它们表示的意义却不一样，需要注意。
5画出执行下列各行语句后各指针及链表的示意图。
L=(LinkList)malloc(sizeof(LNode));
P=L;
for(i=1;i<=4;i++)
{
P->next=(LinkList)malloc(sizeof(LNode));
P=P->next;
P->data=i*2-1;
}
P->next=NULL;
for(i=4;i>=1;i--)
Ins_LinkList(L,i+1,i*2);
for(i=1;i<=3;i++)
Del_LinkList(L,i);
答：根据所给程序，其链表结构变化如图2-17所示。
图2-17 链表结构变化图
6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a．在P结点后插入S结点的语句序列是______。
b．在P结点前插入S结点的语句序列是______。
c．在表首插入S结点的语句序列是______。
d．在表尾插入S结点的语句序列是______。
（1）P->next=S;
（2）P->next=P->next->next;
（3）P->next=S->next;
（4）S->next=P->next;
（5）S->next=L;
（6）S->next=NULL;
（7）Q=P;
（8）while(P->next!=Q)P=P->next;
（9）while(P->next!=NULL)P=P->next;
（10）P=Q;
（11）P=L;
（12）L=S;
（13）L=P;
答：a．（4）（1）；
b．（7）（11）（8）（4）（1）；
c．（5）（12）；
d．（9）（1）（6）。
【注意】b问，单链表中在某一结点前插入一个结点需要遍历该单链表，找到其前驱节点，再进行插入操作。
7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a．删除P结点的直接后继结点的语句序列是______。
b．删除P结点的直接前驱结点的语句序列是______。
c．删除P结点的语句序列是______。
d．删除首元结点的语句序列是______。
e．删除尾元结点的语句序列是______。
（1）P=P->next;
（2）P->next=P;
（3）P->next=P->next->next;
（4）P=P->next->next;
（5）
while(P!=NULL)
P=P->next;
（6）
while(Q->next!=NULL)
{
P=Q;
Q=Q->next;
}
（7）
while(P->next!=Q)
P=P->next;
（8）
while(P->next->next!=Q)
P=P->next;
（9）
while(P->next->next!=NULL)
P=P->next;
（10）Q=P;
（11）Q=P->next;
（12）P=L;
（13）L=L->next;
（14）free(Q);
答：a．（11）（3）（14）；
b．（10）（12）（8）（3）（14）；
c．（10）（12）（7）（3）（14）；
d．（12）（11）（3）（14）；
e．（9）（11）（3）（14）。
8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a．在P结点后插入S结点的语句序列是______。
b．在P结点前插入S结点的语句序列是______。
c．删除P结点的直接后继结点的语句序列是______。
d．删除P结点的直接前驱结点的语句序列是______。
e．删除P结点的语句序列是______。
（1）P->next=P->next->next;
（2）P->prior=P->prior->prior;
（3）P->next=S;
（4）P->prior=S;
（5）S->next=P;
（6）S->prior=P;
（7）S->next=P->next;
（8）S->prior=P->prior;
（9）P->prior->next=P->next;
（10）P->prior->next=P;
（11）P->next->prior=P;
（12）P->next->prior=S;
（13）P->prior->next=S;
（14）P->next->prior=P->prior;
（15）Q=P->next;
（16）Q=P->prior;
（17）free(P);
（18）free(Q);
答：a．（7）（3）（6）（12）；
b．（8）（4）（5）（13）；
c．（15）（1）（11）（18）；
d．（16）（2）（10）（18）；
e．（14）（9）（17）。
【注意】在6、7、8题中画示意图更有利于理解，尤其是7（b）类型的题，画图更加直观。
9简述以下算法的功能。
（1）
Status A(LinkedList L)
{
//L是无表头结点的单链表
if(L&&L->next)
{
Q=L;
L=L->next;
P=L;
while(P->next)
P=P->next;
P->next=Q;
Q->next=NULL;
}
return OK;
} //A
（2）
void BB(LNode *s, LNode *q)
{
p=s;
while(p->next!=q)
p=p->next;
p->next =s;
} //BB
void AA(LNode *pa, LNode *pb)
{
//pa和pb分别指向单循环链表中的两个结点
BB(pa,pb);
BB(pb,pa);
} //AA
答：（1）L的长度大于1时（条件判断语句“if(L&&L->next)”），将L的首元结点变成尾元结点。
（2）将单循环链表拆成两个单循环链表。
10指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。
Status DeleteK(SqList &a,int i,int k)
{
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if(i<1||k<0||i+k>a.length)
return INFEASIBLE; //参数不合法
else
{
for(count=1;count<k;count++)
{
//删除第一个元素
for(j=a.length;j>=i+1;j- -)
a.elem[j-i]=a.elem[j];
a.length--;
}
return OK;
} //Delete OK
答：错误有两处：
（1）参数不合法及判别条件不完整。合法的入口参数为：
(0<i≤a.length)∧(0≤k≤a.length-i)
（2）内层for循环语句错误，元素前移的次序错误。
低效之处：每次只删除了一个元素。
程序改写为：
Status DeleteK(SqList &a,int i,int k)
{
//从顺序存储结构的线性表a中删除从第i个元素起的k个元素
//注意i的编号从0开始
int j;
if(i<0||i>a.length-1||k<0||k>a.length-i)
return INFEASIBLE;
for(j=0;j<=k;j++)
a.elem[j+i-1]=a.elem[j+i+k-1];
a.length=a.length-k;
return OK;
}
【算法设计题】
11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
答：
Status InsertOrderList(SqList &va,ElemType x)
{
//在递增有序的顺序表va中插入元素x,使其仍为顺序表的算法
int i;
//如果表的长度已经等于表的容量,不能再进行插入,直接返回,否则会溢出
if(va.length==va.listsize)
return(OVERFLOW);
//从表尾依次往前循环比较
for(i=va.length;i>0,x<va.elem[i-1];i--)
va.elem[i]=va.elem[i-1];
va.elem[i]=x;
va.length++;
return OK;
}
12设A＝（a1，…，am）和B＝（b1，…，bn）均为顺序表，A′和B′分别为A和B中除去最大共同前缀后的子表（例如，A＝（x，y，y，z，x，z），B＝（x，y，y，z，y，x，x，z），则两者中的最大共同前缀为（x，y，y，z），在两表中除去最大共同前缀后的子表分别为A′＝（x，z）和B′＝（y，x，x，z））。若A′＝B′＝空表，则A＝B；若A′＝空表，而B′≠空表，或者两者均不为空表，且A′的首元小于B′的首元，则A＜B；否则A＞B。试写一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B，并且，也不一定先求得A′和B′才进行比较）。
答：
Status CompareOrderList(SqList &A,SqList &B)
//比较字符表A和B，并用返回值j表示结果，值为1，表示A＞B；值为－1，表示A＜B；值为零，表示A＝B
{
int i,k,j;
//将表A和表B较大的长度值赋给变量k，以便在循环条件中使用
k=A.length>B.length?A.length:B.length;
for(i=0;i<k;i++)
{
if(A.elem[i]>B.elem[i])
j=1;
if(A.elem[i]<B.elem[i])
j=-1;
}
if(A.length>k)
j=1;
if(B.length>k)
j=-1;
if(A.length==B.length)
j=0;
return j;
}
13试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,x)。
答：
LNode* Locate(LinkList L,int x)
//链表上的元素查找，返回指针，该指针指向元素x
{
for(p=L->next;p&&p->data!=x;p=p->next);
if(p==NULL)
return NOTFOUND; //即链表L中不存在数X
return p; //存在数X，返回指针
} //Locate
14试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。
答：
//返回单链表的长度
int Length(LinkList L)
{
//判断指针p的后继只要不为空，说明还未达到链表表尾，继续循环判断
for(k=0,p=L;p->next;p=p->next,k++);
return k;
} //Length
15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
答：
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)
//把链表hb接在ha后面形成链表hc
{
p=ha;
while(p->next)
p=p->next; //循环，直到达到表ha的最后一个结点
//将ha最后一个结点的指针指向表hb的头指针，即将表hb链接在表ha后面
p->next=hb;
hc=ha;
} //ListConcat
基本运算语句为“p=p->next;”，被重复执行的次数为链表ha的长度，因此时间复杂度为T（n）＝O（n）。
16已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。
Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)
{
if(i<0||j<0||len<0)
return INFEASIBLE;
p=la;
k=1;
while(k<i)
{
p=p->next;
k++;
}
q=p;
while(k<=len)
{
q=q->next;
k++;
}
s=lb;
k=1;
while(k<j)
{
s=s->next;
k++;
}
s->next=p;
q->next=s->next;
return OK;
} //DeleteAndInsertSub
答：不正确。
Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)
{
if(i<0||j<0||len<0)
return INFEASIBLE;
//在la表中查找第i个结点
p=la;
k=1;
prev=NULL;
while(p&&k<i)
{ //循环条件应该加上指针p即链表la的非空判断
prev=p;
p=p->next;
k++;
}
if(!p)
return INFEASIBLE;
//在la表中查找第i＋len－1个结点
q=p;
k=1;
while(q&&k<len){ //循环条件应该加上指针q即链表la的非空判断
q=p->next;
k++;
}
if(!q)
return INFEASIBLE;
//完成删除
if(!prev)
la=q->next;
else
prev->next=q->next;
//将从la中删除的结点插入到lb中
if(j==1)
{ //j＝1的情况需要特殊处理
q->next=lb;
lb=p;
}
else
{
s=lb;
k=1;
while(s&&k<j-1)
{ //循环条件应该加上指针s即链表lb的非空判断
s=s->next;
k++;
}
if(!s)
return INFEASIBLE;
q->next=s->next;
s->next=p; //完成插入
}
return OK;
}
17试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。
答：
Status Insert(LinkList &L,int i,int b)
//在无头结点链表L的第i个元素之前插入元素b
{
p=L;
q=(LinkList*)malloc(sizeof(LNode)); //动态创建结点q
q.data=b; //元素b即为结点q的数据域
if(i= =1) //考虑首元结点
{
q.next=p;
L=q; //q插入在链表头部
}
else
{
while(--i>1)
p=p->next; //找到第i-1个结点
q->next=p->next;
p->next=q; //插入在第i个元素的位置
}
} //Insert
头结点的作用是插入和删除操作时不必对首元结点做特殊处理，因此在带头结点的动态单链表上实现删除操作不必单独考虑i＝1时的特殊情况，可统一处理。
18同17题要求。试写一算法，实现线性表操作DELETE(L,i)。
答：
Status Delete(LinkList &L,int i)
//在无头结点链表L中删除第i个元素
{
p=L;
if(i<1||i>L.length)
return false; //不合理的位置
if(i= =1)
{ //考虑首元结点
L=L->next; //删除第一个元素
free(p); //释放存储空间
}
else
{
while(--i>1)
p=p->next; //找到第i-1个元素
q=p->next; //记录下第i个元素,后面需要释放其内存
p->next=p->next->next; //删除第i个元素
free(q); //释放第i个结点所占的内存
}
} //Delete
19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
答：合法的入口条件只要求线性表不空。若mink＞maxk则表明待删元素集为空集。
Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)
{ //删除元素按递增排列的链表L中值大于mink且小于maxk的所有元素
LinkList p,q,prev=NULL;
if(mink>maxk)
return ERROR; //[mink,maxk]区间错误，退出程序
if(maxk <L->data)
return ERROR; //链表有序，且最小结点的数据大于maxk，则直接退出程序
p=L;
prev=p; //prev为p的前驱
p=p->next;
while(p&&p->data<maxk)
{ //p的数据域要小于maxk
if(p->data<=mink)
{ // p的数据域要小于mink
prev=p;
p=p->next; //指针后移，继续比较
}
else
{ //如果同时p的数据域大于mink
prev->next=p->next;
q=p;
p=p->next; //删除p所指的元素结点
free(q); //释放存储空间
}
}
return OK;
}
时间复杂度为T（n）＝O（n2）
20同19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。
答：
Status Delete_Equal(Linklist &L) //删除元素按递增排列的链表L中所有值相同的元素
{
p=L;
q=p->next; //p，q指向相邻两元素，其中q为p的后继结点
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;
q=p->next; //当相邻两元素不相等时，p和q都向后移动一个结点位置
}
else
{ //相邻两个元素相等
while(q->data==p->data)
{ //比较q后面的元素是否还和p与q元素相等，如果相等，则删除
r=q;
q=q->next;
free(r); //释放存储空间
}
p->next=q;
p=q;
q=p->next; //当相邻元素相等时删除多余元素
} //else
} //while
} //Delete_Equal
时间复杂度为T（n）＝O（n3）
21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1，a2，…，an）逆置为（an，an－1，…，a1）。
答：
//顺序表的逆置
Status ListOppose_Sq(SqList &L)
{
int i;
ElemType x; //临时元素x，是一个中间变量，交换元素时用
for(i=0;i<L.length/2;i++)
{
//交换第i个元素和第L.length－1－i个元素，实现逆置
x=L.elem[i];
L.elem[i]=L.elem[L.length-1-i];
L.elem[L.length-1-i]=x;
}
return OK;
}
22试写一算法，对单链表实现就地逆置。
答：将原链表中的头结点和第一个元素结点断开，先构成一个新的空表，然后将原链表中各结点，从第一个结点起插入这个新表的头部。
//链表的就地逆置，为简化算法，假设表长大于2
void LinkList_reverse(Linklist &L)
{
//定义q为p的后继，s为q的后继
p=L->next;
q=p->next;
s=q->next;
p->next=NULL;
while(s->next)
{
q->next=p;
p=q;
q=s;
s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;
s->next=q;
L->next=s;
} //LinkList_reverse
23设线性表A＝（a1，a2，…，am），B＝（b1，b2，…，bn），试写一个按下列规则合并A，B为线性表C的算法，即使得
C＝（a1，b1，…，am，bm，bm＋1，…，bn） 当m≤n时
或者
C＝（a1，b1，…，an，bn，an＋1，…，am） 当m＞n时
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
答：
//将合并后的结果放在C表中，并删除B表
Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb;
pa=A->next; //pa为链表A的首元结点
pb=B->next; //pb为链表B的首元结点
C=A;
while(pa&&pb)
{
qa=pa;
qb=pb;
pa=pa->next;
pb=pb->next;
qb->next=qa->next;
qa->next=qb; //将链表B中的元素链接到链表A后面
}
if(!pa)
qb->next=pb;
pb=B;
free(pb); //将链表B删除，释放表B的表头
return OK;
}
24假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。
答：采用“指针平移，一次扫描”的策略。
//将合并逆置后的结果放在C表中
Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb;
pa=A;
pb=B;
qa=pa; //qa保存pa的前驱指针
qb=pb; //qb保存pb的前驱指针
pa=pa->next;
pb=pb->next;
A->next=NULL;
C=A;
while(pa&&pb)
{
if(pa->data<pb->data)
{ //若表A当前结点小于表B当前结点
qa=pa;
pa=pa->next;
qa->next=A->next; //将当前最小结点插入A表表头
A->next=qa;
}
else
{ //若表B当前结点小于表A当前结点
qb=pb;
pb=pb->next;
qb->next=A->next;
A->next=qb;
}
}
while(pa)
{ //表A中仍有结点
qa=pa;
pa=pa->next;
qa->next=A->next;
A->next=qa; //将表A剩余的所有结点链接到C表
}
while(pb)
{ //表B中仍有结点
qb=pb;
pb=pb->next;
qb->next=A->next; //将表B剩余的所有结点链接到C表
A->next=qb;
}
pb=B;
free(pb); //释放表B表头
return OK;
}
25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。
答：
//将A、B求交后的结果放在C表中
//线性表从0开始存储
Status ListCross_Sq(SqList &A,SqList &B,SqList &C)
{
int i=0,j=0;
while(i<A.length && j<B.length)
{
//如果表A中元素值较小，表A元素下标增1，即向后移动一个位置
if(A.elem[i]<B.elem[j])
i++;
else
//如果表B中元素值较小，表B元素下标增1，即向后移动一个位置
if(A.elem[i]>B.elem[j])
j++;
else
{
//A和B中的元素值相等，即得到A和B的交集元素，放到C中，A、B下标均后移一个单位
ListInsert_Sq(C,k,A.elem[i]);
i++;
j++;
}
}
return OK;
}
26要求同25题。试对单链表编写求C的算法。
答：
//将A、B求交后的结果放在C表中，并删除B表
Status ListCross_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; //qa保存pa的前驱指针
qb=pb; //qb保存pb的前驱指针
pa=pa->next;
pb=pb->next;
C=A;
while(pa&&pb)
{
//如果pa数据域的值较小，则pa指向其后继结点，同时更新qa
if(pa->data<pb->data)
{
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
//如果pb数据域的值较小，则pb指向其后继结点，同时更新qb
else if(pa->data>pb->data)
{
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
else
{
//pa和pb数据域的值相等，即为交集元素，放到C中
qa=pa;
pa=pa->next;
qb=pb;
pb=pb->next;
}
}
while(pa)
{ //链表A有剩余结点
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt); //释放链表A的表头
}
while(pb){ //链表B有剩余结点
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt); //释放链表B的表头
}
pb=B;
free(pb); //删除链表B
return OK;
}
27对25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。
（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；
（2）利用A表空间存放表C。
答：（1）
Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C)
// A、B求交，然后删除相同元素，将结果放在C表中
{
int i=0,j=0,k=0;
while(i<A.length && j<B.length)
{
if(A.elem[i]<B.elem[j])
i++; //A表中元素较小，A下标增1，向后移动
else
if(A.elem[i]>B.elem[j])
j++; //B表中元素较小，B下标增1，向后移动
else
{
if(C.length==0)
{ //如果C表为空表，直接依次插入
ListInsert_Sq(C,k,A.elem[i]);
k++;
}
else //否则，判断有无重复元素，再插入，注意A、B、C都有序这一特性
if(C.elem[C.length-1]!=A.elem[i])
{
ListInsert_Sq(C,k,A.elem[i]);
k++;
}
i++;
}
}
return OK;
}
（2）
//A、B求交，然后删除相同元素，将结果放在A表中
Status ListCrossDelSame_Sq(SqList &A,SqList &B)
{
int i=0,j=0,k=0; //k用于保存更新值后的A表的下标
while(i<A.length && j<B.length)
{
if(A.elem[i]<B.elem[j])
i++; //A表中元素较小，A下标增1，向后移动
else
if(A.elem[i]>B.elem[j])
j++; //B表中元素较小，B下标增1，向后移动
else
{
if(k==0)
{ //将相同元素放到A表中
A.elem[k]=A.elem[i];
k++;
}
else //判断是否有重复元素，利用有序性，只需要检查更新的A表中最后一个元素
if(A.elem[k-1]!=A.elem[i])
{
A.elem[k]=A.elem[i];
k++;
}
i++;
}
}
A.length=k;
return OK;
}
28对25题的条件作以下两点修改，对单链表重新编写求得表C的算法。
（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；
（2）利用原表（A表或B表）中的结点构成表C，并释放A表中的无用的结点空间。
答：（1）
Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkList &C)
//A、B求交，结果放在C表中，并删除相同元素
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; //qa保存pa的前驱指针
qb=pb; //qb保存pb的前驱指针
pa=pa->next;
pb=pb->next;
C=A; //C指向链表A
while(pa&&pb)
{
if(pa->data<pb->data)
{ //如果A中元素值小于B中元素值
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else
if(pa->data>pb->data)
{ //如果A中元素值大于B中元素值
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt); //释放B中该元素结点
}
else
{
if(pa->data==qa->data)
{ //如果B中元素值等于A中元素值
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt); //释放A中该元素结点
}
else
{
qa=pa;
pa=pa->next;
}
}
}
while(pa)
{
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
while(pb)
{
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
（2）
//A、B求交，结果放在A表中，并删除相同元素
Status ListCrossDelSame_L(LinkList &A,LinkList &B)
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; //qa保存pa的前驱指针
qb=pb; //qb保存pb的前驱指针
pa=pa->next;
pb=pb->next;
while(pa&&pb)
{
if(pa->data<pb->data)
{ //如果A中元素小于B中元素
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt); //释放A中该元素结点
}
else
if(pa->data>pb->data)
{ //如果B中元素小于A中元素
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt); //释放B中该元素结点
}
else
{
if(pa->data==qa->data)
{
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else
{
qa=pa;
pa=pa->next;
}
}
}
while(pa)
{
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
while(pb)
{
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
29已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。
答：
void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
{
int i=0;
int j=0;
int k=0;
int m=0; //i指示A中元素原来的位置，m为移动后的位置
while(i<A.length&&j<B.length&& k<C.length)
{
if(B.elem[j]<C.elem[k])
j++;
else if(B.elem[j]>C.elem[k])
k++;
else
{
same=B.elem[j]; //找到了B和C中相同元素same
while(B.elem[j]= =same)
j++; //考虑到表中有重复元素
while(C.elem[k]= =same)
k++; //j，k后移到新的元素
while(i<A.length&&A.elem[i]<same)
A.elem[m++]=A.elem[i++]; //在A表中依次查找小于same的元素，同时移动m
while(i<A.length&&A.elem[i]==same)
i++; //跳过相同的元素，m不变，即作删除操作
}
} //while
while(i<A.length)
A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储｡
A.length=m;
} //SqList_Intersect_Delete
分析：先从B和C中找出共有元素，记为same，并记下位置，在A中从当前位置开始，凡小于same的元素均保留（存到新的位置），等于same的就跳过，到大于same时就再找下一个same。时间复杂度为T（n）＝O（n3）。
30要求同29题。试对单链表编写算法，请释放A表中的无用结点空间。
答：
//在A中删除既在B中出现又在C中出现的元素，并释放B、C
Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C)
{
ListCross_L(B,C);
ListMinus_L(A,B);
}
Status ListMinus_L(LinkList &A,LinkList &B) //求集合A－B，结果放在A表中，并删除B表
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; //qa保存pa的前驱指针
qb=pb; //qb保存pb的前驱指针
pa=pa->next;
pb=pb->next;
while(pa&&pb)
{
if(pb->data<pa->data)
{ //如果B中元素小于A中元素
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt); //释放B中该元素结点
}
else
if(pb->data>pa->data)
{ //如果B中元素大于A中元素
qa=pa;
pa=pa->next;
}
else
{
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt); //释放A中该元素结点
}
}
while(pb)
{
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb); //释放B的首元结点，即删除B
return OK;
}
时间复杂度为T（n）＝O（n3）
31假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
答：
//在单循环链表中删除指针s所指结点的前驱结点
Status ListDelete_CL(LinkList &s)
{
LinkList p,q;
if(s==s->next)
return ERROR; //s为空表
q=s;
p=s->next; //q为p的前驱，p为s的后继
while(p->next!=s)
{
q=p;
p=p->next;
}
q->next=p->next;
free(p); //删除并释放结点p
return OK;
}
32已知有一个单向循环链表，其每个结点中含三个域：prior，data和next，其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为空（NULL），试编写算法将此单向循环链表改为双向循环链表，即使prior成为指向前驱结点的指针域。
答：
Status DuLNode_Pre(DuLinkList &L) //将单向循环链表改为双向循环链表
{
for(p=L;!p->next->prior;p=p->next)
p->next->prior=p;
return OK;
} //DuLNode_Pre
33已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。
答：
Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)
//把单链表L的元素按类型分为三个循环链表，CiList为带头结点的单循环链表类型
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));
p=A; //动态创建头结点
B=(CiList*)malloc(sizeof(CiLNode));
q=B;
C=(CiList*)malloc(sizeof(CiLNode));
r=C; //建立头结点
while(s)
{
if(isAlphabet(s->data)) //数据域为字母字符
{
p->next=s;
p=s;
}
else if(isDigit(s->data))
{ //数字字符
q->next=s;
q=s;
}
else //其他字符
{
r->next=s;
r=s;
}
} //while
p->next=A;
q->next=B;
r->next=C; //完成循环链表
} //LinkList_Divide
在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为：
typedef struct XorNode
{
char data;
struct XorNode * LRPtr;
}XorNode, *XorPointer;
typedef struct
{ //无头结点的异或指针双向链表
XorPointer Left, Right; //分别指向链表的左侧和右端
}XorLinkedList;
XorPointer XorP(XorPointer p, XorPointer q);//指针异或函数XorP返回指针p和q的异或（XOR）值
34假设在算法描述语言中引入指针的二元运算“异或”（用“⊕”表示），若a和b为指针，则a⊕b的运算结果仍为原指针类型，且
a⊕（a⊕b）＝（a⊕a）⊕b＝b
（a⊕b）⊕b＝a⊕（b⊕b）＝a
则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。
答：
Status TraversingLinkList(XorLinkedList &L,char d) //d指示遍历的方向
{
XorPointer p,left,right;
if(d=='l'||d=='L')
{
p=L.Left; //p指向链表的最左结点
left=NULL;
while(p!=NULL)
{
VisitingData(p->data); //循环遍历
left=p;
p=XorP(left,p->LRPtr);
}
}
else
if(d=='r'||d=='R')
{
p=L.Right; //p指向链表的最右结点
right=NULL;
while(p!=NULL)
{
VisitingData(p->data); //循环遍历
right=p;
p=XorP(p->LRPtr,right);
}
}
else
return ERROR;
return OK;
}
35采用34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。
答：
Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)
//在异或链表L的第i个元素前插入元素x
{
p=L.left;
pre=NULL;
r=(XorNode*)malloc(sizeof(XorNode));
r->data=x;
if(i<1)
return FALSE; //位置不合理，返回错误
if(i==1) //当插入点在最左边的情况
{
p->LRPtr=XorP(p.LRPtr,r);
r->LRPtr=p;
L.left=r;
return OK;
}
j=1;
q=p->LRPtr; //当插入点在中间的情况
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
} //while //在p,q两结点之间插入
if(!q)
return INFEASIBLE; //i不可以超过表长
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
q->LRPtr=XorP(XorP(q->LRPtr,p),r);
r->LRPtr=XorP(p,q); //修改指针
return OK;
} //Insert_XorLinkedList
36采用34题所述的存储结构，写出删除第i个结点的算法。
答：
Status Delete_XorLinkedList(XorlinkedList &L,int i) //删除异或链表L的第i个元素
{
p=L.left;
pre=NULL;
if(i<1||i>L.length)
return FALSE; //位置不合理，返回错误
if(i==1) //当删除的结点在链表的最左边
{
q=p->LRPtr;
q->LRPtr=XorP(q->LRPtr,p);
L.left=q;free(p); //释放结点p
return OK;
}
j=1;
q=p->LRPtr;
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;
p=q;
} //找到待删结点q
if(!q)
return INFEASIBLE; //i不可以超过表长
if(L.right==q) //q为最右结点的情况
{
p->LRPtr=XorP(p->LRPtr,q);
L.right=p;free(q);
return OK;
}
r=XorPq->LRPtr,p); //q为中间结点的情况，此时p，r分别为其左右结点
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针
free(q); //释放结点q
return OK;
} //Delete_XorLinkedList
37设以带头结点的双向循环链表表示的线性表L＝（a1，a2，…，an）。试写一时间复杂度O（n）的算法，将L改造为L＝（a1，a3，…，an，…，a4，a2）。
答：时间复杂度为O（n），即基本运算语句执行的次数与链表表长同数量级。
void OEReform(DuLinkedList &L) //按1，3，5，…，4，2的顺序重排双向循环链表L中的所有结点
{
p=L->next; //p为L的首元结点
while(p->next!=L&&p->next->next!=L)
{
p->next=p->next->next;
p=p->next;
} //此时p 指向最后一个奇数结点
if(p->next==L)
p->next=L->pre->pre;
else
p->next=L->pre;
p=p->next; //此时p 指向最后一个偶数结点
while(p->pre->pre!=L)
{
p->next=p->pre->p re;
p=p->next;
}
p->next=L; //按题目要求调整了next链的结构，此时pre链仍为原状
for(p=L;p->next!=L;p=p->next)
p->next->pre=p;
L->pre=p; //调整pre链的结构
} //OEReform
38设有一个双向循环链表，每个结点中除有prior，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。
答：
DuLinkList ListLocate_DuL(DuLinkList &L,ElemType e)
{
DuLinkList p,q;
p=L->next;
while(p!=L&&p->data!=e)
p=p->next;
if(p==L)
return NULL; //空表，返回
else
{
p->freq++;
p->pre->next=p->next; //删除结点
p->next->pre=p->pre;
//插入到合适的位置
q=L->next;
while(q!=L && q->freq>p->freq)
q=q->next;
if(q==L)
{ //q为头结点，在q后面插入
p->next=q->next;
q->next=p;
p->pre=q->pre;
q->pre=p;
}
else
{
//在q之前插入
p->next=q->pre->next;
q->pre->next=p;
p->pre=q->pre;
q->pre=p;
}
return p;
}
}
在2.39至2.40题中，稀疏多项式采用的顺序存储结构SqPoly定义为
typedef struct
{
int coef; //每一项的系数
int exp; //每一项的指数
}PolyTerm;
typedef struct
{
PolyTerm *data; //多项式的顺序存储结构
int length;
}SqPoly;
39已知稀疏多项式
其中n＝em＞em－1＞…＞e1≥0，ci≠0（i＝1，2，…，m），m≥1。试采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn（x0）的算法（x0为给定值），并分析你的算法的时间复杂度。
答：
typedef struct
{
int coef; //每一项的系数
int exp; //每一项的指数
}PolyTerm;
typedef struct
{
PolyTerm *data;
int last;
}SqPoly;
//建立一个多项式
Status PolyInit(SqPoly &L)
{
int i;
PolyTerm *p;
cout<<"请输入多项式的项数:";
cin>>L->last;
L->data=(PolyTerm *)malloc(L.last*sizeof(PolyTerm)); //动态创建结点
if(!L->data)
return ERROR; //判断是否成功分配空间
p=L->data;
for(i=0;i<L.last;i++)
{
cout<<"请输入系数:";
cin>>p->coef;
cout<<"请输入指数:";
cin>>p->exp;
p++;
}
return OK;
}
//求多项式的值
double PolySum(SqPoly &L,double x0)
{
double Pn,x;
int i,j;
PolyTerm *p;
p=L->data;
for(i=0,Pn=0;i<L.last;i++,p++)
{
for(j=0,x=1;j<p->exp;j++)
x=x*x0;
Pn=Pn+p->coef*x;
}
return Pn;
}
时间复杂度为T（n）＝O（n3）
40采用39题给定的条件和存储结构，编写求P（x）＝Pn1（x）－Pn2（x）的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。
答：
Status PolyMinus(SqPoly &L,SqPoly &L1,SqPoly &L2) //求两多项式的差
{
PolyTerm *p,*p1,*p2;
p=L->data;
p1=L1->data;
p2=L2->data;
int i=0,j=0,k=0;
while(i<L1->last&&j<L2->last)
{
if(p1->exp<p2->exp)
{ //多项式L1的指数小于多项式L2的指数
p->coef=p1->coef;
p->exp=p1->exp;
p++;
k++;
p1++;
i++;
}
else
if(p1->exp>p2->exp)
{ //多项式L1的指数大于多项式L2的指数
p->coef=-p2->coef;
p->exp=p2->exp;
p++;
k++;
p2++;
j++;
}
else
{
if(p1->coef!=p2->coef)
{
//L1和L2在该项的指数相同，则系数相减，L1的系数不等于多项式L2的系数
p->coef=(p1->coef)-(p2->coef);
p->exp=p1->exp;
p++;
k++;
}
p1++;
p2++;
i++;
j++;
}
}
if(i<L1->last) //L1未扫描完
while(i<L1->last)
{
p->coef=p1->coef; //新的多项式系数
p->exp=p1->exp; //新的多项式指数
p++;
k++;
p1++;
i++;
}
if(j<L2->last) //L2未扫描完
while(j<L2->last)
{
p->coef=-p2->coef;
p->exp=p2->exp;
p++;
k++;
p2++;
j++;
}
L->last=k;
return OK;
}
时间复杂度为T（n）＝O（n3）
在41至42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为
typedef struct PolyNode
{
PolyTerm data;
Struct PolyNode *next;
}PolyNode,*PolyLink;
typedef PolyLink LinkedPoly;
41试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。
答：
Status PolyDifferential(LinkedPoly &L)
{
If(!L)
return ERROR;
LinkedPoly p,q,pt;
q=L;
p=L->next; //q为p的前缀
while(p!=L)
{
if(p->data.exp==0)
{ //该多项式指数为0，即为常数，求导后为0，删除该结点
pt=p;
p=p->next;
q->next=p;
free(pt); //该项的导函数为0，释放该点
}
else
{ //该多项式系数等于系数乘以指数
p->data.coef*=p->data.exp;
p->data.exp--; //指数减1
q=p;
p=p->next;
}
}
return OK;
}
42试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。
答：
//将单链表L划分成2个单循环链表
Status ListDivideInto2CL(LinkedPoly &L,LinkedPoly &L1)
{
LinkedPoly p,p1,q,pt;
q=L;
p=L->next;
p1=L1;
while(p!=L)
{
if(p->data.exp%2==0)
{ //偶次项
pt=p;
p=p->next;
q->next=p;
pt->next=p1->next;
p1->next=pt;
p1=p1->next;
}
else
{
q=p;
p=p->next;
}
}
return OK;
}