第2章
综合练习
3. [题目分析] 题目要求将两个向量逆置,可以先将两个向量分别逆置,再将整个向量逆置。(也可以先将整个向量逆置,
再将两个向量分别逆置)
void reverse(ElemType A[])
//数组A中有m+n个元素,本算法将两个向量逆置,即将前m个元素移至n个元素之后
{ int i;
for (i=1;i<=m/2;i++) //将前m个元素逆置
A[i]<-->A[m-i+1]
for (i=1;i<=n/2;i++) //将后n个元素逆置
A[m+i]<-->A[m+n-i+1]
for (i=1;i<=(m+n)/2;i++) //将前m+n个元素逆置
A[i]<-->A[m+n-i+1]
}//算法结束
【算法讨论】题目中下标从1开始,若用C语言的从0开始,则可写为:
for (i=0;i<m/2;i++) //将前m个元素逆置
A[i]<-->A[m-i-1]
for (i=0;i<n/2;i++)
//将后n个元素逆置
A[m+i]<-->A[m+n-i-1]
for (i=0;i<(m+n)/2;i++) //将前m+n个元素逆置
A[i]<-->A[m+n-i-1]
4. [题目分析] 计算单链表的长度,即求单链表中元素个数。
int
number(LinkedList la)
//求不带头结点的单链表的长度
{i=0;
p=la; //p为工作指针
while (p)
{i++; p=p->next; }
return i;
}//算法结束
5. [题目分析] 因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。
LinkedList Union(LinkedList ha,hb)
∥ha,hb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。
{ pa=ha->next; pb=hb->next;∥pa，pb分别是链表ha和hb的工作指针
ha->next=null; ∥ha作结果链表的头指针，先将结果链表初始化为空。
while(pa!=null
&& pb!=null) ∥当两链表均不为空时作
if(pa->data<=pb->data)
{ r=pa->next; ∥将pa 的后继结点暂存于r。
pa->next=ha->next; ∥将pa结点链于结果表中，同时逆置。
ha->next=pa;
pa=r; ∥恢复pa为当前待比较结点。
}
else
{r=pb->next;∥ 将pb 的后继结点暂存于r。
pb->next=ha->next; ∥将pb结点链于结果表中，同时逆置。
ha->next=pb;
pb=r; ∥恢复pb为当前待比较结点。
}
if
(pa) pb=pa; //为了下面算法统一,不再单独处理pa
while(pb!=null)
{r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; }
free(hb); return(ha);
}∥算法Union结束。
【算法讨论】上面两链表均不为空的表达式也可简写为while(pa && pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后while语句，哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。
6. [题目分析] 在无序的单链表上，查找最小值结点，要查遍整个链表，初始假定第一结点是最小值结点。当找到最小值结点后，判断数据域的值是否是奇数，若是，则“与其后继结点的值相交换”,即仅仅交换数据域的值，用三个赋值语句即可交换。若与后继结点交换位置，则需交换指针，这时应知道最小值结点的前驱。至于删除后继结点，则通过修改最小值结点的指针域即可。
void
MiniValue（LinkedList la）
∥la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印。若最小值结点的数值是奇数，
∥则与后继结点值交换；否则，就删除其直接后继结点。
{p=la->next； ∥设la是头结点的头指针，p为工作指针。
pre=p； ∥pre指向最小值结点，初始假定首元结点值最小。
while（p->next!=null） ∥p->next是待比较的当前结点。
{if（p->next->data<pre->data）pre=p->next；
p=p->next；
∥后移指针
}
printf（“最小值=%d\n”，pre->data）；
if（pre->data%2!=0） ∥处理奇数
if（pre->next!=null）∥若该结点没有后继，则不必交换
{t= pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕
else∥处理偶数情况
if（pre->next!=null）∥若最小值结点是最后一个结点，则无后继
{u=pre->next；pre->next=u->next；free（u）；}
∥释放后继结点空间
7. [题目分析]在顺序表中查找指定值, 要从头到尾的查, 若为有序的顺序表,则可采用对分(折半)查找.
(1) ElemType MiniDelete(SeqList s)
//在顺序表中删除最小值元素,空出的位置由最后一个元素填补,返回最小值元素
{ElemType min; //min记最小值元素
k=0; //k记最小值元素下标,先假定第一个元素最小
for(i=1;i<s.length;i++)
if (s.data[i]<s.data[k] k=i;
min=s.data[k];
s.length--;
return min;
}//算法结束
(2) 为提高效率,可采用将被删元素空出的位置由最后元素填补的方式解决
void DeleteAllX(SeqList s,ElemType x)
//在顺序表s中删除所有值为x的元素
{i=0; j=s.length; //i,j是数组元素下标
while (i<j)
{while(i<j && s.data[i]!=x)
i++; //从左到右查找第一个值为x的元素
while(i<j &&
s.data[j]==x) j--; //从右到左查找第一个值不为x的元素
if (i<j)
s.data[i++]=s.data[j--];//被删元素空出的位置由最后元素填补
}
if (s.data[i]==x) s.length=i; else s.length=i+1; //置线性表的长度
}//算法结束
(3) void DeleteST(SeqList s)
//在顺序存储的有序表s中删除在给定值在s与t之间的所有元素
{i=0;
while(i<s.length
&& s.data[i]<s) i++;
//从左到右查找第一个值>=s的元素
if (i==s.length) {printf(“表中元素都小于s,无s与t间的元素”);exit(0);}
k=i; //k是第一个值>=s的元素的下标
while(i<s.length
&& s.data[i]<=t) i++;
//查找第一个值>t的元素
for (j=i;j<s.length;j++) //元素前移,覆盖被删元素
s.data[k++]=s.data[j]
s.length=k; //置线性表的长度
}//算法结束
【算法讨论】算法已包括表中最后一个元素也应删除的情况, 请考虑为什么。
14．[题目分析]双循环链表的倒置和单链表类似,单链表采用先将第一元素结点与头结点断开,
头结点指针域置空,然后,从第一元素结点起,依次将结点前插到头结点后面. 对双循环链表来说,第二元素结点和前部断开时,要将头结和第一元素结点先构成循环链表,然后从第二元素结点起,依次将结点前插到头结点后面.
void Reverse (DLinkedList DL)
{p=DL->next->next;
//p为工作指针, 指向第二元素结点(假定循环链表非空)
DL->prior=DL->next; //头结点和第一元素结点先构成循环链表,
DL->next->next=DL;
While (p!=DL)
{r=p->next; //暂存后继
p->next=DL->next;
//插入到头结点后,要修改4条链
p->prior=DL;
DL->next->prior=p;
DL->next=p;
p=r;
}
}//算法结束
15. 先设定多项式结点结构如下:
typedef struct node
{float coef; //系数
int exp; //指数
struct node *next; //指向后继的指针
}PolyNode, *Poly;
void
decpoly(Poly py)
//将稀疏多项式分解为只含奇次幂和偶次幂的两个多项式,利用原结点空间
{podd=(PolyNode
*)malloc(sizeof(PolyNode)); pod->next=pod; //空循环链表
//建立奇次幂链表的头结点的表头指针,
偶次幂链表的头结点仍用原链表
pd=podd; //pd指向奇次幂链表的尾结点
pn=py; //pn指向偶次幂链表的尾结点
p=py->next; //p工作指针
while (p)
{r=p->next; //将p 的后继结点暂存于r
if
(p->exp % 2 == 0) //偶次幂链表的结点
{p->next=pn->next;
pn->next=p;
pn=p;
}
else
//奇次幂链表的结点
{p->next=pd->next;
pd->next=p;
pd=p;
}
p=r; //取下个结点继续分解
}//while (p)
pn->next=py;//将偶次幂链表构成循环链表,即将最后结点的指针域指向原循环链表的头指针py
}//算法结束
17. [题目分析]本题要求将数据域key为整数类型的单链表，按照key 递增的顺序进行就地排序。可以利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开始，将各结点依次插入到有序链表中。
LinkedList InsertSort(LinkedList la)
∥la是带头结点的单链表，本算法按照key 递增的顺序进行就地排序,成为非递减有序链表。
{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;
}//while
}//if
}//算法结束
34．[题目分析] 留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。
LinkedList Common（LinkedList A，B，C）
∥A，B和C是三个带头结点且结点元素值非递减排列的有序表。本算法使A表仅留下三个表均包含的结点，且结点值不重复，释放所有结点。
{pa=A->next；pb=B->next；pc=C->next；∥pa,pb和pc分别是A,B和C三个表的工作指针。
pre=A；∥pre是A表中当前结点的前驱结点的指针。
while（pa && pb && pc）∥当A,B和C表均不空时，查找三表共同元素
{while（pa && pa->data==pa->next->data）
{u=pa->next；pa=u->next；free（u）；}∥删除pa中值相同元素
if（pa->data<pb->data）{u=pa；pa=pa->next；free（u）；}∥结点元素值小时，后移指针。
else if（pa->data>pb->data）pb=pb->next；
else if (pa &&
pb) ∥处理A和B表元素值相等的结点
{while（pc && pc->data<pa->data）pc=pc->next；
if(pc)
if（pc->data>pa->data）∥pc当前结点值与pa当前结点值不等,pa后移指针。
{u=pa；pa=pa->next；free（u）；}
else ∥pc，pa和pb对应结点元素值相等。
if(pre==A){
pre->next=pa；pre=pa；pa=pa->next} ∥结果表中第一个结点。
else {pre->next=pa；pre=pa；pa=pa->next；}∥将新结点链入A表。
pb=pb->next；pc=pc->next；∥链表的工作指针后移。
}// if (pa && pb) 处理A和B表元素值相等的结点
}∥while（pa
&& pb && pc）
if（pa==null）pre->next=null；∥原A表已到尾,置新A表表尾
else ∥处理原A表未到尾而B或C到尾的情况
{pre->next=null；
∥置A表表尾标记
while（pa!=null） ∥删除原A表剩余元素。
{u=pa；pa=pa->next；free（u）；}
}
}
[算法讨论] 算法中A表、B表和C表均从头到尾（严格说B、C中最多一个到尾）遍历一遍，算法时间复杂度符合O（m+n+p）。算法主要由while（pa && pb && pc）控制。三表有一个到尾则结束循环。算法中查到A表与B表和C表的公共元素后，又分三种情况处理：一是三表中第一个公共元素值相等的结点；第二种情况是，尽管不是第一结点，但与前驱结点元素值相同，不能成为结果表中的结点；第三种情况是新结点与前驱结点元素值不同，应链入结果表中，前驱指针也移至当前结点，以便与以后元素值相同的公共结点进行比较。算法最后要给新A表置结尾标记，同时若原A表没到尾，还应释放剩余结点所占的存储空间。