《第3章 链接表》由会员分享，可在线阅读，更多相关《第3章 链接表（60页珍藏版）》请在金锄头文库上搜索。
1、 主要内容 普通高等教育 十一五 国家级规划教材 第3章链接表 3 1链表3 2链栈3 3链队列 返回目录 3 4字符串的链式存储3 5链表应用举例 3 1链表 3 1 1单链表3 1 2循环链表作业 线性表的顺序存储的特点是用物理位置上的邻接关系来表示结点间的逻辑关系 这一特点使我们可以随机存取表中的任一结点 但它也使得插入和删除操作会移动大量的结点 为避免大量结点的移动 本节将介绍线性表的另一种存储方法 链式存储结构 并将这种用链式方式存储的线性表简称为链表 LinkedList 概述 从实现角度 动态链表 静态链表从链接方式角度 单链表 循环链表 双链表 链表的分类 链接存储是最常用的存
2、储方法之一 它不仅可以用来表示线性表 而且可以用来表示各种非线的数据结构 链表是用一组不连续的存储单元来存放线性表中的数据 因此链表中结点的逻辑次序和物理次序不一定相同 因此 在存储每个数据元素值的同时 还要存储指示其后继结点的地址信息 这两部分信息组成的存储映象称为结点 单链表 单链表又称为线性链表 是线性表的一种最简单的链式存储结构 在单链表中的每一个结点都包含两部分内容 存放每一个数据元素本身的数据信息的数据域和存放其直接后继存储位置的指针域 地址域 单链表中结点的结构如下 数据域 指针域 例线性表 zhao qian sun li zhou wu zheng wang 43 13 1
3、NULL 37 7 19 25 头指针 头结点 在单链表第一个结点前附设一个结点叫 头结点指针域为空 表示线性表为空 3 1 1单链表 typedefstructnode datatypedata structnode next linklist 1 单链表的定义和存储结构 定义 一个链表由n个结点组成 每个结点中有一个存储数据的值域和一个存储另一个结点地址的指针域 由于链表的每个结点只有一个链域 故将这种链表称为单链表 通常用头指针head来标识一个单链表的开始头结点 表的第一个结点的data域不存数据空表 head next NULL 也可用 表示空NULL 存储空间动态分配 p mall
4、oc sizeof linklist 释放p所指的结点 free p 单链表的链式存储结构示意图 2 单链表的基本操作 1 建立单链表方法一 头插法建表该方法从一个空表开始 重复读入数据 生成新结点 将读入数据存放到新结点的数据域中 然后将新结点插入到当前链表的表头上 直到读入结束标志为止 a b c d 在线性表la中存放数据 5 4 8 6 时间复杂度为O n 具体算法如下 linklist creatlistbefore datatyped linklist p s head head malloc sizeof linklist head next NULL p head printf
5、 pleaseinputthecharacter enter return rewind stdin scanf c 2 单链表的基本操作 1 建立单链表方法二 从表尾到表头逆向建立 头插法建立链表虽然算法简单 但生成的链表中结点的次序和输入的顺序相反 若希望二者次序一致 可采用尾插法建表 该方法是将新结点插入到当前链表的表尾上 为此必须增加一个尾指针r 使其始终指向当前链表的尾结点 a b c linklist creatlistafter datatyped linklist p s head head malloc sizeof linklist head next NULL p hea
6、d printf pleaseinputthecharacter enter return rewind stdin scanf c 2 插入运算后插操作 x s next p next p next s S malloc sizeof linklist 前插操作 x s next p q next s S malloc sizeof linklist 在单链表L的第i个元素之前插入一个元素x 实现思想 1 找到第i 1个元素 2 在i 1个元素之后插入x head 时间复杂度为O n voidinsert linklist head inti datatypex linklist p s i
7、ntj 1 p head while p 单链表中插入元素示意图 p 单链表中插入元素示意图 s data x s next p next p next s 3 按值查找 算法思路 从链表的第一个元素结点起 判断当前结点其值是否等于x 若是 返回该结点的地址 否则继续向后查找 直到链表结束为止 找不到时返回空 时间复杂度为O n linklist search head x linklist head datatypex linklist p p head next while p NULL 查找运算 4 删除运算 p next p next next 删除运算方法一 在指定位置进行删除 vo
8、iddelete1 linklist head inti intj 1 linklist q p p head while jnext j if p NULL printf 位置参数不正确 n else q p next q指向要删除的结点 p next q next 将p之后的结点删除 free q 删除单链表的第i个元素实现思想 找到第i 1个元素删除第i个元素 算法演示 时间复杂性为O n p q ai 1 ai ai 1 p next q next Free q 删除运算方法二 根据所给条件找到位置再进行删除 voiddelete head x linklist head dataty
9、pex linklist p s p head while p next NULL 3 1 2循环链表 1 循环单链表 对于单链表而言 最后一个结点的指针域是空指针 如果将该链表头结点地址存于该指针域 则使得链表头尾结点相连 就构成了循环单链表 空表 非空表 2 循环双向链表 结点 空表 非空表 循环双向链表 将最后一个结点的空指针域 next域 用来保存头结点地址 而用头结点的prior域保存最后一个结点的地址 用这种结点组成的链表称为循环双向链表 3 静态链表 对于某些高级语言若没有指针类型 就不能动态生成结点 此时也可以借助一维数组来描述线性链表 defineMAX链表的最大长度type
10、defstruct datatypedata intnext snode 结点类型 snodesl MAX 该数组的定义如下 静态链表 数组sl就表示一种链表 该链表的结点中也有数据域data和指针域next 与前面所讲的链表中的指针不同的是 这里的指针是结点的相对地址 数组的下标 称之为静态指针 这种链表就称之为静态链表 空指针用0表示 而sl next 0 中存放的是第一个结点的起始地址 静态链表如图所示 作业 1 简述链表的定义和链表的分类 2 做教材习题中的以下题目 单项选择题 1 2 3 8 9 10 填空题 1 2 3 5 6 7 9 10 应用题 1 3 试写一算法求带头结点的单
11、链表L的长度 4 已知带头结点的动态单链表L中的结点是按整数值递增排列的 试写一算法将值为x的结点插人表中 使L仍然有序 5 试写一算法对带头结点的单链表实现就地逆置 3 2链栈 1 链栈的定义链栈 用链式存储结构实现的栈 只允许在表头进行插入和删除运算的单链表 栈顶指针 单链表的头指针 链栈的类型定义如下 typedefstructnode datatypedata structnode next linkstack linkstackhs hs为链栈栈顶指针 2 链栈的运算 进栈 进栈的算法 voidpush linkstackhs datatypex linkstacks s mallo
12、c sizeof linkstack s data x s next hs hs s hs s x an 1 hs 出栈 voidpop linkstackhs datatype x linkstackp if hs NULL printf 栈空 else x hs data p hs hs hs next free p an hs d an 1 X d p hs 作业 1 简述链栈的定义 2 做教材习题中的以下题目 单项选择题 4 6 填空题 4 应用题 2 3 3链队列 1 链队列的定义链队列 链式存储的队列 只允许在表尾进行插入和在表头进行删除运算的单链表 头指针 front尾指针 re
13、ar typedefstructnode datatypedata structnode next linkqueue typedefstruct linkqueue front rear lqueue lqueue hq hq链队列指针变量 链队列的类型定义如下 2 链队列的运算 voidinsertq lqueue hq datatypex linkqueue p p malloc sizeof linkqueue p data x p next NULL if hq rear NULL hq front p hq rear p else hq rear next p hq rear p
14、an front rear p hp 进队 出队 voiddeleteq lqueue hq datatype x linkqueue p if hq front NULL printf 队空 else p hq front hq front p next x p data free p if hq front NULL hq rear hq front an front rear hp X a1 作业 1 简述链队列的定义 2 做教材习题中的以下题目 单项选择题 5 7 填空题 8 应用题 3 3 4字符串的链式存储 typedefstructnode charch structnode n
15、ext linkstring 由于串结构的特殊性 结构中的每个数据元素是一个字符 所以在用链表存储字符串时 存在一个结点大小的问题 每个结点可以存放一个字符 也可以存放多个字符 块链结构 下图是结点大小为4的链表 由于字符串的长度不一定是结点大小的整倍数 则链表的最后一个结点不一定会占满 此时补上 或其他非串字符值 通常 不属于串的字符集 是一个特殊的符号 尾指针tail 指示最后一个结点len 存储串的实际长度 defineMAX结点块的最大值typedefstructnode charch MAX structnode next cnode typedefstruct intlen cno
16、de head tail lstring 块链结构的结点描述如下 结点存储密度 结点存储密度 结点大小选择的是否合理 直接影响存储空间的利用率 串所占存储空间 结点实际分配的存储空间 作业 1 1个字符串用链式结构存储有几种方式 2 做教材习题中的以下题目 应用题 5 3 5链表应用举例 例3 1试写一算法 求带结点的单链表的长度 单链表的长度是指单链表中结点的个数 求单链表表长的基本操作是移动指针 将指针从表头移动到表尾 在指针移动过程中 累计扫描过的结点数即为表长 由此需要设一个指针p 顺链向后移动 还要设一个整型变量j 作为计数器 指针p的初始值指向头结点 计数器j的初始值为0 intLength linkList linklist l linklist p intj 0 p l p指向头结点 while p next p p next j p所指的是第j个结点 returnj 3 5链表应用举例 例3 2有一单链表l 其头结点指针head 编写一算法将其倒置 即实现如下图的操作 a 为倒置前 b 为倒置后 a b 算法思路 依次取原链表中的每个结点 将其作为第一个结点插入到新链
