數(shù)據(jù)結(jié)構(gòu)雙向鏈表-學(xué)生成績管理系統(tǒng)

數(shù)學(xué)與計算機(jī)學(xué)院實(shí)驗(yàn)報告〔2011/2012學(xué)年第1學(xué)期〕課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼6014279實(shí)驗(yàn)時間年月日指導(dǎo)單位軟件工程系指導(dǎo)教師周立章學(xué)生姓名吳超年級10級學(xué)號專業(yè)軟件工程實(shí)驗(yàn)成績

實(shí)驗(yàn)名稱學(xué)生成績管理系統(tǒng)指導(dǎo)教師周立章實(shí)驗(yàn)類型設(shè)計實(shí)驗(yàn)學(xué)時2+10實(shí)驗(yàn)時間實(shí)驗(yàn)?zāi)康暮鸵蟆?〕掌握線性表的順序存儲結(jié)構(gòu)，在順序存儲結(jié)構(gòu)根底上進(jìn)行的插入、刪除、查找等算法的思想和實(shí)現(xiàn)；〔2〕掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的建立。在鏈表中插入、刪除和查找算法的思想和算法實(shí)現(xiàn)?！?〕掌握線性表在順序存儲、鏈?zhǔn)酱鎯Y(jié)構(gòu)的根底進(jìn)行的各種應(yīng)用?！?〕掌握鏈表的定義和根底知識以及鏈表的存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)及其應(yīng)用。〔5〕掌握隊(duì)列的根底知識，循環(huán)順序隊(duì)列、鏈隊(duì)列及其應(yīng)用。〔6〕會用結(jié)構(gòu)體正確描述每一條學(xué)生記錄的信息，掌握鏈表結(jié)構(gòu)存儲所處理的數(shù)據(jù)。〔7〕設(shè)計友好的人機(jī)交互菜單，通過相應(yīng)的流程控制語句的正確使用，使得在主函數(shù)中表達(dá)對各功能模塊的調(diào)用，從而實(shí)現(xiàn)一個完整的小型管理系統(tǒng)。要求：課內(nèi)實(shí)驗(yàn)學(xué)時2學(xué)時，課后學(xué)時要求為10學(xué)時。二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)硬件:微型計算機(jī)P4軟件:WindowsXP+MicrosoftVisualC++6.0三、實(shí)驗(yàn)原理及內(nèi)容實(shí)驗(yàn)題目利用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲學(xué)生的成績信息，設(shè)計一個學(xué)生成績管理系統(tǒng)，具有以下功能：〔1〕定義學(xué)生結(jié)構(gòu)體類型structStudent，每個學(xué)生包括學(xué)號、姓名、3門功課〔課程名自己定義〕、總分?！?〕建立雙向循環(huán)鏈表：輸入假設(shè)干學(xué)生的信息〔當(dāng)輸入學(xué)生的學(xué)號為0000時結(jié)束，要求自動計算總分〕，并按輸入的順序建立雙向循環(huán)鏈表；〔3〕輸出學(xué)生成績信息：遍歷雙向循環(huán)鏈表，輸出所有學(xué)生的完整信息到屏幕；〔4〕查找指定學(xué)號的學(xué)生信息。如果查找成功，輸出所有學(xué)生信息，否那么輸出失敗?！?〕插入學(xué)生信息：以隊(duì)列的方式將新學(xué)生成績信息插入到鏈表中；〔6〕刪除學(xué)生信息：給出學(xué)生姓名，刪除鏈表所有相同姓名的學(xué)生的信息〔即姓名相同的結(jié)點(diǎn)〕；〔7〕修改學(xué)生信息：給出學(xué)生學(xué)號，修改該生的三門課程成績信息；〔8〕按總分排序：在原來的雙向循環(huán)鏈根底上按總分降序進(jìn)行就地排列。即不能增加額外的空間開銷；實(shí)驗(yàn)前準(zhǔn)備：完成上述(1)-(4)算法，并要求上機(jī)驗(yàn)證通過。實(shí)驗(yàn)時完成(5)-(6)。實(shí)驗(yàn)后，完成算法〔7〕，(8),并要求上機(jī)驗(yàn)證通過。實(shí)驗(yàn)解答：1)畫出主函數(shù)的流程圖2〕數(shù)據(jù)類型定義〔1〕學(xué)生成績信息結(jié)構(gòu)體類型的定義structStudent{ intnum; charname[20]; intmath; intchinese; intenglish; intsum; structStudent*prior,*next;};〔2〕雙向鏈表結(jié)點(diǎn)的定義。是否將結(jié)點(diǎn)的數(shù)據(jù)類型定義為學(xué)生成績信息結(jié)構(gòu)體類型？是的；3〕為了能夠完成鏈表的各項(xiàng)操作，你給出的測試數(shù)據(jù)有哪些？主要用于測試哪些方面？1菜單函數(shù)測試：2輸入函數(shù)測試3查詢函數(shù)測試4插入函數(shù)測試5刪除函數(shù)測試6輸出函數(shù)測試7修改函數(shù)測試8排序函數(shù)測試實(shí)驗(yàn)報告4)你是否在實(shí)驗(yàn)前完成了算法〔1〕-〔4〕？如果完成了難點(diǎn)在哪兒？。如果沒有完成，理由是什么？答：是；難點(diǎn)在于雙向循環(huán)鏈表的創(chuàng)立，在最后需要把最后一個結(jié)點(diǎn)指向頭結(jié)點(diǎn)，否那么會出現(xiàn)一系列問題；5〕建立雙向循環(huán)鏈表，你采用的是后插法還是前插法？寫出C++語言代碼。答：前插法，代碼如下：voidRDLink::Create(){Student*p,*s;intx;if((head=newStudent)==NULL){cout<<"分配內(nèi)存失敗..."<<endl;}head->prior=NULL;head->next=NULL;p=head;cout<<"開始輸入學(xué)生信息，輸入時結(jié)束。"<<endl;while(1){if((s=newStudent)==NULL){cout<<"分配內(nèi)存失敗..."<<endl;}p->next=s;cout<<"請輸入學(xué)生的學(xué)號：";cin>>x;if(x==0000)break;else{s->num=x;cout<<"請輸入學(xué)生的姓名：";cin>>s->name;cout<<"請輸入學(xué)生的數(shù)學(xué)成績：";cin>>s->math;cout<<"請輸入學(xué)生的語文成績：";cin>>s->chinese;cout<<"請輸入學(xué)生的英語成績：";cin>>s->english;s->sum=s->math+s->chinese+s->english;s->prior=p;s->next=NULL;p=s;}}s->next=head;head->prior=s;cout<<"儲存成功！"<<endl;}實(shí)驗(yàn)報告6〕在遍歷雙向循環(huán)鏈表時，你是如何判斷遍歷結(jié)束的？如何控制對結(jié)點(diǎn)的訪問？給出算法的代碼。答：從頭結(jié)點(diǎn)出發(fā)，當(dāng)再次到達(dá)頭結(jié)點(diǎn)時，那么遍歷結(jié)束；首先創(chuàng)立結(jié)點(diǎn)p：Student*p=head->next;用while(p!=head)來控制循環(huán)；循環(huán)一次p再指向下一結(jié)點(diǎn)：p=p->next;voidRDLink::DispList() { Student*p=head->next;while(p!=head) { cout<<"學(xué)生的學(xué)號："<<p->num<<endl; cout<<"學(xué)生的姓名："<<p->name<<endl; cout<<"學(xué)生的數(shù)學(xué)成績："<<p->math<<endl; cout<<"學(xué)生的語文成績："<<p->chinese<<endl; cout<<"學(xué)生的英語成績："<<p->english<<endl; cout<<"個學(xué)生的總成績："<<p->sum<<endl; p=p->next;}cout<<endl;}7〕在循環(huán)雙向鏈表中，有幾種方法可以取鏈表中的首元結(jié)點(diǎn)？寫出表達(dá)式。Student*p=head->next;8〕插入算法：當(dāng)按隊(duì)列的方式進(jìn)行插入運(yùn)算時，新學(xué)生信息是插入到什么位置？寫出算法。答：插到末尾voidRDLink::InsElem(){Student*s;s=newStudent;Student*p=head;cout<<"請輸入學(xué)生的學(xué)號：";cin>>s->num;cout<<"請輸入學(xué)生的姓名：";cin>>s->name;cout<<"請輸入學(xué)生的數(shù)學(xué)成績：";cin>>s->math;cout<<"請輸入學(xué)生的語文成績：";cin>>s->chinese;cout<<"請輸入學(xué)生的英語成績：";cin>>s->english;s->sum=s->math+s->chinese+s->english;head->prior->next=s;s->prior=head->prior;head->prior=s;s->next=head;cout<<"插入成功！"<<endl;}9〕如果要求將新學(xué)生信息插入到鏈表中指定的i位置，寫出插入算法的代碼，并給出時間復(fù)雜度。intRDLink::InsElem(inti) {intj=1;Student*p=head->next,*s;s=newStudent; s->data=x; if(i==1) {head->prior=s; head->next=s;s->prior=head;s->next=head;}else{while(j<i) { p=p->next;j++; } s->next=p->next; s->prior=p; if(p->next!=head) p->next->prior=s;p->next=s; return1;}}時間復(fù)雜度為：0(n)10〕刪除操作：在該刪除中，時間開銷主要用在什么地方？寫出刪除算法的代碼，給出時間復(fù)雜度。它與順序表中同樣的刪除上有什么不同？你是如何保證刪除了所有姓名相同的結(jié)點(diǎn)的？答：用在遍歷鏈表上；時間復(fù)雜度為：O(n)順序表沒有鏈表中前后指針，不用讓前后指針指來指去；遍歷整個雙線循環(huán)鏈表，只要姓名相同，那么執(zhí)行刪除操作；intRDLink::DelElem() {Student*p=head->next,*q;cout<<"請輸入需要刪除的學(xué)生姓名：";charm[20];cin>>m;intj=1,x=0;while(p!=head) { if(strcmp(p->next->name,m)==0) {q=p->next; p->next=q->next;if(q->next!=head) q->next->prior=p;deleteq; cout<<"刪除成功"<<endl; x++;return1; break;} p=p->next;j++;}if(x==0)cout<<"查找失??！"<<endl;return0;}11〕寫出修改學(xué)生成績的代碼。voidRDLink::Modify(){ intx,a,b,c,d; cout<<"請輸入需要修改的學(xué)生學(xué)號"<<endl; cin>>x; Student*p=head->next;while(p!=head) { if(p->num==x) { cout<<"請輸入學(xué)生的學(xué)號：";cin>>d; p->num=d; cout<<"語文成績"<<endl; cin>>a; p->chinese=a; cout<<"英語成績"<<endl; cin>>b; p->english=b; cout<<"數(shù)學(xué)成績"<<endl; cin>>c; p->math=c; p->sum=a+b+c; cout<<"修改成功！"<<endl; break; } p=p->next; }}12〕按總分排序時，你是否增加了空間？寫出該算法的代碼。答：沒有增加。voidRDLink::Rank(){ Student*p=head->next; Student*q=head->next->next; while(p!=head){while(q!=head) {if(p->sum<q->sum) {p->prior->next=q; q->next->prior=p; q->prior=p->prior; p->next=q->next; q->next=p; p->prior=q; }q=q->next; }p=p->next;}cout<<"排序成功！"<<endl;}實(shí)驗(yàn)報告四、實(shí)驗(yàn)小結(jié)〔包括問題和解決方法、心得體會、意見與建議等〕1．在使用鏈表存儲學(xué)生信息進(jìn)行編程時，你所遇到的主要問題是什么，如何解決的？由于本人對鏈表的操作并不是特別熟練，特別是像這種雙向循環(huán)鏈表，剛開始做的時候真的是完全靠照搬老師代碼，但是在拼湊的過程中一次次的出錯，比方一進(jìn)行插入操作和刪除操作就意外停止，通過自己不斷的調(diào)試，并查找資料，自己畫圖理解，修改代碼，終于把問題搞定了！2．鏈棧的進(jìn)棧操作需什么條件？棧操作的特點(diǎn)是什么？答：需要棧未滿；特點(diǎn)是只能從頂部進(jìn)棧，比擬簡單。3．隊(duì)列操作的特點(diǎn)是什么？如果Q表示是循環(huán)順序隊(duì)列，那么表示Q為空的條件和滿的條件是什么？答：特點(diǎn)：隊(duì)頭出隊(duì)，隊(duì)尾入隊(duì)。隊(duì)滿的條件：〔rear+1)%MaxSize=fron