C语言-链表.ppt

1 11 7用指针处理链表1 链表概述1 动态数据结构概念数组和结构体是定长数据结构 而链表 堆栈 队列 树 图等是执行时大小可变的动态数据结构 链表是连成一行的数据项集合 每一个数据项 元素 称为节点 可以在链表中的任意位置进行节点插入或删除操作 使链表数据项的个数随之增加或减少 2 2 链表的构成单向链表图示 104813701012头节点表内节点尾节点 head 其中 各节点是相同的结构体类型 该类型有三个成员 head是指针变量 存放链表的头节点指针1048 各节点应包含一个指针成员存放下一节点的地址 各节点存储有可能不连续 但各节点逻辑上连续 3 3 节点的构成上图每个节点具有如下结构体类型 structstudent longnum floatscore structerstudent next 链节成员 其中 成员num score用于存放一个节点的具体数据 成员next是指针类型 用于存放下一节点指针 最后一个节点的next成员存放空指针NULL 成员next是指向与自身同一类型的结构 这种结构称为自引用结构 只有指针成员可自引用 节点是在运行时动态生成的 4 4 动态内存分配和释放建立和维护动态数据结构需要实现动态内存分配 如在链表中插入节点需要先申请一段存储区域 而删除一个节点需要释放该节点原先占用的存储区域 这可由标准函数实现 内存分配函数原形 void malloc unsignedsize 功能 申请长度为size个字节的内存空间 若申请成功 返回存储块起始指针 该指针类型为void 否则返回空指针 NULL 内存释放函数原形 voidfree void p 功能 释放p所指向的内存块 包含文件 malloc h stdlib h中均有其原型声明 5 5 采用链表的意义 与定长数据结构数组相比 链表能更好地利用内存 按需分配和释放存储空间 在链表中插入或删除一个节点 只需改变某节点 链节 成员的指向 而不需要移动其它节点 相对数组元素的插入和删除效率高 即 链表特别适合于对大线性表频繁插入和删除元素 或成员数目不定的数据结构 6 6 链表的类型单链表 每个节点只有一个指向后继节点的指针双向链表 每个节点有两个用于指向其它节点的指针 一个指向前趋节点 一个指向后继节点循环链表 使最后一个节点的指针指向第一个节点 7 2 单链表的建立和输出建立链表的准备工作 1 定义链表的节点类型 2 定义与节点同类型的链表头指针变量head并赋值0 表示链表在建立之前是空的 3 定义与节点同类型的工作指针变量p1 p2 8 建立链表的步骤 1 开辟第一个节点的存储区域 使head p1 p2指向第一个节点 并输入第一个节点数据 head p2 操作 len sizeof structstudent p1 structstudent malloc len scanf ld f 9 2 开辟下一节点的存储区域 使p1指向新节点 输入新节点数据 并将上一个节点的next成员指向新节点 head p1 1048 操作 p1 structstudent malloc len scanf ld f 使p2也指向新节点 1370 1370 10 3 重复第2步 建立并链接多个节点直至所需长度 将末尾节点的next成员赋值0 head p2 NULL 10481370 操作 p1 structstudent malloc len scanf ld f 末尾节点next赋值0 11 例 建立并输出有3名学生数据的单链表 include 包含NULL的定义 include defineN3structstudent 结构体类型定义 longnum floatscore structstudent next 自引用结构体指针 voidmain 12 voidmain structstudent head p1 p2 inti len sqrt 5 5 TC激活浮点运算 head NULL head不指向任何位置 len sizeof structstudent 求类型长 for i 1 inum 标记末尾节点 13 voidmain for i 1 inext p1指向下一节点 printf d num ld score 5 2f n i p1 num p1 score main 14 例 将上题利用函数实现 并求平均成绩 定义如下函数 建立链表函数 structstudent create void 输出链表函数 voidplink structstudent head 求平均值函数 floataverf structstudent head 函数间信息传递 主函数 create plink averf 无参 头指针 头指针 无返回值 平均值 头指针 15 include include defineN3structstudent 全局结构类型 longnum floatscore structstudent next voidmain 16 voidmain structstudent head create void voidplink structstudent head floataverf structstudent head inti len floataver sqrt 5 5 clrscr TC中使用head NULL head create 返回链表头指针 plink head aver averf head 返回平均值 printf Average 5 2f n aver 17 structstudent create structstudent head p1 p2 inti len len sizeof structstudent for i 1 inum 返回链表头指针 18 voidplink structstudent head 输出各节点 structstduent p inti for i 1 inext printf d num ld score 5 2f n i p num p score return P P 19 floataverf structstudent head structstudent p floatsum 0 intc 0 p head 使p指向首节点 while p NULL c c统计节点数 sum sum p score p p next return sum c 返回平均值 20 1370 3 节点的删除步骤 从头节点开始按查找关键字查找要删除的节点 2 找到 则将要删除节点的 链节 成员赋给前一节点的 链节 成员 使删除的节点脱离链表 若 要删除节点为首节点 则将首节点 链节 成员赋给链头指针变量 3 释放已被删除节点占用的空间 10481012 head p NULL 1048 1012 21 例 按上例删除指定学号的节点structstudent del structstudent head longn structstudent p1 p2 n 要删除学号 p1 head if p1 num n head p1 next 删除首节点 else do p2 p1 p1 p1 next 继续找 while p1 NULL 返回头指针 22 voidplink structstudent head 更具通用性 structstudent p p head while p NULL printf num ld score 5 2f n p num p score p p next return 注 本形式的链表输出函数具有通用性 可适应由于删除或插入节点引起的链表长度的变化 23 4 节点的插入插入可分为随意插入和按顺序插入 随意插入包括插入到头部 尾部或中间指定位置 按顺序插入是指按某关键字的顺序插入 而在插入前链表必须已按该关键字进行了排序 按顺序插入的步骤 开辟待插入节点的存储区域并输入数据 2 查找插入位置 从链表首节点开始按关键字成员与待插入节点相同成员进行比较 直到确定了插入位置 24 3 将插入位置前一节点的 链节 成员赋给待插入节点的 链节 成员 若 插入点在链头 则将头指针赋给待插入节点的 链节 成员 4 将待插入节点的指针赋给前一节点 链节 成员 若 插入点在链头 先将头指针赋给插入节点的指针域 再将待插入节点的指针赋给头指针变量 head 1048 104813701012 1012 2680 2680 25 例 按上例在链表中按学号顺序插入节点插入函数 structstudent insert structstudent head structstudent p0 p1 p2 longn intlen len sizeof structstudent p0 structstudent malloc len 申请新节点 printf Enternum scoretoinsert scanf ld f 从首节点开始查找 26 p1 head 插入在头部 if nnum p0 next head head p0 else do 查找插入位置 p2 p1 p1 p1 next while p1 NULL insert 27 例 编写一个通用的函数 可根据需要建立任意节点数的链表 structstu