C语言基础 模块7 part2.ppt

结构体与链表 模块7 2 某一组数据的逻辑结构 是n 0个数据元素a1 a2 an 1 an的有序集合 集合中每个元素ai的位置仅取决于元素本身的序号i 注意 同一集合中的元素必定具有相同的特性 链表基础 定义与表示 在计算机内部可以采用两种不同方法来表示这一组数据 它们分别是顺序表表示法和链表表示法 顺序表示法用一组地址连续的存储单元依次存储数据元素 这种存储结构称为顺序存储结构 并称为顺序表 链表基础 定义与表示 链表基础 定义与表示 用一组地址连续的存储单元依次存放数据元素 a1a2 ai 1ai an 数据集合的起始地址 顺序表示法的特点 优点 1 存储密度大 空间利用率高 2 数据元素逻辑位置相邻 物理位置也相邻 可随机存取 所以称为随机存取结构 缺点 1 插入和删除时要移动大量的元素 2 长度较大的线性表须按最大需要的空间来分配存储空间 链式表示 用一组地址任意的存储单元存放数据集合中的数据元素 以元素 数据元素 指针 指示后继元素存储位置 结点 以 结点的序列 表示 称作链表 结点 由数据域和指针域构成 链式存储方式 链式存储结构不要求逻辑上相邻的数据元素在物理位置上也相邻 链表 是用一组地址任意的存储单元存放集合的各个数据元素 通过保存直接后继的存储位置来表示元素之间的逻辑关系 所有的数据元素都分别保存在具有相同数据结构的结点中 结点是链表的基本存储单位 结点与数据元素一一对应 每个结点在链表中使用一块连续的存储空间 而相邻结点之间不必使用连续的存储空间 共74页第9页 链表的定义链表是一种最简单 最常见的动态数据结构 它通过指针 链 将一组结点链接在一起 链表 定义与表示 共74页第10页 结点的定义结点包括两部分 信息部分和链接结点的指针例如 使用结点描述一个学生的信息 姓名 structnode charname 20 信息 structnode link 指针 递归定义 链表 定义与表示 共74页第11页 链表组成 指向链表表头结点的指针 表头指针 也称为头指针 表头结点 链表的第一个结点 不保存数据信息 表结点 数据结点 也称为结点 保存数据信息 链表的图示表示 头指针 头结点 数据结点1 数据结点n 数据结点i 数据结点2 链表 定义与表示 申请内存函数 malloc malloc size 功能 申请长度为size字节的内存区 若申请成功 函数返回所分配的内存区首字节的地址 即指向该内存的指针 若申请失败 函数返回NULL 说明 函数malloc的返回值为指向void类型的指针 这是通用指针类型 在实际申请内存空间时 要按照实际指针所指对象的类型进行指针类型强制转换 链表 定义与表示 释放内存 free free p 功能 释放p所指的内存空间 函数无返回值 这里p所指的内存区域必须是用函数malloc申请的内存空间 否则调用时使用其它指针 可能会破坏系统 10 8链表基础 建立链表的基本方法 链表 定义与表示 共74页第14页 定义结点的结构 说明表头指针根据结点实际需要保存的信息来定义结点的结构 结点包括信息部分和链接结点的指针 例如 定义一个描述学生信息 姓名 的结点 structstudent charname 20 信息 structstudent next 指针 定义结点 structstudent head 说明头指针head 链表 建立链表的基本方法 共74页第15页 申请存储空间建立表头结点structstudent p p structstudent malloc sizeof structstudent 申请表头结点 p link NULL 将表头结点的link置为NULL head p head指向表头结点p 只有表头结点 不含数据结点的空链表 链表 建立链表的基本方法 共74页第16页 从表头开始将数据结点插入到链表中 插入第一个数据结点 structstudent p p structstudent malloc sizeof structstudent 申请数据结点 gets p name 按照访问结构的方法 将数据存入p所指向的结点 p link head link 将表头结点的link存入p的link中 head link p 将数据结点p插在表头结点之后 数据结点 name NULL 链表 建立链表的基本方法 共74页第17页 在链头位置插入数据结点 插入下一个数据结点 p structstudent malloc sizeof structstudent 申请数据结点 gets p name 按照访问结构的方法 将数据存入p所指向的结点 p link head link 将表头结点的link存入p的link中 head link p 将数据结点p插在表头结点之后 数据结点 name2 链表 建立链表的基本方法 共74页第18页 将结点插入到链表的链头位置 程序 建立有n个数据结点的链表 调用create函数时 已经建立好表头结点 head structstudent malloc sizeof structstudent head link NULL head指向头结点 create structstudent head intn structstudent p for n 0 n p structstudent malloc sizeof structstudent gets p name p link head link head link p 链表 建立链表的基本方法 共74页第19页 访问链表中全部数据结点output structstudent head structstudent p p head link p指向第一个数据结点 while p NULL puts p name 输出p所指向结点的数据 p p link p指向下一个数据结点 分析 三种情况 链表 访问链表全部结点 共74页第20页 求链表长度链表长度 链表中所包含的数据结点的数量 length structstudent head intlen structstudent p for len 0 p head link p NULL len p p link p指向下一个数据结点 return len 分析 链表 求链表长度 共74页第21页 在链表的第i个结点的后面插入新结点 基本原理 定位 指针q指向第i个结点 指针p指向需要插入的结点 链表 插入操作 链接后面指针 p link q link 链接前面指针 q link p 共74页第22页 在链表的第i个结点的后面插入新结点p 程序 insert node structstudent head structstudent p inti structstudent q intn 0 for q head nlink NULL n q q link 定位 p link q link 链接后面指针 q link p 链接前面指针 特殊情况 空表插入 链表 插入操作 共74页第23页 在链表中删除第i个结点 基本原理 定位 指针q指向第i 1个结点 指针p指向被删除的结点 链表 删除操作 摘链 q link p link