《C++程序設(shè)計教程》PPT Chapter-6

第6章結(jié)構(gòu)體與鏈表皮德常nuaacs@126.com16.2結(jié)構(gòu)體的定義及應(yīng)用結(jié)構(gòu)體類型屬于用戶自定義類型，與指針類型有類似之處，必須先定義數(shù)據(jù)類型，然后再定義該種類型的變量。6.2.1定義結(jié)構(gòu)體類型

struct<結(jié)構(gòu)體類型名> { <成員列表>; };26.2.1定義結(jié)構(gòu)體類型例如1:structdate{

int year;

int month;

int day;};例如2:structstudent{

int ID; char name[20]; char gender; date birthday; doublescore[3];};36.2.2定義結(jié)構(gòu)體類型的變量1．先定義結(jié)構(gòu)體類型再定義變量例如：studentJohn,Merry；2．在定義結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量

structstudent { int ID; charname[20]; chargender; datebirthday; doublescore[3]; }John,Merry;46.2.2定義結(jié)構(gòu)體類型的變量3．使用無名結(jié)構(gòu)體類型定義結(jié)構(gòu)體變量

struct {

int ID; charname[20]; chargender; datebirthday; doublescore[3]; }John,Merry;56.2.3初始化結(jié)構(gòu)體類型的變量初始化方法有兩種：一種是用花括號“{}”括起來的值對結(jié)構(gòu)體變量初始化；例如：studentJohn={801,"Joe",'f',{1990,6,16},{88,99,80}};另一種是用同類型的結(jié)構(gòu)體變量初始化另外一個結(jié)構(gòu)體變量。studentMerry=John;66.2.4結(jié)構(gòu)體類型變量及其成員的引用1．引用結(jié)構(gòu)體變量的成員 例如：John.ID=901；2．整體引用結(jié)構(gòu)體變量 studentJohn={801,"Joe",'f',{1990,6,16},{88,99,80}}; studentMerry; Merry=John; //對結(jié)構(gòu)體變量整體賦值注意：(1)不能將結(jié)構(gòu)體變量作為一個整體進(jìn)行輸入或輸出，例如：

cout<<John; //錯誤

cin>>Merry; //錯誤(2)結(jié)構(gòu)體變量可以用作函數(shù)的參數(shù)，屬于按值傳遞。(3)函數(shù)可以返回一個結(jié)構(gòu)體變量。7【6.1簡略版】在main函數(shù)中輸入一個學(xué)生的學(xué)號、姓名、性別、出生日期和3門課程的成績，在另一函數(shù)print中輸出這個學(xué)生的信息，采用結(jié)構(gòu)體變函數(shù)參數(shù)。voidprint(student);voidmain(){ studentJohn; //定義一個結(jié)構(gòu)體變量

cin>>John.ID>>J>>John.gender;

cin>>John.birthday.year>>John.score[2];

print(John); //調(diào)用函數(shù)完成輸出}voidprint(students) //輸出參數(shù)s成員的值{

cout<<"學(xué)號:"<<setw(5)<<s.ID<<endl;

cout<<setw(5)<<s.birthday.month<<endl;}8使用結(jié)構(gòu)體變量作函數(shù)參數(shù)效率較低，why?可采用指向結(jié)構(gòu)體變量的指針或引用作參數(shù)，

例如： student*ps; studentJohn; 并且如下賦值：

ps=&John;則： J<=>ps->name<=>(*ps).name

思考：如何將程序【例6.1】中的函數(shù)print改為傳指針。96.2.5結(jié)構(gòu)體數(shù)組與指針1．定義結(jié)構(gòu)體數(shù)組和初始化定義的形式：

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}}};106.2.5結(jié)構(gòu)體數(shù)組與指針2．使用結(jié)構(gòu)體數(shù)組引用元素：

for(inti=0;i<4;i++)

cout<<stud[i].name;指針： student*ps;

ps=stud;

ps++；11【例6.2】假設(shè)一個班級有5個學(xué)生，從鍵盤輸入5個學(xué)生的學(xué)號、姓名、性別、出生日期和三門功課的成績，編程輸出個人平均分小于全班總均分的那些學(xué)生的信息。structdate{

intyear,month,day;};structstudent{

int ID; char name[20]; char gender; date birthday; double score[3];};12voidinput(student*,int);doubleaverage(student*,intn);//求總的平均分voidprint(student*,int);constint

studentNumber=5;intmain(){ studentstud[5];

input(stud,studentNumber);

print(stud,studentNumber);

return0;}13voidinput(student*ps,intn) //輸入函數(shù){

cout<<"請輸入如下學(xué)生信息"<<endl;

