第07章C++結構體與鏈表

數組

。

第七章結構體與鏈表

7．1

結構體類型的定義、結構體變量的聲明及初始化、結構體變量的訪問方式

structdate //結構類型"日期"的定義{

int

year;

int

month;

int

day;};voidmain(){ dated={2000,1,1}; //結構體變量的聲明及初始化 cout<<d.year<<"年"; //結構體變量的訪問方式 cout<<d.month<<"月"; cout<<d.day<<"日"<<endl;}說明2：若在函數外定義結構體類型，則該結構體類型為全局類型。說明1：一般不單獨對結構體變量名進行操作，除非同類型結構體變量相互間的賦值；或者結構體變量作為函數的參數（下一節(jié)介紹）。voidmain(){ dated1={2000,1,1},d2;

d2=d1;//結構體變量間的賦值 cout<<"年："<<d2.year; cout<<"\t月："<<d2.month; cout<<"\t日："<<d2.day;}

說明3：結構體變量與簡單變量一樣，一旦聲明，系統(tǒng)將為之分配存儲空間，其大小是其中所有成員變量所占空間之和。因此，每個結構體變量也都有自己的地址。voidmain(){ date1d1={2000,1,1},d2; cout<<"結構體變量d1的大小是："<<sizeof(d1)<<endl; cout<<"結構體變量d2的大小是："<<sizeof(d2)<<endl; cout<<"結構體變量d1的地址是："<<&d1<<endl; cout<<"結構體變量d2的地址是："<<&d2<<endl;}7．2

結構體類型的嵌套

structdate //結構類型"日期"的定義{

int

year;

int

month;

int

day;};structstudent //結構類型"學生信息"的定義{

charno[6];

charname[10];

chargender;

date

birthday; char dpt[20]; int score;};students={"091001","李四",'m',{2000,1,1},"computer",92};//結構體變量的初始化voidmain()//結構體（嵌套）變量的訪問方式{ cout<<"學號："<<s.no; cout<<"\t姓名："<<; cout<<"\t性別："<<s.gender; cout<<"\t出生年月："<<s.birthday.year<<","; cout<<s.birthday.month<<","<<s.birthday.day; cout<<"\t所在系："<<s.dpt; cout<<"\t成績："<<s.score; cout<<endl;} 說明：結構體中的成員可以是另一個結構體的變量，但后者的類型定義必須在先。7．3

結構體數組及其用法voidmain()//結構體數組的訪問方式示例{ students[3]; for(inti=0;i<3;i++){ cout<<"請輸入學號\t姓名\t性別\t出生年月日\t所在系\t成績"; cin>>s[i].no>>s[i].name>>s[i].gender； cin>>s[i].birthday.year>>s[i].birthday.month>>s[i].birthday.day; cin>>s[i].dpt>>s[i].score; }cout<<"學號\t姓名\t出生年月\n";for(inti=0;i<3;i++){cout<<student[i].no<<'\t'<<student[i].name<<'\t';cout<<student[i].birthday.year<<'-'<<student[i].birthday.month<<'-'<<student[i].birthday.day; cout<<endl;}}（程序演示見.txt）7．4

結構體指針及其用法structdate {

int

year;

int

month;

int

day;};structstudnet

{

charno[6];

charname[10];

chargender;

date

birthday; char dpt[20]; int score;};students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s;voidmain()//結構體指針的訪問方式{ students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s; cout<<"學號\t姓名\t性別\t出生年月日\t所在系\t成績"<<endl; cout<<p->no<<"\t";//等價與(*p).no cout<<p->name<<"\t";//等價與(*p).name cout<<p->gender<<"\t";//等價與(*p).gender cout<<p->birthday.year<<","<<p->birthday.month<<","<<p->birthday.day;

//等價與(*p).birthday.day等等 cout<<"\t"<<p->dpt; cout<<"\t"<<p->score<<endl;} （程序演示見.txt）p7．5

結構體作為函數參數7.5.1 結構體變量為參數——值傳遞voidmain(){ voidmodifyStdScore(student);

students={"091001","李四",'m',{2000,1,1},"computer",92};modifyStdScore(s); cout<<"該學生現在的成績是："<<s.score<<endl;} voidmodifyStdScore(studentstd){ std.score=100;}參數傳遞的結果：

std=s運行結果

該學生現在的成績是：927.5.2 結構體引用為參數——引用傳遞voidmain(){ voidmodifyStdScore(student&);

students={"091001","李四",'m',{2000,1,1},"computer",92};modifyStdScore(s); cout<<"該學生現在的成績是："<<s.score<<endl;} voidmodifyStdScore(student&std){ std.score=100;}參數傳遞的結果：

