第第8章章 数据封装数据封装结构体结构体 n n结构体的概述n n结构体类型的定义n n结构体类型的变量n n结构体数组n n结构体作为函数的参数n n链表结构体的概念结构体的概念n n打印学生成绩单打印学生成绩单 ，格式如下：，格式如下：学号姓名语文成绩数学成绩英语成绩.00001张三96948800003李四89707600004王五908778如何在程序中表示这组学生信息？如何在程序中表示这组学生信息？可选方案可选方案n n用二维的数组来表示n n该方案不可行，因为这些信息有不同的类型该方案不可行，因为这些信息有不同的类型n n每一列用一个一维数组来表示，这种方法称为并联数组。n n要保证每位学生信息的完整性和正确性很难要保证每位学生信息的完整性和正确性很难为什么要使用记录为什么要使用记录n n当我们考虑怎么逻辑地组织数据时，应该将一个当我们考虑怎么逻辑地组织数据时，应该将一个人的所有信息项放在一起，即保持相关性。人的所有信息项放在一起，即保持相关性。学号姓名语文成绩 数学成绩 英语成绩.00001张三96948800003李四89707600004王五908778我我们们希希望望的的结结构构学生一00001张三969488学生二00003李四897076学生三00004王五908778记录记录在在C+中称为结构体中称为结构体结构体类型作用结构体类型作用n n结构体类型允许程序员把一些分量聚合成一个整体，用一个变量表示。n n一个结构体的各个分量都有名字，把这些分量称为成员(member)。n n由于结构体的成员可以是各种类型的，程序员能创建适合于问题的数据聚合。结构体的使用结构体的使用n n定义一个新的结构体类型 n n定义新类型的变量 n n访问结构体变量 第第8章章 数据封装数据封装结构体结构体 n n结构体的概述n n结构体类型的定义n n结构体类型的变量n n结构体数组n n结构体作为函数的参数n n链表结构体类型的定义结构体类型的定义n n定义结构体类型中包括哪些分量n n格式：structstruct 结构体类型名结构体类型名 字段声明；字段声明； ；如：如：structstudentTcharno10;charname10;intchinese;intmath;intenglish;注意注意n n字段名可与程序中的变量名相同 n n在不同的结构体中可以有相同的字段名 n n结构体成员的类型可以是任意类型，当然也可以是结构体类型structdateTintmonth;intday;intyear;structstudentT.dateTbirthday;第第8章章 数据封装数据封装结构体结构体 n n结构体的概述n n结构体类型的定义n n结构体类型的变量n n结构体数组n n结构体作为函数的参数n n链表结构体类型的变量结构体类型的变量n n结构体变量的定义n n结构体类型的引用n n指向结构体的指针n n动态分配结构体的空间 结构体变量的定义结构体变量的定义n n结构体变量的定义和普通的变量定义一样。如结构体变量的定义和普通的变量定义一样。如定义了结构体类型定义了结构体类型studentTstudentT，就可以定义结构，就可以定义结构体变量：体变量： studentTstudentT student1; student1;n n一旦定义了一个结构体类型的变量，系统在分一旦定义了一个结构体类型的变量，系统在分配内存时就会分配一块连续的空间，依次存放配内存时就会分配一块连续的空间，依次存放它的每一个分量。这块空间总的名字就是结构它的每一个分量。这块空间总的名字就是结构体变量的名字。内部还有各自的名字体变量的名字。内部还有各自的名字 englishmathchinesenamenostudent1结构体变量的初始化结构体变量的初始化studentT student1= “00001”，“张三张三” ，87，90，77； 定义结构体类型的同时定义变量定义结构体类型的同时定义变量struct结构体类型名结构体类型名字段声明；字段声明；结构体变量；结构体变量；struct字段声明；字段声明；结构体变量；结构体变量；区别：前者可以继续用结构体类型名定义变量结构体类型的变量结构体类型的变量n n结构体变量的定义n n结构体类型的引用n n指向结构体的指针n n动态分配结构体的空间 结构体变量的访问结构体变量的访问成员的表示：成员的表示： 结构变量名结构变量名.成员名成员名 如如: student1.name 如结构中还有结构，则一级一级用如结构中还有结构，则一级一级用”.”分开分开 ，如，如如：如：student1.birthday.yearn n对结构体类型变量的引用一般为引用他的成员 结构变量的赋值结构变量的赋值n n结构体是一个统称。每个结构体类型在使用前都要先定义结构体是一个统称。每个结构体类型在使用前都要先定义自己有哪些分量。系统事先无法知道如何处理他。自己有哪些分量。系统事先无法知道如何处理他。n n因此，结构体变量的赋值通常是通过对它的每一个成员的因此，结构体变量的赋值通常是通过对它的每一个成员的赋值而实现。如：输入赋值而实现。如：输入student1student1的内容可用的内容可用： cincin student1.no student1.name student1.no student1.name student1.chinese student1.math student1.chinese student1.math student1.english student1.english student1.birthday.year student1.birthday.year student1.birthday.month student1.birthday.month student1.birthday.day;student1.birthday.day;n n同类型的结构变量之间可以相互赋值，如同类型的结构变量之间可以相互赋值，如Student1 = student2;Student1 = student2;将将student2student2的成员对应赋给的成员对应赋给student1student1的成员的成员结构变量的输出结构变量的输出n n结构体变量的输出通常是通过输出它的每一个成员而实现。如：输出student1的内容可用： coutcout student1.no student1.name student1.no student1.name student1.chinese student1.math student1.chinese student1.math student1.english student1.english student1.birthday.year student1.birthday.year student1.birthday.month student1.birthday.month 成员成员 如：如：sp-namestudent1.成员成员 -是所有运算符中优先级最高的是所有运算符中优先级最高的 通常程序员习惯使用第二种方法通常程序员习惯使用第二种方法结构体类型的变量结构体类型的变量n n结构体变量的定义n n结构体类型的引用n n指向结构体的指针n n动态分配结构体的空间 动态分配结构体的空间动态分配结构体的空间n n指向结构体指针的另一种用法是存储动态申请到的内存的首地址。用法和申请普通的动态变量一样。如： studentT *sp; sp = new studentT;第第8章章 数据封装数据封装结构体结构体 n n结构体的概述n n结构体类型的定义n n结构体类型的变量n n结构体数组n n结构体作为函数的参数n n链表 结构体数组结构体数组n n用于描述个体的集合n n定义格式： studentT studentArraySIZE;结构体数组的引用结构体数组的引用n n引用数组的某一成员的成员 studentArray3.namen n数组成员之间相互赋值 studentArray4 = studentArray2n n结构数组的初始化 studentT studentArray5 = “00001”, 张三“, 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); return 0; 例：例：输出通讯录输出通讯录 #include#includeusingnamespacestd;structpersonTcharname10;charsex;charaddr30;intphonenum;constintMAX=100;intmain()personTpMAX;inti,num=0;cout姓名姓名性别性别地址地址电话（电话（表示结束）：表示结束）：n;while(numpnum.name;if(pnum.name0=)break;cinpnum.sexpnum.addrpnum.phonenum;+num;coutNameSexttAddrtttPhoneNumn;coutsetiosflags(ios:left);for(i=0;inum;+i)coutsetw(10)pi.namepi.sextsetw(30)pi.addrtpi.phonenumendl;return0;指针与结构体数组指针与结构体数组n n与普通的指针一样，指向结构体的指针也能够用来指向一个结构体数组。此时，对指针加1就是加了该结构体的大小。第第8章章 数据封装数据封装结构体结构体 n n结构体的概述n n结构体类型的定义n n结构体类型的变量n n结构体数组n n结构体作为函数的参数n n链表结构体作为参数传递结构体作为参数传递n n尽管结构体和数组一样也有许多分量组成，但结构体的传递和普通内置类型是一样的。它是将实际参数中的每个分量复制到形式参数的每个分量中。结构体的传递结构体的传递Void printPerson(PersonT p)指向结构体的指针作为参数指向结构体的指针作为参数n n因为结构体是值传递，当希望把函数内部对结构体因为结构体是值传递，当希望把函数内部对结构体的修改返回给主调函数时，可以用指针传递或引用的修改返回给主调函数时，可以用指针传递或引用传递传递n n由于结构体一般占用的内存量都比较大，值传递既由于结构体一般占用的内存量都比较大，值传递既浪费空间又浪费时间。因此可用指针传递或引用传浪费空间又浪费时间。因此可用指针传递或引用传递递n n指针传递形式比较繁琐，所以指针传递形式比较繁琐，所以C+C+通常用引用传递通常用引用传递n n引用传递的问题是函数中可以修改实际参数，要控引用传递的问题是函数中可以修改实际参数，要控制函数中不能修改实际参数，可以加制函数中不能修改实际参数，可以加constconst限定限定指向结构体的指针作为参数指向结构体的指针作为参数n n和普通的指和普通的指针传递一样，针传递一样，函数中可以函数中可以通过指针访通过指针访问主调函数问主调函数的记录的记录n n减少函数调减少函数调用时的数据用时的数据传递量传递量Void PrintPerson(personT &p);Void PrintPerson(const personT &p);结构体传递的实例结构体传递的实例n n设计一函数，打印学生信息设计一：值传递设计一：值传递Void PrintStudent(studentT s)cout s.no t s.name t s.chinese t s.math t s.english endl;缺点：浪费时间空间设计二：指针传递或引用传递设计二：指针传递或引用传递Void Void PrintStudent(studentTPrintStudent(studentT *s) *s) coutcout no t name t no t name t chinesechinese t math t t math t englishenglish endlendl; ; Void Void PrintStudent(studentTPrintStudent(studentT &s) &s) coutcout s.nos.no t t s.names.name t t s.chineses.chinese t t s.maths.math t t s.englishs.english endlendl; ; 缺点：不安全缺点：不安全设计三：设计三：C+的常规做法的常规做法Void Void PrintStudent(constPrintStudent(const studentTstudentT &s) &s) coutcout s.nos.no t t s.names.name t t s.chineses.chinese t t s.maths.math t t s.englishs.english data=x;/把把x放入新节点的数据成员中放入新节点的数据成员中tmp-next=p-next;/把新节点和把新节点和p的下一成员相连的下一成员相连p-next=tmp;/把把p和新节点连接起来和新节点连接起来 单链表操作单链表操作删除删除把结点把结点p后的结点删除后的结点删除headpdelPtr delPtr=p-next;p-next=delPtr-next;delete delPtr; 单链表操作单链表操作-建立建立n n定义头指针：linkRec *head;n n建立头结点n n申请空间申请空间n n设为头结点设为头结点 head单链表操作单链表操作-建立建立（续）（续）n n逐个从键盘输入数据，存入链表 n n接受输入接受输入n n申请空间申请空间n n输入数据放入申请到的空间输入数据放入申请到的空间n n链入链表尾链入链表尾 n n置链表结束标志headabcd 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; 单链表操作单链表操作输出输出headabcd p = head-next;while ( p != NULL) cout data; p = p-next; 创建并访问一个带头结点的、存创建并访问一个带头结点的、存储整型数据的单链表，数据从键储整型数据的单链表，数据从键盘输入，盘输入，0为输入结束标志。为输入结束标志。 #include #include using namespace std;using namespace std; structstruct linkReclinkRec intint data; data; linkReclinkRec *next; *next; ;intint main() main() intint x; / x; /存放输入的值存放输入的值 linkReclinkRec *head, *p, *rear; *head, *p, *rear; head = rear = new head = rear = new linkReclinkRec; ; while (true) / while (true) /创建链表的其他结点创建链表的其他结点 cincin x; x; if (x = 0) break; if (x = 0) break; p = new p = new linkReclinkRec; ; p-data = x; rear-next = p; rear = p; p-data = x; rear-next = p; rear = p; rear-next = NULL; rear-next = NULL;/设置设置rearrear为表尾，其后没有结点了为表尾，其后没有结点了 /读链表读链表 coutcout next; p = head-next; while (p != NULL) while (p != NULL) coutcout data next; data next; coutcout data data) c=a; a=a-next; else c=b;b=b-next; p=c; while (a!=NULL & b!= NULL) if (a-data data) p-next=a; a=a-next; else p-next=b; b=b-next; p=p-next; if (a=NULL) p-next=b; else p-next=a; return (c); 单链表单链表n n链表的概念n n链表的存储n n链表的操作n n链表的应用n n循环链表例：例：n个人围成一圈，从第一个人开始报数个人围成一圈，从第一个人开始报数1、2、3。凡报到。凡报到 3者退出圈子。找出最后留在圈子中的人的序号。者退出圈子。找出最后留在圈子中的人的序号。 解。用循环链表解。用循环链表 01243head当当n = 5时，其删除的节点的顺序为时，其删除的节点的顺序为2，0，4，1，最后剩，最后剩下的节点为下的节点为3。 循环链表的应用循环链表的应用约瑟夫环约瑟夫环structnodeintdata;node*next;intmain()node*head,*p,*q;/head为链表头为链表头intn,i;/输入输入ncoutn;/建立链表建立链表head=p=newnode;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;/绕过节点绕过节点qcoutdatanext;/让让q指向报指向报1的节点的节点/打印结果打印结果coutn最后剩下：最后剩下：dataendl;return0; 链表总结链表总结n n实现较复杂n n插入、删除效率高，但查找第i个元素效率低n n无表满的问题n n适合于动态表总结总结n n本章介绍了结构体n n作用：n n处理更复杂的数据处理更复杂的数据n n使用：n n定义类型定义类型n n定义变量定义变量n n链表