第2单元 线性表 (iii).pptVIP

Data Structure Chapter 2: Linear Table 第二章 线性表 《数据结构》 College of Science, Xidian University 第二章 线性表 (III) 西安电子科技大学·理学院 hjTang@xidian.edu.cn 课程内容 线性表的链式表示 单链表 循环链表 双循环链表 静态链表 线性链表的常用操作 插入 删除 与顺序表的比较 一元多项式 单链表 链式存储的概念 链式存储是指用一组任意的存储单元存储线性表的数据元素 这组存储单元专门利用一个或几个存储单元(称之为指针)来表示元素的前驱和后继的关系 一个数据＋指针＝结点(Node) N个结点通过指针(链)连接成一个链表，即线性表 单链表是指每个结点内只有一个指针的链表 指示链表第一个结点的指针称为头指针 线性链表的最后一个结点的指针赋值为“空”(NULL) 线性表的链式表示 链式表示的线性表的逻辑状态 空表、表长为1的链表的表示 无头结点的表示 有头结点的表示 线性表长度＝1的无头结点的表示 线性表长度＝1的有头结点的表示 为什么要多一个头结点 获得链表的元素 删除结点 插入结点 链表合并算法 循环链表 双向链表 单链表的缺点： 查找直接前驱慢 双向链表 双向循环链表 空表 L-next == L-prev; 双向链表的删除 双向链表的插入 错误方法的结果(1) 错误方法的结果(2) 静态链表 静态链表 静态链表 一元多项式的表示与运算 一元多项式的表示 链表表示 多项式的加法可能出现的情况 指数小于 指数大于 等于，但和不为0 等于，且和为0 完成后，Pb先到最后 完成后，Pa先到最后 * * Data Structure Chapter 2: Linear Table 43 ZHOU 25 37 ZHENG 19 31 ZHAO 7 25 WU 37 19 WANG null 13 SUN 1 7 QIAN 13 1 LI 43 存储地址 数据域 指针域 31 头指针 Li Qian Sun Wang Wu Zhao Zheng Zhou ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ Head typedef struct _NODE { ElemType data; struct _NODE *next; } LNode, *LList; // typedef LNode *LList; data next Head NULL ^ Head ^ Head ^ Head ZHAO ^ Head ZHAO typedef struct _NODE { ElemType data; struct _NODE *next; } LNode, *LList; // typedef LNode *LList; void ClearList(LList L1) { // 释放所有空间的内容 L1 = NULL; } int main() { ...... ClearList(L); if (L == NULL) // 如果表已经为空 ...... } 判断失败 L != NULL L1 L ZHAO ^ ^ ? ^ L ZHAO L1 ^ OK Status GetElem_L(LList L, int i, ElemType *e) { LList p = L-next; while (p != NULL i-- 0) p = p-next; if (p == NULL) return ERROR; *e = p-data; return OK; } 0 1 2 3 4 5 ^ i=4 i=3 i=2 i=1 i=0 L 0 1 2 3 4 5 ^ L Status DeleteElem_L(LList L, int i, ElemType *e) { LList p=L, q = L-next; while (q != NULL i-- 0) // 找到第i个结点 {p = q; q = q-next;} // q总是p的直接前驱 if (q == NULL) return ERROR; *e = p-data; p-next = q-next; free(q); return OK; } p q 3 Status DeleteElem_L(LList L, int i, ElemType e) { LList p=L, q;