第1页:第三章 线性表
第三章 线性表
- 3.1 线性表的定义
- 3.2 线性表的顺序存贮及其运算
- 3.3 线性表的链式存储结构及其运算
- 3.4 串
- 3.5 线性表的应用
- 3.6 小结
第2页:线性表的定义
3.1 线性表的定义
- 线性表是由 n 个数据元素所构成的一个有限序列;
- 表中的每一个数据元素都具有相同的数据类型,可记为(a1, a2, ... ai, ... an-1, an);
- 其中的每个 ai 就是一个数据元素,也称之为结点;
- a1 为表中的第一个结点,an 为表中的最后一个结点;
- 结点与结点之间具有一定的前后次序关系:除第一个结点外,每一个结点都有一个前驱;除最后一个结点外,每一个结点都有一个后继。
第3页:线性表的长度与关键字
3.1 线性表的定义
- 线性表的长度
- 线性表中数据元素的个数 n 就是线性表的长度,当 n = 0 时,该线性表就是一张空表。
- 位置
- 每个数据元素都有确定的位置,即该元素在表中的序号,如结点 ai 的位置就是 i。
- 数据域
- 组成结点的数据项称为结点中的数据域。
- 关键字
- 可以唯一地标识结点的数据域,称为结点的关键字。
第4页:线性表的基本操作
线性表的基本操作:
- 初始化:构造一张空的线性表。
- 销毁:销毁一张已存在的线性表。
- 求长度:求出线性表中数据元素的个数。
- 定位:找出线性表中满足特定条件的元素的位置。
- 插入元素:在线性表中的特定位置之前插入新的数据元素。
- 删除元素:删除线性表中特定位置的数据元素。
- 取元素:根据数据元素的位置,从线性表中取出该元素。
- 求前驱:求出线性表中特定数据元素的前驱。
- 求后继:求出线性表中特定数据元素的后继。
- 遍历:顺序访问线性表中的每个数据元素。
第5页:线性表的顺序存储
3.2 线性表的顺序存贮及其运算
- 顺序表
- 表中的结点依次存储在一组地址连续的存储单元中,结点的逻辑顺序与它在存储器中的物理顺序一致。
表中第 i 个结点的存储地址为:Loc(ai) = Loc(a1) + (i-1) × m(图3-2-1 顺序表的存储结构示意图)。
第6页:顺序表的类型定义
顺序表的特性:只要知道了表中第一个结点的存储位置,就可以得到表中任意结点的存储位置,通常采用一维数组来表示顺序表的存储结构。
typedef struct slist_st { ELEMENT *element; int size; int length; } SLIST;其中 ELEMENT 是顺序表中结点的数据类型,可定义为一个结构类型。
第7页:顺序表的操作实现
顺序表的具体操作实现:
- 初始化
- 销毁
- 求长度
- 定位
- 插入元素
- 删除元素
- 取元素
- 求前驱
- 求后继
- 遍历
第8页:链式存储结构的引入
顺序存储的缺点:
- 占据较大的连续存储空间,不利于零碎内存空间的利用。
- 在数据元素的插入和删除时,为了保证逻辑关系与物理位置的对应,必须要移动元素。
线性表的链式存储结构:线性链表、双向链表、循环链表。
第9页:线性链表的结点结构
3.3.1 线性链表
- 数据元素的逻辑关系是通过指针来表示的;
- 结点除了要有存储数据元素的数据域外,还要有存储指示其与其它元素的逻辑关系的指针。
结点的一般形式为:data | next,尾结点的指针域为空(图3-3-1 线性链表的结构)。
第10页:线性链表的存储结构定义
线性链表的存储结构定义:
typedef struct element_st { int data; ... } ELEMENT; struct node_st { ELEMENT element; struct node_st *next; } NODE; NODE *listhead; 第11页:带头结点的单链表
头结点的引入:
- 在线性链表的第一个结点之前附设一个结点,称为头结点,其存储结构与链表中的结点结构相同;
- 它的指针域中存储指向线性表中真正的第一个结点的指针,链表的头指针就指向该头结点;
- 判断线性表是否为空的标志要看头结点的指针域是否为空。
头结点的作用:使对第一个结点的操作方法与其它结点的操作方法一样;使算法的实现更加简洁。(图3-3-2 带头结点的线性链表、图3-3-3 空链表)
第12页:线性链表的操作实现
线性链表的具体操作实现:
- 初始化
- 销毁
- 求长度
- 定位
- 插入元素
- 删除元素
- 取元素
- 求前驱
- 求后继
- 遍历
第13页:双向链表的结点结构
3.3.2 双向链表
- 在单链表中,寻找一个结点的前驱需要从表头开始进行查找,不太方便。
- 在双向链表中,每个结点包含三个域:一个数据域和两个指针域,其中一个指针域指向结点的后继,另一个指向它的前驱。
结点结构为 forward | element | backward(图3-3-6 双向链表中结点的结构)。
第14页:双向链表的存储结构定义
双向链表的存储结构定义:
typedef struct node_st { ELEMENT element; struct node_st *forward; struct node_st *backward; } NODE;特点:p->backward->forward = p->forward->backward = p,进行插入与删除的操作比较方便。
说明:原文结构定义中 backward 前缺少类型修饰,此处按前后文语义补为 struct node_st *。
第15页:双向链表的操作实现
双向链表的具体操作实现:
- 初始化
- 销毁
- 求长度
- 定位
- 插入元素
- 删除元素
- 取元素
- 求前驱
- 求后继
- 遍历
第16页:双向链表排序示例
例子:利用双向链表对无序的整数数据集合进行排序
- 假设:无序的数据用数组进行存储,如果在数组中直接进行排序,必然需要在数组中进行大量的元素移动操作,既不方便,效率又低。
- 利用双向链表的特性,从空表开始,依次将数组中的数据元素按大小有序地插入到双向链表中,等到包含全部数组元素的双向链表建成时,实际就是完成了对无序数据的排序过程。
- 最后,再把链表中的数据依次存回到数组中,就得到了一个有序的数据集合。
第17页:循环链表
3.3.3 循环链表
- 在单链表中,只有单向指针,从某个结点出发只能查找其后的那些结点;如果要查找它前面的结点,就必须从表头结点开始搜索。
- 在双向链表中,每个结点要求有两个指针域,需要更多的存储空间。
- 循环链表在不增加存储空间的同时,可以实现从表中任意结点出发访问表中其它所有结点,不必借助头指针。
- 循环链表就是将单链表最后那个结点的后继指针改为指向其表头。
第18页:循环链表的结构示意
循环链表的结构:带头结点的循环链表中,尾结点 an 的后继指针回指头结点;空的循环链表中,头结点的后继指针指向自身。(图3-3-9 带头结点的循环链表、图3-3-10 空的循环链表)
第19页:循环链表的运算与双向循环链表
循环链表的运算:
- 判别空表算法
- 例子:两个循环链表的合并
- 双向循环链表(图3-3-12 双向循环链表的示例:(a) 空的双向循环链表、(b) 带头结点的双向循环链表)
第20页:串的概念引入
3.4 串(字符串)
- 把线性表中结点的内容限定为一个字符,那么,这样的线性表就是串,即字符串。
- 串的基本概念
- 串的存储及运算
- 串的应用
第21页:串的基本概念
3.4.1 串的基本概念
- 串是由零个或多个字符组成的有限序列,记作 string = “a1a2.....an”(n ≥ 0);string 是串的名,双引号括起来的字符序列为串的值,双引号本身不属于串。
- 串中包含的字符个数 n 称为串的长度;长度为零的串称为空串,记为 “φ”。
- 空格串 “ ” 是由一个空格字符组成的串,它的长度为1。
- 一个串中任意个连续的字符组成的子序列称为该串的子串,包含该子串的串称为主串。
- 字符在串中的位置指该字符在序列中的序号;子串在主串中的位置指该子串的第一个字符在主串中的位置。
- 当两个串中的字符序列一一对应相等时,称这两个串相等。
第22页:串的基本操作
串的基本操作:
- 初始化:生成一个新串。
- 复制:把一个串的值赋给另一个串。
- 求串长:求串的长度。
- 求子串:求串中从特定位置开始的子串。
- 比较:比较两个串的值是否相等。
- 联接:将两个串合并成一个串。
- 定位:求子串在主串中的位置。
- 替换:将串中的某个子串替换成另一个子串。
- 插入:在串的某个特定位置插入一个串。
- 删除:删除串中从特定位置开始的子串。
第23页:串的顺序存储
3.4.2 串的存储及运算——顺序存储:把串中的字符顺序地存储在一组连续的存储单元中,分为紧缩格式与非紧缩格式两种。
- 紧缩格式存储可以节省空间,但对串中的字符操作比较复杂。
- 非紧缩格式的存储较浪费空间,但操作相对比较方便。
- 在C语言中,串只有紧缩格式,采用字符数组的方式来存放字符串。(图3-4-1 紧缩格式存储示例、图3-4-2 非紧缩格式存储示例,示例串为 Data Structure in C)
第24页:串的顺序存储操作
顺序存储结构上串的基本操作:
- 初始化:生成一个新串。
- 复制:把一个串的值赋给另一个串。
- 求串长:求串的长度。
- 求子串:求串中从特定位置开始的子串。
- 比较:比较两个串的值是否相等。
- 联接:将两个串合并成一个串。
- 定位:求子串在主串中的位置。
- 替换:将串中的某个子串替换成另一个子串。
- 插入:在串的某个特定位置插入一个串。
- 删除:删除串中从特定位置开始的子串。
第25页:链串与块链存储
顺序存储的缺点:需要事先确定串的最大容量;不便于进行删除、插入等会引起大量字符移动的操作。
链式存储:
- 存储的基本单位是结点,每个结点含一个数据域和一个指针域,这种存储形式称为链串。
- 在链串中,每个结点既可以存放一个字符,也可以存放多个字符;把结点中存储字符的个数称为结点的大小。
- 图中给出结点大小为4与结点大小为1两种块链存储形态(示例串 Data Structure in C)。
第26页:块链存储的操作
链式存储(续):
- 块链存储结构的定义
- 某些基本操作的实现:替换、插入、删除
第27页:串的应用:文本编辑
3.4.3 串的应用:文本编辑的例子——文本的查找、替换、插入与删除都可以归结为串上的基本运算。
第28页:工资表管理系统
3.5 线性表的应用——简单的工资表管理系统
- 主要功能:
- 1.生成一个新的工资表
- 2.查找某个职工的信息
- 3.增加一个职工信息
- 4.删除一个职工信息
- 5.按要求统计工资表,如统计职工总数、工资总数、奖金总数等
- 打印输出整个工资表
第29页:第三章小结
3.6 小结
- 线性表是最常用也是最基本的数据结构。
- 线性表的顺序存储结构与链式存储结构。
- 这两种存储结构上线性表的各种基本操作算法。
- 特殊的线性表——串:两种存储结构及其上的运算,以及线性表的实例。