第2篇 线性表顺序表.ppt

线性表的定义 线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有序（前后次序）序列。 线性表的长度：线性表中数据元素的个数。 空表：长度等于零的线性表，记为：L=( )。 非空表记为：L＝（a1, a2 , …, ai-1, ai , …, an) 线性表的图形表示 线性表的特性 线性表的抽象数据类型定义 线性表的抽象数据类型定义（续） 线性表的抽象数据类型定义 线性表的抽象数据类型定义 Insert 前置条件：表已存在 输入：插入i；待插x 功能：在表的第i个位置处插入一个新元素x 输出：若插入不成功，抛出异常 后置条件：若插入成功，表中增加一个新元素 Delete 前置条件：表已存在 输入：删除位置i 功能：删除表中的第i个元素 输出：若删除成功，返回被删元素，否则抛出异常 后置条件：若删除成功，表中减少一个元素 线性表的抽象数据类型定义 Empty 前置条件：表已存在 输入：无 功能：判断表是否为空 输出：若是空表，返回1，否则返回0 后置条件：表不变 }ADT List 顺序表类型的示意图1 SqList L,*p=L; L的数据成员如何表示 （1）L.elem[i], L.length, L.listsize （2）p-elem[i], p-length, p-listsize 顺序表类型的示意图2 顺序表的实现——初始化（方案1） 操作接口： int InitSqlist(SqList L ) 顺序表的实现——初始化（方案1） 顺序表的实现——初始化（方案2） 操作接口： int InitSqlist(SqList L,int n ) 顺序表的实现——初始化（方案2） 顺序表的实现——插入 操作接口 int InsertSqlist(SqList L,int i, ElemType 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； 顺序表的实现——插入 int InsertSqlist(SqList L,int i, ElemType x) { if (L.length=L.listsize){printf(上溢);return 0;} if (i1 | | iL.length+1){printf(位置非法); return 0;} for (j=length; j=i; j--) L.elem[j]=L.elem[j-1]; L.elem[i-1]=x; L.length++; return 1; } 顺序表的实现——插入 最好情况（ i=n+1）： 基本语句执行0次，时间复杂度为O(1)。 最坏情况（ i=1）： 基本语句执行n次，时间复杂度为O(n)。 平均情况（1≤i≤n+1）： 时间复杂度为O(n)。 操作接口： int DeleteSqlist(SqList L,int i,ElemType x) 删除前：(a1, …, ai-1,ai,ai+1,…,an) 删除后：(a1,…,ai-1,ai+1, …,an) 例：（35, 33, 12, 24, 42），删除i=2的数据元素。 顺序表的实现——按位查找 操作接口： int GetSqlist(SqList L,int i) 2.2 线性表的顺序存储结构及实现 0 … i-2 i-1 … n-1 Max-1 a1 … ai-1 ai … an 空闲 n 算法描述： int GetSqlist(SqList L,int i){ if (i=1 i=L.length) return i-1; else return -1; } 时间复杂度？ O(1) 第二章 线性表 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： 学生成绩登记表 2.1 线性表的逻辑结构 姓 名 英语 数据结构 高数 学号 丁一 96 78 87 0101 李二 87 90 78 010