ds2.3.2陆小马功钟浩.ppt

§2.3 线性表的链式表示和实现 （二）其他链表结构 2.3 线性表的链式表示和实现 9.单循环链表 10.双向链表 11.双向循环链表 12.各种链表和顺序表的比较 13.静态链表 9.单循环链表 （1）(单)循环链表 （2）如何判断表尾？ 不能使用 p==NULL 进行判断 可以用 p==L（或p-next==L）来判断 9.单循环链表（2） 如何判断表尾？ 9.单循环链表（2） 结论：单循环链表与单链表操作不同之处仅在于判断表尾的方法不同，其他方法相同。 9.单循环链表（3） （3）设立尾指针的单循环链表 有时为了操作方便，在单循环链表中不设头指针，而设立尾指针指向最后一个元素。 9.单循环链表（3） 将表B中的元素插入表A末尾 9.单循环链表（3） 结论：设立尾指针后，访问两端元素（a1和an）方便了。O(1) 10.双向链表 在单链表中访问后继元素很方便，只要p-next即可（O(1)）；但访问前驱却很麻烦（O(n)）。 考虑改进结点结构，增加指向前驱元素的指针。 （1）双向链表的结点结构定义 10.双向链表（2） （2）双向链表 10.双向链表（3） （3）插入算法ListInsert(L, i, e) 先找到第i-1个结点，在其后插入元素e 10.双向链表（3） Status ListInsert ( DuLinkList L, int i, ElemType e ) { //查找第i-1个结点p p = L; j = 0; while ( p ji-1 ) { p = p-next; j++; } //若找到第i-1个结点p，则在其后插入元素e，否则返回错误 if ( p j==i-1 ) { //TODO: 在p之后插入元素e ……? return OK; } else return ERROR; } 10.双向链表（3） //在p之后插入元素e // 1) 建立结点s存储元素e s = malloc(sizeof(DuLNode)); if ( s==NULL ) exit(1); s-data = e; // 2) 将s插入p之后 s-next = p-next; s-prior = p; s-prior-next = s; if ( s-next ) //只有在下一个结点存在时才修改 s-next-prior = s; 10.双向链表（3） 总结： 时间复杂度O(n)。 注意修改两个方向的指针。 插入算法影响到ai-1的next指针。 若存在ai ，则影响其prior指针。 特别注意，ai未必存在，必须进行判断。 另外，还有其他多种写法 练习1 指针p指向ai，在ai之前插入结点s。 10.双向链表（4） （4）删除算法ListDelete(L,i,e) 找到第i个结点，从链表中删除，取出元素，释放结点。 10.双向链表（4） Status ListDelete ( DuLinkList L, int i, ElemType e ) { //查找第i个结点p p = L-next; j = 1; while ( p ji ) { p = p-next; j++; } //若找到第i个结点p，则删除之，否则返回错误 if ( p j==i ) { //删除结点p ? return OK; } else return ERROR; } 10.双向链表（4） //若找到第i个结点p，则删除之，否则返回错误 if ( p j==i ) { //删除结点p p-prior-next = p-next; if ( p-next ) p-next-prior = p-prior; e = p-data; //返回数据元素 free(p); //释放结点 return OK; } else return ERROR; 10.双向链表（4） 总结： 时间复杂度O(n)。 注意修改两个方向的指针。 删除算法影响到ai-1的next指针。 若存在ai+1 ，则影响其prior指针。 特别注意，ai+1未必存在，必须进行判断。 另外，还有其他多种写法 练习2 指针p指向ai+1，请删除ai。 11.双向循环链表 （1）在双向链表中，令最后一个结点next指向头结点，头结点prior指向最后一个结点，形成双向循环链表，其中包括两个环。 11.双向循环链表（2） （2）结点结构（同双向链表） 11.双向循环链表（3） （3）插入算法 11.双向循环链表（4） （4）删除算法 11.双向循环链表（5） （5）比较双向链表和双向循环链表 在