706-⒈教学内容：21 线性表逻辑结构；22 线性表的顺序存储及运算实现.ppt

01/06/2002 数据结构讲义 第二章 线性表 ⒈教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。 ⒉教学目的：⑴理解线性表的定义及其运算； ⑵理解顺序表和链表的定义、组织形式、结构特征和类型说明； ⑶掌握在这两种表上实现的插入、删除和按值查找的算法； ⑷了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。 ⒊教学重点：⑴线性表的定义及逻辑上的特点； ⑵顺序表上插入、删除和定位运算的实现； ⑶单链表的结构特点及类型说明； ⑷头指针和头结点的作用及区别； ⑸定位、删除、插入运算在单链表上的实现； ⑹循环链表、双链表的结构特点，循环链表、双链表上删除与插入运算的实现。 ⒋教学难点：⑴线性表与线性结构的联系与区别； ⑵头结点在链表中的作用；指针操作； ⑶删除、插入运算中的指针操作顺序； ⑷双链表上指针的操作顺序。 ⒌教学时数： 8学时（含习题课2学时） 2.1 线性表的逻辑结构 线性表的定义 线性表的基本操作 2.1.1 线性表的定义 线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，...，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，...，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。 需要说明的是：ai为序号为 i 的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型； 在字符串中，它是字符型； 等等。 2.1.2 线性表的基本操作 ⑴线性表初始化：Init_List(L) 初始条件：表L不存在 操作结果：构造一个空的线性表 ⑵求线性表的长度：Length_List(L) 初始条件：表L存在 操作结果：返回线性表中的所含元素的个数 ⑶取表元：Get_List(L,i) 初始条件：表L存在且1=i=Length_List(L) 操作结果：返回线性表L中的第ｉ个元素的值或地址 ⑷按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。 初始条件：线性表L存在 操作结果：返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。 ⑸插入操作：Insert_List(L,i,x) 初始条件：线性表L存在，插入位置正确 (1=i=n+1,ｎ为插入前的表长)。 操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1，插入后表长=原表长+1。 ⑹删除操作：Delete_List(L,i) 初始条件：线性表L存在，1=i=n。 操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，新表长＝原表长－１。 需要说明的是： 某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。 在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构。 2.2 线性表的顺序存储及运算实现 线性表的顺序存储 顺序表上基本运算的实现 顺序表应用举例 2.2.1 线性表的顺序顺序存储 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储