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

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