&std=s運行結果

該學生現在的成績是：1007.5.3 結構體指針為參數——地址傳遞voidmain(){ voidmodifyStdScore(student*);

students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s;modifyStdScore(p);//等價與&s cout<<"該學生現在的成績是："<<s.score<<endl;} voidmodifyStdScore(student*std){

std->score=100;}參數傳遞的結果：

std=p即std=&s運行結果

該學生現在的成績是：100voidmain(){

studentsetStudent();

students;

s=setStudent(); cout<<"學號："<<s.no<<"\n姓名："<<<<"\n性別："<<s.gender; cout<<"\n出生年月："; cout<<s.birthday.year<<","<<s.birthday.month<<","<<s.birthday.day; cout<<"\n所在系："<<s.dpt<<"\n成績："<<s.score<<endl;}student setStudent(){ studentstd={"091001","李四","男",{2000,1,1},"計算機",92}; returnstd;}返回值傳遞：

s=std7．6

結構體作為函數返回值7.6.1 結構體變量為返回值7.6.2 結構體指針為返回值structdate//日期結構類型：由年、月、日3項組成{ intyear; intmonth; intday;};structstudent//學生信息結構類型：由姓名、生日及成績3項組成{ charname[10]; datebirthday; intscore;};voidmain(){ student*maxScoreStudent(student*,int); students[3],*p;for(inti=0;i<3;i++){cout<<"輸入姓名:";cin>>s[i].name; cout<<"輸入生日的年月日:";cin>>s[i].birthday.year>>s[i].birthday.month>>s[i].birthday.day; cout<<"輸入成績:";cin>>s[i].score;}

p=maxScoreStudent(s,3); cout<<"成績最好的學生是："<<endl;cout<<p->name<<","<<p->score<<","<<p->birthday.year<<",";cout<<p->birthday.month<<","<<p->birthday.day<<endl;}}

（程序演示見.txt）student*maxScoreStudent(student*st,intn){ studentsmax=*st,*pmax=st; for(inti=1;i<3;i++) if(st[i].score>smax.score) { smax=st[i]; pmax=st+i; } returnpmax;}返回值傳遞：

p=pmax7．7

結構體的應用——鏈表7.7.1 利用new、delete動態(tài)創(chuàng)建結構體變量voidmain()//動態(tài)創(chuàng)建結構體變量并訪問之{

student*p=newstudent;//該結構體變量沒有變量名，只有地址! cout<<"請輸入：學號姓名性別出生年月日所在系成績"<<endl; cin>>p->no>>p->name>>p->gender; cin>>p->birthday.year>>p->birthday.month>>p->birthday.day; cin>>p->dpt>>p->score; cout<<"該學生的信息是："endl; cout<<"學號\t姓名\t性別\t出生年月日\t所在系\t成績"<<endl; cout<<p->no<<"\t"<<p->name<<"\t"<<p->gender; cout<<"\t"<<p->birthday.year<<","<<p->birthday.month<<","<<p->birthday.day; cout<<"\t"<<p->dpt<<"\t"<<p->score<<endl;} 每當程序需要處理的結構體變量，類型相同、數目眾多且不可預知時，則可以利用動態(tài)創(chuàng)建的方式來實現——需要時創(chuàng)建之！然而，大量的指針卻不便于編程。有一種叫“鏈表”的數據結構可以解決這個問題——將一個動態(tài)創(chuàng)建的結構體變量的地址保存到另一個相同類型的結構體變量中——每個結構體變量都如此！structFigure//結構類型"人物"的定義{

char

no[6];

char

name[10]; int age;

Figure*

