C语言讲解.ppt

第十一章指针与结构体 学习用指针引用结构体的成员学习如何进行动态存储分配及管理掌握单链表的构造及操作方法了解循环链表和双向链表的构造和基本操作 11 1指针指向结构体 11 1 1指向结构体变量的指针结构体变量也有地址 指向结构体变量的指针中可以存放一个结构体类型变量所占内存单元的首地址 指向结构体变量的指针的说明形式为 结构体类型说明符 指针变量名 例如 定义一个结构体类型 structstudent charname 20 intnum intage floatscore 可以定义结构体类型的变量及指向结构体类型变量的指针 例如 structstudents1 structstudent p 定义一个结构体指针之后 编译程序只给其分配一个用于存放地址的空间 但它并没有具体的指向 必须将一个结构体变量的地址或结构体数组元素的地址赋给它 结构体变量的地址必须通过取地址符 结构体指针引用结构体变量有两种方法 一种是用圆点操作符 另一种是用箭头操作符 例如 p name或p name 结构体成员的引用是以圆点作为连接符的 例如 s1 name s1 age 若结构体指针p指向结构体变量x 则对结构体变量x成员的引用有3种方法 x 成员名 p 成员名p 成员名 说明 1 不可以写成 p name 因为 的级别高于 2 箭头运算符 是由一个减号和一个大于号组成 且运算优先级最高 结构体指针只能指向结构体类型的变量 不能指向其成员 分析下面几个运算p nump num p num 得到p指向的结构体中成员num的值 得到p指向的结构体中成员num的值 之后使该值加1 先使p指向的结构体中成员num的值加1 再使用它 3 结构体指针指向的变量进行输入输出操作 可用如下语句实现 scanf s d d f p name 11 1 2指针指向结构体数组 如果将结构体数组中某一元素的地址赋给结构体指针 那么结构体指针在进行加1之后可以指向数组的下一元素 例如 structstudentstu 20 p stu 如右图 例11 1 编程通过结构体指针完成对结构体数组中数据的I O main structstudent charname 20 intnum age floatscore structstudentstu 5 p stu p获得stu数组的首地址 inti floatx for i 0 iname 思考 如果没有e1行 程序执行时会出现什么问题 11 2结构体指针作函数参数 结构体变量作函数参数时 实参和形参各有自己的内存单元结构体指针也可以作函数参数形参为结构体类型的指针实参可为结构体类型变量的地址或结构体类型的指针 如果在函数内部对形参指针指向的结构体成员进行改变 则对应的实参结构体成员也会发生变化 因为传给形参的只是结构体变量的地址 而不是整个结构体变量 从而减少了内存的开辟 includestructstudent charname 15 intnum intscore 3 floatave voidaverage structstudent q voidmain structstudent p s 5 inti p s printf inputname num score0 score1 score2 n for i 0 iname 例11 2 有5个学生 信息包括 学号 姓名 三门课的成绩 编函数求每个学生的平均成绩 voidaverage structstudent q inti for i 0 iave q score 0 q score 1 q score 2 3 printf 20s 5d 5d 5d 5d 7 2f n q name q num q score 0 q score 1 q score 2 q ave q 求平均值 指针后移 例11 3 编写一个有计时器功能的程序 在屏幕上显示时 分 秒 include stdio h structmy time inthours intminutes intseconds voiddisplay structmy time t voidupdate structmy time t voiddelay main structmy timetime time hours 0 time minutes 0 time seconds 0 while 1 update voidupdate structmy time t t seconds if t seconds 60 t seconds 0 t minutes if t minutes 60 t minutes 0 t hours if t hours 24 t hours 0 delay voiddelay longinti for i 1423000 ihours t minutes t seconds 11 3链表 11 3 1动态存储分配 程序中使用的变量和数组的类型 数目和大小是在编写程序时由程序员确定下来的 因此在程序运行时这些数据占据的存储空间数也是一定的 这种存储分配方式叫静态存储分配 缺点是程序无法在运行时根据具体情况 如用户的输入 灵活调整存储分配情况 根据需要在程序执行过程中临时申请所需内存单元 不需要时又释放这些内存单元 由系统将这些内存单元回收起来又可以分配给其他的数据使用 这种存储分配方式称动态存储分配 优点可灵活的申请和释放内存 常用的动态数据结构有链表 树 图等 鉴于大家是初学者 在此只介绍链表 C语言的库函数中包含了一组可以在程序执行期间临时分配和回收单元的库函数 在以后的操作中会经常用到 这些函数的原形在头文件stdlib h或malloc h中 1 malloc函数函数原型 void malloc unsignedintsize 功能 在内存中开辟size个字节的存储空间 并将此存储空间的首地址作为函数值返回 如果内存空间不够大 申请不到size个字节的内存空间 则函数返回空指针NULL 说明 1 形参size为无符号整型量 用来指定要申请的空间的大小 例如malloc 16 可开辟一个长为16个字节的内存空间 2 函数的返回值为void型指针 也就是说不规定指向任何具体的类型 如果想把这个指针值赋给某一类型的指针变量 则要强制类型转换 例如 char cp cp char malloc 16 申请的16个字节的首地址转换为字符指针 则16个字节可以存放16个字符 cp也可以看作是含有16个元素的数组名 int p p int malloc 16 申请的16个字节的首地址转换为整形指针 则16个字节可以存放4个整数 p也可以看作是含有4个元素的数组名 动态存储分配函数malloc void malloc unsignedsize 在内存的动态存储区中分配一连续空间 其长度为size若申请成功 则返回一个指向所分配内存空间的起始地址的指针若申请不成功 则返回NULL 值为0 返回值类型 void 通用指针的一个重要用途将malloc的返回值转换到特定指针类型 赋给一个指针 malloc 示例 int ip int malloc sizeof int structstudent p p structstudent malloc sizeof structstudent 调用malloc时 用sizeof计算存储块大小虽然存储块是动态分配的 但它的大小在分配后也是确定的 不要越界使用 2 calloc函数函数原型 void calloc unsignedintnum unsignedintsize 功能 在内存中开辟多个指定大小的存储空间 并将该空间的首地址返回 如果内存空间不够大 申请不到所需的字节数 则函数的返回值为空 NULL 说明 1 形参num和size均为无符号整型量 表示分配num个size大小的存储空间 且这些内存空间是连续的 例如calloc 5 8 表示申请5个大小为8字节的存储空间 即40个字节的内存空间 2 函数的返回值为void型 同malloc 函数一样 如果想把这个返回值赋给其它类型的指针变量 则要强制类型转换 3 calloc 函数申请的内存空间会清0 通常上述两个函数的典型使用为 通过sizeof 计算某类型数据所占的字节数 然后申请若干倍的空间 并将首地址赋给指针 例如 double ptr double malloc sizeof double 10 或double ptr double calloc 10 sizeof double 申请了一个可以存放10个双精度数的存储空间 并将首地址送给ptr 以后ptr可以当做一个有10个元素的双精度数组使用 例如 for i 0 i 10 i ptr i i 相当于 ptr i i 3 realloc 函数函数原型 void realloc void ptr unsignedintsize 功能 改变已分配的存储空间的大小 说明 1 将ptr指向的存储空间的大小改为size字节 ptr必须是用malloc 或calloc 函数分配的 size与原来的存储空间比可大可小 该函数返回新分配的存储空间的首地址 4 free 函数函数原型 voidfree void ptr 功能 将ptr指向的存储空间释放 交由系统再分配 说明 ptr必须是由申请函数所返回的地址 free函数无返回值 例如 free ptr 动态存储释放函数free 当某个动态分配的存储块不再用时 要及时将它释放voidfree void ptr 释放由动态存储分配函数申请到的整块内存空间 ptr为指向要释放空间的首地址 free ip free p 动态输入多个字符串 示例 用动态分配内存的方法处理多个字符串的输入示例例11 4输入一些球的颜色 以 作为输入结束标志 再输出这些颜色 其中颜色数小于20 颜色的英文名称不超过10个字符 include include includeintmain void inti n 0 char color 20 str 10 printf 请输入颜色名称 每行一个 结束输入 n scanf s str while str 0 color n char malloc sizeof char strlen str 1 strcpy color n str n scanf s str printf 你输入的颜色是 for i 0 i n i printf s color i return0 请输入颜色名称 每行一个 结束输入 redblueyellow 你输入的颜色是 redblueyellow 例11 5修改 动态分配内存 include includechar change d chars 20 intmain void inti chars 4 20 p NULL printf 请输入藏头诗 n for i 0 i 4 i scanf s s i p change d s printf s n p return0 char change d chars 20 inti char head p p char calloc 9 sizeof char head p for i 0 i 4 i p s i 0 p s i 1 p 0 returnhead 11 3 2学生信息管理的链表实现 一 程序解析二 链表的概念三 单向链表的常用操作 一 程序解析 例11 6建立一个学生成绩信息 包括学号 姓名 成绩 的单向链表 学生记录按学号由小到大顺序排列 要求实现对成绩信息的插入 修改 删除和遍历操作 例11 6数据定义与函数声明 structstud node 链表结点类型 intnum charname 20 intscore structstud node next structstud node Create Stu Doc 新建链表 structstud node InsertDoc structstud node head structstud node stud 插入 structstud node DeleteDoc structstud node head intnum 删除 voidPrint Stu Doc structstud node head 遍历 二 链表的概念 一种动态存储分布的数据结构若干个同一结构体类型的 结点 依次串接而成单向链表 双向链表 头指针 结点 尾结点 链表的概念 结点定义 structstud node intnum charname 20 intscore structstud node next 结构体的递归定义 链表是一种常见的重要的数据结构 它是动态存储分配的一种 最简单的链表叫单链表 其构造如图所示 由若干个结点构成 每个结点具有相同的类型 头指针 head 用来存放链表中第一个结点的地址 每一个结点是一个结构体类型的数据 结构体中必须有一个成员其类型为指向结构体的指针 用以存放下一结点的地址 其它成员可根据需要而设置 最后一个结点中存放空指针 NULL 代表链表的表尾 也是对链表进行访问时的结束标志 链表的概念 与数组比较 数组事先定义固定长度的数组在数组元素个数不确定时 可能会发生浪费内存空间的情况链表动态存储分配的数据结构根据需要动态开辟内存空间 比较方便地插入新元素 结点 使用链表可以节省内存 提高操作效率 用链表存储和用数组存储的主要区别是 1 数组的元素个数是固定的 而组成链表的结点个数可按需要增加或减少 2 数组元素的存储单元在数组定义时分配 属于静态分配 链表结点的存储单元在程序执行时根据需要随时申请 属于动态分配 3 数组中的元素顺序关系由元素在数组中的位置即下标确定 链表中的结点顺序关系由结点所包含的指针来体现 4 为保证数组中元素的连续性 数组中插入或删除元素需要移动大量的元素 而链表中插入删除元素只需要修改几个指针即可 上述单链表中结点类型的定义如下 structnode intnum 可根据需要设置 structnode next 必须有 定义结构体类型之后 就可以定义指向结构体类型的指针变量 例如 structnode head p 编译系统只是给指针变量head分配了存储空间 而head并没有具体的指向 从图可以看到 一个链表只有一个头指针 从头指针开始沿着结点的成员next可以访问到链表中的所有结点 例如 要访问链表中第一个结点的各成员 可以表示为 head num和head nexthead next为指向第二个结点的指针 要访问链表中第二个结点的各成员 可以表示为 head next num和head next next可以看到 head和head next的类型一样 如果要将一头指针为head的链表中的所有结点的数据输出 可用下面的语句实现 p head while p NULL printf d p num p p next p将指向下一个结点 也可用下面的语句实现 while head NULL printf d head num head head next 两者的区别为 前者在输出完数据后head还指向链表的表头 而后者在输出完数据后head已经指向NULL 三 单向链表的常用操作 1 链表的建立2 链表的遍历3 插入结点4 删除结点 1 链表的建立 structstud node head tail p head tail NULL size sizeof structstud node p structstud node malloc size head tail tail p 链表的建立 程序段 head tail NULL scanf d s d 2 链表的遍历 ptr numptr score for ptr head ptr NULL ptr ptr next printf ld d ptr num ptr score ptr ptr next 链表的遍历 函数 voidPrint Stu Doc structstud node head structstud node ptr if head NULL printf nNoRecords n return printf nTheStudents RecordsAre n printf NumNameScore n for ptr head ptr NULL ptr ptr next printf 8d 20s 6d n ptr num ptr name ptr score s next ptr2ptr1 next s先连后断 head 3 插入结点 ptr2 ptr1 nextptr1 next ptr2 next free ptr2 先接后删 4 删除结点 11 3 3环形链表和双向链表指针的用途非常广泛 除了单链表以外 还有环形链表和双向链表 1 环形链表 循环链表 如果有一个单链表其表尾指针的next域的值不为NULL 而让它指向头结点 这样的链表叫环形链表 环形链表的许多操作都和单链表相同 唯一不同的是判断链表是否结束的条件不同 在单链表中当某一结点的next域指向NULL时 则说明链表操作结束 而在环形链表中没有指向NULL的指针 链表操作