线性表作业参考答案.ppt

第二章线性表,作业参考答案,作业1.1用顺序表表示集合，设计一个算法实现集合的求差集运算，即C=A-B。,算法分析：C中元素为A中所有不属于B的元素。扫描A中元素，若它与B中所有元素均不相同，表示是差集元素，将其放到C中。typedefstructElemType*elem;/存储空间基址intlength;/当前长度intlistsize;/当前分配的存储容量SqList;,Voiddiffence(SqlistA,SqlistB,SqlistC)inti,j,k=0;for(i=0;iA.length;i+)j=0;while(jB.length,作业1.2试写一个算法，实现顺序表的就地逆置。,typedefstructElemType*elem;/存储空间基址intlength;/当前长度intlistsize;/当前分配的存储容量SqList;,算法：statusReverse(SqList/Reverse,作业2.1已知线性表中的数据元素以值递增有序排列，并以单链表作存储结构，试写一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删除的结点空间,typedefstructLnodeelemtypedata;/数据域structLnode*next;/指针域Lnode,*linklist;,StatusDELmink_maxk(LinkLlist/删除若干链结点后，重新建立链接/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)当mn线性表A、B和C均为单链表作存储结构，且C表利用A表和B表中的结点空间构表。注意：单链表的长度值m和n均未显式存储。,算法：statusCOMBINE(linklistA,linklistB,linklist/COMBINE,作业3.1假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。,算法思路：首先找到s所指链结点的直接前驱结点(即将被删除的链结点，算法中由q指出其地址)与直接前驱结点的直接前驱结点(算法中由r指出其地址)，然后做删除操作。,算法：StatusDelS(Linklist/DelS,