《C++程序设计课件：第10章 结构》由会员分享，可在线阅读，更多相关《C++程序设计课件：第10章 结构（42页珍藏版）》请在金锄头文库上搜索。
1、第十章 结构2本章主要内容o10.1 结构o10.2 结构与指针 o10.3 结构与数组 o10.4 传递结构参数o10.5 返回结构 o10.6 链表结构o10.7 创建与遍历链表 o10.8 删除链表结点o10.9 插入链表结点o10.10 结构应用：Josephus问题o作业310.1 结构1.结构的基本概念 o数据类型：基本类型、指针类型、构造类型o构造类型：数组、结构体o结构体可以把不同类型的数据对象组织在一起，而形成一种新的类型的变量，这种变量属于构造类型，由用户自己进行构造，以处理一些复杂的数据。 o例如，希望一个学生的信息组成一条记录，n个学生n条记录，便于管理和处理410.1
2、 结构2.定义结构类型和结构变量 o必须先定义结构体类型，然后才可以定义该类型的变量(1)定义结构类型 一般格式： struct 结构名 结构体成员1定义； 结构体成员2定义； 结构体成员n定义； ; 510.1 结构o例：通讯录：姓名字符串 地址字符串或者： 电话无符号长整型 邮政编码无符号长整型o定义： struct address char *name; char *add; unsigned long tel; unsigned long post_code; ;610.1 结构o或者：struct address char name10; char add30; unsigned l
3、ong tel; unsigned long post_code; ; o即：用户自己定义了一个新的类型：address类型，该类型属于结构体的数据结构o注意：定义一个结构仅仅声明了一个新的数据类型，系统对结构类型不分配内存710.1 结构（2）结构变量的定义o一旦定义了结构类型，就可以定义该类型的变量结构变量o形式1：先定义结构类型，再定义结构变量o例：struct address char *name; char *add; unsigned long tel; unsigned long post_code; ; struct address add1,add2; 810.1 结构o形式
4、2：定义结构类型的同时，定义结构变量o例：struct address char *name; char *add; unsigned long tel; unsigned long post_code; add1,add2;910.1 结构o方法3：直接定义，但无结构类型名，只有结构变量名（无名结构）o例：struct char *name; char *add; unsigned long tel; unsigned long post_code; add1,add2; 1010.1 结构3.访问结构成员（1）结构体成员运算符：. 优先级：最高 结合性：左右（2）结构体变量的成员 例：ad
5、d1 . name add1 . tel add2 . name add2 . post_code 1110.1 结构（3）引用o结构体成员与单个变量一样，可以进行各种合法的运算、赋值等操作，但是必须指出其所属的变量名o例如：add1.post_code=200330; 1210.1 结构struct date int year; int month; int day;struct student int number; char name10; char sex; int age; struct date brithday; char add30;student1,s100; student
6、1.number=12345;student1.name=“li lin”;student1.sex=f;student1.age=20student1.brithday.day=29;student1.brithday.month=7;student1.brithday.year=1984;s0.number=1;s7.brithday.day=5;student1.brithday.year+;s1.number=s0.number+1;1310.1 结构4.结构初始化和赋值（1）初始化o在定义结构体变量的同时赋初值，不能在结构体类型的定义中赋初值1410.1 结构struct stude
7、nt int number; char name10; char sex; int age; struct date int year,month,day; brithday; /内嵌定义另一个结构类型和对象 char add30; student1=9801,余雨,m,18,1980,12,1,华山路1954号; /初始化o或者：struct student student1=9801,余雨,m,18,1980,12,1,华山路1954号;1510.1 结构（2）赋值o由于结构大小确定、成员次序固定，所以，可以把一个结构体变量直接赋值给另一个同类型的结构体变量o上例中的：s99=studen
8、t1;1610.2 结构与指针o指向结构体变量的起始地址o结构体变量在内存中的存放： 按各成员在结构体类型定义中的次序，顺序存放 1710.2 结构与指针1.结构体变量的指针的定义o格式：结构名 * 指针变量名；o运算符：-o优先级：与运算符“”相同o结合性： 左右o当一个指针p定义为某个结构体类型的指针后，该指针可以指向任何同类型的变量；并且可以通过指针间接访问成员 1810.2 结构与指针o访问结构体的成员： 直接访问：student1.name 间接访问：p=&student1; p-nameo(*p)：表示p所指向的那个结构体变量o例如：如果p=&student1;表示结构体变量stu
9、dent1的成员name的值的形式有： student1.name (*p). name p-name 等价：表示结构体变量等价：表示结构体变量student1的成员的成员name的值的值1910.3 结构与数组结构数组中，每个元素都是结构变量，访问结构数组元素中的成员，方法与前类似。例如，下面程序中对一个Person结构数组进行“冒泡排序”，工资高的排在后面。 /ch10_5.cpp#include struct Person char name20; unsigned long id; float salary;Person allone6=jone,12345,339.0,david,1
10、3916,449.0 , marit,27519,311.0,jasen,42876,623.0, peter,23987,400.0,yoke,12335,511.0;int main( ) Person temp; for(int i=1;i6;i+) for(int j=0;jallonej+1.salary) temp=allonej;allonej=allonej+1;allj+1=temp; for( int k=0;k6;k+) coutallonek.name allonek.id allonek.salary endl; 运行结果为：运行结果为：marit 27519 311
11、jone 12345 339peter 23987 400david 13916 449yoke 12335 511jasen 42876 6232110.4 传递结构参数o即：把结构变量作为实参传递给形参o如果形参是实参的引用，则实参与形参之间不进行拷贝 1.传递结构值/ch10_7.cpp#include struct Person char name20; unsigned long id; float salary;void print( Person pr ) coutpr.name pr.id pr.salaryendl;Person allone4=jone,12345,339.
12、0,david,13916,449.0, marit,27519,311.0,yoke,12335,511.0;int main( ) for(int i=0;I4;i+) print(allonei); return 0;程序运行结果为：程序运行结果为：Jone 12345 339david 13916 449marit 27519 311yoke 12335 5112310.4 传递结构参数2.传递结构的引用/ch10_8.cpp#include struct Person char name20; unsigned long id; float salary;void print( Pe
13、rson& pr ) coutpr.name pr.id pr.salaryendl;Person allone4=jone,12345,339.0,david,13916,449.0, marit,27519,311.0,yoke,12335,511.0;int main( ) for(int i=0;i4;i+) print(allonei); return 0;程序运行结果为：程序运行结果为：Jone 12345 339david 13916 449marit 27519 311yoke 12335 5112410.5 返回结构（选讲）o一个函数的返回值可以是一个结构变量，如果返回的是结
14、构的“引用”或是结构指针，则注意被返回的结构变量不能是局部变量。 1. 返回结构/Ch10_9.cpp#include struct Person char name20; unsigned long id; float salary; ;Person GetPerson( ) Person temp; couttemp.name; couttemp.idtemp.salary; return temp;void print(Person& p ) coutp.name p.id p.salaryendl;int main( ) Person employee3; for(int i=0;in
15、ext=0, pe=p结束 3010.7 创建与遍历链表2.遍历与输出链表输出链表的过程：链头指针：ph链尾指针：pep=ph，执行2p=0?(是空链？)，是执行4；否则执行3输出：*p，p=p-next，重复步骤2 结束 3110.8 删除链表结点o删除结点： p:当前结点指针，p0:前一结点指针1ph=0?(空链？)，是输出“空链”，执行8；否则p=ph，执行22输入被删除结点的信息3p-成员值 = 输入信息？，是执行5，否则执行44. p0=p，p=p-next，p=0?(链结束？)，是输出“找不到被删除结点”，然后执行8，否则重复步骤35删除该节点：p=ph?(链首结点)，是，ph=p
16、-next，然后执行7；否则执行66p0-next=p-next7释放p所指向的内存单元8结束 3210.9 插入链表结点o插入结点：1Ph=0?(空链？)，调用“添加结点函数”(append()，调用毕执行9；否则p=ph，p0=ph(p0=插入的定位结点的前一个结点的地址)，执行22输入插入点信息3p-成员值 = 输入信息？，是执行5，否则执行44. p0=p，p=p-next，p=0?(链结束？)，是输出“找不到插入结点”，然后执行8，否则重复步骤35pp=新分配内存单元的地址，pp!=0?(分配成功？)，是输出“分配失败”，然后执行8，否则执行66p=ph?(链首结点)，是：ph=pp
17、，pp-next=p，然后执行8；否则执行77p0-next=pp，pp-next=p8结束 3310.10 结构应用Page 33 小孩围成圈，用环链表来表达是最自然不过的。每个结点代表一个小孩。每个结点是一种结构，内含小孩属性（编号）和结构指针（指向下一个小孩）。 一旦构成了环链，数小孩的事就是在环链中依次经历结点。小孩的离开就是代表该小孩的结点从链中删除。删除后的链表仍是环链表。 不断数小孩到一定个数时，便删除，如此循环，直到只剩最后一个。该结点自己指向自己。此时，该结点代表的小孩就是胜利者。 为了进行链表的删除，需要有“哨兵”结点，该结点指向当前被删结点，见图10-6。3410.10
18、结构应用pivotpJose6754321npCurrent图图10-6 数完第一次小孩数，准备删除结点的情形数完第一次小孩数，准备删除结点的情形3510.10 结构应用Page 35 由于是环链表，所以没有链首指针，只有当前指针pCurrent。但作为链表主体的数组，其第一个元素的地址必须要记住，因为从堆中分配的空间，有义务要归还（用pJose指向数组首地址）。 删除当前结点（pCurrent指向的结点），意味着哨兵指向的结点要“跨过”当前结点(图中虚线)，然后当前结点指针pCurrent立即指向哨兵结点。下一次数小孩则循着虚线开始。试看Joswphus问题解法第二版：/jose2.cpp
19、#include #include struct jose int code; jose* next;int main() /赋初值赋初值 int numOfBoys,interval; coutplease input the number of boys ,n numOfBoysinterval; /建立小孩结构数组建立小孩结构数组 jose* pJose=new josenumOfBoys; jose* pCurrent=pJose;/当前结点指针当前结点指针 /初始化结构数组：构成环链，小孩编号，输出编号初始化结构数组：构成环链，小孩编号，输出编号 int itemsInLine=0;
20、/输出项数输出项数 for(int i=1;inext=pJose+i%numOfBoys;/链到下一个元素链到下一个元素 pCurrent-code=i; /小孩编号小孩编号 pCurrent=pCurrent-next; /改变当前位置改变当前位置 if(itemsInLine+%10=0) coutendl; coutsetw(4)next!=pCurrent) /处理未获胜的所有小孩处理未获胜的所有小孩 for(int j=0;jnext; if (itemsInLine+% 10= =0) /输出小孩输出小孩 coutendl; coutsetw(4)code; pivot-next
21、=pCurrent-next; /小孩脱链小孩脱链 pCurrent=pivot; coutnn the winner is code endl; delete pJose; /end of main( )运行结果为：运行结果为： please input the number of boys, interval of counting:15 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 6 9 12 15 4 8 13 2 10 1 11 7 4the winner is 54010.10 结构应用 程序从堆中分配小孩结构数组空间，因而可以在运行时确定小孩数
22、，给求解问题带来了灵活性。 在初始化链表的时候，将小孩数组顺序地链接起来，直至最后一个结点链到第一个结点，构成环链表。在环链表的形成过程中，给小孩编号和依次输出全体小孩。 如果起点可以是任意一个小孩结点，则程序应作如何修改呢？41作业1、利用结构类型编制程序，实现输入一个学生的数学期中和期末成绩，然后计算并输出其平均成绩。答案：2、已知head指向一个带头结点的单向链表，链表中每个结点包含字符数组数据和指向本结构结点的指针。编写函数实现在值为“jone”的结点前插入值为“marit”的结点，若没有值为“jone”的结点，则插在链表最后。答案：42作业3、建立一个10结点的单向链表，每个结点包括：学号、姓名、年龄、性别。对其进行排序，采用插入排序法，按学号从小到大排序。答案：
