文档介绍：1 线性结构的定义: 若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为:( a 1 , a 2 , ……, a n) 简言之,线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点; 特点②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。线性结构包括: 线性表、堆栈、队列、字符串、数组等,其中最典型、最常用的是------ 线性表线性表一对一(1:1) 2第第2 2章章线性表线性表 线性表的基本概念线性表的基本概念 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法 线性表的链式线性表的链式存储结构及其算法存储结构及其算法 算法算法应用举例应用举例 数组数组 3 线性表的基本概念 1、线性表 它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的,由 n(n ≥0) 个相同类型数据元素 a 0, a 1, …, a n-1 组成的线性结构。 4(a 0, a 1, …a i-1 ,a i, a i+1,…, a n-1) 线性表的逻辑结构: 线性表的逻辑结构: n=0 时称为数据元素线性起点 a i的直接前趋 a i的直接后继下标, 是元素的序号,表示元素在表中的位置 n 为元素总个数,即表长。 n n≥≥0 0空表线性终点 5 ( A, B, C, D, …… , Z ): : : : : 22 88 男王春 005 21 81 男薛荃 004 19 90 男王泽 003 20 80 女赵玉凤 002 23 70 女张东 001 年龄成绩性别姓名学号例2 分析学生档案表是什么结构。分析: 数据元素都是同类型( 记录),元素间关系是线性的。分析: 数据元素都是同类型( 字母), 元素间关系是线性的。注意:同一线性表中的元素必定具有相同特性注意:同一线性表中的元素必定具有相同特性! ! 例1 分析 26 个英文字母组成的英文表是什么结构。 6 2、线性表抽象数据类型它包括两个方面: 数据集合:{ a 0, a 1, …, a n-1 }a i的数据类型为 DataType 操作集合: (1) InitList(List ) 初始化线性表,建一空线性表 List (2) ListLength(L ) 求当前数据元素个数(3) GetElement(List,i ) 取线性表中第 i个元素( 1,n) (4) ListInsert(L,i,x ) 插入数据元素(5)ListDelete(L,i,x) 删除数据元素(6)ListGet(L,i,x) 取数据元素等 7 3、线性表的存储结构(1)顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点: (任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素,物理上也相邻。(2) 链式存储结构:它是把数据元素和指针定义成一个存储体,使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。特点: 任意两个在逻辑上相邻的数据元素在物理上不一定相邻,数据元素的逻辑次序是通过链中的指针链接实现的。 8 线性表的顺序存储结构及其算法一、顺序表的存储结构二、顺序表的实现三、顺序表的运算效率分析 9 一、顺序表的存储结构表示 1、顺序表: 用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。可以利用数组 V[n] 来实现注意:在 C语言中数组的下标是从 0开始,即: V[n] 的有效范围是从 V[0] ~V[n-1] 10 (1) 逻辑上相邻的数据元素,其物理上也相邻; (2) 若已知表中首元素在存储器中的位置,则其他元素存放位置亦可求出( 利用数组 V[n] 的下标)。设首元素 a 0的存放地址为 LOC(a 0)(称为首地址), 设每个元素占用存储空间(地址长度)为 L字节, 则表中任一数据元素的存放地址为: LOC ( a i+1 ) = LOC( a i ) + L LOC ( LOC ( a a i i ) = LOC( ) = LOC( a a 0 0 ) + L ) + L * * i i 对上述公式的解释如图所示 2、线性表顺序存储特点: