228尹龍海上機報告學生成績管理系統(tǒng)

1、數(shù)據(jù)結構實驗報告數(shù)學與計算機學院實 驗 報 告（ 2011 / 2012 學年 第 1 學期）課程名稱數(shù)據(jù)結構課程代碼6014279實驗時間2011年11月16日指導單位軟件工程系指導教師周立章學生姓名尹龍海年 級2010級學 號312010080611228專 業(yè)軟件工程實驗成績實驗名稱學生成績管理系統(tǒng)指導教師周立章實驗類型設計實驗學時2+10實驗時間2011.11一、 實驗目的和要求（1）掌握線性表的順序存儲結構，在順序存儲結構基礎上進行的插入、刪除、查找等算法的思想和實現(xiàn)；（2）掌握線性表的鏈式存儲結構。掌握線性表的鏈式存儲結構的建立。在鏈表中插入、刪除和查找算法的思想和算法實現(xiàn)。（3）

2、掌握線性表在順序存儲、鏈式存儲結構的基礎進行的各種應用。（4）掌握鏈表的定義和基礎知識以及鏈表的存儲和鏈式存儲結構及其應用。（5）掌握隊列的基礎知識，循環(huán)順序隊列、鏈隊列及其應用。（6）會用結構體正確描述每一條學生記錄的信息，掌握鏈表結構存儲所處理的數(shù)據(jù)。（7）設計友好的人機交互菜單，通過相應的流程控制語句的正確使用，使得在主函數(shù)中體現(xiàn)對各功能模塊的調(diào)用，從而實現(xiàn)一個完整的小型管理系統(tǒng)。 要求：課內(nèi)實驗學時2學時，課后學時要求為10學時。二、實驗環(huán)境(實驗設備) 硬件: 微型計算機P4軟件: Windows XP+Microsoft Visual C+6.0三、實驗原理及內(nèi)容實驗題目 利用鏈式

3、存儲結構存儲學生的成績信息，設計一個學生成績管理系統(tǒng)，具有以下功能：（1）定義學生結構體類型struct Student，每個學生包括學號、姓名、3門功課（課程名自己定義）、總分。（2）建立雙向循環(huán)鏈表：輸入若干學生的信息（當輸入學生的學號為0000時結束，要求自動計算總分），并按輸入的順序建立雙向循環(huán)鏈表；（3）輸出學生成績信息：遍歷雙向循環(huán)鏈表，輸出所有學生的完整信息到屏幕；（4）查找指定學號的學生信息。如果查找成功，輸出所有學生信息，否則輸出失敗。（5）插入學生信息：以隊列的方式將新學生成績信息插入到鏈表中；（6）刪除學生信息：給出學生姓名，刪除鏈表所有相同姓名的學生的信息（即姓名相同的

4、結點）；（7）修改學生信息：給出學生學號，修改該生的三門課程成績信息；（8）按總分排序：在原來的雙向循環(huán)鏈基礎上按總分降序進行就地排列。即不能增加額外的空間開銷；實驗前準備：完成上述(1)-(4)算法，并要求上機驗證通過。實驗時完成(5)-(6)。實驗后，完成算法（7），(8) ,并要求上機驗證通過。實驗解答：1) 畫出主函數(shù)的流程圖 2）數(shù)據(jù)類型定義 （1）學生成績信息結構體類型的定義struct student/(1)題學生成績結構體類型定義char no8;/學號（數(shù)組大小要適當，小于5會錯）char name8;int score3;/語文，英語，日語int total;/總分; （2

5、）雙向鏈表結點的定義。是否將結點的數(shù)據(jù)類型定義為學生成績信息結構體類型？ struct DLink/（2）題雙向鏈表節(jié)點定義student data;DLink *prior,*next; 雙向鏈表的節(jié)點由兩個指針域和一個數(shù)據(jù)域組成，數(shù)據(jù)域中的數(shù)據(jù)為學生成績信息結構體類型。而不是將節(jié)點定義為學生成績信息結構體類型。3）為了能夠完成鏈表的各項操作，你給出的測試數(shù)據(jù)有哪些？主要用于測試哪些方面？為了能夠完成鏈表的各項操作，需要具體的給出N個學生的基本信息，基本信息包括學號no，學生姓名name，學生的各項成績score【3】等。菜單界面如下：創(chuàng)建鏈表函數(shù)和顯示函數(shù)的測試數(shù)據(jù)如下，組要用于測試函數(shù)能

