第二章线性表作业参考答案.ppt

《第二章线性表作业参考答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表作业参考答案作业1.1用顺序表表示集合，设计一个算法实现集合的求差集运算，即C=A-B。算法分析：C中元素为A中所有不属于B的元素。扫描A中元素，若它与B中所有元素均不相同，表示是差集元素，将其放到C中。typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;Voiddiffence(SqlistA,SqlistB,SqlistC){inti,j,k=0;for(i=0;i

2、&B.elem[j]!=A.elem[i])j++;if(j==B.length)//表示A.elem[i]不在B中，将其放到C中C.elem[k++]=A.elem[i];}C.length=k;}作业1.2试写一个算法，实现顺序表的就地逆置。typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;算法：statusReverse(SqList&L){//对顺序表实现就地逆序n=L.lengthfor(i=0;i

3、[i];L.elem[i]=L.elem[n-i-1]；L.elem[n-i-1]=temp;}returnOK;}//Reverse作业2.1已知线性表中的数据元素以值递增有序排列，并以单链表作存储结构，试写一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删除的结点空间typedefstructLnode{elemtypedata;//数据域structLnode*next;//指针域}Lnode,*linklist;StatusDELmink_maxk(LinkLlist&L,ElemTypemink,Elem

4、Typemaxk){p=L->next;q=L;//p指向当前链结点，q指向前一个链结点if(!p)returnERROR;//空链表while(p!=NULL&&p->datanext;}if(!p)retutnERROR;//找不到指定范围的数据elsewhile(p->data<=maxk&&p!=NULL){r=p;//删除链结点pp=p->next;free(r);}q->next=p;//删除若干链结点后，重新建立链接}//DELmink_maxk作业2.2设线性表A=(a1,a2,…,an)，B=(b1,b2,…,bm

5、)，试写一个按下列规则合并A、B为线性表C的算法，即使得C=(a1,b1,a2,b2,…,am,bm,bm+1,…,bn)当m<=n或C=(a1,b1,a2,b2,…,an,bn,an+1,…,am)当m>n线性表A、B和C均为单链表作存储结构，且C表利用A表和B表中的结点空间构表。注意：单链表的长度值m和n均未显式存储。算法：statusCOMBINE(linklistA,linklistB,linklist&C){C=A;a=A->next;b=B->next;If(a==NULL){A->next=B;ReturnOk;}do{p=a->next;q=b->

6、next;a->next=b;b->next=p;a=p;b=q;}while(p->next&&q);if(p->next==NULL)a->next=b;}//COMBINE作业3.1假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。算法思路：首先找到s所指链结点的直接前驱结点(即将被删除的链结点，算法中由q指出其地址)与直接前驱结点的直接前驱结点(算法中由r指出其地址)，然后做删除操作。算法：StatusDelS(Linklist&s){r=s;q=s->next/

7、/q指向s的下一个结点while(q->next!=s){r=q;q=q->next;}r->next=s;free(q);}//DelS