part2线性表.pptVIP

线性表 线性表的特征 同一线性表中的元素具有相同特性(类型) 相邻元素间存在序偶关系 具有n个元素的有限序列(a1,…ai-1, ai, ai+1, …, an) 前驱元素/后继元素 线性表的长度：n 位序：i为元素ai在线性表中的位序 线性表的ADT定义 线性表的表示和实现 线性表的顺序表示和实现 线性表的链式表示和实现 线性表的顺序表示和实现 概念 也称顺序表 用一组地址连续的存储单元依次存储各元素 高级语言中常用静态数组来描述顺序表，但如果线性表大小未定，则可使用语言中提供的动态分配空间机制(如C的malloc,free)来定义 特点 逻辑关系上相邻的两个元素在物理位置上也相邻 各元素的存储位置容易计算，易于各元素的随机存取 即 Loc(ai) = Loc(a1) + (i-1)*L // L为各元素的存储单元大小 或 Loc(ai+1) = Loc(ai) + L 顺序表在更新(如插入、删除)时存在大量的元素移动 表的容量难以扩充 存储空间不能有效充分使用 线性表的顺序表示和实现 线性表的顺序表示和实现 线性表的顺序表示和实现 线性表的顺序表示和实现 线性表的链式表示和实现 概念 线性表的链式实现又称为“链表” 元素间的逻辑关系由结点中的指针来指示，“位序”概念淡化，由“位置”概念代替 逻辑上相邻的元素在物理位置上不要求相邻 元素不能随机存取，必须从链表表头开始 分类 单链表/线性链表 双向链表 循环链表 单链表 单链表/线性链表 单链表 单链表的基本操作，如： status MakeNode(LinkList L, ElemType e); void FreeNode(LinkList L); status InitList(LinkList L); status CreateList(LinkList L, int n); status DestoryList(LinkList L); status ClearList(LinkList L); status GetElem(LinkList L, int i, ElemType e); status InsertFirst(LinkList L, LinkList p); status ListInsert(LinkList L, int i, ElemType e) status DeleteFirst(LinkList L, LinkList p); status ListDelete(LinkList L, int i, ElemType e); status Append(LinkList L, LinkList p); … … 单链表的操作 头插法创建由n个数据元素组成的单链表 单链表的操作 取单链表第i个数据元素 单链表的操作 在单链表第i个位置前插入数据元素e 单链表的操作 删除单链表中第i个数据元素 循环链表 循环链表 循环链表 循环链表的操作 与单链表的基本操作相同，如 链表创建 结点插入 结点删除 结点访问 任何操作必须保证链表的循环特性 双向链表 双向链表 双向链表 双向链表的操作 与单链表的基本操作类似，如 链表创建 结点插入 结点删除 结点访问 任何操作必须保证链表的双向特性 双向链表的操作 在双向链表的第i个位置之前插入元素e 双向链表的操作 双向链表中删除第i个数据元素 链表的特点 利用链表组织数据时，需要通过指针域来定义数据间的逻辑关系 链表中更强调“位置”概念，而不再是“位序” 动态、合理地利用内存空间 插入、删除等操作时无需大量的数据移动 两组有序数据的合并算法 用顺序表结构实现 两组有序数据的合并算法 用链表结构实现 作业 写出以下链表操作的算法 创建一个空的双向循环链表 status CreateList_Dul(DuLinkList L); 取得双向循环链表中第i个数据元素的位置指针 status GetElemP_Dul(DuLinkList L, int i); 将单链表置逆 status ReverseList_L(LinkList L); * ADT List{ D = {ai | i = 1,…n} S = {ai-1, ai | i = 2,…n} P: InitList(L); DestoryList (L); ClearList (L); ListEmpty (L); ListLength (L); GetElem(L, i, e); PriorElem(L, Cur_e, pre_e);