计算机软件技术编程基础 链表.ppt

顺序表的特点 运算 简单 时间复杂度好存储特性 静态规模 编译前确定问题 程序的通用性和空间利用率之间的矛盾期望 在实际运行过程中 根据实际问题的需要临时确定存储空间 涉及到动态变量动态变量 在程序运行的过程中产生和释放的变量 与之相反的是静态变量静态变量 在程序运行的过程中一直存在的变量 静态变量是出现在说明语句中的变量 动态变量由于是在运行中产生的 因而不会事先说明如何实现动态变量 通过指针来实现 指针变量的说明 动态变量的产生和释放 2 3线性链表及其运算 线性表的链式存储结构称为线性链表 即将表中元素用链地址连接起来 head 头指针 结点 对线性表中的每一个数据元素 都需用两部分来存储 一部分用于存放数据元素值 称为数据域 另一部分用于存放直接前驱或直接后继结点的地址 指针 称为指针域 称这种存储单元为结点 链表的存储结构 链式存储结构是利用任意的存储单元来存放线性表中的元素 存储数据的单元在内存中可以连续 也可以零散分布 由于线性表中各元素间存在着线性关系 每一个元素有一个直接前驱和一个直接后继 为了表示元素间的这种线性关系 在这种结构中不仅要存储线性表中的元素 还要存储表示元素之间逻辑关系的信息 所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息 除了存储每一个数据元素值以外 还需存储其后继或前驱元素所在内存的地址 两部分信息一起构成链表中的一个结点 结点的结构如下所示 链表结构示意图 从图中可见 每个结点的存储地址存放在直接前驱的指针域中 所以要访问链表中数据元素C 必须由头指针head得到第一个结点 数据A 的地址 由该结点的指针域得到第二个结点 数据B 的地址 再由其指针域得到存储数据C的结点地址 访问该结点的数据域就可以处理数据C了 链表这种顺着指针链依次访问数据元素的特点 表明链表是一种顺序存储结构 只能顺序操作链表中元素 不能像顺序表 数组 那样可以按下标随机存取 在链表存储结构中 不要求存储空间的连续性 数据元素之间的逻辑关系由指针来确定 每个结点由两部分组成 data数据域 存放数据值next指针域 存放后继结点的首地址 链表通过每个指针域将n个结点按逻辑次序链接成一个整体 b c d Head a 头指针 结点 b c a data next 表头的地址由head指针提供 表尾结点没有直接后继 其指针域应为空指针 指针域为NULL 单向链表 在图所示的链表中 每个结点只有一个指向后继的指针 也就是说访问数据元素只能由链表头依次到链表尾 而不能做逆向访问 称这种链表为单向链表或线性链表 这是一种最简单的链表 对于空链表 头结点的指针域为空 图2 8 a 为带头结点的空链 b 为带头结点的单链表 定义链表结点结构的一般形式为Struct结构体名 数据成员表 结构体名 指针变量名 structstudent intnum floatscore student next structListNode ELEMdata ListNode next 167 287 379 486 head tail 建立链表linklist create linklist head p1 p2 head NULL intx cin x structlinklist intnum floatscore linklist next p2 p1 将新的结点作为尾结点p2 next NULL cin x while x 0 p1 new linklist p1 num x cin p1 score n n 1 if head NULL head p1 elsep2 next p1 如果是首结点呢 定义一个新结点 returnhead 建立链表的条件 voidprint cout n endl 链表输出 形参是什么 需要知道链表的头指针 linklist head 如何查找链表 定义一个指针 linklist p1 p1 head if head NULL do coutnumscore coutnext while p1 NULL 查找运算的实现设计思路 设置一个跟踪链表结点的指针p1 初始时p1指向链表中的第一个结点 然后顺着next域依次指向每个结点 每指向一个结点就判断其值是否等于i 若是则返回该结点地址 否则继续往后搜索 要访问单链表中第i个元素值 必须从头指针开始遍历链表 依次访问每个结点 直到访问到第i个结点为止 其时间复杂度为O n linklist getnode else cout i notbeenfound returnNULL 查找 按结点数据域的值查找 形参是什么 linklist head inti linklist p1 intj 0 p1 head 定义一个查找指针 while p1 num i 如果该结点不是要找的结点 if p1 num i j cout thenodeis j endl returnp1 如果该结点是要找的结点 linklist del linklist head intnum linklist p1 p2 if head NULL p1 head elsecout listisnull returnhead 删除链表指定结点 p1 c d p1 c p2 P2 next P1 next 删除条件 if p1 num num if p1 head head p1 next elsep2 next p1 next n n 1 elsecout num notbeenfound 删除链表指定结点 while p1 num num 如果该结点不是要找的结点 找到该结点如何删除 线性链表的插入 在链式存储结构下的线性表中插入一个新结点 在头指针head的线性链表中包含元素x的结点之前加入一个新结点 voidinslst linklist head intx linklist p1 p2 p1 new linklist cin p1 num p1 score if head NULL head p1 p1 next NULL p2 getnode head x 寻找包含元素x的结点 p1 next p2 next 将结点p1插入到结点p2后p2 next p1 在插入和删除算法中 都是先查询确定操作位置 然后再进行插入和删除操作 所以其时间复杂度均为O n 另外在算法中实行插入和删除操作时没有移动元素的位置 只是修改了指针的指向 所以采用链表存储方式要比顺序存储方式的效率高 循环链表 循环链表是单链表的另一种形式 是一个首尾相接的链表 特点 最后一个结点的指针域不空 而是指向头结点 整个链表连成环状 从表中任意结点出发均可到达其他结点 空循环链表 判断表空的条件 head next head 判断指针指向结点为表尾结点的条件 p next head 带头结点的单循环链表的操作算法和带头结点的单链表的操作算法很相似 差别仅在于算法中的循环条件不同 在循环单链表上实现上述基本运算的改动如下 1 初始化链表initlist head 创建的头结点指针域next不为空 而是指向自身head next head 2 线性表查找运算 getnode linklist head inti 函数 链表元素输出运算print linklist head 函数中 循环遍历是否进行的条件由p NULL改为p head 其余函数运算没有变化 请自行写出相关函数的定义 在循环链表中 除了有头指针head外 有时还可加上一个尾指针tail 尾指针tail指向最后一结点 沿最后一个结点的指针又可立即找到链表的第一个结点 在实际应用中 使用尾指针来代替头指针进行某些操作往往会更简单 例 将两个循环链表首尾相接进行合并 La为第一个循环链表表尾指针 Lb为第二个循环链表表尾指针 合并后Lb为新链表的尾指针 head指向整个合并后的链表 解 算法思路 对两个单循环链表La Lb进行的连接操作 是将Lb的第一个数据结点接到La的尾部 操作时需要从La的头指针开始找到La的尾结点 其时间复杂性为O n 而在循环链表中若采用尾指针La Lb来标识 则时间性能将变为O 1 其连接过程如图2 14所示 图两个循环链表首尾相接进行合并 a 连接前p La next q Lb next b 连接后La next q Lb next p 双向链表 双向链表的结点结构 structdlnode ELEMdata dlnode next prior 对结点p而言 后继结点的地址p next 前驱结点的地址p prior p p1 p0 P prior next P next prior P prior P next s p1 p0 P1 prior next s P1 prior s s prior p1 prior s next p1 双向链表中结点的插入 将结点s的插入结点p1之前 p P next P prior 双向链表中结点的删除 P prior next p next P next prior p prior deleteP 应用举例一元多项式相加假设用单链表表示多项式 A x 12 7x 8x10 5x17 B x 8x 15x7 6x10 头指针Ah与Bh分别指向这两个链表 如图2 21所示 对两个多项式进行相加运算 其结果为C x 12 15x 15x7 2x10 5x17 如图所示 图合并以前的链表 图2 22合并以后的链表 对两个一元多项式进行相加操作的运算规则是 假设指针qa和qb分别指向多项式A x 和B x 中当前进行比较的某个结点 则需比较两个结点数据域的指数项 有三种情况 1 指针qa所指结点的指数值 指针qb所指结点的指数值时 则保留qa指针所指向的结点 qa指针后移 2 指针qa所指结点的指数值 指针qb所指结点的指数值时 则将qb指针所指向的结点插入到qa所指结点前 qb指针后移 3 指针qa所指结点的指数值 指针qb所指结点的指数值时 将两个结点中的系数相加 若和不为零 则修改qa所指结点的系数值 同时释放qb所指结点 反之 从多项式A x 的链表中删除相应结点 并释放指针qa和qb所指结点 多项式相加算法 structpolynode add poly polynode Ah polynode Bh polynode qa qb s r Ch qa Ah qb Bh qa和qb分别指向两个链表的第一结点r qa Ch Ah 将链表Ah作为相加后的结果链表while qa NULL 多项式Bh的指数值小 链栈 top 栈顶 链表的头部作栈顶是最方便的链表的头指针叫做栈顶指针只允许在表头进行插入和删除运算 structlinkstack intnum floatscore linkstack next 置空栈linkstack init linkstack returnNULL 判断栈空intempty linkstack linkstack top if top NULL return1 elsereturn0 入栈linkstack push linkstack linkstack top linkstack stud stud next top top stud n n 1 returntop top stud top top 出栈linkstack pop linkstack linkstack top linkstack stud if top NULL returnNULL else stud top top top next n n 1 returntop top top stud 带链的队列 rear front 先进先出的数据结构 只允许在表头删除 表尾插入的单链表 structqnode intnum structqnode next structlqueue qnode front rear lqueue init lqueue lqueue l qnode q l new lqueue q new qnode q next NULL l front l rear q returnl 创建一个空队列 front rear next structqnode intnum structqnode next structlqueue qnode front rear voidin lqueue lqueue l qnode q q next NULL 入队 front rear next next 只能在表尾插入结点 l rear next q 队尾结点的指针域指向新结点 l rear q rear存入新结点地址 出队 删除表头结点 front rear next next next qnode out lqueue lqueue l qnode qreturnq 判断队空的条件 if l rear l front returnNULL 取出队首结点地址 q l front next l front next q next 队首结点地址给下一个结点 作业 P1532 10试写出逆转单链表的算法2 9试写出循环链表长度的算法上机 星期三晚上7 00 3月27日 作业讲评 2 10试写出逆转单链表的算法 如何定义一个新结点 structlinklist intnum