数据结构课程讲稿第2章.pptVIP

2.3.2 循环链表（circular linked list） 在具体操作上： 在链表上进行遍历时，循环条件不是p或p?next是否为空， 而是它们是否等于遍历起点的指针！ 2.3.3 双向链表 单向链表的优点是： 插入和删除不需要移动其它元素 缺点： 失去随机访问的特点—链表的普遍缺点 访问当前结点下一个位置的复杂度为O(1) 但是访问当前结点前一个位置的复杂度为O(n) 如何克服这样的缺点？ 2.3.3 双向链表 2.3.3 双向链表（double linked list） 图2.13 双链表的结点结构 2.3.3 双向链表 存储结构设计： typedef struct DuLNode{ ElemType data; struct DuLNode * prior; struct DuLNode * next; } DuLNode, *DuLinkList; 2.3.3 双向链表 在结构上： 可以有双向的循环链表。 图2.14 双向循环链表图示 2.3.3 双向链表 对于一般的双向链表，其结构上的特点，决定了如下关系： p?prior?next = p = p?next?prior 2.3.3 双向链表 在操作上： 和单链表类似，插入和删除结点，需要修改指针来表示逻辑关系的变化； 但是修改的数量增加。 和单链表类似，在修改指针时，要保证指针不丢失。 对于其它的线性操作，例如：ListLength、GetElem和LocateElem等仅涉及一个方向的指针，其算法描述与单链表相同。 1）双向表的插入操作 指针更改顺序由工作指针位置决定！ 图2.15 双向链表插入操作 Status ListInsert_DuL(DuLinkList L, int i, ElemType e){ if(!(p = GetElemP_Dul(L, i))) return ERROR; if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR ; s?data = e; s?prior = p?prior; p?prior?next = s; s?next = p; p?prior = s; return OK; }//ListInsert_DuL 2）双向链表的删除操作 图2.16 双向链表的删除操作 Status ListDelete_DuL(DuLinkList L, int i, ElemType e){ if(!(p = GetElemP_Dul(L, i))) return ERROR; e = p?data; p?prior?next = p ? next; p?next?prior = p ? prior; free(p); return OK; }//ListDelete_DuL 链表总结 优点： 1. 空间的合理利用 2. 插入、删除时不需要移动元素 缺点： 实现某些操作代价大，例如：求线性表长度。 2.4 一元多项式的表示和相加 大家自学教材中2.4节中的内容 从以下几个方面考虑： 1. 如何把多项式用线性表抽象出来 2. 如何进行顺序表示和链接表示 3. 在两种表示上，如何实现相加操作 例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第5个元素，如图2.4所示。 删除算法的实现如下所示： 图2.4 顺序表中删除元素 Status ListDelete_Sq(SqList L, int i, ElemType e){ if(i 1 || i L.length + 1) return ERROR; p = (L.elem[i-1]); //p为被删除元素的位置指针 e = *p //获取被删除数据 q = L.elem + L.length -1 //表尾元素位置 for(++p; p = q; ++p) *(p - 1) = *p; //前移被删除元素后面的数据 --L.length return OK }//ListDelete_Sq 4）插入和删除操作的算法复杂度分析 在时间上，两种操作算法的实现主要耗费在移动元素上； 而移动元素的个数取决于插入或删除元素的位置！ 这意味着：很难用确定的量来衡量移动个数—即问题的实际规模！ 如何计算其时间复杂度？ 假设pi是在第i个元素之前插入一个元素的概率 在第i个元素之前插入一个元素，需要移动多少个元素？ n –( i - 1) 则移动元素个数的期望是： 同理，假设是删除第i个元素的概率，则删除一个元素需要移动的元素个数的期望值为： 这两个结果说明： 在顺序结构的线性表中，插入或删除一个数据元素，平均移动