数据结构课件

算法与数据结构 第4讲 链表和链表的基本操作 主讲人 王咏刚 知识回顾 数组 线性表的顺序表示方式 A B C D E 0 1 2 3 4 元素 序号 A B C 0 1 2 3 4 元素 下标 5 优点 便于快速 随机存取线性表中任一元素 缺点 插入和删除操作需要移动大量元素 X A B 0 1 2 3 4 元素 下标 链表的定义 链表 线性表的链式存储结构其特点是用一组任意的存储单元存储线性表的数据元素 存储单元可以是连续的 也可以是不连续的为了表示每个元素与后继元素的逻辑关系 除了存储元素本身的信息外 还要存储其直接后继的信息 两部分信息组成一个结点 每个结点包含 数据域 存储数据元素信息指针域 存储直接后继的存储位置信息n个结点链接成一个链表 因为只包含一个指针域 故又称线性链表或单链表 链表的典型实现 C 语言代码structnode Itemitem node next node Itemx node t item x next t typedefnode link 空指针NULL表示链表结尾 C 语言的构造函数可简化结点初始化的代码 链表的典型实现 有头结点的链表 node A node B node C node 头结点 便于操作 不存储任何元素 有时也可保存链表的属性信息 链表的典型实现 用数组实现的静态链表 A 3 C 5 B 2 E 0 D 4 1 2 3 4 5 1 0 下标 数组元素 指向链表的第一个元素 表示链表的结尾 链表的删除操作 C 语言代码 删除结点x next t x next x next t next deletet B C x A 链表的插入操作 C 语言代码 在x后插入新结点 t newnode C x next x next t B x A 循环链表 最后一个结点的指针域指向头结点 整个链表形成一个环 A B C D E 编程实例 C 语言代码 Josephus问题structnode intitem node next node intx node t item x next t typedefnode link intmain inti N M linkt x cout N cout M t newnode 1 0 t next t x t for i 2 inext newnode i t while x x next for i 1 inext coutnext itemnext x next next coutitem endl 创建第一个结点 向环内增加其他结点 直到环内剩下最后一个结点 每次数到M 就删除一个结点 编程实例 Josephus问题的运行过程示意 t newnode 1 0 t next t x t for i 2 inext newnode i t while x x next for i 1 inext x next x next next 1 2 3 4 5 6 7 8 9 课后思考题 用C 语言编写静态链表 存储在静态数组中