第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-查找排序
查找及排序算法實現(xiàn)
一、實驗?zāi)康?/p>
1、熟練掌握二叉排序樹查找算法及C語言描述。
2、熟練掌握折半查找算法及C語言描述。
3、熟練掌握簡單選擇排序算法及C語言描述。
4、熟練掌握簡單插入排序算法及C語言描述。
5、熟練掌握冒泡（起泡）排序算法及C語言描述。
6、了解各種查找及排序算法的優(yōu)缺點、實用性及應(yīng)用。
7、將理論與實際相結(jié)合，切實提高自己的邏輯能力和動手能力。
二、設(shè)計內(nèi)容
1.折半查找算法
折半查找算法的思路：
初始狀態(tài)：假設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的下界、上界和中點,key為給定值，初始時，令low=0,high=n-1,mid=(low+high)/2 讓key與mid指向的記錄比較
若key==r[mid].key，查找成功,算法結(jié)束；若key
起泡排序的思路：
首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較【第二個記錄和第三個記錄】的關(guān)鍵字。以此類推，直至第n-1個記錄和第n個記錄的關(guān)鍵字進行過比較為止。上述過程稱做第一趟起泡排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個記錄的位置上，然后進行第二趟起泡排序，對前n-1個記錄進行同樣操作，其結(jié)果是使關(guān)鍵字次大的記錄被安置到第n-1個記錄的位置上。一般地，第i躺起泡排序是從L.r[1]到L.r[n-i+1]以此比較相鄰兩個記錄的關(guān)鍵字，并在“逆序”時交換相鄰記錄，其結(jié)果是這n-i+1個記錄中關(guān)鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進行k(1<=k 首先以一個元素為基準，從一個方向開始掃描，比如從左至右掃描，以a[0]為基準，接下來從a[0]...a[9] 中找出最小的元素，將其與a[0]交換，然后將基準位置右 移一位，重復(fù)上面的動作，比如，以a[1]為基準，找出a[1]至a[9]中最小的，將其與a[1]交換，一直進行到基準位置移到數(shù)組最后一個元素時排序結(jié)束（此時基準左邊所有元素均遞增有序，而基準為最后一個元素，故完成排序）。4.直接插入排序算法 直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數(shù)增1的有序表。 一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1...i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r[1....i].在自i-1起往前搜索的過程中，可以同時后移記錄。 整個排序過程為進行n-1躺插入，即：先將序列中的第一個記錄看成是一個有序的子序列，然后從第二個記錄起逐個進行插入，直至整個序列變成按關(guān)鍵字非遞減有序序列為止 三、程序源代碼 1.二叉排序樹的創(chuàng)建、遍歷和查找刪除算法 #include void Insert(Tree &T,KeyType key){ if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else } { } if(key } int num;char c;while(scanf(“%d”,&num)){ } Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍歷 { if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){ Tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){ } if(!T){ printf(“n該結(jié)點不存在n”);return;} else { } if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序樹查找 { if(!T){ } printf(“該結(jié)點不存在”);return 0;else if(key == T->data)return T;else if(key < T->data) return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函數(shù) { Tree T,p;T=NULL;KeyType x; printf(“請輸入二叉樹各結(jié)點：n”); CreatTree(T); printf(“中序遍歷為：n”);In_Order(T);printf(“n請輸入要查找和刪除的結(jié)點：n”);scanf(“%d”,&x);p=Search(T, x);if(p){ } DelNode(T, x);printf(“中序遍歷為：n”);In_Order(T); } 2、冒泡排序和折半查找算法 #include int BubbleSort(int c[]){ int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所輸入的數(shù)字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int BinarySearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn請輸入您要查找的數(shù)字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的數(shù)字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“請您輸入數(shù)據(jù):nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } BubbleSort(a);BinarySearch(a);return 0; 3、簡單選擇排序和簡單插入排序算法 #include int i,j,min,p,key,k; for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int InserSort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“請輸入關(guān)鍵字的個數(shù)：”);scanf(“%d”,&n);printf(“排序類型：n”);printf(“1.選擇排序n”);printf(“2.插入排序n”);printf(“請選擇：”);scanf(“%d”,&b);switch(b){ case 1: printf(“請輸入關(guān)鍵字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“請輸入關(guān)鍵字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及結(jié)果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、實驗運行結(jié)果 1.二叉排序樹的創(chuàng)建、遍歷和查找刪除算法 2、冒泡排序和折半查找算法 3、簡單選擇排序和簡單插入排序算法 七、心得體會 通過本次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告，掌握了查找和排序的幾種基本排序算法，了解了他們各自的特點和優(yōu)缺點，完成了對于他們C語言的描述和實際應(yīng)用，對他們有了一個更加具體、深刻的認識，同時也鍛煉了我們的邏輯思維能力和動手實踐能力，使我們受益匪淺，給我們今后的計算機專業(yè)課程學(xué)習(xí)帶來很大的幫助。 東華理工大學(xué) 東華理工大學(xué) 課程設(shè)計報告 課程設(shè)計題目： 綜合排序的設(shè)計 學(xué)生姓名：何楊 班 級：1223202 專 業(yè)：信息與計算科學(xué) 指導(dǎo)教師：郭樹蕻 2014年 12 月 13 日 東華理工大學(xué) 目錄 摘要..............................................................2 一、題目的內(nèi)容及要求-----------------4 二、需求分析------------------------------4 三、概要設(shè)計------------------------------5 四、四種排序源代碼詳細設(shè)計--------5 五、程序輸出的結(jié)果-------------------10 六、運行結(jié)果及分析-------------------12 七、收獲及體會-------------------------13 八、參考文獻-----------------------------1 東華理工大學(xué) 摘 要 數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式，是其在計算機內(nèi)的表示；此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運算才有意義。在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)有的算法有很多種，其中包含冒泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有其特點。對排序算法比較的分析可以遵循若干種不同的準則，通常以排序過程所需要的算法步數(shù)作為度量，有時也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當作一次鍵比較需要較長時間，例如，當鍵是較長的字符串時，常以鍵比較次數(shù)作為排序算法計算時間復(fù)雜性的度量。當排序時需要移動記錄，且記錄都很大時，還應(yīng)該考慮記錄的移動次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復(fù)雜性的度量。 關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)；算法比較；比較次數(shù)；時間復(fù)雜度 東華理工大學(xué) 一、題目的內(nèi)容及要求 排序綜合 利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求： (1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。 (2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。 (3)如果采用4種或4種以上的方法者，可適當加分。 二、需求分析 2.1 問題描述 此次的任務(wù)要求是輸入20000個以上的隨機整數(shù)，對這些數(shù)進行多種方法進行排序。（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。 約束：程序可由用戶自行設(shè)定排序數(shù)的個數(shù)，但排序數(shù)具體值需要由計算機生成，然后用三種以上的排序方法對隨機數(shù)組進行排序，每一種排序方法執(zhí)行后需統(tǒng)計出數(shù)據(jù)移動次數(shù)以判斷排序方法的對比隨機數(shù)組的執(zhí)行優(yōu)劣性。另：用戶自行算出每一種排序方法的時間復(fù)雜度與空間復(fù)雜度。 2.2 基本要求 2.2.1輸入的形式和輸入值的范圍； 設(shè)定的隨機數(shù)據(jù)的范圍為20000以上，用戶自定義隨機數(shù)的個數(shù)n，隨機數(shù)的數(shù)據(jù)類型均為整形。 2.2.2輸出的形式； 程序是以一個完整的有序數(shù)組來進行輸出。 2.2.3程序所達到的功能： 將一個無序數(shù)組進行排序隨機生成20000以上個隨機整數(shù)，對這些數(shù)進行多種方法進行排序。分別采用以下方法實現(xiàn)上述問題求解（可采用的方法有簡單排序、希爾排序、冒泡排序、快速排序這四種排序方法）。 東華理工大學(xué) 三、概要設(shè)計 3.1可排序表的抽象數(shù)據(jù)類型定義： typedef int KeyType;//關(guān)鍵字為整型 typedef int OtherType;//關(guān)鍵字為整型 typedef struct { KeyType key;//關(guān)鍵字為KeyType型 OtherType other_data;}RecordType;//定義一個RecordType型結(jié)構(gòu)體，存放關(guān)鍵字 void quicksort(RecordType a[],int left,int right)//快速排序 void bubbleSort(RecordType a[],int length)//冒泡排序 void shellSort(RecordType a[],int n)//希爾排序 void BinSort(RecordType r[], int length)//折半插入排序 void main()//主函數(shù)運行入口 四、四種排序源代碼詳細設(shè)計： 4.1快速排序模塊： void quicksort(RecordType a[],int left,int right){ RecordType t;int i,j,temp; if(left>right) return; temp=a[left].key; i=left; j=right; while(i!=j) { while(a[j].key>=temp && i j--; while(a[i].key<=temp && i 東華理工大學(xué) i++; if(i { t=a[i]; a[i]=a[j]; a[j]=t; } } a[left] = a[i]; a[i].key = temp; quicksort(a,left,i-1);//繼續(xù)處理左邊的，這是一個遞歸的過程 quicksort(a,i+1,right);//繼續(xù)處理右邊的，這是一個遞歸的過程 } /* 快速排序算法 */ 4.2冒泡排序模塊： //此處是一次冒泡排序過程，在主函數(shù)中會通過循環(huán)調(diào)用此冒泡函數(shù)過程 void bubbleSort(RecordType a[],int length){ int i,temp; for(i=1;i { if(a[i].key>a[i+1].key) { temp = a[i].key; a[i].key=a[i+1].key; a[i+1].key=temp; } } }/* 冒泡排序算法 */ 4.3希爾排序模塊： void shellSort(RecordType a[],int n){ int i, j, temp; int gap = 0; while(gap<=n)//根據(jù)待排序的個數(shù)生成合適的步長，gap是步長 { gap = gap * 3 + 1; 東華理工大學(xué) } } while(gap > 0){ for(i = gap;i < n;i++){ j = igap; } a[j+gap+1].key = temp;} gap =(gap-1)/ 3;} 4.4希爾折半插入排序模塊： /*折半插入排序法*/ void BinSort(RecordType r[], int length)/*對記錄數(shù)組r進行折半插入排序，length為數(shù)組的長度*/ { int i,j;RecordType x;int low,high,mid;for(i=2;i<=length;++i) { x= r[i]; low=1;high=i-1; while(low<=high) /* 確定插入位置*/ { mid=(low+high)/ 2; if(x.key< r[mid].key) high=mid-1; else low=mid+1; } for(j=i-1;j>= low;--j) r[j+1]= r[j]; /* 記錄依次向后移動 */ r[low]=x; /* 插入記錄 */ } }/*BinSort*/ 東華理工大學(xué) 4.5主函數(shù)模塊： void main(){ int n,i,j,t; char b; bool q=false; RecordType a[40000]; while(1) { printf(“nn”);printf(“ ************** 綜 合 排 序*****************************nn”); printf(“ *********************菜 單***************************nn”);printf(“ * ========= * n”); printf(“ * 1.讀 取 待排序長度 * n”); printf(“ * 2.產(chǎn)生隨機數(shù)并輸出 * n”); printf(“ * 3.采用快速排序法排序 * n”); printf(“ * 4.采用冒泡排序法排序 * n”); printf(“ * 5.采用希爾排序法排序 * n”); printf(“ * 6.采用折半插入排序法排序 * n”); printf(“ * 7.輸 出 * n”);printf(“ * 0.退 出 系 統(tǒng) * n”);printf(“ *------------------------* n”); printf(“ ”); b = getch(); switch(b) { case '1': printf(“%cn”,b); printf(“請輸入待排序記錄的長度：”); scanf(“%d”,&n);break; 東華理工大學(xué) case '2': printf(“%cn”,b); srand((unsigned)time(NULL)); printf(“下面隨機生成%d個數(shù)字存儲在數(shù)組中n”,n); for(i=1;i<=n;i++) { a[i].key = rand()%20000; printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } printf(“n”); break; case '3': printf(“%cn”,b); printf(“n -----------------快速排序結(jié)束------------------- nn”); quicksort(a,1,n); q=true;break; case '4': printf(“%cn”,b); for(i=0;i { bubbleSort(a,n-i); } printf(“n -----------------冒泡排序結(jié)束------------------- nn”); q=true;break; case '5': printf(“%cn”,b); printf(“n -----------------希爾排序結(jié)束------------------- nn”); shellSort(a,n); q=true;break; case '6': printf(“%cn”,b); BinSort(a,n); printf(“n -----------------折半插入排序結(jié)束-------------------nn”); q=true;break; case '7': printf(“%cn”,b); 東華理工大學(xué) if(q) { printf(“n -----------------排序后輸出------------------- n”); for(i=1;i<=n;i++) { printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } } else { printf(“n * ========= * n”); printf(“ * 您未對待排序數(shù)據(jù)排序 * n”); printf(“ * 請重新選擇排序的序號 * n”); printf(“ *------------------------* n”); } break; case '0': printf(“%cn”,b); printf(“n 感謝使用綜合排序程序n 按任意鍵退出......n”); return;break; default:printf(“nn”); } } } 五、程序輸出的結(jié)果： 5.1輸入和輸出： (1)主函數(shù)運行的輸出結(jié)果： 東華理工大學(xué) (2)選擇1，讀取待排序長度（這里以20000為例）： (3)選擇2，產(chǎn)生隨機數(shù)并輸出： (4)選擇3，采用快速排序法排序： 東華理工大學(xué) （選擇4、5、6的其他排序法的輸出雷同，此處就不再重復(fù)）(5)選擇7，輸出排序結(jié)果： 六、運行結(jié)果及分析 6.1各算法的比較方法 1.穩(wěn)定性比較 折半插入排序、冒泡排序是穩(wěn)定的希爾排序、快速排序是不穩(wěn)定的 2.時間復(fù)雜性比較 折半插入排序、冒泡排序的時間復(fù)雜性為O(n2)其它非線形排序的時間復(fù)雜性為O(nlog2n)3.輔助空間的比較 東華理工大學(xué) 線形排序的輔助空間為O(n),其它排序的輔助空間為O(1);4.其它比較 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。 反而在這種情況下，快速排序反而慢了。 當n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。 當n較大時，關(guān)鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。 七、收獲及體會 根據(jù)四種排序法的基礎(chǔ)理論實際性模仿和編寫算法程序，很是困難，算法是程序的靈魂，數(shù)據(jù)結(jié)構(gòu)確是算法的基礎(chǔ)，但是不斷的實踐也是一種進步的好途徑。這次課程設(shè)計主要是對基礎(chǔ)知識的靈活應(yīng)用，這就讓我進一步提高了對數(shù)結(jié)構(gòu)知識的鞏固。這次設(shè)計的完成，困難是少不了的，還有很多其它的難題讓我都不知道所措，但是通過努力最終解決他們讓我體會到成就感，更重要的是我的能力在實踐中得到了提升和優(yōu)化，特別是對常用的排序算法的應(yīng)用，這對我以后從事軟件應(yīng)用程序開發(fā)是有很大的幫助的。這次課程設(shè)計的心得體會通過實習(xí)我的收獲如下 1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。 2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。 3、通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。 4、通過課程設(shè)計，培養(yǎng)了我嚴肅認真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。根據(jù)我在實習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。 2、寫程序的過程中要考慮周到，嚴密。 3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。 4、認真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。 5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。我通過課程設(shè)計建立系統(tǒng)設(shè)計的整體思想，鍛煉編寫程序、調(diào)試程序的能力，學(xué)習(xí)文檔編寫規(guī)范，培養(yǎng)獨立學(xué)習(xí)、吸取他人經(jīng)驗，樹立團隊協(xié)作精神。同時，充分彌補了課堂教學(xué)及普通實驗中知識深度與廣度有限的缺陷，更好地幫助從全局角度把握 東華理工大學(xué) 課程體系，并且可以將理論與實際聯(lián)系。在課程設(shè)計的過程中不僅僅是書本上的知識，這便促使我去查閱更多的課外資料來充實自己的內(nèi)容，同時學(xué)會在面對困難時要耐心得分析它細心得解決它以及通過合作更完美得深入了解剖析它以便得到提高。細心、耐心、團結(jié)、求知，是我這次課程設(shè)計最大的收獲。同時要感謝老師這幾天的悉心教導(dǎo)。 八、參考文獻 [1] 啊哈磊，《啊哈！算法》，人民郵電出版社，2014-6-1 [2] 劉艷飛，《C語言范例開發(fā)大全》清華大學(xué)出版社，2010 [3] 嚴蔚敏，吳偉民。數(shù)據(jù)結(jié)構(gòu)。北京：清華大學(xué)出版社，2001 電 子 科 技 大 學(xué) 實 驗 報 告 學(xué)生姓名：XXX 學(xué) 號：20*** 指導(dǎo)教師：劉嶠 實驗地點：信軟機房306 實驗時間：2014/6/20 一、實驗室名稱：軟件實驗室 二、實驗項目名稱：數(shù)據(jù)結(jié)構(gòu)與算法—排序與查找 三、實驗學(xué)時：4 四、實驗原理： 快速排序的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。 假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）設(shè)置兩個變量I、J，排序開始的時候I：=1，J：=N 2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]； 3）從J開始向前搜索，即（J：=J-1），找到第一個小于X的值，兩者交換； 4）從I開始向后搜索，即（I：=I+1），找到第一個大于X的值，兩者交換； 5）重復(fù)第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）確定該區(qū)間的中點位置：mid=（low+high）/2 min代表區(qū)間中間的結(jié)點的位置，low代表區(qū)間最左結(jié)點位置，high代表區(qū)間最右結(jié)點位置 （2）將待查a值與結(jié)點mid的關(guān)鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則確定新的查找區(qū)間： A)如果R[mid].key>a，則由表的有序性可知，R[mid].key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在R[mid].key左邊的表中,這時high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，則查找成功。 （3）下一次查找針對新的查找區(qū)間，重復(fù)步驟（1）和（2） （4）在查找過程中，low逐步增加，high逐步減少，如果high 五、實驗?zāi)康模?/p> 本實驗通過實現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實現(xiàn)快速查找和排序的基本算法思想。通過練習(xí)，加強對算法的理解，提高編程能力。 六、實驗內(nèi)容： （1）實現(xiàn)數(shù)據(jù)序列的輸入; （2）實現(xiàn)快速排序算法,并對輸入的序列排序后輸出； （3）實現(xiàn)折半查找算法,并在步驟(2)排序后的序列上,進行任意地 查找,并輸出查詢結(jié)果。 七、實驗器材（設(shè)備、元器件）： 八、數(shù)據(jù)結(jié)構(gòu)及程序 #include #define MAX_LEN 100 void Sort(int *data,int left,int right){ int i,j,temp; i=left; j=right; temp=data[left]; if(left>right) return; while(i!=j){ while(data[j]>=temp&&j>i) j--; if(j>i) data[i++]=data[j]; while(data[i]<=temp&&j>i) i++; if(j>i) data[j--]=data[i]; } data[i]=temp; Sort(data,left,i-1);PC機一臺，裝有C/C++語言集成開發(fā)環(huán)境。 Sort(data,i+1,right);} int Search(int *data,int start,int end,int key,int num){ int result; int p =(start + end)/ 2; if(data[p] == key&&start<=end){ result = p; num++; if(data[p] > key) result = Search(data, start, p, key,num); else result = Search(data, p + 1, end, key,num); return result; } else if(num==0&&start>end){ result =-1; printf(“n 404 NO FOUNDn”); return result; } else if(num!=0&&start>end){ result=-1; if(num==1) printf(“nFounded number only one”); else printf(“nFounded number more than one”); return result; } else if(result!=-1){ if(data[p] > key) result = Search(data, start, p-1, key, num); else result = Search(data, p + 1, end, key, num); return result; } else { result=-1; return result; } } void loadFile(int *data,char *filename,int n){ int i; FILE *pfile=NULL; pfile=fopen(filename,“r”); if(!pfile){ printf(“Open file failn”); exit(0); } else printf(“Open file success!n”); for(i = 0;i < n;i++) fscanf(pfile , “%d ”,&data[i]);} int main(int argc, const char * argv[]){ int input=1,data[MAX_LEN],num=0,key=1,i,cmd; char filename[100]; printf(“Choose Mode :n 1.Input Mode 2.File Moden”); scanf(“%d”,&cmd); if(cmd==1){ printf(“Input data :(Enter 0 to detemine)n”); while(input!=0){ printf(“Enter the %d data :”,num+1); scanf(“%d”,&input); if(input!=0){ data[num]=input; num++; } } } else{ printf(“nInput the address of the file: ”); scanf(“%s”,filename); printf(“nInput the number of elem: ”); scanf(“%d”,&num); loadFile(data,filename,--num); } Sort(data, 0, num); printf(“nSort result: ”); for(i=1;i<=num;i++) printf(“%d ”,data[i]); printf(“nn”); while(key!=0){ printf(“nInput a key to search :(Enter 0 to detemine)”); scanf(“%d”,&key); if(key!=0) Search(data, 0, num, key, 0); } return 0;} 九、程序運行結(jié)果： 1.打開程序： 2.嘗試手動輸入模式： 3.搜索已存在數(shù)： 4.搜索不存在數(shù)： 5.嘗試文件讀入模式并搜索 實驗成功。 十、實驗結(jié)論： 使用好的排序與查找算法對于程序的運行效率至關(guān)重要，一個好的算法，適合的算法能使計算機對數(shù)據(jù)的處理事半功倍，而選用錯誤的算法，不但可能事倍功半，還有可能造成不穩(wěn)定因素。 快速排序的時間復(fù)雜度為n（log2n）,是排序算法中最為快速的一種，但是不穩(wěn)定，對基本有序的序列效率較差。 二分查找算法在查找算法中，速度快，效率高，但是要求數(shù)據(jù)要有序。 十一、總結(jié)及心得體會： 當空間充足，對穩(wěn)定性要求不高的情況，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以較高的效率查找目標元素。 編號： 139 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 說明書 動態(tài)查找表 學(xué) 院： 海洋信息工程學(xué)院 專 業(yè)： 計算機科學(xué)與技術(shù) 學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 2015年月 26 日 動態(tài)查找表 學(xué)生姓名：銀杰 指導(dǎo)老師：王曉瑩 摘 要 本課程設(shè)計說明書系統(tǒng)地闡述了我使用C語言在Code::Blocks軟件編寫的動態(tài)查找表程序的整個過程，編寫的環(huán)境是win7 64位操作系統(tǒng)。根據(jù)題目要求，編寫動態(tài)查找表使用二叉排序樹，即二叉鏈表作為存儲結(jié)構(gòu)。該程序具有建立數(shù)據(jù)功能、具有數(shù)據(jù)查找功能、具有數(shù)據(jù)插入功能、具有數(shù)據(jù)刪除功能等基本功能操作。 關(guān)鍵詞：動態(tài)查找表，Code::Blocks軟件，win7 64位操作系統(tǒng)，C# dynamic lookup table Author :yinjie Tutor :Wangxiaoying Abstract This course design specification system to explain the whole process of using C language in Code:: Blocks software written in the dynamic look-up table program, the preparation of the environment is win7 64 bit operating system.According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure.The program has the function of building data, data searching, data insertion, data deletion and so on.Key words:dynamic lookup table, Code::Blocks software,win7 64 bit operating system，C # 目 錄 引言.........................................................................................................................................................................1 查找的基本概念.................................................................................................................................................1 小結(jié).....................................................................................................................................................................1 題目.....................................................................................................................................................................1 第1章 程序的構(gòu)圖設(shè)計.....................................................................................................................................2 1.1動態(tài)查詢表：...............................................................................................................................................2 1.2程序功能流程圖：.......................................................................................................................................2(1)、主函數(shù)模塊............................................................................................................................................2(2)、二叉排序樹的生成................................................................................................................................3(3)、二叉排序樹的查找模塊........................................................................................................................4(4)、二叉排序樹的插入模塊........................................................................................................................4(5)、二叉排序樹刪除連接模塊....................................................................................................................5(6)、二叉排序樹的刪除模塊........................................................................................................................5(7)、二叉排序樹的遍歷模塊........................................................................................................................6 第2章 詳細設(shè)計的程序.....................................................................................................................................6 各函數(shù)模塊.........................................................................................................................................................6(1)主函數(shù)模塊................................................................................................................................................6(2)二叉排序樹的生成模塊............................................................................................................................8(3)二叉排序樹的查找模塊............................................................................................................................8(4)二叉排序樹的插入模塊............................................................................................................................9(5)多態(tài)查找表刪除模塊..............................................................................................................................10(6)二叉排序樹的中序遍歷模塊..................................................................................................................12 第3章 程序測試和運行.....................................................................................................................................12 3.1 程序測試....................................................................................................................................................12 3.2 程序運行....................................................................................................................................................13 1、主界面 ...................................................................................................................................................13 2、建立二叉排序樹模塊界面.....................................................................................................................13 3、二叉排序樹查找模塊界面.....................................................................................................................14 4、二叉排序樹插入模塊界面.....................................................................................................................14 5、二叉排序樹刪除模塊界面 ...................................................................................................................14 6、退出程序的界面.....................................................................................................................................14 總 結(jié).....................................................................................................................................................................15 程序完成情況...................................................................................................................................................15 有待改進之處...................................................................................................................................................15 課程設(shè)計期間的收獲.......................................................................................................................................15 附錄源代碼如下...................................................................................................................................................17 桂林電子科技大學(xué)課程設(shè)計說明書 引言 查找的基本概念 查找又稱為檢索，就是從一個數(shù)據(jù)元素集合中找出某個特定的數(shù)據(jù)元素。查找是數(shù)據(jù)處理中最為常用的一種操作，查找算法的優(yōu)劣對整個軟件系統(tǒng)的效率影響很大，尤其當所涉及的數(shù)據(jù)量較大時，更是如此。在一個數(shù)據(jù)集合中進行查找操作可選用的方法與該數(shù)據(jù)元素集合的存儲結(jié)構(gòu)有很大關(guān)系。 查找是根據(jù)某個給定的值，在數(shù)據(jù)元素構(gòu)成的集合中確定是否在這樣一個數(shù)據(jù)元素，它的關(guān)鍵字等于給定值的關(guān)鍵字。 要進行查找，必須明確要查找對象的特征，也就是要查找元素的關(guān)鍵值。如果在數(shù)據(jù)集合中能找到與給定值相等的關(guān)鍵字，則該關(guān)鍵字所屬的數(shù)據(jù)元素就是所要查找的數(shù)據(jù)元素，此時稱該查找成功；如果查遍了整個數(shù)據(jù)元素集合也未能找到與給定值相等的關(guān)鍵字，則稱該查找失敗。小結(jié) 當然對于這個說明書，我不可能做得至善至美，但是一些基本的格式內(nèi)容還是符合要求的。首先，我對查找表進行一個簡要的概述。然后，我就查找表進行了詳細的分析，這是設(shè)計中很重要的一步。接下來，我把查找表中所有的設(shè)計簡明清晰地展現(xiàn)出來，并把我在設(shè)計中遇到的問題和分析解決問題的辦法做了分析。最后，在結(jié)論中，我對自己的課程設(shè)計做了總體的評價同時簡述了我在這次課程設(shè)計中的收獲和經(jīng)驗。 題目 選題十二：動態(tài)查找表 【問題描述】 利用二叉排序樹完成動態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點。【任務(wù)要求】 算法輸入：指定一組數(shù)據(jù)。 桂林電子科技大學(xué)課程設(shè)計說明書 算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找成功與否的信息、插入和刪除后的中序遍歷結(jié)果(排序結(jié)果)。 算法要點：二叉排序樹建立方法、動態(tài)查找方法,對樹進行中序遍歷。【測試數(shù)據(jù)】 自行設(shè)定，注意邊界等特殊情況。 第1章 程序的構(gòu)圖設(shè)計 1.1動態(tài)查詢表： 依照輸入的一組數(shù)據(jù){56,80,65,20}所得的二叉排序樹如下（a）所示：當插入11的時候就如（b）所示。 562065801 156206580 （a） （b）1.2程序功能流程圖： (1)、主函數(shù)模塊 桂林電子科技大學(xué)課程設(shè)計說明書 開始打印輸出動態(tài)表的6個功能選擇欄do循環(huán)輸入選擇號hSwitch(h)執(zhí)行對應(yīng)函數(shù)模塊程序退出結(jié)束 (2)、二叉排序樹的生成 開始輸入數(shù)據(jù)個數(shù)Xfor循環(huán)輸入X個數(shù)據(jù)調(diào)用插入函數(shù)Insert二叉樹建成結(jié)束 桂林電子科技大學(xué)課程設(shè)計說明書 (3)、二叉排序樹的查找模塊 開始二叉排序樹是否為空否根結(jié)點關(guān)鍵字？key是大于遞歸返回在左子樹查找遞歸返回等于小于在右子樹查找查找失敗查找成功結(jié)束 (4)、二叉排序樹的插入模塊 開始調(diào)用查詢函數(shù)Search()是否查詢成功否被插入結(jié)點*s為新的根結(jié)點是插入的節(jié)點根結(jié)點<被插結(jié)點*s為左孩子插入成功結(jié)束 >被插結(jié)點*s為右孩子 桂林電子科技大學(xué)課程設(shè)計說明書 (5)、二叉排序樹刪除連接模塊 開始左右子樹是否為空是While循環(huán)否向右走到盡頭重接它的左右子樹將被刪結(jié)點的前驅(qū)s的內(nèi)容直接替代該結(jié)點的內(nèi)容被刪除結(jié)點的左子樹的右子樹是否為空否重接*q的右子樹是重接*q的左子樹連接成功結(jié)束(6)、二叉排序樹的刪除模塊 開始輸入要刪除的的數(shù)據(jù)是否存在關(guān)鍵字等于n的數(shù)據(jù)元素否調(diào)用刪除的連接函數(shù)Delete()結(jié)束返回是找到關(guān)鍵字并刪除 桂林電子科技大學(xué)課程設(shè)計說明書 (7)、二叉排序樹的遍歷模塊 開始二叉樹根是否為空否對左子樹按中序遍歷進行訪問根結(jié)點對右子樹按中序遍歷進行遍歷完成結(jié)束是遞歸調(diào)用 第2章 詳細設(shè)計的程序 各函數(shù)模塊 (1)主函數(shù)模塊： 用主函數(shù)main()來實現(xiàn)。主要是通過設(shè)計一個do()函數(shù)并讓主函數(shù)調(diào)用它來顯示主菜單，讓用戶選擇操作。在do()函數(shù)中，我應(yīng)用了switch-case語句來進行選擇，是個比較簡單實現(xiàn)的模塊。最后若選擇“5”退出循環(huán)。否則繼續(xù)循環(huán)。主要代碼如下： int main(){ bitree T=NULL,p;ElemType e;int n;int h;char c; do{ printf(“********************************************************n”); 桂林電子科技大學(xué)課程設(shè)計說明書 printf(“* *n”); printf(“* 動態(tài)查找表 *n”); printf(“* 1.建立二叉排序樹 *n”); printf(“* 2.二叉排序樹查找元素 *n”); printf(“* 3.二叉排序樹插入元素 *n”); printf(“* 4.二叉排序樹刪除元素 *n”); printf(“* 5.退出 *n”); printf(“* *n”); printf(“********************************************************n”); printf(“請輸入你的選擇: n”); scanf(“%d”,&h); switch(h) { case 1:Init(T);printf(“中序遍歷二叉排序樹: ”);Zhongxu(T);printf(“n”); break; case 2:printf(“請輸入要查找的數(shù)據(jù):n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“數(shù)據(jù)已經(jīng)存在!n”); else { printf(“數(shù)據(jù)不存在!n”);} break; case 3:printf(“請輸入要插入的數(shù)據(jù):n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“已經(jīng)存在!n”); else{Insert(T, e);printf(“成功插入!n”);printf(“中序遍歷二叉排序樹: ”);Zhongxu(T);printf(“n”);} break; case 4:printf(“請輸入要刪除的數(shù)據(jù):n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) { Deletebit(T,n);printf(“已經(jīng)成功刪除!n”);printf(“中序遍歷二叉排序 桂林電子科技大學(xué)課程設(shè)計說明書 樹: ”);Zhongxu(T);printf(“n”);} else printf(“數(shù)據(jù)不存在!n”); break; case 5:printf(“退出！n”); break; default:printf(“選擇錯誤，重新開始!n”); } } while(h!=5);}(2)二叉排序樹的生成模塊： 二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個結(jié)點數(shù)據(jù)，就調(diào)用一次插入算法將它插到當前已經(jīng)生成的二叉排序樹中。主要代碼如下： void Init(bitree &T)//構(gòu)造一個動態(tài)查找表T { int x;int i;int n; ElemType e;printf(“請輸入結(jié)點個數(shù): ”);scanf(“%d”,&x); for(i=1;i<=x;i++) { printf(“第%d個結(jié)點數(shù)據(jù)值:”,i);scanf(“%d”,&n); e.key=n;Insert(T,e); } printf(“二叉排序樹已經(jīng)建立!n”);} (3)二叉排序樹的查找模塊： 二叉排序樹的查找方法如下。當二叉排序樹為空時，查找失敗。 當二叉排序樹根結(jié)點的關(guān)鍵字等于key時，查找成功。 桂林電子科技大學(xué)課程設(shè)計說明書 當二叉排序樹根結(jié)點的關(guān)鍵字大于key時，從根結(jié)點的左子樹中以同樣方法進行查找。當二叉樹根結(jié)點的關(guān)鍵字小于key時，從根結(jié)點的右子樹以同樣方法進行查找。顯然，該過程是一個遞歸過程，下面給出這一算法的實現(xiàn)。 主要代碼： bitree Search(bitree T,ElemType e,bitree f,bitree &p)//在二叉排序樹中查找數(shù)據(jù) { if(!T) { p=f; return NULL; }//查找不成功 else if(T->data.key==e.key) { p=T;return T; } //查找成功 else if(T->data.key>e.key) return Search(T->lchild,e,T,p); else return Search(T->rchild,e,T,p);}//在二叉排序樹中查找數(shù)據(jù)(4)二叉排序樹的插入模塊： 若要將一個關(guān)鍵字值為key的結(jié)點t插到二叉排序樹中，只需要使該結(jié)點插入后，二叉排序樹中的元素依然按照原來的規(guī)律排列即可。二叉排序樹的插入方法如下。 若二叉排序樹是空樹，則key稱為二叉排序樹的根。 若二叉排序樹為非空，則將key與二叉排序樹的根結(jié)點進行比較：如果key的值等于根結(jié)點的值，則停止插入；如果key的值小于根結(jié)點的值，則將key插到左子樹；如果key的值大于根結(jié)點的值，則將key插到右子樹中。主要代碼如下： void Insert(bitree &T,ElemType e)//在二叉排序樹中插入數(shù)據(jù) 桂林電子科技大學(xué)課程設(shè)計說明書 { bitree p,s; if(!Search(T,e,NULL,p))//查找不成功 { s=(bitree)malloc(sizeof(bitnode)); s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s;//被插入結(jié)點*s為新的根結(jié)點 else if(e.key data.key) p->lchild=s;//被插結(jié)點*s為左孩子 else p->rchild=s;//被插結(jié)點*s為右孩子 } }(5)多態(tài)查找表刪除模塊： 從二叉排序樹中刪除一個結(jié)點，不能簡單地把以該結(jié)點為根的子樹都刪除，只能刪除掉該結(jié)點，并且還應(yīng)該保證刪除后所得到的二叉樹依然滿足二叉樹的性質(zhì)不變。也就是說，在二叉排序樹中刪除一個結(jié)點相當于刪除有序序列中的一個結(jié)點。 假設(shè)要刪除的結(jié)點為P，其雙親結(jié)點為F，同時假設(shè)結(jié)點P是結(jié)點F的左孩子（右孩子的情況類似）。刪除操作首先要確定被刪結(jié)點P是否在二叉排序樹中。若不在，則不做任何操作；若在，分為以下三種情況討論。若P為葉子結(jié)點，可直接將其刪除。 若結(jié)點P只有左子樹，或只有右子樹，則可將P的左子樹或右子樹直接改為其雙親結(jié)點F的左子樹或右子樹。 若P既有左子樹，又有右子樹此時有兩種處理方法。 方法1：首先找到結(jié)點P在中序序列中的直接前驅(qū)結(jié)點S，然后用結(jié)點P的左子樹改為F的左子樹，而將P的右子樹改為S的右子樹。 方法2：首先找到結(jié)點P在中序序列中的直接前驅(qū)結(jié)點s，然后用結(jié)點s的值替代結(jié)點p的值，再將結(jié)點s刪除，原結(jié)點s的左子樹改為s的雙親結(jié)點q的右子樹。主要代碼如下： 桂林電子科技大學(xué)課程設(shè)計說明書 void Delete(bitree &p)//從二叉排序樹中刪除結(jié)點p，并重接它的左或右子樹 { bitree q,s; if(!p->rchild)//右子樹空，只需重接它的左子樹 { q=p;p=p->lchild;free(q);q=NULL; } else if(!p->lchild)//左子樹空，只需重接它的右子樹 { q=p;p=p->rchild;free(q);q=NULL; } else{//左右子樹均不空 q=p;s=p->lchild; while(s->rchild)//向右走到盡頭 { q=s;s=s->rchild; } p->data=s->data;//將被刪結(jié)點的前驅(qū)s的內(nèi)容直接替代該結(jié)點的內(nèi)容 if(q!=p)//若被刪除結(jié)點的左子樹的右子樹不為空 q->rchild=s->lchild;//重接*q的右子樹 else q->lchild=s->lchild;//重接*q的左子樹 free(s);s=NULL; } }//刪除結(jié)點 void Deletebit(bitree &T,int n)//刪除二叉排序樹中的數(shù)據(jù) { if(!T)return;//不存在關(guān)鍵字等于n的數(shù)據(jù)元素 桂林電子科技大學(xué)課程設(shè)計說明書 else{ if(T->data.key==n)return(Delete(T));//找到關(guān)鍵字等于n的數(shù)據(jù)元素并刪除它 else if(T->data.key>n)Deletebit(T->lchild,n);//繼續(xù)在左子樹中刪除 else Deletebit(T->rchild,n);//繼續(xù)在右子樹中刪除 } } (6)二叉排序樹的中序遍歷模塊： 中序遍歷二叉樹定義：若二叉樹根為空，則返回；否則，中序遍歷左子樹；訪問根結(jié)點；中序遍歷右子樹。主要代碼如下： void Zhongxu(bitree T)//中序遍歷 { if(T!=NULL) { Zhongxu(T->lchild); printf(“%d ”,T->data.key); Zhongxu(T->rchild); } } 第3章 程序測試和運行 3.1 程序測試 程序測試是程序質(zhì)量保證的主要活動之一，在程序編寫的過程中，在各個階段都有可能存在錯誤和缺陷。通過測試是可以發(fā)現(xiàn)程序設(shè)計中存在的種種問題，并可以及時改正。避免在程序運行時才出現(xiàn)不必要的錯誤。測試是質(zhì)量保證一個臨界和決定懲罰，它提供對程序說明、設(shè)計和編碼的最終評審。是發(fā)現(xiàn)程序缺陷和錯誤的有力手段。根據(jù)系統(tǒng)設(shè)計目標和功能，對系統(tǒng)進行測試。 桂林電子科技大學(xué)課程設(shè)計說明書 1、功能性 （1）程序?qū)崿F(xiàn)的主要功能，包括查詢，插入，刪除等。 （2）題目要求的輸入輸出字段，以及題目要求的輸入限制。 2、可靠性 程序正確實現(xiàn)了對動態(tài)查找表的查詢、插入、刪除等各種功能。 3、易用性 現(xiàn)有程序?qū)崿F(xiàn)了如下易用性： （1）查詢，插入，刪除，操作相關(guān)提示信息的一致性，可理解性 ? （2）輸入限制的正確性 （3）輸入限制提示信息的正確性，可理解性，一致性 （4）界面排版簡潔完整 3.2 程序運行 1、主界面 ： 2、建立二叉排序樹模塊界面 ： 桂林電子科技大學(xué)課程設(shè)計說明書 3、二叉排序樹查找模塊界面 ： 4、二叉排序樹插入模塊界面 ： 5、二叉排序樹刪除模塊界面 ： 6、退出程序的界面 ： 桂林電子科技大學(xué)課程設(shè)計說明書 總 結(jié) 程序完成情況 在編寫程序?qū)懻n程設(shè)計的時間里，雖然歷經(jīng)重重困難和挫折，但是在我自己的努力和老師的幫助下終于完成了動態(tài)查找表的設(shè)計。盡管該程序在功能和性能上可能還有一些缺陷，但是我已經(jīng)完成了課程設(shè)計的任務(wù)和目標，達到了題目基本要求，成功完成了算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計。有待改進之處 有待改進： 1、我在編寫程序的時候，用的是C++格式去保存編譯的，用了C語言來編寫，但是有一些C++的形式，當我用C來新建保存的時候卻出現(xiàn)問題。所以程序我是用C++來新建保存的。 2、流程圖畫的不是很規(guī)范表準，在一些邏輯表達上不夠簡潔清晰。課程設(shè)計期間的收獲 在完成此次的課程設(shè)計的過程中，我跨越了傳統(tǒng)方式下的教與學(xué)的體制束縛，桂林電子科技大學(xué)課程設(shè)計說明書 通過自己的思考和設(shè)計，培養(yǎng)了自學(xué)能力和動手能力。并且由原先的被動的接受知識轉(zhuǎn)換為主動的尋求知識，這可以說是學(xué)習(xí)方法上的一個很大的突破。在以往的傳統(tǒng)的學(xué)習(xí)模式下，我們可能會記住很多的書本知識，但是通過課程設(shè)計，我們學(xué)會了如何將學(xué)到的知識轉(zhuǎn)化為自己的東西，學(xué)會了怎么更好的處理知識和實踐相結(jié)合的問題。 通過這次課程設(shè)計，我認識到數(shù)據(jù)結(jié)構(gòu)與算法是計算機科學(xué)的基礎(chǔ)課程，是我們學(xué)習(xí)的核心課程。我對數(shù)據(jù)結(jié)構(gòu)和算法又有了新的認識。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機軟件，而且和計算機硬件的研究也有著密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，以便使查找和存取數(shù)據(jù)元素更為方便。可以認為數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一個核心內(nèi)容，是從事計算機科學(xué)研究及其應(yīng)用的人必須掌握的重要內(nèi)容。 這次的課程設(shè)計有效的培養(yǎng)了我們獨立思考的能力，提高了我們的動手操作水平。在具體設(shè)計中，我們鞏固了上學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法的理論知識，進一步提高了自己的編程能力。這也是課程設(shè)計的目的所在。通過編程實踐，不僅開發(fā)了自己的邏輯思維能力，培養(yǎng)了分析問題、解決問題的能力，更充分鍛煉了我們的編程能力。 在這次課程設(shè)計中我也知道了的編程能力不強，有很多程序與算法是借鑒別人的，我想只要我有自己寫程序，并且結(jié)合他人的程序算法，把程序完成，那我還是學(xué)習(xí)到東西了的。 在課程設(shè)計中我體會到：一個好的程序應(yīng)該是一個高內(nèi)聚低耦合的程序。而要做出一個好的程序則應(yīng)該通過對算法與其數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度和空間復(fù)雜度進行實現(xiàn)與改進。然而，實際上很難做到十全十美，原因是各要求有時相互制約，要節(jié)約算法的執(zhí)行時間往往要以犧牲更多的存儲空間為代價：而為了節(jié)省存儲空間又可能要以更多的時間為代價。因此，只能根據(jù)具體情況有所側(cè)重：如果程序的使用次數(shù)較少，則應(yīng)該力求算法簡單易懂；如果程序反復(fù)多次使用，則應(yīng)該盡可能選用快速算法或者設(shè)置為內(nèi)聯(lián)函數(shù)；如果解決問題的數(shù)據(jù)量極大，但是機器的內(nèi)存空間不是很充足，則在編寫算法時應(yīng)該考慮如何節(jié)省空間。 學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)與算法》這門課，我們在編寫程序時就應(yīng)該注意到所編寫程序的時間復(fù)雜度和空間復(fù)雜度，以及是否運用了良好的算法，而不是只是象以前編寫程序時單純使用C++的知識。我們要充分考慮程序的性能，從而編寫出更好的程序。 桂林電子科技大學(xué)課程設(shè)計說明書 在設(shè)計報告的寫作過程中我也學(xué)到了做任何事情都要有的心態(tài)，首先我明白了做學(xué)問要一絲不茍，對于出現(xiàn)的任何問題都不要輕視，要通過正確的途徑去解決，在做事情的過程中要有耐心和毅力，不要一遇到困難就打退堂鼓，只要堅持下去就可以找到思路去解決問題的，在遇到問題時，有必要向老師和同學(xué)請教，合作溝通的意義是巨大的。 在這次課程設(shè)計中，我認識到了自己的不足之處同時我也收獲了很多知識和經(jīng)驗，在今后的學(xué)習(xí)中，我一定勤于思考，并靈活運用所學(xué)知識，多進行編程實踐。在總結(jié)反思和編程訓(xùn)練中，不斷提升自己的編程能力。相信在我的努力下，我的程序設(shè)計水平一定會不斷提高。 參考文獻 [1]數(shù)據(jù)結(jié)構(gòu)與算法/汪沁，奚李峰主編.-北京：清華大學(xué)出版社，2012.9（第8章 查找） [2]百度文庫>專業(yè)資料>IT/計算機>計算機軟件及應(yīng)用>動態(tài)查找表實驗報告 http://wenku.baidu.com/link?url=crizbdK6WO86YXeSJWwkHNdXpaxUDkRJnoShcVDJqBfGO03Cbk6LAdVwBYHxE82kYHkuIjC1HFCiOrSiEWJXOOspWGIo3PNSDjbeY1jHbJu 附錄源代碼如下： 數(shù)據(jù)結(jié)構(gòu)與算法的課程設(shè)計1.cpp 實驗題9.1 設(shè)計一個程序exp9-1.cpp，輸出在順序表{3，6，2，10，1，8，5，7，4，9}中采用順序方法找關(guān)鍵字5的過程。程序如下： //文件名:exp9-1.cpp #include KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 //其他數(shù)據(jù) //定義表中最多記錄個數(shù) InfoType data; } NodeType;typedef NodeType SeqList[MAXL]; //順序表類型 int SeqSearch(SeqList R,int n,KeyType k)//順序查找算法 { int i=0; while(i { } printf(“%d ”,R[i].key);i++; //從表頭往后找 if(i>=n)return-1; else } void main(){ SeqList R;{ } printf(“%d”,R[i].key);return i; } int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i //建立順序表 printf(“關(guān)鍵字序列:”);for(i=0;i 截圖如下： 實驗題9.2 設(shè)計一個程序exp9-2.cpp，輸出在順序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找關(guān)鍵字9的過程。 程序如下： //文件名:exp9-2.cpp #include //定義表中最多記錄個數(shù) KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 InfoType data; //其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL]; //順序表類型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“ 第%d 次 比 較 :在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid; if(R[mid].key>k) //繼續(xù)在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //繼續(xù)在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立順序表 R[i].key=a[i];printf(“關(guān)鍵字序列:”);for(i=0;i 比 較 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截圖如下： 實驗題9.3 設(shè)計一個程序exp9-3.cpp，輸出在順序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分塊查找法查找（每塊的塊長為5，共5塊）關(guān)鍵字46的過程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 //定義表中最多記錄個數(shù) //定義索引表的最大長度 InfoType data; //其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType為關(guān)鍵字的類型 //指向分塊的起始下標 //順序表類型 } IdxType;typedef IdxType IDX[MAXI]; //索引表類型 int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分塊查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m; //b為每塊的記錄個數(shù) printf(“二分查找n”);while(low<=high) //在索引表中進行二分查找,找到的位置存放在low中 { mid=(low+high)/2;printf(“ 第%d 次 比 較 :在[%d,%d] 中 比 較 元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累計在索引表中的比較次數(shù) } if(low //在索引表中查找成功后,再在線性表中進行順序查找 { printf(“比較%d次,在第%d塊中查找元素%dn”,count1,low,k); i=I[low].link; printf(“順序查找:n ”); while(i<=I[low].link+b-1 && R[i].key!=k) { i++;count2++; printf(“%d ”,R[i].key);} //count2累計在順序表對應(yīng)塊中的比較次數(shù) printf(“n”); printf(“比較%d次,在順序表中查找元素%dn”,count2,k); if(i<=I[low].link+b-1) return i; else return-1;} 素 } return-1;void main(){ } SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i]; //建立順序表 I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”); 截圖如下：第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計—綜合排序
第三篇：數(shù)據(jù)結(jié)構(gòu)實驗報告-排序與查找
第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計：動態(tài)查找表
第五篇：數(shù)據(jù)結(jié)構(gòu)查找實驗報告
點擊咨詢 