C++-結構體與鏈表

第11章結構體與鏈表徐遵義主要內容結構體概述結構體與數(shù)組結構體與指針結構體與函數(shù)動態(tài)數(shù)據結構枚舉類型用typedef聲明類型本章小結與作業(yè)211.1結構體概述C++提供了許多種根本的數(shù)據類型(如char、int、float、double等)供用戶使用C++還允許用戶根據需要自己聲明一些類型結構體(structure)類型共用體(union)類型枚舉(enumeration)類型類(class)類型以上數(shù)據類型統(tǒng)稱為用戶自定義類型(user-definedtype,UDT)311.1結構體概述為什么引入結構體類型設有某學生信息管理系統(tǒng)，如果只存儲某班的某門課程的成績，可使用一維數(shù)組；存儲假設干門課程的成績，可用二維數(shù)組；對于下表該如何組織數(shù)據，采用什么存儲結構？學號姓名性別入學年度計算機原理C++語言編譯原理操作系統(tǒng)1令狐沖男1999908372822林平之男1999789288783岳靈珊女1999897298664任瑩瑩女1999789587905……6……charName[30][20]intIDSexYear[30][3]floatScore[30][4]411.1結構體概述為什么引入結構體類型采用分散的數(shù)組結構優(yōu)點：結構簡單、易于實現(xiàn)缺點數(shù)據存儲分散，綜合處理信息時不易操作，操作效率低;結構零散，不易管理操作易出錯intIDSexYear[30][3];charName[30][20];floatScore[30][4];

511.1結構體概述為什么引入結構體類型能否引入一種新的數(shù)據類型，使得

建立一個長度為30的數(shù)組，其中的每一個數(shù)組元素就是一個學生的全部信息，每一個數(shù)組元素的理想存儲結構可為：學號姓名性別入學年度計算機原理C++語言編譯原理操作系統(tǒng)IDNameSexEnterYearConstituteCLanguageCompilerOS一個完整的變量結構體(構造數(shù)據類型)611.1結構體概述可以通過下面的聲明來建立上圖所示的數(shù)據類型structStudent//聲明一個結構體類型Student{intnID;//包括一個整型變量IDcharchName[20];//包括一個字符數(shù)組name,可以容納20個字符charchSex;//包括一個字符變量sexintnEnterYear;//包括一個整型變量nEnterYearfloatfScoreConstitute;//包括一個單精度型變量 floatfScoreConstitute;floatfScoreCLanguage;floatfScoreCompilerfloatfScoreOS;｝;//最后有一個分號711.1結構體概述為什么引入結構體類型這是一種結構體類型，它包括ID,name,sex,EnterYear,fScoreConstitute等不同類型的數(shù)據項,Student是一個類型名，它和系統(tǒng)提供的標準類型〔如int、char、float、double等〕一樣，也可以用來定義變量，不過結構體類型需要事先由用戶自己聲明聲明一個結構體類型的一般形式為struct結構體類型名{類型1域名1；類型2域名2；……類型n域名n;｝；關鍵字成員(域);表示聲明的結束，不能省略811.1結構體概述為什么引入結構體類型成員名的命名規(guī)那么與變量名的命名規(guī)那么相同聲明結構體類型的位置一般在文件的開頭，在所有函數(shù)(包括main函數(shù))之前，以便本文件中所有的函數(shù)都能利用它來定義變量，也可以在函數(shù)中聲明結構體類型在C語言中，結構體的成員只能是數(shù)據；C++中結構體的成員既可以包括數(shù)據(即數(shù)據成員)，又可以包括函數(shù)(即函數(shù)成員)，以適應面向對象的程序設計結構體的聲明只是指定了一種結構體類型，相當于一個模型，其中并無具體數(shù)據，系統(tǒng)也不為之分配實際的內存單元911.1結構體概述結構體類型變量的定義先聲明結構體類型再定義變量名在聲明類型的同時定義變量如上面已定義了一個結構體類型Student，可以用它來定義結構體變量：Studentstudent1,student2；structStudent//聲明結構體類型Student{intnum;charname[20];charsex;intage;floatscore;charaddr[30];｝student1,student2;//定義兩個結構體類型Student的變量student1,student2這種形式的定義的一般形式為struct結構體名{成員表列}變量名表列；1011.1結構體概述結構體類型變量的定義直接定義結構體類型變量，其一般形式為注意不要誤認為但凡結構體類型都有相同的結構類型與變量是不同的概念，不要混淆在編譯時不會為類型分配空間，只為變量分配空間struct//注意沒有結構體類型名{成員表列｝變量名表列；該方法雖然合法，但很少使用。提倡先定義類型后定義變量的第一種方法。1111.1結構體概述結構體的嵌套：結構體的成員也可以是一個結構體變量structDate//聲明一個結構體類型Date{intmonth;intday;intyear;｝;structStudent//聲明一個結構體類型Student{intnum;charname[20];charsex;intage;Datebirthday;//Date是結構體類型，birthday是Date類型的成員charaddr[30];}student1,student2;//定義student1和student2為結構體類型Student的變量1211.1結構體概述結構體變量的初始化結構體變量在定義的同時指定初始值聲明類型與定義變量分開，在定義變量的同時進行初始化structStudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];｝student1={10001，”ZhangXin”,’M’,19,90.5,”Shanghai”};Studentstudent2={10002，”WangLi”,’F’,20,98,“Beijing”};//Student是已聲明的結構體類型Studentstudent2;student2

