1、第8章 数据封装结构体,结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表,结构体的概念,打印学生成绩单 ，格式如下：,如何在程序中表示这组学生信息？,可选方案,用二维的数组来表示 该方案不可行，因为这些信息有不同的类型 每一列用一个一维数组来表示，这种方法称为并联数组。 要保证每位学生信息的正确性很难,为什么要使用记录,当我们考虑怎么逻辑地组织数据时，应该将一个人的所有信息项放在一起，即保持相关性。,我 们 希 望 的 结 构,记录 在C+中称为结构体,结构体类型作用,结构体类型允许程序员把一些分量聚合成一个整体，用一个变量表示。 一个结构体的各个分量都
2、有名字，把这些分量称为成员(member)。 由于结构体的成员可以是各种类型的，程序员能创建适合于问题的数据聚合。,结构体的使用,定义一个新的结构体类型 定义新类型的变量 访问结构体变量,第8章 数据封装结构体,结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表,结构体类型的定义,定义结构体类型中包括哪些分量 格式： struct 结构体类型名 字段声明； ；,如： struct studentT char no10;char name10;int chinese;int math;int english;,注意,字段名可与程序中的变量名相同 在不同的结构
3、体中可以有相同的字段名 结构体成员的类型可以是任意类型，当然也可以是结构体类型,struct dateT int month;int day;int year; ;struct studentT .dateT birthday; ;,第8章 数据封装结构体,结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表,结构体类型的变量,结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间,结构体变量的定义,结构体变量的定义和普通的变量定义一样。如定义了结构体类型studentT，就可以定义结构体变量：studentT student1; 一旦定
4、义了一个结构体类型的变量，系统在分配内存时就会分配一块连续的空间，依次存放它的每一个分量。这块空间总的名字就是结构体变量的名字。内部还有各自的名字,结构体变量的初始化,studentT student1=“00001”，“张三” ，87，90，77；,定义结构体类型的同时定义变量,struct 结构体类型名字段声明； 结构体变量；,struct 字段声明； 结构体变量；,区别：前者可以继续用结构体类型名定义变量,结构体类型的变量,结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间,结构体变量的访问,成员的表示：,结构变量名.成员名,如: student1.name,如结
5、构中还有结构，则一级一级用”.”分开 ，如,如：student1.birthday.year,对结构体类型变量的引用一般为引用他的成员,结构变量的赋值,结构体是一个统称。每个结构体类型在使用前都要先定义自己有哪些分量。系统事先无法知道如何处理他。 因此，结构体变量的赋值通常是通过对它的每一个成员的赋值而实现。如：输入student1的内容可用： cin student1.no student1.name student1.chinese student1.math student1.english student1.birthday.year student1.birthday.month s
6、tudent1.birthday.day; 同类型的结构变量之间可以相互赋值，如 Student1 = student2; 将student2的成员对应赋给student1的成员,结构变量的输出,结构体变量的输出通常是通过输出它的每一个成员而实现。如：输出student1的内容可用： cout student1.no student1.name student1.chinese student1.math student1.english student1.birthday.year student1.birthday.month student1.birthday.day;,结构体类型的变量
7、,结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间,指向记录的指针,直接定义指针变量studentT *sp; 也可以在定义结构体类型的同时定义指向结构体的指针,struct 结构体类型名字段声明； *结构体指针；,通过指针操作记录,给结构体指针赋值，如：sp = 结构体指针的引用：,(*指针).成员 如：(*sp).name,指针-成员 如：sp-name,student1.成员, -是所有运算符中优先级最高的,通常程序员习惯使用第二种方法,结构体类型的变量,结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间,动态分配结构体的空间,指向结构体
8、指针的另一种用法是存储动态申请到的内存的首地址。用法和申请普通的动态变量一样。如：studentT *sp;sp = new studentT;,第8章 数据封装结构体,结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表,结构体数组,用于描述个体的集合 定义格式：studentT studentArraySIZE;,结构体数组的引用,引用数组的某一成员的成员studentArray3.name 数组成员之间相互赋值studentArray4 = studentArray2 结构数组的初始化 studentT studentArray5 = “00001”,
9、 张三“, 80, 90,98 , , , ;,统计候选人得票。设有三个候选人，每次输入一个 得票的候选人名字，要求最后输出各人得票结果。,struct personT int id;int count; leader3= 0, 0,1, 0,2, 0;,int main() int i, j, inputID;for (i=1; i inputID;if (inputID 2) cout “废票”；continue；leaderinputID.count += 1;cout endl;for (i=0; i3; +i)cout leaderi.id “ “ leaderi.count);re
10、turn 0;,指针与结构体数组,与普通的指针一样，指向结构体的指针也能够用来指向一个结构体数组。此时，对指针加1就是加了该结构体的大小。,第8章 数据封装结构体,结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表,结构体作为参数传递,尽管结构体和数组一样也有许多分量组成，但结构体的传递和普通内置类型是一样的。它是将实际参数中的每个分量复制到形式参数的每个分量中。,结构体的传递,Void printPerson(PersonT p),指向结构体的指针作为参数,因为结构体是值传递，当希望把函数内部对结构体的修改返回给主调函数时，可以用指针传递或引用传递 由于
11、结构体一般占用的内存量都比较大，值传递既浪费空间又浪费时间。因此可用指针传递或引用传递 指针传递形式比较繁琐，所以C+通常用引用传递 引用传递的问题是函数中可以修改实际参数，要控制函数中不能修改实际参数，可以加const限定,指向结构体的指针作为参数,和普通的指针传递一样，函数中可以通过指针访问主调函数的记录 减少函数调用时的数据传递量,Void PrintPerson(personT ,结构体传递的实例,设计一函数，打印学生信息,设计一：值传递,Void PrintStudent(studentT s) cout s.no t s.name t s.chinese t s.math t s.
12、english endl; 缺点：浪费时间空间,设计二：指针传递或引用传递,Void PrintStudent(studentT *s) cout no name chinese math english endl; Void PrintStudent(studentT 缺点：不安全,设计三：C+的常规做法,Void PrintStudent(const studentT 特点：节约内存，提高函数调用速度，可靠,返回结构体类型的函数,一个函数返回一个结构体。如： personT GetPersonData(void) personT person; . Return(person); 返回的是
13、一个结构体的复制。 在主调函数中必须有这样的程序段： Main() personT p1,p2;p1=GetPersonData();,返回结构体引用的函数,函数返回一个结构体的引用。如： personT 函数中返回的结构体不能是局部变量,第8章 数据封装结构体,结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表,单链表,链表的概念 链表的存储 链表的操作 循环链表,单链表,头结点,只指出后继关系的链表,双链表,循环链表,同时存储前趋和后继,单链表,链表的概念 链表的存储 链表的操作 循环链表,单链表的存储,struct linkRecdatatype d
14、ata;linkRec *next;,存储链表就是存储链表中的一个节点的地址，因此需要定义一个节点类型,单链表,链表的概念 链表的存储 链表的操作 循环链表,单链表操作插入,申请空间 输入数据放入申请到的空间 链入p后,在结点p后插入一个结点,tmp = new LinkRec; / 创建一个新节点 tmp-data = x; / 把x放入新节点的数据成员中 tmp-next = p-next; / 把新节点和p的下一成员相连 p-next = tmp; /把p和新节点连接起来,单链表操作删除,把结点p后的结点删除,delPtr=p-next; p-next=delPtr-next; dele
15、te delPtr;,单链表操作-建立,定义头指针：linkRec *head; 建立头结点 申请空间 设为头结点,head,单链表操作-建立（续）,逐个从键盘输入数据，存入链表 接受输入 申请空间 输入数据放入申请到的空间 链入链表尾 置链表结束标志,a,b,c,d,head = new linkRec; rear = head; Cin in_data; while(输入未结束) p= new linkRec;p-data = in_data;rear-next = p;rear=p;cin in_data; rear-next = NULL;,单链表操作输出,p = head-next;
16、 while ( p != NULL) cout data;p = p-next;,创建并访问一个带头结点的、存储整型数据的单链表，数据从键盘输入，0为输入结束标志。,#include using namespace std;struct linkRec int data; linkRec *next; ;,int main() int x; /存放输入的值linkRec *head, *p, *rear;head = rear = new linkRec; while (true) /创建链表的其他结点cin x;if (x = 0) break;p = new linkRec; p-dat
17、a = x; rear-next = p; rear = p; rear-next = NULL; /设置rear为表尾，其后没有结点了/读链表cout next;while (p != NULL) cout data next; cout endl;return 0; ,单链表,链表的概念 链表的存储 链表的操作 循环链表,例：n个人围成一圈，从第一个人开始报数1、2、3。凡报到3者退出圈子。找出最后留在圈子中的人的序号。,解。用循环链表,当n = 5时，其删除的节点的顺序为2，0，4，1，最后剩下的节点为3。,循环链表的应用约瑟夫环,struct node int data; node *
18、next; ;int main() node *head, *p, *q; / head为链表头int n, i; /输入ncout n;/建立链表head = p = new node; p-data = 0; /p指向表尾for (i=1; idata =i; p-next = q; p = q; /将q链入表尾p-next = head; / 头尾相连,/ 删除过程 q=head;while (q-next != q) /只要表非空 for (i = 0; inext;p-next = q-next; /绕过节点qcout data next; /让q指向报1的节点/ 打印结果 cout data endl;return 0; ,链表总结,实现较复杂 插入、删除效率高，但查找第i个元素效率低 无表满的问题 适合于动态表,总结,本章介绍了结构体 作用： 处理更复杂的数据 使用： 定义类型 定义变量 链表,