link;};例如，一個由結構體Figure的變量組成的存放人物信息的鏈表如下所示：頭指針7.7.2 鏈表的概念鏈表其實是一種“由結構變量自己來管理自己”的數據結構——每一個結構變量內部都保存著另一個結構變量的地址！而你只需要管好“頭指針”即可！顯然，鏈表是一種完全由用戶自行創(chuàng)建并管理、處理的數據結構：鏈表中的結構變量的類型定義、每個結構變量的動態(tài)創(chuàng)建、結構變量之間的鏈接。注意：為便于鏈表的處理，通常將鏈表最后一個結點中的后繼指針賦值為NULL！頭指針鏈表的建立過程：NULL7.7.3 鏈表的基本操作（由用戶定義的函數實現）（1）鏈表的遍歷——output(L)或Traversal(L):輸出鏈表L中每個結點的數據（2）鏈表的長度——Length(L):返回鏈表L中的結點個數（3）鏈表的搜索——search(L,x):若鏈表L中存在x結點則返回其指針;否則返回NULL（4）鏈表的刪除——delete(L,x):刪除鏈表L中第一個值為x的結點（5）鏈表的插入——insert(L,i,x):在鏈表L中的第i個結點前插入新結點x（6）鏈表的創(chuàng)建——creat():建立一個鏈表并返回其頭結點指針（7）鏈表的撤銷——destroy(L):撤銷鏈表L中的全部結點假定，鏈表L的類型定義如下：structnode{ ...........//其他數據成員 node*

next;};node*L;//頭指針聲明L程序示例1：鏈表的基本操作之一(鏈表的創(chuàng)建、打印)struct