6、否成功創(chuàng)建鏈表，并將結果顯示出來。錄入學生信息界面如下：輸出學生成績界面如下：按學號查詢學生信息界面如下： （1） （2）插入學生成績時，有兩種情況，一種是插入的位置在鏈表節(jié)點之間，界面如下：另一種是插入的位置長于鏈表總長，則尾插法，界面如下：刪除學生信息界面如下：將鏈表數(shù)據(jù)輸出來如下界面，再接合以上相關界面信息便知道刪除成功了的。修改學生信息界面如下： （1） （2）將鏈表數(shù)據(jù)輸出來如下界面，再接合以上相關界面信息便知道修改成功了的?？偡峙判蚪缑嫒缦拢簩㈡湵頂?shù)據(jù)輸出來如下界面，再接合以上相關界面信息便知道排序成功了的。結束程序界面如下：實 驗 報 告4)你是否在實驗前完成了算法（1）-（4）

7、？如果完成了難點在哪兒？。如果沒有完成，理由是什么？ 實驗前，為成功的完成第二點。首先，在初始化鏈表，創(chuàng)建鏈表頭結點分配空間，若未分配成功則由exit（0）正常結束程序。if(!p)cout<<"分配內(nèi)存失??！"<<endl;exit(0);/stdlib.hreturn L；忘記一個十分關鍵的大括號。應為：if(!p)cout<<"分配內(nèi)存失??！"<<endl;exit(0);/stdlib.hReturn L；5）建立雙向循環(huán)鏈表，你采用的是后插法還是前插法？寫出C+語言代碼。我采用尾插法創(chuàng)建雙向量表。

8、void LinkListC:creatList()/采用尾插法建立雙向循環(huán)鏈表DLink *p,*q; q=L;p=new DLink;if(!p)cout<<"分配內(nèi)存失?。?quot;<<endl;exit(0);/stdlib.hcout<<"輸入學生學號(形如XXXX)："cin>>p->data.no;while(strcmp(p->data.no,"0000")/輸入學號為0000時結束cout<<"輸入姓名："cin>>p-&

9、gt;;cout<<endl;cout<<"依次輸入語文 英語 日語3門課程的成績"<<endl;cin>>p->data.score0>>p->data.score1>>p->data.score2; p->data.total=p->data.score0+p->data.score1+p->data.score2;q->next=p;p->prior=q;p->next=L;L->prior=p;q=q->n

10、ext;/p=new DLink;/cout<<endl;cout<<"輸入下一個學生的學號(形如XXXX)："cin>>p->data.no;實 驗 報 告6）在遍歷雙向循環(huán)鏈表時，你是如何判斷遍歷結束的？如何控制對結點的訪問？給出算法的代碼。 我是通過循環(huán)結束條件p=L實現(xiàn)的，通過建立指向結點的指針p，以及循環(huán)，使p不斷地更新，指向下一個結點，并輸出學生成績信息。void LinkListC:displayLink()/顯示學生表信息int i;DLink *p;p=L->next;cout<<"學生

11、成績?nèi)缦拢?quot;<<endl;cout<<"學號 姓名 語文 英語 日語 總分"<<endl;cout<<endl;docout<<p->data.no<<" "cout<<p-><<" "for(i=0;i<3;i+)cout<<p->data.scorei<<" "cout<<p->data.total;/cout<<

12、;endl;p=p->next;while(p!=L);cout<<endl;7）在循環(huán)雙向鏈表中，有幾種方法可以取鏈表中的首元結點？寫出表達式。因為是帶頭結點的循環(huán)雙向鏈表，所以可以通過以下兩種方法取首元結點。（1） 可以通過定義結點類型的指針變量取 DLink *P;student A;P=L-next;A=P->data;(2)可以直接取Student A；A =L->next->data; 8）插入算法：當按隊列的方式進行插入運算時，新學生信息是插入到什么位置？寫出算法。 按隊列的形式插入運算，即鏈表的尾插法，即將新學生信息插在鏈表的最后面。void

13、 LinkListC:insert(int i) int j=1,k;/DLink *p,*q;p=new DLink;if(!p)cout<<"分配內(nèi)存失敗！"exit(0);q=L->next;/q=L;while(j<i&&q->next!=L)j+;q=q->next;if(j<=i&&q->next=L)/在末尾插入節(jié)點(即尾插法)cout<<"現(xiàn)在進行插入操作！"<<endl;cout<<"輸入學號(形如XXXX)：&

14、quot;cin>>p->data.no;cout<<"輸入姓名："cin>>p->;cout<<"依次輸入語文 英語 日語3門課程的成績"<<endl;for(k=0;k<3;k+)cin>>p->data.scorek;p->data.total=p->data.score0+p->data.score1+p->data.score2; q->next=p;p->prior=q;p->next=L

