第3章线性表分解.ppt

数据结构与算法 作 者：胡明 王红梅 出版社：电子工业出版社 邮 箱：wanghm@mail.ccut.edu.cn 线性表的定义 线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。 线性表的长度：线性表中数据元素的个数。 空表：长度等于零的线性表，记为：L=( )。 非空表记为：L＝（a1, a2 , …, ai-1, ai , …, an) 线性表的特性 线性表的抽象数据类型定义 线性表的抽象数据类型定义 线性表的抽象数据类型定义 线性表的抽象数据类型定义 Insert 前置条件：表已存在 输入：插入i；待插x 功能：在表的第i个位置处插入一个新元素x 输出：若插入不成功，抛出异常 后置条件：若插入成功，表中增加一个新元素 Delete 前置条件：表已存在 输入：删除位置i 功能：删除表中的第i个元素 输出：若删除成功，返回被删元素，否则抛出异常 后置条件：若删除成功，表中减少一个元素 线性表的抽象数据类型定义 Empty 前置条件：表已存在 输入：无 功能：判断表是否为空 输出：若是空表，返回1，否则返回0 后置条件：表不变 ADT 顺序表的实现——初始化顺序表 操作接口：void InitList(SeqList L) 顺序表的实现——建立顺序表 操作接口：void Creat(SeqList L, DataType a[ ], int n) 顺序表的实现——建立顺序表 void Creat(SeqList L, DataType a[ ], int n) { if (n MaxSize) {printf(参数非法); exit(-1);} for (i = 0; i n; i++) L.data[i] = a[i]; L.length = n; } 顺序表的实现——插入 操作接口： void Insert(int i, DataType x) 插入前：(a1, … , ai-1, ai, … , an) 插入后：(a1, … , ai-1, x , ai, … , an) 顺序表的实现——插入 例：（35，12，24，42），在i=2的位置上插入33。 算法描述——伪代码 1. 如果表满了，则抛出上溢异常; 2. 如果元素的插入位置不合理，则抛出位置异常; 3. 将最后一个元素至第i个元素分别向后移动一个位置； 4. 将元素x填入位置i处； 5. 表长加1； 顺序表的实现——插入 void Insert(SeqList L, int i, DataType x) { if (L.length = MaxSize) {printf(上溢); exit(-1);} if (i 1 || i length + 1) {printf(位置); exit(-1);} for (j = L.length; j = i; j--) //j表示元素序号 L.data[j] = L.data[j - 1]; L.data[i - 1] = x; L.length++; } 顺序表的实现——插入 最好情况（ i=n+1）： 基本语句执行0次，时间复杂度为O(1)。 最坏情况（ i=1）： 基本语句执行n+1次，时间复杂度为O(n)。 平均情况（1≤i≤n+1）： 时间复杂度为O(n)。 操作接口： DataType Delete(int i) 删除前：(a1, …, ai-1,ai,ai+1,…,an) 删除后：(a1,…,ai-1,ai+1, …,an) 例：（35, 33, 12, 24, 42），删除i=2的数据元素。 ⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用链表做存储结构。 ⑵当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。 单链表的实现———删除 操作接口： DataType Delete(int i); p 如何实现结点ai-1和ai之间逻辑关系的变化？ first a1 ai-1 ai+1 ai 算法描述： q=p-next; x=q-data; p-next=q-next; fre