数据结构 第2章 线性表.ppt

线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 可表示为：（a1 , a2 , , an） 简言之，线性结构反映结点间的逻辑关系是 的。 特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个 直接后继。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是- 线性表线性表 一对一 (1:1) 1 第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构 及其算法及其算法 2.3 2.3 线性表的链式线性表的链式存储结构存储结构 及其算法及其算法 2.4 2.4 算法算法应用举例应用举例 2 2.1 线性表的基本概念 、线性表 它是一种最简单的线性结构。是一种 可以在任意位置进行插入和删除数据元素操作的， 由n（n0)个相同类型数据元素a0, a1, , an-1组 成的线性结构。 3 （a0, a1, ai-1，ai, ai1 ，, an-1） 线性表的逻辑结构：线性表的逻辑结构： n=0时称为 数据元素 线性起点ai的直接前趋ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总 个数，即表 长。n0n0 空表 线性终点 4 （ A, B, C, D, , Z） 学号姓名性别成绩年龄 001张东女7023 002赵玉凤女 8020 003王 泽男 9019 004薛 荃男 8121 005王 春男 8822 ： ： 例2 分析学生档案表是什么结构。 分析：数据元素都是同类型（记录），元素间关系是线性的。 分析： 数据元素都是同类型（字母）， 元素间关系是线性的。 注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！ 例1 分析26 个英文字母组成的英文表是什么结构。 5 、线性表抽象数据类型 它包括两个方面： 数据集合： a0, a1, , an-1 ai的数据类 型为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) 取数据元素等 6 3、线性表的存储结构 (1)顺序存储结构:它是使用一片地址连续的 有限内存单元空间存储数据元素的一种计算机存储 数据方法。 特点：(任意两个在逻辑上相邻的数据元素 在物理位置上也必然相邻)逻辑上相邻的元素，物理 上也相邻。 (2)链式存储结构:它是把数据元素和指针定 义成一个存储体，使用指针把发生联系的数据元素 链接起来的一种计算机存储数据方法。 特点：任意两个在逻辑上相邻的数据元素在 物理上不一定相邻，数据元素的逻辑次序是通过链 中的指针链接实现的。 7 2.2 线性表的顺序存储结构及其算法 一 、顺序表的存储结构 二、 顺序表的实现 三、 顺序表的运算效率分析 8 一、 顺序表的存储结构表示 1、顺序表：用一组地址连续的存储单元 依次存储线性表的各个数据元素。即采用顺序存储 结构的线性表。它通常采用静态数组实现数据元素 的存储。 可以利用数组Vn来实现 注意：在C语言中数组的下标是从0开始，即： Vn的有效范围是从 V0Vn-1 9 (1) 逻辑上相邻的数据元素，其物理上也 相邻； (2) 若已知表中首元素在存储器中的位置， 则其他元素存放位置亦可求出（利用数组Vn的下 标）。 设首元素a0的存放地址为LOC(a0)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( LOC ( a a i i ) = LOC( a) = LOC( a 0 0 ) + L *i ) + L *i 对上述公式的解释如图所示 2、线性表顺序存储特点： 10 a0 a1 ai ai+1 an-1 地址 内容 元素在表中的位序 0 i 1 n-1 空闲区 i+1 L b=LOC(a0) b + L b +iL b +(n-1)L b +(MaxSize-1)L LOC ( LOC ( a a i i ) = LOC( a) = LOC( a 0 0 ) + L *i) + L *i 3、线性表的顺序存储结构示意图 11 4、用C语言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示数组的最大元素个数，list表 示顺序表的数组名，size表示顺序表中当前存储的数 据元素个数，它必须满足size MaxSize，SeqList是 该结构体的名字。*/ 12 设有一维数组，下标的范围是到 ，每个数组元素用相邻的个字节存储。存储 器按字节编址，设存储数组元素的第一 个字节的地址是，则的第一个字节 的地址是多少？ 113 LOC( M3 ) = 98 + 5 3 =113 解：已知地址计算通式为： LOC(ai) = LOC(a0) + L *i 例1 13 char V30; void build() /*字母线性表的生成，即建表操作 */ int i; V0=a; for( i=1; i=i; j- -) aj+1=a j ; a i =x; n+; / 元素后移一个位置 / 插入x / 表长加1 核 心 语 句 ： 2)插入 17 在线性表的第i个位置前插入一个元素的示意图如下： 12 13 21 24 28 30 42 77 12 13 21 24 2525 28 30 42 77 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 插入2525 18 实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 删除线性表的第i个位置上的元素 for ( j=i+1; j=n-1; j+ ) aj-1=aj; n-; / 元素前移一个位置 / 表长减1 核心语句： 3)删除 19 1 2 3 4 5 6 7 8 9 12 13 21 24 25 28 30 42 77 1 2 3 4 5 6 7 8 12 13 21 24 28 30 42 77 删除顺序表中某个指定的元素的示意图如下 ： 20 例：建立一个线性表，先依次输入数据元素1，2 ，3，4，10，然后删除，最后依次显示当 前线性表中的数据元素。假设该线性的数据元素 个数最坏情况下不会超过100个。 实现方法： 1、采用直接编写一个主函数实现。 2、利用已设计实现的抽象数据类型模块。（存 放在头文件名为SeqList.h中，通过 #include “SeqList.h” ） 21 三、 顺序表操作的效率分析 算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度 ） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位 置. 思考：若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。 时间效率分析: 22 推导：假定在每个元素位置上插入x的可能性都一样（即 概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。 若在首结点前插入，需要移动的元素最多，后移n次； 若在a1后面插入，要后移n-1个元素，后移次数为n-1; 若在an-1后面插入，要后移1个元素； 若在尾结点an之后插入，则后移0个元素； 所有可能的元素移动次数合计： 0+1+n = n(n+1)/2 故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n)O(n) 共有多少种插入形式?连头带尾有n+1种! 23 同理可证：顺序表删除一元素的时间效率为: T（n)=(n-1)