数据结构(c语言版 严蔚敏)习题集答案第2章 线性表 1

StatusOrderListInsert-sq(SqListva,ElemTypex){〃将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1)pe));if(Inewbase)exit(OVERFLOW);}〃当前存储空间已满，增加分配空间for*q=x;returnOK;}//OrderListlnsert-sqStatusOrderListlnsert-sq(SqListva,ElemTypex){〃将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2)newbase=(ElemType*)if(!newbase)exit(OVERFLOW);}〃当前存储空间已满，增加分配空间*(p+l)=X；returnOK;}//OrderListlnsert-sq④)和B=(b„...,bn)均为顺序表，A，和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'二空表，而B'W空表，或者两者均不为空表，且A'的首元小于B'的首元，则否则A>B。试写一个比较A,B大小的算法。intCompare-List(SqLista,SqListb){〃冉b为顺序表，若水b时，返回T；a二b时，返回0；a>b时，返回1i=0;switch{,length-1)default:return1;)}//Compare-Liststatusdel-l(LinkList&la,intmink,intmaxk){/伯为带头结点的单链表的头指针，单链表中的结点以值递增有序排列〃本算法删除表中所有值大于mink且小于maxk的元素，mink<maxkif(mink>=maxk)returnERRORp=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;A->next=s;}//LinkList_reverse分析:本算法的思想是，逐个地把L的当前元素q插入新的链表头部,p为新表表头.voidmerge1(LinkList&A,LinkList&B,LinkList&C)〃把链表A和B合并为C,A和B的元素间隔排列，且使用原存储空间(p=A->next;q=B->next;C=A;while(p&&q){s=p->next;p->next=q;〃将B的元素插入if⑸(t=q->next;q->next=s;//$□A非空，将A的元素插入)P=s；q=t;}//while}//merge1voidreverse_merge(LinkList&A,LinkList&B,LinkList&C)〃把元素递增排列的链表A和B合并为C,且C中元素递减排列，使用原空间(pa=A->next;pb=B->next;pre=NULL;//pa和pb分别指向A,B的当前元素while(pa&&pb)(if(pa->data<pb->data)(pc=pa;q=pa->next;pa->next=pre;pa=q;//^A的元素插入新表elsepc=pb;q=pb->next;pb->next=pre;pb=q;//^B的元素插入新表)pre=pc;)while(pa)(q=pa->next;pa->next=pc;pc=pa;pa=q;//^AA中余下的元素)while(pb)(q=pb->next;pb->next=pc;pc=pb;pb=q;//插入B中余下的元素)C=A;A->next=pc;〃构造新表头}//reverse_merge分析:本算法的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余元素.voidSqList_lntersect(SqListA,SqListB,SqList&C)〃求元素递增排列的线性表A和B的元素的交集并存入C中(i=1;j=1;k=O;i++;j++;〃就添加到C中)}//while}//SqList_lntersectvoidLinkList_lntersect(LinkListA,LinkListB,LinkList&C)〃在链表结构上重做上题(p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode));while(p&&q)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;else(s=(LNode*)malloc(sizeof(LNode));s->data=p->data;pc->next=s;pc=s;p=p->next;q=q->next;)}//whileC=pc;}//LinkList_lntersectvoidSqList_lntersect_True(SqList&A,SqListB)〃求元素递增排列的线性表A和B的元素的交集并存回A中(i=1;j=1;k=O;i++;j++;〃且C中没有，就添加到C中)}//while}//SqList_lntersect_TruevoidLinkList_lntersect_True(LinkList&A,LinkListB)〃在链表结构上重做上题(p=A->next;q=B->next;pc=A;while(p&&q)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;elseif(p->data!=pc->data)(pc=pc->next;pc->data=p->data;p=p->next;q=q->next;)}//while}//LinkList_lntersect_TruevoidSqList_lntersect_delete(SqList&A,SqListB,SqListC)〃从有序顺序表A中删除那些在B和C中都出现的元素else〃找到了需要从A中删除的元素}//else}//while)j++;}//for}//SqList_lntersect_delete分析:本算法的时间复杂度为O(m),m为表长.思考:你自己的算法时间复杂度是多少？实际上也可以只用一遍扫描就完成整个操作，且时间复杂度也为0(m),但非常复杂，你能写出来吗？voidLinkList_lntersect_delete(LinkList&A,LinkListB,LinkListC)〃在链表结构上重做上题(p=B->next;q=C->next;r=A-next;while(p&&q&&r)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;else(u=p->data;〃确定待删除元素uwhile(r->next・>datav(j)r=r・>next;〃确定最后一个小于u的元素指针rif(r->next->data==u)(s=r->next;while(s->data==u)仁s;s=s->next;free(t);〃确定第一个大于u的元素指针s}//whiler->next=s;〃册i］除r和s之间的元素}//ifwhile(p->data=u)p=p->next;while(q->data=u)q=q->next;}//else}//while}//LinkList_lntersect_deleteStatusDelete_Pre(CiLNode*s)〃删除单循环链表中结点s的直接前驱(P=S；while(p->next->next!=s)p=p->next;〃找至！］s的前驱的前驱pp->next=s;returnOK;}//Delete_preStatusDuLNode_pre(DuLinkList&L)〃完成双向循环链表结点的pre域(for(p=L;!p->next->pre;p=p->next)p->next->pre=p;returnOK;}//DuLNode_pre(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;)elseif(isdigit(s->data))q->next=s;q=s;)else(r->next=s;r=s;)}//whilep->next=A;q->next=B;r->next=C;//完成循环链表}//LinkList_dividevoidPrint_XorLinkedList(XorLinkedListL)〃从左向右输出异或链表的元素值(while(p){printf("％d”,p->data);q=XorP(p->LRPtr,pre);pre二p;p=q;〃任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针)}//Print_XorLinkedListStatuslnsert_XorLinkedList(XorLinkedList&L,intx,inti)〃在异或链表L的第i个元素前插入元素x(r=(XorNode*)malloc(sizeof(XorNode));r->data=x;if(i==1)〃当插入点在最左边的情况(r->LRPtr=p;returnOK;)j=1;q=p->LRPtr;〃当插入点在中间的情况while(++j<i&&q)q=XorP(p->LRPtr,pre);pre=p;p=q;}//while〃在p,q两结点之间插入if(!q)returnINFEASIBLE;//i不可以超过表长p->LRPtr=XorP(XorP(p->LRPtr,q),r);q->LRPtr=XorP(XorP(q->LRPtr,p),r);r->LRPtr=XorP(p,q);〃修改指针returnOK;}//lnsert_XorLinkedListStatusDelete_XorLinkedList(XorlinkedList&L,inti)〃删除异或链表L的第i个元素(if(i==1)//删除最左结点的情况(q=p->LRPtr;q->LRPtr=XorP(q->LRPtr,p);returnOK;)j=1;q=p->LRPtr;while(++j<i&&q)(q=XorP(p->LRPtr,pre);pre=p;p=q;}//while//找到待删结点qif(!q)returnINFEASIBLE;//i不可以超过表长p->LRPtr=XorP(p->LRPtr,q);returnOK;)r=XorP(q->LRPtr,p);//q为中间结点的情况，此时p,r分别为其左右结点p->LRPtr=XorP(XorP(p->LRPtr,q),r);r->LRPtr=XorP(XorP(r・>LRPtr,q),p);〃修改指针free(q);returnOK;}//Delete_XorLinkedListwhile(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;elsep->next=l->pre;p=p->next;〃此时p指向最后一个偶数结点while(p->pre->pre!=L)(p->next=p->pre->pre;p=p->next;)p->next=L;//按题目要求调整了next链的结构，此时pre链仍为原状for(p=L;p->next!=L;p=p->next)p->next->pre=p;}//reform分析:next链和pre链的调整只能分开进行.如同时进行调整的话，必须使用堆栈保存偶数结点的指针，否则将会破坏链表结构，造成结点丢失.DuLNode*LOCATE(DuLinkedList&L,intx)〃带freq域的双向循环链表上的查找if(p==L)returnNULL;//没找到p->freq++;q=p->pre;while(q->freq<=p->freq)q=q->pre;〃查找插入位置if(q!=p->pre)(p->pre->next=p->next;p->next->pre=p->pre;q->next->pre=p;p->next=q->next;q->next=p;p->pre=q;〃调整位置)returnp;}//LOCATEfloatGetValue_SqPoly(SqPolyP,intx0)〃求升幕顺序存储的稀疏多项式的值(PolyTerm*q;sum=0;ex=0;while(q->coef)(while(ex<q->exp)xp*=xO;sum+=q->coef*xp;q++；}returnsum;}//GetValue_SqPolyvoidSubtract_SqPoly(SqPolyP1,SqPolyP2,SqPoly&P3)〃求稀疏多项式P1减P2的差式P3(PolyTerm*p,*q,*r;Create_SqPoly(P3);〃建立空多项式P3p=la;while(p->next<>NULL&&p->next->data<=mink)p=p->next;q=p；while(q->next<>NULL&&q->next->data<maxk)q=q->next;q=q->next;p1=p->next;while(p1<>q){q1=p1;p1=p1->next;free(q1);}p->next=q;}//del-lLinkListpriou(LinkListla,LinkListq1){〃返回指向单链表la中结点的指针p1,p1->next=q1p1=la;while(p1->next!=q1)p1=p1->next;returnp1;}//priouvoidReverse-List-l(LinkList&la){〃就地逆置单链表la(算法1)if(!la->next)return;p=la->next;q=priou(la,NULL);while(p!=q){p->data<->q->data;if(p=q)return;q=priou(la,q);while(p->coef&&q->coef)if(p->exp<q->exp)(r->coef=p->coef;r->exp=p->exp;p++；r++;)elseif(p->exp<q->exp){r->coef=-q->coef;r->exp=q->exp;q++;r++;)else(if((p->coef-q->coef)!=0)〃只有同次项相减不为零时才需要存入P3中(r->coef=p->coef-q->coef;r->exp=p->exp;r++;}//ifp++；q++；}//else}//whilewhile(p->coef)//处理P1或P2的剩余项(r->coef=p->coef;r->exp=p->exp;p++；r++;)while(q->coef)r->coef="q->coef;r->exp=q->exp;q++；r++;)}//Subtract_SqPolyvoidQiuDao_LinkedPoly(LinkedPoly&L)〃对有头结点循环链表结构存储的稀疏多项式L求导(p=L->next;L->nex仁p->next;p=p->next;//跳过常数项)while(p!=L)p=p->next;)}//QiuDao_LinkedPolyvoidDivide_LinkedPoly(LinkedPoly&L,&A,&B)〃把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B(p=L->next;A=(PolyNode*)malloc(sizeof(PolyNode));B=(PolyNode*)malloc(sizeof(PolyNode));pa=A;pb=B;while(p!=L)pa->next=p;pa=p;)elsepb->next=p;pb=p;)p=p->next;}//whilepa->next=A;pb->next=B;}//Divide_LinkedPoly}//Reverse-List-lvoidReverse-List-l(LinkList&la){〃就地逆置单链表la(算法2)p=priou(la,NULL);last=p;pre=priou(la,p);while(pre!=la){p->next=pre;p=pre;pre=priou(la,p);)p->next=NULL;la->next=last;}//Reverse-List-lvoidReverse-List-l(LinkList&la){〃就地逆置单链表la(算法3)if(!la->next)return;〃空表pre=la->next;〃前if(!pre->next)return;p=pre->next;〃中pre->next=NULL;//原来的第一项将被作为最后一项；next=p->next;〃后while(p){〃当p不指向空地址时；p->next=pre;〃最终使每一个后项的地址域都指向前一项，实现逆置；pre=p;//后移p=next;〃后移if(p)next=p->next;〃当p不指向空地址，即原来的next没有被指向空；la->next=pre;//将头指针指向现在的第一项；return;}//Reverse-List-lvoidReverse-List-l(LinkList&la){〃就地逆置单链表la(算法4)p=la->next;if(!p||!p->next)return;〃空表或只有一项；pn=p->next;p->next=NULL;while(pn){p=pn;pn=pn->next;//后移;p->next=la->next;〃后一项的地址域指向前一项；la->next=p;〃头指针指向后一项；)return;}//Reverse-List-lvoidMergeList(LinkList&a,LinkList&b,LinkList&c){〃已知单链表a和b的元素按值递增有序排列//归并a和b得到新的单链表c,c的元素按值递减有序c=a;p=a->next;q=b->next;c->next=NULL;while(p&&q)if(p->data<q->data){pn=p->next;p->next=c->next;c->next=p;p=pn;else{qn=q->next;q->next=c->next;c->next=q;q=qn;)while(p){pn=p->next;p->next=c->next;c->next=p;p=pn;}while(q){qn=q->next;q->next=c->next;c->next=q;q=qn;}free(b);}//MergeListvoidCutApart-LinkList(LinkList&l,LinkListla,LinkListlb,LinkListlc){〃单链表I中的元素含有三类字符：字母、数字和其它字符〃本算法将|分割为la.lb和1c三个循环链表，它们分别只含字母、数字和其它字符la=(LinkList)malloc(sizeof(LNode));la->next=la;lb=(LinkList)malloc(sizeof(LNode));lb->next=lb;lc=(LinkList)malloc(sizeof(LNode));lc->next=lc;pn=l->next;while(pn){p=pn;pn=pn->next;switch{case('a'<=p->data&&p->data<=*z')||('A,<=p->data&&p->data<='Z'):p->next=la->next;la->next=p;break;case(,0,<=p->data&&p->data<=*9'):p->next=lb->next;lb->next=p;break;default:p->next=lc->next;lc->next=p;}//switch}//whilefree(l);}//CutApart-LinkListtypedefstruct{floatcoef;intexpn;}*Poly,ElemType;floatPolynomial(Poly&p,intm,floatx0){//多项式p的顺序存储结构中依次存放有ci,ei,C2,e2,...,cm,em〃X0为给定值,本算法计算Pn(X0)的值x=xOAp[O].expn;pn=p[0].coef*x;for(i=1;i<=m;++i){x=x*xOA(p[i].expn-p[i-1].expn);pn=pn+p[i].coef*x;)retrunpn;}//Polynomial(以下内容来自)第二章线性表StatusDeleteK(SqList&a,inti,intk)〃删除线性表a中第i个元素起的k个元素returnOK;}//DeleteKStatuslnsert_SqList(SqList&va,intx)〃把x插入递增有序表va中returnOK;}//lnsert_SqListintListComp(SqListA,SqListB)〃比较字符表A和B,并用返回值表示结果，值为正，表示A>B;值为负，表示A〈B;值为零，表示A=Breturn0;}//ListCompLNode*Locate(LinkListL,intx)〃链表上的元素查找，返回指针(for(p=l->next;p&&p->data!=x;p=p->next);returnp;}//LocateintLength(LinkListL)〃求链表的长度(for(k=0,p=L;p->next;p=p->next,k++);returnk;}//LengthvoidListConcat(LinkListha,LinkList