第07章C++結(jié)構(gòu)體與鏈表

數(shù)組

。

第七章結(jié)構(gòu)體與鏈表

7．1

結(jié)構(gòu)體類型的定義、結(jié)構(gòu)體變量的聲明及初始化、結(jié)構(gòu)體變量的訪問方式

structdate //結(jié)構(gòu)類型"日期"的定義{

int

year;

int

month;

int

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

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

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

結(jié)構(gòu)體類型的嵌套

structdate //結(jié)構(gòu)類型"日期"的定義{

int

year;

int

month;

int

day;};structstudent //結(jié)構(gòu)類型"學(xué)生信息"的定義{

charno[6];

charname[10];

chargender;

date

birthday; char dpt[20]; int score;};students={"091001","李四",'m',{2000,1,1},"computer",92};//結(jié)構(gòu)體變量的初始化voidmain()//結(jié)構(gòu)體（嵌套）變量的訪問方式{ cout<<"學(xué)號(hào)："<<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成績(jī)："<<s.score; cout<<endl;} 說明：結(jié)構(gòu)體中的成員可以是另一個(gè)結(jié)構(gòu)體的變量，但后者的類型定義必須在先。7．3

結(jié)構(gòu)體數(shù)組及其用法voidmain()//結(jié)構(gòu)體數(shù)組的訪問方式示例{ students[3]; for(inti=0;i<3;i++){ cout<<"請(qǐng)輸入學(xué)號(hào)\t姓名\t性別\t出生年月日\t所在系\t成績(jī)"; 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<<"學(xué)號(hào)\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

結(jié)構(gòu)體指針及其用法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()//結(jié)構(gòu)體指針的訪問方式{ students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s; cout<<"學(xué)號(hào)\t姓名\t性別\t出生年月日\t所在系\t成績(jī)"<<endl; cout<<p->no<<"\t";//等價(jià)與(*p).no cout<<p->name<<"\t";//等價(jià)與(*p).name cout<<p->gender<<"\t";//等價(jià)與(*p).gender cout<<p->birthday.year<<","<<p->birthday.month<<","<<p->birthday.day;

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

