网站建设服务商是什么,设计网站多少钱,郑州政策最新消息,网站详细页制作目录 #x1f33b;#x1f33b;一、线性表概述1.1 线性表的基本概念1.2 线性表的顺序存储1.2.1 线性表的基本运算在顺序表上的实现1.2.2 顺序表实现算法的分析1.2.3 单链表类型的定义1.2.4 线性表的基本运算在单链表上的实现1.3 其他运算在单链表上的实现1.3.1 建表1.3.2 删除…
目录 一、线性表概述1.1 线性表的基本概念1.2 线性表的顺序存储1.2.1 线性表的基本运算在顺序表上的实现1.2.2 顺序表实现算法的分析1.2.3 单链表类型的定义1.2.4 线性表的基本运算在单链表上的实现1.3 其他运算在单链表上的实现1.3.1 建表1.3.2 删除重复结点1.4 其他链表1.4.1 循环链表1.4.2 双向循环链表1.5 顺序实现与链接实现的比较二、典例练习一、线性表概述
1.1 线性表的基本概念 线性表中结点具有一对一的关系如果结点数不为零则除起始结点没有直接前驱外其他每个结点有且仅有一个直接前驱除终端结点没有直接后继外其他每个结点有且仅有一个直接后继。 线性表基本运算有初始化、求表长、读表元素、定位、插入、删除。 1.2 线性表的顺序存储 线性表的顺序存储逻辑结构相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表一般用数组来表示顺序表如图1-1 所示 图1-1 顺序表示意图 1.2.1 线性表的基本运算在顺序表上的实现
插入 图1-2 顺序表插入元素前、后状况示意图 a插入前b插入前移出空位之后c插入x后 具体算法描述如下 删除 图2-5 顺序表删除元素前、后的状况示意图 a删除前b删除后 具体算法描述如下 定位 定位运算的功能是查找出线性表L中值等于x的结点序号的最小值当找不到值为x的结点时返回结果0。 描述算法如下 1.2.2 顺序表实现算法的分析 插入On删除On定位On 2.3 线性表的链接存储 1.2.3 单链表类型的定义 线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向循环链表其中最简单的是单链表。 单链表的一个结点由两部分组成数据元素和指针。各个结点在内存中的存储位置并不一定连续。链表的结点可以重新链接。 图2-7 结点结构
非空的单链表和空单链表如图所示 图2-8 单链表示例 a非空的单链表b空单链表 我们通常用结构体类型来定义单链表的结点数据类型。 单链表的类型定义如下
Typedef struct node
{DataType data; //数据域struct node * next; //指针域
}Node, *LinkList;【例2-4】学生档案信息链表的类型完整描述如下 则学生档案信息链式存储实现如图2-9所示. 图2-9 学生档案信息表链式存储实现示意图 为了便于运算的实现在单链表的第一个结点之前增设一个类型相同的结点称之为头结点其他结点称为表结点。 图2-10 带头结点的单链表 a带头结点的非空单链表b带头结点的空单链表 1.2.4 线性表的基本运算在单链表上的实现
我们首先来讨论单链表的一些基本运算这是使用单链表的开始。 初始化 初始化的工作是建立一个空表空表由一个头指针和一个头结点组成。求表长 在单链表存储结构中线性表的表长等于单链表中数据元素的结点个数即除了头结点以外的结点的个数即除了头结点以外的结点的个数。图2-9所示为数据为整数的单链表其长度为4. 读表元素 通常给定一个序号i查找线性表的第i个元素。从头指针出发一直往后移动直到第i个结点。 定位 线性表的定位运算就是对给定表元素的值找出这个元素的位置。从头至尾访问链表直至找到需要的结点返回其序号。若未找到返回0。插入重点掌握 单链表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。 插入结点的指针变化 如图2-12所示。 图2-12 单链表上插入结点的指针变化 插入算法描述如下 注意p-nextq-next和q-nextp两条语句的执行顺序不能颠倒。 删除重点掌握 删除运算是给定一个值i将链表中第i个结点从链表中移出并修改相关结点的指针域以维持剩余结点的链接关系。删除结点的指针变化如图2-13所示。 图2-13 单链表上删除结点时的指针变化 单链表的删除运算算法描述如下 注意freep是必不可少的无用结点需要释放它的空间。 1.3 其他运算在单链表上的实现
1.3.1 建表
我们讨论建立含头结点的单链表。 方法一尾插法这个过程分为三部首先建立带头结点的空表其次建立一个新结点然后将新结点链接到头结点之后重复后面两个步骤直到线性表中所有元素链接到单链表中。 代码描述如下 方法中的链接操作如图2-14所示它的时间与元素个数成正比故其时间复杂度为On。 图2-14 建表算法中的表尾链入操作 方法二头插法始终将新增加的结点插入到头结点之后第一个数据结点之前。它的时间复杂度也是On。如图2-15所示。 图 2-15 建表算法中的在表头链入操作
代码描述如下 1.3.2 删除重复结点 1.4 其他链表
1.4.1 循环链表 在单链表中如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中从任一结点出发能够扫描整个链表。 图 2-15 循环链表示意图 a带头结点的非空循环链表b带头结点的空循环链表c设立尾指针的非空循环链表d设立尾指针的空循环链表 1.4.2 双向循环链表
双向循环链表的结点结构 如图2-18所示 图2-18 双向循环链表结点结构 双向循环链表示意图如图2-19所示prior与next类型相同它指向直接前驱结点。头结点的prior指向最后一个结点最后一个结点的next指向头结点。 图2-19 双向循环链表示意图 a空表b非空表 删除 在单链表中删除结点时需要用一个指针指向待删除结点的前驱结点在双循环链表中设p指向待删除结点删除*p可通过下述语句完成执行效果如图2-18所示。 1p-prior-nextp-next; //p前驱结点的后链指向p的后继结点2p-next-priorp-prior; //p后继结点的前链指向p的前驱结点3freep; //释放*p的空间 1、2这两个语句的执行顺序可以颠倒。 图 2-20 双向循环链表上结点的删除 a删除结点*p之前b删除结点*p后 插入 在p所指结点的后面插入一个新结点*t需要修改四个指针 1t-priorp;2t-nextp-next;3p-next-priort;4p-nextt; 插入操作过程如图2-21所示注意这些语句之间的顺序。 图 2-21 双向循环链表上结点的插入 a插入前b插入后 1.5 顺序实现与链接实现的比较 二、典例练习 【例题单选题】在表长为n的顺序表上做删除运算其平均时间复杂度为 。 A.O1 B.On C.Onlog2n D.On2 『正确答案』B 『答案解析』在顺序表上做删除运算需要后续结点向前移动一个位置以保证顺序表的连续。 【例题单选题】在表长为n的顺序表上做插入运算平均要移动的点数为 。 A.n/4 B.n/3 C.n/2 D.n 『正确答案』C 『答案解析』如果在顺序表的尾部插入则移动0个结点如果在顺序表的头部插入则移动n个结点。 【例题单选题】从一个长度为n的顺序表中删除第i个元素1in时需向前移动的元素个数为 。 A.n-i B.n-i1 C.n-i-1 D.i 『正确答案』A 『答案解析』删除第i个元素则后面n-i个元素都要前移。 【例题单选题】设单链表中指针p指向结点A要删除A之后的结点若存在则修改指针的操作为 。 A.p-nextp-next-next B.pp-next C.pp-next-next D.p-nextp 『正确答案』A 『答案解析』要删除A之后的结点即将A的指针域指向A之后的结点的下一个结点。参见教材P47。 【例题填空题】设r指向单链表的最后一个结点要在最后一个结点之后插入s所指的结点需执行的语句序列是________; rs; r-nextNULL。 『正确答案』r-nexts 『答案解析』在单链表中用尾插法插入一个结点将尾结点的指针域指向待插结点带插结点的指针域指向NULL。
