习题课2012-12-27 居振飞.ppt

* * * * * 第一反应就是蛮力法：在第一链表上顺序遍历每个结点。每遍历一个结点的时候，在第二个链表上顺序遍历每个结点。如果此时两个链表上的结点是一样的，说明此时两个链表重合，于是找到了它们的公共结点。如果第一个链表的长度为m，第二个链表的长度为n，显然，该方法的时间复杂度为O(mn)。 * * * * * * * * Institute of Computer Software Nanjing University Institute of Computer Software Nanjing University * * 习题课 * * 拓展 双向链表 循环链表 * * 单链表 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; * * 单链表 * * 循环链表 首节点和末节点被连接在一起 * * 循环链表 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或者p-next是否为空，而是他们是否等于头指针。 head==head-next; * * 双向链表 typedef struct DuLNode { ElemType data; struct DuLNode *next; struct DuLNode *prior }DuLNode, *DuLinkList; * * 双向链表 * * 双向链表操作 删除 * * 双向链表操作 删除 void?DDeleteNode(DListNode?*p)?? ????{//在带头结点的双链表中，删除结点*p，设*p为非终端结点?? ????????p-prior-next=p-next;//①?? ????????p-next-prior=p-prior;//②?? ????????free(p);//③?? ????}??? a 删除 b c (1) p-left-right = p-right; (2) p-right-left = p-left; p * * 双向链表操作 插入 * * 双向链表操作 插入 void?DInsertBefore(DListNode?*p,DataType?x)?? ???{ //在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL?? ?????DListNode?*s=malloc(sizeof(DListNode));//①?? ?????s-data=x;//②?? ?????s-prior=p-prior;//③?? ?????s-next=p;//④?? ?????p-prior-next=s;//⑤?? ?????p-prior=s;//⑥?? ????}?? a c b (1) q-right = p-right; (3) q-left = p; (2) q-right-left = q; (4)p-right = q; p q a c 插入 双向链表 * * 链表应用 例1.已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按非递减有序排列。 思路： LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，再将LA或LB中的元素逐个插入到LC中即可。 * * 链表应用 例1.已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按非递减有序排列。 思路：需设立三个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若 pa-data≤pb—data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。 显然，指针的初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。 * * 链表应用 void MergeList_L (LinkList La， LinkList Lb，LinkList Lc) {//已知单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc，Lc元素也按值非递减排列。????pa = La—next； pb =Lb—next； Lc = pc = La； //用La的头结点作为Lc的头结点????while (pa pb) {???