for(inti=0;i<n;i++) {

cin>>ps->ID;

cin>>ps->name;

cin>>ps->gender;

cin>>ps->birthday.year>>ps->birthday.month

>>ps->birthday.day;

cin>>ps->score[0]>>ps->score[1]>>ps->score[2];

ps++;

} }14voidprint(student*ps,intn){student*pStart;doubleaverAll,averPerson;

averAll=average(ps,n);

cout<<"總均分:"<<averAll<<endl;

for(pStart=ps;pStart<ps+n;pStart++){

averPerson=(pStart->score[0]+pStart->score[1] +pStart->score[2])/3; if(averPerson<averAll)

{ cout<<"\n個人均分:"<<averPerson<<endl;

cout<<"學(xué)號:"<<setw(5)<<pStart->ID;

cout<<“出生年:"<<pStart->birthday.year;

cout<<"成績:"<<setw(4)<<pStart->score[0]; }}}15doubleaverage(studentstud[],intn)//求總均分{ doubleaver=0;

for(inti=0;i<n;i++)

for(intj=0;j<3;j++) aver+=stud[i].score[j]; aver/=n*3; returnaver;}166.3用typedef定義類型語法格式為：

typedef<類型名1><類型名2>;例如：

typedef

int

WorkDay;

WorkDayday;定義新類型的步驟：1~3.176.4單向鏈表6.4.1鏈表的概念186.4單向鏈表196.4.2帶頭結(jié)點(diǎn)的單向鏈表常用算法【例6.3】帶頭結(jié)點(diǎn)的鏈表的常用算法。

#defineLENsizeof(NODE)typedef

structnode{

intdata;

node*next;}NODE;206.4.2帶頭結(jié)點(diǎn)的單向鏈表常用算法//創(chuàng)建一個空鏈表NODE*initlist(){ NODE*head; head=(NODE*)malloc(sizeof(NODE)); head->next=NULL; returnhead; //返回指向頭結(jié)點(diǎn)的地址，即頭指針}21NODE*create()//創(chuàng)建無序鏈表{ NODE*p1,*p2,*head;

inta;

cout<<"Creatingalist...\n"; p2=head=initlist();

cout<<"Pleaseinputanumber(if(-1)stop):";

cin>>a; //輸入第1個數(shù)據(jù)

while(a!=-1) //循環(huán)輸入數(shù)據(jù)，建立鏈表

{ p1=(NODE*)malloc(sizeof(NODE)); p1->data=a; p2->next=p1; p2=p1;

cout<<"Pleaseinputanumber(if(-1)stop):";

cin>>a;//輸入下一個數(shù)據(jù)

} p2->next=NULL;

return(head); //返回創(chuàng)建鏈表的首指針}22//輸出鏈表各結(jié)點(diǎn)值，也稱為對鏈表的遍歷voidprint(NODE*head){ NODE*p; p=head->next; //讓p指向第一個數(shù)據(jù)結(jié)點(diǎn)

if(p!=NULL) {

cout<<"Outputlist:"; while(p!=NULL) {

cout<<setw(5)<<p->data; p=p->next; }

cout<<"\n"; }}23//查詢結(jié)點(diǎn)數(shù)據(jù)為x的結(jié)點(diǎn)，返回指向該結(jié)點(diǎn)指針NODE*search(NODE*head,intx){ NODE*p; p=head->next; while(p!=NULL) {

if(p->data==x) returnp; //返回該結(jié)點(diǎn)指針

p=p->next; } returnNULL; //找不到返回空指針}24//刪除鏈表中值為num的結(jié)點(diǎn)，返回值:鏈表的首指針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);

cout<<"Deletesuccessfully"; } else cout<<"Notfound!"; returnhead;}25//釋放鏈表voidfree_list(NODE*head){ NODE*p;

while(head)

{ p=head; head=head->next;

free(p); }}26//插入結(jié)點(diǎn)，將s指向的結(jié)點(diǎn)插入鏈表，結(jié)果鏈表保持有序NODE*insert(NODE*head,NODE*s){ NODE*p; p=head;

while(p->next!=NULL&&p->next->data<s->data)

p=p->next; s->next=p->next;

p->next=s;

returnhead;}27//創(chuàng)建有序鏈表。返回值:鏈表的首指針NODE*create_sort(){ NODE*p,*head=NULL;

inta;

cout<<"Createanincreasinglist...\n"; head=initlist();

cout<<"Pleaseinputanumber(if(-1)exit):";

cin>>a; while(a!=-1) { p=(NODE*)malloc(sizeof(NODE)); p->data=a;

insert(head,p);

cout<<"Pleaseinputanumber(if(-1)exit):";

cin>>a; }

return(head);}28intmain(){ NODE*st,*head=NULL;

intnum; charc;

cout<<"\n\tCreatealist:\n"; head=initlist();//建立一條無序鏈表

while(1) {

cout<<"\n\tD:Delete