第一篇：數(shù)據(jù)結(jié)構(gòu)大型實驗報告-銀行系統(tǒng)模擬
數(shù)據(jù)結(jié)構(gòu)大型實驗報告
軟工1102班 201126630230 周云閣
問題描述...........................................................................................................................................1 類結(jié)構(gòu)..............................................................................................................................................1 模擬算法說明...................................................................................................................................2 問題分析...........................................................................................................................................4 展望和收獲.......................................................................................................................................5
問題描述
②銀行系統(tǒng)模擬
【問題描述】假設銀行有四個服務窗口，初始每個窗口都可以提供服務；模擬開始后，每個窗口都能給出最早空閑時間（即最早可以提供服務的時間）；當顧客到達后，總可以看到每個窗口標出的最早可以提供服務的時間，由此來選擇窗口，其中，顧客按照一定的頻率到達;到達后系統(tǒng)隨機產(chǎn)生服務時間，同時產(chǎn)生下一個到達事件的時間。當顧客離開窗口時，該窗口為空閑，即可以為下一個等待顧客提供服務。所有到達事件和離開事件都被插入優(yōu)先隊列。銀行系統(tǒng)模擬中的關(guān)鍵部分為客戶事件，包括到達事件和離開事件，所有事件都被加上時間戳，放到優(yōu)先隊列中，隊列中優(yōu)先級最高的事件就是時間戳最早的事件。銀行模擬中用隨機數(shù)來決定下個顧客何時到達及當前顧客所需的服務時間，它可保證事件在某一范圍內(nèi)等概率發(fā)生。如果，當前到達事件發(fā)生在Ｔ時刻，下一個到達事件將發(fā)生在范圍T+arrivalLow和T+arrivelHigh之間。而每個顧客的服務事件在范圍ServiceLow和ServiceHigh之間。到達/離開事件數(shù)據(jù)均應包括：時間、事件類型、顧客號、服務窗口、等待時間、服務時間等。試編寫程序模擬銀行系統(tǒng)的運行。
類結(jié)構(gòu)
1.兩個自定義的優(yōu)先隊列；
WIndowsPriorityQueues類，用單鏈表實現(xiàn)的優(yōu)先隊列，用于存放窗口對象，在隊列里的 優(yōu)先權(quán)參考 窗口的悠閑程度，即time屬性，time越小，悠閑程度越大，則越在鏈表的最 前面。取出的時候，執(zhí)行g(shù)et()方法，取出表頭，即優(yōu)先權(quán)最高的對象。
EventPriorityQueues類，向量實現(xiàn)，用以存放生成的顧客事件對象，優(yōu)先權(quán)是顧客事件 生成順序，顧客越早生成的，就排在向量的前面。顧客事件對象就按線性順序排列在這 個隊列中
模擬算法說明
(手工圖略粗糙)
總體是來說，以事件為主，時間由事件驅(qū)動向前進。以此圖為例，假設A,B,C,D四個窗口的起始時間分別為 0 1 2 3，然后由A先開始。systemTime，時間軸直接跳到開始處理的時刻 即A 的 0 時刻。
2.然后A接到顧客，A的0 時刻 加上 顧客的服務時間2，說明A將在2時刻完成處理。3..此時，時間軸 加上 下一個顧客的到達時間 3，那么時間軸(systemTime)就跳到3時刻。4.明顯，當時間軸到3時，A已經(jīng)處理完畢，則彈出。則在 3時刻，A仍為空閑的。5.但事實上，在時刻3，是B 接待顧客，因為B的時刻較小，雖然此時所有的窗口都為空閑狀態(tài)，但由于默認的處理效率一樣，沒有區(qū)別，但如果要考慮不同窗口的效率話，那么在只要在優(yōu)先隊列再增加優(yōu)先級的參考項即可。
6.那么由此循環(huán)向前進，如果遇到所有的窗口都是處于處理狀態(tài)。那么只要把時刻最小的窗口彈出，且時間軸(systetTime)跳到那個時刻即可。當然這當中略有瑕疵要處理。
1.顧客的生成問題 及解決方法
按照正常的流程來說，應該是先生成第一位顧客，然后程序就可以開始了，然后是那邊窗口一邊處理，一邊生成顧客，而實際上是，c++本身貌似沒有多線程的機制，所以要實現(xiàn)這種方法，就要c++程序去調(diào)用windows系統(tǒng)的接口，借助一個windows.h的文件，然后在該進程下，開辟一個子線程。網(wǎng)上教程都大概這個樣子，但實際操作起來的話，include windows.h文件的時候，卻會報類似“找不到該文件“的錯誤。各種折騰之后，無奈就采取了第二種解決方法。根據(jù)四個窗口最大化的服務時間的總和ST，在不考慮顧客到達的間隙的情況下，批量生產(chǎn)顧客的信息，存入隊列中，直至所有顧客的服務時間總和大于ST.2.對事件機制的理解
在這個模擬中，并不是很明顯的顯示各種事件的運作。圍繞整個模擬，基本是以窗口的運作為核心，顧客是窗口的附屬，然后窗口和顧客的結(jié)合或分離，才是對應的到達或離開事件。所以以事件機制來解釋的話，窗口在等待隊列中準備，顧客在顧客隊列待續(xù)，然后各取出優(yōu)先級最高的，窗口的時間加上顧客的服務時間，然后把窗口壓入處理隊列中，這就是到達事件，在處理好的時候彈出。而處理好的標志就是窗口的時間小于systemTime，說明在下一位顧客到達時，該窗口已經(jīng)處理好了，可以彈出，此為離開事件，該則將該窗口壓入等待隊列，如果大于，則等到下一次ystemTime，再判斷，以此重復，3.模擬算法的各種調(diào)整
a.剛開始的時候，算法的實現(xiàn)就是簡單的最高優(yōu)先級窗口的時間，加成最高優(yōu)先級顧客的服務時間和等待時間，然后發(fā)現(xiàn)這與實際情況實在相差太大，故不得不拋棄。b.然后換了另外一種，.就是先判斷一下，如果服務時間大于等待時間，則最高優(yōu)先級的窗口不增加顧客等待時間，只加顧客的服務時間，然后其它窗口增加等待時間，這一開始在四個窗口的起始服務時間相同的情況下確實行得同，可是后來發(fā)現(xiàn)當四個窗口的起始時間不一樣的時候，就發(fā)現(xiàn)出問題了。c.所以就發(fā)現(xiàn)需要一個變量來客觀的變量，像systemTime，來告訴窗口現(xiàn)在進行到什么時候了，該不該加等待時間，再經(jīng)過調(diào)整之后就是現(xiàn)在的算法了
4.模擬算法的缺陷
當連續(xù)的，顧客的處理大大于其等待時間時，也就是說，此時四個窗口都會是處于處理狀態(tài)，那么下一個顧客即使到達了，仍需等待最先處理完窗口的彈出才行，那么這一期間內(nèi)，顧客仍會陸續(xù)到達，此時把已經(jīng)到達的等待時間應該變成0才是正確的，可是實際上這么做的時候，總之沒發(fā)生什么好事，程序崩潰了。
展望和收獲
簡單的收獲1：想得總比做得簡單。本來我想要完成這道題目，只要事件類來一個，隊列類來一個，然后一個main函數(shù)，這三個攪一攪就能搞定的事。可實際上，真正動手寫時，就發(fā)現(xiàn)了很多，在空想階段忽略的細節(jié)和問題。比如一個簡單向量下標越界的問題，鏈表尾部為空的問題等不大，但卻很惱人的錯誤。而整個大型實驗所花費的時間大部分都在排除各種不大不小的錯誤上.。細節(jié)很重要、簡單的收獲2：發(fā)現(xiàn)用流程結(jié)構(gòu)圖可以更加直觀明白，把大概的脈絡展現(xiàn)出來。但實際上流程圖真心不好畫，比如本篇的這張消耗大概3~5小時，流程圖總要隨著代碼而改變。
改進：一切為了模擬更接近實際，實際上有些地方因為一開始大致模型以及定下來了，后面改起來就比較麻煩，雖然可能只是看起來麻煩。但去改動它就會讓人恨難受，故而被我主動屏蔽了。
第二篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
注意：實驗結(jié)束后提交一份實驗報告電子文檔
電子文檔命名為“學號+姓名”，如：E01214058宋思怡
《數(shù)據(jù)結(jié)構(gòu)》實驗報告
（一）學號：姓名：專業(yè)年級：
實驗名稱：線性表
實驗日期：2014年4月14日
實驗目的：
1、熟悉線性表的定義及其順序和鏈式存儲結(jié)構(gòu)；
2、熟練掌握線性表在順序存儲結(jié)構(gòu)上實現(xiàn)基本操作的方法；
3、熟練掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表基本操作的方法；
4、掌握用 C/C++語言調(diào)試程序的基本方法。
實驗內(nèi)容：
一、編寫程序?qū)崿F(xiàn)順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：
（1）初始化順序表L；
（2）依次在L尾部插入元素-1,21,13,24,8；
（3）輸出順序表L；
（4）輸出順序表L長度；
（5）判斷順序表L是否為空；
（6）輸出順序表L的第3個元素；
（7）輸出元素24的位置；
（8）在L的第4個元素前插入元素0；
（9）輸出順序表L；
（10）刪除L的第5個元素；
（11）輸出順序表L。
源代碼
調(diào)試分析（給出運行結(jié)果界面）
二、編寫程序?qū)崿F(xiàn)單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：
????
????
小結(jié)或討論:
（1）實驗中遇到的問題和解決方法
（2）實驗中沒有解決的問題
（3）體會和提高
第三篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
南京信息工程大學實驗（實習）報告
實驗（實習）名稱數(shù)據(jù)結(jié)構(gòu)實驗（實習）日期 2011-11-2得分指導教師周素萍
系公共管理系專業(yè)信息管理與信息系統(tǒng)年級10級班次1姓名常玲學號2010230700
3實驗一順序表的基本操作及C語言實現(xiàn)
【實驗目的】
1、順序表的基本操作及 C 語言實現(xiàn)
【實驗要求】
1、用 C 語言建立自己的線性表結(jié)構(gòu)的程序庫，實現(xiàn)順序表的基本操作。
2、對線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個集合的并的結(jié)果存儲在一個新的線性表集合中，并輸出。
【實驗內(nèi)容】
1、根據(jù)教材定義的順序表機構(gòu)，用 C 語言實現(xiàn)順序表結(jié)構(gòu)的創(chuàng)建、插入、刪除、查找等操作；
2、利用上述順序表操作實現(xiàn)如下程序：建立兩個順序表表示的集合（集合中無重
復的元素），并求這樣的兩個集合的并。
【實驗結(jié)果】
[實驗數(shù)據(jù)、結(jié)果、遇到的問題及解決]
一． Status InsertOrderList(SqList &va,ElemType x)
{
}
二． Status DeleteK(SqList &a,int i,int k)
{//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的編號從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 將合并逆置后的結(jié)果放在C表中，并刪除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅(qū)指針 // 保存pb的前驅(qū)指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當前最小結(jié)點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結(jié)點插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲在數(shù)組中，元素之間的關(guān)系直接通過相鄰元素的位置來表達。 優(yōu)點：簡單，數(shù)據(jù)元素的提取速度快； 缺點：（1）靜態(tài)存儲，無法預知問題規(guī)模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n） 求兩個集合的并集 該算法是求兩個集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數(shù)集合中得到并集。 數(shù)據(jù)結(jié)構(gòu)實驗報告 一． 題目要求 1）編程實現(xiàn)二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷； 3）每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對于前三個題目要求，我們用一個程序?qū)崿F(xiàn)代碼如下 #include typedefintElemType; //數(shù)據(jù)類型 typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//創(chuàng)建二叉樹函數(shù) BiTreebst=NULL;inti=0;while(i //數(shù)據(jù)域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子樹為空重接它的左子樹 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子樹空則重新接它的右子樹 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被刪除結(jié)點的前驅(qū) if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數(shù)，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函數(shù) printf(“ ---------------------二叉排序樹的實現(xiàn)-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節(jié)點個數(shù):”);scanf(“%d”,&num);printf(“依次輸入這些整數(shù)（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創(chuàng)建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示輸入操作符************************:”);printf(“n”);printf(“ 1:插入節(jié)點 2:刪除節(jié)點 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節(jié)點:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“樹狀圖為:n”); printtree(bst,layer); break; case 2: } printf(“輸入要刪除的節(jié)點”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst); printf(“后序遍歷:n”); PostOrderNoRec(bst); printf(“樹狀圖為:n”); printtree(bst,layer); break;case 5: printf(“程序執(zhí)行完畢!”); return 0;} goto loop;} return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結(jié)構(gòu)變?yōu)?typedefintElemType; //數(shù)據(jù)類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數(shù)據(jù)域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數(shù)不是key,而是另外三個 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含參函數(shù)也類似 即可完成50個信息存儲 用數(shù)組存儲50個信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學生管理系統(tǒng)”< cout<<“該學號信息已經(jīng)存在，添加失敗”< break;} cout<<“重新輸入添加的學號”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“謝謝使用”< 二叉排序樹儲存數(shù)據(jù)界面（儲存學生信息略） 創(chuàng)建二叉樹： 插入節(jié)點： 刪除節(jié)點： 非遞歸遍歷： 退出： 數(shù)組儲存學生信息界面 分析查找效率： 因為二叉樹查找要創(chuàng)建二叉樹，而數(shù)組查找只創(chuàng)建一個數(shù)組，二叉樹的創(chuàng)建時間比較長，所以對于數(shù)據(jù)量較少的情況下數(shù)組的查找效率比較高。但當數(shù)據(jù)量增加時，二叉樹的查找優(yōu)勢就顯現(xiàn)出來。所以數(shù)據(jù)量越大的時候，二叉樹的查找效率越高。 四． 總結(jié)與改進 這個實驗工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進。 一開始打算用棧實現(xiàn)非遞歸，但是根據(jù)書里面的偽代碼發(fā)現(xiàn)部分是在C++編譯器里運行不了的（即使補充了頭文件和數(shù)據(jù)的定義），所以之后參考了網(wǎng)上的數(shù)組非遞歸，發(fā)現(xiàn)其功能和棧相似。 遞歸遍歷的實現(xiàn)比非遞歸的遍歷真的簡單很多。 開始時只看到前三問，所以沒有寫到儲存學生數(shù)據(jù)的代碼，里面還可以用clock（）函數(shù)加一個計算查找所要數(shù)據(jù)時間的代碼，讓二叉樹查找與數(shù)組查找到效率比較更加直觀。 實驗報告4 排序 一、實驗目的 1、掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。 2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用。 3、了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時間復雜度的分析方法。 二、實驗要求及內(nèi)容 要求編寫的程序所能實現(xiàn)的功能包括： 1、從鍵盤輸入要排序的一組元素的總個數(shù) 2、從鍵盤依次輸入要排序的元素值 3、對輸入的元素進行快速排序 4、對輸入的元素進行折半插入排序 三、實驗代碼及相關(guān)注釋 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的結(jié)構(gòu)體 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的結(jié)構(gòu)體 int Partition(SqList &L, int low, int high) //1 尋找基準 { L.r[0]=L.r[low];//子表的第一個記錄作基準對象 int pivotkey = L.r[low].key;//基準對象關(guān)鍵字 while(low while(low L.r[low] = L.r[high];//小于基準對象的移到區(qū)間的左側(cè) while(low L.r[high] = L.r[low];//大于基準對象的移到區(qū)間的右側(cè) } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列l(wèi)ow-high中遞歸地進行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //尋找基準 QuickSort(L, low, pivotloc-1);//對左序列同樣遞歸處理 QuickSort(L, pivotloc+1, high);//對右序列同樣遞歸處理 } } Sequenlist *Sqlset() //2 輸入要折半插入排序的一組元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“請輸入要排序的所有元素的總個數(shù)：”; cin>>i; cout< cout<<“請依次輸入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入點在前半?yún)^(qū) else low=mid+1;//插入點在后半?yún)^(qū) } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“請選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“請輸入要排序的所有元素的總個數(shù)：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后為：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函數(shù)功能說明 1、Sequenlist *Sqlset() 輸入要折半插入排序的一組元素 2、int Partition(SqList &L, int low, int high) 尋找快速排序的基準 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序運行結(jié)果 下圖僅為分別排序一次，可多次排序，后面有相關(guān)截圖： 六、實驗中遇到的問題、解決及體會 1、起初編寫快速排序的程序時，我是完全按照老師PPT上的算法敲上去的，然后建立了一個SqList的結(jié)構(gòu)體，調(diào)試運行時出現(xiàn)錯誤，仔細查看才意識到Partition函數(shù)中L中應該包含元素key，而我建立結(jié)構(gòu)體時沒有注意，然后我將key這個元素補充進去，繼續(xù)調(diào)試，又出現(xiàn)錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經(jīng)寫了函數(shù)定義，為什么會這樣，當我又回過頭來閱讀程序時，我發(fā)現(xiàn)QuickSort函數(shù)中調(diào)用了Partition函數(shù)，但是我的Partition函數(shù)的定義在QuickSort函數(shù)的后面，于是我將Partition函數(shù)放到了QuickSort函數(shù)的前面，再次調(diào)試運行，就可以正常運行，得出結(jié)果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。 運行程序錯誤截圖： 2、本來我是編寫了兩個程序，分別實現(xiàn)快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現(xiàn)不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續(xù)思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環(huán)到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現(xiàn)所需功能的前提下，多想問題，看是否能使程序更加實用簡便。 修改程序前兩個運行結(jié)果截圖 （兩個程序，調(diào)試運行兩次，每次只能進行一次排序） 1、快速排序程序運行結(jié)果截圖： 2、折半插入排序程序結(jié)果截圖： 程序重要模塊修改截圖： 修改程序后運行截圖： （一個程序，調(diào)試運行一次，可多次進行不同序列的不同排序）第四篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
第五篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
點擊咨詢 