第一篇:數據結構-實驗8查找的算法
8.1 實現順序查找的算法
一,實驗目的
1.熟悉掌握各種查找方法,深刻理解各種查找算法及其執行的過程; 2.學會分析各種查找算法的性能。
二,實驗內容
8.1 實現順序查找的算法
編寫一個程序,輸出在順序表{3,6,2,10,1,8,5,7,4,9}中采用順序查找法查找關鍵字5的結果。
8.2 實現折半查找算法
編寫一個程序,輸出在順序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找關鍵字9的結果。要求:(1)用非遞歸方法;(2)用遞歸方法。8.3 實現二叉排序樹的基本運算
編寫一個程序實現二叉排序樹的基本運算,并在此基礎上完成如下功能:(1)由{4,9,0,1,8,6,3,5,2,7}創建一個二叉排序樹bt;
(2)判斷bt是否為一棵二叉排序樹(提示:在遍歷過程中檢查是否符合二叉排序樹定義);
(3)采用非遞歸方法查找關鍵字為6的結點,并輸出其查找路徑(提示:查找過程中保留經過的結點信息,找到后順序輸出之)。8.4 實現哈希表的相關運算
編寫一個程序,實現哈希表的相關運算,并在此基礎上完成如下功能:
(1)建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12],哈希函數為H(k)=key % 11,并采用線性探測法解決沖突。輸出哈希表;(2)在上述哈希表中查找關鍵字為29的記錄;
(3)在上述哈希表中刪除關鍵字為77的記錄,再將其插入,然后輸出哈希表。要求:輸出格式
哈希地址:0 1 2 ………..12 關鍵字值:……………………
三,源代碼及結果截圖
8.1 //實現順序查找的算法 #include
//定義表中最多記錄個數 typedef int KeyType;typedef int InfoType;typedef struct {
KeyType key;//KeyType為關鍵字的數據類型 InfoType data;//其他數據 } NodeType;
typedef NodeType SeqList[MAXL];
//順序表類型 int Search(SeqList R,int n,KeyType k)//順序查找算法
{ int i=0;while(i printf(“%d ”,R[i].key); i++; //從表頭往后找 } if(i>=n) return-1;else { printf(“%d”,R[i].key); return i;} } void main(){ SeqList R;int n=10;KeyType k=5;InfoType a[]={3,6,2,10,1,8,5,7,4,9};int i;for(i=0;i //建立順序表 R[i].key=a[i];printf(“查找結果:n”);if((i=Search(R,n,k))!=-1) printf(“n元素%d的位置是:%d”,k,i);else printf(“n元素%d不在表中n”,k);printf(“n”);} 8.2 //實現折半查找算法 #include //定義表中最多記錄個數 typedef int KeyType;typedef char InfoType[10];typedef struct { KeyType key; //KeyType為關鍵字的數據類型 InfoType data; //其他數據 } NodeType;typedef NodeType SeqList[MAXL]; //順序表類型 int BinSearch1(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) //繼續在R[low..mid-1]中查找 元 素 } } high=mid-1;else low=mid+1; //繼續在R[mid+1..high]中查找 return-1;int BinSearch2(SeqList R,KeyType k,int low,int high,int count)//遞歸二分查找算法 { int mid;if(low<=high){ mid=(low+high)/2;第%d 次 查 找 : 在[%d,%d] 中 查 找 到 元 素printf(“R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid;else if(R[mid].key>k) //繼續在R[low..mid-1]中查找 BinSearch2(R, k,low,mid-1,count);else BinSearch2(R, k,mid+1,high,count); //繼續在R[mid+1..high]中查找 } else 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 //建立順序表 printf(“用非遞歸方法:n”);if((i=BinSearch1(R,n,k))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k);printf(“用遞歸方法:n”);if((i=BinSearch2(R,k,0,9,0))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k); 8.3 //實現二叉排序樹的基本運算 #include int key; struct BTNode *lchild; struct BTNode *rchild;}BTNode;//定義二叉排序樹插入結點的算法 int BSTInsert(BTNode *&T,int k){ if(T==NULL) { T=(BTNode *)malloc(sizeof(BTNode)); T->lchild=T->rchild=NULL; T->key=k; return 1; } else { if(k==T->key) return 0; else if(k return BSTInsert(T->lchild, k); else return BSTInsert(T->rchild, k); } } //定義二叉排序樹的創建算法 BTNode *createBST(int k[],int n){ BTNode *T; T=NULL; for(int i=0;i<=n-1;i++){ BSTInsert(T,k[i]); } return T;} //判斷是否為二叉排序樹 Status Judge(BTNode *&T){ } //定義二叉排序樹的查找算法 BTNode *BSTSearch(BTNode *&T,int k){ if(T==NULL) return NULL; else if(T==NULL)return 1;else if((T>T->lchild)&&(T } else return 0;Judge(T->lchild);Judge(T->rchild); { printf(“%d ”,T->key); if(T->key==k) return T; else if(k { return BSTSearch(T->lchild, k); } else { return BSTSearch(T->rchild, k); } } } void main(){ int a[50]={4,9,0,1,8,6,3,5,2,7}; BTNode *bt=createBST(a,10); if(Judge(bt)==0)cout<<“bt不是二叉排序樹”< } 8.4 //實現哈希表的相關運算 #include //定義最大哈希表長度 #define NULLKEY 0 //定義空關鍵字值 #define DELKEY-1 //定義被刪關鍵字值 typedef int KeyType; //關鍵字類型 typedef char * InfoType;//其他數據類型 typedef struct { KeyType key;//關鍵字域 InfoType data; //其他數據域 int count; //探查次數域 } HashTable[MaxSize]; //哈希表類型 void InsertHT(HashTable ha,int *n,KeyType k,int p)中 { //將關鍵字k插入到哈希表 int i,adr;adr=k % p;if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中 } void CreateHT(HashTable ha,KeyType x[],int n,int m,int p)//創建哈希表 { } else { } n++;i=1;do { adr=(adr+1)% p;i++; //i記錄x[j]發生沖突的次數 //發生沖突時采用線性探查法解決沖突 ha[adr].key=k;ha[adr].count=1;} while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);ha[adr].key=k;ha[adr].count=i; { int i,n1=0;for(i=0;i //哈希表置初值 { ha[i].key=NULLKEY; ha[i].count=0; } } int SearchHT(HashTable ha,int p,KeyType k){ int i=0,adr;adr=k % p;while(ha[adr].key!=NULLKEY && ha[adr].key!=k){ } if(ha[adr].key==k)return adr; //查找失敗 //查找成功 i++; //采用線性探查法找下一個地址 //在哈希表中查找關鍵字k for(i=0;i } return-1;int DeleteHT(HashTable ha,int p,int k,int *n)//刪除哈希表中關鍵字k { } void DispHT(HashTable ha,int n,int m) //輸出哈希表 { float avg=0;int i;printf(“ 哈希表地址:t”);for(i=0;i } else //在哈希表中未找到該關鍵字 ha[adr].key=DELKEY;n--; //哈希表長度減1 //在哈希表中找到該關鍵字 return 1;return 0; printf(“ n”); printf(“ 哈希表關鍵字:t”); for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //輸出3個空格 else printf(“ %3d”,ha[i].key);printf(“ n”);printf(“ 搜索次數:t”);for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //輸出3個空格 else printf(“ %3d”,ha[i].count);printf(“ n”); for(i=0;i } if(ha[i].key!=NULLKEY && ha[i].key!=DELKEY)avg=avg+ha[i].count;avg=avg/n;printf(“平均搜索長度ASL(%d)=%gn”,n,avg); void main(){ int x[]={16,74,60,43,54,90,46,31,29,88,77};int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf(“n”);DispHT(ha,n,m);printf(“ 查找關鍵字29:n”);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k);k=77;printf(“ 刪除關鍵字%dn”,k);DeleteHT(ha,p,k,&n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k); } printf(“ 插入關鍵字%dn”,k);InsertHT(ha,&n,k,p);DispHT(ha,n,m);printf(“n”); 四,實驗小結 1、通過本次實驗,加深了我對查找表的認識。 2、有序表的查找之折半查找:前提必須是有序表,性能只有在均勻分布的時候才是最優的。 3、二叉排序樹查找:通過一系列的查找和插入過程形成的樹。之所以叫做排序樹,因為按照中序遍歷可得一個有序的序列。 實驗五 查找算法 實驗項目:必做:順序查找、折半查找 選做:二叉查找樹 實驗類型: 驗證性 實驗內容: 順序查找:用數組或鏈表實現,數據有序或無序均可; 折半查找:必須用數組實現,且數據有序; 注意:提交的實驗報告要顯示已有的數據元素、待查找的數據;應包含查找成功、不成功的情況。 《數據結構》 第八次實驗報告 學生姓名 學生班級 學生學號 指導老師 重慶郵電大學計算機學院 計算機專業實驗中心 一、實驗內容 1)有序表的二分查找 ?建立有序表,然后進行二分查找 2)二叉排序樹的查找 ?建立二叉排序樹,然后查找 二、需求分析 二分查找的基本思想是將n個元素分成大致相等的兩部分,取a[n/2]與x做比較,如果x=a[n/2],則找到x,算法中止;如果xa[n/2],則只要在數組a的右半部搜索x.時間復雜度無非就是while循環的次數!總共有n個元素,漸漸跟下去就是n,n/2,n/4,....n/2^k(接下來操作元素的剩余個數),其中k就是循環的次數 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,(是以2為底,n的對數)所以時間復雜度可以表示O()=O(logn)下面提供一段二分查找實現的偽代碼: BinarySearch(max,min,des)mid-<(max+min)/2 while(min<=max)mid=(min+max)/2 if mid=des then return mid elseif mid >des then max=mid-1 else min=mid+1 return max 折半查找法也稱為二分查找法,它充分利用了元素間的次序關系,采用分治策略,可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是,將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/2]則找到x,算法終止。如 果xa[n/2],則我們只要在數組a的右 半部繼續搜索x。 三、概要設計 1、順序查找,在順序表R[0..n-1]中查找關鍵字為k的記錄,成功時返回找到的記錄位置,失敗時返回-1,具體的算法如下所示: int SeqSearch(SeqList R,int n,KeyType k){ } int i=0;while(i } if(i>=n){ } printf(“%d”,R[i].key);return i;return-1;else printf(“%d”,R[i].key);i++; 2、二分查找,在有序表R[0..n-1]中進行二分查找,成功時返回記錄的位置,失敗時返回-1,具體的算法如下: int BinSearch(SeqList R,int n,KeyType k){ } return-1;} 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;high=mid-1;low=mid+1;if(R[mid].key>k)else 四、詳細設計 源代碼: #include static int a[1024],count=0; void Find1(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid]>x)Find1(low,mid-1,x);else if(a[mid] void Find2(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid] 五、心得體會 通過這次在實現順序和二分查找算法的過程中,讓我對順序和二分查找算法有了更多的了解。查找根據給定的某個值,在查找表中確定一個其關鍵字等于給定值的數據元素或(記錄)的操作,應用十分廣泛。順序查找是一種最簡單的查找方法。它的基本思路是:從表的一端開始,順序掃描線性表,依次將掃描到的關鍵字和給定值k相比較,若當前掃描到的關鍵字與k相等,則查找成功;若掃描結束后,仍未找到關鍵字等于k的記錄,則查找失敗。二分查找也稱為折半查找要求線性表中的結點必須己按關鍵字值的遞增或遞減順序排列。它首先用要查找的關鍵字k與中間位置的結點的關鍵字相比較,這個中間結點把線性表分成了兩個子表,若比較結果相等則查找完成;若不相等,再根據k與該中間結點關鍵字的比較大小確定下一步查找哪個子表,這樣遞歸進行下去,直到找到滿足條件的結點或者該線性表中沒有這樣的結點。在學習過程中,善于發現,會找到更多的捷徑。 六、附錄 運行結果截圖。 金陵科技學院實驗報告 學 生 實 驗 報 告 冊 課程名稱: 學生學號: 所屬院部: (理工類) 算法與數據結構 專業班級: 13網絡工程 1305106009 學生姓名: 陳韜 網絡與通信工程學院 指導教師: 沈奇 14 ——20 15 學年 第 1 學期 金陵科技學院教務處制 金陵科技學院實驗報告 實驗報告書寫要求 實驗報告原則上要求學生手寫,要求書寫工整。若因課程特點需打印的,要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。 實驗報告書寫說明 實驗報告中一至四項內容為必填項,包括實驗目的和要求;實驗儀器和設備;實驗內容與過程;實驗結果與分析。各院部可根據學科特點和實驗具體要求增加項目。 填寫注意事項 (1)細致觀察,及時、準確、如實記錄。(2)準確說明,層次清晰。 (3)盡量采用專用術語來說明事物。 (4)外文、符號、公式要準確,應使用統一規定的名詞和符號。(5)應獨立完成實驗報告的書寫,嚴禁抄襲、復印,一經發現,以零分論處。 實驗報告批改說明 實驗報告的批改要及時、認真、仔細,一律用紅色筆批改。實驗報告的批改成績采用百分制,具體評分標準由各院部自行制定。 實驗報告裝訂要求 實驗批改完畢后,任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學號升序排列,裝訂成冊,并附上一份該門課程的實驗大綱。 金陵科技學院實驗報告 實驗項目名稱: 順序表 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗1 順序表 一、實驗目的和要求 掌握順序表的定位、插入、刪除等操作。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)編寫程序建立一個順序表,并逐個輸出順序表中所有數據元素的值。編寫主函數測試結果。 (2)編寫順序表定位操作子函數,在順序表中查找是否存在數據元素x。如果存在,返回順序表中和x值相等的第1個數據元素的序號(序號從0開始編號);如果不存在,返回-1。編寫主函數測試結果。(3)在遞增有序的順序表中插入一個新結點x,保持順序表的有序性。 解題思路:首先查找插入的位置,再移位,最后進行插入操作;從第一個元素開始找到第一個大于該新結點值x的元素位置i即為插入位置;然后將從表尾開始依次將元素后移一個位置直至元素i;最后將新結點x插入到i位置。 (4)刪除順序表中所有等于X的數據元素。 2、選做題 (5)已知兩個順序表A和B按元素值遞增有序排列,要求寫一算法實現將A和B歸并成一個按元素值遞減有序排列的順序表(允許表中含有值相同的元素)。 程序清單: #include 金陵科技學院實驗報告 } sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技學院實驗報告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技學院實驗報告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技學院實驗報告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技學院實驗報告 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 單鏈表 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗2 單鏈表 一、實驗目的和要求 1、實驗目的 掌握單鏈表的定位、插入、刪除等操作。 2、實驗要求 (1)注意鏈表的空間是動態分配的,某結點不用之后要及時進行物理刪除,以便釋放其內存空間。 (2)鏈表不能實現直接定位,一定注意指針的保存,防止丟失。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)編寫程序建立一個單鏈表,并逐個輸出單鏈表中所有數據元素。(2)在遞增有序的單鏈表中插入一個新結點x,保持單鏈表的有序性。 解題思路:首先查找插入的位置然后進行插入操作;從第一個結點開始找到第一個大于該新結點值的結點即為插入位置;然后在找到的此結點之前插入新結點;注意保留插入位置之前結點的指針才能完成插入操作。 (3)編寫實現帶頭結點單鏈表就地逆置的子函數,并編寫主函數測試結果。 2、選做題 已知指針LA和LB分別指向兩個無頭結點單鏈表的首元結點。要求編一算法實現,從表LA中刪除自第i個元素起共len個元素后,將它們插入到表LB中第j個元素之前。程序清單: 金陵科技學院實驗報告 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 堆棧和隊列 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗3 堆棧和隊列 一、實驗目的和要求 (1)掌握應用棧解決問題的方法。(2)掌握利用棧進行表達式求和的算法。 (3)掌握隊列的存儲結構及基本操作實現,并能在相應的應用問題中正確選用它們。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)判斷一個算術表達式中開括號和閉括號是否配對。(2)測試“漢諾塔”問題。 (3)假設稱正讀和反讀都相同的字符序列為”回文”,試寫一個算法判別讀入的一個以’@’為結束符的字符序列是否是“回文”。 2、選做題 在順序存儲結構上實現輸出受限的雙端循環隊列的入列和出列算法。設每個元素表示一個待處理的作業,元素值表示作業的預計時間。入隊列采取簡化的短作業優先原則,若一個新提交的作業的預計執行時間小于隊頭和隊尾作業的平均時間,則插入在隊頭,否則插入在隊尾。程序清單: 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 金陵科技學院實驗報告 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 串 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗4 串 一、實驗目的和要求 掌握串的存儲及應用。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)編寫輸出字符串s中值等于字符ch的第一個字符的函數,并用主函數測試結果。 (2)編寫輸出字符串s中值等于字符ch的所有字符的函數,并用主函數測試結果。 解題思路:可以將第一題程序改進成一個子函數,在本題中循環調用。(3)設字符串采用單字符的鏈式存儲結構,編程刪除串s從位置i開始長度為k的子串。 2、選做題 假設以鏈結構表示串,編寫算法實現將串S插入到串T中某個字符之后,若串T中不存在這個字符,則將串S聯接在串T的末尾。 提示:為提高程序的通用性,插入位置字符應設計為從鍵盤輸入。程序清單: 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 金陵科技學院實驗報告 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 二叉樹 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗5 二叉樹 一、實驗目的和要求 (1)掌握二叉樹的生成,以及前、中、后序遍歷算法。(2)掌握應用二叉樹遞歸遍歷思想解決問題的方法。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷,輸出遍歷序列。 (2)在第一題基礎上,求二叉樹中葉結點的個數。(3)在第一題基礎上,求二叉樹中結點總數。(4)在第一題基礎上,求二叉樹的深度。 2、選做題 已知一棵完全二叉樹存于順序表sa中,sa.elem[1…sa.last]存儲結點的值。試編寫算法由此順序存儲結構建立該二叉樹的二叉鏈表。 解題思路:根據完全二叉樹順序存儲的性質來確定二叉樹的父子關系即“還原”了二叉樹,之后再按照二叉樹二叉鏈表的構造方法進行建立。完全二叉樹順序存儲的一個重要性質為,第i個結點的左孩子是編號為2i的結點,第i個結點的右孩子是編號為2i+1的結點。程序清單: 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 金陵科技學院實驗報告 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 圖 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗6 圖 一、實驗目的和要求 (1)熟練掌握圖的基本概念、構造及其存儲結構。 (2)熟練掌握對圖的深度優先搜索遍歷和廣度優先搜索遍歷的算法。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)構造一個無向圖(用鄰接矩陣表示存儲結構)。 (2)對上面所構造的無向圖,進行深度優先遍歷和廣度優先遍歷,輸出遍歷序列。 2、選做題 采用鄰接表存儲結構,編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復頂點的路徑。提示:兩個頂點及k值均作為參數給出。程序清單: 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 排序 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗7 排序 一、實驗目的和要求 (1)熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數排序的基本概念。 (2)掌握以上各種排序的算法。區分以上不同排序的優、缺點。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 用隨機數產生100000個待排序數據元素的關鍵字值。測試下列各排序函數的機器實際執行時間(至少測試兩個):直接插入排序、希爾排序(增量為4,2,1)、冒泡排序、快速排序、直接選擇排序、堆排序。 2、選做題 假設含n個記錄的序列中,其所有關鍵字為值介于v和w之間的整數,且其中很多關鍵字的值是相同的。則可按如下方法排序:另設數組number[v…w],令number[i]統計關鍵字為整數i的紀錄個數,然后按number重排序列以達到有序。試編寫算法實現上述排序方法,并討論此種方法的優缺點。程序清單: 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 金陵科技學院實驗報告 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 金陵科技學院實驗報告 實驗項目名稱: 查找 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間: 金陵科技學院實驗報告 實驗8 查找 一、實驗目的和要求 (1)掌握順序表查找、有序表查找、索引順序表查找的各種算法。(2)掌握哈希表設計。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)在一個遞增有序的線性表中利用二分查找法查找數據元素X。 2、選做題 (2)構造一個哈希表,哈希函數采用除留余數法,哈希沖突解決方法采用鏈地址法。設計一個測試程序進行測試。 提示:構造哈希表只是完成查找的第一步,大家應該掌握在哈希表上進行查找的過程,可以試著編程序實現。程序清單: 金陵科技學院實驗報告 四、實驗結果與分析(程序運行結果及其分析) 五、實驗體會(遇到問題及解決辦法,編程后的心得體會) 北 京 郵 電 大 學 計 算 機 科 學 與 技 術 學 院 算 法 與 數 據 結 構 實 驗 指 導 書 楊俊、徐塞虹、漆濤 編著 2006年9月 算法與數據結構 實驗指導書 目錄 實驗要求....................................................................................................................................3 試驗 一、約瑟夫環..............................................................................…………………..……4 試驗 二、長整數四則運算運算………………………………………………………………4 實驗三、八皇后.....................................……..........................................................................5 實驗 四、騎士遍歷......................................……………………..............................................5 實驗 五、桌面計算器...............................……………..............................................................6 實驗 六、平衡排序二叉樹....................…...…….....................................................................6 試驗 七、多重集合的實現……......................................………………………………………7 試驗 八、圖論………………………………………………………………………….……..8 實驗 八、內部排序性能的比較..........………………….............................................................8 教材及主要參考文獻………………………………………………………………………………..9 2 北京郵電大學 計算機科學與技術學院 算法與數據結構 實驗指導書 實驗要求 一、本課程在講課期間需要做上機實驗,目的之一是檢查學生對所學算法的掌握和理解程度;其次是鍛煉學生的團隊合作精神。 二、成績: 1、編碼:占整個實驗成績的50%; 2、測試:占整個實驗成績的20%; 3、文檔:占整個實驗成績的30%。 三、按時提交上機文檔,實驗文檔包含以下各項: 1、問題描述:實驗題目、內容和要求; 2、算法思路:實驗小組對問題的解決方法的文字描述; 3、算法描述:用類算法語言等對算法進行描述; 4、源程序及驅動程序:上機實驗編制的代碼源程序及程序運行環境; 5、測試數據:對算法的測試用例; 6、結果分析和結論:對算法及測試結果的分析及結論; 7、心得體會:通過實驗獲得的心得體會; 8、分工及簽名:最后是小組成員的分工及簽名。 北京郵電大學 計算機科學與技術學院-1-算法與數據結構 實驗指導書 實驗 一、約瑟夫環 一、實驗類別:設計型實驗。 二、問題描述:約瑟夫環問題是:n個人p0,p1,…pn 圍坐成一個圓環。每個人pk持有一個秘密的數字ck。0 < ck <= m。開始時隨機選取一個數 c = c0。每個人從p0 開始從1開始報數。報到數c 的人出對。然后以出隊的人的秘密數字作為新的c 值。從出隊者的下一個人順時針從1 開始再報數。直到所有的人全部出隊。 三、實驗目的:檢查學生對各種線性表的實現的掌握程度。 四、實驗學時:2小時 五、實驗組人數:1人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):各種隊列的實現。 八、實驗內容和要求:至少用3種以上的線性表來完成此試驗。可以在帶頭節點的和不帶頭節點的線性表、循環的和非循環線性表、動態鏈表和靜態鏈表以及向量(數組)之間選擇三種。從空表開始,為每個人生成一個隨機數。然后將此人加入到線性表之中。 九、可研究與探索的問題:給出各種實現的優缺點比較。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出各種線性表實現的優缺點分析。 實驗 二、長整數四則運算 一、實驗類別:驗證實驗。 二、問題描述:計算機CPU本身可以做32位或者64位的整數四則運算。本試驗要求對任意大小的整數實現其四則運算。將一個整數N表示為 N = ±(d0 + d1*B + d2*B2 + ….+ bk*Bk) 其中 1< B <= 256 為一個取定的整數。0 <= dk < B。用線性表存儲{bk}。給出整數的四則運算程序。 三、實驗目的:對具體的問題選擇適當的線性表實現。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):各種隊列的實現。 八、實驗內容和要求:至少用2種以上的線性表來完成此試驗。比較不同線性表實現的速度。 九、可研究與探索的問題:1)對具體問題選擇合適的線性表實現。2)B 的選取問題。可 否選擇更大的基B。B的選擇所應考慮的因素。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。能夠得出用向量(數組)實現的線性表速度最快。 實驗三、八皇后問題 一、實驗類別:設計型實驗。 二、問題描述:在n*n 的國際象棋棋盤上放置n個皇后,使每個皇后不受其他皇后的攻擊。 三、實驗目的:檢查學生對堆棧和遞歸程序掌握程度。 四、實驗學時:2小時 五、實驗組人數:1人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):遞歸程序與堆棧 八、實驗內容和要求: 分別用遞歸和堆棧完成此試驗。統計程序運行時間與問題規模n 的關系。 九、可研究與探索的問題:問題的復雜度。當n 比較大時,討論提高程序運行的方法。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。 實驗 四、騎士遍歷 一、實驗類別:設計型實驗。 二、問題描述:在國際象棋n*n的棋盤中,一匹馬從棋盤中任意一格出發,要求用n2-1步走完所有的n2個格子。每個格子走且只走過一次。應如何走? 試給出算法實現。 三、實驗目的:檢查學生對堆棧與回溯算法的掌握。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):堆棧與回溯 八、實驗內容和要求:用堆棧完成此試驗。統計程序運行時間與問題規模n 的關系。 九、可研究與探索的問題:怎樣枚舉所有馬下一步可走的位置。選擇下一步所走位置的策略。注意由于這個程序非常耗時,在初期程序調試時應取較小的n。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。給出不同選擇策略的程序運行 速度的比較結果。 實驗 五、桌面計算器(表達式求值) 一、實驗類別:設計型實驗。 二、問題描述:模仿Unix系統下的dc命令。輸入表達式字符串,按回車鍵后給出表達式的值。操作數為實數。 1)操作符有 “+”、“-”、“*”、“/”、“^”(乘方) 2)還可以有臨時變量。用法如 pi = 3.1415926,r = 3, r*pi^2 3)還可以有事先定義的函數如:“sin()”(正弦)、“cos()”(余弦)、“log()”(對數)、“ln()”(自然對數)等函數。 三、實驗目的:檢查學生用堆棧解決實際問題。為本課程后續的內容提供伏筆。也為后繼的課程如編譯原理預習。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):堆棧,線性表,命令行參數的處理。 八、實驗內容和要求:學生應至少應實現處理五個運算符:“+”、“-”、“*”、“/”、“^”(乘方)。可以用一個線性表來存儲臨時變量。另一個線性表來存儲預定義的函數名。 九、可研究與探索的問題:查找臨時變量名的不同方法。如哈希表,二叉樹。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。 實驗 六、平衡排序二叉樹 一、實驗類別:設計型實驗。 二、問題描述:隨機生成一組整數p0,p1,…pn-1。將這組整數按生成的次序插入到一個平衡排序二叉樹中。然后將p0,p1,…pn-1隨機重新排列為q0,q1,…qn-1。再按照次次序將這些整數從生成的平衡排序二叉樹刪除。 三、實驗目的:平衡排序二叉樹的插入和刪除。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):平衡排序二叉樹的插入和刪除中的旋轉。 八、實驗內容和要求:統計在平衡排序二叉樹的插入和刪除過程中各種旋轉的出現次數。 九、可研究與探索的問題:研究平衡排序二叉樹與一般的排序二叉樹在插入和刪除方面的性能比較。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下,平衡排序二叉樹與一般排序二叉樹的性能比較。 實驗 七、多重集合的實現 一、實驗類別:設計型實驗。 二、問題描述:實現數學上多重集合。所謂的多重集合類似于集合,但是一件東西可以放置多個副本。就如一個菜籃子里面可以放兩個蘋果。 三、實驗目的:查找結構的各種實現。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):平衡排序二叉樹的插入和刪除、遍歷,查找。哈希查找結構。 八、實驗內容和要求: 假設集合中包含的元素是可以排序的。將多重集合封裝成一個類。具體的實現可以是中序線索化的平衡排序二叉樹,或者帶父節點指針的平衡排序二叉樹。多重集合的界面如下: template { Multi_set(void);//構造函數,初始化為空集合~Multi_set(void);//析構函數 Multi_set& operator=(Multi_set const a);//重載運算符= bool contains(T const& v)const;//如果集合包含v 則返回true,否則返回false Multi_set& operator+=(Multi_set const&a);//將集合a 并到自身中。 Multi_set& operator-=(Multi_set const& a);//自身減去集合a Multi_set& operator-=(T const& a);//自身減去一個元素a };//~class Multi_set //返回集合a,b的并 template //返回集合a,b的差 template //返回 a –{v} template Multi_set 九、可研究與探索的問題:哈希函數的選取。比較哈希與平衡排序二叉樹的優缺點、性能和速度。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出平衡排序二叉樹實現的多重集合和用哈希實現的多重集合的性能比較。 實驗 八、圖論 一、實驗類別:設計型實驗。 二、問題描述:實現圖論中的各種算法。 1)最小代價生成樹的Krscal 算法和Prim算法。2)單源點的最短路徑的Dijstra 算法。3)深度優先遍歷與廣度優先遍歷。4)拓撲排序 5)求所有節點之間的最短路徑Floyd算法 (在這五個小題中只要選作一個即可。) 三、實驗目的:學習根據不同的運算來選取不同的存儲結構。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):圖論中的各種算法及其復雜度。根據不同的操作來決定圖的存儲結構。 八、實驗內容和要求:至少實現上面五個小題目中的一個。從文件中讀入一個圖的信息。 九、可研究與探索的問題:高級數據結構如堆、并查集在圖論算法中的應用。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下,平衡排序二叉樹與一般排序二叉樹的性能比較。 實驗 九、內部排序性能的比較 一、實驗類別:設計型實驗。 二、問題描述:隨機生成一組整數p0,p1,…pn-1。對這組數據進行排序。 三、實驗目的:比較不同排序算法的性能。 四、實驗學時:2小時 五、實驗組人數:3人。 六、實驗設備環境:計算機。 七、實驗原理及要點(知識點):各種內部排序算法。 八、實驗內容和要求: 1)實現插入排序,選擇排序,希爾排序,堆排序以及快速排序。2)快速排序的多種版本。3)對單鏈表實現歸并排序。4)基數排序。 5)對小型問題(n = 10)、中型問題(n = 1000)以及大型問題(n = 1百萬)分別統計不同排序算法的鍵值比較次數、鍵值移動次數以及程序運行時間。 26)排序算法的時間復雜度可以有O(n)和 O(n log n)。對相同復雜度的算法,給出他們運行時間與時間復雜度的比值。 九、可研究與探索的問題:研究快速排序算法的不同改進方法。自省排序算法。只需要移動而不需要交換的快速排序方法。 十、驗收及實驗報告要求:現場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下,對大中小問題的最快的排序算法。 教材及主要參考文獻 [1] 嚴蔚敏、吳偉民,數據結構習題集,清華大學出版社,1999年 [2] John R.Hubbard, Data Structures with C++, China Machine Press, 2002.[3] Mark Allen Weiss, Data Structures and Problem Solving Using C++, 2ed, 清華大學出版社。2004年。[4] Robert Sedgewick,Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中國電力出版社,2003年。 [5] 嚴蔚敏、吳偉民,數據結構(C語言版),清華大學出版社,2006年第二篇:數據結構實驗指導(實驗五:查找算法)
第三篇:數據結構實驗報告-查找算法
第四篇:算法與數據結構實驗
第五篇:算法與數據結構實驗指導書