={10002，”WangLi”,’F’,20,98,“Beijing”};

1311.1結構體概述結構體變量的引用引用一個結構體變量中的一個成員的值將一個結構體變量的值賦給另一個具有相同結構的結構體變量如果成員本身也是一個結構體類型,那么要用假設干個成員運算符,一級一級地找到最低一級的成員引用結構體變量中成員的一般方式為:結構體變量名.成員名student1.num=10010;Studentstudent1,student2;……student1=student2;student1.num//引用結構體變量student1中的num成員)student1.birthday.month//引用student1變量中的birthday成員中的month成員1411.1結構體概述結構體變量的引用不能將一個結構體變量作為一個整體進行輸入和輸出,只能對結構體變量中的各個成員分別進行輸入和輸出對結構體變量的成員可以像普通變量一樣進行各種運算〔根據其類型決定可以進行的運算種類〕student2.score＝student1.score；sum＝student1.score＋student2.score；student1.age++；++student1.age；cout<<student2；cout<<student1.score；cout<<student1.age；1511.1結構體概述//引用結構體變量中的成員。#include<iostream>usingnamespacestd;structDate//聲明結構體類型Date{intmonth;intday;intyear;};structStudent//聲明結構體類型Student{intnum;charname[20];charsex;Datebirthday;//聲明birthday為Date類型的成員floatscore;}student1,student2={10002,″WangLi″,′f′,5,23,1982,89.5};//定義Student類型的變量student1,student2，并對student2初始化1611.1結構體概述intmain(){student1=student2;//將student2各成員的值賦予student1的相應成員cout<<student1.num<<endl;//輸出student1中的num成員的值cout<<<<endl;//輸出student1中的name成員的值cout<<student1.sex<<endl;//輸出student1中的sex成員的值cout<<student1.birthday.month<<‘/’<<student1.birthday.day<<‘/’<<student1.birthday.year<<endl;//輸出student1中的birthday各成員的值cout<<student1.score<<endl;return0;}//運行結果如下：10002WangLif5/23/198289.51711.2結構體與數(shù)組概念：每個數(shù)組元素都是一個結構體類型的數(shù)據，它們都分別包括各個成員項定義結構體數(shù)組與定義結構體變量的方法相仿，定義結構體數(shù)組時只需聲明其為數(shù)組即可structStudent//聲明結構體類型Student{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};Studentstu[3];//定義Student類型的數(shù)組stu1811.2結構體與數(shù)組定義結構體數(shù)組也可以直接定義一個結構體數(shù)組structStudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu[3];

struct

