《第8章数据封装结构体ppt课件》由会员分享，可在线阅读，更多相关《第8章数据封装结构体ppt课件（64页珍藏版）》请在金锄头文库上搜索。
1、程序设计 cs.sjtu 2011.9程序设计 - 1第第8章章数据封装数据封装结构体结构体v结构体的概述结构体的概述v结构体类型的定义结构体类型的定义v结构体类型的变量结构体类型的变量v结构体数组结构体数组v结构体作为函数的参数结构体作为函数的参数v链表链表杂轰馆姓颤蔷乖嘛汉吸袍戎鱼邻如瞄讨贬炮贰郴闯谊矿嗅竭拓辖遭岩复站第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 2结构体的概念结构体的概念v打印学生成绩单打印学生成绩单，格式如下：，格式如下：学号学号姓名姓名语文成绩语文成绩数学成绩数学成绩英语成绩英语成绩.00001张三张三96948800003
2、李四李四89707600004王五王五908778如何在程序中表示这组学生信息？如何在程序中表示这组学生信息？庙绒描惠崇痈纳太秸续李鲍湘物限象巾胎朵骏库泣擞邢奏皋俊赞涡溢咨沂第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 3可选方案可选方案v用二维的数组来表示用二维的数组来表示该方案不可行，因为这些信息有不同的类型该方案不可行，因为这些信息有不同的类型v每一列用一个一维数组来表示，这种方法每一列用一个一维数组来表示，这种方法称为并联数组。称为并联数组。要保证每位学生信息的正确性很难要保证每位学生信息的正确性很难帧葬剔遮疯赔骇栏栈薛廉美豫贿役兵熏贬色侠呜
3、萝麓裤弛袖褥阻淖线炕握第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 4为什么要使用记录为什么要使用记录v当我们考虑怎么逻辑地组织数据时，应该将一当我们考虑怎么逻辑地组织数据时，应该将一个人的所有信息项放在一起，即保持相关性。个人的所有信息项放在一起，即保持相关性。学号学号姓名姓名语文成绩语文成绩 数学成绩数学成绩 英语成绩英语成绩.00001张三张三96948800003李四李四89707600004王五王五908778疼噎卞深难获蜀意首欠欣激档顶将治痒责焦事坐俯漠颠台半萄湍碱绊谱呐第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 20
4、11.9程序设计 - 5我我们们希希望望的的结结构构学学生生一一00001张三张三969488学学生生二二00003李四李四897076学学生生三三00004王五王五908778记录记录在在C+中称为结构体中称为结构体祈扮眨九缘诡吹琵承礁窗暇队叛厚星妙赔茨歪挖酉瑚酣迹庭构黄便乔灭郸第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 6结构体类型作用结构体类型作用v结构体类型允许程序员把一些分量聚合结构体类型允许程序员把一些分量聚合成一个整体，用一个变量表示。成一个整体，用一个变量表示。v一个结构体的各个分量都有名字，把这一个结构体的各个分量都有名字，把这些
5、分量称为成员些分量称为成员(member)。v由于结构体的成员可以是各种类型的，由于结构体的成员可以是各种类型的，程序员能创建适合于问题的数据聚合。程序员能创建适合于问题的数据聚合。鲤浇祟毅屋奈换备惶付寸抖怒嗜峡阁妙成弃课叮毁挽寸士耽肾辙爽握端运第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 7结构体的使用结构体的使用v定义一个新的结构体类型定义一个新的结构体类型v定义新类型的变量定义新类型的变量v访问结构体变量访问结构体变量淋八岗丝插勃轮缅镑瓮烦怪尤嗡凤笺搭丢线钮伸瞩扬帆嗓贫松焊渴顷叶刀第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu
6、2011.9程序设计 - 8第第8章章数据封装数据封装结构体结构体v结构体的概述结构体的概述v结构体类型的定义结构体类型的定义v结构体类型的变量结构体类型的变量v结构体数组结构体数组v结构体作为函数的参数结构体作为函数的参数v链表链表烂宗琅绽裤衅沽亭管挟哗班砌搪宠啡输猛矣谭创隐锐挨逃哦馈站浇诚素观第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 9结构体类型的定义结构体类型的定义v定义结构体类型中包括哪些分量定义结构体类型中包括哪些分量v格式：格式：struct结构体类型名结构体类型名字段声明；字段声明；如：如：structstudentTcharno1
7、0;charname10;intchinese;intmath;intenglish;钠脱夜枫兆报梗层脏烧耕稗媳丛碌蒲侄玫次匪斤活烛晨姑恰这涝卡袜弟恒第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 10注意注意v字段名可与程序中的变量名相同字段名可与程序中的变量名相同v在不同的结构体中可以有相同的字段名在不同的结构体中可以有相同的字段名v结构体成员的类型可以是任意类型，当结构体成员的类型可以是任意类型，当然也可以是结构体类型然也可以是结构体类型耙储篷侨贸概食琐挫缉烧坪养绚托笺秦惺桅闻习溺芒硬匡抢集乘逐汾霸她第8章数据封装结构体ppt课件程序设计程序设计
8、 cs.sjtu 2011.9程序设计 - 11structdateTintmonth;intday;intyear;structstudentT.dateTbirthday;酉楔扛钉兵纪鳖享草甚拯咳穆闽影径糜引胳席擞寂掩拉裁颇躁宾磁皮胃厄第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 12第第8章章数据封装数据封装结构体结构体v结构体的概述结构体的概述v结构体类型的定义结构体类型的定义v结构体类型的变量结构体类型的变量v结构体数组结构体数组v结构体作为函数的参数结构体作为函数的参数v链表链表譬孜蛛裙蚁概省酋章研三尖名禹硅可渴戌弱泛渭那妻躬线称哭鹤谓剥
9、噪暴第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 13结构体类型的变量结构体类型的变量v结构体变量的定义结构体变量的定义v结构体类型的引用结构体类型的引用v指向结构体的指针指向结构体的指针v动态分配结构体的空间动态分配结构体的空间畴岸凤互纷尉脉碉完罢塔卞贩准硬钧荷奸伞整郡割御瘩恫涵贤廓位冰尹洱第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 14结构体变量的定义结构体变量的定义v结构体变量的定义和普通的变量定义一样。如结构体变量的定义和普通的变量定义一样。如定义了结构体类型定义了结构体类型studentT，就可
10、以定义结构，就可以定义结构体变量：体变量：studentTstudent1;v一旦定义了一个结构体类型的变量，系统在分一旦定义了一个结构体类型的变量，系统在分配内存时就会分配一块连续的空间，依次存放配内存时就会分配一块连续的空间，依次存放它的每一个分量。这块空间总的名字就是结构它的每一个分量。这块空间总的名字就是结构体变量的名字。内部还有各自的名字体变量的名字。内部还有各自的名字englishmathchinesenamenostudent1闺保敲蜂姚份蔚逊惮滇缘冯暗奥铸城曳仟莹红霸讳婚接蚂墟盐病雀澳筋万第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 -
11、15结构体变量的初始化结构体变量的初始化studentTstudent1=“00001”，“张三张三”，87，90，77；珠嫌儒饯伊四仗母游园访悄敦幂初虏腥窝诅藻麻游嗅帛顽抿宰素非兢光蛀第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 16定义结构体类型的同时定义变量定义结构体类型的同时定义变量struct结构体类型名结构体类型名字段声明；字段声明；结构体变量；结构体变量；struct字段声明；字段声明；结构体变量；结构体变量；区别：前者可以继续用结构体类型名定义变量酉蒲烃憨撇糖锚莆目钥镭憾桶钾馏描婿蔷丛骆门诲液穿洋啮陷萍沽嫌肃梳第8章数据封装结构体pp
12、t课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 17结构体类型的变量结构体类型的变量v结构体变量的定义结构体变量的定义v结构体类型的引用结构体类型的引用v指向结构体的指针指向结构体的指针v动态分配结构体的空间动态分配结构体的空间铁戎墓钧野癣挥咎驳驮局职窘抽西岔挖镑视亲脑避杏邹捉锰斋江兹复坟氟第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 18结构体变量的访问结构体变量的访问成员的表示：成员的表示： 结构变量名结构变量名.成员名成员名 如如:student1.name 如结构中还有结构，则一级一级用如结构中还有结构，则一级一级用”.”分
13、开分开，如，如如：如：student1.birthday.yearv对结构体类型变量的引用一般为引用他对结构体类型变量的引用一般为引用他的成员的成员储烩氖涎砂表帕绢寂咸临于霍斩寂厉京烹菇氛柠谚逞溶撑与绣男脆儡弥犯第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 19结构变量的赋值结构变量的赋值v结构体是一个统称。每个结构体类型在使用前都要先定义结构体是一个统称。每个结构体类型在使用前都要先定义自己有哪些分量。系统事先无法知道如何处理他。自己有哪些分量。系统事先无法知道如何处理他。v因此，结构体变量的赋值通常是通过对它的每一个成员的因此，结构体变量的赋值通
14、常是通过对它的每一个成员的赋值而实现。如：输入赋值而实现。如：输入student1的内容可用的内容可用： cinstudent1.nostudent1.namestudent1.chinesestudent1.mathstudent1.englishstudent1.birthday.yearstudent1.birthday.month student1.birthday.day;v同类型的结构变量之间可以相互赋值，如同类型的结构变量之间可以相互赋值，如Student1=student2;将将student2的成员对应赋给的成员对应赋给student1的成员的成员潍率姓恰傅胀苇砰痪跌泌篡脾手
15、釉产巫包脖幸絮秦膝威遁静梁萎邦异英催第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 20结构变量的输出结构变量的输出v结构体变量的输出通常是通过输出它的每一结构体变量的输出通常是通过输出它的每一个成员而实现。如：输出个成员而实现。如：输出student1的内容可的内容可用用： coutstudent1.nostudent1.namestudent1.chinesestudent1.mathstudent1.englishstudent1.birthday.yearstudent1.birthday.month 成员成员如：如：sp-namestuden
16、t1.成员成员 -是所有运算符中优先级最高的是所有运算符中优先级最高的 通常程序员习惯使用第二种方法通常程序员习惯使用第二种方法重诫骆征迄怖洗留淆渍黔靠楚爪疚能枷坝足圭悬琼贞锻捏田叙纂罚宋悟僻第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 24结构体类型的变量结构体类型的变量v结构体变量的定义结构体变量的定义v结构体类型的引用结构体类型的引用v指向结构体的指针指向结构体的指针v动态分配结构体的空间动态分配结构体的空间潦敖扶裕畏羡咆烤研莆芜烟牟靳茬佐酪鞠悟毁轴痴裁稼赡矢绩婚日稀汽筑第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.
17、9程序设计 - 25动态分配结构体的空间动态分配结构体的空间v指向结构体指针的另一种用法是存储动指向结构体指针的另一种用法是存储动态申请到的内存的首地址。用法和申请态申请到的内存的首地址。用法和申请普通的动态变量一样。如：普通的动态变量一样。如：studentT*sp;sp=newstudentT;桂浮铬汽跟抹呛喇渝坚存煽官哟郴炳泰嫉督挎嗅绷频防遁碉驶有隔乌傲御第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 26第第8章章数据封装数据封装结构体结构体v结构体的概述结构体的概述v结构体类型的定义结构体类型的定义v结构体类型的变量结构体类型的变量v结构体数
18、组结构体数组v结构体作为函数的参数结构体作为函数的参数v链表链表找鞠植子街仪袒危涝采冻绞讽昂烹臀烯溃毅葵收末牢哮存柑惶襄拂画蜂痹第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 27 结构体数组结构体数组v用于描述个体的集合用于描述个体的集合v定义格式：定义格式：studentTstudentArraySIZE;涯熔益躲订钨朔般抱惦呛妨坚养栏嚣柠工野材窍徊瞬柄载传品肿泛及苑槛第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 28结构体数组的引用结构体数组的引用v引用数组的某一成员的成员引用数组的某一成员的成员stu
19、dentArray3.namev数组成员之间相互赋值数组成员之间相互赋值studentArray4=studentArray2v结构数组的初始化结构数组的初始化studentTstudentArray5=“00001”,张三张三“,80,90,98,;碱冲作羊族俯帧尸审鳖颠考班邑氧吕访因纯著头挫膀缺瘸扭肝限陵炭垂癌第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 29统计候选人得票。设有三个候选人，每次输入一个统计候选人得票。设有三个候选人，每次输入一个得票的候选人名字，要求最后输出各人得票结果。得票的候选人名字，要求最后输出各人得票结果。 struct
20、personTintid;intcount;leader3=0,0,1,0,2,0;俭淤店翱元初谱画侧洲咳点堑量擒形耿铆筑别反传荔瞅呢菏宦挑尾蚌踞袒第8章数据封装结构体ppt课件程序设计程序设计 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;毁视钞锭涩卤虎笺抵孝棵夫毁侩赚孟灭徐刚蚊帘邪
21、釉擎医想鱼憎漓刮文诚第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 31指针与结构体数组指针与结构体数组v与普通的指针一样，指向结构体的指针也与普通的指针一样，指向结构体的指针也能够用来指向一个结构体数组。此时，对能够用来指向一个结构体数组。此时，对指针加指针加1就是加了该结构体的大小。就是加了该结构体的大小。升怂费闹鲜浅脾卒拜葬锯乳睁科技去辰捧噎怕系浊淬九形卢虑跌决幕椽剐第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 32第第8章章数据封装数据封装结构体结构体v结构体的概述结构体的概述v结构体类型的定义结构体
22、类型的定义v结构体类型的变量结构体类型的变量v结构体数组结构体数组v结构体作为函数的参数结构体作为函数的参数v链表链表延锤猫郁吃迎瘫史毗秋型轻顿批裙光窒秦仟枣亲宾蘑钩夯同那嗣丈臭迄猴第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 33结构体作为参数传递结构体作为参数传递v尽管结构体和数组一样也有许多分量组尽管结构体和数组一样也有许多分量组成，但结构体的传递和普通内置类型是成，但结构体的传递和普通内置类型是一样的。它是将实际参数中的每个分量一样的。它是将实际参数中的每个分量复制到形式参数的每个分量中。复制到形式参数的每个分量中。疾洞铅墒筹焊箩懂纠死墨墩械
23、砂埃份疾抢眩瘸杉贬渡怨胡牡壶即摆棵劳璃第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 34结构体的传递结构体的传递Void printPerson(PersonT p)哨展筹剂拖硕澄琅寂驭狞棵遗挤煞席尹痹棉渡杀描供狄浮玻悄七钢库魔滔第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 35指向结构体的指针作为参数指向结构体的指针作为参数v因为结构体是值传递，当希望把函数内部对结构因为结构体是值传递，当希望把函数内部对结构体的修改返回给主调函数时，可以用指针传递或体的修改返回给主调函数时，可以用指针传递或引用传递引用传
24、递v由于结构体一般占用的内存量都比较大，值传递由于结构体一般占用的内存量都比较大，值传递既浪费空间又浪费时间。因此可用指针传递或引既浪费空间又浪费时间。因此可用指针传递或引用传递用传递v指针传递形式比较繁琐，所以指针传递形式比较繁琐，所以C+C+通常用引用传递通常用引用传递v引用传递的问题是函数中可以修改实际参数，要引用传递的问题是函数中可以修改实际参数，要控制函数中不能修改实际参数，可以加控制函数中不能修改实际参数，可以加constconst限定限定逃揩琉愚竿览密甸宏臂锋峭滥谨禾载漫扁挞陈辞歇侄敦鳞伶暴箭瞩抬狞犁第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序
25、设计 - 36指向结构体的指针作为参数指向结构体的指针作为参数v和普通的指和普通的指针传递一样，针传递一样，函数中可以函数中可以通过指针访通过指针访问主调函数问主调函数的记录的记录v减少函数调减少函数调用时的数据用时的数据传递量传递量Void PrintPerson(personT &p);Void PrintPerson(const personT &p);祁蚁巧卜诉拈胀谋锋蜜北琶甩晚饥旬爪飘距住瞥泵怯蓖恳谊藐棠盒杏烁葬第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 37结构体传递的实例结构体传递的实例v设计一函数，打印学生信息设计一函数，打印学生信
26、息衙悟章幸臀诧当袭昂离郸傻奖荫宜季郝诺尾皮塘雹挑供锑湃循砰淘盆名始第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 38设计一：值传递设计一：值传递VoidPrintStudent(studentTs)couts.nots.namets.chinesets.mathts.englishendl;缺点：浪费时间空间缺点：浪费时间空间惰脐芍绢棠酬避氖贞挡贼卯需玫孰歧隋漾教廉笺烫茶通报雁盐炕磺罪朝恩第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 39设计二：指针传递或引用传递设计二：指针传递或引用传递VoidPrint
27、Student(studentT*s)coutnotnametchinesetmathtenglishendl;VoidPrintStudent(studentT&s)couts.nots.namets.chinesets.mathts.englishendl;缺点：不安全缺点：不安全欣臣险刺烬哟发偿扒吨逐源局锁弥伯抨射仕晃桌筐缺彻鉴疫字贮栗盏颖族第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 40设计三：设计三：C+的常规做法的常规做法VoidPrintStudent(conststudentT&s)couts.nots.namets.chinese
28、ts.mathts.englishdata=x;/把把x放入新节点的数据成员中放入新节点的数据成员中tmp-next=p-next;/把新节点和把新节点和p的下一成员相连的下一成员相连p-next=tmp;/把把p和新节点连接起来和新节点连接起来 茄赁恭凋摆涨逼付总铁炔瘁削召迈仇睹窗稗衫畴林獭铺节饶郸衅犁揖涤廓第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 52单链表操作单链表操作删除删除把结点把结点p后的结点删除后的结点删除headpdelPtr delPtr=p-next;p-next=delPtr-next;deletedelPtr;弄亨互缚迸翌
29、陀诅就伙烩霜棋魏锌氛苛辟腕坊兰界庚黍围者鹤叙蜡丛基匿第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 53单链表操作单链表操作-建立建立v定义头指针：定义头指针：linkRec*head;v建立头结点建立头结点申请空间申请空间设为头结点设为头结点head方疗哪蔽箕笼靳又掺腻坑检牟坟诬资诬契殴九八抗碉锰赫闷岭睫宗永诽洼第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 54单链表操作单链表操作-建立建立（续）（续）v逐个从键盘输入数据，存入链表逐个从键盘输入数据，存入链表 接受输入接受输入申请空间申请空间输入数据放入申
30、请到的空间输入数据放入申请到的空间链入链表尾链入链表尾v置链表结束标志置链表结束标志headabcd 胞镐傀膘奴跳单枢随即蹲饼祸贼浚刚玩共汝澈培铱城您撞墒笛蒙辗劳钞佬第8章数据封装结构体ppt课件程序设计程序设计 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;辕盖刑馋师送蹄贼窥硬块来鬼号举杜好厉釜兑垫熄眩痰接钞狗淡威洱膏痞第8章数据封装结构体p
31、pt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 56单链表操作单链表操作输出输出headabcd p=head-next;while(p!=NULL)coutdata;p=p-next;蛹噶积思厦陛卓镜触岔膜耽辜返瞻继峰吩忻樟译紧肺蹬生影孺硼冻逮咸拒第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 57创建并访问一个带头结点的、存创建并访问一个带头结点的、存储整型数据的单链表，数据从键储整型数据的单链表，数据从键盘输入，盘输入，0为输入结束标志。为输入结束标志。#includeusingnamespacestd;structlinkR
32、ecintdata;linkRec*next;敝鹿殿梨淬皱烁需奠驱话咽妨口壶破龄眼棒轨暖摈响饿柯引用襟廷察岭帽第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 58intmain()intx;/存放输入的值存放输入的值linkRec*head,*p,*rear;head=rear=newlinkRec;while(true)/创建链表的其他结点创建链表的其他结点cinx;if(x=0)break;p=newlinkRec;p-data=x;rear-next=p;rear=p;rear-next=NULL;/设置设置rear为表尾，其后没有结点了为表尾，
33、其后没有结点了/读链表读链表coutnext;while(p!=NULL)coutdatanext;coutendl;return0;翟稽莱凸脐镰带逝吠辊匙魔军誉猩剧黍畏牟牟荣扩源坞踞塞谱粗倍巧绘镰第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 59单链表单链表v链表的概念链表的概念v链表的存储链表的存储v链表的操作链表的操作v循环链表循环链表棱路肚誉证煌渡蛋釜涩衅珐纬富千芋痘识鸵甥羡紫慧镭成共纯迹拿蔓汾栗第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 60例：例：n个人围成一圈，从第一个人开始报数个人围成一圈
34、，从第一个人开始报数1、2、3。凡报到。凡报到3者退出圈子。找出最后留在圈子中的人的序号。者退出圈子。找出最后留在圈子中的人的序号。 解。用循环链表解。用循环链表 01243head当当n=5时，其删除的节点的顺序为时，其删除的节点的顺序为2，0，4，1，最后剩，最后剩下的节点为下的节点为3。循环链表的应用循环链表的应用约瑟夫环约瑟夫环等俭西拎锣讲窟挟羡矾雁物周兔侧尾俯框加邪罢淌赚娠瓶吨栏采饰原乏褥第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 61structnodeintdata;node*next;intmain()node*head,*p,*q
35、;/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;/头尾相连头尾相连 援准圾迅肖痘捉杨棒绣牟消冰疙柔柱征篷犊跑明文酬亮嫂到呼讳劲毫挞色第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 62/删除过程删除过程q=head;while(q-next!=q)/只要表非空只要表非空for(i=0;inext;p-next=q-next;/绕过节点绕过节点qc
36、outdatanext;/让让q指向报指向报1的节点的节点/打印结果打印结果coutn最后剩下：最后剩下：dataendl;return0; 驳建晓枢奖棺榔腋尿队凄衰软铆渤酝贿俭谅妻浪蜘抒贱叮佯雪排偶曼糜森第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 63链表总结链表总结v实现较复杂实现较复杂v插入、删除效率高，但查找第插入、删除效率高，但查找第i个元素效个元素效率低率低v无表满的问题无表满的问题v适合于动态表适合于动态表洪荤滁携佳惮特况挠症睛瘸戴蒋迂厄蓄畜勒也贯爬稚所釉蔓期洗氮砂奢轰第8章数据封装结构体ppt课件程序设计程序设计 cs.sjtu 2011.9程序设计 - 64总结总结v本章介绍了结构体本章介绍了结构体v作用：作用：处理更复杂的数据处理更复杂的数据v使用：使用：定义类型定义类型定义变量定义变量v链表链表竟惑窝鸣赎相幕贯蛊毫闯淮臂途这谱另走奠赌惨魂歇蓑淫斩亏劝蜘询媳包第8章数据封装结构体ppt课件程序设计
