当前位置:首页 >> >>

数据结构第2章线性表-PPT课件_图文

第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储结构及其运算 2.3 线性表的链式存储结构及其运算 2.4 顺序表和链表的比较 2.5 线性表的应用 本章学习目标 ? ? ? ? 掌握线性表的基本概念 重点 掌握顺序表的各种基本操作及实现 掌握单链表、双向链表的的各种基本操作 会用线性表解决实际问题 ? 关键:各种基本操作的程序实现 ? 难点:用线性表解决实际问题 2.1 线性表的基本概念 2.1.1 线性表的定义 ? 线性表(List):数据类型相同的n(n≥0)个数据元素组成 的有限序列, L=(a1,a2, …,ai-1,ai,ai+1, …,an) ? 表中数据元素类型相同,可为一个数、字符、结构体 ? 线性表的长度:表中数据元素的个数n; ? 空表:n=0,L=( ); ? 下标i:表示数据元素的位序; ? n>0时a1:表头元素; an:表尾元素; ? ai-1为ai(i>=2)的直接前驱; ai+1为ai(i<=n-1)为的直接 后继 职工工资表 职工 号 001 姓名 性别 年龄 工资 160.5 0 002 32 150.0 蔡三 男 0 003 28 130.0 张四 女 0 每一行数据为一个数据元素(结点)。 …… …… …… …… …… 王二 男 35 ? 线性表的逻辑结构是线性结构 ? 元素间是1对1关系 ? 有且仅有一个开始(头)结点 ? 有且仅有一个终端(尾)结点 ? 除开始结点和终端结点外的结点都最多只有一 个直接前驱和一个直接后继 ? 当表中只有一个元素时,它既没前驱也没后继 ? 线性表是一种最简单、最常用的(线性)数 据结构 2.1.2 线性表及其基本操作 ? 1.初始化线性表 InitList(L) ? ? 初始条件 线性表L不存在。 运算结果 构造一个空的线性表,n=0。 ? 2.求线性表的长度LenList(L) ? 初始条件 表L存在。 ? 运算结果 返回线性表中所含数据元素的个数n。 3.读取线性表中的第i个数据元素GetfromList(L,i) ? 初始条件 表L存在。 ? 运算结果 返回线性表L中第i个元素的值或地址 1≤i≤n 。如果线性表为空,或者i超过 了线性表的长度,则报错。 4.按值查找SearchList(L,x) ? 初始条件 线性表L存在,x是给定的一个数据元素。 ? 运算结果 在表L中查找值为x的数据元素,返回x在L 中的位置或地址,若有多个则返回在L中首 次的位序或地址(查找成功);否则,在L中 未找到值为x的数据元素,返回一特殊值表 示查找失败。 5.插入操作InsertList(L,i,x) ? 初始条件 线性表L存在,i表示新元素将要插入的位置 (1≤i≤n+1,n为插入前的表长)。 ? 运算结果 在线性表L的第i个位置上插入一个值为x的新元素,该 元素成为新的第i个数据元素。 原位序为i,i+1,…,n 的数据元素的位序变为i+1,i+2,…,n+l。如果插入位 置i=n+1,则直接在线性表的最后一个数据元素后增加 x,插入后,表长=原表长+1。 6.删除操作:DeleteList(L,i) ? 初始条件 线性表L存在,i表示需要删除的数据元素的位序。 ? 运算结果 如果L为空表或位序i大于线性表长度,则报错。在线性 表L中删除位序为i的数据元素,删除后使位序为i+1,i+2,…,n 的元素变成位序为i,i+1,…,,n-1,新表长=原表长-1。 ? 7. PriorElement(L,i) ? 8. NextElement(L,i) ? 9. ClearList(L) ? 10. ListEmpty(L) ? 11. PrintList(L) 根据以上基本操作,可以 实现一些复杂的操作。 假设利用线性表LA和LB分别表 示两个集合A和B,现要求构成一个 新的集合A=AUB。要求对线性表作如 下操作:扩大线性表LA,将存在于 LB中而不存在线性表LA中的数据元 素插入到线性表LA中去。 Step1 LB中依次取出每个元素。 Step2 依次在LA中进行查找。 Step3 若不存在,则插入之。 2.2 线性表的顺序存储结构及其运算 2.2.1 顺序表 ?顺序存储结构 ? 顺序存储结构:用一组地址连续(存储空间 紧邻)的存储单元依次存储数据元素的方法 ?顺序表:采用顺序存储结构的线性表 ?顺序表的特点 ? 数据元素的逻辑顺序与物理顺序是一致的。 ? 由于线性表的各个数据元素的类型相同,所以 线性表便于顺序存储。 ? 对顺序表,根据表的第一个数据元素的地址可 以计算出其他数据元素的地址。 ? 假设每个数据元素占据的存储块包括c个存储 地址,则第一个存储地址通常称为该数据元素 的地址。 ? ai的地址用Loc(ai)表示,则第i+1个数据元素的 地址为 Loc(ai+1)=Loc(ai)+c l≤i≤n-1 ? 线性表的基地址:数据元素a1的地址 ?则 Loc(ai)=Loc(a1)+(i-1)c l≤i≤n 顺序存储结构示意图(顺序表): 首地址 起始地址 基地址 存储地址 内存状态 元素a1 b b+m 元素a2 …….. b+(i-1)*m 元素ai …….. b+(maxlen-1)*m 元素an 每个元素所占用 的存储单元个数 Loc(元素i)=b +(i-1)*m 线性表的顺序存储示意图 ?在C语言中,一维数组在内存中占用的存 储空间是一组连续的存储区域,因此顺序 表可用一维数组表示。 #define MAXSIZE 100 TypeDef struct { DataType elem[MAXSIZE]; /*存放顺序表的容量*/ int Length; /*顺序表的实际长度*/ } SeqList; 静态数组-----存储空间的申请和释放有系统 自动完成 ? 由于线性表所需最大存储空间不容易确定,通常 可以使