{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu[3];1911.2結構體與數(shù)組結構體數(shù)組的初始化結構體數(shù)組定義的同時進行初始化定義數(shù)組stu時，也可以不指定元素個數(shù)structStudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu[3]={{10101,"LiLin",'M',18,87.5,"103BeijingRoad"},{10102,"

ZhangFun",'M'，19,99,"130ShanghaiRoad"},{10104,"

WangMin",'F',20,78.5,"

1010,ZhongshanRoad"}};2011.2結構體與數(shù)組結構體數(shù)組的初始化定義后逐個元素初始化定義后逐個元素用cin初始化Studentstu[3]；stu[1].num=10101;strcpy(stu[1].name,

"Lilin“);stu[1].sex='m’;stu[1].age=18;stu[1].score=87.5;strcpy(stu[1].address,"103Beijingroad“);2111.2結構體與數(shù)組結構體數(shù)組應用舉例對候選人得票的統(tǒng)計程序。設有3個候選人，最終只能有1人中選為領導。今有10個人參加投票，從鍵盤先后輸入這10個人所投的候選人的名字，要求最后輸出這3個候選人的得票結果可以定義一個候選人結構體數(shù)組，包括3個元素，在每個元素中存放有關的數(shù)據#include<iostream>#include<string>usingnamespacestd;structPerson//聲明結構體類型Person{charname[20];intcount;};2211.2結構體與數(shù)組intmain(){//定義Person類型的數(shù)組，內容為3個候選人的姓名和當前的得票數(shù)Personleader[3]={"Li",0,"Zhang",0,"Fun",0};inti,j;charleader_name[20];//leader_name為投票人所選的人的姓名for(i=0;i<10;i++){cin>>leader_name;//先后輸入10張票上所寫的姓名//將票上姓名與3個候選人的姓名比較,如果與某一候選人的姓名相同，就給他加一票for(j=0;j<3;j++)if(strcmp(leader_name,leader[j].name)==0)leader[j].count++;

}cout<<endl;for(i=0;i<3;i++)//輸出3個候選人的姓名與最后得票數(shù){cout<<leader[i].name<<":"<<leader[i].count<<endl;}return0;}2311.2結構體與數(shù)組程序略作修改：#include<iostream>#include<string>usingnamespacestd;structPerson{

stringname;//成員name為字符串變量intcount;};intmain(){Personleader[3];inti,j;for(i=0;i<3;i++){cin>>leader[i].name>>leader[i].count;}2411.2結構體與數(shù)組cout<<"input"<<endl;stringleader_name;//leader_name為字符串變量for(i=0;i<10;i++){cin>>leader_name;for(j=0;j<3;j++)if(leader_name==leader[j].name)//用“==”進行比較leader[j].count++;}cout<<endl;for(i=0;i<3;i++){cout<<leader[i].name<<":"<<leader[i].count<<endl;}return0;}2511.3結構體與指針指向結構體變量的指針一個結構體變量的指針就是該變量所占據的內存段的起始地址定義一個指針變量，用來指向一個結構體變量，此時該指針變量的值是結構體變量的起始地址指針變量也可以用來指向結構體數(shù)組中的元素通過指向結構體變量的指針引用結構體變量中的成員格式：結構類型名

*指針名；指針結構體變量成員的引用Student

*pStudent,

student；pStudent=&student;//指針p即指向結構體變量student的首地址pStudent->num=35;//等價于student.num=35;(*pStudent).num=36;//不建議使用2611.3結構體與指針//指向結構體變量的指針的應用。#include<iostream>#include<string>usingnamespacestd;intmain(){structStudent//聲明結構體類型student{intnum;stringname;charsex;floatscore;};2711.3結構體與指針//指向結構體變量的指針的應用。Studentstu;//定義Student類型的變量stuStudent*p=&stu;//定義p為指向Student類型數(shù)據的指針變量并指向stustu.num=10301;//對stu中的成員賦值="WangFun";//對string變量可以直接賦值stu.sex='f';stu.score=89.5;cout<<stu.num<<"

"<<<<"

“<<stu.sex<<"

"<<stu.score<<endl;cout<<p->num<<"

"<<p->name<<"

“<<p->sex<<"

"<<p->score<<endl;return0;}2811.3結構體與指針指向結構體數(shù)組的指針Studentstu[30];//結構體數(shù)組,Student*p;//結構體指針,//結構體指針,其算術運算相當于指針的移動p=stu; //初始化*pstu[0]*(p+1)stu[1]*(p+2)stu[2]*(p+3)stu[3]結構體數(shù)組成員的三種引用方法：stu[1].num(p+1)->num(*(p+1)).num

2911.3結構體與指針//對候選人得票的統(tǒng)計#include<iostream>#include<string.h>usingnamespacestd;//結構體structPerson{charname[20];intcount;};//結構體數(shù)組Personleader[3]={"li",0,"zhang",0,"wang",0};intmain(intargc,char*argv[]){ inti,j; charname[20]; Person*pt; //結構體指針3011.3結構體與指針

pt=leader;// for(i=1;i<=10;i++) { // cin>>name; // for(j=0;j<3;j++) if(strcmp(name,(pt+j)->name)==0) (pt+j)->count++; } // for(i=0;i<3;i++) cout<<(pt+i)->name<<“\t”<<(pt+i)->count<<endl; return0;}3111.4結構體與函數(shù)結構體類型數(shù)據作為函數(shù)參數(shù)用結構體變量名作參數(shù)，是單向值傳遞，在函數(shù)內部對參數(shù)進行操作不影響結構體的變化，一般較少用這種方法用指向結構體變量的指針作實參，將結構體變量的地址傳給形參用結構體變量的引用變量作函數(shù)參數(shù)例：有一個結構體變量stu，內含學生學號、姓名和3門課的成績。要求在main函數(shù)中為各成員賦值，在另一函數(shù)print中將它們的值輸出3211.4結構體與函數(shù)(1)用結構體變量作函數(shù)參數(shù)#include<iostream>#include<string>usingnamespacestd;structStudent{intnum;stringname;floatscore[3];};intmain(){voidprint(Student);Studentstu;stu.num=12345;="LiFung";stu.num=12345;="LiFung";stu.score[0]=67.5;stu.score[1]=89;stu.score[2]=78.5;print(stu);return0;}voidprint(Studentstu){cout<<stu.num<<""<<<<""<<stu.score[0]<<""<<stu.score[1]<<""<<stu.score[2]<<endl;}3311.4結構體與函數(shù)(2)用指向結構體變量的指針作實參#include<iostream>#include<string>usingnamespacestd;structStudent{intnum;stringname;//用string類型定義字符串變量floatscore[3];}stu;intmain(){

//函數(shù)聲明，形參為指向Student類型數(shù)據的指針變量voidprint(Student*p);cout<<"Inputnum,name,score[0],score[1],score[2]:";cin>>stu.num>>>>stu.score[0]>>stu.score[1]>>stu.score[2];3411.4結構體與函數(shù)Student*pt=&stu;//定義基類型為Student的指針變量pt，并指向stuprint(pt);//實參為指向Student類數(shù)據的指針變量return0;}//定義函數(shù)，形參p是基類型為Student的指針變量voidprint(Student*p){cout<<p->num<<""<<p->name<<""<<p->score[0]<<""<<p->score[1]<<""<<p->score[2]<<endl;}3511.4結構體與函數(shù)(3)用結構體變量的引用作函數(shù)參數(shù)#include<iostream>#include<string>usingnamespacestd;structStudent{intnum;stringname;floatscore[3];}stu;intmain(){

//函數(shù)聲明，形參為Student類型變量的引用voidprint(Student&);

cout<<"InputStu-data:";cin>>stu.num>>>>stu.score[0]>>stu.score[1]>>stu.score[2];

print(stu);//實參為結構體Student變量return0;}3611.4結構體與函數(shù)//函數(shù)定義，形參為結構體Student變量的引用voidprint(Student&stud){cout<<stud.num<<""<<<<"“<<stud.score[0]<<""<<stud.score[1]<<"“<<stud.score[2]<<endl;}程序(1)用結構體變量作實參和形參，程序直觀易懂，效率較低程序(2)采用指針變量作為實參和形參，空間和時間的開銷都很小，效率較高，但程序〔2〕不如程序(1)那樣直觀程序(3)的實參是結構體Student類型變量，而形參用Student類型的引用，虛實結合時傳遞的是stu的地址，效率較高，它兼有(1)和(2)的優(yōu)點。引用變量主要用作函數(shù)參數(shù)，它可以提高效率，而且保持程序良好的可讀性3711.4結構體與函數(shù)結構體類型作為一種數(shù)據類型也可以作為函數(shù)的返回值一個函數(shù)可以返回一個結構的引用和結構的指針，但不要返回一個局部結構變量的引用和指針Student

fnFind(intnum){

Studentstu;

…………

return(stu);//函數(shù)返回值}voidfnFind(intnum,Student&st){

=“xuzy”;

…………}3811.5動態(tài)數(shù)據結構為什么使用動態(tài)數(shù)據結構遞歸結構體在定義結構體類型時，可定義指針域，當指針域基類型就是結構體自身〔包括一個指向結構體自身類型的指針域〕，那么稱遞歸結構體使用靜態(tài)數(shù)據結構，當數(shù)據較少時，浪費大量空間，如結構數(shù)組。動態(tài)數(shù)據使用的是鏈表結構，當有一個數(shù)據時，就申請一個結點，鏈到鏈表中去各域值各域值各域值NULLpHead…3911.5動態(tài)數(shù)據結構遞歸結構體struct

Student

{intnum;charname[20];charsex;

Student*pNext;};學生信息Student指針pNext遞歸結構體構成鏈表動態(tài)結構，鏈表的每一個節(jié)點都是遞歸結構體4011.5動態(tài)數(shù)據結構1.在鏈表中易于插入一個新節(jié)點各域值各域值各域值NULLhead各域值╳各域值各域值各域值NULLhead╳2.在鏈表中易于刪除一個節(jié)點3.在鏈表中不易于檢索一個節(jié)點4.在鏈表中易于出現(xiàn)斷鏈鏈表的特點及操作原理4111.5動態(tài)數(shù)據結構動態(tài)鏈表建立—尾部插入新節(jié)點structStudent{charname[20];longnum;Student*link;}*pHead,*pR,*pS;各域值各域值NULLpHeadpRpS=newStudent;NULLstrcpy(pS－＞name,"zhangsan");pS－＞num=9901012;pS－＞pNext=NULL;pR－＞pNext=pS;pR=pS;各域值pRpS4211.5動態(tài)數(shù)據結構Student*ListCreat(Student*pHead){Student*pS;//新節(jié)點Student*pR;//尾節(jié)點//創(chuàng)立新節(jié)點pS=newStudent;if(pS==NULL){cout<<“Newmemoryerror!”returnpHead;}pS->pNext=NULL;cin>>pS->num>>pS->name>>pS->sex;

if(pHead==NULL)//空鏈表pHead=pS;else{//找到尾節(jié)點pR=pHead;while(pR->pNext!=NULL)pR=pR->pNext;//將新節(jié)點插入尾部pR=pS;}returnpHead;}43各域值各域值pHeadpHead各域值NULLpRpS=pHead;pHead=pHead－＞link;deletepS;pS系統(tǒng)

刪除節(jié)點就是將該節(jié)點從鏈表中別離出來。刪除后，一定將該節(jié)點歸還給系統(tǒng)，以便于再分配；否那么，該節(jié)點所占內存將永久喪失。首端刪除尾端刪除中間刪除╳鏈表的刪除操作——首端刪除11.5動態(tài)數(shù)據結構44鏈表的刪除操作——首端刪除11.5動態(tài)數(shù)據結構intListDeleteFront(Student*pHead){Student*p;if(pHead==NULL)return(0);else{p=pHead;pHead=pHead->pNext;deletep;return(1);}}45各域值各域值p各域值NULLpHeadNULLStudent*delete_rear(Student*pHead){Student*p;if(pHead==NULL)returnpHead;else{if(phead->pNext==NULL)//只有一個節(jié)點{deletepHead;pHead=NULL;}

else{//遍歷鏈表p=pHead;while(p->pNext->pNext!=NULL)p=p->pNext;

//刪除節(jié)點deletep->pNext);p->pNext=NULL；}}//endofif(pHead==NULL)returnpHead;}鏈表的刪除操作——尾端刪除11.5動態(tài)數(shù)據結構╳系統(tǒng)46各域值各域值各域值NULLqpheadintListDeleteMid(Student*pHead,intnum){Student*p,*q;if(pHead==NULL)return(0);elseif(pHead->num==num){ListDeleteFront(pHead);return(1);}各域值鏈表的刪除操作——中間刪除11.5動態(tài)數(shù)據結構4711.5動態(tài)數(shù)據結構鏈表的刪除操作——尾端刪除else{

//遍歷查找

p=pHead;while(p->pNext!=NULL&&p->pNext->num!=num)p=p->pNext;//

刪除if(p->pNext->num==num){q=p->pNext;p->pNext=q->pNext;deleteq;return(1);}elsereturn(0);}}4811.5動態(tài)數(shù)據結構12364…pHeadJosephus問題：用鏈表實現(xiàn)pJose57npCurpPrev4911.5動態(tài)數(shù)據結構12364…pHeadJosephus問題：用鏈表實現(xiàn)pJose57npCurpPrev5011.5動態(tài)數(shù)據結構#include<iostream>#include<iomanip>usingnamespacestd;structJose//小孩結點{intcode;Jose*pNext;};intmain(){//賦初值intnBoyNum,nInterval;inti,j;cout<<"pleaseinputthenumberofboys,\n"http://小孩數(shù)<<"intervalofcounting:\n";//數(shù)小孩個數(shù)cin>>nBoyNum>>nInterval;5111.5動態(tài)數(shù)據結構Jose*pHead,*pNew,*pTmp;pHead=NULL;for(i=0;i<BoyNum;i++){pNew=newJose;if(pNew==NULL){cout<<“CannotnewJose!”;return-1;}pNew->code=i+1;pNew->pNext=NULL;if(pHead==NULL)pHead=pNew;else{pTmp=pHead;while(pTmp->pNext!=NULL)pTmp=pTmp->pNext;pTmp->pNext=pNew;}}pNew->pNext=pHead;//構成循環(huán)鏈表

cout<<"TheallBoys:";pTmp=pHead;while(pTmp->pNext!=pHead){cout<<pTmp->code<<",";pTmp=pTmp->pNext;}cout<<pTmp->code<<endl;

5211.5動態(tài)數(shù)據結構Jose*pRrev,*pCur;pCur=pPrev=pHead;cout<<“TheleavingBoy:”;while(pCur->pNext!=pCur){for(j=0;j<nInterval-1;j++){pPrev=pCur;pCur=pCur->pNext;}//刪除cout<<pC