结构体数组学习.ppt

一 结构体数组 形式一 间接定义structstudent intnum charname 20 studentstu 2 形式二 直接定义structstudent intnum charname 20 stu 2 形式三 无名定义struct intnum charname 20 stu 2 结构数组的初始化 顺序初始化 structstudent intnum charname 20 intage studentstu 200401 WangYong 19 200402 LiGang 20 如果对所有数组元素赋初值 则数组元素个数可省略 分行初始化 structstudent intnum charname 20 intage studentstu 200401 WangYong 19 200402 LiGang 20 结构数组的引用 引用形式 结构数组名 下标 成员名 结构数组元素 成员名 例如 stu 0 num structstudent intnum charname 20 charsex intage stu 3 stu 1 age cin stu 0 name strcpy stu 0 name ZhaoDa cin stu 1 num EXAMPLE2 Sortbystudent aver include include includeusingnamespacestd structGrade ints1 ints2 ints3 floataver structStudentRec intnum stringname Grades typedefstructStudentRecSTUDENT STUDENTinputstu int voidsort STUDENTstu int voidmain STUDENTstu 6 for inti 0 i 0 i cout 6 i stu i num setw 6 left stu i name stu i s aver endl 声明结构体数组 用结构体数组名作实参 voidsort STUDENTstu intn inti j min STUDENTt for i 0 i n i min i for j i 1 j n j if stu j s aver stu min s aver min j t stu i stu i stu min stu min t 用结构体数组名作形参 选择法排序 指针不仅可以指向普通变量 数组 数组元素 函数 同样的 指针也可以指向结构变量 我们把指向结构变量的指针称为结构指针 结构指针指向了结构变量所在存储空间的起始地址 二 结构体指针 定义形式 结构类型名 结构指针名 使用结构指针引用结构成员 方法一 结构指针 成员名方法二 结构指针 成员名结构指针的运算 1 指向结构变量的指针 指针不仅可以指向普通变量 数组 数组元素 函数 同样的 指针也可以指向结构变量 我们把指向结构变量的指针称为结构指针 结构指针指向了结构变量所在存储空间的起始地址 二 结构体指针 定义形式 结构类型名 结构指针名 使用结构指针引用结构成员 方法一 结构指针 成员名方法二 结构指针 成员名结构指针的运算 1 指向结构变量的指针 s num structstudent intnum charname 20 charsex intage studentstu student s 指针不仅可以指向普通变量 数组 数组元素 函数 同样的 指针也可以指向结构变量 我们把指向结构变量的指针称为结构指针 结构指针指向了结构变量所在存储空间的起始地址 定义形式 结构类型名 结构指针名 使用结构指针引用结构成员 方法一 结构指针 成员名方法二 结构指针 成员名结构指针的运算 1 指向结构变量的指针 s num s是结构指针 s 表示s指向的结构变量stu s num表示s所指的结构变量中的成员num 所以 s num的意义是先访问结构指针所指向的结构变量 再访问该结构变量中的成员 由于结构成员运算符 优先于指针运算符 故 s num中的括号 不能省略 s num 指向结构成员运算符优先级和 同级别结合性是左结合 指针不仅可以指向普通变量 数组 数组元素 函数 同样的 指针也可以指向结构变量 我们把指向结构变量的指针称为结构指针 结构指针指向了结构变量所在存储空间的起始地址 定义形式 结构类型名 结构指针名 使用结构指针引用结构成员 方法一 结构指针 成员名方法二 结构指针 成员名结构指针的运算 1 指向结构变量的指针 s num s num 常用运算符的优先级顺序 一级运算符 单目运算符 sizeof 类型 算术运算符 关系运算符 逻辑运算符 条件条件符 赋值运算符 逗号运算符 访问结构变量中的结构成员共有三种方式 结构变量 成员名stu num 结构指针 成员名 s num 结构指针 成员名s num 指针不仅可以指向普通变量 数组 数组元素 函数 同样的 指针也可以指向结构变量 我们把指向结构变量的指针称为结构指针 结构指针指向了结构变量所在存储空间的起始地址 定义形式 结构类型名 结构指针名 使用结构指针引用结构成员 方法一 结构指针 成员名方法二 结构指针 成员名结构指针的运算 1 指向结构变量的指针 s num s num 结构指针指向的是结构变量所在存储空间的首地址 将结构指针加1 则指针指向内存中下一个结构变量 其地址的增加量取决于指针所指向的结构的长度 coutnum 输出结构成员num的值 coutnum 先输出结构成员num的值 然后将该值加1 coutnum 先取结构成员num的值 然后将该值加1 之后再输出 coutnum 先输出num的值 然后指针加1 指向下一个结构变量 在C 语言中 把指向结构数组或数组元素的指针称为结构数组指针 includestructstudent intnum charname 20 floatscore 2 指向结构体数组的指针 例使用结构数组指针输出数据 voidmain studentstu 3 1001 LiuJin 75 1002 LiLan 82 1003 MaKai 80 student s stu coutnumnamescore endl 程序的运行结果为 NumNameScore1001LiuJin751002LiLan821003MaKai80 注意 1 如果s的初值为stu 即指向第一个元素stu 0 则s 1后指向下一个元素stu 1 的起始地址 2 程序中已定义了指针s是指向structstudent类型数据的变量 它只能指向一个structstudent型的数据 而不能指向stu数组元素中的某一个成员 三 动态分配内存 通常定义变量 或对象 编译器在编译时都可以根据该变量 或对象 的类型知道所需内存空间的大小 从而系统在适当的时候为他们分配确定的存储空间 这种内存分配称为静态存储分配有些操作对象只有在程序运行时才能确定 这样编译器在编译时就无法为他们预定存储空间 只能在程序运行时 系统根据运行时的要求进行内存分配 这种方法称为动态存储分配 所有动态存储分配都在堆区中进行 当程序运行到需要一个动态分配的变量或对象时 必须向系统申请取得堆中的一块所需大小的存贮空间 用于存贮该变量或对象 当不再使用该变量或对象时 也就是它的生命结束时 要显式释放它所占用的存贮空间 这样系统就能对该堆空间进行再次分配 做到重复使用有限的资源 new运算符用于申请所需的内存空间 返回指定类型的一个指针 常量 即内存空间首地址 它的语法格式为 指针变量 new数据类型 其中 指针变量应预先声明 指针变量指向的数据类型与new后面的数据类型相同 若申请成功 则返回分配空间的首地址赋给指针变量 否则 如没有足够的内存空间 返回0 NULL一个空指针 例如 int p p newint 20 系统为指针p开辟了一个用来保存int类型数据的内存空间 在申请时 也可以进行初始化 new运算符 在C 中 申请和释放堆中分配的存贮空间 分别使用new和delete的两个运算符来完成 其使用的格式如下 例如 int p p newint 20 系统为指针p开辟了一个用来保存int类型数组的内存空间 数组中有20个元素 也可以用new运算符申请一块保存数组的内存空间 即动态创建一个数组 格式为 指针变量 new数据类型 数组大小 其中 数组大小给出数组元素的个数 指针指向分配的内存空间首地址 指针的类型与new后的数据类型相同 new运算符 当程序中不再使用由运算符new申请的某个内存空间时 可以用delete运算符释放它 它的语法格式为 delete指针变量 delete 常量 指针变量 它的功能是释放由new申请到的内存空间 其中指针变量是指向需要释放内存空间的指针变量名字 并且delete只是删除动态内存空间 并不是将指针变量本身删除 常量可以省略 且不用考虑数组的维数 int p1 newint int p2 newint 20 deletep1 delete p2 delete运算符 1 new运算符返回的是一个指向所分配类型变量 对象 的指针 对所创建的变量或对象 都是通过该指针来间接操作的 而动态创建的对象本身没有名字 2 一般定义变量和对象时要用标识符命名 称命名对象 而动态所创建的变量或对象称无名对象 堆区是不会自动在分配时做初始化的 包括清零 所以必须用初始化式 来显式初始化 但不可对动态数组初始化 3 指针变量 new数据类型 数组大小 请注意 数组大小 不是常量表达式 即它的值不必在编译时确定 可以在运行时确定 变量n在编译时没有确定的值 而是在运行中输入 按运行时所需分配堆空间 这一点是动态分配的优点 可克服数组 大开小用 的弊端 在表 排序与查找中的算法 若用动态数组 通用性更好 说明 4 动态分配失败 返回一个空指针 NULL 表示发生了异常 堆资源不足 分配失败 因此 一定要检查分配的内存指针是否为空 如果是空指针 则不能引用这个指针 否则将造成系统崩溃 说明 int p newint 20 if p NULL else 5 指针删除与堆空间释放 删除一个指针p 实际意思是删除了p所指的目标 变量或对象等 释放了它所占的堆空间 而不是删除 本身 释放堆空间后 成了空悬指针 6 动态分配的变量或对象的生命期 无名对象的生命期并不依赖于建立它的作用域 比如在函数中建立的动态对象在函数返回后仍可使用 我们也称堆空间为自由空间 freestore 就是这个原因 但必须记住释放该对象所占堆空间 并只能释放一次 在函数内建立 而在函数外释放是一件很容易失控的事 往往会出错 说明 7 内存泄漏 memoryleak 和重复释放 new与delete是配对使用的 delete只能释放堆空间 如果new返回的指针值丢失 则所分配的堆空间无法回收 称内存泄漏 同一空间重复释放也是危险的 因为该空间可能已另分配 所以必须妥善保存new返回的指针 以保证不发生内存泄漏 也必须保证不会重复释放堆内存空间 链表是一种最常见的数据结构 分为动态链表和静态链表 程序员经常使用的是动态链表 它能进行动态内存分配 可以适应数据动态增减的情况 并且可以方便地进行数据元素的插入 删除等操作 链表有单向链表 双向链表 循环链表等形式 下图是一个单向链表的结构示意图 四 用指针处理链表 链表是一种最常见的数据结构 分为动态链表和静态链表 程序员经常使用的是动态链表 它能进行动态内存分配 可以适应数据动态增减的情况 并且可以方便地进行数据元素的插入 删除等操作 链表有单向链表 双向链表 循环链表等形式 下图是一个单向链表的结构示意图 8 6用指针处理链表 头指针 每个链表都有一个 头指针 变量 图中以head表示 它存放一个地址 指向链表的第一个元素 结点 链表中每一个元素被称为一个 结点 node 每个结点都应包含两部分 第一部分是链表中存放的用户需要用的实际数据 在图中以 表示 第二部分是一个地址 指向下一个结点 表尾 链表中最后一个结点称为 表尾 表尾结点存放一个NULL 表示空地址 因此该结点不再指向其它结点 链表是一种最常见的数据结构 分为动态链表和静态链表 程序员经常使用的是动态链表 它能进行动态内存分配 可以适应数据动态增减的情况 并且可以方便地进行数据元素的插入 删除等操作 链表有单向链表 双向链表 循环链表等形式 下图是一个单向链表的结构示意图 链表中各结点在内存中可以不是连续存放的 要找到某一结点 必须先找到上一个结点 根据它提供的下一个结点的地址才能找到下一个结点 结点中的地址用指针变量来实现 即一个结点中应包含一个指针变量 用它存放下一个结点的地址 用结构变量作链表中的结点是最合适的 一个结构体变量包含若干成员 它们可以是数值类型 字符类型 数组类型 也可以是指针类型 我们用这个指针类型成员来存放下一个结点的地址 链表是一种最常见的数据结构 分为动态链表和静态链表 程序员经常使用的是动态链表 它能进行动态内存分配 可以适应数据动态增减的情况 并且可以方便地进行数据元素的插入 删除等操作 链表有单向链表 双向链表 循环链表等形式 下图是一个单向链表的结构示意图 structstudent intnum floatscore student next 每个结点数据都属于student结构类型 因而next也应为一个student类型的结构指针 它指向下一结点的地址 用这种方法可以建立链表 链表是一种最常见的数据结构 分为动态链表和静态链表 程序员经常使用的是动态链表 它能进行动态内存分配 可以适应数据动态增减的情况 并且可以方便地进行数据元素的插入 删除等操作 链表有单向链表 双向链表 循环链表等形式 下图是一个单向链表的结构示意图 structstudent intnum floatscore student next 每个结点数据都属于student结构类型 因而next也应为一个student类型的结构指针 它指向下一结点的地址 用这种方法可以建立链表 链表的特点在于动态地进行内存分配 即在需要时才会开辟一个结点的存储空间 当某个存储空间不再需要时可以释放 在 语言中 可使用new和delete两个运算符进行动态内存的分配和释放 算法分析 假设输入的学号为0时 表示建立链表的过程结束 该结点不应链接到链表中 根据题目要求 链表中结点数据应采用结构体类型来描述 同时定义三个指针变量head p1 p2 它们都是结构类型的指针变量 结构指针变量head的初值为NULL 即等于0 此时是空链表 head不指向任何结点 链表中无结点 当链表建成后 应使head指向第一个结点 例写一个函数 建立一个有5名学生数据 包含学号和成绩 的单向动态链表 structstudent longnum floatscore student next student head p1 p2 intn 0 n为结点个数 初值为0 p1 数据域 指针域 建立链表的过程 首先利用new运算符 在内存中开辟一个存储空间 用来存放新结点 使p1 p2都指向该存储空间 然后从键盘上输入一个学生的数据进行判断 如果输入的p1 num不等于0 而且是第一个结点数据 n 1 则把p1的值赋给head head p1 这样 结构指针head就指向了链表中的第一个结点 p2 p1 head n 1 建立表头结点 0001 89 5 p2 p1 head 0001 89 5 然后利用new再开辟一个新的存储空间 用来存放另一个结点 并使p1指向新开辟的存储空间 然后输入该结点的数据 如果输入的p1 num不等于0 而且不是第一个结点 n 1 时 则应将新建结点与前一个结点连接在一起 即 执行p2 next p1 使第一个结点的next成员指向第二个结点 接着使p2 p1 即 使p2指向刚刚建立的结点 即建立链表进程中的最后一个结点 建立中间结点 n 2 p2 p1 head 0001 89 5 然后利用new再开辟一个新的存储空间 用来存放另一个结点 并使p1指向新开辟的存储空间 然后输入该结点的数据 如果输入的p1 num不等于0 而且不是第一个结点 n 1 时 则应将新建结点与前一个结点连接在一起 即 执行p2 next p1 使第一个结点的next成员指向第二个结点 接着使p2 p1 即 使p2指向刚刚建立的结点 即建立链表进程中的最后一个结点 建立中间结点 n 2 0002 76 p2 p1 head 0001 89 5 然后利用new再开辟一个新的存储空间 用来存放另一个结点 并使p1指向新开辟的存储空间 然后输入该结点的数据 如果输入的p1 num不等于0 而且不是第一个结点 n 1 时 则应将新建结点与前一个结点连接在一起 即 执行p2 next p1 使第一个结点的next成员指向第二个结点 接着使p2 p1 即 使p2指向刚刚建立的结点 即建立链表进程中的最后一个结点 建立中间结点 n 2 0002 76 p2 p1 head 0001 89 5 然后利用new再开辟一个新的存储空间 用来存放另一个结点 并使p1指向新开辟的存储空间 然后输入该结点的数据 如果输入的p1 num不等于0 而且不是第一个结点 n 1 时 则应将新建结点与前一个结点连接在一起 即 执行p2 next p1 使第一个结点的next成员指向第二个结点 接着使p2 p1 即 使p2指向刚刚建立的结点 即建立链表进程中的最后一个结点 n 2 0002 76 p2 head 0001 89 5 0002 76 重复步骤 依次建立若干个新结点 每次都让p1指向新建立的结点 p2指向链表中最后一个结点 然后用 p2 next p1 把p1所指的结点连接到p2所指结点的后面 当输入某个结点数据后 如果p1 num等于0 则不再执行上述循环 此新结点不应该被连接到链表中 用语句 p2 next NULL 将NULL值赋给前一个结点的next成员 至此 建立链表的过程结束 p1 n 2 p2 head 0001 89 5 0002 76 重复步骤 依次建立若干个新结点 每次都让p1指向新建立的结点 p2指向链表中最后一个结点 然后用 p2 next p1 把p1所指的结点连接到p2所指结点的后面 当输入某个结点数据后 如果p1 num等于0 则不再执行上述循环 此新结点不应该被连接到链表中 用语句 p2 next NULL 将NULL值赋给前一个结点的next成员 至此 建立链表的过程结束 p1 0003 88 p2 head 0001 89 5 0002 76 重复步骤 依次建立若干个新结点 每次都让p1指向新建立的结点 p2指向链表中最后一个结点 然后用 p2 next p1 把p1所指的结点连接到p2所指结点的后面 当输入某个结点数据后 如果p1 num等于0 则不再执行上述循环 此新结点不应该被连接到链表中 用语句 p2 next NULL 将NULL值赋给前一个结点的next成员 至此 建立链表的过程结束 0003 88 p2 head 0001 89 5 0002 76 重复步骤 依次建立若干个新结点 每次都让p1指向新建立的结点 p2指向链表中最后一个结点 然后用 p2 next p1 把p1所指的结点连接到p2所指结点的后面 当输入某个结点数据后 如果p1 num等于0 则不再执行上述循环 此新结点不应该被连接到链表中 用语句 p2 next NULL 将NULL值赋给前一个结点的next成员 至此 建立链表的过程结束 0003 88 0 0 p1 NULL 建立表尾结点 structstudent creat student head p1 p2 head NULL 在没有创建任何结点时 表头指向空p1 newstudent 创建一个新结点 1 p2 p1 cin p1 num p1 score 输入第一个结点的学生数据 p2 p1 head 0001 89 5 n 1 建立表头结点 while p1 num 0 2 n if n 1 head p1 将链表中第一个新建结点作为表头else p2 next p1 p2 p1 p1 new student 新建一个结点cin p1 num p1 score deletep1 p2 next NULL returnhead 返回表头指针 endcreat while p1 num 0 2 n if n 1 head p1 将链表中第一个新建结点作为表头else p2 next p1 p2 p1 p1 new student 新建一个结点cin p1 num p1 score deletep1 p2 next NULL returnhead 返回表头指针 endcreat 建立中间结点 n 2 0002 76 p1 p2 while p1 num 0 2 n if n 1 head p1 将链表中第一个新建结点作为表头else p2 next p1 p2 p1 p1 new student 新建一个结点cin p1 num p1 score deletep1 p2 next NULL returnhead 返回表头指针 endcreat while p1 num 0 2 n if n 1 head p1 将链表中第一个新建结点作为表头else p2 next p1 p2 p1 p1 new student 新建一个结点cin p1 num p1 score deletep1 p2 next NULL returnhead 返回表头指针 endcreat 0 0 p1 while p1 num 0 2 n if n 1 head p1 将链表中第一个新建结点作为表头else p2 next p1 p2 p1 p1 new student 新建一个结点cin p1 num p1 score deletep1 p2 next NULL returnhead 返回表头指针 endcreat p1 NULL 建立表尾结点 while p1 num 0 2 n if n 1 head p1 将链表中第一个新建结点作为表头else p2 next p1 p2 p1 p1 new student 新建一个结点cin p1 num p1 score deletep1 p2 next NULL returnhead 返回表头指针 endcreat 输出链表就是将链表中各结点的数据依次输出 首先要知道链表第一个结点的地址 也就是要知道表头结点head的值 然后依次通过各结点next的值找到下一个结点 就可以依次输出所有结点的数据 直到链表的尾结点为止 voidmain structstudent head1 cout inputrecords endl head1 creat 建立链表 并返回表头 print head1 输出链表 例main函数调用两个函数creat 和print 实现链表的创建和链表数据的输出 voidprint structstudent p coutnumscorenext 使p指向下一个结点 while p NULL voidprint structstudent p coutnumscorenext 使p指向下一个结点 while p NULL 对链表的删除操作是把某个结点从链表中摘除 并不是真正从内存中将这个结点删除掉 使它脱离原来的链表 解除原来的链接关系 算法分析 以指定的学号为删除标志 从指针变量p指向的第一个结点开始 检查该结点中的num是否为要删除的学号 如果是则将其删除 如果不是 则将p移到下一个结点 再继续判断 直到删除或到表尾为止 对链表的删除操作 执行过程 设两个指针p1和p2 先使p1指向第一个结点 如果p1所指的结点不是要删除的结点 就将p2指向p1所指的结点 p2 p1 然后将p1指向下一个结点