數據結構課程設計實驗報告

1、徐州工程學院管理學院實驗報告實驗課程名稱 ： 數據結構 實驗地點： 南主樓七樓機房 2011 年 9 月至 2012 年 1 月 專 業(yè) 信息管理與信息系統(tǒng) 班 級 09信管2 學生姓名 學 號 指導老師 實驗報告實驗項目：鏈表的應用實驗學時：2 實驗日期：2011.9.9實驗要求：對單鏈表實現就地逆置。實驗內容：#include#include#define null 0struct llist int num; struct llist * next;void main() struct llist * head,* p,*q; int len,i; scanf(%d,&len); pri

2、ntf(the number is:n); /*建立鏈表*/ for(i=1;inum); p-next=null; if(i=1) head=p; else q=head; while(q-next!=null) q=q-next; q-next=p; printf(the llist is:n); p=head; for(i=1;inum); p=p-next; printf(n); p=head; /*鏈表逆置*/ while(head-next!=null) q=p; p=head-next; head-next=p-next; p-next=q;head=p; p=head; for

3、(i=1;inum); p=p-next; getch();實驗項目：棧的應用實驗學時： 2 實驗日期：2011.9.16實驗要求：假設用順序存儲結構實現一個雙向棧，即在一維數組的存儲空間中存在著2個棧，它們的棧底分別設在數組的兩個端點，試編寫這個雙向棧tws的三個操作，初始化initstack(tws), 入棧push(tws i), 出棧pop(tws i)的算法，其中i為0或1，用以分別指示設在數組兩端的兩個棧。實驗內容：#include stdio.h/*stack part*/#define bool int#define true 1#define false 0typedef s

4、tructint *base2;int *top2;bdstacktype;bool initstack(bdstacktype tws,int m);bool pushstack(bdstacktype tws,int i,int x);int main()int i,m,x,n;bdstacktype stack1;scanf(%d,&n);scanf(%d,&m);if( !initstack(stack1,n) )printf(alloc failure!n);exit(0);for( i=0; itws.top1)return false;if( i = 1)*tws.top1-=x

5、;else if( i=0 )*tws.top0+ = x;elsereturn false;return true;實驗項目：矩陣的應用實驗學時：2 實驗日期：2011.10.7實驗要求：假設稀疏矩陣a,b均以三元組順序表作為存儲結構，試寫出矩陣值相加的算法，另設三元組c存放結果矩陣。實驗內容：#include#include#define maxsize 1000 /*用戶自定義*/typedef int datatype; /*用戶自定義*/typedef struct int i,j; datatype v; triple;/*定義三元組結構*/typedef struct tripl

6、e datamaxsize;/*定義可存三元組大小*/int mu,nu,tu; tsmatrix;/*行數，列數，非零元*/void addtriple( tsmatrix *a ,tsmatrix *b,tsmatrix *c) /*三元組相加算法*/int x,sum,pb,pc,pa;c-mu=a-mu;c-nu=a-nu;c-tu=0; /*定義矩陣c的非零元個數開始為0個*/ pa=1; pb=1; pc=1; for(x=1;xmu;x+)while(a-datapa.idatapb.idatapa.i=x & b-datapb.i=x) /*行數相等時*/if(a-datapa

7、.j=b-datapb.j) /*列數相等時*/sum=a-datapa.v+b-datapb.v; /*矩陣想加*/if(sum) /*相加不為零時*c-datapc.i=x;c-datapc.j=a-datapa.j;c-datapc.v=sum; pa+; pb+; pc+; elseif(a-datapa.jb-datapb.j) /*a的列數大于b的列數時*/c-datapc.i=x;c-datapc.j=b-datapb.j; c-datapc.v=b-datapb.v;pb+;pc+; else c-datapc.i=x;c-datapc.j=a-datapa.j;c-datap