stu{ char name[20];

//注意：結構體中的字符串成員不便聲明為“char*name;” stu *next;};voidmain(){ stu

*head,

*tail,

*p;

//頭結點指針haed、尾結點指針tail、工作指針p int

i; head

=

tail

=

NULL; for(

i

=

1;

i

<=

3;

i++

){ //建立一個包含3個節(jié)點的鏈表 p

=

new

stu;

//讓p指向一個新創(chuàng)建的結點 cout<<"請輸入姓名："<<endl; cin>>p->name;

//若name為字符指針，則不能這樣賦值! p->next

=

NULL;

//讓p的后繼為空（即p將作為鏈表中的最后一個結點） if(

head

==

NULL)

//若頭指針head為空，則讓head指向新創(chuàng)建的結點

head

=

p; else

//若頭指針不空，則讓p所指結點為尾結點

tail->next

=

p; tail

=

p;

//讓tail指向尾結點 }

cout<<"鏈表中的結點是："<<endl; p

=

head;

//使指針p指向鏈表的頭結點

while(

p

!=

NULL

){ //若p不空(即p所指結點存在),則打印該節(jié)點中數據

cout<<p->name<<","; p

=

p->next;

//注意此句p的作用：使p指向下一個結點！ } cout<<endl;}值得注意的是：鏈表的頭指針（保存著表頭結點的地址）是用戶掌控及訪問鏈表的唯一信息——一旦丟失，無處復得！因此，在鏈表的操作過程中，通常需要一些工作指針（如指針p、tail等）。而頭指針（如head）在建表后，一般將不再被改變——以免丟失頭結點的地址——丟失鏈表!!程序示例2：鏈表的基本操作之二(鏈表的創(chuàng)建、打印分別由函數實現)#include"stdafx.h"#include"iostream"usingnamespacestd;structstu{ char name[20]; int age; stu *next;};voidmain()//主函數{ stu*create(int); //聲明“創(chuàng)建鏈表”的函數create原型 voidoutput(stu*); //聲明“打印鏈表”的函數output原型 stu*head; //聲明鏈表的頭指針 head=create(5); //調用create函數來創(chuàng)建鏈表(長度為5) cout<<"鏈表中的信息是:"<<endl; output(head); //調用output函數來打印鏈表}

stu*create(intn)//創(chuàng)建長度為n的鏈表：返回鏈表的頭指針{ stu*head,*tail,*p;//head指向表頭、tail指向表尾、 //p指向動態(tài)申請的新結點。 inti; for(i=0;i<n;i++){ p=newstu; cout<<"inputNumberandAge"<<endl; cin>>p->name>>p->age;

p->next=NULL;//使pb所指結點沒有后繼——尾結點 if(i==0)//等價與“head==NULL” head=p; elsetail->next=p; tail=p; } returnhead;//返回鏈表頭指針的值（表頭結點的地址）}voidoutput(stu*head)//打印鏈表（頭指針為head）{ stu*p; //聲明工作指針p p=head; //開始時，讓p指向鏈表頭結點 while(p!=NULL) { cout<<"姓名是:"<<p->name<<",年齡是"<<p->age<<endl; p=p->next;//注意此句的作用——指向鏈表中的下一個結點!! }}（程序演示見.txt）說明：“鏈表打印”函數output(head)也叫做“鏈表遍歷”函數showList(head)。（請參見《易學C++》P.101）讓“打印函數”output()輸出的鏈表結果更直觀、形象：voidoutput(stu*head)//2.打印鏈表{ stu*p;

cout<<"head"; p=head; while(p!=NULL) { cout<<"→（"<<p->num<<"、"<<p->name<<"、"<<p->score<<"）"; p=p->next; } cout<<endl;}

程序示例3：鏈表創(chuàng)建函數的另一種算法、打印函數的遞歸算法#include"stdafx.h"#include"iostream"usingnamespacestd;structstu{ char name[20]; int age; stu *next;};voidmain()//主函數{ stu*create(int); //聲明“創(chuàng)建鏈表”的函數create原型 voidoutput(stu*); //聲明“打印鏈表”的函數output原型 stu*head; //聲明鏈表的頭指針 head=create(3); //調用create函數來創(chuàng)建鏈表(長度為5) cout<<"鏈表中的信息是:"<<endl; output(head); //調用output函數來打印鏈表}

stu*create(intn)//（逆向）創(chuàng)建鏈表：返回鏈表的頭指針{ node*head=NULL,*p; inti; for(i=0;i<n;i++) { p=newnode; cout<<"inputNmaeandAge"<<endl; cin>>p->name>>p->age; p->next=head; head=p; } returnhead;}voidoutput1(stu*head)//遞歸算法{ if(head!=NULL) { cout<<"姓名是:"<<head->name<<",年齡是"<<head->age<<endl;

output1(head->next); }}程序示例4：求鏈表的長度（自行實現）程序示例5：鏈表的查詢（參見講義P.104）程序示例6：鏈表的刪除（參見講義P.105）程序示例7：鏈表的插入（參見講義P.104）關于“鏈表的基本操作函數”的一些說明：（1）由于結點類型的不同(比如，結點類型為figure、node、student等)，其鏈表的基本操作函數的具體實現就會不同！（2）在一般教材中，每種鏈表的“基本操作函數”通常只定義有6、7個(比如，creat()、output()、insert()、delete()、search()、length()、DestroyList()

等）。而在實際應用中，則可根據實際需要來定義（比如有，獲取第i個結點元素getElem(L，i)、修改第i個結點元素putElem(L，i，x)、兩個鏈表的合并merger(La，Lb)、鏈表的初始化init(L)等等）。a0a1an-1

head…a0a1an-1

head…通常在鏈表的第一結點之前增設一個稱為“頭結點”的結點——也叫做“哨兵結點”，其數據域一般不存放任何數據。此舉僅出于簡化程序設計的考慮。關于鏈表結構的一個約定head空鏈表的情形：“哨兵(Sentinel)”結點程序示例8：帶哨兵鏈表的初始化函數、插入函數、打印函數structnode{ char name[20]; int age; node *next;};voidmain(){ boolinsert(node*,int,node*); //鏈表的插入函數 voidoutput(node*); //鏈表的打印函數 node*init(); //鏈表的初始化函數 node*head=init(),*p;//初始化表頭指針head（指向帶哨兵的空鏈表） intn; cout<<"請輸入鏈表的長度:"<<endl; cin>>n; for(inti=1;i<=n;i++)//建立長度為n的鏈表head（功能相當于函數create） { p=newnode; cout<<"請輸入鏈表中的第"<<i<<"個數據（姓名、年齡）:"<<endl; cin>>p->name>>p->age; insert(head,i,p); //在鏈表head中的第i個結點前插入新結點p } output(head);}

voidoutput(node*head)

//鏈表的輸出{ node*p=head->next;

//讓p指向第一個元素結點a1 while(p!=NULL) { cout<<"姓名是:"<<p->name<<",年齡是"<<p->age<<endl; p=p->next; }}node*init()//鏈表的初始化：創(chuàng)建一個空表（帶哨兵結點）{ node*head=newnode; //創(chuàng)建哨兵結點 head->next=NULL; returnhead;}

boolinsert(node*head,inti,node*newnode){//在鏈表head中的第i(1~n+1)個結點前插入新結點newnode node*p=head; intn=0; while(p!=NULL&&n<i-1)//定位第i-1個結點 { p=p->next; n++; }

if(p!=NULL&&n==i-1)

//等價與if(i<=n+1&&i>=1) {//將指針newnode所指結點插入到p所指結點的后邊 newnode->next=p->next; p->next=newnode; return1; } else //i>表長+1或i<1——插入位置不存在 return0;}程序示例9：帶哨兵結點鏈表的刪除函數（課堂討論） delete(head,no) //刪除鏈表head中學號為no的結點及 delete(head,i) //刪除鏈表head中第i個結點注意： 為便于日后《數據結構》的學習，從現在開始，凡是有關鏈表的程序設計，建議使用帶哨兵結點的鏈表結構！ 除特別說明外，以后的鏈表均指帶哨兵結點。delete(head,no)//刪除鏈表head中學號為no的結點voiddelete(

stu*head,

intno

)

//刪除鏈表中學號等于no的節(jié)點。

{ stu*p=head->next,q=head; while(p!=NULL

&&

p->num!=no

){ q=p; p=p->next; } if(p==NULL){ cout<<"不存在學號為"<<no<<"的學生\n"; return; } else{ q->next=p->next; deletep; }}

delete(head,i) //刪除鏈表head中第i個結點voiddelete(stu*head,

inti)//刪除鏈表head中第i個結點(i的范圍為：1~n){ stu*

p

=

head,q; intn=0; while((p->next!=

NULL)&&(n<i-1)) {

n++; p=p->next; } if((p->next!=

NULL)&&(n==i-1)

) { q=

p->next;

p->next

=

p->next->next; deleteq; } else

cout<<"不存在學號為"<<no<<"的學生\n";}程序示例10： 建立一個鏈表，每個節(jié)點包括：學號、姓名、成績；編程：測試該鏈表的各基本操作函數。structstu{ intnum; charname[10]; intscore; structstu*next;};voidmain(

)

