數(shù)據(jù)結(jié)構(gòu)試驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu)實驗報告 學(xué)院：數(shù)理與信息工程學(xué)院 姓名： 班級： 學(xué)號：專心-專注-專業(yè)1、 線性表實驗一：順序表的刪除（一）實驗?zāi)康模?.掌握使用C+上機調(diào)試線性表的基本方法；2.掌握線性表的基本操作：插入、刪除、查找等運算在順序存儲結(jié)構(gòu)上的實現(xiàn)。（二)實驗內(nèi)容：實現(xiàn)一個線性表，對一個n不超過1000的線性表進行刪除操作。（3） 實驗程序：#include<stdio.h>#include<stdlib.h>typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;int ma

2、in() int n,m;while(scanf("%d",&n)!=EOF)LinkList L=(LinkList)malloc(sizeof(LNode);L->next=NULL;LinkList p=L,q;for(int i=1;i<=n;i+)q=(LinkList)malloc(sizeof(LNode);scanf("%d",&q->data);q->next=NULL;p->next=q;p=q;scanf("%d",&m);for(int j=1;j<=

3、m;j+)int num;scanf("%d",&num);p=L;int k;int e=-1;if(num>=1 && num<=n)for(k=1;k<num;k+)p=p->next;q=p->next;p->next=q->next;e=q->data;n-;free(q);printf("%dn",e); （4） 運行結(jié)果：（五）實驗總結(jié)：初次接觸數(shù)據(jù)結(jié)構(gòu)，心理有些期待，也有些畏懼。因為沒學(xué)習(xí)過這種程序，心里總擔(dān)心著能不能把它學(xué)好呢？當(dāng)我們把該章節(jié)學(xué)完就嘗試著做這個實驗，

4、說實話突然從理論到實驗還是消化不了呢，后來，通過慢慢的揣摩和問老師和同學(xué)，慢慢的做完了。實驗二：鏈表及其多項式相加（1） 實驗?zāi)康模?. 掌握使用C+上機調(diào)試線性表的基本方法；2. 掌握線性表的基本操作：插入、刪除、查找等運算在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。3. 掌握基于鏈表的多項式相加的算法。（2） 實驗內(nèi)容：通過有序?qū)斎攵囗検降母鱾€項，利用單鏈表存儲該一元多項式，并建立的2個存儲一元多項式的單鏈表，然后完成2個一元多項式的相加，并輸出相加后的多項式。（3） 實驗程序:#include<stdio.h>#include<stdlib.h>#include<malloc

5、.h>#include<conio.h>typedef struct Lnode int cof; int expn; struct Lnode *next;Lnode,*LinkList;void Creatpolyn(LinkList &La,int m) int i; LinkList p,q; La=(LinkList)malloc(sizeof(Lnode); La->next=NULL; p=La; for(i=1;i<=m;i+) q=(LinkList)malloc(sizeof(Lnode); q->next=NULL; scanf

6、("%d %d",&q->cof,&q->expn); p->next=q; p=q;LinkList addpolyn(LinkList &A,LinkList &B) LinkList pa,pb,pc,Lb,p1,p2; pc=Lb=A; pa=A->next; pb=B->next; while(pa && pb) if(pa->expn=pb->expn) pa->cof=pa->cof+pb->cof; if(pa->cof!=0) pc->n

7、ext=pa; pc=pa; p2=pb; pa=pa->next; pb=pb->next; free(p2); else p1=pa; p2=pb; pa=pa->next; pb=pb->next; free(p1); free(p2); else if(pa->expn>pb->expn) pc->next=pb; pc=pb; pb=pb->next; else if(pb->expn>pa->expn) pc->next=pa; pc=pa; pa=pa->next; pc->next=pa?

