LinkList p,q; if(i==0) { } else if(i==1)
{ p=L;L=L->next;free(p);} else {
int j=1; p=L;
while(p->next!=NULL&&j p=p->next; j++; } q=p->next; p->next=q->next; free(q); } } 2.20② 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素 (使得操作后的线性表中所有元素的值均不相同) 同时释放被删结点空间，并分析你的算法的时间复杂度。 void Purge(LinkList &L) { LinkList p,q; p=L->next; q=p->next; while(q) { if(p->data==q->data) { q=q->next; p->next=q; } q=q->next; p=p->next; } } ◆2.21③ 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。 void Inverse(SqList &L) { int temp; int i,j; for(i=0,j=L.length-1;i<=j;i++,j--) { temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; } } ◆ 2.22③ 试写一算法，对单链表实现就地置。 void Inverse(LinkList &L) /* 对带头结点的单链表L实现就地逆置 */ { LinkList p,q,r; p=L->next;q=NULL; while(p) { r=q; q=p;p=p->next; q->next=r; } L->next=q; } 2.23③ 设线性表A=(a1,...,am), B=(b1,...,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均未显式存储。 void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ { LinkList pa,pb,pc; pa=ha->next;pb=hb->next;pc=hc=ha; while(pa&&pb) { pc->next=pa;pc=pa;pa=pa->next; pc->next=pb;pc=pb;pb=pb->next; } while(pa) { pc->next=pa; pc=pa; pa=pa->next; } while(pb) { pc->next=pb; pc=pb; pb=pb->next; } } ◆2.24④ 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C， 并要求利用原表（即A表和B表）的结点空间构造C表。 void Union(LinkList &lc, LinkList &la, LinkList &lb) { LinkList p,q,s,t; lc=la; p=la->next; q=lb->next; lc->next=NULL; while (p && q) if (p->data { s=p->next; p->next=lc->next; lc->next=p; p=s; } else { t=q->next; q->next=lc->next; lc->next=q; q=t; } while (p) {s=p->next; p->next=lc->next; lc->next=p; p=s;} while (q) {t=q->next; q->next=lc->next; lc->next=q; q=t;} free(lb); } 2.31② 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。 ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ { LinkList p,q; nt i; p=s; while(p->next->next!=s) p=p->next; q=p->next; i=q->data; p->next=q->next; free(q); return i; } 2.32② 已知有一个单向循环链表，其每个结点中 含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。 void PerfectBiLink(BiLinkList &CL) { BiLinkList p; for(p=CL;!p->next->prev;p=p->next) p->next->prev=p; } ◆2.33③ 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) { LinkList p,q,r,s; p=lc;q=lo; r=ld,s=ll->next; while(s) { if(s->data>='0'&&s->data<='9') { r->next=s; r=r->next; } else if(s->data>='A'&&s->data<='Z'||s->data>='a'&&s->data<='z') { p->next=s; p=p->next; } else { q->next=s; q=q->next; } s=s->next; } p->next=NULL; q->next=NULL; r->next=NULL; } 2.37④ 设以带头结点的双向循环链表表示的线性表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。 void ReverseEven(BiLinkList &L) { BiLinkList p; p=L->next; if(p->next==L){} else { while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; } if(p->next==L) p->next=L->prev->prev; else p->next=L->prev; p=p->next; while(p->prev->prev!=L) { p->next=p->prev->prev; p=p->next; } p->next=L; for(p=L;p->next!=L;p=p->next) p->next->prev=p; L->prev=p; } } ◆2.39③ 试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。 float f(float x,int j) { int i; float s = 1; for( i = 0 ; i < j; ++i ){ s *= x; } return s; } float Evaluate(SqPoly pn, float x) /* pn.data[i].coef 存放ai， */ /* pn.data[i].exp存放ei (i=1,2,...,m) */ /* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0≤e1 float s = 0; for( i = 0; i < pn.length; ++i ){ s += pn.data[i].coef * f( x, pn.data[i].exp ); } return s; } ◆2.41② 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。 void Difference(LinkedPoly &pa)/* 稀疏多项式 pa 以循环链表作存储结构， */ /* 将此链表修改成它的导函数，并释放无用结点 */ { LinkedPoly p; p=pa->next; if(!p->exp) { pa->next=p->next; p=p->next; } while(p!=pa) { p->coef=p->coef*p->exp ; p->exp--; p=p->next; } } 第三章 ◆3.17③ 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而'1+3&3-1'则不是。