8、c.v=a-datapa.v;pa+;pc+; while(a-datapa.i=x) /*插入a剩余的元素*/c-datapc.i=x; c-datapc.j=a-datapa.j; c-datapc.v=a-datapa.v; pa+; pc+;實驗項目：實驗學時： 實驗日期：實驗要求：實驗內容：c-tu=pc;main() tsmatrix *a , *b, *c; int b,e,k;a=(tsmatrix*)malloc(sizeof(tsmatrix);b=(tsmatrix*)malloc(sizeof(tsmatrix);c=(tsmatrix*)malloc(sizeof(t

9、smatrix); /*生成a、b、c三元組存儲空間*/printf(input a-mu:);/*輸入a的行數*/scanf(%d,&a-mu);printf(input a-nu:);scanf(%d,&a-nu); /*輸入b的列數*/printf(input a-tu:);scanf(%d,&a-tu);/*輸入a 的非零元*/printf(input a:n);/*輸入a的非零元三元組*/for(e=1;etu;e+)/*循環(huán)輸入a的三元組*/scanf(%d%d%d,&a-datae.i,&a-datae.j,&a-datae.v);printf(n);printf(input b

10、.tu:);/*輸入b的非零元三元組*/scanf(%d,&b-tu);printf(input b:n);for(k=1;ktu;k+)scanf(%d%d%d,&b-datak.i,&b-datak.j,&b-datak.v);printf(n);addtriple( a,b,c); /*引用相加算法*/printf(output c:n);/*輸出c的三元組*/for(b=1;btu;b+)printf(%d,%d,%dn,c-data-i,c-data-j,c-data-v);實驗項目：樹的應用實驗學時： 2 實驗日期：2011.10.7實驗要求：統(tǒng)計二叉樹中的葉子結點的個數實驗內容：

11、#include #include #define elemtype chartypedef struct bitnode elemtype data; struct bitnode *lchild,*rchild; bitnode;bitnode *bulid() bitnode *q; bitnode *s20; int i,j; char x; printf(請按順序輸入二叉樹的結點以輸入0和*號結束n); printf(請輸入你要輸入的為第幾個結點i=n); scanf(%d,&i); printf(請輸入你要輸入該結點的數為x=); getchar(); scanf(%c,&x);

12、while(i!=0&x!=*) q=(bitnode*)malloc(sizeof(bitnode); q-data=x; q-rchild=null; q-lchild=null; si=q; if(i!=1) j=i/2; if(i%2=0) sj-lchild=q; else sj-rchild=q; printf(請輸入你要輸入的為第幾個結點x=n); scanf(%d,&i); printf(請輸入你要輸入該結點的數x=); getchar(); scanf(%c,&x); return s1;void preoder(bitnode *bt) /*先序遍歷*/ if(bt!=nu

13、ll) printf(%cn,(bt-data); preoder(bt-lchild); preoder(bt-rchild);void inorder(bitnode *bt) /*中序遍歷*/ if(bt!=null) inorder(bt-lchild); printf(%cn,bt-data); inorder(bt-rchild);void postorder(bitnode *bt) /*后序遍歷*/ if(bt!=null) postorder(bt-lchild); postorder(bt-rchild); printf(%cn,bt-data);main() int a;

14、 bitnode *bt; bt=bulid();k1: printf(需要先序遍歷輸出請輸入1，中序遍歷請輸入2，后序遍歷請輸入3,結束輸入0:); scanf(%d,&a); switch(a) case(1): preoder(bt); goto k1; case(2): inorder(bt); goto k1; case(3): postorder(bt); goto k1; case(0): break; 實驗項目：圖的應用實驗學時： 2 實驗日期：2011.10.21實驗要求：編寫一個算法，由依次輸入的頂點數目、弧的數目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。先確立頂點、

15、弧的信息，并且要定義最大值、一維數組等，要有結構體類型（在函數外定義宏定義），建立數組后初始化，將頂點信息輸入進來并存放，即頂點信息初始化。實驗內容：#include stdio.h#include stdlib.h#define maxvertexnum 100typedef char vertextype;typedef struct node int adjvex;struct node *next;edgenode;typedef struct vnodevertextype vertex;edgenode *firstedge;vertexnode;typedef vertexnod

16、e adjlistmaxvertexnum;typedef structadjlist adjlist;int n,e;algraph;void creatalgraph(algraph *g)int i,j,k;edgenode *s;scanf(%d%d,&g-n,&g-e);for(i = 0;i n;i+)g-adjlisti.vertex = getchar();g-adjlisti.firstedge = null;for(k = 0;k e;k+)scanf(%d%d,&i,&j);s = (edgenode *)malloc(sizeof(edgenode);s-adjvex

17、= j;s-next = g-adjlisti.firstedge;g-adjlisti.firstedge = s;bool visitedmaxvertexnum;void dfs(algraph *g,int i)edgenode *p = g-adjlisti.firstedge;visitedi = true;while(p)if(!visitedp-adjvex)dfs(g,p-adjvex);p = p-next;bool isconnected(algraph *g)int i,j;for(i = 0;i n;i+)for(j = 0;j n;j+)visitedj = fal

18、se;dfs(g,i);for(j = 0;j n;j+)if(!visitedj)return false;return true;int main()algraph g;creatalgraph(&g);if(isconnected(&g)printf(連通n);elseprintf(不連通n);system(pause);實驗項目：排序、查找的應用實驗學時： 2 實驗日期：2011.10.28實驗要求：先從鍵盤輸入26個字母生成無序數組，對數組排序后，再從鍵盤輸入一個字符進行折半查找。實驗內容：#include#include#define max 50typedef char datatype;typedef struct datatype datamax; int length;sequelist;sequelist *initist(sequelist *l) l=(sequelist *)malloc(sizeof(sequelist); l-length=-1; return l;sequelist *bubblesort(sequelist *l) int i,j; datatype temp; for(i=0;ilength;i+) for(j=i+1;jlength;j+) if(l-datail-dataj) temp=l-d