15、;L->prior=p;9）如果要求將新學生信息插入到鏈表中指定的i位置，寫出插入算法的代碼，并給出時間復雜度。插入操作使用了查找算法和插入算法，插入算法的時間主要花在查找算法上，其時間復雜度為o（n），n為除頭結點外結點的個數(shù)其中插入時分兩種情況，一種是插入的位置在鏈表節(jié)點之間，另一種是插入的位置長于鏈表總長，則采用尾插法。void LinkListC:insert(int i)/在第i個位置插入學生信息int j=1,k;/DLink *p,*q;p=new DLink;if(!p)cout<<"分配內(nèi)存失??！"exit(0);q=L->next

16、;/q=L;while(j<i&&q->next!=L)j+;q=q->next;if(j<=i&&q->next=L)/在末尾插入節(jié)點(即尾插法)cout<<"現(xiàn)在進行插入操作！"<<endl;cout<<"輸入學號(形如XXXX)："cin>>p->data.no;cout<<"輸入姓名："cin>>p->;cout<<"依次輸入語文 英語 日語3

17、門課程的成績"<<endl;for(k=0;k<3;k+)cin>>p->data.scorek;p->data.total=p->data.score0+p->data.score1+p->data.score2; q->next=p;p->prior=q;p->next=L;L->prior=p;else if(q!=L)/在鏈表中間位置插入cout<<"現(xiàn)在進行插入操作！"<<endl;cout<<endl;cout<<&quo

18、t;輸入學號(形如XXXX)："cin>>p->data.no;cout<<"輸入姓名："cin>>p->;cout<<"依次輸入語文 英語 日語3門課程的成績"<<endl;for(k=0;k<3;k+)cin>>p->data.scorek;p->data.total=p->data.score0+p->data.score1+p->data.score2; q->prior->next=p;

19、p->prior=q->prior;p->next=q;q->prior=p;10）刪除操作：在該刪除中，時間開銷主要用在什么地方？寫出刪除算法的代碼，給出時間復雜度。它與順序表中同樣的刪除上有什么不同？你是如何保證刪除了所有姓名相同的結點的？ 刪除操作時，時間開銷主要用在查找待刪除的學生的位置上。其代碼如下：void LinkListC:del()/刪除student Name;DLink *p,*q;q=L;p=L->next;cout<<"輸入待刪除學生姓名："cin>>N;/while(p!=L&

20、amp;&strcmp(N,p->)!=0)q=p;p=p->next;if(p!=L)q->next=p->next;p->next->prior=q;delete p;cout<<endl; cout<<"刪除成功"<<endl;elsecout<<" 沒有"<<N<<endl;cout<<endl;刪除操作的時間復雜度為：o（n）順序表中，每刪除一個結點就需要將其后面的結點

21、的位置向前移動一次，而鏈表則不需要這樣的操作，只需重新建立刪除結點的前結點和后結點之間的鏈接；為保證刪除所有的姓名相同的結點，這需要使用循環(huán)語句，一一查找，找到就執(zhí)行刪除操作，直到全部刪除為止。11）寫出修改學生成績的代碼。void LinkListC:modify()/修改學生成績int b3,i;DLink *p;p=L->next;student No;/學號cout<<"輸入待修改學生學號(形如XXXX)："cin>>No.no;while(p!=L&&strcmp(p->data.no,No.no)!=0)p=p

22、->next;if(p!=L)cout<<"依次輸入正確的語文 英語 日語3門課程的成績："<<endl;for(i=0;i<3;i+)cin>>bi;p->data.score0=b0;p->data.score1=b1;p->data.score2=b2;p->data.total=b0+b1+b2;elsecout<<endl;cout<<" 沒有這個學號"<<endl;cout<<endl;12）按總分排序時，你是否增加了空間？

23、寫出該算法的代碼。因為不能增加空間，所以我采用了冒泡排序法的思想。void LinkListC:order()/又高到低總分排列DLink *p,*q,*r;p=L->next;if(p!=L)r=p->next;p->next=L;p=r;while(p!=L)r=p->next;q=L;while(q->next!=L&&q->next->data.total>=p->data.total)q=q->next;p->next=q->next;if(q->next!=L)q->next->

24、;prior=p;q->next=p;p->prior=q;p=r;cout<<"排序成功！"<<endl;cout<<endl;實 驗 報 告四、實驗小結（包括問題和解決方法、心得體會、意見與建議等）1在使用鏈表存儲學生信息進行編程時，你所遇到的主要問題是什么，如何解決的？ 在處理鏈表的過程中，最大的問題是排序算法。在實現(xiàn)排序算法時，雙向鏈表不像數(shù)組那樣容易操作，而且要求是不能增加存儲空間，這意味著只能在雙向鏈表上操作。采用冒泡排序或者選擇算法。而最方便的算法插入不能使用。 最初認為選擇排序效率比冒泡排序高，所以采用了它，但后來做了很久，也不能實現(xiàn)這個算法，就改為冒泡排序。冒泡排序容易實現(xiàn)，我在做時，