【正文】 第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)_177安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告—— 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)姓名： 陳白楊學(xué)號： 099074177學(xué)院： 計(jì)算機(jī)學(xué)院班級： 軟件092指導(dǎo)老師：王森玉2011年6月29日第 1 頁 完成日期： 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書正文一．[棧的應(yīng)用（數(shù)值轉(zhuǎn)換）]1．問題描述利用棧的數(shù)據(jù)結(jié)構(gòu)和不同進(jìn)制的轉(zhuǎn)換結(jié)合，將十進(jìn)制轉(zhuǎn)換為二進(jìn)制。2．算法實(shí)現(xiàn)includedefine maxsize 100 typedef struct linklist {long data[maxsize]。long top。}stack,*stacklist。void change(long n){stacklist S。//初始化棧if((S=(stacklist)malloc(sizeof(stack)))==NULL){printf(“申請內(nèi)存空間失敗!”)。return。}Stop=1。while(n0){Stop++。Sdata[Stop]=n%2。//進(jìn)棧n=n/2。}while(Stop=0){printf(“%ld”,Sdata[Stop])。//出棧Stop。}free(S)。//銷毀棧} int main(){long n。printf(“輸入測試數(shù)據(jù):”)。scanf(“%ld”,amp。n)。if(n==0)printf(“%d”,n)。else change(n)。getch()。return 0。} 3．運(yùn)行結(jié)果數(shù)據(jù)結(jié)構(gòu) 第 2 頁 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書二．[二叉樹的遍歷] 1．問題描述二叉樹的遍歷主要有先序、中序、后序遍歷。對已建立的二叉樹，使用遞歸算法對二叉樹進(jìn)行遍歷較為方便。同時，可以使用棧模擬遞歸。本次實(shí)驗(yàn)主要使用遞歸來演示二叉樹的遍歷。2．算法實(shí)現(xiàn)先序遍歷void Get_Fdata(tree_n *p){} 中序遍歷void Get_Mdata(tree_n *p){} 后序遍歷void Get_Ldata(tree_n *p){if(p){第 3 頁if(p){} printf(“%d ”,pdata)。Get_Fdata(plchild)。Get_Fdata(prchild)。if(p){} Get_Mdata(plchild)。printf(“%d ”,pdata)。Get_Mdata(prchild)。數(shù)據(jù)結(jié)構(gòu) 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書}} Get_Ldata(plchild)。Get_Ldata(prchild)。printf(“%d ”,pdata)。3．運(yùn)行結(jié)果三．[圖的建立及遍歷] 1．問題描述圖的建立和遍歷是圖的一個基本的使用。圖是非線性的結(jié)構(gòu)，建立和遍歷圖只是圖的操作中的一個部分。圖的存儲結(jié)構(gòu)只要有鄰接矩陣、鄰接表、十字鏈表、臨界多重表。圖的遍歷主要有深度優(yōu)先遍歷、廣度優(yōu)先遍歷。2．算法實(shí)現(xiàn)圖的建立=rand()%10。for(i=1。i=rand()%48。sum=sum+i。}while({ [i]=i+39。039。for(j=0。ji=rand()%10。} for(i=0。i} printf(“V%c ”,[i])。for(j=0。j”,[i][j])。printf(“n”)。j=rand()%10。if(i1amp。amp。i1amp。amp。j} [i][j]=1。k++。圖的遍歷(廣度優(yōu)先)void BFStraverse(MGraph G){} void BFS(MGraph G,int v){int i,j。PQ Q。Q=Init_s()。Visit(v)。visited[v]=1。In_s(Q,v)。while(!Empty_s(Q)){ int visted[MaxVertextNUm]。int v。for(v=0。v}} Out_s(Q,amp。i)。for(j=0。jif([i][j]==1amp。amp。!visted[j]){} Visit(j)。visited[j]=1。In_s(Q,j)。3．運(yùn)行結(jié)果四．[查找算法設(shè)計(jì)]1．問題描述本次實(shí)驗(yàn)主要是查找算法，查找算法主要有順序查找、折半查找（有序表的查找）、分塊查找、樹表查找、哈希表查找。下面將介紹幾種查找算法。2．算法實(shí)現(xiàn)順序查找：int Search(int a[],int key){}數(shù)據(jù)結(jié)構(gòu)第 6 頁int i。for(i=0。iif(a[i]==key)return 1。return 0。安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書折半查找while(right=left){} printf(“No Find!”)。mid=(right+left)/2。if(key==a[mid]){} if(keya[mid]){ } if(keyprintf(“Find!nn”)。getch()。return 0。樹表查找void Getkey(Treenode *p,Datetype key){if(p==NULL)return。else if(pKey==key){} else if(pKeykey)Getkey(pLchild,key)。Getkey(pRchild,key)。else if(pKey3．運(yùn)行結(jié)果順序查找：數(shù)據(jù)結(jié)構(gòu) 第 7 頁 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書折半查找：五．[排序算法設(shè)計(jì)] 1．問題描述本次實(shí)驗(yàn)只要是排序算法，主要的排序算法有直接插入排序，折半插入排序，Shell排序，冒泡排序，快速排序，簡單選擇排序，堆排序，二路歸并排序，基數(shù)排序。算法的好壞只要是有算法的平均時間，輔助空間，穩(wěn)定性決定的。不同的算法，適用于不同的情況，本次實(shí)驗(yàn)只要是比較不同排序算法的好壞。下面將介紹幾種排序算法。2．算法實(shí)現(xiàn)直接插入排序：for(i=1。i} temp=a[i]。j=i1。while(j=0amp。amp。a[j]temp)j。a[k]=a[k1]。for(k=i。kj+1。k)a[j+1]=temp。冒泡排序改進(jìn)：數(shù)據(jù)結(jié)構(gòu) 第 8 頁 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書for(i=Max_Size1。i=0。i)//篩選{} Change=0。for(j=0。j} if(Change==0)break。count++。if(a[j]a[j+1])//交換 {} temp=a[j]。a[j]=a[j+1]。a[j+1]=temp。Change=1。簡單選擇排序：for(i=0。i} min=a[i]。tag=i。for(j=i+1。j} a[tag]=a[i]。a[i]=min。if(mina[j]){} min=a[j]。tag=j。二路歸并排序：void merge(int c[],int d[],int l,int m,int r)//將已排好序的數(shù)組合并{int i=l,j=m+1,k=l,q。while((i第 9 頁安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書if(c[i]d[k++]=c[i++]。else d[k++]=c[j++]。if(im)for(q=j。qd[k++]=c[q]。elsefor(q=i。qd[k++]=c[q]。for(i=l。ic[i]=d[i]。} void mergePass(int x[],int y[],int s,int n){int i=0,j。while(i{merge(x,y,i,i+s1,i+2*s1)。i=i+2*s。}if(i+smerge(x,y,i,i+s1,n1)。elsefor(j=i。jy[j]=x[j]。}void Mer_s(int a[],int b[],int m){int s=1。while(s{mergePass(a,b,s,m)。s+=s。mergePass(b,a,s,m)。s+=s。} } 快速排序：int Get_sort(int a[],int l,int r)數(shù)據(jù)結(jié)構(gòu) 第 10 頁 安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告書{} void Quick(int a[],int l,int r){} Shell 排序：d=N/2。while(d=1){for(i=0。ifor(j=i+d。j{if(a[j]{k=j。temp=a[j]。while(kd=0amp。amp。temp{a[k]=a[kd]。int q=Get_sort(a,l,r)。if(l} Quick(a,l,q)。//q 針對于左邊1位數(shù)字時 Quick(a,q+1,r)。int t=a[l]。int i=l。int j=r。while(1){} a[j]=t。