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

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

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