數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)與算法B上機(jī)實(shí)驗(yàn)報(bào)告第1次2011-10-02順序表的實(shí)現(xiàn)和基本操作第2次2011-10-29二叉樹(shù)的實(shí)現(xiàn)和遞歸遍歷第3次2011-11-23內(nèi)部排序第4次2011-12-dd實(shí)現(xiàn)圖從鄰接矩陣到鄰接表存儲(chǔ)轉(zhuǎn)化第一次 線性表數(shù)據(jù)結(jié)構(gòu)一、上機(jī)實(shí)習(xí)題目線性鏈表操作插入、刪除、合并、排序、查找二 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（算法設(shè)計(jì)）源程序（#include #define MaxSize 100using namespace std;typedef int ElemType;class SeqList ElemType listMaxSize;int length;public: SeqList() le

2、ngth=0; void SeqListSort(int i,ElemType x); void SeqListCreat(int n); void SeqListInset(int i,ElemType x); void SeqListDelete(int i); void SeqListMerge(); int GetLength()return length; int SeqListFind(ElemType x); int SeqListIsEmpty(); void SeqListPrint(); Mylist1,Mylist2;/創(chuàng)建順序表 void SeqList:SeqList

3、Creat(int n) ElemType x;cout請(qǐng)輸入數(shù)據(jù)元素:;for (int i=0;ix;listi=x;length+; /對(duì)順序表進(jìn)行排序void SeqList:SeqListSort(int i,ElemType x) for(int k=0;klength;k+) for(i=k+1;ilisti) x=listk; listk=listi; listi=x; /在順序表L中的第i個(gè)位置插入新元素xvoid SeqList:SeqListInset(int i,ElemType x)int k;if(length=MaxSize)cout表已滿，無(wú)法插入！endl;e

4、lse if(ilength)cout參數(shù)i不合理！=i;k-)listk=listk-1;listi-1=x;length+; /刪除第i個(gè)位置的數(shù)據(jù)元素void SeqList:SeqListDelete(int i)int k;if(!SeqListIsEmpty()cout表已空，無(wú)法刪除！endl;else if(ilength)cout參數(shù)i不合理！endl;elsefor(k=i-1;klength;k+)listk=listk+1;length-; /查找元素x在表中的位置int SeqList:SeqListFind(ElemType x) int i=0;while(ile

5、ngth)return -1;else return i+1;/判斷順序表是否為空int SeqList:SeqListIsEmpty()if(length=0)return 0;else return 1;/將順序表顯示在屏幕上void SeqList:SeqListPrint()if(!SeqListIsEmpty()cout空表！endl;elsefor(int i=0;ilength;i+)coutlisti ;coutendl; int main() SeqList Mylist1,Mylist2; int i,n,flag=1,select;ElemType x;cout1. 建立

6、順序表n;cout2. 對(duì)順序表進(jìn)行排序n; cout3. 求x數(shù)值的位置n;cout4. 在第i個(gè)位置插入新元素xn;cout5. 刪除第i個(gè)位置上的數(shù)值n;cout6. 將兩個(gè)順序表合并n; cout7. 退出n;coutendl;while (flag)coutselect;switch(select)case 1: coutn; Mylist1.SeqListCreat(n); cout你所輸入的順序表1為：; Mylist1.SeqListPrint(); coutn; Mylist2.SeqListCreat(n); cout你所輸入的順序表2為：; Mylist2.SeqList

7、Print(); break; case 2: coutn; if(n=1) Mylist1.SeqListSort(i,x); cout排序后的順序表1為:; Mylist1.SeqListPrint(); else Mylist2.SeqListSort(i,x); cout排序后的順序表2為:; Mylist2.SeqListPrint(); break;case 3: coutx; i=Mylist1.SeqListFind(x); if(i!=-1) coutx的位置為：iendl; else cout沒(méi)有找到！; break;case 4: coutix; Mylist1.SeqL

8、istInset(i,x); cout插入后的順序表為:; Mylist1.SeqListPrint(); break;case 5: couti; Mylist1.SeqListDelete(i); cout刪除后的順序表為：; Mylist1.SeqListPrint(); break; case 6: cout合并后的順序表為：n; Mylist1.SeqListPrint(); Mylist2.SeqListPrint(); break; case 7: flag=0; break; 三 運(yùn)行結(jié)果為：四、上機(jī)環(huán)境和使用語(yǔ)言（計(jì)算機(jī)程序?qū)崿F(xiàn)）Visual C+。 使用語(yǔ)言：C+五、上機(jī)總

9、結(jié)（體會(huì)提高）總的來(lái)說(shuō)，這次讓我感觸最深的就是C+挺麻煩的，應(yīng)該說(shuō)我還是太不熟悉了，以前沒(méi)有怎么接觸過(guò)，通過(guò)這次實(shí)驗(yàn)，我初步掌握了一點(diǎn)點(diǎn)的C+的基礎(chǔ)，往后我要多花點(diǎn)時(shí)間學(xué)習(xí)。再者，通過(guò)這次實(shí)驗(yàn)，我也掌握了對(duì)于線性表的的表示，使用，特別是順序表。但是對(duì)于鏈表還是有待提高。六、參考資料據(jù)結(jié)構(gòu)與算法分析教材，據(jù)結(jié)構(gòu)（C語(yǔ)言版），軟件開(kāi)發(fā)技術(shù)基礎(chǔ)（第二版）。同時(shí)還有網(wǎng)上的一些資源。當(dāng)然還有同學(xué)之間的探討。第二次：非線性表數(shù)據(jù)結(jié)構(gòu)一、上機(jī)實(shí)習(xí)題目編寫(xiě)的遞歸算法，交換二叉樹(shù)的左右子樹(shù)。二 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（算法設(shè)計(jì)）源程序#include#include#define N 9typedef struct bi

10、node int data; struct binode *lchild,*rchild;/指向左右孩子的指針binode,*bitree;/結(jié)點(diǎn)與指針typedef struct bitree elem100; int top;stack;bitree creat_bt()/按先序建二叉樹(shù) bitree t; int i,x=0;/一顆N個(gè)結(jié)點(diǎn)的二叉樹(shù)t scanf(%d,&x); if(x=100)/輸入100作為結(jié)束該結(jié)點(diǎn)，而不是用循環(huán) t=NULL; else t=(bitree)malloc(sizeof(binode); t-data=x; printf(請(qǐng)輸入%d結(jié)點(diǎn)的左子結(jié)點(diǎn),

11、t-data); t-lchild=creat_bt(); printf(請(qǐng)輸入%d結(jié)點(diǎn)的右子結(jié)點(diǎn),t-data); t-rchild=creat_bt(); return t;bitree exchange(bitree t) /遞歸左、右子樹(shù)交換bitree p; if(t!=NULL) p=t-lchild; t-lchild=t-rchild; t-rchild=p; exchange(t-lchild); exchange(t-rchild); return t;void preorder(bitree bt) /遞歸的先序遍歷 if (bt) printf(% d,bt-data)

12、; preorder(bt-lchild); preorder(bt-rchild);main()bitree root;/一顆樹(shù)rootprintf(n);printf(輸入二叉樹(shù)的元素：);root=creat_bt();printf(交換前的先序序列是：);preorder(root);exchange(root);printf(n交換后的先序序列是：);preorder(root);printf(n);三 運(yùn)行結(jié)果為：四、上機(jī)環(huán)境和使用語(yǔ)言（計(jì)算機(jī)程序?qū)崿F(xiàn)）Visual C+。 使用語(yǔ)言：C Win7操作系統(tǒng)五、上機(jī)總結(jié)（體會(huì)提高）通過(guò)這次實(shí)驗(yàn)，個(gè)人覺(jué)得對(duì)于二叉樹(shù)的定義和主要特性有了更

13、深的了解，當(dāng)然對(duì)于二叉樹(shù)的一些基本操作處理也有了一定的掌握。同時(shí)也更熟練的使用遞歸算法。六、參考資料據(jù)結(jié)構(gòu)與算法分析教材，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），軟件開(kāi)發(fā)技術(shù)基礎(chǔ)（第二版）。同時(shí)還有網(wǎng)上的一些資源。當(dāng)然還有同學(xué)之間的探討。第三次 算法一、上機(jī)實(shí)習(xí)題目編寫(xiě)一個(gè)程序，程序中包括各種排序算法，希爾排序，冒泡排序，快速排序等，用這些算法對(duì)數(shù)據(jù)進(jìn)行排序處理。二 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（算法設(shè)計(jì)）源程序#include using namespace std;void BiInsertsort(int r, int n) /插入排序（折半） for(int i=2;i=n;i+) if (riri-1) r0 = r

14、i; /設(shè)置哨兵 int low=1,high=i-1; /折半查找 while (low=high) int mid=(low+high)/2; if (r0high;j-) rj+1 = rj; /后移 rj+1 = r0; for(int k=1;k=n;k+) coutrk ; cout=1;d=d/2) /以d為增量進(jìn)行直接插入排序 for (int i=d+1;i0 & r0rj; j=j-d) rj+d = rj; /記錄后移d個(gè)位置 rj+d = r0; for(int i=1;i=n;i+) coutri ; coutn;void BubbleSort(int r, int

15、n) /起泡排序 int temp,exchange,bound; exchange=n; /第一趟起泡排序的范圍是r0到rn-1 while (exchange) /僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序 bound=exchange; exchange=0; for (int j=1; jrj+1) temp=rj; rj=rj+1; rj+1=temp; exchange=j; /記錄每一次發(fā)生記錄交換的位置 for(int i=1;i=n;i+) coutri ; coutn;int Partition(int r, int first, int end) /快速排序一次劃分 int

