《数据结构》课程教学资源（PPT课件）第二章 线性表（2.1 线性表 2.2 顺序表）

线性结构的定义：如果一个数据元素序列满足：（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；（2）第一个数据元素没有前驱数据元素；（3）最后一个数据元素没有后继数据元素则称这样的数据结构为线性结构简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。数组线性结构包括：线性表、堆栈、队列、字符串、等，其中最典型、最常用的是，线性表---

线性结构的定义： 如果一个数据元素序列满足： （1）除第一个和最后一个数据元素外，每个数据元素只有 一个前驱数据元素和一个后继数据元素； （2）第一个数据元素没有前驱数据元素； （3）最后一个数据元素没有后继数据元素。 则称这样的数据结构为线性结构。 简言之，线性结构反映结点间的逻辑关系是 的。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是- 线性表 一对一 (1:1)

第2章线性表2.1线性表2.2顺序表2.3单链表2.4循环单链表2.5双向链表2.6仿真链表BACK

第2章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表

线性表2.1线性表的定义2.1.1线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n（n≥0）个相同类型数据元素ao,ai，a2，…an-1组成的线性结构

2.1 线性表 2.1.1 线性表的定义 线性表是一种可以在任意位置进行插入和删除数据元 素操作的、由n（n ≥ 0）个相同类型数据元素a0 , a1 , a2 , ., an-1组成的线性结构

线性表的逻辑结构：ao, ao ... ai-1, a, ai+1 '.数据元素线性起点线性终点a;的直接后继a;的直接前趋下标，是元素的序号，表示元素n为元素总在表中的位置个数，即表长。n≥0空表用符号（）表示n=0时称为

（a0 , a1 , . ai-1， ai , ai＋1 ，., an-1） 线性表的逻辑结构： n=0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总 个数，即表 长。n≥0 空表 线性终点 用符号（）表示

例1分析26个英文字母组成的英文表是什么结构。(A, B, C, D, ...... , Z)分析：数据元素都是同类型（字母），元素间关系是线性的例2 分析学生情况登记表是什么结构。学号姓名性别年龄班级男19陈建武2003级电信0301班012003010622女18赵玉凤0120030107042003级电信0302班男19012003010813王泽2003级电信0303班男薛荃190120030109062003级电信0304班男19王春0120030110182003级电信0305班:::::分析：数据元素都是同类型（记录），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！

（ A, B, C, D, . , Z） 学号 姓名 性别 年龄 班级 012003010622 陈建武 男 19 2003级电信0301班 012003010704 赵玉凤 女 18 2003级电信0302班 012003010813 王 泽 男 19 2003级电信0303班 012003010906 薛 荃 男 19 2003级电信0304班 012003011018 王 春 男 19 2003级电信0305班 ： ： ： ： ： 例2 分析学生情况登记表是什么结构。 分析：数据元素都是同类型（记录），元素间关系是线性的。 注意：同一线性表中的元素必定具有相同特性 ！ 例1 分析26 个英文字母组成的英文表是什么结构。 分析： 数据元素都是同类型（字母）， 元素间关系是线性的

2.1.2线性表抽象数据类型数据集合线性表的数据元素集合可以表示为序列ao，ai，a2…，an-1，每个数据元素的数据类型可以是任意的类类型。操作集合在线性表的第i个数据元素前插入数据元素obj。（1）求当前数据元素个数（2）插入数据元素insert(i,obi)(3）丹删除数据元素delete(i)(4)1取数据元素getData(i)删除线性表的第i个数据元素。（5）线性表是否空isEmpty)

数据集合 线性表的数据元素集合可以表示为序列a0 , a1 , a2 ,., an-1，每个数据元素的数据类型可以是任意的类类型。 操作集合 （1）求当前数据元素个数getSize( ) （2）插入数据元素insert(i, obj) （3）删除数据元素delete(i) （4）取数据元素getData(i) （5）线性表是否空isEmpty( ) 2.1.2 线性表抽象数据类型 在线性表的第i个数据元素 前插入数据元素obj。 删除线性表的第i个数据 元素

线性表抽象数据类型的接口定义如下：interface List3void insert(int i, Object obi);//插入//删除Object delete(int i);//取数据元素Object getData(int i);//求元素个数int getSize();bool isEmpty();

线性表抽象数据类型的接口定义如下： interface List { void insert(int i, Object obj);//插入 Object delete(int i); //删除 Object getData(int i); //取数据元素 int getSize(); //求元素个数 bool isEmpty(); }

2.2顺序表2.2.1 顺序表用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用数组实现数据元素的存储。注意：在C#中数组的下标是从开始，即：listArray[n]的有效范围是从listArray[0] ~ listArray[n-1]

2.2.1 顺序表 2.2 顺序表 用一组地址连续的存储单元依次存储线性表的 各个数据元素。即采用顺序存储结构的线性表。 它通常采用数组实现数据元素的存储。 注意：在C#中数组的下标是从0开始， 即：listArray[n]的有效范围是从 listArray[0]～listArray[n-1]

线性表顺序存储特点：(1）逻辑上相邻的数据元素，其物理上也相邻；(2）若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组的下标）。设首元素a.的存放地址为LOC（ao）（称为首地址）设每个数据元素占用L个存储空间，则表中任一数据元素的存放地址为：LOC(ai+1)= LOC(a;) + LLOC( a; ) =LOC(ao)+L*i对上述公式的解释如图所示

(1) 逻辑上相邻的数据元素，其物理上也相邻； (2) 若已知表中首元素在存储器中的位置，则其他元素存放位 置亦可求出（利用数组的下标）。 设首元素a0的存放地址为LOC(a0 )（称为首地址）， 设每个数据元素占用L个存储空间， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a0 ) + L *i 对上述公式的解释如图所示 线性表顺序存储特点：

线性表的顺序存储结构示意图内容地址元素在表中的位序b=LOC(ao)01ao1aib+Liaib +iLi+1ai+1......an-1n-1b +(n-1)L空闲区b +(maxSize-上LOC(a; ) =LOC(ao)+ L*i

an-1 . ai+1 ai . a1 a0 地址 内容 元素在表中的位序 0 i 1 n-1 空闲区 i+1 b=LOC(a0 ) L b + L b +iL b +(n-1)L b +(maxSize- 1)L LOC ( ai ) = LOC( a0 ) + L *i 线性表的顺序存储结构示意图