第7章 C语言 动态数据结构.ppt

第七章动态数据结构 目录 态数据结构 本章开始介绍动态数据结构 主要介绍链表结构的建立 在链表中查找指定元素 插入一个新元素 删除一个元素等操作 学完本章内容后 要求深刻理解动态存储结构的概念 并正确运用 7 1从静态数据结构到动态数据结构 在此之前 我们涉及到的都是静态数据结构 像数组 简单类型 int float 等 静态数据结构的特点是由系统分配固定大小的存储空间 以后在程序运行的过程中 存储空间的位置和容量都不会再改变 而实际生活中常常有这样的问题 数据量的多少是动态变化的 7 1从静态数据结构到动态数据结构 例如 图书馆的藏书量 在图书馆初建时 假设有10000本 随着时间的推移 藏书的数量必定要增加 有人可能会想 在定义一个静态变量时 预留出一部分空间 但这也会引起一些问题 首先多出的那部分空间不知何时才能使用 在没有被使用之前一直被闲置 其次 谁又能保证增加的空间就足够呢 7 1从静态数据结构到动态数据结构 问题的关键在于 此问题的数据本身就是变化的 而且是不确定的变化 什么时候变 怎么变都是未知的 对这样的问题用静态存储结构来描述和存放显然捉襟见肘 存在隐患 动态数据结构不确定总的数据存储量 而是为现有的每一个数据元素定义一个确定的初始大小的空间 若干个数据元素分配若干个同样大小的空间 当问题的数据量发生变化时 数据的存储空间的大小也发生变化 如果数据量增加 就重新向系统申请新的空间 如果数据量减少 就将现有的多余的空间归还给系统 7 2 动态内存分配 使用计算机解决问题的所有方法都是通过使用系统提供给我们的基本命令或函数来实现的 所以首先让我们来看看 c的标准函数中有哪些是用于动态内存分配的 怎样使用 7 2 1ANSIC中动态内存操作标准函数 ANSIC中提供了若干个动态内存操作标准函数 它们的名称分别是malloc calloc realloc free等 这些函数可以使用在任何的C环境中 1 malloc函数 malloc函数是C的标准函数之一 原型定义在malloc h文件中 原型为 void malloc unsignedintsize 其作用是向系统申请一个确定大小 size个字节 的存储空间 返回值为一个指向void类型的分配域起始地址的指针值 如果此函数操作失败 返回值为空 1 malloc函数 使用格式 指针型变量 基类型 malloc 需要的存储空间的字节数 例7 1 为一个整数分配存储空间 需要的语句为 在文件的头部 include在说明部分 int p 在程序中 p int malloc sizeof int 测试malloc的程序举例 include include includevoidmain int p 定义一个指向整型的指针变量 intx p int malloc sizeof int if p exit 0 p 2 calloc函数 calloc函数是C的标准函数之一 原型定义在malloc h文件中 原型为 void calloc unsignedintn unsignedintsize 其作用是向系统申请n个大小为size个字节的连续存储空间 返回值为一个指向void类型的分配域起始地址的指针值 如果此函数操作失败 返回值为空 可以为一维数组开辟一片连续的动态存储空间 2 calloc函数 使用格式 指针型变量 数组元素类型 calloc n 每一个数组元素的存储空间的字节数 例7 2 为一个有10个整数的一维数组分配存储空间 需要的语句为 在文件的头部 include在说明部分 int p 在程序中 p int calloc 10 sizeof int 使用calloc函数程序举例 include include includemain int p intx p int calloc 10 sizeof int if p exit 0 for i 0 i 10 i scanf d 3 realloc函数 realloc函数是C的标准函数之一 原型定义在malloc h文件中 原型为 void realloc void p unsignedintsize 其作用是向系统重新申请一个确定大小的存储空间 并将原存储空间中的数据值传送到新的地址空间的低端 返回值为一个指向void类型的分配域起始地址的指针值 如果此函数操作失败 返回值为空 原存储空间的数据将丢失 3 realloc函数 使用格式 指针型变量 基类型 realloc 原存储空间的首地址 新的存储空间的字节数 例7 3 现有一个为10个整数分配的存储空间 其首地址为p1 由于数据量的增加 原存储空间已满 需要扩大原空间为20个整数的大小 需要的语句为 在文件的头部 include在说明部分 int p2 在程序中 p2 int realloc p1 sizeof int 20 程序举例 include include includemain int p1 p2 intx p1 int malloc sizeof int 10 if p1 exit 0 p2 int realloc p1 sizeof int 20 if p2 exit 0 realloc函数主要的用于当原分配空间已被占满 而新的数据又要加入到该空间时的状况 它的优点是可以自动地将原空间的内容全部传递到新空间中 不必程序员再编语句来实现 缺点是一旦新空间申请失败 原空间的内容也将丢失 对这一点 使用时应加以注意 4 free函数 free函数是C的标准函数之一 原型定义在malloc h文件中 原型为 voidfree void p 其作用是释放由p所指的内存区 将一个存储空间归还给系统 使用格式 free 指针型变量 例7 4 将一个已分配存储空间释放 需要的语句为在文件的头部 include在说明部分 int p 在程序中 free p 程序举例 include include includemain int p p int malloc sizeof int if p exit 0 free p c 中为进行动态操作提供的运算符 new和delete 在软件的研制过程中 程序中动态申请内存空间和释放内存空间是一件很常见的事 前面一节中 我们讲解了ANSIC中的办法 利用标准库函数malloc calloc reallloc free等 但malloc calloc reallloc等函数都要求程序设计者知道应开辟空间的确切大小 返回值的类型需要强制类型转换 c 中对此进行了改进 为进行动态内存操作提供了运算符new和delete 来代替malloc和free 但在c 中依然保留了malloc和free 以便和C兼容 1 new运算符 new是c 中提供的用于开辟一个动态存储空间的运算符 new运算符的一般格式 变量指针 new类型 初值 例如 1 申请一个存放整数的空间 语句格式 p newint 执行结果 开辟了一个整数大小的空间 并将该空间的首地址送入指向整型数据的指针变量p中 2 申请一个存放字符型数据的空间 并为该空间赋初值 a 语句格式 p newchar a 执行结果 开辟了一个字节大小的空间 并将该空间的首地址送入指向字符型数据的指针变量p中 P所指空间中的数据值为字符 a 3 申请一个存放实数的空间 语句格式 p newfloat 1 414 执行结果 开辟了一个实数大小的空间 并将该空间的首地址送入指向实型数据的指针变量p中 并将该空间中赋入初值1 414 4 申请一个存放10个实数的数组的空间 语句格式 p newfloat 10 执行结果 开辟了一个10个实数大小的空间 将该空间的首地址送入指向实型数据的指针变量p中 注意 用new为数组分配空间不能指定初值 2 delete运算符 delete运算符是c 中的提供的实现动态内存释放功能的运算符 类似于标准库函数free 一般格式为 delete名字指针 例如 1 释放一个存放整数的空间 如果p newint 则释放一个存放整数的空间的语句为 deletep 执行结果 将该整数空间释放掉 即将该资源归还给系统 2 delete运算符 2 释放一个存放10个实数的数组的空间 如果 p newfloat 10 则释放一个数组空间的语句为 delete p 执行结果 将该数组空间释放掉 即将该资源归还给系统 2 delete运算符 new试图创建一个名字类型的对象 向系统申请sizeof 名字 个字节大小的空间 新对象的生存周期始于创建点 直到delete将其释放或到程序结束 如果申请成功 返回指向新对象的指针 若返回的指针为空指针 表示动态空间分配失败 注意 delete只能用于用new分配的内存的释放 例7 5申请一个结构体类型的存储空间 用来存放相应类型的数据 解决问题要点 包含相关的头文件 定义一个结构体类型 定义结构体类型的变量 申请空间 对指定空间赋值 释放申请的空间 程序举例 include include include includetypedefstructLNode intdata structLNode next LNode main LNode p p newLNode if p exit 0 p data 10 p next NULL deletep new与malloc的相同点是他们的作用都是在程序的执行过程中向系统申请存储空间 返回值都是申请到的存储空间的首地址 不同点是 malloc是c编译系统提供的标准库函数 new是c 系统提供的运算符 new的操作效率要高于malloc new不需要使用显式的sizeof函数就能知道名字的大小 而malloc需要明确指出所申请的空间的大小 总的字节数 new的返回值是指向名字类型的确定的指针类型 不需要强制说明 而malloc的返回值是一个指向void类型的指针类型 需要强制转换成指向具体数据类型的指针类型 当所申请的空间是一个变量所需的空间时 new运算符还可以为所申请的空间赋初值 malloc不具有此功能 7 3链表 计算机处理数据需要两方面的工作 一方面是对数据信息的描述 另一方面是对数据的操作 而操作的方式取决于数据的描述方式 数据的描述方式又取决于数据本身固有的内在联系 这里仅介绍数据之间的线性关系 对于图书馆的藏书这类数据信息可以用一种称为线性表的动态数据结构来描述 简单的说 线性表是n个数据元素的有限序列 各数据元素属于同一数据对象 相邻数据元素之间存在序偶关系 记为 a1 a2 ai ai 1 an 线性表中的数据元素之间存在严格的顺序关系 有一个唯一的称为第一个的元素 首元 有唯一的称为最后一个的元素 尾元 其它元素都有唯一的直接后继元素和唯一的直接前趋元素 线性表这种逻辑结构在计算机内表示时 可以采用链式存储结构 即一个数据元素存放于一个结点中 不同的数据元素之间的先后顺序用结点的指针域链接 一个结点就是一个结构体类型的变量 7 3 1链表的定义 链表是表示具有线性关系的一组数据元素的动态结构 每一个数据元素占据一个独立申请的存储空间 这个存储空间通常是一个结构体型变量 主要包括两部分 一部分用来存放数据元素的值 称为值域 另一部分用来存放一个指向该结构体类型的指针变量值 称为指针域 指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址 数据元素结点的结构如图所示 若干个结点首尾相连按照其逻辑顺序链接成一排 称为线性链表 单向链表如下图所示 图7 2单向链表 1 链表结点的C语句定义 对于链表这种数据结构 ANSIC中 按如下方式描述 首先用结构体类型描述一个数据元素结点 定义一个结点类型的语句格式 typedefstructLNode ElemTypedata structLNode next LNode LinkList 其中 typedef语句定义了一个结构体类型和链表类型LNode是一个结点的类型名称 它有两个成员 一个名称为data 类型为数据元素的类型 用来存放一个数据元素的值 另一个成员名称为next 类型为指向本结构体类型的指针类型 用来存放逻辑上排在本结点后面的结点的首地址 LinkList是指向LNode类型的指针类型 ElemType是数据元素的类型的一般性描述 当我们具体写程序时 应该用确定类型名称来替换 例如 int float char等 例7 6 链表中的数据元素用来存放整数 定义链表的结点类型的语句格式为 typedefstructLNode intdata structLNode next LNode LinkList 定义一个指向结点类型的指针类型变量的语句 LNode p 3 定义一个链表类型的指针变量 LinkListL 4 访问结点变量p的各个成员 p data p next说明 本章的所有程序都是基于以上类型定义 7 3 2链表的建立 1 构造一个空线性链表L首先 构造一个空的线性链表 为了描述方便 通常将链表的第一个结点空置 不存放数据元素 只是作为链表的开始标志 称为头结点 数据元素从链表的第二个结点开始存放 空的线性表定义为没有数据元素的表 一个空的线性链表就规定为 只有一个头结点的链表 所以 构造一个空的线性链表就是建立只有一个头结点的链表 1 算法描述 申请一个结点的空间 将该结点作为线性链表的头结点 将该结点的next域置空 2 完整程序 Example7 6 cpp 程序名 Example7 6 cpp voidInitList LinkList L 构造一个空的线性链表 L LNode malloc sizeof LNode 申请一个结点空间 if L exit 0 申请不成功 异常结束程序运行 L next NULL 申请成功 头结点的next域置空 return 1 2 逆序输入n个数据元素 建立带表头结点的单线性链表L 现在开始建立一个非空的线性链表 我们这里所建的链表的第一个结点都是头结点 数据元素从链表的第二个结点开始存放 一个非空的线性链表是除了头结点以外至少有一个数据元素的链表 线性链表由若干个数据元素结点组成 那么 构造一个非空的线性链表的过程就是逐个建立数据元素结点 并将它们依次插入到链表中的过程 所谓头插入 即每次将数据元素结点插入到表头结点的之后 第一个数据元素结点之前 插入过程如图7 3所示 初始状态 插入第一个结点之后 插入第二个结点之后 插入第三个结点之后 插入最后一个结点之后 voidCreateList LinkList L intn inti LNode P L LNode malloc sizeof LNode if L exit 0 L next NULL for i n i 0 i p LNode malloc sizeof LNode if p exit 0 scanf d 以上的算法只是建立链表的一种方法 它的核心是新的数据元素结点插在链表的第一个数据元素的位置 我们也可以将新建立的数据元素结点每次都插在链表的尾部 大家可以思考一下 以尾插入的方式建立链表 程序怎样编写 7 3 3链表结点的插入 将一个数据元素插入到链表中 有三种情况 头插入 尾插入以及在链表中的第i个数据元素的位置处插入 将一个新元素插入在链表的头结点的后面 其它的所有结点之前称为头插入 将一个新元素插入在链表的尾结点的后面 使得新插入的结点成为尾结点称为尾插入 将一个新元素插入在链表中的第i个数据元素的位置处 即插入在第i个数据元素结点之前 使得新插入的结点成为链表中的第i个结点 下面我们详细介绍每一种插入的算法实现 例7 8 已有链表L如图所示 链表中的元素按递增有序排列 图7 4链表的插入过程其中每个结点中存放的值为学生的考试成绩 现在有另外三个学生的的成绩分别为65 82 90 将他们插入到链表L中 要求插入之后链表依然递增有序 图7 5头插入过程 首先将65插入到链表L中 插入的过程 设p L next 因为p非空 判断p data 65 所以 65应该插在L的后面 70结点的前面 插入之后的链表为 L 80 70 85 s p 实现语句 p L next s LNode malloc sizeof LNode s data x s next p L next s 将82插入到链表L中 插入的过程 首先应找到82应在的位置 82应该插在两个结点之间 82前面结点的data域值小于82 82后面结点的data域值大于等于82 如图所示 L 实现语句 q L p L next while p 将90插入到链表L中 显然 90应插到链表的尾部 即 插到链表的最后一个结点的后面 插入的过程 首先找到插入的位置 设p L next 当p非空并且p datanext 循环一定以p为空结束 将新结点90插在q的后面 插入之后的链表为 L 实现语句