第二章线性表作业答案公开课一等奖课件省课获奖课件

第二章线性表作业参照答案第1页作业1.1用次序表表达集合，设计一种算法实现集合求差集运算，即C=A-B。算法分析：C中元素为A中所有不属于B元素。扫描A中元素，若它与B中所有元素均不相同，表达是差集元素，将其放到C中。typedefstruct

{ElemType*elem;//存放空间基址intlength;//目前长度intlistsize;//目前分派存放容量}SqList;第2页Voiddiffence(SqlistA,SqlistB,SqlistC){inti,j,k=0;for(i=0;i<A.length;i++){j=0;while(j<B.length&&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;}第3页作业1.2试写一种算法，实现次序表就地逆置。typedefstruct

{ElemType*elem;//存放空间基址intlength;//目前长度intlistsize;//目前分派存放容量}SqList;第4页算法：statusReverse(SqList&L){//对次序表实现就地逆序n=L.lengthfor(i=0;i<n/2;i++){temp=L.elem[i];L.elem[i]=L.elem[n-i-1]；L.elem[n-i-1]=temp;}returnOK;}//Reverse第5页作业2.1已知线性表中数据元素以值递增有序排列，并以单链表作存放构造，试写一种高效算法，删除表中所有值大于mink且不大于maxk元素（若表中存在这样元素），同步释放被删除结点空间typedefstructLnode {elemtypedata;//数据域 structLnode*next;//指针域 }Lnode,*linklist;第6页StatusDELmink_maxk(LinkLlist&L,ElemTypemink,ElemTypemaxk){p=L->next;q=L;//p指向目前链结点，q指向前一种链结点if(!p)returnERROR;//空链表while(p!=NULL&&p->data<mink){q=p;p=p->next;}if(!p)retutnERROR;//找不到指定范围数据elsewhile(p->data<=maxk&&p!=NULL){r=p;//删除链结点pp=p->next;free(r);}q->next=p;//删除若干链结点后，重新建立链接}//DELmink_maxk第7页作业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表中结点空间构表。注意：单链表长度值m和n均未显式存放。第8页算法：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第9页作业3.1假设某个单向循环链表长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点前驱结点。算法思绪：首先找到s所指链结点直接前驱结点(即将被删除链结点，算法中由q指出其地址)与直接前驱结点直接前驱结点(算法中由r指出其地址)，然后做删除操作。第10页算法：StatusDelS(Linklist&s){r=s;q=s->n