线性表作业参考答案

《线性表作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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、gth;i++){j=0;while(j

3、List&L){//对顺序表实现就地逆序n=L.lengthfor(i=0;i

4、数据域structLnode*next;//指针域}Lnode,*linklist;StatusDELmink_maxk(LinkLlist&L,ElemTypemink,ElemTypemaxk){p=L->next;q=L;//p指向当前链结点，q指向前一个链结点if(!p)returnERROR;//空链表while(p!=NULL&&p->datanext;}if(!p)retutnERROR;//找不到指定范围的数据elsewhile(p->data<=maxk&

5、&p!=NULL){r=p;//删除链结点pp=p->next;free(r);}q->next=p;//删除若干链结点后，重新建立链接}//DELmink_maxk作业2.2设线性表A=(a1,a2,…,an)，B=(b1,b2,…,bm)，试写一个按下列规则合并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表中的

6、结点空间构表。注意：单链表的长度值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->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假设某个单向循环链表的

7、长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。算法思路：首先找到s所指链结点的直接前驱结点(即将被删除的链结点，算法中由q指出其地址)与直接前驱结点的直接前驱结点(算法中由r指出其地址)，然后做删除操作。算法：StatusDelS(Linklist&s){r=s;q=s->next//q指向s的下一个结点while(q->next!=s){r=q;q=q->next;}r->next=s;free(q);}//DelS