发布时间 : 星期三 文章数据结构课后习题答案详解（C语言版 - 严蔚敏） 2- 更新完毕开始阅读
pt=pa; pa=pa->next; qa->next=pa; free(pt); } else if(pa->data>pb->data){ pt=pb; pb=pb->next; qb->next=pb; free(pt); } 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; }
2.29 已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 解：
// 在A中删除既在B中出现又在C中出现的元素，结果放在D中 Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C) { SqList Temp; InitList_Sq(Temp); ListCross_L(B,C,Temp); ListMinus_L(A,Temp,D); }
2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。 解：
// 在A中删除既在B中出现又在C中出现的元素，并释放B、C Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C) { ListCross_L(B,C); ListMinus_L(A,B); }
// 求集合A-B，结果放在A表中，并删除B表 Status ListMinus_L(LinkList &A,LinkList &B) { LinkList pa,pb,qa,qb,pt; pa=A; pb=B; qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; while(pa&&pb){ if(pb->data
9
else{ 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.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。 解：
// 在单循环链表S中删除S的前驱结点 Status ListDelete_CL(LinkList &S) { LinkList p,q; if(S==S->next)return ERROR; q=S; p=S->next; while(p->next!=S){ q=p; p=p->next; } q->next=p->next; free(p); return OK; }
2.32 已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。 解：
// 建立一个空的循环链表
Status InitList_DL(DuLinkList &L) { L=(DuLinkList)malloc(sizeof(DuLNode)); if(!L) exit(OVERFLOW); L->pre=NULL; L->next=L; return OK; } // 向循环链表中插入一个结点
Status ListInsert_DL(DuLinkList &L,ElemType e) { DuLinkList p; p=(DuLinkList)malloc(sizeof(DuLNode)); if(!p) return ERROR; p->data=e; p->next=L->next; L->next=p; return OK; } // 将单循环链表改成双向链表 Status ListCirToDu(DuLinkList &L) { DuLinkList p,q; q=L; p=L->next; while(p!=L){ p->pre=q; q=p; p=p->next; } if(p==L) p->pre=q; return OK; }
2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 解：
// 将单链表L划分成3个单循环链表
Status ListDivideInto3CL(LinkList &L,LinkList &s1,LinkList &s2,LinkList &s3) { LinkList p,q,pt1,pt2,pt3; p=L->next; pt1=s1; pt2=s2;
10
pt3=s3; while(p){ if(p->data>='0' && p->data<='9'){ q=p; p=p->next; q->next=pt1->next; pt1->next=q; pt1=pt1->next; } else if((p->data>='A' && p->data<='Z') || (p->data>='a' && p->data<='z')){ q=p; p=p->next; q->next=pt2->next; pt2->next=q; pt2=pt2->next; } else{ q=p; p=p->next; q->next=pt3->next; pt3->next=q; pt3=pt3->next; } } q=L; free(q); return OK; }
在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为： typedef struct XorNode { char data; struct XorNode *LRPtr; } XorNode, *XorPointer; typede struct { //无头结点的异或指针双向链表 XorPointer Left, Right; //分别指向链表的左侧和右端 } XorLinkedList;
XorPointer XorP(XorPointer p, XorPointer q); // 指针异或函数XorP返回指针p和q的异或值
2.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) { XorPointer p,left,right; if(d=='l'||d=='L'){ p=L.Left; left=NULL; while(p!=NULL){ VisitingData(p->data); left=p; p=XorP(left,p->LRPtr); } } else if(d=='r'||d=='R'){ p=L.Right; right=NULL; while(p!=NULL){ VisitingData(p->data); right=p; p=XorP(p->LRPtr,right); } } else return ERROR; return OK; }
2.35 采用2.34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。 2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。 2.37 设以带头结点的双向循环链表表示的线性表
L??a1,a2,?,an?。试写一时间复杂度O(n)的算法，将L改造为
L??a1,a3,?,an,?,a4,a2?。
解：
// 将双向链表L=(a1,a2,...,an)改造为(a1,a3,...,an,...,a2) Status ListChange_DuL(DuLinkList &L) {
11
int i; DuLinkList p,q,r; p=L->next; r=L->pre; i=1; while(p!=r){ if(i%2==0){ q=p; p=p->next; // 删除结点 q->pre->next=q->next; q->next->pre=q->pre; // 插入到头结点的左面 q->pre=r->next->pre; r->next->pre=q; q->next=r->next; r->next=q; } else p=p->next; i++; } return OK; }
2.38 设有一个双向循环链表，每个结点中除有pre，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){ 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 last; } SqPoly;
2.39 已知稀疏多项式
Pn?x??c1xe1?c2xe2???cmxem，其中
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;
// 建立一个多项式
12