第一篇：教案程序代碼-查找與排序
一、查找
1、順序查找
int search(ET v[], int n , ET x){ int k=0;while(k 2、二分法查找 int bsearch(ET v[] , int n, ET x){ int i, j, k;while(i<=j){ k=(i+j)/2;if(x==v[k])return k;if(x 3、分塊查找 struct indnode { int key;int k;};int insearch(ET v[], struct indnode s[], int n, int m, ET x){ int i, j, t;i=0;j=m-1;while(i<=j){ t=(i+j)/2; if(x<=s[t].key)j=t-1; else if(x>s[t].key)i=t+1;} if(i 二、排序 1、雙向冒泡 void bubsort(ET p[], int n) { int m, k, j, i;ET d; k=0;m=n-1; while(k if(p[i]>p[i+1]) { d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;} j=k+1;k=0;for(i=m;i>=j;i--) if(p[i-1]>p[i]) { d=p[i];p[i]=p[i+1];p[i+1]=d;k=i;} } } 2、快速排序1 void qksort(ET p[], int m, int n){ int i;if(n>m) { i=split(p, m, n); qksort(p, m, i-1);qksort(p, i+1, n);} return;} static int split(ET p[], int m , int n){ int I, j, k, u;ET t;i=m-1;j=n-1;k=(i+j)/2;if(p[i]>=p[j]&&p[j]>=p[k])u=j;else if(p[i]>=p[k]&&p[k]>=p[j])u=k;else u=i;t=p[u];p[u]=p[i];while(i!=j){ while(i while(i if(i 3、快速排序2 void quicksort(int p[],int left,int right){ int i, j, t; i=left;j=right;t=p[i]; while(i { } p[i]=t; outtable(p); if(left if(j 4、直接插入排序 void insort(ET p[], int n) { int j, k;ET t; for(j=1;j { t=p[j]; k=j-1; while(k>=0 && p[k]>t) { p[k+1]=p[k];k=k-1;} p[k+1]=t;} } 5、希爾排序 void shlsort(ET p[], int n){ int h, j, k;ET t; h=h/2; while(h>0) { for(j=h;j<=n-1;j++) { t=p[j]; k=j-h; while(k>=0 && p[k]>t) { p[k+h]=p[k];k=k-h;} p[k+h]=t;} h=h/2;} } 6、選擇排序 void select(ET p[], int n){ int i, j, k;ET d;for(i=0;i p[i]=p[j];i++; } while((i } for(j=i+1;j void heap(ET p[], int n){ int i, k;ET t; k=n/2; for(i=k-1;i>=0;i--)sift(p, n-1, i); for(i=n-1;i>=1;i--) { t=p[0];p[0]=p[i];p[i]=t; sift(p, i-1, 0); } return;} static sift(ET A[], int n, int m) { int j;ET t; t=h[m];j=2*(m+1)-1;while(j<=n){ if(j 如有打錯的地方請指出。 電 子 科 技 大 學 實 驗 報 告 學生姓名：XXX 學 號：20*** 指導教師：劉嶠 實驗地點：信軟機房306 實驗時間：2014/6/20 一、實驗室名稱：軟件實驗室 二、實驗項目名稱：數據結構與算法—排序與查找 三、實驗學時：4 四、實驗原理： 快速排序的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）設置兩個變量I、J，排序開始的時候I：=1，J：=N 2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]； 3）從J開始向前搜索，即（J：=J-1），找到第一個小于X的值，兩者交換； 4）從I開始向后搜索，即（I：=I+1），找到第一個大于X的值，兩者交換； 5）重復第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）確定該區間的中點位置：mid=（low+high）/2 min代表區間中間的結點的位置，low代表區間最左結點位置，high代表區間最右結點位置 （2）將待查a值與結點mid的關鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則確定新的查找區間： A)如果R[mid].key>a，則由表的有序性可知，R[mid].key右側的值都大于a，所以等于a的關鍵字如果存在，必然在R[mid].key左邊的表中,這時high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，則查找成功。 （3）下一次查找針對新的查找區間，重復步驟（1）和（2） （4）在查找過程中，low逐步增加，high逐步減少，如果high 五、實驗目的： 本實驗通過實現快速排序和折半查找算法，使學生理解如何實現快速查找和排序的基本算法思想。通過練習，加強對算法的理解，提高編程能力。 六、實驗內容： （1）實現數據序列的輸入; （2）實現快速排序算法,并對輸入的序列排序后輸出； （3）實現折半查找算法,并在步驟(2)排序后的序列上,進行任意地 查找,并輸出查詢結果。 七、實驗器材（設備、元器件）： 八、數據結構及程序 #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++語言集成開發環境。 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;} 九、程序運行結果： 1.打開程序： 2.嘗試手動輸入模式： 3.搜索已存在數： 4.搜索不存在數： 5.嘗試文件讀入模式并搜索 實驗成功。 十、實驗結論： 使用好的排序與查找算法對于程序的運行效率至關重要，一個好的算法，適合的算法能使計算機對數據的處理事半功倍，而選用錯誤的算法，不但可能事倍功半，還有可能造成不穩定因素。 快速排序的時間復雜度為n（log2n）,是排序算法中最為快速的一種，但是不穩定，對基本有序的序列效率較差。 二分查找算法在查找算法中，速度快，效率高，但是要求數據要有序。 十一、總結及心得體會： 當空間充足，對穩定性要求不高的情況，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以較高的效率查找目標元素。 查找及排序算法實現 一、實驗目的 1、熟練掌握二叉排序樹查找算法及C語言描述。 2、熟練掌握折半查找算法及C語言描述。 3、熟練掌握簡單選擇排序算法及C語言描述。 4、熟練掌握簡單插入排序算法及C語言描述。 5、熟練掌握冒泡（起泡）排序算法及C語言描述。 6、了解各種查找及排序算法的優缺點、實用性及應用。 7、將理論與實際相結合，切實提高自己的邏輯能力和動手能力。 二、設計內容 1.折半查找算法 折半查找算法的思路： 初始狀態：假設表長為n，low、high和mid分別指向待查元素所在區間的下界、上界和中點,key為給定值，初始時，令low=0,high=n-1,mid=(low+high)/2 讓key與mid指向的記錄比較 若key==r[mid].key，查找成功,算法結束；若key 起泡排序的思路： 首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較【第二個記錄和第三個記錄】的關鍵字。以此類推，直至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。上述過程稱做第一趟起泡排序，其結果使得關鍵字最大的記錄被安置到最后一個記錄的位置上，然后進行第二趟起泡排序，對前n-1個記錄進行同樣操作，其結果是使關鍵字次大的記錄被安置到第n-1個記錄的位置上。一般地，第i躺起泡排序是從L.r[1]到L.r[n-i+1]以此比較相鄰兩個記錄的關鍵字，并在“逆序”時交換相鄰記錄，其結果是這n-i+1個記錄中關鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進行k(1<=k 首先以一個元素為基準，從一個方向開始掃描，比如從左至右掃描，以a[0]為基準，接下來從a[0]...a[9] 中找出最小的元素，將其與a[0]交換，然后將基準位置右 移一位，重復上面的動作，比如，以a[1]為基準，找出a[1]至a[9]中最小的，將其與a[1]交換，一直進行到基準位置移到數組最后一個元素時排序結束（此時基準左邊所有元素均遞增有序，而基準為最后一個元素，故完成排序）。4.直接插入排序算法 直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數增1的有序表。 一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1...i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r[1....i].在自i-1起往前搜索的過程中，可以同時后移記錄。 整個排序過程為進行n-1躺插入，即：先將序列中的第一個記錄看成是一個有序的子序列，然后從第二個記錄起逐個進行插入，直至整個序列變成按關鍵字非遞減有序序列為止 三、程序源代碼 1.二叉排序樹的創建、遍歷和查找刪除算法 #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該結點不存在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(“該結點不存在”);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()//主函數 { Tree T,p;T=NULL;KeyType x; printf(“請輸入二叉樹各結點：n”); CreatTree(T); printf(“中序遍歷為：n”);In_Order(T);printf(“n請輸入要查找和刪除的結點：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您所輸入的數字的升序排列是: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請輸入您要查找的數字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的數字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“請您輸入數據: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(“請輸入關鍵字的個數：”);scanf(“%d”,&n);printf(“排序類型：n”);printf(“1.選擇排序n”);printf(“2.插入排序n”);printf(“請選擇：”);scanf(“%d”,&b);switch(b){ case 1: printf(“請輸入關鍵字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“請輸入關鍵字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及結果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、實驗運行結果 1.二叉排序樹的創建、遍歷和查找刪除算法 2、冒泡排序和折半查找算法 3、簡單選擇排序和簡單插入排序算法 七、心得體會 通過本次的數據結構課程設計報告，掌握了查找和排序的幾種基本排序算法，了解了他們各自的特點和優缺點，完成了對于他們C語言的描述和實際應用，對他們有了一個更加具體、深刻的認識，同時也鍛煉了我們的邏輯思維能力和動手實踐能力，使我們受益匪淺，給我們今后的計算機專業課程學習帶來很大的幫助。 中班數學活動：《有趣的排序》 活動目標： 1、通過觀察、嘗試，引導幼兒發現規律，并對2種顏色進行各種有規律的排序。 2、在操作活動中，進一步提高孩子發現問題、解決問題的能力及發散性思維能力。 3、在游戲活動中，讓幼兒感受排序的趣味性。活動準備： 1、PPT，黑板，自制圖片。 2、各種排列規律的卡片。活動過程： （一）圖片導入，自由探索。 觀察、討論圖片上不同的變化，說說它們的排列規律。 師：今天，王老師帶來幾張神奇的圖片，請你看一看，找一找，這三張圖片的神奇之處在哪里？（出示三張不同變化規律的圖片，激發幼兒興趣。） 幼兒：通過觀察，自由發言，找出圖片規律。 （二）初步感受規律，嘗試按物體顏色規律排序。 師：十一國慶假期，小朋友們和爸爸媽媽都去哪里旅游了？那你們是怎么去的呀？（火車、汽車......） 老師也去旅游了，你們看老師是怎么去的？（火車） 1、出示火車圖片的排列，讓幼兒感知物體排列的次序規律。學習按顏色間隔排列的方法。 2、請幼兒補規律。找出卡片上物體的規律，想想接著應該排什么？ 3、幼兒動手操作，把缺的補上去，將規律補完整，并說說為什么要這樣補。 （三）嘗試按規律排序，動手操作。 師：旅游景點到了，我們先要將車子放到停車場里，然后再去游玩。請你來觀察，停車場里有什么規律？ 幼兒說一說自己的想法。（幼兒一邊回答，教師一邊操作，并引導孩子將規律說出來） （四）自主嘗試設計規律，將兩種顏色的花瓶有規律的排序。 師：說了這么多規律，現在請小朋友們自己動手試一試，老師給你們準備了漂亮的花瓶，請你們按照規律來排一排。聽清楚要求：從頭到尾堅持一種規律。 幼兒自選操作活動，教師巡回指導。鼓勵幼兒大膽地嘗試進行有規律的排列。 請幼兒介紹自己是按什么規律排列的。 （五）按規律排隊 師：我們能不能像剛才排列花瓶一樣，按照一種規律來排隊呢？ 幼兒自己說一說自己的想法。幼兒根據規律排隊。 查找資料 教學目標： ①知識與技能 掌握運用Inter網收集資料的方法 讓學生學會使用“百度”搜索引擎搜索資料 ②過程與方法 利用完成任務練習，培養學生在網上迅速搜集信息，整理篩選信息的能力 ③情感態度 讓學生養成正確的網絡道德意識 讓學生養成保護環境的環保意識 教學過程 ㈠導入 T：在我們的學習與生活中，都需要查找各種資料，那么同學們都是利用什么工具來查找資料的呢？ S： T：的確（我們還可以利用因特網），因特網不僅提供豐富的信息資料，還提供方便快捷的查找方法 T：在因特網上有許多專業機構專門對某一領域的信息建立資源網站，為人們提供專業的信息資源服務，那么今天我們就來學習如何查找資料 ㈡過程 活動一：查找“恐龍”的科普知識 T：大家有沒有聽說過“恐龍”呢？ S： T：是不是，覺得恐龍是很神秘的動物呢，那么今天我們就來查找一些恐龍的資料 T：那么在查找有關恐龍的資料之前，首先我們先來認識一個網站：中國科普博覽網 T：現在，同學們先看老師操作：啟動IE瀏覽器，找到地址欄，輸入網址，按enter鍵或者轉到，就打開了中國科普博覽的首頁，打開首頁，里面有很多的資料，包含了很多方面的知識，當我們的鼠標在首頁移動的時候，會發現光標的樣式會發生變化，當它發生變化時就說明它是一個超級鏈接，現在點擊“生命奧秘”，然后找到“恐龍”就找到了有關恐龍的知識資料了 T：同學都會了沒有，好接下來就請同學們用老師剛才的那個方法，查 找有關“計算機病毒”方面的科普知識，閱讀里面的內容。不會的同學可以看老師ppt的步驟 T： 同學們的任務都完成了沒有？沒有的話，等下再操作了，現在我們進入下一個活動 活動二：查找有關“酸雨”的信息 T：當我們不知道要查找的資料應該用具體的哪個網站時，我們該用生命辦法來查找資料呢？ S： T：我們還可以利用專門的因特網上搜索網頁網址的搜索網站，下面我們先介紹幾個常用的搜索引擎 T：那么下面我們就以百度搜索引擎為例，通過百度查找關于“酸雨”的資料 T：動IE瀏覽器，在地址欄輸入百度網址，按enter進入首頁，其次要找到搜索引擎的位置，在文本框中輸入關鍵詞“酸雨”點擊百度一下，百度搜索網站就會根據關鍵詞，在因特網上進行搜索，接著的頁面就是顯示這個詞的網頁標題以及簡要信息，點擊其中的一個標題，就可以打開該網頁，查看具體信息了 T：那么如果輸入的關鍵詞太簡單了，搜索出來的往往會不符合我們的要求，要是逐一查看去篩選就會浪費很多時間，那要怎么辦呢？ S： T：那么我們可以將滾動條往下拉，下面有一個相關搜索欄，可以看到有列出符合我們要求的關鍵詞，這樣再進行搜索的結果就會更加的準確 T： 那么接下來同學們打開百度搜索網站，查找“蚯蚓”和成語“兵不厭詐”的有關資料，等下請同學起來說一下。不會的同學可以看老師ppt上面的步驟。 ㈢總結： 那么我們今天學習了如何查找資料，同時在不懂具體網站時還可以利用其他搜索引擎，例如百度搜索，來查找我們所需要的資料第二篇：數據結構實驗報告-排序與查找
第三篇：數據結構課程設計-查找排序
第四篇：排序教案
第五篇：查找資料教案
點擊咨詢 