数据结构精品课程课件_第二章.ppt

循环链表中尾指针的应用 考虑如何实现将带有尾指针的两个循环论链表合并为一个？ an A a2 a1 an a2 a1 B 带尾指针的循环链表 rear 31 48 15 57 22 如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。 在表尾插入，时间复杂性 O(1) 在表尾删除，时间复杂性 O(n) 在表头插入，相当于在表尾插入 在表头删除，时间复杂性 O(1) 2.3.3双向链表 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点有两个指针域, 结构如下： 双向链表通常采用带头结点的循环链表形式。 前驱方向 ? ? 后继方向 prior data next 双向链表的C语言定义 typedef struct DuLNode { ElemType data; struct DuLNode *prior,*next; } DuLNode ,*DuLinkList; prior data next 空双向循环链表： 非空双向循环链表： L L A B p-prior-next == p == p-next-prior p-prior p-next p prior next 结点指向 双向链表中插入操作 s=(DuLNode *)malloc(sizeof(DuLNode )); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; x S b a P 双向链表的插入操作算法: Status ListInsert_DuL ( DuLinkList L, int i, ElemType e ) { if ( ! ( s = ( DuLinkList ) malloc ( sizeof ( DuLNode ) ) ) ) return ERROR s-data = e; // 将数据放入新结点的数据域 s-prior = p-prior; // 将 p 的前驱结点指针放入新结点的前向指针域 s-next = p; // 将 p 的放入新结点的反向指针域 p-prior-next = s; // 修改 p 的前驱结点的反向指针 p-prior = s; // 修改 p 的前向指针 return OK; } // ListInsert_DuL 算法评价：T(n)=O(n) 删除操作 b c a P p-prior-next=p-next; p-next-prior=p-prior; 双向链表的删除操作算法: Status ListDelete_DuL ( DuLinkList L, int i, ElemType e ) { // 删除带头结点的双向循环链表 L 中第 i 个元素并将元素值返回，1≤i≤表长 if ( ! ( p = GetElemP_DuL ( L, i ) ) ) return ERROR; // 在 L 中确定第 i 个元素，p 为指向该结点的指针； // 若 i 1 或 i 表长，则 p 为 NULL，第 i 个元素不存在 e = p-data; // 将 p 指向的结点数据域中的值取出 p-prior-next = p-next; // 修改 p 的前驱结点的反向指针 p-next-prior = p-prior; // 修改 p 的后继结点的前向指针 free (p); // 释放 p 结点 return OK; } // ListDelete_DuL 算法评价：T(n)=O(n) 顺序表与链表的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 若插入/删除仅发生在表的两端，宜采用带尾指针的循环链表 考虑如何选择合适的存储结构？ 静态链表 定义：用数组描述的链表叫静态链表 存储结构： #define MAXSIZE = 100; //静态链表的最大长度 typedef struct { ElemType data; int cur; //游标,代替指针指示结点在数组中的位置 } component,SLinkList[MAXSIZE]; 目的是为了在不设指针类型的高级程序设计语言中使用链表结构 1 zhao 2 qian 3 sun 4 li zhou 6 wu 7 zheng 8 wang 0 0 1 2 3 4 5 6 7 8 9 10 1 z