C++课件(南航皮德常)6

1第6章结构体与链表皮德常[e-mail]26.2结构体的定义及应用结构体类型属于用户自定义类型，与指针类型有类似之处，必须先定义数据类型，然后再定义该种类型的变量。6.2.1定义结构体类型struct结构体类型名{成员列表;};36.2.1定义结构体类型例如1:structdate{intyear;intmonth;intday;};例如2:structstudent{intID;charname[20];chargender;datebirthday;doublescore[3];};46.2.2定义结构体类型的变量1．先定义结构体类型再定义变量例如：studentJohn,Merry；2．在定义结构体类型的同时定义结构体变量structstudent{intID;charname[20];chargender;datebirthday;doublescore[3];}John,Merry;56.2.2定义结构体类型的变量3．使用无名结构体类型定义结构体变量struct{intID;charname[20];chargender;datebirthday;doublescore[3];}John,Merry;66.2.3初始化结构体类型的变量初始化方法有两种：•一种是用花括号“{}”括起来的值对结构体变量初始化；例如：studentJohn={801,Joe,'f',{1990,6,16},{88,99,80}};•另一种是用同类型的结构体变量初始化另外一个结构体变量。studentMerry=John;76.2.4结构体类型变量及其成员的引用1．引用结构体变量的成员例如：John.ID=901；2．整体引用结构体变量studentJohn={801,Joe,'f',{1990,6,16},{88,99,80}};studentMerry;Merry=John;//对结构体变量整体赋值注意：(1)不能将结构体变量作为一个整体进行输入或输出，例如：coutJohn;//错误cinMerry;//错误(2)结构体变量可以用作函数的参数，属于按值传递。(3)函数可以返回一个结构体变量。【6.1简略版】在main函数中输入一个学生的学号、姓名、性别、出生日期和3门课程的成绩，在另一函数print中输出这个学生的信息，采用结构体变函数参数。voidprint(student);voidmain(){studentJohn;//定义一个结构体变量cinJohn.IDJohn.nameJohn.gender;cinJohn.birthday.yearJohn.score[2];print(John);//调用函数完成输出}voidprint(students)//输出参数s成员的值{cout学号:setw(5)s.IDendl;coutsetw(5)s.birthday.monthendl;}使用结构体变量作函数参数效率较低，why?可采用指向结构体变量的指针或引用作参数，例如：student*ps;studentJohn;并且如下赋值：ps=&John;则：John.name=ps-name=(*ps).name思考：如何将程序【例6.1】中的函数print改为传指针。106.2.5结构体数组与指针1．定义结构体数组和初始化定义的形式：studentstudOne[4];初始化的形式：studentstudTwo[4]={{801,Joe,'F',{1990,6,16},{88,99,80}},{802,Smith,'F',{1991,6,1},{68,79,87}},{805,Merry,'M',{1992,3,23},{78,89,79}},{808,Anna,'M',{1993,7,6},{98,69,68}}};116.2.5结构体数组与指针2．使用结构体数组引用元素：for(inti=0;i4;i++)coutstud[i].name;指针：student*ps;ps=stud;ps++；【例6.2】假设一个班级有5个学生，从键盘输入5个学生的学号、姓名、性别、出生日期和三门功课的成绩，编程输出个人平均分小于全班总均分的那些学生的信息。structdate{intyear,month,day;};structstudent{intID;charname[20];chargender;datebirthday;doublescore[3];};voidinput(student*,int);doubleaverage(student*,intn);//求总的平均分voidprint(student*,int);constintstudentNumber=5;intmain(){studentstud[5];input(stud,studentNumber);print(stud,studentNumber);return0;}voidinput(student*ps,intn)//输入函数{cout请输入如下学生信息endl;for(inti=0;in;i++){cinps-ID;cinps-name;cinps-gender;cinps-birthday.yearps-birthday.monthps-birthday.day;cinps-score[0]ps-score[1]ps-score[2];ps++;}}voidprint(student*ps,intn){student*pStart;doubleaverAll,averPerson;averAll=average(ps,n);cout总均分:averAllendl;for(pStart=ps;pStartps+n;pStart++){averPerson=(pStart-score[0]+pStart-score[1]+pStart-score[2])/3;if(averPersonaverAll){cout\n个人均分:averPersonendl;cout学号:setw(5)pStart-ID;cout“出生年:pStart-birthday.year;cout成绩:setw(4)pStart-score[0];}}}doubleaverage(studentstud[],intn)//求总均分{doubleaver=0;for(inti=0;in;i++)for(intj=0;j3;j++)aver+=stud[i].score[j];aver/=n*3;returnaver;}176.3用typedef定义类型•语法格式为：typedef类型名1类型名2;例如：typedefintWorkDay;WorkDayday;定义新类型的步骤：1~3.186.4单向链表6.4.1链表的概念196.4单向链表206.4.2带头结点的单向链表常用算法【例6.3】带头结点的链表的常用算法。#defineLENsizeof(NODE)typedefstructnode{intdata;node*next;}NODE;216.4.2带头结点的单向链表常用算法//创建一个空链表NODE*initlist(){NODE*head;head=(NODE*)malloc(sizeof(NODE));head-next=NULL;returnhead;//返回指向头结点的地址，即头指针}NODE*create()//创建无序链表{NODE*p1,*p2,*head;inta;coutCreatingalist...\n;p2=head=initlist();coutPleaseinputanumber(if(-1)stop):;cina;//输入第1个数据while(a!=-1)//循环输入数据，建立链表{p1=(NODE*)malloc(sizeof(NODE));p1-data=a;p2-next=p1;p2=p1;coutPleaseinputanumber(if(-1)stop):;cina;//输入下一个数据}p2-next=NULL;return(head);//返回创建链表的首指针}//输出链表各结点值，也称为对链表的遍历voidprint(NODE*head){NODE*p;p=head-next;//让p指向第一个数据结点if(p!=NULL){coutOutputlist:;while(p!=NULL){coutsetw(5)p-data;p=p-next;}cout\n;}}//查询结点数据为x的结点，返回指向该结点指针NODE*search(NODE*head,intx){NODE*p;p=head-next;while(p!=NULL){if(p-data==x)returnp;//返回该结点指针p=p-next;}returnNULL;//找不到返回空指针}//删除链表中值为num的结点，返回值:链表的首指针NODE*delete_one_node(NODE*head,intnum){NODE*p,*temp;p=head;while(p-next!=NULL&&p-next-data!=num)p=p-next;temp=p-next;if(p-next!=NULL){p-next=temp-next;free(temp);coutDeletesuccessfully;}elsecoutNotfound!;returnhead;}//释放链表voidfree_list(NODE*head){NODE*p;while(head){p=head;head=head-next;free(p);}}//插入结点，将s指向的结点插入链表，结果链表保持有序NODE*insert(NODE*head,NODE*s){NODE*p;p=head;while(p-next!=NULL&&p-next-datas-data)p=p-next;s-next=p-next;p-next=s;returnhead;}//创建有序链表。返回值:链表的首指针NODE*create_sort(){NODE*p,*head=NULL;inta;coutCreateanincreasinglist...\n;head=initlist();coutPleaseinputanumber(if(-1)exit):;cina;while(a!=-1){p=(NODE*)malloc(sizeof(NODE));p-data=a;insert(head,p);coutPleaseinputanumber(if(-1)exit):;cina;}return(head);}intmain(){NODE*st,*head=NULL;intnum;charc;cout\n\tCreatealist:\n;head=initlist();//建立一条无序链表while(1){cout\n\tD:DeleteI:InsertP:Print\\S:SearchE:Exit\n;cinc;//c=getch();switch(toupper(c)){case'I':st=(NODE*)malloc(LEN);coutPleaseinputanumbertobeinserted:;cinst-data;insert(head,st);break;case'D':coutPleaseinputanumbertobedeleted:;cinnum;delete_one_node(head,num);//删除一个结点