8、pa:pb; free(B); return(Lb); void printfpolyn(LinkList &p) while(p->next!=NULL) p=p->next; printf("%d %dn",p->cof,p->expn); int main() int n1,n2; LinkList A,B,C; scanf("%d",&n1); Creatpolyn(A,n1); scanf("%d",&n2); Creatpolyn(B,n2); C=addpolyn(A,B)

9、; printfpol（4） 運行結(jié)果：（5） 實驗總結(jié)：在學(xué)習(xí)C語言的時候，我就對指針類型概念很模糊，更加不用說怎樣運用他了。這個線性表的鏈?zhǔn)酱鎯σ彩沁@樣的。掌握了指針應(yīng)該怎么指向，做實驗并不是想像中的這么難，只要你自己理清楚了自己的思緒，一步一步的來，不要太急于成功了，那么，到了最后，你就會發(fā)現(xiàn)真的很容易。2、 棧實驗三：括號匹配判斷算法（1） 實驗?zāi)康模?.掌握使用C+上機調(diào)試棧的基本方法；2. 深入了解棧的特性，掌握棧的各種基本操作。（二）實驗內(nèi)容：假設(shè)在表達式中（）或（ ）等為正確的格式，（ ）或（ ）或 ( )均為不正確的格式。基于棧設(shè)計一個判斷括號是否正確匹配的算法。（3） 實驗

10、程序:#include<stdio.h>#include<stdlib.h>typedef struct snodechar data;struct snode *next;snode,*Linkstack;void Linkstackpush(Linkstack *ls,char e)Linkstack p=(Linkstack)malloc(sizeof(snode);p->data=e;p->next=*ls;*ls=p;int Linkstackpop(Linkstack *ls)Linkstack p;p=*ls;if(*ls=NULL) retu

11、rn 0;(*ls)=(*ls)->next;free(p);return 1;int Linkstackgettop(Linkstack ls,char *e)if(ls=NULL) return 0;*e=(ls)->data;return 1;void initLinkstack(Linkstack *ls)*ls=NULL;void matching(char str)char e;int k,flag=1;Linkstack s;initLinkstack(&s);for(k=0;strk!='0' && flag;k+)if(st

12、rk!='('&&strk!=')'&&strk!=''&&strk!=''&&strk!=''&&strk!='') continue;switch(strk)case'(':case'':case'':Linkstackpush(&s,strk);break;case')':if(s)Linkstackgettop(s,&e);if(e=

13、'(') Linkstackpop(&s);else flag=0;else flag=0; break;case'':if(s)Linkstackgettop(s,&e);if(e='')Linkstackpop(&s);else flag=0;else flag=0; break;case'':if(s)Linkstackgettop(s,&e);if(e='')Linkstackpop(&s);else flag=0;else flag=0; break; if(fla

14、g=1 && s=NULL)printf("yesn");else printf("non");int main()char str8000;while(gets(str)matching(str);return 0;（四）運行結(jié)果：實驗五：四則運算表達式求值（1） 實驗?zāi)康模?. 掌握順序棧的實現(xiàn)；2. 掌握順序棧的應(yīng)用；3. 利用棧實現(xiàn)算法優(yōu)先算法。（2） 實驗內(nèi)容：按中綴形式輸入一個四則運算的表達式，利用算法優(yōu)選算法把其轉(zhuǎn)換為后綴表達式輸出，并求表達式的值。（3） 實驗程序:#include<stdio.h> #incl

15、ude<stdlib.h> #define STACK_INIT_SIZE 10000 #define STACKINCREMENT 10 #define TURE 1 #define FALSE 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Selemtype; typedef int Status; typedef struct Selemtype *base; Selemtype *top; int stacksize; Sqstack; Status

16、initstack(Sqstack &s) s.base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype); if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return 0; Status travelstack(Sqstack s) Selemtype *p; p=s.base; printf("%c",*p+); while(p!=s.top) printf(" %c",*p+); retur

