《动态数据结构》PPT课件.ppt

1 第七章动态数据结构 2 教学目标 动态数据结构的概念动态申请和释放内存的方法链表的建立链表结点的插入和删除算法 3 7 1从静态数据结构到动态数据结构7 2动态内存分配7 3链表7 4本章小结 4 7 1从静态数据结构到动态数据结构 静态数据结构的特点是由系统分配固定大小的存储空间 以后在程序运行的过程中 存储空间的位置和容量都不会再改变 如数组 简单类型 int float 等 实际生活中常常有这样的问题 数据量的多少是动态变化的 如何解决 5 动态数据结构不确定总的数据存储量 而是为现有的每一个数据元素定义一个确定的初始大小的空间 若干个数据元素分配若干个同样大小的空间 当数据量发生变化时 数据存储空间的大小也发生变化 如果数据量增加 就重新向系统申请新的空间 如果数据量减少 就将现有的多余空间归还给系统 6 7 2 动态内存分配 ANSIC中用于动态操作的标准函数C 中用于动态操作的运算符 new和delete 不要求 7 ANSIC中用于动态操作的标准函数 ANSIC中提供了若干个动态内存操作标准函数 它们的名称分别是malloc calloc realloc free等 这些函数可以使用在任何的C环境中 其原型定义在malloc h文件中 8 malloc函数 原型 void malloc unsignedintsize 功能 向系统申请一个确定大小 size个字节 的存储空间 返回值为一个指向void类型的分配域起始地址的指针值 如果此函数操作失败 返回值为空 9 使用格式 指针型变量 基类型 malloc 需要的存储空间的字节数 例7 1 为一个整数分配存储空间 需要的语句为 在文件的头部 include在说明部分 int p 在程序中 p int malloc sizeof int 10 例7 1 测试malloc的程序 include include includevoidmain int p p int malloc sizeof int if p exit 0 p 10 printf p d n p free p 11 calloc函数 原型 void calloc unsignedintn unsignedintsize 功能 向系统申请n个大小为size个字节的连续存储空间 返回值为一个指向void类型的分配域起始地址的指针值 如果此函数操作失败 返回值为空 使用此函数可以为一维数组开辟一片连续的动态存储空间 12 使用格式 指针型变量 数组元素类型 calloc n 每一个数组元素的存储空间的字节数 例7 2 为一个有10个整数的一维数组分配存储空间 需要的语句为 在文件的头部 include在说明部分 int p 在程序中 p int calloc 10 sizeof int 13 例7 2 使用calloc函数程序 include include include defineN10voidmain int p intx i p int calloc N sizeof int if p exit 0 for i 0 i N i scanf d scanf d p i 14 realloc函数 原型 void realloc void p unsignedintsize 功能 向系统重新申请一个确定大小的存储空间 并将原存储空间中的数据值传送到新的地址空间的低端 返回值为一个指向void类型的分配域起始地址的指针值 如果此函数操作失败 返回值为空 原存储空间的数据也将丢失 15 使用格式 指针型变量 基类型 realloc 原存储空间的首地址 新的存储空间的字节数 例7 3 现有一个为10个整数分配的存储空间 其首地址为p 由于数据量的增加 原存储空间已满 需要扩大原空间为20个整数的大小 需要的语句为 在文件的头部 include在说明部分 int p 在程序中 p int realloc p sizeof int 20 16 例7 3 使用realloc函数程序 include include includevoidmain int p1 p2 p1 int malloc sizeof int 10 if p1 exit 0 p2 int realloc p1 sizeof int 20 if p2 exit 0 free p2 17 include include includevoidmain int p inti p int malloc sizeof int 3 p int calloc 3 sizeof int if p exit 0 for i 0 i 3 i scanf d p i p int realloc p sizeof int 2 if p exit 0 for i 0 i 2 i printf 6d p i free p 补充程序 18 realloc函数主要用于当原分配空间已被占满 而新的数据又要加入到该空间时的状况 优点是可以自动地将原空间的内容全部传递到新空间中 不必程序员再编语句来实现 缺点是一旦新空间申请失败 原空间的内容也将丢失 对这一点 使用时应加以注意 19 free函数 原型 voidfree void p 功能 释放由p所指的内存区 将一个存储空间归还给系统 使用格式 free 指针型变量 例7 4 将一个已分配存储空间释放 需要的语句 在文件的头部 include在说明部分 int p 在程序中 free p 20 例7 4 使用free函数程序 include include includemain int p p int malloc sizeof int if p exit 0 free p 21 C 中用于动态操作的运算符 new和delete ANSIC中 在用malloc calloc reallloc等函数动态申请内存空间都要求程序设计者知道应开辟空间的确切大小 用sizeof 并且返回值的类型需要强制类型转换 C 中对此进行了改进 为进行动态内存操作提供了运算符new和delete 代替malloc和free 但在C 中依然保留了malloc和free 以便和C兼容 使用运算符new和delete程序文件的文件名后缀必须为cpp 22 new运算符 new是C 中提供的用于开辟一个动态存储空间的运算符 new运算符的一般格式 变量指针 new类型 初值 如果申请成功 返回指向新对象的指针 若返回的指针为空指针 表示动态空间分配失败 23 例如 申请一个存放整数的空间 语句格式 p newint 执行结果 开辟了一个整数大小的空间 并将该空间的首地址送入指向整型数据的指针变量p中 申请一个存放字符型数据的空间 并为该空间赋初值 a 语句格式 p newchar a 执行结果 开辟了一个字节大小的空间 并将该空间的首地址送入指向字符型数据的指针变量p中 p所指空间中的数据值为字符 a 24 申请一个存放实数的空间 语句格式 p newfloat 1 414 执行结果 开辟了一个实数大小的空间 并将该空间的首地址送入指向实型数据的指针变量p中 p所指空间中的数据值为1 414 申请一个存放10个实数的数组的空间 语句格式 p newfloat 10 执行结果 开辟了一个10个实数大小的空间 将该空间的首地址送入指向实型数据的指针变量p中 注意 用new为数组分配空间不能指定初值 25 include includevoidmain float p inti p newfloat 3 if p exit 0 for i 0 i 3 i scanf f p i for i 0 i 3 i printf f p i delete p 补充程序 不用加头文件malloc h 26 delete运算符 delete运算符是C 中提供的实现动态内存释放功能的运算符 类似于标准库函数free 一般格式为 delete名字指针 例如 释放一个存放整数的空间 如果p newint 则释放一个存放整数的空间的语句为 deletep 执行结果 将该整数空间释放掉 即将该资源归还给系统 27 释放一个存放10个实数的数组的空间 如果 p newfloat 10 则释放一个数组空间的语句为 delete p 执行结果 将该数组空间释放掉 即将该资源归还给系统 注意 delete只能用于用new分配的内存的释放 28 例7 5申请一个结构体类型的存储空间 用来存放相应类型的数据 解决问题要点 包含相关的头文件 定义一个结构体类型 定义结构体类型的变量 申请空间 对指定空间赋值 释放申请的空间 29 例7 5 程序举例 include include include includetypedefstructLNode intdata structLNode next LNode typedeffloatREAL voidmain LNode p p newLNode if p exit 0 p data 10 p next NULL deletep structLNode intdata structLNode next 30 new与malloc的相同点和不同点 相同点 它们的作用都是在程序的执行过程中向系统申请存储空间 返回值都是申请到的存储空间的首地址 不同点 malloc是C编译系统提供的标准库函数 new是C 系统提供的运算符 new的操作效率要高于malloc 31 new不需要使用显式的sizeof函数就能知道类型的大小 而malloc需要明确指出所申请的空间的大小 总的字节数 new的返回值是指向名字类型的确定的指针类型 不需要强制说明 而malloc的返回值是一个指向void类型的指针类型 需要强制转换成指向具体数据类型的指针类型 当所申请的空间是一个变量所需的空间时 new运算符还可以为所申请的空间赋初值 malloc不具有此功能 32 7 3链表 计算机处理数据需要两方面的工作 一方面是对数据信息的描述 另一方面是对数据的操作 而操作的方式取决于数据的描述方式 数据的描述方式又取决于数据本身固有的内在联系 这里仅介绍数据之间的线性关系 线性表 线性表是n个数据元素的有限序列 各数据元素属于同一数据对象 相邻数据元素之间存在序偶关系 记为 a1 a2 ai ai 1 an 33 7 3链表 链表的定义链表的建立链表结点的插入链表结点的删除循环链表 34 线性表中的数据元素之间存在严格的顺序关系 有一个唯一的称为第一个的元素 首元 有唯一的称为最后一个的元素 尾元 其它元素都有唯一的直接后继元素和唯一的直接前趋元素 线性表这种逻辑结构在计算机内表示时 可以采用链式存储结构 即一个数据元素存放于一个结点中 不同的数据元素之间的先后顺序用结点的指针域链接 一个结点就是一个结构体类型的变量 35 链表的定义 链表是表示具有线性关系的一组数据元素的动态结构 每个数据元素占据一个独立申请的存储空间 这个存储空间通常是一个结构体型变量 主要包括两部分 一部分用来存放数据元素的值 称为值域 另一部分用来存放一个指向该结构体类型的指针变量值 称为指针域 指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址 36 数据元素结点的结构如图所示 单向链表和单向循环链表如下图所示 单向链表 单向循环链表 37 链表结点的C语句定义 首先用结构体类型描述一个数据元素结点 定义一个结点类型的语句格式 typedefstructLNode ElemTypedata structLNode next LNode LinkList 38 typedefstructNode ElemTypedata structNode next LNode LinkList 等价于structNode ElemTypedata structNode next typedefstructNodeLNode typedefstructNode LinkList 39 说明 typedef语句定义了一个结构体类型和链表类型 结构体指针类型 Node是一个结点的类型名称 它有两个成员 一个名称为data 类型为数据元素的类型 用来存放一个数据元素的值 另一个成员名称为next 类型为指向本结构体类型的指针类型 用来存放逻辑上排在本结点后面的结点的首地址 LNode类型等价于structNode类型 也等价于Node类型 LinkList类型等价于LNode的指针类型 ElemType是数据元素的类型的一般性描述 当我们具体写程序时 应该用确定类型名称来替换 例如 int float char等 40 例 链表中的数据元素用来存放整数 定义链表的结点类型的语句格式为 typedefstructNode intdata structNode next LNode LinkList 41 定义一个结点类型的变量的语句 structNodeq LNodeq 定义一个指向结点类型的指针变量的语句 structNode p LNode p LinkListL 访问结点变量的各个成员 q data q nextp data p nextL data L next 42 链表的建立 1 构造一个空线性链表首先 构造一个空的线性链表 为了描述方便 通常将链表的第一个结点空置 不存放数据元素 只是作为链表的开始标志 称为头结点 数据元素从链表的第二个结点开始存放 空的线性表定义为没有数据元素的表 一个空的线性链表就规定为 只有一个头结点的链表 所以 构造一个空的线性链表就是建立只有一个头结点的链表 43 算法描述 申请一个结点的空间 将该结点作为线性链表的头结点 将该结点的next域置空 44 程序 构造一个空的线性链表 LNode InitList LinkListL 头结点指针L LNode malloc sizeof LNode 申请一结点空间 if L exit 0 申请不成功 异常结束程序运行 L next NULL 申请成功 头结点的next域置空 return L 45 2 逆序输入n个数据元素 建立带表头结点的单向链表 现在开始建立一个非空的线性链表 这里所建的链表的第一个结点都是头结点 数据元素从链表的第二个结点开始存放 一个非空的线性链表是除了头结点以外至少有一个数据元素的链表 线性链表由若干个数据元素结点组成 那么 构造一个非空的线性链表的过程就是逐个建立数据元素结点 并将它们依次插入到链表中的过程 46 头插入 即每次将数据元素结点插入到表头结点的之后 第一个数据元素结点之前 插入过程如下图所示 初始状态 插入第一个结点之后 头结点 47 插入第二个结点之后 插入第三个结点之后 插入最后一个结点之后 48 LNode CreateList intn inti LNode p LinkListL 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 程序 头结点 头插入 49 链表结点的插入 将一个数据元素插入到链表中 有三种情况 头插入 尾插入以及在链表中的第i个数据元素的位置处插入 将一个新元素插入在链表的头结点的后面 其它的所有结点之前称为头插入 将一个新元素插入在链表的尾结点的后面 使得新插入的结点成为尾结点称为尾插入 将一个新元素插入在链表中的第i个数据元素的位置处 即插入在第i个数据元素结点之前 使得新插入的结点成为链表中的第i个结点 50 例 已有链表L如图所示 链表中的元素按递增有序排列 其中每个结点中存放的值为学生的考试成绩 现在有另外三个学生的的成绩分别为65 82 90 将他们插入到链表L中 要求插入之后链表依然递增有序 p L q 51 将65插入到链表L中 s p L q 头插入 52 将82插入到链表L中 s p L q 中间插入 53 将90插入到链表L中 s p L q 尾插入 54 实现语句 LNode p q s LinkListL 头结点指针q L p L next while p 55 程序 intListInsert LNode L inte LNode p q s if L return0 q L p L next while p 56 链表结点的删除 例 已有链表如图所示 删除链表中数据元素值为76的结点 q p L 57 q p L q p L q L 58 程序 intListDelete LNode L inte LNode q p if L return0 p L next q L while p 59 include include includestructNode intdata structNode next typedefstructNodeLNode typedefstructNode LinkList 综合程序 60 LNode CreateList intn 创建链表 inti LNode p LinkListL 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 61 intListInsert LNode L inte 插入元素 LNode p q s if L return0 q L p L next while p 62 intListDelete LNode L inte 删除元素 LN