C语言链表详解ppt课件

《C语言链表详解ppt课件》由会员分享，可在线阅读，更多相关《C语言链表详解ppt课件（92页珍藏版）》请在金锄头文库上搜索。

1、1 第十一章链表链表详解珍藏版 2 例 跳马 依下图将每一步跳马之后的位置 x y 放到一个 结点 里 再用 链子穿起来 形成一条链 相邻两结点间用一个指针将两者连到一起 结构的概念与应用 3 依上图有7个结点 为了表示这种既有数据又有指针的情况 引入结构这种数据类型 4 11 7用指针处理链表 链表是程序设计中一种重要的动态数据结构 它是动态地进行存储分配的一种结构 动态性体现为 链表中的元素个数可以根据需要增加和减少 不像数组 在声明之后就固定不变 元素的位置可以变化 即可以从某个位置删除 然后再插入到一个新的地方 5 1 链表中的元素称为 结点 每个结点包括两个域 数据域和指针域 2 单

2、向链表通常由一个头指针 head 用于指向链表头 3 单向链表有一个尾结点 该结点的指针部分指向一个空结点 NULL Head1249135614751021 结点里的指针是存放下一个结点的地址 6 链表中结点的定义 链表是由结点构成的 关键是定义结点 链表的结点定义打破了先定义再使用的限制 即可以用自己定义自己 递归函数的定义也违反了先定义再使用 这是C语言程序设计上的两大特例 7 链表的基本操作 对链表的基本操作有 1 创建链表是指 从无到有地建立起一个链表 即往空链表中依次插入若干结点 并保持结点之间的前驱和后继关系 2 检索操作是指 按给定的结点索引号或检索条件 查找某个结点 如果找到

3、指定的结点 则称为检索成功 否则 称为检索失败 3 插入操作是指 在结点ki 1与ki之间插入一个新的结点k 使线性表的长度增1 且ki 1与ki的逻辑关系发生如下变化 插入前 ki 1是ki的前驱 ki是ki 1的后继 插入后 新插入的结点k 成为ki 1的后继 ki的前驱 8 4 删除操作是指 删除结点ki 使线性表的长度减1 且ki 1 ki和ki 1之间的逻辑关系发生如下变化 删除前 ki是ki 1的前驱 ki 1的后继 删除后 ki 1成为ki 1的前驱 ki 1成为ki 1的后继 5 打印输出 9 一个指针类型的成员既可指向其它类型的结构体数据 也可以指向自己所在的结构体类型的数据

4、 numScorenext next是structstudent类型中的一个成员 它又指向structstudent类型的数据 换名话说 next存放下一个结点的地址 10 11 7 2简单链表 defineNULL0structstudent longnum floatscore structstudent next main structstudenta b c head p a num 99101 a score 89 5 b num 99103 b score 90 c num 99107 c score 85 head 例11 7 建立和输出一个简单链表 各结点在程序中定义 不是临时

5、开辟的 始终占有内容不放 这种链表称为 静态链表 11 11 7 3处理动态链表所需的函数 C语言使用系统函数动态开辟和释放存储单元 1 malloc函数 函数原形 void malloc unsignedintsize 作用 在内存的动态存储区中分配一个长度为size的连续空间 返回值 是一个指向分配域起始地址的指针 基本类型void 执行失败 返回NULL 12 函数原形 void calloc unsignedn unsignedsize 作用 在内存动态区中分配n个长度为size的连续空间 函数返回值 指向分配域起始地址的指针执行失败 返回null主要用途 为一维数组开辟动态存储空间

6、n为数组元素个数 每个元素长度为size 2 calloc函数 13 3 free函数 函数原形 voidfree void p 作用 释放由p指向的内存区 P 是最近一次调用calloc或malloc函数时返回的值 free函数无返回值动态分配的存储单元在用完后一定要释放 否则内存会因申请空间过多引起资源不足而出现故障 14 结点的动态分配 ANSIC的三个函数 头文件malloc h void malloc unsignedintsize void calloc unsignedn unsignedsize voidfree void p C 的两个函数new类型 初值 delete 指针

7、变量 表示释放数组 可有可无 使用new的优点 可以通过对象的大小直接分配 而不管对象的具体长度是多少 p340例14 10 15 11 7 4建立动态链表 基本方法 三个结点 头结点head 尾结点NULL和待插入结点P 第一步 定义头结点head 尾结点p2和待插入结点p1 待插入的结点数据部分初始化 第二步 该结点被头结点 尾结点同时指向 P1 p2 structstudent malloc LEN 头指针部分为空 head NULL 第三步 重复申请待插入结点空间 对该结点的数据部分赋值 或输入值 将该结点插入在最前面 或者最后面 书上在尾部插入 P2 next P1 P2 P1 最后

8、 P2 next NULL head p1 p2 使用malloc LEN P2 next NULL 16 11 7 4建立动态链表 head P1p2 1 任务是开辟结点和输入数据2 并建立前后相链的关系 待插入的结点p1数据部分初始化 该结点被头结点head 尾结点p2同时指向 17 图11 14 head p2 p1 head p2 p1 a b p1重复申请待插入结点空间 对该结点的数据部分赋值 或输入值 P2 next指向p1新开辟的结点 18 图11 14 head p1 p2 c P2指向新结点p2 p1 19 图11 15 p2 p1 head p2 p1 head a b 2