17、n 0; Status Gettop(Sqstack s) if(s.base=s.top) return ERROR; return *(s.top-1); Status push(Sqstack &s,Selemtype e) if(s.top-s.base>=s.stacksize) s.base=(Selemtype*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(Selemtype); if(!s.base) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize

18、+=STACKINCREMENT; *s.top=e; s.top+; return OK; Status pop(Sqstack &s,Selemtype &e) if(s.base=s.top) return ERROR; s.top-; e=*s.top; return OK; Status bijiao(Selemtype a,Selemtype b) switch(a) case '+': switch(b) case '+': case ')': case '#': case '-':r

19、eturn '>' case '*': case '/': case '(':return '<' case '-': switch(b) case '+': case ')': case '#': case '-':return '>' case '*': case '/': case '(':return '<' case 

20、9;*': switch(b) case '(':return '<' case '+': case ')': case '#': case '-': case '*': case '/':return '>' case '/': switch(b) case '(':return '<' case '+': case '#': case '

21、;)': case '*': case '-': case '/':return '>' case '(': switch(b) case ')':return '=' case '(': case '+': case '-': case '*': case '/':return '<' case ')': switch(b) case ')&#

22、39;: case '+': case '#': case '-': case '*': case '/':return '>' case '#': switch(b) case '#':return '=' case '(': case '+': case '-': case '*': case '/':return '<' Status op

23、erate(Selemtype a,Selemtype c,Selemtype b) switch(c) case '+':return a+b; case '-':return a-b; case '*':return (a)*(b); case '/':return (a)/(b); Status qiuzhi() Selemtype c,a,b,x,theta; Sqstack optr,opnd,houzhui; initstack(optr); initstack(opnd); initstack(houzhui); p

