首页计算机计算机基础程序设计基础与数据结构 04 第三章 线性表.pptx

04 第三章 线性表.pptx

页数:29页文件大小:177.9 KB来源: 程序设计基础与数据结构ppt课件

本课件系统讲解线性表这一最基础的数据结构:先给出线性表的定义、长度与关键字等概念及十项基本操作,再分别展开顺序存储与链式存储两种实现方式,其中链式部分覆盖单链表与头结点、双向链表、循环链表,最后介绍特殊的线性表——串的存储结构与运算,并以工资表管理系统作为综合应用示例。

第三章章节目录页,列出线性表定义、顺序存储、链式存储、串、应用与小结六节
线性表定义页,把线性表描述为同类型数据元素的有限序列,并说明前驱与后继关系
线性表长度与关键字页,说明元素个数即表长、空表、元素位置与结点中的数据域
查看本课件的文字版(共 29 页,供检索与复制)

第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页:线性表的基本操作

线性表的基本操作:

  1. 初始化:构造一张空的线性表。
  2. 销毁:销毁一张已存在的线性表。
  3. 求长度:求出线性表中数据元素的个数。
  4. 定位:找出线性表中满足特定条件的元素的位置。
  5. 插入元素:在线性表中的特定位置之前插入新的数据元素。
  6. 删除元素:删除线性表中特定位置的数据元素。
  7. 取元素:根据数据元素的位置,从线性表中取出该元素。
  8. 求前驱:求出线性表中特定数据元素的前驱。
  9. 求后继:求出线性表中特定数据元素的后继。
  10. 遍历:顺序访问线性表中的每个数据元素。

第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页:顺序表的操作实现

顺序表的具体操作实现:

  1. 初始化
  2. 销毁
  3. 求长度
  4. 定位
  5. 插入元素
  6. 删除元素
  7. 取元素
  8. 求前驱
  9. 求后继
  10. 遍历

第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页:线性链表的操作实现

线性链表的具体操作实现:

  1. 初始化
  2. 销毁
  3. 求长度
  4. 定位
  5. 插入元素
  6. 删除元素
  7. 取元素
  8. 求前驱
  9. 求后继
  10. 遍历

第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页:双向链表的操作实现

双向链表的具体操作实现:

  1. 初始化
  2. 销毁
  3. 求长度
  4. 定位
  5. 插入元素
  6. 删除元素
  7. 取元素
  8. 求前驱
  9. 求后继
  10. 遍历

第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页:串的基本操作

串的基本操作:

  1. 初始化:生成一个新串。
  2. 复制:把一个串的值赋给另一个串。
  3. 求串长:求串的长度。
  4. 求子串:求串中从特定位置开始的子串。
  5. 比较:比较两个串的值是否相等。
  6. 联接:将两个串合并成一个串。
  7. 定位:求子串在主串中的位置。
  8. 替换:将串中的某个子串替换成另一个子串。
  9. 插入:在串的某个特定位置插入一个串。
  10. 删除:删除串中从特定位置开始的子串。

第23页:串的顺序存储

3.4.2 串的存储及运算——顺序存储:把串中的字符顺序地存储在一组连续的存储单元中,分为紧缩格式与非紧缩格式两种。

  • 紧缩格式存储可以节省空间,但对串中的字符操作比较复杂。
  • 非紧缩格式的存储较浪费空间,但操作相对比较方便。
  • 在C语言中,串只有紧缩格式,采用字符数组的方式来存放字符串。(图3-4-1 紧缩格式存储示例、图3-4-2 非紧缩格式存储示例,示例串为 Data Structure in C)

第24页:串的顺序存储操作

顺序存储结构上串的基本操作:

  1. 初始化:生成一个新串。
  2. 复制:把一个串的值赋给另一个串。
  3. 求串长:求串的长度。
  4. 求子串:求串中从特定位置开始的子串。
  5. 比较:比较两个串的值是否相等。
  6. 联接:将两个串合并成一个串。
  7. 定位:求子串在主串中的位置。
  8. 替换:将串中的某个子串替换成另一个子串。
  9. 插入:在串的某个特定位置插入一个串。
  10. 删除:删除串中从特定位置开始的子串。

第25页:链串与块链存储

顺序存储的缺点:需要事先确定串的最大容量;不便于进行删除、插入等会引起大量字符移动的操作。

链式存储:

  • 存储的基本单位是结点,每个结点含一个数据域和一个指针域,这种存储形式称为链串。
  • 在链串中,每个结点既可以存放一个字符,也可以存放多个字符;把结点中存储字符的个数称为结点的大小。
  • 图中给出结点大小为4与结点大小为1两种块链存储形态(示例串 Data Structure in C)。

第26页:块链存储的操作

链式存储(续):

  • 块链存储结构的定义
  • 某些基本操作的实现:替换、插入、删除

第27页:串的应用:文本编辑

3.4.3 串的应用:文本编辑的例子——文本的查找、替换、插入与删除都可以归结为串上的基本运算。

第28页:工资表管理系统

3.5 线性表的应用——简单的工资表管理系统

  • 主要功能:
  • 1.生成一个新的工资表
  • 2.查找某个职工的信息
  • 3.增加一个职工信息
  • 4.删除一个职工信息
  • 5.按要求统计工资表,如统计职工总数、工资总数、奖金总数等
  • 打印输出整个工资表

第29页:第三章小结

3.6 小结

  • 线性表是最常用也是最基本的数据结构。
  • 线性表的顺序存储结构与链式存储结构。
  • 这两种存储结构上线性表的各种基本操作算法。
  • 特殊的线性表——串:两种存储结构及其上的运算,以及线性表的实例。
顶部目录