第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)踐報(bào)告
20XX 報(bào) 告 匯 編 Compilation of reports
數(shù)據(jù)結(jié)構(gòu)實(shí)踐報(bào)告
學(xué)
號(hào)：
150906112
姓
名：
武錦蓉
班
級(jí)：
NET2 班
指導(dǎo)老師：
田喜平
時(shí)
間：
2016-12-21
報(bào)告文檔·借鑒學(xué)習(xí)word 可編輯·實(shí)用文檔
項(xiàng)目名稱
一、項(xiàng)目構(gòu)思 程序由三個(gè)模塊組成：
（1）輸入模塊：無提示語(yǔ)句，直接輸入總?cè)藬?shù) n 和報(bào)數(shù)次數(shù) m，中間用逗號(hào)隔開。
（2）處理模塊：將元素儲(chǔ)存于順序表中。在主函數(shù)中根據(jù)報(bào)數(shù)間隔確定需要?jiǎng)h除的元素的位置，在順序表中設(shè)置該位置并刪除該位置，同時(shí)輸出該位置的值。反復(fù)設(shè)置并刪除直到表空。
（3）輸出模塊：分別在 DOS 下和文件中，按移除元素的順序依次顯示其位置。
約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置，而這種數(shù)據(jù)是存在“第一元素、最后元素”，并且存在“唯一的前驅(qū)和后繼的”，符合線性表的特點(diǎn)。由于需要模擬約瑟夫環(huán)的出列問題，可以采用順序表來實(shí)現(xiàn)線性表，完成出列順序的輸出。
核心算法主要分為兩步：
1、確定需要?jiǎng)h除的位置，2、設(shè)置并刪除該位置。
已知報(bào)數(shù)間隔 m，我們可以把當(dāng)前位置加上 m 獲得需要?jiǎng)h除的位置，如果獲得的位置超過順序表中實(shí)際元素的總長(zhǎng)度，則可以通過減去數(shù)組的實(shí)際長(zhǎng)度來修正（即模擬環(huán)狀計(jì)數(shù)）。然后把順序表中的當(dāng)前指向位置設(shè)置為該位置，繼而刪掉該位置。
反復(fù)進(jìn)行上述確定位置和刪除位置的操作，直到順序表為空。
程序主要功能模塊 1、輸入的形式和輸入值的范圍：
每一次輸入的值為兩個(gè)正整數(shù)，中間用逗號(hào)隔開。
若分別設(shè)為 n,m，則輸入格式為：“n,m”。
不對(duì)非法輸入做處理，即假設(shè)輸入都是合法的。、輸出的形式：
輸出格式 1：在字符界面上輸出這 n 個(gè)數(shù)的輸出序列 輸出格式 2：將這 n 個(gè)數(shù)的輸出序列寫入到文件中、程序所能達(dá)到的功能：
對(duì)于輸入的約瑟夫環(huán)長(zhǎng)度 n 和間隔 m，輸出約瑟夫環(huán)的出列順序。、測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。
正確：
輸入：10,3
輸出：3 6 9 2 7 1 8 5 10 4
報(bào)告文檔·借鑒學(xué)習(xí)word 可編輯·實(shí)用文檔
輸入：41,3 輸出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
錯(cuò)誤：
輸入：10 3 輸出：6 8 7 1 3 4 2 9 5 10 二、程序清單 1、抽象數(shù)據(jù)類型的定義：
為實(shí)現(xiàn)上述程序的功能，可以用整數(shù)存儲(chǔ)用戶的輸入。并將用戶輸入的值存儲(chǔ)于線性表中。線性表 ADT 定義如下：
ADT list 數(shù)據(jù)對(duì)象：整形 數(shù)據(jù)關(guān)系：線性關(guān)系，即
基本操作：
bool remove(int &elem)//移除一個(gè)元素，被移除的元素賦給 elem
//如果操作成功，返回 true,否則返回 false
bool isEmpty()//判斷數(shù)組的元素是否清空，空返回 true,否則返回false
bool setPos(int place)//設(shè)置當(dāng)前元素的位置，設(shè)置成功返回 true,否則返回 false
int getLength()//獲取數(shù)組的實(shí)際長(zhǎng)度、各程序模塊之間的層次（調(diào)用）關(guān)系：
主函數(shù)會(huì)按設(shè)計(jì)的方法調(diào)用順序表中“獲取實(shí)際長(zhǎng)度”、“設(shè)置需要?jiǎng)h除元素的位置”、“移除該位置元素”和“判斷是否為空表”四種方法方法，使元素依次出列，并正確結(jié)束程序。
用整形存儲(chǔ)用戶輸入的整數(shù)。
用順序表實(shí)現(xiàn)線性表：
class AList {
private:
int *listArray;//指向數(shù)組的指針
int realSize;//數(shù)組中含有元素的實(shí)際長(zhǎng)度
報(bào)告文檔·借鑒學(xué)習(xí)word 可編輯·實(shí)用文檔
int fence;//指向當(dāng)前元素下標(biāo)
public:
AList(int s)//構(gòu)造函數(shù)，初始化數(shù)組
{
listArray=new int[s];
for(int i=0;i listArray[i]=i+1;//數(shù)組值等于數(shù)組下標(biāo)+1 realSize=s; fence=0;//指向首元素 } bool remove(int &elem)//移除一個(gè)元素 { if(isEmpty())return false;//如果數(shù)組為空返回 false elem = listArray[fence]; for(int i=fence;i { listArray[i]=listArray[i+1]; } realSize--; return true; } bool isEmpty()//判斷數(shù)組的元素是否清空 { if(realSize==0)return true; else return false; } bool setPos(int place)//設(shè)置當(dāng)前元素的位置 { if(place>=0&&place<=realSize) { fence=place; return true; } return false; } 報(bào)告文檔·借鑒學(xué)習(xí)word 可編輯·實(shí)用文檔 int getLength()//獲取數(shù)組長(zhǎng)度 { return realSize; } }; 在主函數(shù)中調(diào)用上述模塊的方法： ofstream fout;//文件流 fout.open(“C:Josephus.txt”);//設(shè)置文件路徑 int n,m,elem,point=0; scanf(“%d,%d”,&n,&m);//獲得用戶輸入 AList alist(n);//創(chuàng)建順序表對(duì)象 while(!alist.isEmpty())//如果順序表不為空，繼續(xù)刪除 { m=m%alist.getLength();//調(diào)整計(jì)數(shù)的長(zhǎng)度 if(m==0)m=alist.getLength(); if(point+m-1 else{point=point+m-alist.getLength()-1;} alist.setPos(point);//設(shè)置當(dāng)前需要?jiǎng)h除的位置 alist.remove(elem);//刪除元素 cout< fout< 四、測(cè)試結(jié)果（截圖顯示） 報(bào)告文檔·借鑒學(xué)習(xí)word 可編輯·實(shí)用文檔 五、遇到的問題及解決方法 1、初始化部分為循環(huán)賦值，時(shí)間復(fù)雜度為Θ(n)。 2、處理部分，我為了提高效率沒有采用循環(huán)尋找的方法，直接利用數(shù)學(xué)關(guān)系通過當(dāng)前位置獲得下一位置，因此對(duì)于長(zhǎng)度為 n 的約瑟夫環(huán)，只做了 n 次定位，每次定位的復(fù)雜度為Θ(1)，所以時(shí)間復(fù)雜度為Θ(n)。 但是用順序表實(shí)現(xiàn)時(shí)，每次其移除的方法是時(shí)間復(fù)雜度為Θ(k)的(k 與實(shí)際長(zhǎng)度有關(guān))，所以處理部分總的結(jié)果是(2)1(n n ?)的，化簡(jiǎn)后時(shí)間復(fù)雜度仍然為Θ(n 2)。 綜上，該算法的時(shí)間代價(jià)為Θ(n 2)。 （PS：如果是用循環(huán)查找，在 n 次定位中每次都使用了 m 次的循環(huán)，至少是Θ(n*m)，然后再用順序表的移除方法，總的復(fù)雜度應(yīng)該是Θ(m*n 2)的。） 事實(shí)上要用線性表來完成這道題，其復(fù)雜度最好也是Θ(n 2)的，畢竟對(duì)于 n個(gè)數(shù)據(jù)，每個(gè)都要進(jìn)行時(shí)間復(fù)雜度為Θ(n)的刪除工作。欲到達(dá)Θ(n)的效率除非不用線性表來實(shí)現(xiàn)。 六、體會(huì) 輸入人數(shù) n,報(bào)數(shù)間隔 m，創(chuàng)建順序表對(duì)象。 報(bào)告文檔·借鑒學(xué)習(xí)word 可編輯·實(shí)用文檔 主程序 輸入和輸出的格式： 輸入：10,3 輸出：3 10（文本中的輸出）：3 ！isEmpty()//順序表不為空 確定需要?jiǎng)h除的位置 Remove（）//調(diào)用刪除方法 數(shù)據(jù)結(jié)構(gòu)實(shí)踐報(bào)告整理 031040102 劉玉 ? 簡(jiǎn)述每一部分的對(duì)象、目的和要求； ? 畫出程序流程圖；另附A4紙手繪； ? 附源程序清單； ? 實(shí)驗(yàn)的收獲：遇到的問題以及解決的辦法、方法的優(yōu)缺點(diǎn)。 實(shí)驗(yàn)一 單鏈表的基本操作與運(yùn)算 題目一：?jiǎn)捂湵淼亩x、創(chuàng)建、插入和刪除操作，將數(shù)據(jù)元素顯示出來。 本題目針對(duì)單鏈表。聯(lián)表示通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表格中的數(shù)據(jù)元素。為了建立起數(shù)據(jù)元素之間的存儲(chǔ)關(guān)系，設(shè)置每一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)既存放數(shù)據(jù)data，又存放其后繼地址的部分next。而每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼的指針，所以稱其為單鏈表。本題目的要求是創(chuàng)建一個(gè)新的鏈表，并且完成鏈表的創(chuàng)建定義。鏈表是一種動(dòng)態(tài)管理的存儲(chǔ)結(jié)構(gòu)，鏈表中的每一個(gè)結(jié)點(diǎn)所占用的空間是根據(jù)運(yùn)行是的實(shí)際需要的空間生成的。因此建立單鏈表是從空鏈表開始的，每次讀入一個(gè)數(shù)據(jù)元素就申請(qǐng)一個(gè)結(jié)點(diǎn)鏈表的一段。在單鏈表中插入一個(gè)結(jié)點(diǎn)不需要移動(dòng)元素指針的指向。而刪除則需要找到木比啊偶元素的前驅(qū)結(jié)點(diǎn)，并且修改指針的指向。題目一需要的操作就是，對(duì)于一個(gè)新建的空鏈表，以其為對(duì)象進(jìn)行具體的數(shù)據(jù)的插入填寫。待鏈表中存有數(shù)據(jù)后，再進(jìn)行數(shù)據(jù)的整理查找，然后刪除目標(biāo)數(shù)據(jù)。 //031040102單鏈表 #include //定義一個(gè)鏈表 { int data;SLNODE *next;};void CREATE_SL(SLNODE *h)//創(chuàng)建一個(gè)單鏈表 { SLNODE *p,*s;int x;h->next=NULL; cout<<“輸入以-1結(jié)尾的一組數(shù)”< cin>>x; //開始輸入數(shù)據(jù) while(x!=-1) { s=new SLNODE[sizeof(SLNODE)]; //申請(qǐng)一個(gè)動(dòng)態(tài)新空間 s->data=x; if(h->next==NULL) h->next=s; else p->next=s; p=s; cin>>x; } p->next=NULL; //鏈表最后指向空 };int Insert_LinkList(SLNODE *h,int i,int x) //在單鏈表第i個(gè)位置插入x { SLNODE *p,*s;int j=0; p=h;while(p->next!=NULL&&j { p=p->next; j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;} else { s=new SLNODE[sizeof(SLNODE)]; s->data=x; s->next=p->next; p->next=s; return 1; } };int Del_LinkList(SLNODE *h,int i) //刪除單鏈表上第i個(gè)結(jié)點(diǎn) { SLNODE *p,*s;int j=0;p=h;while(p->next!=NULL&&j p=p->next;j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;4 6 8 9 7 2 6 9 7 5-1 } 鏈表數(shù)據(jù)如下 else 4 6 8 9 7 2 6 9 7 5 { 輸入需插入的數(shù)據(jù)8 if(p->next==NULL)輸入需插入的結(jié)點(diǎn)3 { 插入成功 cout<<“第i個(gè)結(jié)點(diǎn)不存在鏈表數(shù)據(jù)如下 ”< return 0;輸入需刪除的結(jié)點(diǎn) 4 } 刪除成功 else 鏈表數(shù)據(jù)如下 {s=p->next;p->next=s->next; 7 2 6 9 7 */ //刪除結(jié)點(diǎn) Deletes; //釋放結(jié)點(diǎn)空間 return 1; } } };void Print_LinkList(SLNODE *h)//輸出鏈表中所有元素 { SLNODE *p;p=h->next;cout<<“鏈表數(shù)據(jù)如下”< cout< data<<'t';} cout< data< cout<<“插入成功”< cout<<“插入失敗”< cout<<“刪除成功”< cout<<“刪除失敗”< 實(shí)驗(yàn)一的收獲 實(shí)驗(yàn)一讓我對(duì)于鏈表的創(chuàng)建于定義有了更多的接觸與認(rèn)識(shí)。之前的學(xué)習(xí)經(jīng)驗(yàn)里主要是 扎實(shí)，VC++，涉及鏈表的內(nèi)容，我學(xué)的不夠所以這次在軟件基礎(chǔ)時(shí)間里重新再次 學(xué)習(xí)。題目一比較簡(jiǎn)單，設(shè)僅是創(chuàng)建和插入以及刪除的基本操作。實(shí)驗(yàn)一的困難較小，我也是比較順利參照課本，完成體題目一，也讓我對(duì)于進(jìn)一步學(xué)習(xí)鏈表有了興趣和動(dòng)力。由淺入深，我會(huì)一點(diǎn)點(diǎn)開展學(xué)習(xí)。在圖書館借閱一本《數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實(shí)驗(yàn)指 導(dǎo)》，里面對(duì)于實(shí)驗(yàn)的指導(dǎo)比較全面而且有很多實(shí)例可以參考。 上機(jī)實(shí)踐二 題目二：棧、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義、創(chuàng)建、插入和刪除操作，將數(shù)據(jù)元素顯示出來。本題目要求掌握棧和列隊(duì)。棧和列隊(duì)是 兩種常見的數(shù)據(jù)結(jié)構(gòu)。它們的邏輯結(jié)構(gòu)和線性表相同。其特點(diǎn)是，插入和刪除等運(yùn)算的位置有所限制：棧是按照先進(jìn)后出的規(guī)則進(jìn)行操作，而是按照先進(jìn)先出的規(guī)則進(jìn)行操作。堆棧技術(shù)現(xiàn)在的應(yīng)用非常廣泛，不管是編譯軟件還是程序設(shè)計(jì)，在操作系統(tǒng)和事務(wù)管理中則是廣泛應(yīng)用了隊(duì)列技術(shù)。棧是限制在一段進(jìn)行插入和刪除的線性表，允許插入刪除的這一端稱為棧頂，固定端稱為棧底。棧是運(yùn)算受到限制的一種線 性表，采用順序存儲(chǔ)的是順序棧，采用鏈?zhǔn)酱鎯?chǔ)的是鏈棧。題目要求對(duì)于兩種存儲(chǔ)結(jié)構(gòu) 的棧進(jìn)行定義創(chuàng)建。對(duì)于順序棧，首先需要申請(qǐng)共享的一位數(shù)組空間。即為先置空棧，然后入棧插入元素（特別要注意棧滿不能插入），刪除出棧（特別要注意棧空不能出棧）。對(duì)于鏈棧，采用帶頭指針的單鏈表來實(shí)現(xiàn).隊(duì)列操作的順序隊(duì)列，插入在表的隊(duì)尾一端，刪除在表的另外的隊(duì)頭一端。隊(duì)的隊(duì)頭和隊(duì)尾都是活動(dòng)的，特別地需要設(shè)置隊(duì)頭和隊(duì)尾兩個(gè)指針。需要實(shí)現(xiàn)置空隊(duì)、入隊(duì)、出對(duì)、以及判別隊(duì)列是否為空的運(yùn)算。對(duì)于鏈?zhǔn)疥?duì)列，通常是用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)的，并且設(shè)置一個(gè)隊(duì)頭指針（始終指向頭結(jié)點(diǎn)）和一個(gè)隊(duì)尾指針（指向當(dāng)前的最后一個(gè)元素），特別地，當(dāng)隊(duì)列為空時(shí)隊(duì)頭和隊(duì)尾指針均指向頭結(jié)點(diǎn)。顯示創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)，申請(qǐng)頭尾結(jié)點(diǎn)，然后進(jìn)行如對(duì)操作不斷申請(qǐng)新的結(jié)點(diǎn)，還需要進(jìn)行隊(duì)列是否為空的判斷操作，隊(duì)空則出隊(duì)失敗。 //031040102 順序棧 #include return 1;else return 0;};int Push_SeqStack(SqStack *s,ElemType x)//入棧 { if(s->top==MaxSize-1) return 0;else { s->top++; s->data[s->top]=x; return 1; } };int Pop_SeqStack(SqStack *s,ElemType x) //出棧 { if(IsEmpty_SeqStack(s)) return 0;else { x=s->data[s->top]; s->top--; return 1; } }; ElemType Top_SeqStack(SqStack *s) //取出棧頂元素 { if(IsEmpty_SeqStack(s)) return 0; else return(s->data[s->top]); };void Print(SqStack *s) //輸出棧內(nèi)所有元素 { if(IsEmpty_SeqStack(s)) cout<<“ 此棧為空 ”< cout<<“棧內(nèi)元素為”< for(int i=s->top;i>-1;i--) cout< } };void main(){ SqStack *s;int x; s=Init_SeqStack();cout<<“ 輸入一組以-1結(jié)尾的數(shù)”< s->top++; s->data[s->top]=x; cin>>x;} Print(s);cout<<“輸入需插入的數(shù)”< cout<<“插入成功”< cout<<“插入失敗”< Print(s); delete p;if(Pop_SeqStack(s,x)) return top; cout<<“刪除成功”< cout<<“刪除失敗”< Print(s);} 輸入一組以-1結(jié)尾的數(shù) 5 8 9 7 3 6 2 1 8-1 棧內(nèi)元素為 8 1 2 6 3 7 9 8 5 輸入需插入的數(shù)4 插入成功 棧內(nèi)元素為 4 8 1 2 6 3 7 9 8 5 刪除成功 棧內(nèi)元素為 8 1 2 6 3 7 9 8 5 //031040102 鏈棧 #include //定義一個(gè)鏈棧 { elemtype data;LinkStack *next;};LinkStack *Init_LinkStack()//鏈棧的初始化 { LinkStack *top;top=new LinkStack[sizeof(LinkStack)];top=NULL;return top;};LinkStack *Push_LinkStack(LinkStack *top,elemtype x) //數(shù)據(jù)入棧 { LinkStack *s;s=new LinkStack[sizeof(LinkStack)];s->data=x;s->next=top;top=s;return top;};LinkStack *Pop_LinkStack(LinkStack *top,elemtype x) //數(shù)據(jù)出棧 { LinkStack *p;if(top==NULL) return NULL;else { x=top->data; p=top; top=top->next;//輸出棧內(nèi)所有元素 { LinkStack *p;p=top;if(p==NULL) cout<<“此棧為空”< cout<<“棧內(nèi)元素為”< for(;p->next!=NULL;p=p->next) cout< data<<'t'; cout< data< s=new LinkStack[sizeof(LinkStack)]; s->data=x; s->next=top; top=s; cin>>x;} Print(top);cout<<“輸入需插入的數(shù)”< 輸入需插入的數(shù)15 棧內(nèi)元素為 15 65 23 1 6 3 4 8 9 7 棧內(nèi)元素為 65 23 1 6 3 4 8 9 7 //031040102 順序隊(duì)列 #include typedef struct queue //定義一個(gè)順序隊(duì)列 { ElemType data[MaxSize];int rear,front;}SeQueue;SeQueue*Init_Queue()//隊(duì)列的初始化 { SeQueue *sq;sq=new SeQueue[sizeof(SeQueue)];sq->front=sq->rear=-1;return sq;};int IsEmpty_Queue(SeQueue *sq)//判空隊(duì)列 { if(sq->rear==-1) return 1;else return 0;};int In_Queue(SeQueue *sq,ElemType x) //入隊(duì) { if(sq->rear==MaxSize-1) return 0;else { sq->rear++; sq->data[sq->rear]=x; return 1;} };int Out_Queue(SeQueue*sq) //出隊(duì) { if(IsEmpty_Queue(sq)) return 0;else { sq->front++; return(sq->data[sq->front]);} };int Front_Queue(SeQueue *sq)//讀隊(duì)頭元素 { if(IsEmpty_Queue(sq)) return 0;else { return(sq->data[sq->front+1]);} };void Print(SeQueue *sq)//輸出隊(duì)列所有元素 { if(IsEmpty_Queue(sq)) cout<<“此隊(duì)列為空”< cout<<“隊(duì)列內(nèi)元素為”< for(int i=sq->front+1;i<=sq->rear;i++) cout< cout< cin>>x;while(x!=-1){ sq->rear++; sq->data[sq->rear]=x; cin>>x;} Print(sq);cout<<“輸入需插入的數(shù)”< cout<<“插入成功”< cout<<“插入失敗”< cout<<“刪除成功”< cout<<“刪除失敗”< //定義鏈隊(duì)的結(jié)點(diǎn)類型 { ElemType data;QNODE *next;}; typedef struct linkqueue p=q->front->next; //封裝頭尾指針 if(IsEmpty_LQueue(q)){ cout<<“此棧為空”< cout<<“ 隊(duì)列內(nèi)元素為 ”< { for(;p->next!=q->rear->next;p=p->next)LinkQueue *q; cout< data<<'t';QNODE *p; cout< data< } //申請(qǐng)頭尾節(jié)點(diǎn) p=new QNODE[sizeof(QNODE)];//申請(qǐng)鏈隊(duì)頭結(jié)點(diǎn) p->next=NULL;q->front=q->rear=p;return q;};void In_LQueue(LinkQueue *q,ElemType x)//入隊(duì)操作 { QNODE *p;p=new QNODE[sizeof(QNODE)];//申請(qǐng)新結(jié)點(diǎn) p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;};int IsEmpty_LQueue(LinkQueue *q)//判隊(duì)空 { if(q->front==q->rear) return 1;else return 0;};int Out_LQueue(LinkQueue *q,ElemType x)//出隊(duì)操作 { QNODE *p;if(IsEmpty_LQueue(q)) return 0;else { p=q->front->next; q->front->next=p->next; x=p->data; delete p; if(q->front->next==NULL) //一個(gè)元素時(shí)，出隊(duì)后隊(duì)空還要改隊(duì)尾指針 q->rear=q->front; return 1;} };void Print(LinkQueue *q){ QNODE *p;}; void main(){ LinkQueue *q;QNODE *s;int x; q=Init_LQueue();cout<<“輸入一組以-1結(jié)尾的數(shù)”< { s=new QNODE[sizeof(QNODE)]; s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; cin>>x; } Print(q);cout<<“輸入需插入的數(shù)”< cout<<“刪除成功”< else cout<<“刪除失敗”< 隊(duì)列內(nèi)元素為 8 9 4 5 3 2 1 實(shí)驗(yàn)二的收獲 實(shí)驗(yàn)二是全新的知識(shí)需要理解。在之前的學(xué)習(xí)經(jīng)歷中沒有接觸到棧和隊(duì)列。所以這 次是從概念開始學(xué)習(xí)的。在具體程序的學(xué)習(xí)應(yīng)用時(shí)候，我對(duì)于書上提到的，首先需要的是為棧申請(qǐng)共享空間，有了理解和認(rèn)識(shí)。特別地，在棧空的時(shí)候有s->top[0]==-1;s->top[1]==Maxsize。再有就是棧滿的時(shí)候不可以入棧操作，未滿的入棧操作則是先移動(dòng)再賦入值。例如語(yǔ)句(兩句的順序不可以顛倒)s->top++;s->data[s->top]=x;由于棧的主要運(yùn)算是在棧頂插入、刪除。因此我在鏈表的頭部作為棧頂，這樣方便了程序，而且不需要像單鏈表一樣為了運(yùn)算方便附加一個(gè)頭結(jié)點(diǎn)。在聯(lián)系隊(duì)列的相關(guān)程序時(shí)候，我理解了，列隊(duì)單向空間無法利用，即為前面的已經(jīng)被指針制動(dòng)過的空間不能釋放也無法利用。除此，隊(duì)列的操作里面。有可能出現(xiàn)“隊(duì)滿”“隊(duì)空”的條件相同，front==rear;需要具體區(qū)分。 上機(jī)實(shí)踐三 題目三：二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)定義、創(chuàng)建、先序和后序遍歷，并將結(jié)果序列輸出。 二叉樹是有限個(gè)元素的集合，該集合或者為空、或者由一個(gè)稱為根的元素以及兩個(gè)不相交的、被稱為左子樹右子樹的二叉樹組成。二叉樹的臉是存儲(chǔ)結(jié)構(gòu)是指，用鏈表來表示一顆二叉樹，即用鏈表來表示元素的邏輯關(guān)系。二叉樹的鏈表存儲(chǔ)的結(jié)點(diǎn)有三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來指向該節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的存儲(chǔ)地址。當(dāng)左子結(jié)點(diǎn)或者右子結(jié)點(diǎn)不存在的時(shí)候，相應(yīng)的指針值域?yàn)榭铡６鏄涞谋闅v是指按照某種順序結(jié)構(gòu)訪問二叉樹的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)僅被訪問一次。限定先左后右，只有三種方式即為先序遍歷、中序遍歷、后序遍歷。遍歷其實(shí)是一個(gè)遞歸的過程，若二叉樹為空，則遍歷結(jié)束，不然就按照順序依次訪問根結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)。 //031040102 二叉樹 #include //定義二叉樹結(jié)點(diǎn) { elemtype data; BiTNode *lchild,*rchild;//兩結(jié)點(diǎn)指針 }BiTree; BiTree *Create()//二叉樹的創(chuàng)建,遞歸算法 { BiTree *bt;elemtype ch;cin>>ch;if(ch=='0'){ bt=NULL;} else { bt=new BiTNode[sizeof(BiTNode)]; bt->data=ch; bt->lchild=Create(); bt->rchild=Create();} return bt;}; void PreOrder(BiTree *bt) //先序遍歷二叉樹，遞歸算法 { if(bt==NULL) return;cout< void PostOrder(BiTree *bt) //先序遍歷二叉樹，遞歸算法 { if(bt==NULL) return;PostOrder(bt->lchild);PostOrder(bt->rchild);cout< void main(){ BiTree *bt;cout<<“輸入所需字符（空結(jié)點(diǎn)以零代替）”< 輸入所需字符（空結(jié)點(diǎn)以零代替）frt0e000qj00m00 先序遍歷可得二叉樹元素為 f r t e q j m 后序遍歷可得二叉樹元素為 e t r j m q f 實(shí)驗(yàn)三的收獲 二叉樹可以用計(jì)算機(jī)語(yǔ)言來讀取，通過遍歷可以恢復(fù)二叉樹。通過這次試驗(yàn)更加深刻理解二叉樹。本體操作不斷調(diào)用函數(shù)，遞歸實(shí)現(xiàn)遍歷。實(shí)際需要的時(shí)候?qū)τ谝阎亩鏄涞拿總€(gè)結(jié)點(diǎn)逐一訪問。一次完整的便利科室的一個(gè)二叉樹的結(jié)點(diǎn)信息由非線性排列轉(zhuǎn)變?yōu)橐饬x上的線性排列。在二叉樹的鏈表中無法根據(jù)結(jié)點(diǎn)找到其父結(jié)點(diǎn)。不過，二叉樹的鏈表結(jié)構(gòu)靈巧簡(jiǎn)便、操作方便。特別地還節(jié)省空間。對(duì)于一個(gè)龐大的工程型程序的話，空間與簡(jiǎn)便十分重要。同樣的目的，同樣的結(jié)果，需要比較選擇，肯定是精巧簡(jiǎn)單操作性強(qiáng)等等優(yōu)勢(shì)作為判斷取舍。 上機(jī)實(shí)踐四 題目四：查找：順序查找、二分查找 查找是許多程序中最為耗費(fèi)時(shí)間的部分。因此需要方法提高運(yùn)行的速度和效率。順序查找又稱為線性查找，也是最為基本的查找方法之一。具體實(shí)現(xiàn)為：從表的一端開始，依次將關(guān)鍵碼與給定的值比較，若找到查找成功，并且給出數(shù)據(jù)元素在表中的位置，若整個(gè)表查找完成仍未找到相同的關(guān)鍵碼，則查找失敗給出失敗信息。 二分法查找只適用于順序存儲(chǔ)的有序表。有序表即是表中數(shù)據(jù)元素按照關(guān)鍵碼的升序或者降序排列。去中間元素作為比較對(duì)象，若給定值與中間元素的關(guān)鍵碼相等，則為查找成功；若給定值小于中間元素的關(guān)鍵碼，則在中間元素的左半?yún)^(qū)繼續(xù)查找，若給定值大于中間元素的關(guān)鍵碼，則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述的查找過程直到查找成功，或者所查找的區(qū)域，沒有該元素查找失敗。 //031040102順序查找 #include #define MaxSize 1024 typedef struct { KeyType key; //定義關(guān)鍵碼字段 ElemType elem;//定義其他字段 }elemtype; typedef struct //順序存儲(chǔ)結(jié)構(gòu)定義 { elemtype elem[MaxSize];//定義數(shù)組 int length; //表長(zhǎng)度 }S_TBL; S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int s_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素 { tbl->elem[0].key=kx; //存放檢測(cè) for(int i=tbl->length;tbl->elem[i].key!=kx;i--); //從表尾向前查找 return i;}; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結(jié)尾的數(shù)(關(guān)鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“請(qǐng)輸入所需查找數(shù)的關(guān)鍵碼字段：”< { flag=mid; cout<<“查找成功”< break; cout<<“所查找的數(shù)為//查找成功，元素位置設(shè)置到flag中 ”< } } } else return flag; cout<<“查找失敗”< //定義關(guān)鍵碼字段 ElemType elem; //定義其他字段 }elemtype;typedef struct //順序存儲(chǔ)結(jié)構(gòu)定義 { elemtype elem[MaxSize];//定義數(shù)組 int length; //表長(zhǎng)度 }S_TBL;S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素 { int mid,flag=0,low=1,high=tbl->length;//1.設(shè)置初始區(qū)間 while(low<=high) //2.表空測(cè)試 { //非空，進(jìn)行比較測(cè)試 mid=(low+high)/2; //3.得到中間點(diǎn) if(kx high=mid-1; //調(diào)整到左半?yún)^(qū) else if(kx>tbl->elem[mid].key) low=mid+1; //調(diào)整到右半?yún)^(qū) else { //返回該元素在表中的位置，或返回0 };void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結(jié)尾的數(shù)(關(guān)鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“輸入所需查找數(shù)的關(guān)鍵碼字段”< cout<<“查找成功”< cout<<“所查找的數(shù)為”< } else cout<<“查找失敗”< -1結(jié)尾的數(shù)(數(shù)據(jù)元素)33 22 11 55 99 77 88 66 44-1 輸入所需查找數(shù)的關(guān)鍵碼字段3 查找成功 所查找的數(shù)為33 實(shí)驗(yàn)四的收獲 查找的程序?qū)ξ襾碚f不陌生。兩種基本方法的比較和應(yīng)用里，我留意了最大查找次 數(shù)的不同。順序查找的進(jìn)行，如果查找不成功那么會(huì)議共比較N+1次。當(dāng)數(shù)據(jù)量很大的時(shí)候，平均查找長(zhǎng)度過大，當(dāng)然順序查找對(duì)于數(shù)據(jù)的存貯方式?jīng)]有任何的要求。折半查找會(huì)有一個(gè)平均查找長(zhǎng)度以及查找的最大長(zhǎng)度。 我比較傾向于這本查找，其查找的效率明顯會(huì)高于順序查找。特別地，我還留意到對(duì)于單鏈表結(jié)構(gòu)，無法進(jìn)行二分法的查找，因?yàn)槿康脑氐亩ㄎ恢荒軓闹羔橀_始。對(duì)于線性列表只能采取順序查找的方式。 上機(jī)實(shí)踐五 題目五：排序(插入排序選擇排序冒泡排序)排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要的運(yùn)算，其目的就是將一組數(shù)據(jù)按照規(guī)定的順序進(jìn)行排列。排序的目的是便于查詢和處理。插入排序的基本思想是每一步將一個(gè)待排序的元素，按照其關(guān)鍵字嗎的大小，插入到前面已經(jīng)排序號(hào)的一組元素的適當(dāng)?shù)奈恢蒙希浪械脑囟疾迦霝橹埂Ｒ话愕卣J(rèn)為插入排序是一個(gè)穩(wěn)定的排序方法。選擇排序，每次從當(dāng)前待排序的記錄中，通過依次地進(jìn)行關(guān)鍵字媽的比較從中選擇一個(gè)關(guān)鍵字最小的記錄，并且把它與當(dāng)前待排序的第一個(gè)記錄進(jìn)行交換。直接選擇排序是一個(gè)不穩(wěn)定的排序方法。冒泡排序是一種簡(jiǎn)單的交換排序的方法。一次地比較相鄰兩個(gè)記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個(gè)記錄的次序相反（即位前一個(gè)記錄的關(guān)鍵字大雨后有一個(gè)記錄的關(guān)鍵字），進(jìn)行記錄的交換一直到?jīng)]有反序?yàn)橹埂O端情況下，冒泡排序會(huì)有最短與最長(zhǎng)時(shí)間，整個(gè)隊(duì)列越是接近有序，則冒泡排序的進(jìn)行次數(shù)越少。 //031040102 插入排序 #include //定義關(guān)鍵碼字段 ElemType elem; //定義其他字段 }elemtype; typedef struct //順序存儲(chǔ)結(jié)構(gòu)定義 { elemtype elem[MaxSize]; //定義數(shù)組 int length; //表長(zhǎng)度 }S_TBL; S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素 { int mid,flag=0,low=1,high=tbl->length;//1.設(shè)置初始區(qū)間 while(low<=high) //2.表空測(cè)試 { //非空，進(jìn)行比較測(cè)試 mid=(low+high)/2; //3.得到中間點(diǎn) if(kx high=mid-1; //調(diào)整到左半?yún)^(qū) else if(kx>tbl->elem[mid].key) low=mid+1; //調(diào)整到右半?yún)^(qū) else { flag=mid; break; //查找成功，元素位置設(shè)置到flag中 } } Return flag;//返回該元素在表中的位置，或返回0 }; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結(jié)尾的數(shù)(關(guān)鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)”< while(k!=-1)};{ void Print(RecType R[],int n) tbl->elem[i].elem=k; i++; cin>>k;} cout<<“輸入所需查找數(shù)的關(guān)鍵碼字段”< cout<<“查找成功”< cout<<“所查找的數(shù)為”< cout<<“查找失敗”< k=i; for(j=i+1;j<=n;j++) if(R[j].key k=j; if(k!=i) { R[0]=R[k]; R[k]=R[i]; R[i]=R[0]; } } //輸出數(shù)組內(nèi)所有元素 { cout<<“關(guān)鍵字段為：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“請(qǐng)輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)：”< R[++n].otherinfo=x; cin>>x;} cout<<“ 排序前 ”< Print(R,n);SelectSort(R,n);cout<<“排序后”< 請(qǐng)輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)： 33 22 11 44 55 66 99 88 77-1 排序前 關(guān)鍵字段為： 6 9 7 4 1 5 6 8 3 所有元素為： 33 22 11 44 55 66 99 88 排序后 關(guān)鍵字段為： 1 3 4 5 6 6 7 8 9 所有元素為： 55 44 66 33 99 11 88 22 //031040102 冒泡排序 #include #define MaxSize 50 cin>>x;typedef struct RecType } //定義排序記錄的形式 cout<<“排序前：”< 請(qǐng)輸入一組以 -1結(jié)尾的數(shù)(關(guān)鍵碼字段)： //選擇排序函數(shù) { int i,j,flag;for(i=1;i flag=1; for(j=1;j<=n-i;j++) if(R[j+1].key { flag=0; R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; } if(flag==1) return;} };void Print(RecType R[],int n)//輸出數(shù)組內(nèi)所有元素 { cout<<“關(guān)鍵字段為：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“請(qǐng)輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)：”< R[++n].otherinfo=x;9 8 7 4 1 5 6-1 請(qǐng)輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)： 11 22 33 44 66 55 77 88-1 排序前： 關(guān)鍵字段為： 6 9 8 7 4 1 5 6 所有元素為： 11 22 33 44 66 55 77 88 排序后： 關(guān)鍵字段為： 1 4 5 6 6 7 8 9 所有元素為： 55 66 77 11 88 44 33 22 實(shí)驗(yàn)五的收獲 三種不同的排序方式，都是之前C++ 學(xué)習(xí)時(shí)候的重點(diǎn)掌握內(nèi)容。 直接插入排序的算法很簡(jiǎn)潔，也很容易實(shí)現(xiàn)。從空間看，它只需要一個(gè)元素的輔助，從實(shí)踐看該算法的主程序運(yùn)行次數(shù)只比元素的個(gè)數(shù)少一。當(dāng)然由于原列表的排序狀況未知，其總比較次數(shù)和總的移動(dòng)次數(shù)也是未定的，取平均數(shù)約為0.25N^2。對(duì)于直接選擇排序，比較次數(shù)與原表元素的排列順序無關(guān)，移動(dòng)次數(shù)有關(guān)。根據(jù)冒泡排序的思想，待排序的記錄有序之 后，則在下一趟的排序時(shí)候不會(huì)再有記錄的交換位置，由此，我增加了一個(gè)標(biāo)記flag，來直觀表示每一次的排序是否需要發(fā)生交換，無交換則已經(jīng)完成可以結(jié)束冒泡。特別地冒泡排序需要增加一個(gè)附加的單元來實(shí)現(xiàn)元素的交換。在交換時(shí)需要留意免得出錯(cuò)。 · 北京聯(lián)合大學(xué) 實(shí)訓(xùn)報(bào)告 課程（項(xiàng)目）名稱： 數(shù)據(jù)結(jié)構(gòu) 學(xué) 院： 專 業(yè)： 班 級(jí)： 學(xué) 號(hào)： 姓 名： 成 績(jī)： 2012年 6 月 21 日 數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)任務(wù)一 一、任務(wù)與目的： 1、用順序表表示兩個(gè)無序集合A、B，實(shí)現(xiàn)集合的如下操作，求兩個(gè)集合的并集、交集、差集。 2、用順序表表示兩個(gè)集合A、B（集合A、B都是有序遞增的情況）實(shí)現(xiàn)集合的如下操作，求兩個(gè)集合的并集、交集、差集。 3、用帶頭單鏈表存儲(chǔ)結(jié)構(gòu)表示兩個(gè)無序集合A、B，實(shí)現(xiàn)集合的如下操作，求兩個(gè)集合的并集、交集、差集。 4、用帶頭單鏈表存儲(chǔ)結(jié)構(gòu)表示兩個(gè)集合A、B（集合A、B都是有序遞增的情況），實(shí)現(xiàn)集合的如下操作，求兩個(gè)集合的并集、交集、差集。 5、殺人游戲 N個(gè)人坐成一圈玩殺人游戲，按順時(shí)針編號(hào) N。從1號(hào)開始順時(shí)針開始數(shù)到第m號(hào)就殺掉第一個(gè)人，被殺掉的人要退出游戲。 如果數(shù)到了編號(hào)的末尾，接著數(shù)開頭的編號(hào)。 重復(fù)，直至殺掉一半人時(shí)，游戲結(jié)束，聰明的你能告訴我活到最后的幸存者最初的編號(hào)是多少嗎？ 輸入數(shù)據(jù)：N、M ；輸出數(shù)據(jù)：幸存者的編號(hào) 分析該程序，如果N=20，M=2，……10。聰明的你應(yīng)選擇的編號(hào)是多少，（提示，計(jì)算出M分別等于1到10的情況下，那些編號(hào)生存概率較大）。給出實(shí)驗(yàn)結(jié)果 6、作業(yè)抽查問題：有35個(gè)學(xué)生的班級(jí)，由于某種原因不能夠做到全部檢查作業(yè)，現(xiàn)在希望每次抽查10名學(xué)生，希望能夠隨機(jī)抽查，并能夠有記憶，即希望抽查過的學(xué)生，下次抽查的概率有所減小，但避免不被抽查。設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)該功能，給出你的解釋。1.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j;int flag=0;C.length=0;for(i=0;i if(flag==0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j;int flag=0;C.length=0;i=0;for(j=0;j if(flag!=0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;C.length=0;k=0;for(i=0;i if(flag==0) {C.elem[k]=A.elem[i];k++;} } C.length=k;} 運(yùn)行結(jié)果： 2.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];k++;i++; } else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {C.elem[k]=B.elem[j];k++;j++;} } } if(i {C.elem[k]=A.elem[i];k++;i++; } } if(j {C.elem[k]=B.elem[j];k++;j++;} } C.length=k;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {i++;} else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {j++;} } } C.length=k;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];i++;k++; } else {if(A.elem[i]==B.elem[j]) {i++;j++;} else {j++; } } } if(i {C.elem[k]=A.elem[i];k++;i++;} } C.length=k;} void InserOrder_Sq(SqList &L,ElemType e){int i,j;for(i=0;i L.elem[j+1]=L.elem[j];L.elem[i]=e;L.length++;} 運(yùn)行結(jié)果： 3.void bing(link &p,link &h,link &q) {//求并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void jiao(link &p,link &h,link &q) { //求交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void cha(link &p,link &h,link &q) {//求差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l;m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) { int i,j=0;Elem e;for(i=0;i<11;){if(i==0){p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 運(yùn)行結(jié)果： 4.void bing(link &p,link &h,link &q) { //并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l;} s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0) {LInsert(q,i);} s=s->next;} } void jiao(link &p,link &h,link &q) {//交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void cha(link &p,link &h,link &q) {//差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) {int i,j=0;Elem e;for(i=0;i<11;){if(i==0) {p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 運(yùn)行結(jié)果： 5.#include struct kill { int num; struct kill *next;}; struct kill *create(int m) {struct kill *head,*p1,*p2;int i;p1=p2=(struct kill*)malloc(LEN);head=p1; head->num=1; for(i=1,p1->num=1;i p2->next=p1;p2=p1;} p2->next=head;return head;} struct kill *findout(struct kill *start,int n){int i; struct kill *p;i=n;p=start; for(i=1;i struct kill *letout(struct kill *last){struct kill *out,*next;out=last->next; last->next=out->next;next=out->next;free(out);return next;} void main() { int m,n,i,servive;struct kill *p1,*p2; cout<<“請(qǐng)輸入?yún)⒓託⑷擞螒蚩側(cè)藬?shù)m:”< cout<<“要?dú)⒌舻娜说男蛱?hào)n:”< { p1=p2=create(m);for(i=1;i p2=letout(p1);p1=p2;} servive=p2->num;free(p2);} cout<<“幸存者是：”< 6.#include //學(xué)生id int times; //定義學(xué)生抽查數(shù)};Student stu[35];//35個(gè)學(xué)生 int cho[10]; //抽查的10個(gè)學(xué)生 int top; //已抽查學(xué)生數(shù) int choose(){int n=rand()%35;//隨機(jī)抽取 for(int i=0;i int n2=rand()%stu[n].times;//否則幾率按抽取的次數(shù)減小,具體為(1/抽取次數(shù))if(n2==0)return n;else return choose();} void main(){char a='Y';srand(time(0));//隨機(jī)數(shù)初始化 int i;for(i=0;i<35;i++)//學(xué)生初始化 {stu[i].id=i+1;stu[i].times=0;} while(a=='Y'||a=='y'){int tmp;top=0;for(i=0;i<10;i++)//抽取10個(gè)學(xué)生 {tmp=choose();//抽取學(xué)生 cho[top++]=tmp;stu[tmp].times++;cout<<“第”< 數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)任務(wù)二 一、任務(wù)與目的：主要考察的是棧與隊(duì)列的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。 1、用棧，判斷一個(gè)算數(shù)表達(dá)式中的圓括弧、方括弧和花括弧是否匹配。 2、用棧，把十進(jìn)制的整數(shù)轉(zhuǎn)換為二至九之間的任一進(jìn)制 3、設(shè)計(jì)一個(gè)算法，檢測(cè)一個(gè)字符串?dāng)?shù)組是否是回文，回文是指這個(gè)字符串是否關(guān)于中心對(duì)稱。int Check（char a[]，int n） 4、采用SPT規(guī)則的單機(jī)生產(chǎn)計(jì)劃問題。問題描述如下，存在一臺(tái)機(jī)器，要加工n個(gè)工件，每個(gè)工件i都有一個(gè)確定的加工時(shí)間，采用按照 遞增的順序，進(jìn)行加工，計(jì)算每個(gè)工件的完成時(shí)間（初始加工時(shí)間為0）。設(shè)計(jì)一個(gè)算法，輸入工件數(shù)量n，隨機(jī)在[1，30]的區(qū)間內(nèi)產(chǎn)生每個(gè)工件的加工時(shí)間。按照SPT規(guī)則進(jìn)行加工，輸出每個(gè)工件的完成時(shí)間。 5、采用EDD規(guī)則的單機(jī)生產(chǎn)計(jì)劃問題。問題描述如下，存在一臺(tái)機(jī)器，要加工n個(gè)工件，每個(gè)工件i都有一個(gè)確定的加工時(shí)間，同時(shí)每個(gè)工件都有一個(gè)確定的交貨期，采用按照 遞增的順序，進(jìn)行加工，計(jì)算每個(gè)工件的完成時(shí)間（初始加工時(shí)間為0）。設(shè)計(jì)一個(gè)算法，輸入工件數(shù)量n，隨機(jī)在[1，30]的區(qū)間內(nèi)產(chǎn)生每個(gè)工件的加工時(shí)間，在區(qū)間[2，20*n]內(nèi)隨機(jī)產(chǎn)生每個(gè)工件的交貨期。按照EDD規(guī)則進(jìn)行加工，輸出每個(gè)工件的完成時(shí)間，計(jì)算每個(gè)工件i完成時(shí)間和 的差值。1.void Ininstack(stack &s) {//初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) {//擴(kuò)容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) { //入棧 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) {//出棧 stype e;e=s.elem[s.top];s.top--;return e;} stype GetTop(stack s) {//取棧頂 stype e;e=s.elem[s.top ];return e;} void main(){stype e,t,ch;stack s;char a[20];int i=0,n;Ininstack(s);cout<<“請(qǐng)輸入算術(shù)表達(dá)式(以$結(jié)尾):”;while(ch!='$'){cin>>ch; a[i]=ch;i++;} n=i;for(i=0;i {e=a[i];Push(s,e);} if(a[i]=='}'||a[i]==']'||a[i==')']) {t=GetTop(s); if(a[i]=='}' && t=='{')Pop(s); else if(a[i]==']' && t=='[') Pop(s);else if(a[i]==')' && t=='(') Pop(s);}} if(s.top==-1) cout<<“括號(hào)匹配!”< cout<<“括號(hào)不匹配!”< 2.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //擴(kuò)容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入棧 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) { //出棧 stype e;e=s.elem[s.top];s.top--;return e;} void main(){stack s;int a,b;Ininstack(s);cout<<“請(qǐng)輸入任意非負(fù)十進(jìn)制數(shù):”;cin>>a;cout<<“請(qǐng)輸入需要轉(zhuǎn)換的進(jìn)制數(shù)(進(jìn)制數(shù)為二至九):”;cin>>b;while(a){Push(s,a%b);a=a/b;} while(!(s.top==-1))cout< 運(yùn)行結(jié)果： 3.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //擴(kuò)容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入棧 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} void Error(char *a) { cout< stype Pop(stack &s) { stype e;e=s.elem[s.top];s.top--;return e;} int Check(char a[],int n,stack &s) {//判斷 int i;char e;Pop(s);for(i=0;i urn 0;} void main(){stack s; r ch,a[50];t i=0,n,t;instack(s);cout<<“請(qǐng)輸入字符串(以$結(jié)尾):”;while(ch!='$'){cin>>ch;[i]=ch;ush(s,ch);+;} n=i;Check(a,n,s);if(t==1)cout<<“是回文!”< 運(yùn)行結(jié)果： 4.void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 { int i,j,t,m;for(i=0;i 5.typedef struct {elemtype *elem; //加工時(shí)間 elemtype *num; //序號(hào) elemtype *welem; //完成時(shí)間 elemtype *jelem; //交貨期 elemtype *celem; //差值 int length; //長(zhǎng)度 int listsize; //分配量 int incrementsize;//增補(bǔ)量 }sqlist;void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.celem=new elemtype[SIZE]; a.jelem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 {int i,j,t,m,p;for(i=0;i a.welem[i]=a.elem[i];else {a.welem[i]=a.elem[i]+a.welem[i-1];} a.celem[i]=a.jelem[i]-a.welem[i];cout< 數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)任務(wù)書三：二叉樹鏈?zhǔn)酱鎯?chǔ)的基本操作 1、創(chuàng)建二叉樹 a)熟悉使用教材的先序創(chuàng)建二叉樹的方法 b)編寫一個(gè)算法，實(shí)現(xiàn)在已知二叉樹的先序序列和中序序列的情況下創(chuàng)建二叉樹。 c)如果已知二叉樹的順序表示形式，將其轉(zhuǎn)換為二叉樹的鏈?zhǔn)酱鎯?chǔ)方式。 2、二叉樹的遍歷 a)先序、中序和后序三種形式的鏈?zhǔn)酱鎯?chǔ)遞歸式算法 b)先序、中序和后序三種形式的鏈?zhǔn)酱鎯?chǔ)非遞歸式算法 c)層次遍歷的算法。 3、二叉樹一些基本操作 a)計(jì)算二叉樹的深度； b)計(jì)算二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù) c)計(jì)算二叉樹的單支節(jié)點(diǎn)的個(gè)數(shù) d)計(jì)算二叉樹的雙支節(jié)點(diǎn)的個(gè)數(shù) 4、編寫一個(gè)主函數(shù)能夠測(cè)試你所設(shè)計(jì)的算法。 主函數(shù)調(diào)用教材創(chuàng)建二叉樹的創(chuàng)建教材圖7-10的二叉樹鏈?zhǔn)酱鎯?chǔ)方式。 {p=st.a[st.top]; st.top--; cout< data; while(p->right!=NULL) {st.top++; st.a[st.top]=p->right; q=p->right; while(q->left!=NULL) {st.top++; st.a[st.top]=q->left; q=q->left; } 代碼：#include //二叉樹結(jié)點(diǎn)的結(jié)構(gòu)體表示形式 {char data;struct node* left,*right;}BTree;typedef BTree *Tree;typedef struct stackelem //棧的結(jié)構(gòu)體表示形式 {BTree* a[MAXSIZE];int top;}Stack;void CreateBiTree_Rec(Tree &T)//先序創(chuàng)建二叉樹的方法 {char ch;cin>>ch;if(ch=='#') T=NULL;else {T= new BTree; T->data=ch; CreateBiTree_Rec(T->left); CreateBiTree_Rec(T->right);}} void Preorder(Tree t)//前序遍歷，遞歸的方法 {if(NULL!=t){cout< Preorder(t->left); Preorder(t->right);}} void Preorder2(Tree t)//前序遍歷的非遞歸實(shí)現(xiàn) {Tree p;Stack st;st.top=-1;if(NULL==t){return;} else {st.top++; st.a[st.top]=t; while(st.top!=-1) {p=st.a[st.top]; st.top--; cout< data; if(p->right!=NULL) {st.top++; st.a[st.top]=p->right;} if(p->left!=NULL) {st.top++; st.a[st.top]=p->left;} void Inorder(Tree t)//中序遍歷，遞歸實(shí)現(xiàn) {if(NULL!=t){Inorder(t->left); cout< Inorder(t->right);}} void Inorder2(Tree t)//中序遍歷，非遞歸實(shí)現(xiàn) {Tree p,q;Stack st;st.top=-1;if(NULL==t){return;} else {while(t!=NULL) {st.top++; st.a[st.top]=t; t=t->left; }}} 20 } while(st.top!=-1)break; } }}} void Postorder(Tree t)//后序遍歷，遞歸實(shí)現(xiàn) {if(t!=NULL){Postorder(t->left); Postorder(t->right); cout< {st.top++; st.a[st.top]=t; t=t->left; } m=NULL; flag=1; while(st.top!=-1 && flag) {t=st.a[st.top]; if(t->right==m) {cout< st.top--; m=t;} else {t=t->right; flag=0; }}} while(st.top!=-1);} int Height(Tree t)//求二叉樹的高度，遞歸實(shí)現(xiàn){int depth1,depth2;if(!t){ return 0;} else {depth1=Height(t->left); depth2=Height(t->right); if(depth1>depth2) {return(depth1+1); } else {return(depth2+1); }}} int leafs_rec(Tree t) //葉子結(jié)點(diǎn) {int l,r;if(t==NULL) return 0;else if((t->left==NULL)&&(t->right==NULL)) return 1;else {l=leafs_rec(t->left); r=leafs_rec(t->right); return(l+r);}} int danzhi(Tree t)//單只 {if(t==NULL) return 0;else if((t->left==NULL)&&(t->right!=NULL)) d++;else if((t->left!=NULL)&&(t->right==NULL)) d++;danzhi(t->left);danzhi(t->right);return(d);} int shuangzhi(Tree t) //雙只 {if(t==NULL) return 0;else if((t->left!=NULL)&&(t->right!=NULL)) l++;shuangzhi(t->left);shuangzhi(t->right);return(l);} void TraversalOfLevel(Tree t)//層次遍歷二叉樹 { Tree p,q[100];int f=0,r=0;if(t!=NULL) {p=t; q[r]=t; r++;} while(f!=r){p=q[f];f++; cout< data; if(p->left!=NULL) {q[r]=p->left; r++; } if(p->right!=NULL) {q[r]=p->right; r++;} }} void CreateBiTree_XZ(Tree &T,char a[],int la,int ra,char b[],int lb,int rb)//知先序、中序求二叉樹 {int i,lla,lra,llb,lrb,rla,rra,rlb,rrb;if(la>ra) T=NULL;else {T=new BTree; T->data=a[la]; for(i=lb;i<=rb;i++) {if(b[i]==a[la]) break;} lla=la+1; lra=lla+i-lb-1; rla=lra+1; rra=ra;llb=lb; lrb=i-1; rlb=i+1; rrb=rb; CreateBiTree_XZ(T->left,a,lla,lra,b,llb,lrb); CreateBiTree_XZ(T->right,a,rla,rra,b,rlb,rrb);}} void CreateBiTree_SX(Tree &T,char S[],int pos,int n)//二叉樹的順序表示形式，將其轉(zhuǎn)換為二叉樹的鏈?zhǔn)酱鎯?chǔ)方式 {int i;if(S[pos]=='#') T=NULL;else {T=new BTree; T->data=S[pos]; if((i=2*pos+1)<=n) CreateBiTree_SX(T->left,S,i,n); else T->left=NULL; if((i=2*pos+2)<=n) CreateBiTree_SX(T->right,S,i,n); else T->right=NULL;}} void main(){int n,i;char a[30],b[30],c[30];Tree s;Tree m;cout<<“請(qǐng)輸入先序:”;CreateBiTree_Rec(m);cout< 數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)任務(wù)書四：圖的操作 1、建立圖的存儲(chǔ)結(jié)構(gòu) a)創(chuàng)建圖的鄰接矩陣表示方式 b)創(chuàng)建圖的鄰接表表示方式 c)實(shí)現(xiàn)兩種方式的互換 2、圖的遍歷 a)基于鄰接矩陣的深度和廣度遍歷 b)基于鄰接表的深度和廣度遍歷 3、最小生成樹，使用Prim算法實(shí)現(xiàn)從某一節(jié)點(diǎn)出發(fā)的圖的最小生成樹25 4、單源最短路徑，算法8-10 5、關(guān)鍵路徑算法。 1．代碼： typedef enum{DG,DN,UDG,UDN}GKind;typedef enum{FALSE,TRUE}Boolean;Boolean visited[max_v];typedef int VType;typedef int EType;typedef int qtype;typedef struct { qtype *elem;int front;int rear;int qsize;int insize;}squeue;typedef struct { VType vexs[max_v];EType edges[max_v][max_v];int vnum,ednum;GKind kind;}MGraph;typedef struct ENode { int advex;struct ENode *next;int weight;}ENode;typedef struct VNode { VType vex;ENode *first;}VNode,List[max_v];typedef struct { List ver;int vnum,ednum;int kind;}AGraph;int LocatV(MGraph g,VType x){ int k;k=-1;for(k=0;(k //鄰接矩陣 { int i,j,k,v1,v2,w;cout<<“請(qǐng)輸入頂點(diǎn)數(shù):”;cin>>g.vnum;cout<<“請(qǐng)輸入邊數(shù):”;cin>>g.ednum;cout<<“請(qǐng)輸入構(gòu)造頂點(diǎn)數(shù)組頂點(diǎn)值:”< g.edges[i][j]=infinity;cout<<“請(qǐng)輸入構(gòu)造鄰接矩陣:”< cin>>v1; cout<<“請(qǐng)輸入頂點(diǎn)V2:”; cin>>v2; cout<<“請(qǐng)輸入權(quán)值:”; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); while((i<0)||(i>(g.vnum-1))||(j<0)||(j>(g.vnum-1))) { cout<<“編號(hào)超出范圍，請(qǐng)重新輸入頂點(diǎn)及權(quán)值:”< cin>>v1; cin>>v2; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); g.edges[i][j]=w; g.edges[j][i]=g.edges[i][j];}} int LocatVA(AGraph g,VType x){ int k;k=-1;for(k=0;(k cout<<“編號(hào)超出范圍，請(qǐng)重新輸入:”< cin>>v1; cin>>v2; i=LocatVA(g,v1); j=LocatVA(g,v2);} p=new ENode;p->advex=j;p->next=g.ver[i].first;g.ver[i].first=p;}} void DFS(AGraph g,VType i){ ENode *p;VType w;visited[i]=TRUE;cout< DFS(g,w);}} void Draverse(AGraph g) //鄰接表深度遍歷 { int i;for(i=0;i DFS(g,i);} void MDFS(MGraph g,VType i){ VType p;visited[i]=TRUE;cout< MDFS(g,p);}} void Mraverse(MGraph g) //鄰接矩陣深度遍歷 { int i;for(i=0;i MDFS(g,i);} void InQueue(squeue &q) { q.elem=new qtype[SIZE];q.front=q.rear=0;q.qsize=SIZE;q.insize=IN;} void INsize(squeue &q) { qtype *a;int i;a=new qtype[q.qsize+q.insize];for(i=0;i { if(((q.rear+1)%q.qsize)==q.front)INsize(q);q.elem[q.rear]=e;q.rear=(q.rear+1)%q.qsize;} void Error(char *a) //錯(cuò) { cout< { qtype e;if(q.front==q.rear)Error(“循環(huán)隊(duì)列空!”);e=q.elem[q.front];q.front=(q.front+1)%q.qsize;return e;} void BFS(MGraph g) { int i,w,u;squeue q; //初始化 //擴(kuò)容 //入隊(duì) //出隊(duì) //鄰接矩陣廣度遍歷29 for(i=0;i cout< EnQueue(q,i); while(q.front!=q.rear) { u=DeQueue(q); for(w=0;w if(g.edges[u][w]&&(!visited[w])) { visited[w]=TRUE; cout< EnQueue(q,w);}}}} void MBFS(AGraph g) //鄰接表廣度遍歷 { int i,w,u;squeue q;ENode *p;for(i=0;i EnQueue(q,i); while(q.front!=q.rear) {u=DeQueue(q); cout< p=g.ver[u].first; while(p) {w=p->advex; if(visited[w]!=TRUE) { visited[w]=TRUE; EnQueue(q,w);} p=p->next;}}}}} void MatToList(MGraph l,AGraph &g)//此函數(shù)用于實(shí)現(xiàn)將鄰接矩陣轉(zhuǎn)換成鄰接表{ int i,j;ENode *p;g.vnum = l.vnum;for(i = 0;i g.ver[i].first = NULL; g.ver[i].vex=l.vexs[i];} for(i=0;i for(j = l.vnum-1;j>=0;j--) { if((l.edges[i][j]!= 0)&&(l.edges[i][j]!=100)){ p =(ENode*)malloc(sizeof(ENode)); p->advex = j; p->next= g.ver[i].first; g.ver[i].first= p;}}} void ListToMat(MGraph &g, AGraph l)//表轉(zhuǎn)矩陣 { int i,j;ENode *p;g.vnum=l.vnum;g.ednum=l.ednum;for(i = 0;i g.edges[i][j] = 0;for(i=0;i while(p){g.edges[i][p->advex] = 1; p=p->next;} }} void main(){ int j=0,i;MGraph g;AGraph h;ENode *p;CreatUDN_MG(g);cout<<“n此無向圖共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) { cout<<“<”< p=p->next; } } cout< Draverse(h);cout< MatToList(g,h);cout<<“n此無向圖共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) {cout<<“<”< p=p->next;} }} 2.代碼：#include struct edgeNode *link;//與之相連的端點(diǎn) }; //存儲(chǔ)節(jié)點(diǎn)信息 vexNode adjlist[MAX];//訪問標(biāo)志 bool visited[MAX];//lowcost[j]存儲(chǔ)從開始節(jié)點(diǎn)到節(jié)點(diǎn)j的最小花費(fèi) WeiType lowcost[MAX];//parent[j]表示節(jié)點(diǎn)j的前驅(qū)節(jié)點(diǎn) int parent[MAX];//建立鄰接表存儲(chǔ) void createGraph(vexNode *adjlist,const int n,const int e,const int v0){ edgeNode *p1,*p2;int i,v1,v2;WeiType weight;for(i=1;i<=n;i++){ cout<<“請(qǐng)輸入節(jié)點(diǎn)”< visited[i] = false;lowcost[i] = Infinity;parent[i] = v0;} for(i=1;i<=e;i++){ cout<<“請(qǐng)輸入邊”< p1->weight = weight;p1->info = adjlist[v1].info;p1->next = adjlist[v2].link;adjlist[v2].link = p1;p2->no = v2;p2->weight = weight;p2->info = adjlist[v2].info;p2->next = adjlist[v1].link;adjlist[v1].link = p2;}} void f(int n,int e,int v){ int i,j,k;edgeNode *p,*q;WeiType sum = 0,minCost;createGraph(adjlist,n,e,v);p = adjlist[v].link; visited[v] = true;while(p!=NULL){ lowcost[p->no] = p->weight;p = p->next;} for(i=1;i minCost = Infinity; int k; for(j=1;j<=n;j++) { if(minCost>lowcost[j]&&!visited[j]) { minCost = lowcost[j]; k = j; } } sum += minCost; visited[k] = true; q = adjlist[k].link; while(q!= NULL) { if(!visited[q->no]&&q->weight { lowcost[q->no] = q->weight; parent[q->no] = k; } q = q->next;} } cout<<“最小生成樹的邊集為：”< cout<<“(”< } } 7、評(píng)語(yǔ) 工作態(tài)度（認(rèn)真、一般、較差），工作量（飽滿、一般、不夠），每個(gè)任務(wù)能夠獨(dú)立（完成、基本完成、在輔導(dǎo)下完成），程序運(yùn)行結(jié)果（正確、基本正確、部分正確），實(shí)訓(xùn)報(bào)告格式（標(biāo)準(zhǔn)、一般）。創(chuàng)新意識(shí)（較強(qiáng)、一般、沒有），運(yùn)行所學(xué)知識(shí)解決實(shí)際問題的能力（強(qiáng)、一般、較差）。 ? 優(yōu)(100~90)：能夠熟練運(yùn)用開發(fā)工具，編程解決實(shí)際問題，創(chuàng)意新穎，功能實(shí)現(xiàn)完善。 ? 良(89~80)：能夠熟練運(yùn)用開發(fā)工具，編程解決實(shí)際問題，有一定創(chuàng)新，功能實(shí)現(xiàn)較好。 ? 中(79~70)：能夠較熟練使用開發(fā)工具，編程解決實(shí)際問題，獨(dú)立完成實(shí)訓(xùn)，功能實(shí)現(xiàn)一般。 ? 及格(69~60)：能夠運(yùn)用開發(fā)工具，在教師輔導(dǎo)下完成實(shí)訓(xùn)，實(shí)現(xiàn)部分功能。? 不及格(59~0)：編程解決實(shí)際問題的能力差，功能實(shí)現(xiàn)較差。 實(shí)訓(xùn)成績(jī)?yōu)椋?分 教師簽字： Harbin Institute of Technology at Weihai 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目： 院 系： 班 級(jí)： 學(xué) 號(hào)： 組 號(hào)： 設(shè) 計(jì) 者： 哈爾濱工業(yè)大學(xué)（威海）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱工業(yè)大學(xué)（威海）《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》報(bào)告 前 言 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的必修、主干課程之一，它旨在使讀者學(xué)會(huì)分析研究數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及相應(yīng)的運(yùn)算(操作)，把現(xiàn)實(shí)世界中的問題轉(zhuǎn)化為計(jì)算機(jī)內(nèi)部的表示和處理，這是一個(gè)良好的程序設(shè)計(jì)技能訓(xùn)練的過程。在整個(gè)教學(xué)或?qū)W習(xí)過程中，解題能力和技巧的訓(xùn)練是一個(gè)重要的環(huán)節(jié)。 本課題設(shè)計(jì)要求學(xué)生分組進(jìn)行（每組1-2人），自行選題，選題的思想是根據(jù)實(shí)際需要進(jìn)行調(diào)研，以組為單位提交課程設(shè)計(jì)任務(wù)書，給出所選項(xiàng)目的背景和意義，由導(dǎo)師確定選題的級(jí)別，主要是以實(shí)用性為主，開發(fā)一個(gè)具有實(shí)際價(jià)值的項(xiàng)目，經(jīng)過2周的課程設(shè)計(jì)后接受課程設(shè)計(jì)組老師的解題驗(yàn)收。 計(jì)算機(jī)科學(xué)與工程系 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 課程設(shè)計(jì)題目 迷宮 航班信息查詢系統(tǒng) 學(xué) 號(hào) 姓 名 班 級(jí) 專 業(yè) 網(wǎng)絡(luò)工程 完 成 時(shí) 間 2013-1-4 指 導(dǎo) 教 師 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮 題目一 1.設(shè)計(jì)內(nèi)容 1.1問題描述 求迷宮從入口到出口的所有路徑。1.2設(shè)計(jì)要求 1．迷宮中不能使用遞歸算法查找路徑。2．試探方向限定為上、下、左、右四個(gè)方向。3．迷宮采用隨機(jī)生成和手工生成兩種方式。4．生成從迷宮入口到出口的最短和最長(zhǎng)路徑。5．迷宮的入口和出口由鍵盤輸入。 1.3開發(fā)環(huán)境 Visual C++6.0的集成化環(huán)境 1.4研究思路 對(duì)這樣的矩形迷宮，可以用N*M的矩陣來描述，N和M分別代表迷宮的行數(shù)和列數(shù)。這樣，迷宮中的每一個(gè)位置都可以用行號(hào)和列號(hào)來指定。從入口到出口的路徑則是由一個(gè)位置構(gòu)成的，每個(gè)位置上都沒有障礙，且每個(gè)位置（第一個(gè)除外）都是前一個(gè)位置的東、南、西或北的鄰居。為了描述迷宮中位置（i,j）處有無障礙，規(guī)定：當(dāng)位置（i,j）處有一個(gè)障礙時(shí)，其值為1，否則為0。 經(jīng)分析，一個(gè)簡(jiǎn)單的求解方法是：從入口出發(fā)，沿某一方向進(jìn)行探索，若能走通，則繼續(xù)向前走；否則沿原路返回，換一方向再進(jìn)行搜索，直到所有可能的通路都探索到為止。即所謂的回溯法。 2.設(shè)計(jì)步驟 2.1 需求分析 （1）題目：迷宮的生成與路由。生成一個(gè)N*M（N行M列）的迷宮，0和 1-1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮 在該程序中，首先進(jìn)入的是菜單選擇，在菜單中有3種選擇，選1是手動(dòng)輸入迷宮函數(shù)；選2是隨機(jī)自動(dòng)生成迷宮；選3是退出程序。在手動(dòng)生成迷宮時(shí)，有兩種輸出方式，一是矩陣輸出，二是圖形輸出。在矩陣輸出時(shí)，直接將數(shù)組中的數(shù)進(jìn)行輸出，在圖形輸出時(shí)，則要判斷該點(diǎn)的情況，然后輸入迷宮的出入口，再調(diào)用mgpath（）函數(shù)進(jìn)行判斷是否存在路徑，如果存在則將路徑經(jīng)過的點(diǎn)進(jìn)行輸出，并且將經(jīng)過的點(diǎn)進(jìn)入到輔助數(shù)組中（輔助數(shù)組是輔助圖形界面的輸出），并且將輔助數(shù)組初始為1，輔助數(shù)組中點(diǎn)為路徑的重新賦值為0，然后根據(jù)情況輸出圖形界面。在自動(dòng)生成迷宮時(shí)，用到了c語(yǔ)言隨機(jī)函數(shù)，對(duì)于其它問題，和手動(dòng)情況基本相同。 2.3 詳細(xì)設(shè)計(jì)（1）主菜單偽代碼： while(flag1){ } {shuru();//輸入行列數(shù) printf(“手動(dòng)建立迷宮矩陣(0表示可通1表示障礙):n”);for(i=1;i<=m;i++) for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宮輸出 churukou();//迷宮出入口的輸入 x=Mazepath(mg);// 判斷路徑函數(shù) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮 和“class ‘maze’has an illegal zero-sized array”兩行錯(cuò)誤。雙擊錯(cuò)誤信息，找到出錯(cuò)的程序段，經(jīng)過查閱資料發(fā)現(xiàn)，在利用順序棧時(shí)，沒有定義順序棧的向量空間大小，導(dǎo)致程序出錯(cuò)。但不要對(duì)向量空間定義過大，否則會(huì)浪費(fèi)空間。 （2）算法的時(shí)空分析： 由于鏈棧實(shí)際上是運(yùn)算受限制的單鏈表。所以取棧頂元素運(yùn)算的算法、置空棧運(yùn)算的算法執(zhí)行時(shí)間與問題的規(guī)模無關(guān)，則該算法的時(shí)間復(fù)雜度為O(1)；而其入棧運(yùn)算的算法與出棧運(yùn)算的算法相當(dāng)于在鏈表的表尾進(jìn)行插入和刪除操作，不需要移動(dòng)元素，時(shí)間復(fù)雜度也為O（1）。建立迷宮矩陣的時(shí)間復(fù)雜度為O（x*y）。在查找路徑的過程中，最壞的情況下可能要考察每一個(gè)非障礙的位置。因此，查找路徑的時(shí)間復(fù)雜度應(yīng)為O（unblocked）。 鏈棧的入棧算法、出棧算法、取棧頂元素算法、置空棧算法執(zhí)行時(shí)所需要的空間都是用于存儲(chǔ)算法本身所用的指令、常數(shù)、變量，各個(gè)算法的空間性能均較好。只是對(duì)于存放順序棧的向量空間大小的定義很難把握好，如果定義過大，會(huì)造成不必要的空間浪費(fèi)。所以在定義時(shí)要慎重考慮。 3.用戶使用說明 運(yùn)行該程序，運(yùn)行的界面的會(huì)出現(xiàn)菜單界面，然后用戶可根據(jù)界面的提示進(jìn)行相應(yīng)的操作，生成迷宮的方式有兩種方式，手動(dòng)生成和自動(dòng)生成，手動(dòng)生成時(shí)、，用戶可根據(jù)自己的要求輸入迷宮的格式，還需輸入相應(yīng)的入出口，確認(rèn)程序就會(huì)生成相應(yīng)的路徑圖形；自動(dòng)生成只需輸入所需的行數(shù)和列數(shù)，就會(huì)生成迷宮，接下來的操作和手動(dòng)操作相同了。 圖數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮 圖1-2 圖1-3 退出 5.總結(jié)與心得體會(huì) 本次課程設(shè)計(jì)過程中由于掌握的知識(shí)不牢固，在編程序的過程中得到了同學(xué)的幫助和指導(dǎo)，在此表示感謝。課程設(shè)計(jì)的過程中，遇到了一些問題，大部分是課本中的知識(shí)掌握的不牢固，還有就是在以前學(xué)習(xí)C++的過程中相關(guān)的知識(shí)掌握的不夠全面。在以后的學(xué)習(xí)過程中，自己一定要把各種知識(shí)掌握牢固。 { } mg[i][j]=1;//初始化 矩陣,將最外圍置為1 printf(“n輸入迷宮入口：n”);scanf(“%d%d”,&x1,&y1);printf(“輸入迷宮出口：n”);scanf(“%d%d”,&x2,&y2); }mlink;mlink *stack;//定義一個(gè)棧 int m,n,x1,x2,y1,y2;//定義全局變量 } void showplay(int mg[][M+2])//迷宮輸出 { n“); for(i=1;i<=m;i++){ printf(”n“);for(j=1;j<=n;j++) printf(”%d “,mg[i][j]); int i,j; printf(”迷宮矩陣如下(0可通)：printf(“輸入行數(shù)：n”);scanf(“%d”,&m);printf(“輸入列數(shù)：n”);scanf(“%d”,&n);數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮 } } printf(“n迷宮圖形如下(白色for(i=1;i<=m;i++){ } printf(”n“);for(j=1;j<=n;j++){ } if(mg[i][j]==0)printf(” if(mg[i][j]==1)printf(“ if(mg[stack->row][stack->col+1]== p->next=stack; stack=p;{ p=(mlink 可通)：n”);0)//下面位置可通 *)malloc(sizeof(mlink)); p->row=stack->row;p->col=stack->col+1;□“);//為0的輸出□ ■”);//為1的輸出■ //入棧 mg[stack->row][stack->col]=1;//將 } else 訪問過的標(biāo)記為1 int Mazepath(int mg[][N+2]){ mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p; //將入口 mg[stack->row][stack->col]=1;/while((!(stack->row==NULL& if(mg[stack->row][stack->col-1]==0)//上面可通 //入棧 stack=p; p->next=stack; { p=(mlink *)malloc(sizeof(mlink)); *)malloc(sizeof(mlink)); p->row=stack->row;p->col=stack->col-1;放入堆棧 /標(biāo)志入口已訪問 &stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循環(huán)條件直到找到輸入的出口 { mg[stack->row][stack->col]=1;//將 訪問過的標(biāo)記為1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 迷宮 void tonglu()//將坐標(biāo)的頂點(diǎn)輸出 { 始化 printf(“(%d%3d)n”,q->row,q->col); 情況 else printf(“□”);//0的 } q=stack;{ } for(i=0;i for(j=0;j = while(q!=NULL)//循環(huán)條件 q=q->next;for(j=0;j 情況 } void create(int mg[][N+2])//創(chuàng)建和菜單 { int i,j,x,choice,flag1=1;chushi();while(flag1){ } printf(“n”);printf(“所有通道為（由下而q=stack;{ 上）：n”);while(q!=NULL)//循環(huán)條件 printf(“ ## printf(”# n“); *********選擇菜單********** #n”); printf(“ ## printf(”輸入選項(xiàng)：“);scanf(”%d“,&choice);switch(choice){ case 1://手動(dòng)建立迷宮 { shuru(); printf(”手動(dòng)建立for(i=1;i<=m;i++) n“); printf(”# 1-手動(dòng)生成迷 宮 2-自動(dòng)生成迷宮 3-退出 #n“);0;//將路徑中的點(diǎn)賦給輔助數(shù)組a 形的界面輸出 迷宮矩陣(0表示可通1表示障礙):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) 題目二 1.設(shè)計(jì)內(nèi)容 1.1問題描述 設(shè)計(jì)一個(gè)航班信息查詢系統(tǒng)，提供信息的管理和使用功能，管理包括更新、添加、刪除功能。 1.2設(shè)計(jì)要求 （1）原始信息存儲(chǔ)在文件中，記錄不少于50條。（2）用戶界面至少包括以下功能： ? 創(chuàng)建 ? 修改（插入、添加、刪除、更新）? 查詢 ? 瀏覽 ? 退出管理系統(tǒng)（3）航班信息包括： ? 航班號(hào)：字符序列，具體字符表達(dá)的意思上網(wǎng)查詢 ? 起點(diǎn)站和終點(diǎn)站：字符串 ? 班期：指一周中哪些天有航班 ? 起飛時(shí)間：可將時(shí)間定義成一個(gè)時(shí)、分組成的序列 ? 到達(dá)時(shí)間：可將時(shí)間定義成一個(gè)時(shí)、分組成的序列 ? 機(jī)型：字符序列，具體字符表達(dá)的意思上網(wǎng)查詢 ? 票價(jià)：整型數(shù)，具體值可上網(wǎng)查詢 （4）創(chuàng)建是指從文件中讀取數(shù)據(jù)，并存入所定義的順序表中。 （5）可按航班號(hào)、起點(diǎn)站、終點(diǎn)站、起飛時(shí)間、到達(dá)時(shí)間等進(jìn)行查詢。查詢時(shí)要用到順序查找、二分查找方法。輸出查詢結(jié)果時(shí)必須排序。 （6）可按航班號(hào)、起點(diǎn)站、起飛時(shí)間、票價(jià)進(jìn)行刪除和更新操作，刪除的記錄存入另外的文件中，作為日志文件保存。 （7）作插入操作前，先對(duì)信息按起點(diǎn)站進(jìn)行排序。新記錄插入為起點(diǎn)站相同的最后一條記錄。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) typedef struct node { Time rh;Time lv;}Pnode;（2）飛機(jī)結(jié)構(gòu)體： struct Plane { };（3）靜態(tài)鏈表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 詳細(xì)設(shè)計(jì)（1）主函數(shù)： do{printf(“* * * * * * * * * * * * * 航班查詢系統(tǒng)* * * * * * * * * * * * *n”); printf(“* 1.創(chuàng)建 2.修改 3.查詢 4.瀏覽 5.表長(zhǎng) 6.文件 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”); scanf(“%d”,&opt);switch(opt){ case 1:Initlist(L);break; case 2:handle(L);break; case 3:search(L);break; case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) } }while(opt!=0);} （4）文件操作： void File(Sqlist &L){ int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“* *n”); printf(“* 1.保存信息到文件 2.從文件讀取信息 0 退出 *n”); printf(“* *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“請(qǐng)輸入選項(xiàng)n”); scanf(“%d”,&ch); switch(ch) { case 1:SaveList(L);break; } }while(ch!=0);case 2:ReadList(L);break; case 0:printf(“退出！n”);break;} （5）瀏覽信息：就是循環(huán)使用輸出函數(shù)，在此就不必多說了 2.4 調(diào)試分析 （1）在課設(shè)過程中，遇到問題時(shí)，通過與同學(xué)、老師交流，在圖書館查閱資料，使問題得以解決。 （2）算法中有許多不是很優(yōu)化的地方。3.用戶使用說明 程序運(yùn)行后用戶根據(jù)提示輸入要進(jìn)行的操作選項(xiàng)（應(yīng)先選擇創(chuàng)建選項(xiàng)，這樣可以直接讀取保存好的文件），然后選擇要進(jìn)行的操作選項(xiàng)。由于主菜單中有修改、查詢和瀏覽項(xiàng)目，每個(gè)項(xiàng)目又有各自的子菜單，所以在進(jìn)行管理和使用時(shí)要注意輸入的元素是否正確，需按照提示輸入。輸入操作元素時(shí)，元素之間以空格隔開。程序?qū)摧斎氲牟僮髟卣业较鄳?yīng)的算法，然后進(jìn)行處理，然后將結(jié)果打 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) 圖2-2 查詢信息 圖2-3插入 圖2-4刪除 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) 時(shí)就需要重新寫出一個(gè)子函數(shù)，哪怕這個(gè)子函數(shù)就是在原有的一個(gè)子函數(shù)的基礎(chǔ)上改那么一丁點(diǎn)的地方，例如航班信息查詢系統(tǒng)中的查詢函數(shù)，其實(shí)每個(gè)子函數(shù)只是改了一下關(guān)鍵碼而已。 6.附錄 #include { } void search_key(Sqlist L)//按航班號(hào)查找 { 號(hào)：“); Time rh;Time lv; scanf(”%s“,n);int i; printf(”此航班的航班號(hào)，起點(diǎn)char n[20]; printf(“請(qǐng)輸入要查找的航班 printf(”%dn“,L.length);//表長(zhǎng) }Time;typedef struct node { }Pnode;struct Plane { };typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price; 終點(diǎn)，班期，起飛時(shí)間，到達(dá)時(shí)間，票價(jià)：n”); if(strcmp(L.plane[i].key,n)==0) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length; plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) printf(“此航班的航班號(hào)，起點(diǎn) ted，{ 終點(diǎn)，班期，起飛時(shí)間，到達(dá)時(shí)間，票價(jià)：n”); if(L.plane[i].lv.hour<=hour) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search(Sqlist L){ int i;do { printf(“* * * * * * * * * * * } } printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search_rh(Sqlist L){ int hour;printf(”請(qǐng)輸入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班號(hào)，起點(diǎn) } } [i].price); * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); printf(“* 1.航班號(hào)查詢 2.起點(diǎn)終點(diǎn)查詢 3.班期查詢 4.起飛時(shí)間查詢 5.到達(dá)時(shí)間查詢 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); scanf(“%d”,&i); switch(i) { case 晚時(shí)間：“);終點(diǎn)，班期，起飛時(shí)間，到達(dá)時(shí)間，票價(jià)：n”); if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){ 1:search_key(L);break; 2數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) n“); } else { } printf(”查找不成功。 i--;if(i==0) { char c[20]; printf(“輸入修改后的scanf(”%s“,c); 內(nèi)容：”); strcpy(L.plane[i].sche,c); printf(“修改成功！n”);}break;{ int a,b; printf(“輸入修改后的int opt;printf(”選擇修改對(duì)象：“);scanf(”%d“,&opt);switch(opt){ case 1: printf(”修改成功！n“);printf(”修改成功！n“);{ char a[10];printf(”輸入修改后的scanf(“%s”,a); case 4: 內(nèi)容：“); char b[20];printf(”請(qǐng)輸入修改后scanf(“%s”,b); scanf(“%d:%d”,&a,&b); L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班號(hào)：“); }break;{ int a,b; printf(”輸入修改后的strcpy(L.plane[i].key,a);}break;{ case 5: case 2: 內(nèi)容：“); scanf(”%d:%d“,&a,&b); L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的內(nèi)容：”);strcpy(L.plane[i].sted,b);}break; }break;{ int a; case 6: case 3: 4數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) *n“); printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“); printf(”請(qǐng)輸入選項(xiàng)n“); scanf(”%d“,&ch); switch(ch) { case 1:SaveList(L);break;case 2:ReadList(L);break; L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane [i].rh.hour,&L.plane[i].rh.min,&L.pl } void delet_Sq1(Sqlist &L){ char n[10];int i,j; printf(”請(qǐng)輸入您要?jiǎng)h除的航scanf(“%s”,n);if(L.length==0){ printf(“沒有選項(xiàng)！n”);for(i=0;i L.length++; ane[i].price); case 0:printf(“退出！n”);break; } void Initlist(Sqlist &L)//插入存儲(chǔ) { “); 容：”);價(jià)n“); scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i 班期 起飛時(shí)間 到達(dá)時(shí)間 票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”請(qǐng)輸入順序表中的內(nèi) int i,n;printf(“輸入表中航班的數(shù)量： } }while(ch!=0); 班號(hào)：”); if(strcmp(L.plane[i].key,n)==0) { printf(“所刪除的班機(jī)*)malloc((n+10000)*sizeof(Plane));的信息：n”); printf(“n航班號(hào) 起點(diǎn)終點(diǎn) printf(”%s %s %s %d:%d %d:% d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 6數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) n”);} printf(“無法打開文件！} }while(opt!=0); void insert_Sq(Sqlist &L){ 數(shù)量 價(jià)n”); for(i=0;i printf(“* * * * * * * * * * * scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[ { int a=get_Sq(L); printf(”請(qǐng)輸入要添加班機(jī)的scanf(“%d”,&n); printf(“請(qǐng)輸入要添加的班機(jī)printf(”n航班號(hào) 起點(diǎn)終點(diǎn) int i,n; //n表示添加的fprintf(fp,“航班號(hào)：%sn起點(diǎn)站：%s 終點(diǎn)站：%sn班期：%dn起飛時(shí)間：%d:%d 到達(dá)時(shí)間：%d:%dn價(jià)格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi n“);} void delet_Sq(Sqlist &L){ int opt;do { fclose(fp);printf(”保存刪除的信息成功。n,p.rh.hour,p.rh.min,p.price); 數(shù)量：“); 信息：n”); 班期 起飛時(shí)間 到達(dá)時(shí)間 票* * * * * * * * * *n“); printf(”* 1.航班號(hào)刪除 printf(“* * * * * * * * * * printf(”輸入你的選擇：“);2.路線刪除 0.退出 *n”);* * * * * * * * * * *n“); scanf(”%d“,&opt); switch(opt){ case 1:delet_Sq1(L);break; case 2:delet_Sq2(L);break; case 0:printf(”退出。} L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan e[L.length].rh.min,&L.plane[L.length].price); } void handle(Sqlist &L){ } L.length++; n");break;第二篇：南航計(jì)算機(jī)軟件數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)踐報(bào)告
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報(bào)告
第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 封面
第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
點(diǎn)擊咨詢 