24、ush(optr,'#'); c=getchar(); while(c!='#'|Gettop(optr)!='#') if(c='n') c='#' if(c>='0'&&c<='9') push(opnd,c-48);push(houzhui,c);c=getchar(); else switch(bijiao(Gettop(optr),c) case '<':push(optr,c);c=getchar();break; cas

25、e '=':if(c='#') break; elsepop(optr,x);c=getchar();break; case '>':pop(optr,theta);pop(opnd,b);pop(opnd,a); push(houzhui,theta); push(opnd,operate(a,theta,b); break; travelstack(houzhui); printf("n"); return Gettop(opnd); int main() printf("%dn",qiuzhi(

26、); return 0; （4） 運行結(jié)果：（五）實驗總結(jié)：在這兩個實驗中，主要是要分析清楚出現(xiàn)不同情況下要進行的操作，調(diào)理清晰了才能編寫好程序。我剛開始也不是很分得清。后來在同學(xué)的幫助下，對這點有了進一步的了解。而我的耐心所以在出現(xiàn)的指向的問題上總是很煩，這一點需要改正。三、隊列實驗四：循環(huán)隊列插入與刪除操作（1） 實驗?zāi)康模?. 深入了解隊列的特性，掌握隊列的各種基本操作（二）實驗內(nèi)容：實現(xiàn)環(huán)形隊列(MAXN不超過)，能夠進行進隊出隊操作（3） 實驗程序:#include<stdio.h>#include<string.h>#define M int aM;int

27、tou,wei,geshu;int main()int T,k;int s;char mingl100;while(scanf("%d%*c",&T)!=EOF)tou=wei=geshu=0;for(k=1;k<=T;k+)scanf("%s",mingl);if(strcmp(mingl,"enqueue")=0)scanf("%d%*c",&s);geshu+;atou+=s;if(tou=M)tou=0;if(strcmp(mingl,"dequeue")=0)if

28、(tou=wei && geshu=0) printf("-1");elseprintf("%d",awei+);if(wei=M) wei=0;geshu-;printf("n");（4） 運行結(jié)果：（5） 實驗總結(jié)：通過這個實驗的上機操作，我從實質(zhì)上了解了隊列的實現(xiàn)和存儲方式，對于隊列有了更深的理解。并且學(xué)會了隊列的插入和刪除操作。4、 樹和二叉樹實驗八：二叉樹建立及其先序遍歷（1） 實驗?zāi)康模罕敬螌嶒灥哪康氖鞘煜涞母鞣N物理表示方法及各種遍歷方式(其中以二叉樹為側(cè)重點)，解樹在計算機科學(xué)及其他工程中的應(yīng)用。（2）

29、 實驗內(nèi)容：按先序遍歷順序輸入二叉樹的各個結(jié)點值，采用二叉鏈表的存儲結(jié)構(gòu)存儲該二叉樹，并按先序遍歷輸出二叉樹的各結(jié)點的值及深度。（3） 實驗程序:#include<stdio.h>#include<stdlib.h>#include<string.h>#define ERROR 0#define OK 1#define OVERFLOW -2#define MAX int k;char strMAX;typedef int status;typedef struct Binodechar data;int deep;Binode *parent;Binode

30、 *lchild;Binode *rchild;*Bitree;status prebitree(Bitree T)if(T)printf("%c(%d)",T->data,T->deep);prebitree(T->lchild);prebitree(T->rchild);return OK; status depthbitree(Bitree &T)if(T)if(T->lchild!=NULL)T->lchild->deep=T->deep+1;if(T->rchild!=NULL)T->rchild

31、->deep=T->deep+1;depthbitree(T->lchild);depthbitree(T->rchild);return OK;status creatbitree(Bitree &T)k+;if(strk='#') T=NULL;elseT=(Bitree)malloc(sizeof(Binode);if(!T) exit(OVERFLOW);T->data=strk;creatbitree(T->lchild);creatbitree(T->rchild);return OK;int main()k=-1;

32、scanf("%s",str);Bitree T;creatbitree(T);T->parent=NULL;T->deep=1;depthbitree(T);prebitree(T);printf("n");return 0;（4） 運行結(jié)果：實驗十：中序線索二叉樹（1） 實驗?zāi)康模?. 理解線索的含義，掌握線索二叉樹的算法；2. 了解中序線索及其遍歷的實現(xiàn)過程。（2） 實驗內(nèi)容：建立中序線索二叉樹，并按中序遍歷該二叉樹。（3） 實驗程序:#include<stdio.h>#include<stdlib.h>#def

33、ine OK 1#define ERROR 0#define OVERFLOW -1typedef int status;typedef enum PointerTagLink,Thread;typedef struct BiThrNodechar data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;BiThrTree pre;status CreateThrTree(BiThrTree &T)char ch;ch=getchar();if(ch='#')T=NU

34、LL;else T=(BiThrTree)malloc(sizeof(BiThrNode);T->data=ch;T->LTag=Link;T->RTag=Link;CreateThrTree(T->lchild);CreateThrTree(T->rchild);return OK;status InThreading(BiThrTree T)if(T)InThreading(T->lchild);if(!T->lchild)T->LTag=Thread;T->lchild=pre;if(!pre->rchild)pre->R

35、Tag=Thread;pre->rchild=T;pre=T;InThreading(T->rchild);return OK;status InOrderThreading(BiThrTree &Thrt,BiThrTree T)Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;else Thrt->lchild=T;pre=Thrt;InThreading(T

36、);pre->RTag=Thread;pre->rchild=Thrt;Thrt->rchild=pre;return OK;status InOrderTraverse_Thr(BiThrTree Thrt)BiThrTree p=Thrt->lchild;while(p!=Thrt)while(p->LTag=Link)p=p->lchild;printf("%c",p->data);while(p->RTag=Thread && p->rchild!=Thrt)p=p->rchild;prin

37、tf("%c",p->data);p=p->rchild;return OK;int main()BiThrTree Thrt,T;CreateThrTree(T);InOrderThreading(Thrt,T);InOrderTraverse_Thr(Thrt);puts("");return 0;（4） 運行結(jié)果：（五）實驗總結(jié)：1. 問題與解決方法 在編寫程序時， 遇到了一個程序保存后編譯正確卻運行不了， 之后請教了我們班的同學(xué)， 才知道是第一個函數(shù)出了問題，改了之后就好了。 2. 收獲和體會 做程序編寫時，必須要細心，有時候問題出現(xiàn)

38、了，可能會一直查不出來。自己也不容易 發(fā)現(xiàn)。在編寫這個程序時，我就出現(xiàn)了這個問題，之后一定要盡量避免此類問題出現(xiàn)。 3. 尚存在的問題 這幾個子函數(shù)的名稱都是邊看著書邊寫的， 還沒有完全脫離書本， 真正變成自己建的東 西。還要加強記憶。 五、圖實驗十二：圖的建立與遍歷（1） 實驗?zāi)康模?、 掌握圖的意義；2、 掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結(jié)構(gòu)；3、 理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲結(jié)構(gòu)。（2） 實驗內(nèi)容：按鄰接矩陣的方法創(chuàng)建圖，分別用深度優(yōu)先和廣度優(yōu)先方法遍歷圖。（3） 實驗程序:#include<stdio.h> #include<string.h&g

39、t; int n,m,tou,wei,team1000,biao200,ji200;struct node int a105,sum;e105; void DFS(int x) int i,j,p,q; for(i=0;i<ex.sum;i+) if(jiex.ai=0) jiex.ai=1; printf(" %d",ex.ai); DFS(ex.ai); void BFS() int i,j,p,q; for(i=0;i<n;i+) if(biaoi=0) biaoi=1; teamtou+=i; if(i=0) printf("%d",

40、i); else printf(" %d",i); while(tou>wei) p=teamwei+; for(j=0;j<ep.sum;j+) if(biaoep.aj=0) biaoep.aj=1; printf(" %d",ep.aj); teamtou+=ep.aj; printf("n"); int main () while(scanf("%d%d",&n,&m)!=EOF) memset(team,0,sizeof(team); memset(biao,0,sizeof(

41、biao); memset(ji,0,sizeof(ji); tou=0,wei=0; for(int i=1;i<=m;i+) int a,b; scanf("%d%d",&a,&b); ea.aea.sum+=b; eb.aeb.sum+=a; for(int i=0;i<n;i+) if(jii=0) if(i=0) printf("%d",i); else printf(" %d",i); jii=1; DFS(i); printf("n"); BFS(); printf(&qu

42、ot;n"); （4） 運行結(jié)果：(五）實驗總結(jié)：圖的存儲結(jié)構(gòu)相比表和樹都要復(fù)雜，其操作過程也較難進行掌握。僅僅是創(chuàng)建圖的存儲結(jié)構(gòu)便分為矩陣、臨接鏈表、十字鏈表等，對于每一種存儲結(jié)構(gòu)又分為有向與無向之分。然而，深度優(yōu)先和廣度優(yōu)先是兩種算法，其算法思想并不依賴與元素的存儲方式，也就是說算法思想不會因為存儲結(jié)構(gòu)的改變而發(fā)生改變，當(dāng)然對于不同的存儲結(jié)構(gòu)僅僅是代碼的表現(xiàn)形式不同而已，正所謂一同百通，只要熟悉存儲結(jié)構(gòu)的特點又對算法思想爛熟于心便可無往不勝。實驗十三：最小生成樹Prim算法（1） 實驗?zāi)康模?. 理解構(gòu)造無向連通圖的最小生成樹的Prim算法；2. 能用Prim算法求出最小生成樹。

43、（2） 實驗內(nèi)容：農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長！他其中一個競選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場。當(dāng)然，他需要你的幫助。 約翰已經(jīng)給他的農(nóng)場安排了一條高速的網(wǎng)絡(luò)線路，他想把這條線路共享給其他農(nóng)場。為了用最小的消費，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場。 你將得到一份各農(nóng)場之間連接費用的列表，你必須找出能連接所有農(nóng)場并所用光纖最短的方案。 每兩個農(nóng)場間的距離不會超過。（3） 實驗程序:#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -1#define MA

44、X_VERTEX_NUM 100typedef int Status;typedef struct int vexsMAX_VERTEX_NUM;int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vexnum;MGraph;structint adjvex;int lowcost;closedgeMAX_VERTEX_NUM;Status CreateGraph(MGraph &G)int i,j;scanf("%d",&G.vexnum);for(i=0;i<G.vexnum;i+)G.vexsi=i;for(j=0;

45、j<G.vexnum;j+)scanf("%d",&G.arcsij);return OK;Status mininum(int num)int i,w=1;for(i=1;i<num;i+)if(closedgei.lowcost) w=i;break; for(i+;i<num;i+) if(closedgei.lowcost && (closedgew.lowcost>closedgei.lowcost)w=i; return w;Status MiniSpanTree_PRIM(MGraph &G,int v)

46、int i,j,w,sum=0;for(i=0;i<G.vexnum;i+)closedgei.adjvex=v;closedgei.lowcost=G.arcsvi;for(i=1;i<G.vexnum;i+)w=mininum(G.vexnum);sum+=closedgew.lowcost;closedgew.lowcost=0;for(j=1;j<G.vexnum;j+)if(closedgej.lowcost && (G.arcswj<closedgej.lowcost)closedgej.adjvex=w;closedgej.lowcost=

47、G.arcswj;printf("%dn",sum);return OK;int main()MGraph G;CreateGraph(G);MiniSpanTree_PRIM(G,0);return 0;（4） 運行結(jié)果：（5） 實驗總結(jié)：通過此次實驗后我深刻地學(xué)習(xí)了最小生成樹的Prim算法，通過分析實驗?zāi)康暮蛯嶒瀮?nèi)容；闡述不同方法的原理；分析不同方法的特點和區(qū)別以及時空復(fù)雜度；分析和調(diào)試測試數(shù)據(jù)和相應(yīng)的結(jié)果.明白了Prim算法是設(shè)計思想：設(shè)圖G =（V，E），其生成樹的頂點集合為U。 把v0放入U。；在所有uU，vV-U的邊(u，v)E中找一條最小權(quán)值的邊，加入生成樹；

48、把找到的邊的v加入U集合。如果U集合已有n個元素，則結(jié)束，否則繼續(xù)執(zhí)行。Prim算法實現(xiàn)：一方面利用集合，設(shè)置一個數(shù)組set(i=0,1,.,n-1),初始值為 0,代表對應(yīng)頂點不在集合中（注意：頂點號與下標(biāo)號差1） 。從算法、輸入方便、存儲安全等角度，我采用數(shù)組作為數(shù)據(jù)結(jié)構(gòu)，即采用鄰接矩陣的存儲方式來存儲無向帶權(quán)圖。另一方面，圖用鄰接矩陣或鄰接表表示。通過本次的試驗我大體掌握了圖的基本操作設(shè)計與實現(xiàn)并學(xué)會利用Prim算法求網(wǎng)絡(luò)的最小生成樹。雖然本次試驗做起來是比較成功的，但是我感覺還有不足試驗效率很低，很難理解參考代碼，所以測試時有一部分用了參考代碼。然而我感覺自還是很有收獲的，基本上讀懂了參考代碼，領(lǐng)悟了一些編程思想。 實驗十五：單源最短路Dijkstra算法（一）實驗?zāi)康模?、 理解單源最短路的Dijkstra算法；2、 能用Dijkstra算法求出兩點之間的最短路。（二）實驗內(nèi)容：某省自從實行了很多年的暢通工程計劃后，終于修建了很多路。不過路多了也不好，每次要從一個城鎮(zhèn)到另一個城鎮(zhèn)時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾?，F(xiàn)在，已知起點和終點，請你計算出要從起點到終