第3章数据结构—— 线性表.ppt

第三章 线性表 线性结构特点 在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 3.1 线性表的概念 3.1 线性表的概念 3.1.2 线性表的抽象数据类型描述 基本操作 基本操作 基本操作 定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址计算方法 LOC(ai+1)=LOC(ai)+d LOC(ai)=LOC(a1)+(i-1)*d d —一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 图3.1 线性表的顺序存储结构 定义：线性表的插入是指在第i（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表 int ListInsert(SqList *L,int i,DataType e){  int k; if (L-length==MAXSIZE) return ERROR; if (i1 || iL-length+1) return ERROR; if (i=L-length)  { for(k=L-length-1;k=i-1;k--)  L-data[k+1]=L-data[k]; } L-data[i-1]=e;  L-length++; return OK;} 算法时间复杂度T(n) 设Pi 是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为： 11. 线性表中数据元素的删除 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为： 顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 练习： 1.实现在顺序表中按值插入元素。 2.给定一个顺序表L=（a1,a2,a3,...,an),请设计一个算法删除所有值大于min而且小于max的元素。 实现在顺序表中按值插入元素 int ListInsert(SqList *L,DataType e){ int k; if (L-length==MAXSIZE) return ERROR; for(k=L-length;k=1;k--) { if(L-data[k-1]e) { L-data[k]=L-data[k-1]; } else { break; } } L-data[k]=e; L-length++; return OK; } 给定一个顺序表L=（a1,a2,a3,...,an),请设计一个算法删除所有值大于min而且小于max的元素 int ListDelete(SqList *L,int min,int max) { int k,i; if (L-length==0) return ERROR; for(k=1;k=L-length;k++) { if(L-data[k-1]minL-data[k-1]max) { for(i=k;iL-length;i++) { L-data[i-1]=L-data[i]; } L-length--; k--; } } return OK; } 3.3 单向链表 3.3 单向链表 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。 这两部分信息组成数据元素的存储映像，称为结点。由于上述链表的每个结一个点只有一个指示其直接相继的信息，故将这种链表称为单向链表，简称为单链表。 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 3.3.3单向链表的基本操作 (1) 初始化单向链表 (2)判断是否为空 (3) 置空 (4) 求表长 (5) 取值 (6) 求位序(查找) (7) 单链表的插入 (7) 单链表的插入 (7) 单链表的插入 (8) 单链表的删除 (8) 单链表的删除 (8) 单链表的删除 (9) 单链表的遍历 (10) 头插法 (10) 头插法 (11) 尾插法 (11) 尾插法 它是一种动态结构 不需预先分配空间 指针