[计算机软件及应用]23490数据结构习题答案.docx

《[计算机软件及应用]23490数据结构习题答案.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表2．算法设计题(1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}elseif(pa->dat

2、a>pb->data){pc->next=pb;pc=pb;pb=pb->next;}else{//相等时取La的元素，删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb的头结点}(2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。voidunion(LinkList&La,LinkL

3、ist&Lb,LinkList&Lc,){pa=La->next;pb=Lb->next;//初始化Lc=pc=La;//用La的头结点作为Lc的头结点Lc->next=NULL;while(pa

4、

5、pb){if(!pa){q=pb;pb=pb->next;}elseif(!pb){q=pa;pa=pa->next;}elseif(pa->data<=pb->data){q=pa;pa=pa->next;}else{q=pb;pb=pb->next;}q->next=Lc->next;Lc->next=q;//插入}deleteLb

6、;//释放Lb的头结点}(3)已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出B的交集，并存放于A链表中。voidMix(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=la->next;pb=lb->next;〃设工作指针pa禾口pb;Lc=pc=La;II用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data==pb->data)//交集并入结果表中。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;dele

7、teu;}elseif(pa->datadata){u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;};}//释放结点空间;}//释放结点空间B表不作释放空间的处理while(pa){u=pa;pa=pa->next;deleteuwhile(pb){u=pb;pb=pb->next;deleteupc->next=nuII;〃置链表尾标记。deleteLb;//注：本算法中也可对(1)已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合

8、A和B的差集(即仅由在A中出现而不在B中出现的元素所构成的集合)，并以同样的形式存储，同时返回该集合的元素个数。voidDifference(LinkedListA，B，*n)//A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0{p=A->next;//p和q分别是链表A和B的工作指针。q=B->next;pre=A;//pre为A中p所指结点的前驱结点的指针。whiIe(p!=nuII&&q!=nuII)if(p->datadata){p

9、re=p；p=p->next；*n++；}/A链表中当前结点指针后移。elseif(p->data>q->data)q=q->next;//B链表中当前结点指针后移。else{pre->next=p->next;//处理A,B中元素值相同的结点，应删除。u=p；p=p->next；deIeteu；}/删除结点(2)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点(链表A的元素类型为整型，要求BC表利用A表的结点)。(6)设计一个算法,通过一趟

10、遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;//假定第一个结点中数据具有最大值p=L->next->next;whil