第一篇：數(shù)據(jù)結(jié)構(gòu)實驗_177
安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書
《數(shù)據(jù)結(jié)構(gòu)》實驗報告
—— 安徽工業(yè)大學(xué)計算機(jī)學(xué)院
數(shù)據(jù)結(jié)構(gòu)
姓名： 陳白楊
學(xué)號： 099074177
學(xué)院： 計算機(jī)學(xué)院
班級： 軟件092
指導(dǎo)老師：王森玉
2011年6月29日
第 1 頁 完成日期： 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書
正文
一．[棧的應(yīng)用（數(shù)值轉(zhuǎn)換）]
1．問題描述
利用棧的數(shù)據(jù)結(jié)構(gòu)和不同進(jìn)制的轉(zhuǎn)換結(jié)合，將十進(jìn)制轉(zhuǎn)換為二進(jìn)制。
2．算法實現(xiàn)
#include
#define 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;
}
S->top=-1;
while(n>0)
{
S->top++;
S->data[S->top]=n%2;//進(jìn)棧
n=n/2;
}
while(S->top>=0)
{
printf(“%ld”,S->data[S->top]);//出棧
S->top--;
}
free(S);
//銷毀棧
} int main(){
long n;
printf(“輸入測試數(shù)據(jù):”);
scanf(“%ld”,&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ī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書
二．[二叉樹的遍歷] 1．問題描述
二叉樹的遍歷主要有先序、中序、后序遍歷。對已建立的二叉樹，使用遞歸算法對二叉樹進(jìn)行遍歷較為方便。同時，可以使用棧模擬遞歸。本次實驗主要使用遞歸來演示二叉樹的遍歷。
2．算法實現(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 ”,p->data);Get_Fdata(p->lchild);Get_Fdata(p->rchild);if(p){
} Get_Mdata(p->lchild);printf(“%d ”,p->data);Get_Mdata(p->rchild);數(shù)據(jù)結(jié)構(gòu) 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書
}
} Get_Ldata(p->lchild);Get_Ldata(p->rchild);printf(“%d ”,p->data);3．運(yùn)行結(jié)果
三．[圖的建立及遍歷] 1．問題描述
圖的建立和遍歷是圖的一個基本的使用。圖是非線性的結(jié)構(gòu)，建立和遍歷圖只是圖的操作中的一個部分。圖的存儲結(jié)構(gòu)只要有鄰接矩陣、鄰接表、十字鏈表、臨界多重表。圖的遍歷主要有深度優(yōu)先遍歷、廣度優(yōu)先遍歷。
2．算法實現(xiàn)
圖的建立
G.vertexNum=rand()%10;for(i=1;i G.edgeNum=rand()%48;sum=sum+i;}while(G.edgeNum<=sum);for(i=0;i { G.vertex[i]=i+'0';for(j=0;j i=rand()%10; } for(i=0;i } printf(“V%c ”,G.vertex[i]);for(j=0;j ”,G.arcs[i][j]);printf(“n”);j=rand()%10;if(i>-1&&i } G.arcs[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,&i); for(j=0;j if(G.arc[i][j]==1&&!visted[j]) { } Visit(j);visited[j]=1;In_s(Q,j); 3．運(yùn)行結(jié)果 四．[查找算法設(shè)計] 1．問題描述 本次實驗主要是查找算法，查找算法主要有順序查找、折半查找（有序表的查找）、分塊查找、樹表查找、哈希表查找。下面將介紹幾種查找算法。 2．算法實現(xiàn) 順序查找： int Search(int a[],int key){ } 數(shù)據(jù)結(jié)構(gòu) 第 6 頁 int i;for(i=0;i if(a[i]==key)return 1;return 0;安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 折半查找 while(right>=left) { } printf(“No Find!”);mid=(right+left)/2;if(key==a[mid]){ } if(key>a[mid]){ } if(key printf(“Find!nn”);getch();return 0;樹表查找 void Getkey(Treenode *p,Datetype key){ if(p==NULL)return;else if(p->Key==key){ } else if(p->Key>key)Getkey(p->Lchild,key);Getkey(p->Rchild,key);else if(p->Key 3．運(yùn)行結(jié)果 順序查找： 數(shù)據(jù)結(jié)構(gòu) 第 7 頁 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 折半查找： 五．[排序算法設(shè)計] 1．問題描述 本次實驗只要是排序算法，主要的排序算法有直接插入排序，折半插入排序，Shell排序，冒泡排序，快速排序，簡單選擇排序，堆排序，二路歸并排序，基數(shù)排序。算法的好壞只要是有算法的平均時間，輔助空間，穩(wěn)定性決定的。不同的算法，適用于不同的情況，本次實驗只要是比較不同排序算法的好壞。下面將介紹幾種排序算法。 2．算法實現(xiàn) 直接插入排序： for(i=1;i } temp=a[i];j=i-1;while(j>=0&&a[j]>temp)j--;a[k]=a[k-1];for(k=i;k>j+1;k--)a[j+1]=temp;冒泡排序改進(jìn)： 數(shù)據(jù)結(jié)構(gòu) 第 8 頁 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 for(i=Max_Size-1;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(min>a[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<=m)&&(j<=r))數(shù)據(jù)結(jié)構(gòu) 第 9 頁 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; if(i>m) for(q=j;q<=r;q++) d[k++]=c[q]; else for(q=i;q<=m;q++) d[k++]=c[q]; for(i=l;i<=r;i++) c[i]=d[i]; } void mergePass(int x[],int y[],int s,int n){ int i=0,j; while(i<=n-2*s) { merge(x,y,i,i+s-1,i+2*s-1); i=i+2*s; } if(i+s merge(x,y,i,i+s-1,n-1); else for(j=i;j y[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ī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 { } void Quick(int a[],int l,int r){ } Shell 排序： d=N/2; while(d>=1) { for(i=0;i for(j=i+d;j { if(a[j] { k=j; temp=a[j]; while(k-d>=0&&temp { a[k]=a[k-d];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; return j;while(j>=l&&i j--;a[i]=a[j];if(j<=i) break;while(i<=r&&i i++;a[j]=a[i];數(shù)據(jù)結(jié)構(gòu) 第 11 頁 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 k-=d; } a[k]=temp; } } d/=2; } 運(yùn)行結(jié)果 直接插入排序： 冒泡排序： 簡單選擇排序： 二路歸并排序： 快速排序： 數(shù)據(jù)結(jié)構(gòu) 第 12 頁 安徽工業(yè)大學(xué)計算機(jī)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》實驗報告書 Shell 排序： 六．實驗總結(jié)[心得體會] 通過這許多實驗使我逐步了解了許多關(guān)于數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計，看著簡單，平常會眼高手低，不過敢想，敢嘗試，努力就會有收獲啊。我覺得課程設(shè)計這種樣式真是需要的，可以學(xué)到很多，包括書上的，書外的等等。理論永遠(yuǎn)！=實際。 數(shù)據(jù)結(jié)構(gòu) 第 13 頁 實驗七 稀疏矩陣的實現(xiàn)基本操作 班級：1208341 4學(xué)號：1208141姓名：陳峰 一、實驗內(nèi)容 （1）掌握稀疏矩陣的壓縮存儲；（2）掌握稀疏矩陣的轉(zhuǎn)置算法； 二、實驗?zāi)康?/p> （1）實現(xiàn)上三角陣的壓縮存儲； （2）用三元組書序表存儲稀疏矩陣，并實現(xiàn)矩陣的轉(zhuǎn)置； 三、設(shè)計思想 （1）創(chuàng)建一個數(shù)組；（2）輸入數(shù)據(jù)； （3）給定矩陣任一元素的下標(biāo)；（4）打印給定下標(biāo)所對應(yīng)的數(shù)據(jù)；（5）創(chuàng)建三元組順序表；（6）輸入矩陣中的數(shù)據(jù)；（7）輸出對應(yīng)的矩陣； 四、程序源代碼 （1）三元組順序表存儲稀疏矩陣并實現(xiàn)矩陣的轉(zhuǎn)置； #include # define MAXSIZE 100 # define MAXRC 10 struct Triple { int i,j; /*該非零元的行下標(biāo)和列下標(biāo)*/ int e;};struct TSMtrix { struct Triple data[MAXSIZE+1]; /*非零元三元組表，data[0]未用*/ int rpos[MAXRC+1]; /*各行第一個非零元的位置表*/ int cpos[MAXRC+1]; /*各列第一個非零元的位置表*/ int num[MAXRC+1]; /*各列非零元的個數(shù)*/ int mu,nu,tu; /*矩陣的行數(shù)、列數(shù)和非零元個數(shù)*/ }; void CreateMtrix(struct TSMtrix *M){ /*創(chuàng)建一個稀疏矩陣*/ int i,elem,col,row,mu,nu,tu; printf(“please input matrix col,row,unzeroed numbers:n”); scanf(“%d%d%d”,&mu,&nu,&tu); M->mu=mu; M->nu=nu; M->tu=tu; for(i=1;i<=tu;i++) { printf(“please input element col,row,value:n”); scanf(“%d%d%d”,&col,&row,&elem); if(mu<0 || nu<0 || mu>M->mu || nu>M->nu) { printf(“error!”); i--; } else { M->data[i].i=col; M->data[i].j=row; M->data[i].e=elem; } } } void ShowMtrix(struct TSMtrix M){ /*打印出矩陣*/ int i=1,j=1,dir=1; printf(“The matrix is:n”); for(i=1;i<=M.mu;i++) { for(j=1;j<=M.nu;j++) { if(M.data[dir].i==i && M.data[dir].j==j) { printf(“%d ”,M.data[dir].e); /*存在非零元*/ dir++; } else printf(“0 ”); } printf(“n”); } } void FastTransposeSMtrix(struct TSMtrix M,struct TSMtrix *T){ /*矩陣的快速轉(zhuǎn)置*/ int t=1,p=1,q,col=M.nu; T->mu=M.mu; T->nu=M.nu; T->tu=M.tu; if(T->tu) { for(col=1;col<=M.nu;col++) M.num[col]=0; for(t=1;t<=M.nu;t++) ++M.num[M.data[t].j]; M.cpos[1]=1; /*找到M中cpos的位置*/ for(col=2;col<=M.nu;col++) M.cpos[col]=M.cpos[col-1]+M.num[col-1]; for(p=1;p<=M.tu;p++) { col=M.data[p].j; q=M.cpos[col]; T->data[q].i=M.data[p].j; T->data[q].j=M.data[p].i; T->data[q].e=M.data[p].e; ++M.cpos[col]; } } } main(){ struct TSMtrix M; struct TSMtrix N; CreateMtrix(&M); ShowMtrix(M); printf(“n”); FastTransposeSMtrix(M,&N); ShowMtrix(N); getch();} （2）實現(xiàn)矩陣的經(jīng)典轉(zhuǎn)置算法并測試； #include typedef struct { int i,j;Elemtype e;}te; typedef struct { te data[maxsize+1];//存儲非0元素的數(shù)組，該數(shù)組是從1開始，所以下面的p從等于1開始// int mu,nu,tu;//mu 表示行數(shù)，nu 表示列數(shù)，tu 表示該矩陣中非0的個數(shù)// }tx; //向矩陣中輸入元素 int intput(tx &a){ int row,col,p=1;//row 表示元素的行標(biāo)，col 表示元素的列標(biāo)，p表示非0元素的計數(shù)器// int temp; printf(“請輸入矩陣行數(shù)：”); scanf(“%d”,&a.mu); printf(“請輸入矩陣列數(shù)：”); scanf(“%d”,&a.nu); printf(“請輸入原始矩陣的每行每列元素：n”); for(row=1;row<=a.mu;row++)//雙重循環(huán)// { for(col=1;col<=a.nu;col++) { scanf(“%d”,&temp); if(temp!=0) { a.data[p].i=row; a.data[p].j=col; a.data[p].e=temp; p++; } a.tu=p; } printf(“n”); } return 0;} //輸出上面的矩陣 int output(tx &a){ int row,col; int p=1; printf(“輸出原始矩陣：n”); for(row=1;row<=a.mu;row++) { for(col=1;col<=a.nu;col++) { if(row==a.data[p].i && col==a.data[p].j) { printf(“t%d”,a.data[p].e); p++; } else //剩余的輸出0// printf(“t%d”,0); } printf(“n”);//換行符的位置// } return 0;} //定義了一個新的矩陣b// int transpose(tx a,tx &b) { int row,col; //找出非0元素// int p,q=1; b.mu=a.nu;//矩陣b的行數(shù)等于矩陣a的列數(shù)// b.nu=a.mu;//矩陣b的列數(shù)等于矩陣a的行數(shù)// b.tu=a.tu;//非0元素的個數(shù)/// if(a.tu!=0)//判斷是否有非0元素// { //雙重循環(huán)// for(col=1;col<=a.nu;col++) // 該循環(huán)是以列循環(huán)目的是：把非0元素中列標(biāo)小的元素從頭排列// { for(p=1;p<=a.tu;p++){ if(a.data[p].j==col) //循環(huán)非0數(shù)組中的元素，并找出a.data[p].j等于當(dāng)時的a矩陣在中的col// { //把矩陣a中非0元素的行標(biāo)和列標(biāo)等于矩陣b非0元素的列標(biāo)和行標(biāo)// b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].e=a.data[p].e; q++; } } } printf(“n”); } return 0;} //輸出轉(zhuǎn)置后的矩陣 int outputtranspose(tx &b){ int q=1; int row,col; printf(“輸出轉(zhuǎn)置后的矩陣：n”); for(row=1;row<=b.mu;row++) { for(col=1;col<=b.nu;col++) { if(row==b.data[q].i && col==b.data[q].j)//找出b矩陣非0元素// { printf(“t%d”,b.data[q].e); q++; } else printf(“t%d”,0);//剩余的輸出0// } printf(“n”); } return 0;} void main(){ tx a,b;intput(a);output(a);transpose(a,b);outputtranspose(b);} 五、調(diào)試及測試數(shù)據(jù) （1）三元組順序表存儲稀疏矩陣并實現(xiàn)矩陣的轉(zhuǎn)置； （2）實現(xiàn)矩陣的經(jīng)典轉(zhuǎn)置算法并測試； 六、實驗總結(jié) 在本實驗中，老師給出了“三元組順序表存儲稀疏矩陣并實現(xiàn)矩陣的轉(zhuǎn)置”的完整實驗代碼供我們參考。通過對參考例子的代碼的理解，看懂之后程序代碼之后就能比較輕松地寫出題目的代碼。在本次實驗中能夠清楚的知道要做什么，從哪里開始做，怎么做，思路很清晰。經(jīng)過編程，學(xué)會了串的操作與實現(xiàn)，并且對C++也有了新的認(rèn)識。 《數(shù)據(jù)結(jié)構(gòu)》實驗(訓(xùn))指導(dǎo)書 電氣與信息工程學(xué)院實驗中心 前 言 《數(shù)據(jù)結(jié)構(gòu)》是計算機(jī)相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校研究生入學(xué)考試專業(yè)課必考課程之一。它主要介紹線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法分析、設(shè)計能力及良好的程序設(shè)計習(xí)慣。通過學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的存儲方案，設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實驗是兩個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法的最佳途徑是上機(jī)實驗。因此，實驗環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。為了更好地配合學(xué)生實驗，特編寫該實驗指導(dǎo)書。 一、實驗?zāi)康?、要求和任?wù) 計算機(jī)編程中加工處理的對象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)編寫計算機(jī)程序僅僅了解計算機(jī)語言是不夠的，還必須掌握數(shù)據(jù)組織、存儲和運(yùn)算的一般方法，這是數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)和研究的內(nèi)容。由于數(shù)據(jù)結(jié)構(gòu)的原理和算法較抽象，而該課程一般在本科低年級開設(shè)，對于計算機(jī)程序設(shè)計知識的初學(xué)者，理解和掌握其中的原理就顯得較為困難。 1.熟練掌握C語言的編輯、編譯、調(diào)試程序。2.會書寫類C語言的算法，并將算法轉(zhuǎn)變?yōu)槌绦驅(qū)崿F(xiàn)。 3.正確理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯特性和存儲表示和基本操作的算法實現(xiàn)。4.有較強(qiáng)的邏輯分析能力。 5.針對問題的不同選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法設(shè)計的能力和動手實驗的技能。 6.學(xué)會分析研究計算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用設(shè)計的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。 7.本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚、正確易讀，符合軟件過程的規(guī)范，從而培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。 8.通過若干數(shù)據(jù)結(jié)構(gòu)應(yīng)用實例，引導(dǎo)學(xué)生學(xué)習(xí)數(shù)據(jù)類型的使用，為今后學(xué)習(xí)面向?qū)ο蟮某绦蜃鲆恍╀亯|。 二、實驗基本內(nèi)容及學(xué)時分配 為了達(dá)到實驗?zāi)康?，本課程安排了4個實驗單元，訓(xùn)練的重點(diǎn)在于基本的數(shù)據(jù)結(jié)構(gòu)，而不是強(qiáng)調(diào)面面俱到。各實驗單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個實驗題常常涉及到幾部分教學(xué)內(nèi)容?？倢W(xué)時：8學(xué)時。 1、線性表（2學(xué)時） （1）熟悉線性表的基本運(yùn)算在兩種存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實現(xiàn)；（2）以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為重點(diǎn)； （3）通過本次實驗幫助學(xué)生提高C語言的編程能力（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。 2、數(shù)組和廣義表（2學(xué)時）（1）掌握稀疏矩陣的壓縮存儲 （2）掌握稀疏矩陣的轉(zhuǎn)置算法 3、樹與二叉樹（2學(xué)時） 常見的二叉樹遍歷算法有先序遍歷，中序遍歷和后序遍歷算法。實現(xiàn)簡單的先序遍歷，中序遍歷和后序遍歷算法。 4、排序（2學(xué)時） 常見的內(nèi)部排序算法，插入類排序算法，如直接插入排序和希爾排序；交換類排序算法，如冒泡排序和快速排序；選擇類排序算法，如簡單選擇排序、樹形選擇類排序和堆排序。實冒泡排序或者直接插入排序算法。 三、說明 該課程采用理論與實踐相結(jié)合的教學(xué)方法，集知識性與趣味性于一體，達(dá)到良好的教學(xué)效果。硬件要求：在多媒體教室講解及演示。為保證教學(xué)順利進(jìn)行，要求實驗室提供電腦等設(shè)備。學(xué)生每次上機(jī)實驗都必須遵守實驗室的有關(guān)規(guī)定。 四、實驗報告規(guī)范 實驗報告的內(nèi)容包括： 1、實驗?zāi)康模赫f明實驗所驗證的知識點(diǎn)。 2、需求分析：以無歧義的陳述說明程序設(shè)計的任務(wù)、約束條件、輸入輸出要求、對功能的規(guī)定及模型。 3、邏輯設(shè)計：說明本程序中用到的所有抽象的數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系。 4、詳細(xì)設(shè)計：邏輯設(shè)計中定義的所有數(shù)據(jù)類型的實現(xiàn)，核心算法的設(shè)計描述、人機(jī)界面設(shè)計、函數(shù)之間調(diào)用關(guān)系的描述，主要功能的算法框架，測試數(shù)據(jù)設(shè)計。 5、測試分析：測試結(jié)果的分析與討論，測試過程中遇到的主要問題及采取的解決措施。 6、心得：軟件設(shè)計與實現(xiàn)過程中的經(jīng)驗與體會，進(jìn)一步改進(jìn)的設(shè)想。 7、程序清單：源程序中應(yīng)有足夠的注釋。如果提交源程序軟盤，列出程序文件名。 五、如何提高上機(jī)效率 為了提高上機(jī)的效率，真正達(dá)到實驗?zāi)康?，要求同學(xué)做好實驗前的準(zhǔn)備工作，寫好實驗預(yù)習(xí)報告，即實驗報告規(guī)范中的1）、2）、3）、4）部分，編寫好程序，并用一組測試數(shù)據(jù)手工執(zhí)行程序靜態(tài)檢查程序是否有錯，通過閱讀、執(zhí)行程序或給別人講解自己的程序而深入全面地理解程序邏輯，提高程序的正確性。對C語言程序不熟悉的同學(xué)，上機(jī)時最好帶上C語言程序設(shè)計的教材，以備查閱。調(diào)試中遇到問題，應(yīng)認(rèn)真分析，確定可疑點(diǎn)，設(shè)置調(diào)試斷點(diǎn)或輸出斷點(diǎn)處變量的值，以便發(fā)現(xiàn)問題，迅速排除問題，加快調(diào)試速度。 實驗室要求： 不能曠課，不遲到，不穿拖鞋進(jìn)實驗室 實驗需預(yù)習(xí)報告（不能單純抄寫，預(yù)習(xí)程序代碼）實驗報告（總結(jié)，注釋，實驗結(jié)果） 目 錄 實驗一 線性表實驗（設(shè)計性實驗）..........................................4 實驗二 數(shù)組和廣義表實驗（設(shè)計性實驗）....................................6 實驗三 樹與二叉樹（設(shè)計性實驗）..........................................8 實驗四 排序（設(shè)計性實驗）................................................9 實驗一 線性表實驗（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.熟悉C語言的上機(jī)環(huán)境，進(jìn)一步掌握C語言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。 3.掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表中的各種基本操作。 二、實驗內(nèi)容 1.順序線性表的建立、插入及刪除。2.鏈?zhǔn)骄€性表的建立、插入及刪除。 三、實驗儀器設(shè)備與器材 上機(jī)電腦 四、實驗步驟 1.建立含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。 2.利用前面的實驗先建立一個順序表L={21，23，14，5，56，17，31}，然后在第i個位置插入元素68。 3.建立一個帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。 五、實驗提示 1.由于C語言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。 在此，我們利用C語言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。 2.注意如何取到第i個元素，在插入過程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。 3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個指針域。用C語言描述結(jié)點(diǎn)結(jié)構(gòu)如下： typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域 struct node *next;//指針域 }linklist; 注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時指針的變化。構(gòu)造一個結(jié)點(diǎn)需用到C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個結(jié)點(diǎn)的地址： p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲空間，這時p為空值（NULL）。 六、實驗總結(jié)與思考 1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語句，會出現(xiàn)什么結(jié)果？ 實驗二 數(shù)組和廣義表實驗（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.掌握稀疏矩陣的壓縮存儲 2.掌握稀疏矩陣的轉(zhuǎn)置算法 二、實驗內(nèi)容 1.實現(xiàn)上三角陣的壓縮存儲。 2.用三元組順序表存儲稀疏矩陣，并實現(xiàn)矩陣的轉(zhuǎn)置。 三、實驗儀器設(shè)備與器材 上機(jī)電腦 四、實驗步驟 1.創(chuàng)建一個數(shù)組。2.輸入數(shù)據(jù) 3.給定矩陣任一元素的下標(biāo)，4.打印給定下標(biāo)所對應(yīng)的數(shù)據(jù)。5.創(chuàng)建三元組順序表。?a22 7.A輸出對應(yīng)的矩陣。?? 21五、實驗提示 ?aaa6.輸入矩陣中的數(shù)據(jù)。?11?a11??a?313233a2122?1.對于如下對稱矩陣： ??A?aaa?4243?41?a31a32a33??1個位置，a21存入到第二個位置，?將它們存入到一個線性數(shù)組中B，不存非零元素，a11存入到第a41a42aija44????aij的位則aij能存到第幾個位置，我們要以用梯形公式算面積。置是它上面的元素之和再加上左邊的元素之和。 它上面的元素之和為((1+(i-1))×(i-1)/2，左邊的元素為(j-1)所以這個元素存儲的位置為k=i(i-1)/2+j-1。 因為矩陣A為對稱矩陣，(另一部分沒有寫出)，所以另一部分的元素為 k=j(j-1)/2+i-1.所以存在關(guān)系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.結(jié)點(diǎn)結(jié)構(gòu) struct triple{ int i,j;//非零元的行下標(biāo)和列下標(biāo) elemtype e;//非零元數(shù)據(jù)} 三元組順序表存儲類型 struct tsmatrix{ triple data[12500];aa?????a44?? int mu,nu,tu;} 三元順序表的轉(zhuǎn)置 方法：(1)將矩陣行列互換，(2)重排矩陣 六、實驗總結(jié)與思考 1.如何存儲三對角陣？ 2.如何用行邏輯鏈接順序表及十字鏈表存儲稀疏矩陣？ 實驗三 樹與二叉樹（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.掌握稀疏矩陣的壓縮存儲 2.掌握稀疏矩陣的轉(zhuǎn)置算法 二、實驗內(nèi)容 1.練習(xí)二叉樹的建立與存儲 2.練習(xí)二叉樹的遍歷 三、實驗儀器設(shè)備與器材 上機(jī)電腦 四、實驗步驟 1.建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 2.建立二叉樹,并通過調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。 五、實驗提示 建立二叉樹的代碼如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉樹，輸入結(jié)點(diǎn)對應(yīng)的編號和值,編號和值之間用逗號隔開nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一個新結(jié)點(diǎn)q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新結(jié)點(diǎn)地址存入s指針數(shù)組中*/ if(i!= 1)/*i = 1，對應(yīng)的結(jié)點(diǎn)是根結(jié)點(diǎn)*/ {j = i / 2;/*求雙親結(jié)點(diǎn)的編號j*/ if(i % 2 == 0)s[j]->lchild = q;/*q結(jié)點(diǎn)編號為偶數(shù)則掛在雙親結(jié)點(diǎn)j的左邊*/ else s[j]->rchild = q;} /*q結(jié)點(diǎn)編號為奇數(shù)則掛在雙親結(jié)點(diǎn)j的右邊*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根結(jié)點(diǎn)地址*/ } 六、實驗總結(jié)與思考 1.如何用孩子兄弟表示法存儲樹？ 2.熟悉及難赫夫曼樹。 實驗四 排序（設(shè)計性實驗） 一、實驗?zāi)康?/p> 1.掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法； 2.深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用； 3.了解各種方法的排序過程及其時間復(fù)雜度的分析方法。 二、實驗內(nèi)容 統(tǒng)計成績 給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計一個算法： （1）按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2）按名次列出每個學(xué)生的姓名與分?jǐn)?shù)。 三、實驗儀器設(shè)備與器材 上機(jī)電腦 四、實驗步驟 1.定義結(jié)構(gòu)體。2.定義結(jié)構(gòu)體數(shù)組。 3.定出主程序，對數(shù)據(jù)進(jìn)行排序。 五、實驗提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n請輸入學(xué)生成績: n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、實驗總結(jié)與思考 1.快速排序算法解決本問題。2.較各種排序算法的優(yōu)缺點(diǎn)及。 3.使用其它排序算法實現(xiàn)該問題（直接插入排序、希爾排序、簡單選擇排序、堆排序等）。 數(shù) 據(jù) 結(jié) 構(gòu) 實 驗 指 導(dǎo) 書 南京工程學(xué)院 信息管理與信息系統(tǒng)教研室 2014年3月 實驗一 線性表操作 一、實驗?zāi)康?/p> 1.熟悉C語言的上機(jī)環(huán)境，進(jìn)一步掌握C語言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。 3.掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表中的各種基本操作。 二、實驗內(nèi)容 1.順序線性表的建立、插入及刪除。 2.鏈?zhǔn)骄€性表的建立、插入及刪除。 三、實驗步驟 1.建立含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。2.利用前面的實驗先建立一個順序表L={21，23，14，5，56，17，31}，然后在第i個位置插入元素68。 3.建立一個帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。 四、實現(xiàn)提示 1.由于C語言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。 在此，我們利用C語言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。 2.注意如何取到第i個元素，在插入過程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。 3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個指針域。用C語言描述結(jié)點(diǎn)結(jié)構(gòu)如下： typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域 struct node *next;//指針域 }linklist;注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時指針的變化。構(gòu)造一個結(jié)點(diǎn)需用到C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個結(jié)點(diǎn)的地址： p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲空間，這時p為空值（NULL）。 五、思考與提高 1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語句，會出現(xiàn)什么結(jié)果？ 實驗二 棧和隊列的應(yīng)用 一、實驗?zāi)康?/p> 1.掌握棧的順序表示和實現(xiàn) 2.掌握隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 二、實驗內(nèi)容 1.編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2.實現(xiàn)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)。 三、實驗步驟 1.順序棧(1)初始化順序棧;(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 2.鏈隊列 (1)初始化并建立鏈隊列(2.)入鏈隊列(3)出鏈隊列(4)遍歷鏈隊列 四、實現(xiàn)提示 1./*定義順序棧的存儲結(jié)構(gòu)*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack; /*初始化順序棧函數(shù)*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack));/*申請空間*/} /*入棧函數(shù)*/ void Push(SqStack *p,ElemType x){if(p->top SqStack S; ElemType e; int N; /*初始化順序棧*/ /*入棧*/ /*出棧*/ /*遍歷順序棧*/ getch();} 2./*定義鏈隊列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue; /*初始化并建立鏈隊列函數(shù)*/ void creat(Lqueue *q) { h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請空間*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循環(huán)快速輸入數(shù)據(jù)*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入鏈隊列函數(shù)快速輸入數(shù)據(jù)*/ } /*入鏈隊列函數(shù)*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出鏈隊列函數(shù)*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*釋放空間*/ /*遍歷鏈隊列函數(shù)*/ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可參考如下代碼： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){ LinkQueue Q; ElemType e; /*初始化并建立鏈隊列*/ /*入鏈隊列*/ /*出鏈隊列*/ *遍歷鏈隊列*/ } DestoryQueue(&Q); getch();} 五、思考與提高 1.讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？ 試寫一個算法，判別讀入的一個以‘@’為結(jié)束符的字符序列是否是?回文?。實驗三 樹操作 一、實驗?zāi)康?/p> 1.通過實驗，掌握二叉樹的建立與存儲 2.通過實驗，掌握二叉樹的遍歷方法 二、實驗內(nèi)容 1.練習(xí)二叉樹的建立與存儲 2.練習(xí)二叉樹的遍歷 三、實驗步驟 1.建立二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 2.建立二叉樹,并通過調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。 四、實現(xiàn)提示 1.采用遞歸方法建立二叉樹： 首先建立二叉樹的根 結(jié)點(diǎn)，然后建立其左右子樹，直到空子樹為止。 2.先序遍歷、中序遍歷與后序遍歷二叉樹。#include BiTree CreateBiTree(BiTree &T){ } /*先序遍歷*/ Status PreOrderTraverse(BiTree T){ } /*中序遍歷*/ Status InOrderTraverse(BiTree T){ } /*后序遍歷*/ Status PostOrderTraverse(BiTree T){ } int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍歷*/ InOrderTraverse(T);printf(“n”);/*中序遍歷*/ PostOrderTraverse(T);printf(“n”);/*后序遍歷*/ return 0;} 五、思考與提高 編寫遞歸算法，計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。 目 錄 實驗規(guī)則················································2 實驗環(huán)境················································2 實驗報告要求············································3 實驗一 單鏈表 （一）······································4 實驗二 單鏈表 （二）······································5 實驗三 ?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ? 實驗四 二叉樹···········································7 實驗五 最短路徑·········································8 實驗六 內(nèi)部排序·········································9 實 驗 規(guī) 則 為了順利完成實驗教學(xué)任務(wù)，確保人身、設(shè)備的安全，培養(yǎng)嚴(yán)謹(jǐn)、踏實、實事求是的科學(xué)作風(fēng)和愛護(hù)國家財產(chǎn)的優(yōu)良品質(zhì)，特制定以下實驗規(guī)則： 1、實驗前必須充分預(yù)習(xí)，完成指定的預(yù)習(xí)任務(wù)。預(yù)習(xí)要求如下： （1）認(rèn)真閱讀指導(dǎo)書，進(jìn)行必要的設(shè)計與計算。（2）熟悉實驗內(nèi)容。 （3）預(yù)先復(fù)習(xí)，并按要求編寫程序。（4）未完成預(yù)習(xí)任務(wù)者不得進(jìn)入實驗室。 2、遵守以下紀(jì)律： （1）在實驗室不得做和實驗無關(guān)的事情。 （2）進(jìn)行任課老師指定內(nèi)容以外的實驗，必須經(jīng)指導(dǎo)教師同意。（3）遵守紀(jì)律，不遲到。 （4）保持實驗室內(nèi)安靜、整潔，愛護(hù)公物，不許亂寫亂畫。 實 驗 環(huán) 境 本實驗在386以上的微機(jī)上進(jìn)行，運(yùn)行環(huán)境為VC6.0。 實驗報告要求 1、實驗題目 2．實驗?zāi)康?3．實驗環(huán)境 4．實驗內(nèi)容與完成情況（可以附上自主設(shè)計的源程序）5．出現(xiàn)的問題及對問題的解決方案 6．實驗思考：（學(xué)生對本次實驗的收獲的總結(jié)） 實驗一 單鏈表 （一）一、實驗?zāi)康?/p> 掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作。 二、預(yù)習(xí)要求 1、看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。 2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。 三、實驗內(nèi)容 實現(xiàn)一個簡單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有： 1、利用單鏈表建立學(xué)生基本信息表 2、瀏覽每個學(xué)生的信息 3、根據(jù)學(xué)號查詢某個學(xué)生的基本信息 4、添加學(xué)生信息到單鏈表中 5、刪除一個學(xué)生的信息 四、實現(xiàn)提示 設(shè)計結(jié)點(diǎn)的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號、姓名、年齡、性別；要求設(shè)計一個簡單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個函數(shù)實現(xiàn)上述的一個功能。 實驗二 單鏈表 （二）一、實驗?zāi)康?/p> 掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作。 二、預(yù)習(xí)要求 1、看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。 2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。 三、實驗內(nèi)容 1、實現(xiàn)單鏈表的就地逆置。 2、建立兩個非遞減有序單鏈表，然后合并成一個非遞減鏈表。 3、建立兩個非遞減有序單鏈表，然后合并成一個非遞增鏈表。 4、編寫一個主函數(shù),調(diào)試上述算法。 四、選做題、思考題 1、如何用帶表頭結(jié)點(diǎn)的單鏈表作為多項式的存儲表示，實現(xiàn)兩個多項式的相加。 2、約毖夫環(huán)的實現(xiàn)。 3、如何利用文件實現(xiàn)學(xué)生信息的存取。 實驗三 棧 一、實驗?zāi)康?/p> 深入了解并掌握棧的特性及其在實際中的應(yīng)用；熟練掌握棧的算法實現(xiàn)；運(yùn)用棧操作求解實際問題。 二、預(yù)習(xí)要求 1、看懂書上的算法，深入理解棧的特性和存儲結(jié)構(gòu)，以便在實際問題背景下靈活運(yùn)用。 2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。 三、實驗內(nèi)容 利用棧實現(xiàn)數(shù)據(jù)的分類，要求當(dāng)輸入為偶數(shù)時進(jìn)棧1，當(dāng)輸入為奇數(shù)時進(jìn)棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。 四、實現(xiàn)提示 1、開辟一個連續(xù)的存儲空間，實現(xiàn)兩個棧順序存儲空間的共享；分別在兩端設(shè)置棧頂指針，并按要求實現(xiàn)棧操作。 2、采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。 五、選做題、思考題 1、兩?？臻g共享時，棧滿的條件是什么？ 2、為停車場編制進(jìn)行管理的模擬程序（習(xí)題集P96，2.1）。 3、編寫程序，利用棧實現(xiàn)表達(dá)式求值。 實驗四 二叉樹 一、實驗?zāi)康?/p> 通過實踐掌握二叉樹的存儲結(jié)構(gòu)和遍歷思想；掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。 二、預(yù)習(xí)要求 二叉樹的三種遍歷方法。 三、實驗內(nèi)容 1、輸入字符序列，建立二叉鏈表。 2、利用棧，編寫非遞歸算法，編程實現(xiàn)二叉樹的中序遍歷。 3、求二叉樹的葉子結(jié)點(diǎn)個數(shù)。 4、在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。 四、選做題、思考題 1、如何實現(xiàn)二叉樹的后序遍歷（非遞歸）。 2、如何求二叉樹的高度。 實驗五 最短路徑（旅游景點(diǎn)導(dǎo)游咨詢模擬） 一、實驗?zāi)康?/p> 利用圖的最短路徑原理為用戶提供路徑咨詢，掌握求最短路徑的算法并編程實現(xiàn)。 二、預(yù)習(xí)要求 學(xué)習(xí)了解圖的存儲結(jié)構(gòu)，掌握求最短路徑的兩種算法。 三、實驗內(nèi)容 設(shè)計一個旅游景點(diǎn)導(dǎo)游模擬程序，為來訪的客人提供景點(diǎn)最短路徑的信息查詢服務(wù)，任意選取n城市，構(gòu)成一個有向帶權(quán)圖，圖中頂點(diǎn)表示城市，邊上的權(quán)值表示兩點(diǎn)間的距離，根據(jù)用戶指定的始點(diǎn)和終點(diǎn)輸出相應(yīng)的最短路徑。 四、實現(xiàn)提示 咨詢以用戶和計算機(jī)的對話方式進(jìn)行，由用戶輸入起始點(diǎn)和終點(diǎn)，輸出信息：最短路徑是多少？并指出所經(jīng)過的城市。存儲結(jié)構(gòu)可選用鄰接矩陣。 五、選做題、思考題 1．如何實現(xiàn)對城市信息進(jìn)行編輯（如：添加或刪除）的功能。 2．用鄰接表作存儲結(jié)構(gòu)，求一指定景點(diǎn)出發(fā)，到其余各景點(diǎn)的最短路徑。 實驗六 內(nèi)部排序 一、實驗?zāi)康?/p> 直觀感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)。 二、預(yù)習(xí)要求 1、常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點(diǎn)及其適用條件。 2、根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。 三、實驗內(nèi)容 1、對直接插入排序和簡單選擇排序算法進(jìn)行關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)的比較。 2、利用鏈?zhǔn)酱鎯Y(jié)構(gòu)，編寫程序，實現(xiàn)直接插入排序和冒泡排序。 四、實現(xiàn)提示 測試數(shù)據(jù)可以為幾組典型的數(shù)據(jù)：正序、逆序、亂序。 五、選做題、思考題 1、快速排序算法的非遞歸實現(xiàn)。 2、結(jié)合實驗，理解針對不同待排元素的特點(diǎn)而選擇不同排序方法的重要性。 3、如何對本實驗進(jìn)行時間、空間的復(fù)雜度分析。第二篇：實驗7 數(shù)據(jù)結(jié)構(gòu)
第三篇：《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書
第四篇：《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書
第五篇：數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書
點(diǎn)擊咨詢 