//主函數:用于調試各函數{ stu*

create();

//create函數：創(chuàng)建鏈表 stu*

search(stu*,int);//search函數：搜索鏈表中學號為no的結點 void

output(stu*);

//output函數：遍歷打印鏈表 void

delete(stu*,int);

//delete函數：刪除學號為no的結點 stu*

locate(stu*,int);//locate函數：搜索鏈表中第i個結點 stu*

prior(stu*,int);

//prior函數：搜索鏈表中學號為no的前一個結點 int

length(stu*);

//length函數：求鏈表的長度 stu

*L,

*p; int

no,i; char

choice;

L=

create(); //調用creat函數創(chuàng)建鏈表并將頭指針返回給指針L cout<<"鏈表中的信息是:\n";

output(L); //調用output函數打印鏈表L程序示例10： 建立一個鏈表，每個節(jié)點包括：學號、姓名、成績；編程：測試該鏈表的各基本操作函數。

do{

cout<<"\n請輸入你要找的學號：";

cin>>no; if(

p

=

search(L,no)

)

//調用search函數搜索鏈表L中學號為no的結點 cout<<"-->（"<<p->num<<","<<p->name<<","<<p->score<<"）\n"; else cout<<"學號為"<<no<<"的學生不存在！\n"; cout<<"\n你要找?guī)滋柕那耙晃粚W生？";

cin>>no; if(

p

=

prior(L,no)

) //調用prior函數搜索鏈表L中學號為no的前一個結點 cout<<no<<"號的前一個學生是:（"<<p->name<<","<<p->score<<"）\n"; else cout<<no<<"號的前一個學生不存在！\n"; cout<<"你想刪除的學號是：\t";

cin>>no;

delete(L,

no

);

//調用delete函數刪除鏈表L中學號為no的節(jié)點 cout<<"\n刪除學號"<<no<<"后，鏈表中的信息是:\n"; cout<<"當前鏈表的長度是："<<length(L)<<endl;

//調用函數length獲取鏈表L的長度 cout<<"當前鏈表中的數據有："<<endl;

output(L); cout<<"你想找鏈表中第幾個結點？\t";

cin>>i; if(

p

=

locate(L,i)

)

//調用locate函數搜索鏈表L中第i個結點 cout<<"\n該結點是：("<<p->num<<","<<p->name<<","<<p->score<<")\n"; else cout<<"第"<<no<<"個結點不存在！\n"; cout<<"\n您還想繼續(xù)嗎？(

Y

/

N

)";

cin>>choice;

}while(

choice

==

'Y'

||

choice

==

'y');

cout<<"謝謝您的使用！******再見！\n";}

//其中各基本操作函數的實現及其測試程序請見.txt課堂練習：假設鏈表的結點類型定義為：structnode{ char name[20]; int num; node *next;};1、編寫鏈表的“創(chuàng)建”函數ordList_create(head)——輸入若干結點數據并按學號遞增序存入鏈表head中——創(chuàng)建一個有序鏈表L。2、編寫鏈表的“合并”函數union(La，Lb)——將存在于線性表

LB

中而不存在于線性表LA中的學號并入到線性表LA中去課堂練習1分析：鏈表的“創(chuàng)建”函數or