9、0 图11 16 p2 p1 head p2 p1 head 21 例11 8建立一个有3名学生数据的单向动态链表 defineNULL0 defineLENsizeof structstudent structstudent longnum floatscore structstudent next intn structstudent creat void structstudent head structstudent p1 p2 n 0 p1 p2 structstudent malloc LEN scanf 1d f 结构体类型数据的长度 sizeof是 字节数运算符 定义指针类型的

10、函数 带回链表的起始地址 开辟长度为LEN的内存区 P1 p2是指向结构体类型数据的指针变量 强行转换成结构体类型 假设头指向空结点 22 续 while p1 num 0 n n 1 n是结点的个数 if n 1 head p1 elsep2 next p1 p2 p1 p1 structstudent malloc LEN scanf 1d f 返回链表的头指针 算法 p1指向新开的结点 p1 stuctstudent malloc LEN p1的所指向的结点连接在p2所指向结点后面 用p2 next p1来实现 p2指向链表中最后建立的结点 p2 p1 头指针指向p1结点 P1开辟的新结

11、点链到了p2的后面 P1继续开辟新结点 给新结点赋值此 23 11 7 5输出链表 链表遍历1 单向链表总是从头结点开始的 2 每访问一个结点 就将当前指针向该结点的下一个结点移动 p p next 3 直至下一结点为空P NULL 24 图11 18 head p P P 25 例题9 voidprint structstudent head structstudent p printf nNow These drecordsare n n p head if head NULL do printf ld 5 lf n p num p score p p next while p NULL

12、26 11 7 6对链表的删除操作 删除结点原则 不改变原来的排列顺序 只是从链表中分离开来 撤消原来的链接关系 两种情况 1 要删的结点是头指针所指的结点则直接操作 2 不是头结点 要依次往下找 另外要考虑 空表和找不到要删除的结点 27 链表中结点删除 需要由两个临时指针 P1 判断指向的结点是不是要删除的结点 用于寻找 P2 始终指向P1的前面一个结点 28 图11 19 a B 29 图11 20 head p1 a b head p2 p1 原链表P1指向头结点 P2指向p1指向的结点 P1指向下移一个结点 30 图11 20 head p1 head p2 p1 c d 经判断后

13、第1个结点是要删除的结点 head指向第2个结点 第1个结点脱离 经P1找到要删除的结点后使之脱离 31 例题10 structstudent del structstudent head longnum structstudent p1 p2 if head NULL printf nlistnull n gotoend p1 head while num p1 num 找到了 没找到 32 11 7 7对链表的插入操作 插入结点 将一个结点插入到已有的链表中插入原则 1 插入操作不应破坏原链接关系2 插入的结点应该在它该在的位置实现方法 应该有一个插入位置的查找子过程共有三种情况 1 插入

14、的结最小2 插入的结点最大3 插入的结在中间 33 操作分析 同删除一样 需要几个临时指针 P0 指向待插的结点 初始化 p0 数组stu P1 指向要在P1之前插入结点 初始化 p1 head P2 指向要在P2之后插入结点 插入操作 当符合以下条件时 p0 num与p1 num比较找位置if p0 num p1 num 34 图11 22 head p1 a p0 35 图11 22 p1 b 36 例题11 structstudentinsert structstudent head structstudent stud structstudent p0 p1 p2 p1 head p0

15、 stud if head NULL head p0 p0 next NULL elsewhile p0 num p1 num 原来的链表是空表 P0指向要插的结点 使p0指向的结点作为头结点 使p2指向刚才p1指向的结点 插到原来第一个结点之前 插到p2指向的结点之后 插到最后的结点之后 链接 37 head 课堂举例 已有一个如图所示的链表 它是按结点中的整数域从小到大排序的 现在要插入一个结点 该结点中的数为10 待插入结点 此结点已插入链表 38 分析 按三种情况1 第一种情况 链表还未建成 空链表 待插入结点p实际上是第一个结点 这时必然有head null 只要让头指针指向p就可以

16、了 语句为 headp head p p next null 2 第二种情况 链表已建成 待插入结点p的数据要比头结点的数据还要小 这时有 p num num 当然p结点要插在head结点前 39 head head p p next head head p 语句为 null 40 3 第三种情况 链表已建成 待插入结点p的数据比头结点的数据大 需要找到正确的插入位置 这时 可以借助两个结构指针r和g 利用循环比较来找到正确位置 然后将结点p插入到链表中正确的位置 参见下面的图示 41 head p g r 说明 这种情况下 p结点已经与链表的第一个结点比较过了 所以从链表的下一个结点开始比较 13 8 继续比较 42 head p g r 说明 13 12 继续比较 43 head p g r null 说明 13 15 找到了正确的插入位置 则插入结点p 语句为 r next p p next g 44 结构7 c include 预编译命令 include 内存空间分配 definenull0 定义空指针常量 defineLENsizeof structnumST 定义常量 表示