16、i=first; /初始化 int j=end; r0=rfirst; while (ij) while (ij & r0= rj) j-; /右側(cè)掃描 ri=rj; while (ij & ri= r0) i+; /左側(cè)掃描 rj=ri; ri=r0; return i; /i為軸值記錄的最終位置void QuickSort(int r, int first, int end) /快速排序 if (firstend) /遞歸結(jié)束 int pivot=Partition(r, first, end); /一次劃分 QuickSort(r, first, pivot-1);/遞歸地對(duì)左側(cè)子序列進(jìn)

17、行快速排序 QuickSort(r, pivot+1, end); /遞歸地對(duì)右側(cè)子序列進(jìn)行快速排序 void SelectSort(int r , int n) /簡(jiǎn)單選擇排序 int i,j,index,temp; for (i=1; in; i+) /對(duì)n個(gè)記錄進(jìn)行n-1趟簡(jiǎn)單選擇排序 index=i; for (j=i+1; j=n; j+) /在無(wú)序區(qū)中選取最小記錄 if (rjrindex) index=j; if (index!=i) temp=ri; ri=rindex; rindex=temp; for(i=1;i=n;i+) coutri ; coutn;void main

18、() const int numv=12; int a3numv=0,6,13,19,23,37,39,41,45,48,58,86,0,86,58,48,45,41,39,37,23,19,13,6,0,23,13,48,86,19,6,41,58,37,45,39; int z1numv,z2numv; int m,n; cout請(qǐng)選擇測(cè)試數(shù)據(jù)類型：正序 逆序 隨機(jī) 若跳出,請(qǐng)按 m; while(m0&m4) cout請(qǐng)選擇排序算法：直接插入排序 希爾排序 冒泡排序 快速排序 n 簡(jiǎn)單選擇排序n; switch(n) case 1: cout 直接插入排序前： n; for(int j=

19、1;jnumv;j+) coutam-1j ; cout n直接插入排序結(jié)果為： n; BiInsertsort(am-1,numv-1); break; case 2: cout n希爾排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n希爾排序結(jié)果為： n; ShellSort(am-1, numv-1); break; case 3: cout n冒泡排序前： n; for(int k=1;knumv;k+) coutam-1k ; cout n冒泡排序結(jié)果為： n; BubbleSort(am-1, numv-1); break; case

