实用数据结构(C++描述)(第二版)第3章.ppt

第3章线性链表 3 1线性链表的基本概念3 2线性链表的基本运算3 3循环链表 3 1线性链表的基本概念 3 1 1线性表顺序存储的问题3 1 2线性链表3 1 3带链的栈3 1 4带链的队列 第3章线性链表 4 3 1 1线性表顺序存储的问题顺序存储结构是线性表中最简单 最常用的存储方式 顺序表中任意数据元素的存储地址可由公式直接导出 因此顺序表是随机存取的存储结构 也就是取元素操作和定位操作可以直接实现的一种存储结构 高级程序设计语言提供的数组数据类型可直接定义顺序表 使顺序表的程序设计十分方便 其主要的优点主要有 1 无须为表示结点间的逻辑关系而增加额外的存储空间 2 可以方便地随机存取表中的任一结点 第3章线性链表 5 但是 顺序存储结构也有一些不利之处 主要是 1 顺序存储结构要求占用连续的存储空间 线性表中数据元素的最大个数需要预先设定 这就使得高级程序设计语言编译系统需要预先分配相应的存储空间 即需要静态分配 当进行静态分配时 如果表长变化较大 设定最大表长就比较困难 如果按可能达到的最大长度预先分配表空间 有可能造成部分内存空间的浪费 但若对预先分配的空间不够大 如果进行插入操作 就可能造成溢出 第3章线性链表 6 2 为了保持顺序表中数据元素的顺序 在插入操作和删除操作时需要移动大量数据 对一个有n个数据元素的顺序表 插入操作和删除操作需移动数据元素的平均次数约为n 2 这对于有些需要频繁进行插入和删除操作的问题 以及每个数据元素所占字节较大的问题来说 将导致系统的运行速度难以提高 第3章线性链表 7 由于线性表的顺序存储结构的特点是逻辑关系上相临的两个元素在物理位置上也相邻 因此可以随机地 快速地存取表中任一个元素 然而 这种存储结构对插入或删除操作是非常困难的 往往要引起大量的数据移动 而且表的容量扩充时也比较繁琐 为了解决顺序表所遇到的这些困难 本节将讨论线性表的另一种表示方法 链式存储结构 由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻 因此它没有顺序存储结构所存在的上述缺点 第3章线性链表 8 在链式存储方式中 要求每个结点由两部分组成 一部分用于存放数据元素值 称为数据域 另一部分用于存放指针 称为指针域 其中指针用于指向该结点的前一个或后一个结点 即前件或后件 在链式存储方式中 存储数据结构的存储空间可以不连续 各数据接点的存储顺序与数据元素之间的逻辑关系可以不一致 而数据元素之间的逻辑关系是由指针域来确定的 链式存储方式既可用于线性链表 也可用于表示非线性链表 第3章线性链表 9 3 1 2线性链表 线性表的链式存储结构称为线性链表 在线性链表中 用一个专门的指针HEAD指向线性链表中第一个元素的结点 既存放线性表中第一个元素的存储结点的序号 线性表中最后一个元素没有后件 最后一个结点的指针域为空 用NULL或0表示 时 表示链表终止 举例说明线性链表的存储结构 a1 a2 a3 a4 a5 算法 依次输出线性链表中的各结点值输入 线性链表的存储空间V 1 m NEXT 1 m 线性链表的头指针HEAD 输出 依次输出线性链表中各结点的值 PROCEDUREPRTLL HEAD 1 j HEAD2 WHILE j 0 DO3 OUTPUTV j j NEXT j 4 RETURN c语言中 定义链表结点结构的一般形式如下 struct结构体名 数据成员表 struct结构体名 指针变量名 例如structnode charname 10 数据域 charsex 数据域 structnode next 指针域 include stdlib h malloc函数需要包含头文件stdlib h structnode 定义结点类型 intd 数据域 structnode next 指针域 main structnode p 定义该类型的指针变量p p structnode malloc sizeof structnode 申请分配结点存储空间 free p 释放结点存储空间 include stdlib h include stdio h structnode intd structnode next main intx structnode head p q head NULL q NULL scanf d x 定义结点类型 置链表空 输入一个正整数 while x 0 p structnode malloc sizeof structnode p d x p next NULL if head NULL head p elseq next p q p scanf d x 如果输入值大于0 申请一个结点 设置当前结点的数据域和指针域 若链表空 则将头指针指向当前结点p 将当前结点链接在最后 置当前结点为链表最后一个结点 第3章线性链表 18 p head while p NULL printf 5d p d q p p p next free q printf n 打印当前结点中的数据 删除当前结点 释放该结点空间 上面讨论的线性链表又称为线性单链表 在这种链表中 每一个结点只有一个指针域 由这个指针只能找到后件结点 但不能找到前件接点 因此 在这种线性链表中 只能顺指针向链尾方向进行扫描 这样 当由一个结点出发后 为了找出它的前件 必须从头指针开始重新寻找 为了弥补线性单链表这个缺点 对线性链表中的每个结点设置两个指针 一个称为左指 Llink 用于指向前件结点 另一个一个称为右指针 Rlink 用于指向后件结点 这样的线性链表称为双向链表 3 1 3带链的栈栈也是线性表 也可以用链式存储结构 下面是栈在链式存储时的逻辑状态示意图 在实际应用中 带链的栈可以用来收集计算机存储空间中所有空闲的存储结点 这种带链的栈称为可利用栈 可利用栈及其运算 算法 将结点送回可利用栈输入 可利用栈栈顶指针TOP 默认 送回可利用栈的结点序号p 输出 结点p入栈后的可利用栈栈顶指针TOP 默认 PROCEDUREDISPOSE p NEXT p TOP TOP pRETURN 第3章线性链表 23 算法 从可利用栈取得一个结点输入 可利用栈的栈顶指针TOP 默认 输出 退栈后的可利用栈栈顶指针TOP 默认 存放取得结点序号的变量p PROCEDURENEW p p TOP TOP NEXT TOP RETURN 算法 带链栈的入栈运算输入 带链栈的栈顶指针top 入栈的元素值x 输出 元素x入栈后的带链栈栈顶指针top PROCEDUREPUSHLL top x 1 NEW p 从可利用栈取得一个新结点 2 V p x 置新结点数据域 3 NEXT p top 置新结点指针域 4 top p 改变栈顶指针 5 RETURN include stdlib h structnode 定义结点类型 ETd 数据元素类型 structnode next pushll top x ETx structnode top structnode p p structnode malloc sizeof structnode p d x p next top 置新结点的数据域与指针域 top p 改变栈顶指针 return 算法 带链栈的退栈运算输入 带链栈的栈顶指针top 输出 退栈后的带链栈栈顶指针top 存放退出结点元素值的变量y PROCEDUREPOPLL top y y V top 取出栈顶元素值 p toptop NEXT p 改变栈顶指针 DISPOSE p 被删除结点送回可利用栈 RETURN include stdlib h structnode 定义结点类型 ETd 数据元素类型 structnode next popll top y ETy structnode top structnode p y top d 取出栈顶元素值 p top top p next 改变栈顶指针 free p return 释放被删除结点后返回 3 1 4带链的队列 算法 带链队列的入队运算输入 带链队列的队尾指针rear 入队的新元素x 输出 元素x入队后的带链队列队尾指针rear PROCEDUREADDLL rear x NEW p 从可利用栈取得一个新结点p V p x 置新结点的数据域 NEXT p 0 置新结点的指针为空 NEXT rear p 最后一个结点的指针指向新结点 rear p 改变队尾指针 RETURN include stdlib h structnode 定义结点类型 ETd 数据元素类型 structnode next addll rear x ETx structnode rear structnode p p structnode malloc sizeof structnode p d x p next NULL 置新结点的数据域与指针域 rear next p 置最后一个结点的指针指向新结点 rear p 改变队尾指针 return 算法 带链队列的退队运算输入 带链队列的排头指针front 输出 退队后的带链队列排头指针front 存放退出结点值的变量y PROCEDUREDELLL front y y V front 取出排头元素值 p frontfront NEXT front 改变排头指针 DISPOSE p 释放删除的结点 RETURN include stdlib h structnode 定义结点类型 ETd 数据元素类型 structnode next delll front y ETy structnode front structnode p y front d 取出排头元素值 p front front p next 改变排头指针 free p 释放被删除结点 return 3 2线性链表的基本运算 3 2 1在线性链表中查找指定元素3 2 2线性链表的插入3 2 3线性链表的删除 第3章线性链表 34 线性链表的运算主要有以下几种 1 在线性链表中包含指定元素的结点之前插入一个新元素 2 在线性链表中删除包含指定元素的结点 3 将两个线性链表按要求合并成一个线性链表 4 将一个线性链表按要求进行分解 5 逆转线性链表 6 复制线性链表 7 线性链表的排序 8 线性链表的查找 3 2 1在线性链表中查找指定元素算法 在非空线性链表中寻找包含元素x的前一个结点p输入 非空线性链表头指针HEAD 被寻找元素x 输出 非空线性链表中包含元素x的前一个结点p PROCEDURELOOKST HEAD x p p HEADWHILE NEXT p 0 and V NEXT p x DOp NEXT p RETURN structnode 定义结点类型 ETd 数据元素类型 structnode next structnode lookst head x ETx structnode head structnode p p head while p next NULL p next d x p p next return p 3 2 2线性链表的插入 线性链表的插入是指在链式存储结构下的线性表中插入一个新元素 为了要在线性链表中插入一个新元素 首先要给该元素分配一个新结点 以便用于存储该元素的值 新结点可以从可利用栈中取得 然后将存放新元素值的结点链接到线性链表中指定的位置 可利用栈与线性链表 1 从可利用栈取得一个结点 设该结点号为p 并置结点p的数据域为插入的元素值b 即V p b 2 在线性链表中寻找包含元素x的前一个结点q 3 将结点p插入到结点q之后 使结点p指向包含元素x的结点 即NEXT p NEXT q 使结点q的指针域内容改为指向结点p 即NEXT q p 算法 线性链表的插入输入 线性链表的头指针HEAD 插入位置处的前一个结点值x 插入的新元素b 输出 插入后的线性链表 PROCEDUREINSLST HEAD x b 1 NEW p 2 V p b3 IF HEAD 0 THEN HEAD p NEXT p 0 RETURN 4 IF V HEAD x THEN NEXT p HEAD HEAD p RETURN 5 LOOKST HEAD x q 6 NEXT p NEXT q NEXT q p7 RETURN include stdlib h structnode 定义结点类型 ETd structnode next inslst head x b ETx b structnode head structnode p q p structnode malloc sizeof structnode p d b 置结点的数据域 if head NULL 链表为空 head p p next NULL return if head d x 在第一个结点前插入 p next head head p return q lookst head x 寻找包含元素x的前一个结点q p next q next q next p 结点p插到结点q之后 return 3 2 3线性链表的删除 线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点 为了在线性链表中删除包含指定元素的结点 首先要在线性链表中找到这个结点 然后将要删除结点放回到可利用栈 可利用栈与线性链表 1 寻找包含元素x的前一个结点q 则包含元素x的结点序号p NEXT q 2 将结点q后的结点p删除 即NEXT q NEXT p 3 将包含元素x的结点p送回可利用栈 算法 线性链表的删除输入 线性链表的头指针HEAD 需删除的元素x 输出 删除后的线性链表 PROCEDUREDELST HEAD x 1 IF HEAD 0 THEN Thisisaemptylist RETURN 2 IF V HEAD x THEN p NEXT HEAD DISPOSE HEAD HEAD p RETURN 3 LOOKST HEAD x q 4 IF NEXT q 0 THEN Nothisnodeinthelist RETURN 5 p NEXT q NEXT q NEXT p 6 DISPOSE p 7 RETURN include stdlib h structnode 定义结点类型 ETd structnode next delst head x ETx structnode head structnode p q if head NULL 链表为空 printf Thisisaemptylist n return if head d x 删除第一个结点 p head next free head head p return q lookst head x 寻找包含元素x的前一个结点q if q next NULL 链表中没有包含元素x的结点 printf Nothisnodeinthelist n return p q next q next p next 删除结点p free p 释放结点p return 3 3循环链表 1 在循环链表中增加了一个表头结点 其数据域为任意或根据需要来设置 指针域指向线性表第一个元素的结点 循环链表的头指针指向表头结点 2 循环链表中最后一个结点的指针域不空 而是指向表头结点 即在循环链表中 所有结点的指针构成了一个环状链 1 在循环链表中 只要指出表中任何一个结点的位置 就可以从它出发访问到表中其他所有的结点 2 空表与非空表的运算统一 算法 在头指针为HEAD的循环链表中寻找包含元素x的前一个结点输入 循环链表的头指针HEAD 被寻找的元素x 输出 循环链表中包含元素x的前一个结点p PROCEDURELOOKCST HEAD x p p HEADWHILE NEXT p HEAD and V NEXT p x DOp NEXT p RETURN include stdlib h structnode 定义结点类型 ETd structnode next structnode lookcst head x ETx structnode head structnode p p head while p next head p next d x p p next return p 算法 在头指针为HEAD的循环链表中包含元素x的结点前插入新元素b输入 循环链表的头指针HEAD 插入位置处的前一个结点值x 插入的新元素b 输出 插入后的循环链表 PROCEDUREINSCST HEAD x b NEW p 从可利用栈取得一个新结点p V p b 置新结点p的数据域 插入的元素值b LOOKCST HEAD x q 寻找循环链表中包含元素x