第一篇：數(shù)據(jù)結構實驗指導(實驗五：查找算法)
實驗五 查找算法
實驗項目：必做：順序查找、折半查找
選做：二叉查找樹 實驗類型: 驗證性 實驗內(nèi)容：
順序查找：用數(shù)組或鏈表實現(xiàn)，數(shù)據(jù)有序或無序均可； 折半查找：必須用數(shù)組實現(xiàn)，且數(shù)據(jù)有序；
注意：提交的實驗報告要顯示已有的數(shù)據(jù)元素、待查找的數(shù)據(jù)；應包含查找成功、不成功的情況。
第二篇：數(shù)據(jù)結構-實驗8查找的算法
8.1 實現(xiàn)順序查找的算法
一，實驗目的
1.熟悉掌握各種查找方法，深刻理解各種查找算法及其執(zhí)行的過程； 2.學會分析各種查找算法的性能。
二，實驗內(nèi)容
8.1 實現(xiàn)順序查找的算法
編寫一個程序，輸出在順序表{3,6,2,10,1,8,5,7,4,9}中采用順序查找法查找關鍵字5的結果。
8.2 實現(xiàn)折半查找算法
編寫一個程序，輸出在順序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找關鍵字9的結果。要求：（1）用非遞歸方法；（2）用遞歸方法。8.3 實現(xiàn)二叉排序樹的基本運算
編寫一個程序?qū)崿F(xiàn)二叉排序樹的基本運算，并在此基礎上完成如下功能：（1）由{4,9,0,1,8，6,3,5,2,7}創(chuàng)建一個二叉排序樹bt；
（2）判斷bt是否為一棵二叉排序樹（提示：在遍歷過程中檢查是否符合二叉排序樹定義）；
（3）采用非遞歸方法查找關鍵字為6的結點，并輸出其查找路徑（提示：查找過程中保留經(jīng)過的結點信息，找到后順序輸出之）。8.4 實現(xiàn)哈希表的相關運算
編寫一個程序，實現(xiàn)哈希表的相關運算，并在此基礎上完成如下功能：
（1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函數(shù)為H(k)=key % 11，并采用線性探測法解決沖突。輸出哈希表；（2）在上述哈希表中查找關鍵字為29的記錄；
（3）在上述哈希表中刪除關鍵字為77的記錄，再將其插入，然后輸出哈希表。要求：輸出格式
哈希地址：0 1 2 ………..12 關鍵字值：……………………
三，源代碼及結果截圖
8.1 //實現(xiàn)順序查找的算法 #include
//定義表中最多記錄個數(shù) typedef int KeyType;typedef int InfoType;typedef struct {
KeyType key;//KeyType為關鍵字的數(shù)據(jù)類型 InfoType data;//其他數(shù)據(jù) } 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 //實現(xiàn)折半查找算法 #include //定義表中最多記錄個數(shù) typedef int KeyType;typedef char InfoType[10];typedef struct { KeyType key; //KeyType為關鍵字的數(shù)據(jù)類型 InfoType data; //其他數(shù)據(jù) } 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) //繼續(xù)在R[low..mid-1]中查找 元 素 } } high=mid-1;else low=mid+1; //繼續(xù)在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) //繼續(xù)在R[low..mid-1]中查找 BinSearch2(R, k,low,mid-1,count);else BinSearch2(R, k,mid+1,high,count); //繼續(xù)在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 //實現(xiàn)二叉排序樹的基本運算 #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); } } //定義二叉排序樹的創(chuàng)建算法 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 //實現(xiàn)哈希表的相關運算 #include //定義最大哈希表長度 #define NULLKEY 0 //定義空關鍵字值 #define DELKEY-1 //定義被刪關鍵字值 typedef int KeyType; //關鍵字類型 typedef char * InfoType;//其他數(shù)據(jù)類型 typedef struct { KeyType key;//關鍵字域 InfoType data; //其他數(shù)據(jù)域 int count; //探查次數(shù)域 } 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)//創(chuàng)建哈希表 { } else { } n++;i=1;do { adr=(adr+1)% p;i++; //i記錄x[j]發(fā)生沖突的次數(shù) //發(fā)生沖突時采用線性探查法解決沖突 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(“ 搜索次數(shù):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、有序表的查找之折半查找：前提必須是有序表，性能只有在均勻分布的時候才是最優(yōu)的。 3、二叉排序樹查找：通過一系列的查找和插入過程形成的樹。之所以叫做排序樹，因為按照中序遍歷可得一個有序的序列。 金陵科技學院實驗報告 學 生 實 驗 報 告 冊 課程名稱： 學生學號： 所屬院部： （理工類） 算法與數(shù)據(jù)結構 專業(yè)班級： 13網(wǎng)絡工程 1305106009 學生姓名： 陳韜 網(wǎng)絡與通信工程學院 指導教師： 沈奇 14 ——20 15 學年 第 1 學期 金陵科技學院教務處制 金陵科技學院實驗報告 實驗報告書寫要求 實驗報告原則上要求學生手寫，要求書寫工整。若因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。 實驗報告書寫說明 實驗報告中一至四項內(nèi)容為必填項，包括實驗目的和要求；實驗儀器和設備；實驗內(nèi)容與過程；實驗結果與分析。各院部可根據(jù)學科特點和實驗具體要求增加項目。 填寫注意事項 （1）細致觀察，及時、準確、如實記錄。（2）準確說明，層次清晰。 （3）盡量采用專用術語來說明事物。 （4）外文、符號、公式要準確，應使用統(tǒng)一規(guī)定的名詞和符號。（5）應獨立完成實驗報告的書寫，嚴禁抄襲、復印，一經(jīng)發(fā)現(xiàn)，以零分論處。 實驗報告批改說明 實驗報告的批改要及時、認真、仔細，一律用紅色筆批改。實驗報告的批改成績采用百分制，具體評分標準由各院部自行制定。 實驗報告裝訂要求 實驗批改完畢后，任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學號升序排列，裝訂成冊，并附上一份該門課程的實驗大綱。 金陵科技學院實驗報告 實驗項目名稱： 順序表 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗1 順序表 一、實驗目的和要求 掌握順序表的定位、插入、刪除等操作。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結果。 （2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回－1。編寫主函數(shù)測試結果。（3）在遞增有序的順序表中插入一個新結點x，保持順序表的有序性。 解題思路：首先查找插入的位置，再移位，最后進行插入操作；從第一個元素開始找到第一個大于該新結點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結點x插入到i位置。 （4）刪除順序表中所有等于X的數(shù)據(jù)元素。 2、選做題 （5）已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將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）注意鏈表的空間是動態(tài)分配的，某結點不用之后要及時進行物理刪除，以便釋放其內(nèi)存空間。 （2）鏈表不能實現(xiàn)直接定位，一定注意指針的保存，防止丟失。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。（2）在遞增有序的單鏈表中插入一個新結點x，保持單鏈表的有序性。 解題思路：首先查找插入的位置然后進行插入操作；從第一個結點開始找到第一個大于該新結點值的結點即為插入位置；然后在找到的此結點之前插入新結點；注意保留插入位置之前結點的指針才能完成插入操作。 （3）編寫實現(xiàn)帶頭結點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結果。 2、選做題 已知指針LA和LB分別指向兩個無頭結點單鏈表的首元結點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單： 金陵科技學院實驗報告 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 堆棧和隊列 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗3 堆棧和隊列 一、實驗目的和要求 （1）掌握應用棧解決問題的方法。（2）掌握利用棧進行表達式求和的算法。 （3）掌握隊列的存儲結構及基本操作實現(xiàn)，并能在相應的應用問題中正確選用它們。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）判斷一個算術表達式中開括號和閉括號是否配對。（2）測試“漢諾塔”問題。 （3）假設稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以’@’為結束符的字符序列是否是“回文”。 2、選做題 在順序存儲結構上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 串 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗4 串 一、實驗目的和要求 掌握串的存儲及應用。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結果。 （2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結果。 解題思路：可以將第一題程序改進成一個子函數(shù)，在本題中循環(huán)調(diào)用。（3）設字符串采用單字符的鏈式存儲結構，編程刪除串s從位置i開始長度為k的子串。 2、選做題 假設以鏈結構表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。 提示：為提高程序的通用性，插入位置字符應設計為從鍵盤輸入。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 二叉樹 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗5 二叉樹 一、實驗目的和要求 （1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應用二叉樹遞歸遍歷思想解決問題的方法。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。 （2）在第一題基礎上，求二叉樹中葉結點的個數(shù)。（3）在第一題基礎上，求二叉樹中結點總數(shù)。（4）在第一題基礎上，求二叉樹的深度。 2、選做題 已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲結點的值。試編寫算法由此順序存儲結構建立該二叉樹的二叉鏈表。 解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構造方法進行建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結點的左孩子是編號為2i的結點，第i個結點的右孩子是編號為2i+1的結點。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 圖 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗6 圖 一、實驗目的和要求 （1）熟練掌握圖的基本概念、構造及其存儲結構。 （2）熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）構造一個無向圖（用鄰接矩陣表示存儲結構）。 （2）對上面所構造的無向圖，進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。 2、選做題 采用鄰接表存儲結構，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復頂點的路徑。提示：兩個頂點及k值均作為參數(shù)給出。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 排序 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗7 排序 一、實驗目的和要求 （1）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。 （2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 用隨機數(shù)產(chǎn)生100000個待排序數(shù)據(jù)元素的關鍵字值。測試下列各排序函數(shù)的機器實際執(zhí)行時間（至少測試兩個）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、堆排序。 2、選做題 假設含n個記錄的序列中，其所有關鍵字為值介于v和w之間的整數(shù)，且其中很多關鍵字的值是相同的。則可按如下方法排序：另設數(shù)組number[v…w]，令number[i]統(tǒng)計關鍵字為整數(shù)i的紀錄個數(shù)，然后按number重排序列以達到有序。試編寫算法實現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 查找 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗8 查找 一、實驗目的和要求 （1）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設計。 二、實驗儀器和設備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）在一個遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。 2、選做題 （2）構造一個哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設計一個測試程序進行測試。 提示：構造哈希表只是完成查找的第一步，大家應該掌握在哈希表上進行查找的過程，可以試著編程序?qū)崿F(xiàn)。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 北 京 郵 電 大 學 計 算 機 科 學 與 技 術 學 院 算 法 與 數(shù) 據(jù) 結 構 實 驗 指 導 書 楊俊、徐塞虹、漆濤 編著 2006年9月 算法與數(shù)據(jù)結構 實驗指導書 目錄 實驗要求....................................................................................................................................3 試驗 一、約瑟夫環(huán)..............................................................................…………………..……4 試驗 二、長整數(shù)四則運算運算………………………………………………………………4 實驗三、八皇后.....................................……..........................................................................5 實驗 四、騎士遍歷......................................……………………..............................................5 實驗 五、桌面計算器...............................……………..............................................................6 實驗 六、平衡排序二叉樹....................…...…….....................................................................6 試驗 七、多重集合的實現(xiàn)……......................................………………………………………7 試驗 八、圖論………………………………………………………………………….……..8 實驗 八、內(nèi)部排序性能的比較..........………………….............................................................8 教材及主要參考文獻………………………………………………………………………………..9 2 北京郵電大學 計算機科學與技術學院 算法與數(shù)據(jù)結構 實驗指導書 實驗要求 一、本課程在講課期間需要做上機實驗，目的之一是檢查學生對所學算法的掌握和理解程度；其次是鍛煉學生的團隊合作精神。 二、成績： 1、編碼：占整個實驗成績的50%； 2、測試：占整個實驗成績的20%； 3、文檔：占整個實驗成績的30%。 三、按時提交上機文檔，實驗文檔包含以下各項： 1、問題描述：實驗題目、內(nèi)容和要求； 2、算法思路：實驗小組對問題的解決方法的文字描述； 3、算法描述：用類算法語言等對算法進行描述； 4、源程序及驅(qū)動程序：上機實驗編制的代碼源程序及程序運行環(huán)境； 5、測試數(shù)據(jù)：對算法的測試用例； 6、結果分析和結論：對算法及測試結果的分析及結論； 7、心得體會：通過實驗獲得的心得體會； 8、分工及簽名：最后是小組成員的分工及簽名。 北京郵電大學 計算機科學與技術學院-1-算法與數(shù)據(jù)結構 實驗指導書 實驗 一、約瑟夫環(huán) 一、實驗類別：設計型實驗。 二、問題描述：約瑟夫環(huán)問題是：n個人p0,p1,…pn 圍坐成一個圓環(huán)。每個人pk持有一個秘密的數(shù)字ck。0 < ck <= m。開始時隨機選取一個數(shù) c = c0。每個人從p0 開始從1開始報數(shù)。報到數(shù)c 的人出對。然后以出隊的人的秘密數(shù)字作為新的c 值。從出隊者的下一個人順時針從1 開始再報數(shù)。直到所有的人全部出隊。 三、實驗目的：檢查學生對各種線性表的實現(xiàn)的掌握程度。 四、實驗學時：2小時 五、實驗組人數(shù)：1人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：各種隊列的實現(xiàn)。 八、實驗內(nèi)容和要求：至少用3種以上的線性表來完成此試驗。可以在帶頭節(jié)點的和不帶頭節(jié)點的線性表、循環(huán)的和非循環(huán)線性表、動態(tài)鏈表和靜態(tài)鏈表以及向量（數(shù)組）之間選擇三種。從空表開始，為每個人生成一個隨機數(shù)。然后將此人加入到線性表之中。 九、可研究與探索的問題：給出各種實現(xiàn)的優(yōu)缺點比較。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出各種線性表實現(xiàn)的優(yōu)缺點分析。 實驗 二、長整數(shù)四則運算 一、實驗類別：驗證實驗。 二、問題描述：計算機CPU本身可以做32位或者64位的整數(shù)四則運算。本試驗要求對任意大小的整數(shù)實現(xiàn)其四則運算。將一個整數(shù)N表示為 N = ±(d0 + d1*B + d2*B2 + ….+ bk*Bk) 其中 1< B <= 256 為一個取定的整數(shù)。0 <= dk < B。用線性表存儲{bk}。給出整數(shù)的四則運算程序。 三、實驗目的：對具體的問題選擇適當?shù)木€性表實現(xiàn)。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：各種隊列的實現(xiàn)。 八、實驗內(nèi)容和要求：至少用2種以上的線性表來完成此試驗。比較不同線性表實現(xiàn)的速度。 九、可研究與探索的問題：1）對具體問題選擇合適的線性表實現(xiàn)。2）B 的選取問題?？?否選擇更大的基B。B的選擇所應考慮的因素。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。能夠得出用向量（數(shù)組）實現(xiàn)的線性表速度最快。 實驗三、八皇后問題 一、實驗類別：設計型實驗。 二、問題描述：在n*n 的國際象棋棋盤上放置n個皇后，使每個皇后不受其他皇后的攻擊。 三、實驗目的：檢查學生對堆棧和遞歸程序掌握程度。 四、實驗學時：2小時 五、實驗組人數(shù)：1人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：遞歸程序與堆棧 八、實驗內(nèi)容和要求： 分別用遞歸和堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關系。 九、可研究與探索的問題：問題的復雜度。當n 比較大時，討論提高程序運行的方法。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。 實驗 四、騎士遍歷 一、實驗類別：設計型實驗。 二、問題描述：在國際象棋n*n的棋盤中，一匹馬從棋盤中任意一格出發(fā)，要求用n2-1步走完所有的n2個格子。每個格子走且只走過一次。應如何走？ 試給出算法實現(xiàn)。 三、實驗目的：檢查學生對堆棧與回溯算法的掌握。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：堆棧與回溯 八、實驗內(nèi)容和要求：用堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關系。 九、可研究與探索的問題：怎樣枚舉所有馬下一步可走的位置。選擇下一步所走位置的策略。注意由于這個程序非常耗時，在初期程序調(diào)試時應取較小的n。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。找出程序運行速度的瓶頸。給出不同選擇策略的程序運行 速度的比較結果。 實驗 五、桌面計算器（表達式求值） 一、實驗類別：設計型實驗。 二、問題描述：模仿Unix系統(tǒng)下的dc命令。輸入表達式字符串，按回車鍵后給出表達式的值。操作數(shù)為實數(shù)。 1）操作符有 “+”、“-”、“*”、“/”、“^”（乘方） 2）還可以有臨時變量。用法如 pi = 3.1415926，r = 3, r*pi^2 3）還可以有事先定義的函數(shù)如：“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。 三、實驗目的：檢查學生用堆棧解決實際問題。為本課程后續(xù)的內(nèi)容提供伏筆。也為后繼的課程如編譯原理預習。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：堆棧，線性表，命令行參數(shù)的處理。 八、實驗內(nèi)容和要求：學生應至少應實現(xiàn)處理五個運算符：“+”、“-”、“*”、“/”、“^”（乘方）。可以用一個線性表來存儲臨時變量。另一個線性表來存儲預定義的函數(shù)名。 九、可研究與探索的問題：查找臨時變量名的不同方法。如哈希表，二叉樹。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。 實驗 六、平衡排序二叉樹 一、實驗類別：設計型實驗。 二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。將這組整數(shù)按生成的次序插入到一個平衡排序二叉樹中。然后將p0,p1,…pn－１隨機重新排列為q0,q1,…qn－１。再按照次次序?qū)⑦@些整數(shù)從生成的平衡排序二叉樹刪除。 三、實驗目的：平衡排序二叉樹的插入和刪除。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：平衡排序二叉樹的插入和刪除中的旋轉(zhuǎn)。 八、實驗內(nèi)容和要求：統(tǒng)計在平衡排序二叉樹的插入和刪除過程中各種旋轉(zhuǎn)的出現(xiàn)次數(shù)。 九、可研究與探索的問題：研究平衡排序二叉樹與一般的排序二叉樹在插入和刪除方面的性能比較。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。 實驗 七、多重集合的實現(xiàn) 一、實驗類別：設計型實驗。 二、問題描述：實現(xiàn)數(shù)學上多重集合。所謂的多重集合類似于集合，但是一件東西可以放置多個副本。就如一個菜籃子里面可以放兩個蘋果。 三、實驗目的：查找結構的各種實現(xiàn)。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：平衡排序二叉樹的插入和刪除、遍歷，查找。哈希查找結構。 八、實驗內(nèi)容和要求： 假設集合中包含的元素是可以排序的。將多重集合封裝成一個類。具體的實現(xiàn)可以是中序線索化的平衡排序二叉樹，或者帶父節(jié)點指針的平衡排序二叉樹。多重集合的界面如下： template { Multi_set(void);//構造函數(shù)，初始化為空集合~Multi_set(void);//析構函數(shù) 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 九、可研究與探索的問題：哈希函數(shù)的選取。比較哈希與平衡排序二叉樹的優(yōu)缺點、性能和速度。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出平衡排序二叉樹實現(xiàn)的多重集合和用哈希實現(xiàn)的多重集合的性能比較。 實驗 八、圖論 一、實驗類別：設計型實驗。 二、問題描述：實現(xiàn)圖論中的各種算法。 1）最小代價生成樹的Krscal 算法和Prim算法。2）單源點的最短路徑的Dijstra 算法。3）深度優(yōu)先遍歷與廣度優(yōu)先遍歷。4）拓撲排序 5）求所有節(jié)點之間的最短路徑Floyd算法 （在這五個小題中只要選作一個即可。） 三、實驗目的：學習根據(jù)不同的運算來選取不同的存儲結構。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：圖論中的各種算法及其復雜度。根據(jù)不同的操作來決定圖的存儲結構。 八、實驗內(nèi)容和要求：至少實現(xiàn)上面五個小題目中的一個。從文件中讀入一個圖的信息。 九、可研究與探索的問題：高級數(shù)據(jù)結構如堆、并查集在圖論算法中的應用。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。 實驗 九、內(nèi)部排序性能的比較 一、實驗類別：設計型實驗。 二、問題描述：隨機生成一組整數(shù)p0,p1,…pn－１。對這組數(shù)據(jù)進行排序。 三、實驗目的：比較不同排序算法的性能。 四、實驗學時：2小時 五、實驗組人數(shù)：3人。 六、實驗設備環(huán)境：計算機。 七、實驗原理及要點（知識點）：各種內(nèi)部排序算法。 八、實驗內(nèi)容和要求： 1）實現(xiàn)插入排序，選擇排序，希爾排序，堆排序以及快速排序。2）快速排序的多種版本。3）對單鏈表實現(xiàn)歸并排序。4）基數(shù)排序。 5）對小型問題（n = 10）、中型問題（n = 1000）以及大型問題（n = 1百萬）分別統(tǒng)計不同排序算法的鍵值比較次數(shù)、鍵值移動次數(shù)以及程序運行時間。 26）排序算法的時間復雜度可以有O(n)和 O(n log n)。對相同復雜度的算法，給出他們運行時間與時間復雜度的比值。 九、可研究與探索的問題：研究快速排序算法的不同改進方法。自省排序算法。只需要移動而不需要交換的快速排序方法。 十、驗收及實驗報告要求：現(xiàn)場操作及運行效果驗收。要求程序必須上機編譯通過并且正確運行。給出試驗報告。給出在均勻的隨機分布下，對大中小問題的最快的排序算法。 教材及主要參考文獻 [1] 嚴蔚敏、吳偉民，數(shù)據(jù)結構習題集，清華大學出版社，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] 嚴蔚敏、吳偉民，數(shù)據(jù)結構(C語言版)，清華大學出版社，2006年 金陵科技學院實驗報告 學 生 實 驗 報 告 冊 課程名稱： 學生學號： 所屬院部： （理工類） 算法與數(shù)據(jù)結構 專業(yè)班級： 14計單（2） 1413201007 學生姓名： 毛卓 計算機工程學院 指導教師： 章海鷗 16 ——20 17 學年 第 二 學期 金陵科技學院教務處制 金陵科技學院實驗報告 實驗報告書寫要求 實驗報告原則上要求學生手寫，要求書寫工整。若因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。 實驗報告書寫說明 實驗報告中一至四項內(nèi)容為必填項，包括實驗目的和要求；實驗儀器和設備；實驗內(nèi)容與過程；實驗結果與分析。各院部可根據(jù)學科特點和實驗具體要求增加項目。 填寫注意事項 （1）細致觀察，及時、準確、如實記錄。（2）準確說明，層次清晰。 （3）盡量采用專用術語來說明事物。 （4）外文、符號、公式要準確，應使用統(tǒng)一規(guī)定的名詞和符號。（5）應獨立完成實驗報告的書寫，嚴禁抄襲、復印，一經(jīng)發(fā)現(xiàn)，以零分論處。 實驗報告批改說明 實驗報告的批改要及時、認真、仔細，一律用紅色筆批改。實驗報告的批改成績采用百分制，具體評分標準由各院部自行制定。 實驗報告裝訂要求 實驗批改完畢后，任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學號升序排列，裝訂成冊，并附上一份該門課程的實驗大綱。 金陵科技學院實驗報告 實驗項目名稱： 順序表 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗1 順序表 一、實驗目的和要求 掌握順序表的定位、插入、刪除等操作。 二、實驗儀器和設備 VC6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結果。 （2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回－1。編寫主函數(shù)測試結果。（3）在遞增有序的順序表中插入一個新結點x，保持順序表的有序性。 解題思路：首先查找插入的位置，再移位，最后進行插入操作；從第一個元素開始找到第一個大于該新結點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結點x插入到i位置。 （4）刪除順序表中所有等于X的數(shù)據(jù)元素。 2、選做題 （5）已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。 程序清單： （1）:/*編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。*/ #include 金陵科技學院實驗報告 }sequenlist;void main(){ sequenlist L;int i,n;printf(“請輸入元素個數(shù)：”);scanf(“%d”,&n);printf(“n請輸入元素：”);for(i=0;i 如果不存在，返回－1。*/ #include int fun(sequenlist L,int x,int n){ 金陵科技學院實驗報告 } int i;for(i=0;i } int i,n,y;int x; printf(“請輸入元素個數(shù)：”);scanf(“%d”,&n);printf(“n請輸入元素：”);for(i=0;i printf(“n請輸入要查找的數(shù)據(jù)元素：”);scanf(“%d”,&x);y=fun(L,x,n);if(y==-1)else printf(“n數(shù)據(jù)元素 %d 所在的位置為 %d n”,x,y);printf(“n所要查找的數(shù)據(jù)元素不存在。n”);(3): /*在遞增有序的順序表中插入一個新結點x，保持順序表的有序性。 解題思路：首先查找插入的位置，再移位，最后進行插入操作； 從第一個元素開始找到第一個大于該新結點值x的元素位置i即為插入位置； 金陵科技學院實驗報告 然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結點x插入到i位置。*/ #define maxsize 100 typedef struct{ int data[maxsize]; int last;}sequenlist;main(){ int i,x,j; sequenlist l={{1,3,5,6,7,9},5}; printf(“n插入元素前的數(shù)據(jù)為:”); for(i=0;i<=l.last;i++) printf(“%2d”,l.data[i]); printf(“n請輸入要插入的元素:”); scanf(“%d”,&x); for(i=1;i<=l.last;i++) if(l.data[i-1]>x)break; if(i>l.last) { l.data [l.last +1]=x; } else { for(j=l.last;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x; } l.last++; printf(“插入元素后的數(shù)據(jù)為:n”); 金陵科技學院實驗報告 for(j=0;j<=l.last;j++) printf(“%3d”,l.data[j]); printf(“n”);}(4): /*刪除順序表中所有等于X的數(shù)據(jù)元素。*/ #define maxsize 100 typedef struct{ int data[maxsize]; int last;}sequenlist;main(){ int i,j,x=0,k=0; sequenlist L={{1,3,5,7,2,4,6,8,2,9},9}; printf(“n原數(shù)據(jù)為:”); for(i=0;i<=L.last;i++)printf(“%3d”,L.data[i]); printf(“n請輸入要刪除的數(shù)據(jù):”); scanf(“%d”,&x); for(i=1;i<=L.last+1;i++) if(L.data[i-1]==x){ for(j=i;j<=L.last+1;j++)L.data[j-1]=L.data[j]; L.last--; i--; k=1; } if(k==1){ printf(“刪除后的數(shù)據(jù)為:n”); for(j=0;j<=L.last;j++)printf(“%3d”,L.data[j]); } else printf(“Not found!n”); 金陵科技學院實驗報告 printf(“n”);} 四、實驗結果與分析（程序運行結果及其分析）（1）結果： 請輸入元素個數(shù)：5 請輸入元素：1 2 3 4 5 元素輸出：1 2 3 4 5（2）結果： 請輸入元素個數(shù)：5 請輸入元素：1 2 3 4 5 請輸入要查找的數(shù)據(jù)元素：5 數(shù)據(jù)元素5所在的位置為 4（3）結果：插入數(shù)據(jù)前的元素為：1 3 5 6 7 9 請輸入要插入的元素為：10 插入元素后的數(shù)據(jù)為: 5 6 7 9 10（4）結果：原數(shù)據(jù)為：1 3 5 7 2 4 6 8 2 9 請輸入要刪除的數(shù)據(jù)為：7 刪除后的數(shù)據(jù)為： 3 5 2 4 6 8 2 9 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 單鏈表 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗2 單鏈表 一、實驗目的和要求 1、實驗目的 掌握單鏈表的定位、插入、刪除等操作。 2、實驗要求 （1）注意鏈表的空間是動態(tài)分配的，某結點不用之后要及時進行物理刪除，以便釋放其內(nèi)存空間。 （2）鏈表不能實現(xiàn)直接定位，一定注意指針的保存，防止丟失。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。（2）在遞增有序的單鏈表中插入一個新結點x，保持單鏈表的有序性。 解題思路：首先查找插入的位置然后進行插入操作；從第一個結點開始找到第一個大于該新結點值的結點即為插入位置；然后在找到的此結點之前插入新結點；注意保留插入位置之前結點的指針才能完成插入操作。 （3）編寫實現(xiàn)帶頭結點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結果。 2、選做題 已知指針LA和LB分別指向兩個無頭結點單鏈表的首元結點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單： 金陵科技學院實驗報告 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 堆棧和隊列 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗3 堆棧和隊列 一、實驗目的和要求 （1）掌握應用棧解決問題的方法。（2）掌握利用棧進行表達式求和的算法。 （3）掌握隊列的存儲結構及基本操作實現(xiàn)，并能在相應的應用問題中正確選用它們。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）判斷一個算術表達式中開括號和閉括號是否配對。（2）測試“漢諾塔”問題。 （3）假設稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以’@’為結束符的字符序列是否是“回文”。 2、選做題 在順序存儲結構上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 串 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗4 串 一、實驗目的和要求 掌握串的存儲及應用。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結果。 （2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結果。 解題思路：可以將第一題程序改進成一個子函數(shù)，在本題中循環(huán)調(diào)用。（3）設字符串采用單字符的鏈式存儲結構，編程刪除串s從位置i開始長度為k的子串。 2、選做題 假設以鏈結構表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。 提示：為提高程序的通用性，插入位置字符應設計為從鍵盤輸入。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 二叉樹 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗5 二叉樹 一、實驗目的和要求 （1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應用二叉樹遞歸遍歷思想解決問題的方法。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。 （2）在第一題基礎上，求二叉樹中葉結點的個數(shù)。（3）在第一題基礎上，求二叉樹中結點總數(shù)。（4）在第一題基礎上，求二叉樹的深度。 2、選做題 已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲結點的值。試編寫算法由此順序存儲結構建立該二叉樹的二叉鏈表。 解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構造方法進行建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結點的左孩子是編號為2i的結點，第i個結點的右孩子是編號為2i+1的結點。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 金陵科技學院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 圖 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗6 圖 一、實驗目的和要求 （1）熟練掌握圖的基本概念、構造及其存儲結構。 （2）熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）構造一個無向圖（用鄰接矩陣表示存儲結構）。 （2）對上面所構造的無向圖，進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。 2、選做題 采用鄰接表存儲結構，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復頂點的路徑。提示：兩個頂點及k值均作為參數(shù)給出。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 排序 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗7 排序 一、實驗目的和要求 （1）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。 （2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 用隨機數(shù)產(chǎn)生100000個待排序數(shù)據(jù)元素的關鍵字值。測試下列各排序函數(shù)的機器實際執(zhí)行時間（至少測試兩個）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、二路歸并排序、堆排序和基于鏈式隊列的基數(shù)排序。 2、選做題 假設含n個記錄的序列中，其所有關鍵字為值介于v和w之間的整數(shù)，且其中很多關鍵字的值是相同的。則可按如下方法排序：另設數(shù)組number[v…w]，令number[i]統(tǒng)計關鍵字為整數(shù)i的紀錄個數(shù)，然后按number重排序列以達到有序。試編寫算法實現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點。程序清單： 金陵科技學院實驗報告 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學院實驗報告 實驗項目名稱： 查找 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學院實驗報告 實驗8 查找 一、實驗目的和要求 （1）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設計。 二、實驗儀器和設備 Visual C++6.0 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）在一個遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。 2、選做題 （2）構造一個哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設計一個測試程序進行測試。 提示：構造哈希表只是完成查找的第一步，大家應該掌握在哈希表上進行查找的過程，可以試著編程序?qū)崿F(xiàn)。程序清單： 金陵科技學院實驗報告 四、實驗結果與分析（程序運行結果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會）第三篇：算法與數(shù)據(jù)結構實驗
第四篇：算法與數(shù)據(jù)結構實驗指導書
第五篇：算法與數(shù)據(jù)結構實驗冊
點擊咨詢 