软件技术基础_链表.ppt

二 链表 1 链表的引入用数组实现的顺序表可随机存取表中任一元素 但存在以下缺陷 1 插入 删除运算时需大量移动元素2 表的空间固定 一旦确定最大元素个数 则无法更改解决措施 元素离散存放 通过指针表示元素与元素之间的逻辑关系 链式存储 用链表实现线性表 非连续存储 线性表元素 a1 a2 a3 a4 链表数据元素 线性关系 a1 a2 a3 a4 链表指针 2 单链表 元素域 链接域 元素域 数据元素域 存放一个数据元素 链接域 关系域 存放指向下一个元素的指针 元素间的关系 元素域 链接域 节 结点 链点 链点 单链表 由链点及链点相互间的链接构成 head 链表头 链表尾 链表长度 结点数目 C语言描述 typedefstructnode elemtypedata structnode next node type typedefstruct node type head node type tail intlength list type 链点类型定义 链表类型定义 链表头是数据内容为第一个元素的链点 头指针是一个指针变量 指向表头元素 一个单链表可由头指针唯一确定 头结点是一个特殊的链点 其数据内容无效且链点指针指向链表头 引入头结点可方便算法的实现 统一空表和非空表的处理 动态数据结构 若一种数据结构 在物理上并不一定占用连续的内存空间 且占用的内存空间在程序运行期间可以动态地变化 可以根据需要随机地增加或删除其元素 就称为动态数据结构动态数据结构分配内存空间时必须采用动态存储分配技术链表是一种动态数据结构 内存动态申请和释放 void malloc unsignedintsize 在动态存储区分配长度为size的连续空间 并返回指向该空间起始地址的指针 若分配失败 系统不能提供所需内存 则返回空指针 NULL 例 int p int malloc sizeof int length voidfree void ptr 释放ptr指向的内存空间 ptr是malloc 函数返回的指针 例 free p 单链表的操作 1 初始化 建立一个空的带头结点的单链表node type init sllist void node type head head node type malloc sizeof node type if head NULL head next NULL else printf initerror head NULL returnhead 2 访问单链表 问题描述 取单链表中第i个结点 以带头结点的单链表为例 输入 链表头指针 i 输出 指向第i个结点的指针 算法分析 从表头开始逐个访问 直到第i个结点 或表完 设立移动指针temptemp temp next 注意计数器counter的初值 h 头结点 逐个往后 数 算法实现 node type getnode ofsllist node type head inti intcounter node type temp temp head counter 0 while counternext NULL counter counter 1 temp temp next if temp NULL 思考 i越界判断 3 链表的插入运算 问题描述 在单链表的结点ai前插入一个新的元素结点输入 链表指针list 位置i 新元素结点的指针p输出 插入新元素后的链表 算法分析 1 找到ai的直接前驱结点ai 12 插入新结点3 链表长度加一 a1 ai an head ai 1 anew 插入操作 pnew 在算法实现时设立 1 计数器 counter2 移动指针 temp x ai 1 temp counter p 算法实现 head 以不带头结点的单链表为例 voidinsert sllist list type list inti node type p 找到ai 1 执行插入操作 注意顺序不能反 p next temp next temp next p while counternext counter 1 temp list head 初始化 list length voidinsert sllist list type list inti node type p 找到ai 1 执行插入操作 p next temp next temp next p while counternext counter 1 temp list head 初始化 list length 边界情况 表首插入 表尾插入 长度加一 list head p next list head list head p p voidinsert sllist list type list inti node type p 找到ai 1 执行插入操作 p next temp next temp next p while counternext counter 1 temp list head 初始化 list length 表首插入 if i 1 p next list head list head p else list head 注意当循环执行到表尾时temp的值为NULL 空 temp next是悬空的值 while counternext p next temp next temp next p temp next NULL voidinsert sllist list type list inti node type p 找到ai 1 执行插入操作 p next temp next temp next p while counternext NULL counter counter 1 temp temp next counter 1 temp list head 初始化 list length 表首插入 if i 1 p next list head list head p else 对链表操作的体会 1 链表操作往往从表头开始 逐个找到需要的链点2 链表操作的有向性 不能回退 3 链表指针小心使用 谨防丢失 4 插入过程没有进行链点内容进行搬移 思考1 改为在元素值为x的链点前插入 算法如何写 2 如果改为在带头结点的单链表中插入新元素如何实现 4 链表的删除运算 问题描述 删除单链表中的数据元素结点ai 带头结点 算法分析 1 找到ai 12 执行删除操作 修改链指针pai 1 next pai 1 next next3 释放被删结点所占的空间 算法实现 temp s指针 temp next temp next next voiddelete sllist list type list inti intcounter node type temp s temp list head counter 0 while counternext NULL counter temp temp next if counter i 1 printf iisinvalid return else s temp next temp next temp next next free s list length 思考 1 如果改为删除元素为x的链点 删除算法如何实现 2 如果改为不带头结点的单链表 删除算法如何实现 5 链表的建立 建立线性表的链式存储结构的过程就是一个动态生成链表的过程 即从空表的初始化状态开始 依次生成各元素结点 并逐个插入表中 链表占用的空间不需预先分配 而按需动态分配 问题描述 输入一组数据建立单链表 以 1作为输入结束条件 算法分析 1 初始化一个空链表2 申请空间 生成新结点3 把新结点插入链表中 新元素如何插入表中 2 1 h 1 向前生成 元素插在表尾 2 向后生成 元素插在表头 2 3 h 具体方法有两种 算法实现 1 元素插在表尾node type create sllist elemtypex node type h newnode temp h NULL read x if x 1 h node type malloc sizeof node type if h NULL h data x h next NULL else returnNULL elsereturn h read x temp h while x 1 newnode node type malloc sizeof node type if newnode NULL newnode data x temp next newnode temp newnode read x else return h temp next NULL return h node type create sllist elemtypex node type h newnode h NULL read x while x 1 newnode node type malloc sizeof node type if newnode NULL newnode data x newnode next h h newnode read x else return h return h 2 元素插在表头 链表的特点 1 操作的顺序性 平均n 2次查找过程2 离散存放 不受链表初始大小限制不进行结点内容的搬移查找操作 顺序表优于链表插入删除操作 链表优于顺序表 特点 每一个链点包含两个指针 前趋指针P 后继指针N 3 双向链表 typedefstructdouble link node structdouble link node prior structdouble link node next elemtypedata dl node type typedefstruct dl node type head dl node type tail intlength dl list type C语言描述 链点的定义 链表的定义 ai 1 N P 双向链表的插入操作 ai N P 问题描述 在元素ai前插入新元素anew anew N P 1 pnew next ai 2 pai 1 next pnew 3 pnew prior ai 1 4 pai prior pnew pnew next temp temp prior next pnew pnew prior temp prior temp prior pnew pnew 算法实现 略 体会 插入操作有多种方式实现 步骤比较复杂 双向链表的使用灵活 可进可退 思考 四个步骤的组合顺序里 哪些是正确的 哪些是错误的 双向链表的删除操作 问题描述 删除元素ai ai 1 N P ai N P ai 1 N P temp prior next temp next temp next prior temp prior free temp a1 ai 1 an head ai 1 将链表头尾相接 对循环链表的遍历可以从任何一个节点开始 4 循环链表 例 将两个带头结点的循环链表连接成一个链表 P 19 例 删除一个单向链表中数据大于100的所有结点 算法分析 1 逐个取结点元素进行比较 current while current NULL current current next 2 删除大于100的结点if current data 100 删除由current指针指向的结点 current last last next current next free current current last next 删除操作 否则 移动指针 last current current current next 注意 last指针的作用 3 边界问题 被删结点是第一个结点if current head head head next free current current head 算法实现 voiddeleteover100 list type list node type last current last NULL current list head while current NULL if current data 100 if last NULL list head current next free current current list head else last next current next free current current last next list length else last current current current next 例 将一个单向链表反向连接 算法分析 1 逐个进行的基本框架 2 反向操作 方法一 head1 head2 目标 a1 方法二 直接在原链表的基础上操作 a2 a3 a4 a1 a2 a3 a4 ai 2 ai 1 ai ai 1 ai 2 current next last last current current continue continue continue next voidinvert list list type list last NULL current list head continue current while current NULL continue current next current next last last current current continue list tail list head list head last 问题描述一个一元多项式可以表示为 其中每一项由系数Pi及x的指数i组成 若多项式按升幂排列 则它由n 1个系数唯一确定 因此可以用一个线性表P表示 其指数I隐藏在系数Pi的序号内 例 两个一元多项式相加 算法分析1 存储结构 多项式相加时 常要合并同类项 由此就要改变多项式的系数和指数 而且在实际问题中 时常会出现多项式的幂次数很高但又存在大量零系数的项 因此宜采用链式存储结构 2 结点结构 每一个非零项构成链表中的一个结点 结点由两个数据域和一个指针域构成 如下图 typedefstructnode intexp intcoef structnode next poly node 3 链表结构 采用带头结点的单链表表示多项式A x B x 相加后结果为多项式C x 4 运算过程 设指针ha hb分别为多项式链表A x B x 的头指针 指针p q的初始位置分别指向A x B x 中的第一项 过程为 比较p q所指结点中的指数项 如果 p expexp 那