《第8章数据封装—结构体》由会员分享,可在线阅读,更多相关《第8章数据封装—结构体(64页珍藏版)》请在金锄头文库上搜索。
1、程序设计 cs.sjtu 2011.9程序设计 - 1第第8章章数据封装数据封装结构体结构体v结构体的概述构体的概述v结构体构体类型的定型的定义v结构体构体类型的型的变量量v结构体数构体数组v结构体作构体作为函数的参数函数的参数v链表表程序设计 cs.sjtu 2011.9程序设计 - 2结构体的概念结构体的概念v打印学生成绩单打印学生成绩单,格式如下:,格式如下:学号学号姓名姓名语文成绩语文成绩数学成绩数学成绩英语成绩英语成绩.00001张三张三96948800003李四李四89707600004王五王五908778如何在程序中表示这组学生信息?如何在程序中表示这组学生信息?程序设计 cs.
2、sjtu 2011.9程序设计 - 3可选方案可选方案v用二用二维的数的数组来表示来表示该方案不可行,因方案不可行,因为这些信息有不同的些信息有不同的类型型v每一列用一个一每一列用一个一维数数组来表示,来表示,这种方法种方法称称为并并联数数组。要保要保证每位学生信息的正确性很每位学生信息的正确性很难程序设计 cs.sjtu 2011.9程序设计 - 4为什么要使用记录为什么要使用记录v当我们考虑怎么逻辑地组织数据时,应该将一当我们考虑怎么逻辑地组织数据时,应该将一个人的所有信息项放在一起,即保持相关性。个人的所有信息项放在一起,即保持相关性。学号学号姓名姓名语文成绩语文成绩 数学成绩数学成绩
3、英语成绩英语成绩.00001张三张三96948800003李四李四89707600004王五王五908778程序设计 cs.sjtu 2011.9程序设计 - 5我我们们希希望望的的结结构构学学生生一一00001张三张三969488学学生生二二00003李四李四897076学学生生三三00004王五王五908778记录记录在在C+中称为结构体中称为结构体程序设计 cs.sjtu 2011.9程序设计 - 6结构体类型作用结构体类型作用v结构体构体类型允型允许程序程序员把一些分量聚合把一些分量聚合成一个整体,用一个成一个整体,用一个变量表示。量表示。v一个一个结构体的各个分量都有名字,把构体的各
4、个分量都有名字,把这些分量称些分量称为成成员(member)。v由于由于结构体的成构体的成员可以是各种可以是各种类型的,型的,程序程序员能能创建适合于建适合于问题的数据聚合。的数据聚合。程序设计 cs.sjtu 2011.9程序设计 - 7结构体的使用结构体的使用v定定义一个新的一个新的结构体构体类型型v定定义新新类型的型的变量量v访问结构体构体变量量程序设计 cs.sjtu 2011.9程序设计 - 8第第8章章数据封装数据封装结构体结构体v结构体的概述构体的概述v结构体构体类型的定型的定义v结构体构体类型的型的变量量v结构体数构体数组v结构体作构体作为函数的参数函数的参数v链表表程序设计
5、cs.sjtu 2011.9程序设计 - 9结构体类型的定义结构体类型的定义v定定义结构体构体类型中包括哪些分量型中包括哪些分量v格式:格式:struct结构体构体类型名型名字段声明;字段声明;如:如:structstudentTcharno10;charname10;intchinese;intmath;intenglish;程序设计 cs.sjtu 2011.9程序设计 - 10注意注意v字段名可与程序中的字段名可与程序中的变量名相同量名相同v在不同的在不同的结构体中可以有相同的字段名构体中可以有相同的字段名v结构体成构体成员的的类型可以是任意型可以是任意类型,当型,当然也可以是然也可以是
6、结构体构体类型型程序设计 cs.sjtu 2011.9程序设计 - 11structdateTintmonth;intday;intyear;structstudentT.dateTbirthday;程序设计 cs.sjtu 2011.9程序设计 - 12第第8章章数据封装数据封装结构体结构体v结构体的概述构体的概述v结构体构体类型的定型的定义v结构体构体类型的型的变量量v结构体数构体数组v结构体作构体作为函数的参数函数的参数v链表表程序设计 cs.sjtu 2011.9程序设计 - 13结构体类型的变量结构体类型的变量v结构体构体变量的定量的定义v结构体构体类型的引用型的引用v指向指向结构体
7、的指构体的指针v动态分配分配结构体的空构体的空间程序设计 cs.sjtu 2011.9程序设计 - 14结构体变量的定义结构体变量的定义v结构体构体变量的定量的定义和普通的和普通的变量定量定义一一样。如。如定定义了了结构体构体类型型studentT,就可以定,就可以定义结构构体体变量:量:studentTstudent1;v一旦定一旦定义了一个了一个结构体构体类型的型的变量,系量,系统在分在分配内存配内存时就会分配一就会分配一块连续的空的空间,依次存放,依次存放它的每一个分量。它的每一个分量。这块空空间总的名字就是的名字就是结构构体体变量的名字。内部量的名字。内部还有各自的名字有各自的名字en
8、glishmathchinesenamenostudent1程序设计 cs.sjtu 2011.9程序设计 - 15结构体变量的初始化结构体变量的初始化studentTstudent1=“00001”,“张三张三”,87,90,77;程序设计 cs.sjtu 2011.9程序设计 - 16定义结构体类型的同时定义变量定义结构体类型的同时定义变量struct结构体类型名结构体类型名字段声明;字段声明;结构体变量;结构体变量;struct字段声明;字段声明;结构体变量;结构体变量;区别:前者可以继续用结构体类型名定义变量程序设计 cs.sjtu 2011.9程序设计 - 17结构体类型的变量结构体
9、类型的变量v结构体构体变量的定量的定义v结构体构体类型的引用型的引用v指向指向结构体的指构体的指针v动态分配分配结构体的空构体的空间程序设计 cs.sjtu 2011.9程序设计 - 18结构体变量的访问结构体变量的访问成员的表示:成员的表示: 结构变量名结构变量名.成员名成员名 如如:student1.name 如结构中还有结构,则一级一级用如结构中还有结构,则一级一级用”.”分开分开,如,如如:如:student1.birthday.yearv对结构体构体类型型变量的引用一般量的引用一般为引用他引用他的成的成员程序设计 cs.sjtu 2011.9程序设计 - 19结构变量的赋值结构变量的
10、赋值v结构体是一个构体是一个统称。每个称。每个结构体构体类型在使用前都要先定型在使用前都要先定义自己有哪些分量。系自己有哪些分量。系统事先无法知道如何事先无法知道如何处理他。理他。v因此,因此,结构体构体变量的量的赋值通常是通通常是通过对它的每一个成它的每一个成员的的赋值而而实现。如:。如:输入入student1的内容可用的内容可用: cinstudent1.nostudent1.namestudent1.chinesestudent1.mathstudent1.englishstudent1.birthday.yearstudent1.birthday.month student1.birt
11、hday.day;v同同类型的型的结构构变量之量之间可以相互可以相互赋值,如,如Student1=student2;将将student2的成的成员对应赋给student1的成的成员程序设计 cs.sjtu 2011.9程序设计 - 20结构变量的输出结构变量的输出v结构体构体变量的量的输出通常是通出通常是通过输出它的每一出它的每一个成个成员而而实现。如:。如:输出出student1的内容可的内容可用用: coutstudent1.nostudent1.namestudent1.chinesestudent1.mathstudent1.englishstudent1.birthday.years
12、tudent1.birthday.month 成员成员如:如:sp-namestudent1.成员成员 -是所有运算符中优先级最高的是所有运算符中优先级最高的 通常程序员习惯使用第二种方法通常程序员习惯使用第二种方法程序设计 cs.sjtu 2011.9程序设计 - 24结构体类型的变量结构体类型的变量v结构体构体变量的定量的定义v结构体构体类型的引用型的引用v指向指向结构体的指构体的指针v动态分配分配结构体的空构体的空间程序设计 cs.sjtu 2011.9程序设计 - 25动态分配结构体的空间动态分配结构体的空间v指向指向结构体指构体指针的另一种用法是存的另一种用法是存储动态申申请到的内存
13、的首地址。用法和申到的内存的首地址。用法和申请普通的普通的动态变量一量一样。如:。如:studentT*sp;sp=newstudentT;程序设计 cs.sjtu 2011.9程序设计 - 26第第8章章数据封装数据封装结构体结构体v结构体的概述构体的概述v结构体构体类型的定型的定义v结构体构体类型的型的变量量v结构体数构体数组v结构体作构体作为函数的参数函数的参数v链表表程序设计 cs.sjtu 2011.9程序设计 - 27 结构体数组结构体数组v用于描述个体的集合用于描述个体的集合v定定义格式:格式:studentTstudentArraySIZE;程序设计 cs.sjtu 2011.
14、9程序设计 - 28结构体数组的引用结构体数组的引用v引用数引用数组的某一成的某一成员的成的成员studentArray3.namev数数组成成员之之间相互相互赋值studentArray4=studentArray2v结构数构数组的初始化的初始化studentTstudentArray5=“00001”,张三三“,80,90,98,;程序设计 cs.sjtu 2011.9程序设计 - 29统计候选人得票。设有三个候选人,每次输入一个统计候选人得票。设有三个候选人,每次输入一个得票的候选人名字,要求最后输出各人得票结果。得票的候选人名字,要求最后输出各人得票结果。 structpersonTi
15、ntid;intcount;leader3=0,0,1,0,2,0;程序设计 cs.sjtu 2011.9程序设计 - 30intmain()inti,j,inputID;for(i=1;iinputID;if(inputID2)cout“废票废票”;continue;leaderinputID.count+=1;coutendl;for(i=0;i3;+i)coutleaderi.id“leaderi.count);return0;程序设计 cs.sjtu 2011.9程序设计 - 31指针与结构体数组指针与结构体数组v与普通的指与普通的指针一一样,指向,指向结构体的指构体的指针也也能能够用
16、来指向一个用来指向一个结构体数构体数组。此。此时,对指指针加加1就是加了就是加了该结构体的大小。构体的大小。程序设计 cs.sjtu 2011.9程序设计 - 32第第8章章数据封装数据封装结构体结构体v结构体的概述构体的概述v结构体构体类型的定型的定义v结构体构体类型的型的变量量v结构体数构体数组v结构体作构体作为函数的参数函数的参数v链表表程序设计 cs.sjtu 2011.9程序设计 - 33结构体作为参数传递结构体作为参数传递v尽管尽管结构体和数构体和数组一一样也有也有许多分量多分量组成,但成,但结构体的构体的传递和普通内置和普通内置类型是型是一一样的。它是将的。它是将实际参数中的每个
17、分量参数中的每个分量复制到形式参数的每个分量中。复制到形式参数的每个分量中。程序设计 cs.sjtu 2011.9程序设计 - 34结构体的传递结构体的传递Void printPerson(PersonT p)程序设计 cs.sjtu 2011.9程序设计 - 35指向结构体的指针作为参数指向结构体的指针作为参数v因因为结构体是构体是值传递,当希望把函数内部,当希望把函数内部对结构构体的修改返回体的修改返回给主主调函数函数时,可以用指,可以用指针传递或或引用引用传递v由于由于结构体一般占用的内存量都比构体一般占用的内存量都比较大,大,值传递既浪既浪费空空间又浪又浪费时间。因此可用指。因此可用指
18、针传递或引或引用用传递v指指针传递形式比形式比较繁繁琐,所以,所以C+C+通常用引用通常用引用传递v引用引用传递的的问题是函数中可以修改是函数中可以修改实际参数,要参数,要控制函数中不能修改控制函数中不能修改实际参数,可以加参数,可以加constconst限定限定程序设计 cs.sjtu 2011.9程序设计 - 36指向结构体的指针作为参数指向结构体的指针作为参数v和普通的指和普通的指针传递一一样,函数中可以函数中可以通通过指指针访问主主调函数函数的的记录v减少函数减少函数调用用时的数据的数据传递量量Void PrintPerson(personT &p);Void PrintPerson(
19、const personT &p);程序设计 cs.sjtu 2011.9程序设计 - 37结构体传递的实例结构体传递的实例v设计一函数,打印学生信息一函数,打印学生信息程序设计 cs.sjtu 2011.9程序设计 - 38设计一:值传递设计一:值传递VoidPrintStudent(studentTs)couts.nots.namets.chinesets.mathts.englishendl;缺点:浪缺点:浪费时间空空间程序设计 cs.sjtu 2011.9程序设计 - 39设计二:指针传递或引用传递设计二:指针传递或引用传递VoidPrintStudent(studentT*s)cou
20、tnotnametchinesetmathtenglishendl;VoidPrintStudent(studentT&s)couts.nots.namets.chinesets.mathts.englishendl;缺点:不安全缺点:不安全程序设计 cs.sjtu 2011.9程序设计 - 40设计三:设计三:C+的常规做法的常规做法VoidPrintStudent(conststudentT&s)couts.nots.namets.chinesets.mathts.englishdata=x;/把把x放入新节点的数据成员中放入新节点的数据成员中tmp-next=p-next;/把新节点和把
21、新节点和p的下一成员相连的下一成员相连p-next=tmp;/把把p和新节点连接起来和新节点连接起来 程序设计 cs.sjtu 2011.9程序设计 - 52单链表操作单链表操作删除删除把结点把结点p后的结点删除后的结点删除headpdelPtr delPtr=p-next;p-next=delPtr-next;deletedelPtr;程序设计 cs.sjtu 2011.9程序设计 - 53单链表操作单链表操作-建立建立v定定义头指指针:linkRec*head;v建立建立头结点点申申请空空间设为头结点点head程序设计 cs.sjtu 2011.9程序设计 - 54单链表操作单链表操作-建
22、立建立(续)(续)v逐个从逐个从键盘输入数据,存入入数据,存入链表表 接受接受输入入申申请空空间输入数据放入申入数据放入申请到的空到的空间链入入链表尾表尾v置置链表表结束束标志志headabcd 程序设计 cs.sjtu 2011.9程序设计 - 55head=newlinkRec;rear=head;Cinin_data;while(输入未结束输入未结束)p=newlinkRec;p-data=in_data;rear-next=p;rear=p;cinin_data;rear-next=NULL;程序设计 cs.sjtu 2011.9程序设计 - 56单链表操作单链表操作输出输出heada
23、bcd p=head-next;while(p!=NULL)coutdata;p=p-next;程序设计 cs.sjtu 2011.9程序设计 - 57创建并访问一个带头结点的、存创建并访问一个带头结点的、存储整型数据的单链表,数据从键储整型数据的单链表,数据从键盘输入,盘输入,0为输入结束标志。为输入结束标志。#includeusingnamespacestd;structlinkRecintdata;linkRec*next;程序设计 cs.sjtu 2011.9程序设计 - 58intmain()intx;/存放存放输入的入的值linkRec*head,*p,*rear;head=rea
24、r=newlinkRec;while(true)/创建建链表的其他表的其他结点点cinx;if(x=0)break;p=newlinkRec;p-data=x;rear-next=p;rear=p;rear-next=NULL;/设置置rear为表尾,其后没有表尾,其后没有结点了点了/读链表表coutnext;while(p!=NULL)coutdatanext;coutendl;return0;程序设计 cs.sjtu 2011.9程序设计 - 59单链表单链表v链表的概念表的概念v链表的存表的存储v链表的操作表的操作v循循环链表表程序设计 cs.sjtu 2011.9程序设计 - 60例:
25、例:n个人围成一圈,从第一个人开始报数个人围成一圈,从第一个人开始报数1、2、3。凡报到。凡报到3者退出圈子。找出最后留在圈子中的人的序号。者退出圈子。找出最后留在圈子中的人的序号。 解。用循环链表解。用循环链表 01243head当当n=5时,其删除的节点的顺序为时,其删除的节点的顺序为2,0,4,1,最后剩,最后剩下的节点为下的节点为3。循环链表的应用循环链表的应用约瑟夫环约瑟夫环程序设计 cs.sjtu 2011.9程序设计 - 61structnodeintdata;node*next;intmain()node*head,*p,*q;/head为链表头为链表头intn,i;/输入输入
26、ncoutn;/建立链表建立链表head=p=newnode;p-data=0;/p指向表尾指向表尾for(i=1;idata=i;p-next=q;p=q;/将将q链入表尾链入表尾p-next=head;/头尾相连头尾相连 程序设计 cs.sjtu 2011.9程序设计 - 62/删除过程删除过程q=head;while(q-next!=q)/只要表非空只要表非空for(i=0;inext;p-next=q-next;/绕过节点绕过节点qcoutdatanext;/让让q指向报指向报1的节点的节点/打印结果打印结果coutn最后剩下:最后剩下:dataendl;return0; 程序设计 cs.sjtu 2011.9程序设计 - 63链表总结链表总结v实现较复复杂v插入、插入、删除效率高,但除效率高,但查找第找第i个元素效个元素效率低率低v无表无表满的的问题v适合于适合于动态表表程序设计 cs.sjtu 2011.9程序设计 - 64总结总结v本章介本章介绍了了结构体构体v作用:作用:处理更复理更复杂的数据的数据v使用:使用:定定义类型型定定义变量量v链表表