20、4: cout n快速排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n快速排序結(jié)果為： n; QuickSort(am-1,0,numv-1); for(int i=1;inumv;i+) coutam-1i ; coutn; break; case 5: cout n簡(jiǎn)單選擇排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n簡(jiǎn)單選擇排序結(jié)果為： n; SelectSort(am-1,numv-1); break; default: cout輸入錯(cuò)誤！endl; m=0; cout請(qǐng)選擇測(cè)試數(shù)據(jù)類型：

21、正序 逆序 隨機(jī) 若跳出,請(qǐng)按 m; if(m=4) cout(*_*) 再見(jiàn)！endl; else cout輸入錯(cuò)誤！endl;三 運(yùn)行結(jié)果為：對(duì)于各種排序方法的時(shí)間復(fù)雜度T(n)的分析：排序方法T（n）排序方法T(n)簡(jiǎn)單排序O（）堆排序O(nlog n)排序方法T（n）排序方法T（n）快速排序O(nlog n)歸并排序O(nlog n)排序方法T（n）排序方法T（n）直接插入排序O（）冒泡排序O（）四、上機(jī)環(huán)境和使用語(yǔ)言（計(jì)算機(jī)程序?qū)崿F(xiàn)）Visual C+。 使用語(yǔ)言：C+ Win7操作系統(tǒng)五、上機(jī)總結(jié)（體會(huì)提高）通過(guò)這次實(shí)驗(yàn)，感受最深的就是對(duì)于各種排序算法有了更深的了解和掌握。同時(shí)也對(duì)