結(jié)構(gòu)體作為函數(shù)參數(shù)7.5.1 結(jié)構(gòu)體變量為參數(shù)——值傳遞voidmain(){ voidmodifyStdScore(student);

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

std=s運(yùn)行結(jié)果

該學(xué)生現(xiàn)在的成績(jī)是：927.5.2 結(jié)構(gòu)體引用為參數(shù)——引用傳遞voidmain(){ voidmodifyStdScore(student&);

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

&std=s運(yùn)行結(jié)果

該學(xué)生現(xiàn)在的成績(jī)是：1007.5.3 結(jié)構(gòu)體指針為參數(shù)——地址傳遞voidmain(){ voidmodifyStdScore(student*);

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

std->score=100;}參數(shù)傳遞的結(jié)果：

std=p即std=&s運(yùn)行結(jié)果

該學(xué)生現(xiàn)在的成績(jī)是：100voidmain(){

studentsetStudent();

students;

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

s=std7．6

結(jié)構(gòu)體作為函數(shù)返回值7.6.1 結(jié)構(gòu)體變量為返回值7.6.2 結(jié)構(gòu)體指針為返回值structdate//日期結(jié)構(gòu)類型：由年、月、日3項(xiàng)組成{ intyear; intmonth; intday;};structstudent//學(xué)生信息結(jié)構(gòu)類型：由姓名、生日及成績(jī)3項(xiàng)組成{ 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<<"輸入成績(jī):";cin>>s[i].score;}

p=maxScoreStudent(s,3); cout<<"成績(jī)最好的學(xué)生是："<<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

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

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

char

no[6];

char

name[10]; int age;

Figure*

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

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

stu{ char name[20];

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

*head,

*tail,

*p;

//頭結(jié)點(diǎn)指針haed、尾結(jié)點(diǎn)指針tail、工作指針p int

i; head

=

tail

=

NULL; for(

i

=

1;

i

<=

3;

i++

){ //建立一個(gè)包含3個(gè)節(jié)點(diǎn)的鏈表 p

=

new

stu;

//讓p指向一個(gè)新創(chuàng)建的結(jié)點(diǎn) cout<<"請(qǐng)輸入姓名："<<endl; cin>>p->name;

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

=

NULL;

//讓p的后繼為空（即p將作為鏈表中的最后一個(gè)結(jié)點(diǎn)） if(

head

==

NULL)

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

head

=

p; else

//若頭指針不空，則讓p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)

tail->next

=

p; tail

=

p;

//讓tail指向尾結(jié)點(diǎn) }

cout<<"鏈表中的結(jié)點(diǎn)是："<<endl; p

=

head;

//使指針p指向鏈表的頭結(jié)點(diǎn)

while(

p

!=

NULL

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

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

=

p->next;

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

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

p->next=NULL;//使pb所指結(jié)點(diǎn)沒有后繼——尾結(jié)點(diǎn) if(i==0)//等價(jià)與“head==NULL” head=p; elsetail->next=p; tail=p; } returnhead;//返回鏈表頭指針的值（表頭結(jié)點(diǎn)的地址）}voidoutput(stu*head)//打印鏈表（頭指針為head）{ stu*p; //聲明工作指針p p=head; //開始時(shí)，讓p指向鏈表頭結(jié)點(diǎn) while(p!=NULL) { cout<<"姓名是:"<<p->name<<",年齡是"<<p->age<<endl; p=p->next;//注意此句的作用——指向鏈表中的下一個(gè)結(jié)點(diǎn)!! }}（程序演示見.txt）說明：“鏈表打印”函數(shù)output(head)也叫做“鏈表遍歷”函數(shù)showList(head)。（請(qǐng)參見《易學(xué)C++》P.101）讓“打印函數(shù)”output()輸出的鏈表結(jié)果更直觀、形象：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)建函數(shù)的另一種算法、打印函數(shù)的遞歸算法#include"stdafx.h"#include"iostream"usingnamespacestd;structstu{ char name[20]; int age; stu *next;};voidmain()//主函數(shù){ stu*create(int); //聲明“創(chuàng)建鏈表”的函數(shù)create原型 voidoutput(stu*); //聲明“打印鏈表”的函數(shù)output原型 stu*head; //聲明鏈表的頭指針 head=create(3); //調(diào)用create函數(shù)來創(chuàng)建鏈表(長(zhǎng)度為5) cout<<"鏈表中的信息是:"<<endl; output(head); //調(diào)用output函數(shù)來打印鏈表}

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：求鏈表的長(zhǎng)度（自行實(shí)現(xiàn)）程序示例5：鏈表的查詢（參見講義P.104）程序示例6：鏈表的刪除（參見講義P.105）程序示例7：鏈表的插入（參見講義P.104）關(guān)于“鏈表的基本操作函數(shù)”的一些說明：（1）由于結(jié)點(diǎn)類型的不同(比如，結(jié)點(diǎn)類型為figure、node、student等)，其鏈表的基本操作函數(shù)的具體實(shí)現(xiàn)就會(huì)不同?。?）在一般教材中，每種鏈表的“基本操作函數(shù)”通常只定義有6、7個(gè)(比如，creat()、output()、insert()、delete()、search()、length()、DestroyList()

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

head…a0a1an-1

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

voidoutput(node*head)

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

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

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

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

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

stu*head,

intno

)

//刪除鏈表中學(xué)號(hào)等于no的節(jié)點(diǎn)。

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

&&

p->num!=no

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

delete(head,i) //刪除鏈表head中第i個(gè)結(jié)點(diǎn)voiddelete(stu*head,

inti)//刪除鏈表head中第i個(gè)結(jié)點(diǎn)(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<<"不存在學(xué)號(hào)為"<<no<<"的學(xué)生\n";}程序示例10： 建立一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包括：學(xué)號(hào)、姓名、成績(jī)；編程：測(cè)試該鏈表的各基本操作函數(shù)。structstu{ intnum; charname[10]; intscore; structstu*next;};voidmain(

)

//主函數(shù):用于調(diào)試各函數(shù){ stu*

create();

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

search(stu*,int);//search函數(shù)：搜索鏈表中學(xué)號(hào)為no的結(jié)點(diǎn) void

output(stu*);

//output函數(shù)：遍歷打印鏈表 void

delete(stu*,int);

//delete函數(shù)：刪除學(xué)號(hào)為no的結(jié)點(diǎn) stu*

locate(stu*,int);//locate函數(shù)：搜索鏈表中第i個(gè)結(jié)點(diǎn) stu*

prior(stu*,int);

//prior函數(shù)：搜索鏈表中學(xué)號(hào)為no的前一個(gè)結(jié)點(diǎn) int

length(stu*);

//length函數(shù)：求鏈表的長(zhǎng)度 stu

*L,

*p; int

no,i; char

choice;

L=

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

output(L); //調(diào)用output函數(shù)打印鏈表L程序示例10： 建立一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包括：學(xué)號(hào)、姓名、成績(jī)；編程：測(cè)試該鏈表的各基本操作函數(shù)。

do{

cout<<"\n請(qǐng)輸入你要找的學(xué)號(hào)：";

cin>>no; if(

p

=

search(L,no)

)

//調(diào)用search函數(shù)搜索鏈表L中學(xué)號(hào)為no的結(jié)點(diǎn) cout<<"-->（"<<p->num<<","<<p->name<<","<<p->score<<"）\n"; else cout<<"學(xué)號(hào)為"<<no<<"的學(xué)生不存在！\n"; cout<<"\n你要找?guī)滋?hào)的前一位學(xué)生？";

cin>>no; if(

p

=

prior(L,no)

) //調(diào)用prior函數(shù)搜索鏈表L中學(xué)號(hào)為no的前一個(gè)結(jié)點(diǎn) cout<<no<<"號(hào)的前一個(gè)學(xué)生是:（"<<p->name<<","<<p->score<<"）\n"; else cout<<no<<"號(hào)的前一個(gè)學(xué)生不存在！\n"; cout<<"你想刪除的學(xué)號(hào)是：\t";

cin>>no;

delete(L,

no

);

//調(diào)用delete函數(shù)刪除鏈表L中學(xué)號(hào)為no的節(jié)點(diǎn) cout<<"\n刪除學(xué)號(hào)"<<no<<"后，鏈表中的信息是:\n"; cout<<"當(dāng)前鏈表的長(zhǎng)度是："<<length(L)<<endl;

//調(diào)用函數(shù)length獲取鏈表L的長(zhǎng)度 cout<<"當(dāng)前鏈表中的數(shù)據(jù)有："<<endl;

output(L); cout<<"你想找鏈表中第幾個(gè)結(jié)點(diǎn)？\t";

cin>>i; if(

p

=

locate(L,i)

)

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

Y

/

N

)";

cin>>choice;

}while(

choice

==

'Y'

||

choice

==

'y');

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

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

LB

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