内容概要
1、线性表的概念、特点、及其基本操作定义
3、线性表的链式存储结构及其算法实现
4、循环链表及其线性表的应用
教学目标
1、了解线性表的逻辑结构特征，即数据元素之间的线性关系。 2、熟练掌握线性表的两类存储结构。
3、重点掌握顺序表的插入和删除操作的算法以及链表的建立、查、插入和删除操作的算法。 4、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
基本知识点：线性表、顺序表、链表、循环链表。
重点：线性表的存储结构及算法实现，链式存储结构及算法实现。
难点：单链表和双链表的各种算法设计。
本章知识体系结构：
课时安排：4个课时。
课程 | 数据结构 | 教学教具 | 多媒体课件 |
学时 | 2 | 班级 | 06网络 | 教学日期/ 课时 | /2课时 |
教学单元 | 第二章 线性表 |
教学方法 | 讲授（PPT） |
教学目标 | 1、了解线性表的逻辑结构特征，即数据元素之间的线性关系。 2、熟练掌握线性表的两类存储结构。 3、重点掌握顺序表的插入和删除操作的算法以及链表的建立、查、插入和删除操作的算法。 |
教学重点 | 线性表的顺序存储结构和链式存储结构 |
教学难点 | 线性表的存储结构和链式存储结构上的操作算法 |
组 织 教 学 | 一．线性表的定义 二．线性表的顺序存储结构及其运算 三．线性表的链式存储结构及其运算 四．小结 五．布置作业 |
作 业 | 复习本节内容并预习下节课 |
课堂情况及 课后分析 | |
课程 | 数据结构 | 教学教具 | 多媒体课件 |
学时 | 2 | 班级 | 06网络 | 教学日期/ 课时 | /2课时 |
教学单元 | 第二章 线性表 |
教学方法 | 讲授（PPT）与实验演示 |
教学目标 | 1、掌握循环链表和双向链表。 2、熟练掌握线性表在实际问题中的应用。 |
教学重点 | 线性表的应用 |
教学难点 | 循环链表及线性表在实际问题中的应用 |
组 织 教 学 | 一．导入 二．循环链表和双向链表 三．线性表的应用举例 四．小结 五．布置作业 |
作 业 | 复习本讲内容并预习新课 |
课堂情况及 课后分析 | |
课程 | 数据结构 | 教学教具 | 多媒体课件 |
学时 | 2 | 班级 | 06网络 | 教学日期/ 课时 | /2课时 |
教学单元 | 第二章 线性表 |
教学方法 | 讲授（PPT）与实验演示 |
教学目标 | 熟练掌握线性表在实际问题中的应用。 |
教学重点 | 线性表的应用 |
教学难点 | 线性表的应用 |
组 织 教 学 | 一．导入 二．线性表的应用举例 三．综合实验 四．小结 五．布置作业 |
作 业 | 习题二 |
课堂情况及 课后分析 | |
| | | | | | | | | | | | | | | | |
2.1 线性表的定义和基本运算
线性表是最常用且最简单的一种数据结构，是其他数据结构的基础，它被广泛地应用在程序设计中。从本章到第4章讨论的线性表、栈、队列和串的逻辑结构都属于线性结构。
2.1.1 线性表的定义
1. 定义
线性表（linear list）是由n(n≥0)个相同类型的数据元素a1，a2，…，an组成的有限序列，记作：
L=(a1,a2,…,an)
其中，L为线性表的名称，ai为组成该线性表的数据元素(i=1,2,3,…,n)。
线性表中数据元素的个数n(n≥0)称为线性表的长度。当n=0时，线性表为空表，即该线性表不包含任何数据元素。当n＞0时，线性表中的每一个数据元素都有一个确定的位置，即线性表中数据元素在位置上是有序的。
数据元素的类型可以是高级语言提供的简单类型或用户定义的任何类型，如整型、实型、字符型或记录类型等。
2．逻辑特点
从线性表的定义可以看出，非空线性表（n＞1）的逻辑特征为：有且仅有一个开始数据元素a1，它没有直接前驱，仅有一个直接后继a2；有且仅有一个最后数据元素an，它没有直接后继，仅有一个直接前驱an-1；其余的数据元素 ai (1＜i＜n)有且仅有一个直接前驱ai-1和一个直接后继ai+1。对于仅有一个数据元素的线性表（n=1），数据元素a1既是开始数据元素又是最后数据元素，它没有直接前驱，也没有直接后继。
3. 线性表举例
例2-1 某个班级星期一的课表（大学英语，数据结构，程序设计，统计原理）是一个线性表，表中的数据元素是课程名。
例2-2 大写英文字母(A,B,C,…,Z)是一个线性表，表中的数据元素是大写英文字母，数据元素按照字母顺序排列，长度为26。
例2-3 表1-1所示的学生信息表是一个线性表，数据元素是每个学生的信息，包括学号、姓名、性别、专业、年级等，可以对它进行插入、删除、查和修改等操作。
2.1.2 线性表的基本运算
数据结构的运算是定义在逻辑结构上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。
线性表有如下基本运算。
（1）线性表初始化：Init_List(L)
初始条件：表L不存在。
操作结果：构造一个空的线性表。
（2）求线性表的长度：Length_List(L)
初始条件：表L存在。
操作结果：返回线性表所含数据元素的个数。
（3）取线性表元素：Get_List(L,i)
初始条件：表L存在且1≤i≤Length_List(L)。
操作结果：返回线性表L中第ｉ个元素的值或地址。
（4）按值查：Locate_List(L,x)，ｘ是给定的一个数据元素。
初始条件：线性表L存在。
操作结果：在表L中查值为ｘ的数据元素，其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查成功；否则，在L中未到值为ｘ的数据元素，返回一特殊值表示查失败。
（5）插入操作：Insert_List(L,i,x)
初始条件：线性表L存在，插入位置正确（1≤ i ≤n+1，ｎ为插入前的表长），且有足够的空间。
操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i ,i+1,…,n 的数据元素的序号变为 i+1,i+2,…,n+1，插入后表长等于n+1。
（6）删除操作：Delete_List(L,i)
初始条件：线性表L存在，1≤i≤n。
操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1,i+2,…,n 的元素的序号变为 i,i+1,…,n-1，新表长等于n-１。
（7）判断线性表是否为空：IsEmpty(L)
初始条件：线性表L存在。
操作结果：若线性表L为空，则返回TRUE，否则返回FALSE。
（8）判断线性表是否为满：IsFull(L)。线性表的空间总是有限的，为了使插入操作正确，在插入之前可判断线性表是否已满，若满则无法进行插入操作。
初始条件：线性表L存在。
操作结果：若线性表L已满，则返回TRUE，否则返回FALSE。
对线性表的操作有许多，在此不一一列举。将上述基本操作进行组合，可以实现对线性表的各种复杂的操作，比如将一个线性表按照某种需要拆分成两个线性表，将两个线性表按某种要求合并成一个线性表等。
2.2 线性表的顺序存储
2.2.1 顺序表
计算机的内存是由有限多个存储单元组成的，每个存储单元都有唯一的地址，各存储单元的地址是连续编址的。线性表中各元素依次存储在连续的一块存储空间中，用这种存储形式存储的线性表称为顺序表。即逻辑结构上相邻的数据元素，其在物理位置上也是相邻的。设数据元素a１的存储地址为Loc(a１)，通常将它作为顺序表的起始地址，又叫做基地址。每个数据元素占c个存储单元，则第i个数据元素的存储地址为：
Loc(ai)=Loc(a１)+(i-1)*c (1≤i≤n)
由此可见，数据元素ai的存储地址是其在线性表中的位序i的线性函数，由首元素地址和每个数据元素所占存储单元的个数就可求出第i个数据元素的存储地址。
由上述可知，顺序存储结构的特点如下：
（1）在顺序表中，逻辑上相邻的两个数据元素，在物理上也是相邻的。
（2）在访问线性表时，可以利用公式，快速地计算出任何一个数据元素的存储地址。因此，访问每个数据元素所花费的时间相等。具有这种特性的存储结构被称为随机存储结构，顺序表便是一种随机存储结构。
在程序设计语言中，一维数组在内存中占用的存储空间是一组连续的存储区域，因此，常常用一维数组来表示顺序表。由于对线性表可进行插入、删除等操作，所以，线性表的长度是可变的，因此在定义数组大小时，要考虑到线性表的长度，数组的容量需满足最大长度的线性表。
在C语言中，实现线性表的顺序存储结构的类型定义如下：
#define ListSize 100 /* 假定顺序表的最大容量可存储100数据元素 */
typedef int DataType; /* 数据元素的类型设为整型 */
typedef struct {
DataType data[ListSize]; /* 存放顺序表的数组 */
int Length; /* 存储顺序表数据元素的个数，即顺序表的长度 */
} SeqList;
从以上说明可知，顺序表是一个记录类型结构。包括了两个域：数据域data，表示线性表中数据元素所占用的存储空间；长度域Length，表示当前线性表的长度。值得注意的是，C语言中数组的下标从0开始，在本书的部分章节中，为了叙述上的方便，下标为0的单元不予利用。DataType为线性表中数据元素的类型，它既可以是原子类型如字符型、整型、实型，也可以是用户自定义类型。
2.2.2 顺序表的基本运算
我们已经在线性表的逻辑结构上定义了几种基本运算。在线性表的顺序存储结构上，我们
仅讨论插入、查和删除等运算的实现。其他运算较简单，读者可以自己设计实现。
1. 插入运算
线性表的插入是指在具有n个元素的线性表的第i(1≤i≤n+1)个位置上插入一个值为 x 的新元素，插入后顺序表的长度为 n+1。
在顺序表上完成插入元素的操作步骤如下：
（1）从第n个元素开始，一直到第i个元素，依次向后移动一个位置，空出第i个元素的位置；
（2）将x置入空出的第i个位置；
（3）顺序表长度加1。
在设计算法时注意以下问题：
（1）检查顺序表是否已存满数据元素，若满则产生溢出错误。
（2）检查插入位置的有效性，这里 i 的有效范围是：1≤i≤n+1，其中 n 为顺序表的长度。
（3）注意数据的移动方向，从最后一个元素开始依次向后移动一个位置，直到第i个元素为止。
插入算法的时间复杂度分析：
顺序表上的插入运算，时间主要消耗在数据的移动上，在第i个位置上插入x，从ai到an都要向后移动一个位置，共需要移动n－i＋1个元素，而i的取值范围为：1≤i≤n+1，即有n＋1个位置可以插入。设在第i个位置插入一个新元素的概率相等时（包括在an之后），则在插入操作中数据元素的平均移动次数为：
上式表明，在顺序表中插入一个新元素，平均要移动表中一半的数据元素，时间复杂度为Ｏ(n)。
2. 按值查运算
顺序表的查运算是指，对于给定的数据元素的值x，判定顺序表中是否有值与 x 相同的数据元素，若有，则返回其在线性表中的位序，若无，则返回表示查失败的标志。如果在顺序表中存在多个值为x的数据元素，则返回首次到的数据元素的位序。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议