数据结构第2章线性表课件.

《数据结构第2章线性表课件.》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学目标1、知识目标1）了解线性表的有关概念及线性表逻辑特征；2）掌握线性表的顺序存储结构和链式存储结构；3）掌握顺序表、链表的描述方法；4）掌握顺序表、链表基本操作的实现算法。5）掌握头插法建立链表和尾插法建立带头结点的链表的方法；6）了解循环链表和双向链表的描述和基本操作的实现。2、能力目标1）具有恰当的选择线性表作为数据的逻辑结构、顺序表作为数据的存储结构的能力；2）具有应用顺序表解决实际问题的能力。3、素质目标养成善于思考解决实际问题的良好习惯。2.1线性表的顺序存储结构一、线性表1、线性表的定义线性表是由n个数据元素的有限序列（a1,a2,…,a

2、n）组成的，其中每一个数据元素ai的具体含义可以按不同的情况和要求定义为具体的内容，它可以是一个数、一个符号、一串文字，甚至是其他更复杂的信息。线性表中数据元素的个数n称为线性表的长度。2、线性表的例子例如：英文字母表（A,B,…,Z）是一个线性表，表中的每个字母是一个数据元素；又如：一副扑克牌的点数（2,3,…,10,J,Q,K,A）也是一个线性表，这里的数据元素是每张牌的点数；再如：学生成绩表由学号、姓名、各科成绩组成，该成绩表是一个线性表，每个学生的信息是一个数据元素（记录）。3、线性表的逻辑特征一个线性表（a1,a2,…,an）是由n个数据元素组成

3、的有限序列。若n=0，则表示一个空表，即没有任何数据元素的线性表；若n>0，则除a1和an外，每个数据元素有且仅有一个直接前驱和一个直接后继，即如果ai（其中1

4、在线性表中是连续的，表的长度（即数据元素的个数）可根据需要增加（插入）和减少（删除），但调整后的线性表中，数据元素仍然必须是连续的。即在线性表中的某个位置插入一个数据元素，该位置及其后的数据元素都要依次后移，在线性表中的某个位置删除一个数据元素，其后的数据元素都要依次前移，不能出现空位，要保持线性表的线性结构；2）线性表有确定的最大长度，即线性表的容量，表内元素的个数是线性表的当前长度。根据表内元素的数量，线性表可以分为空表（元素个数为0）、满表（元素个数为线性表的容量）或有若干个元素的表；3）线性表中所有数据元素的同一数据项，其属性相同，它们的数据类型是

5、一致的。5、线性表的基本操作对于线性表，根据其性质、结构特点以及在实际应用中的需要，有如下几种基本的运算或操作。1）线性表初始化格式：InitList(L)初始条件：线性表L不存在。操作结果：构造一个空的线性表L。2）求线性表的长度格式：LengthList(L)初始条件：线性表L存在。操作结果：返回线性表L中所有元素的个数。3）取表元格式：GetList(L，i)初始条件：线性表L存在，且1≤i≤LengthList(L)。操作结果：返回线性表L的第i个元素(ai)的值。4）按值查找格式：LocateList(L，x)初始条件：线性表L存在，x有确定的值

6、。操作结果：在线性表L中查找值为x的数据元素，并返回该元素在L中的位置。5）插入操作格式：InsertList(L，i，x)初始条件：线性表L存在，i为插入位置。操作结果：在线性表L的第i个元素(ai)位置上插入值为x的新元素，原序号为i,i+1,…,n的数据元素的序号插入后变为i+1,i+2,…,n+1，插入后表长=原表长+1。6）删除操作格式：DeleteList(L，i)初始条件：线性表L存在，i（1≤i≤n）为给定的待删除元素的位置值。操作结果：在线性表L中删除序号为i的数据元素(ai)，删除后，原序号为i+1,i+2,…,n的数据元素的序号变为i

7、,i+1,…,n-1，删除后表长=原表长-1。二、线性表的顺序存储结构——顺序表1、顺序表把线性表按顺序存储方法，即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称为顺序表。2、顺序表中数据元素存储地址的计算假设每个数据元素在存储器中占用d个字节的存储单元，如果第一个元素a1的存储地址（也称为基地址）设为LOC(a1)，则第i个元素ai的存储地址LOC(ai)可表示为LOC(ai)=LOC(a1)+(i-1)×d由此，只要知道基地址和每个数据元素的存储长度，就可以求出任一数据元素的存储地址，也就可以随机地访问顺序表的每

8、一个元素。因此，顺序表是一种随机存取结构。3、顺序表的描述1）通过