22、他們之間的差別有了更深的認(rèn)識(shí)。原來(lái)對(duì)數(shù)據(jù)進(jìn)行排序也可以有聲有色！六、參考資料據(jù)結(jié)構(gòu)與算法分析教材，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），軟件開(kāi)發(fā)技術(shù)基礎(chǔ)（第二版）。同時(shí)還有網(wǎng)上的一些資源。當(dāng)然還有同學(xué)之間的探討。第四次 上機(jī)實(shí)驗(yàn)題目：編寫(xiě)算法，將圖的鄰接矩陣存儲(chǔ)轉(zhuǎn)化為圖的鄰接表存儲(chǔ)。并對(duì)下圖給出的實(shí)例執(zhí)行算法，輸出結(jié)果。數(shù)據(jù)結(jié)構(gòu)知識(shí)：圖的實(shí)現(xiàn)，圖的鄰接矩陣存儲(chǔ)，圖的鄰接表存儲(chǔ)以及他們之間的轉(zhuǎn)化。程序源代碼#include #include #define N 7#define E 15typedef char VexType;typedef int AdjType;typedef structVexType

23、vertexN+1;AdjType edgeN+1N+1;AdjMatrix;typedef struct nodeint adjvex;struct node *next;EdgeNode;typedef structVexType vertxe;EdgeNode *link;VexNode;VexNode adjlistN+1;AdjMatrix *adj;void creatAdj(AdjMatrix *adj)int i,j,k; printf(請(qǐng)輸入各頂點(diǎn)信息：);for(i=1;ivertexi);for(i=1;i=N;i+)for(j=1;jedgeij=0;printf(請(qǐng)輸入各邊的信息:);for(k=1;kedgeij=1;void Convert(AdjMatrix *adj)int i,j,k;EdgeNode *s;for(i=1;ivertexi; adjlisti.link=NULL;for(i=1;i=N;i+)for(j=1;jedgeij!=0) s=(EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=j; s-ne