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

1、.數(shù)據(jù)結(jié)構(gòu)實驗報告學院：數(shù)理與信息工程學院姓名：班級：學號：.一、線性表實驗一：順序表的刪除（一）實驗?zāi)康模?. 掌握使用 C+上機調(diào)試線性表的基本方法；2. 掌握線性表的基本操作：插入、刪除、查找等運算在順序存儲結(jié)構(gòu)上的實現(xiàn)。（二 ) 實驗內(nèi)容：實現(xiàn)一個線性表，對一個 n 不超過 1000 的線性表進行刪除操作。（三）實驗程序：#include#includetypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;int main() int n,m; while(scanf(%d,&n)!=EOF)LinkList L

2、=(LinkList)malloc(sizeof(LNode); L-next=NULL;.LinkList p=L,q;for(int i=1;idata);q-next=NULL;p-next=q;p=q;scanf(%d,&m);for(int j=1;j=1 & num=n)for(k=1;knext;q=p-next;p-next=q-next;e=q-data;.n-;free(q);printf(%dn,e);（四）運行結(jié)果：（五）實驗總結(jié)：初次接觸數(shù)據(jù)結(jié)構(gòu)，心理有些期待，也有些畏懼。因為沒學習過這種程序，心里總擔心著能不能把它學好呢？當我們把該章節(jié)學完就嘗試著做這個實驗，說實話

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

4、 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;inext=NULL;scanf(%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-

5、next;while(pa & pb)if(pa-expn=pb-expn)pa-cof=pa-cof+pb-cof;if(pa-cof!=0)pc-next=pa;pc=pa;p2=pb;.pa=pa-next;pb=pb-next;free(p2);elsep1=pa;p2=pb;pa=pa-next;pb=pb-next;free(p1);free(p2);else if(pa-expnpb-expn)pc-next=pb;pc=pb;pb=pb-next;else if(pb-expnpa-expn)pc-next=pa;pc=pa;pa=pa-next;.pc-next=pa?pa:

6、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);printfpol（四）運行結(jié)果：（五）實驗總結(jié)：在學習 C語言的時候，我就對指針類型概念很模糊， 更加不用說怎樣運用他了。這個線性表的鏈式存儲也是這樣的。

7、掌握了指針應(yīng)該怎么指向，做實驗并不是想像中的這么難， 只要你自己理清楚了自己的思緒，一步一步的來，不要太急于成功了，那么，到了最后，你就會發(fā)現(xiàn)真的很容易。二、棧實驗三： 括號匹配判斷算法（一）實驗?zāi)康模?. 掌握使用 C+上機調(diào)試棧的基本方法；2. 深入了解棧的特性，掌握棧的各種基本操作。.（二）實驗內(nèi)容：假設(shè)在表達式中（）或（ ）等為正確的格式，（ ）或（ ）或 ( )均為不正確的格式?；跅ＴO(shè)計一個判斷括號是否正確匹配的算法。（三）實驗程序 :#include#includetypedef struct snodechar data;struct snode *next;snode,*Li

8、nkstack;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)return 0;(*ls)=(*ls)-next;.free(p);return 1;int Linkstackgettop(Linkstack ls,char *e)if(ls=NULL)return 0;*e=(ls)-data;r

9、eturn 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(strk!=(&strk!=)&strk!=&strk!=&strk!=&strk!=)continue;switch(strk).case(:case:case:Linkstackpush(&s,strk);break;case):if(s)Linkstackgettop(s,&e);if(e

10、=() 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(flag=1 & s=NULL)printf(yesn);else printf(non);int main()char str8000;whi

11、le(gets(str)matching(str);return 0;（四）運行結(jié)果：實驗五：四則運算表達式求值（一）實驗?zāi)康模?. 掌握順序棧的實現(xiàn)；2. 掌握順序棧的應(yīng)用；.3. 利用棧實現(xiàn)算法優(yōu)先算法。（二）實驗內(nèi)容：按中綴形式輸入一個四則運算的表達式， 利用算法優(yōu)選算法把其轉(zhuǎn)換為后綴表達式輸出，并求表達式的值。（三）實驗程序 : #include #include#define STACK_INIT_SIZE 10000 #define STACKINCREMENT 10 #define TURE 1#define FALSE 0 #define INFEASIBLE -1 #defi

12、ne OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Selemtype; typedef int Status; typedef structSelemtype *base;Selemtype *top;int stacksize;.Sqstack;Status initstack(Sqstack &s) s.base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STAC

13、K_INIT_SIZE;return 0;Status travelstack(Sqstack s)Selemtype *p;p=s.base;printf(%c,*p+);while(p!=s.top)printf( %c,*p+);.return 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.

14、stacksize+STACKINCREMENT)*sizeof(Selemtype);if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=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 +:swit

15、ch(b)case +:case ):case #:.case -:return ;case *:case /:case (:return ;case *:case /:case (:return ;case *:switch(b)case (:return ;case /:switch(b)case (:return ;case (:switch(b)case ):return =;case (:case +:.case -:case *:case /:return ;case #:switch(b)case #:return =;case (:case +:case -:case *:.c

16、ase /:return =0&c=9)push(opnd,c-48);push(houzhui,c);c=getchar();elseswitch(bijiao(Gettop(optr),c)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();return 0;（四）運行結(jié)果：（五

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

18、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(tou=wei & geshu=0) printf(-1);elseprintf(%d,awei+);if(wei=M) wei=0;geshu-;printf(n);（四）運行結(jié)果：（五）實驗總結(jié)：通過這個實驗的上

19、機操作，我從實質(zhì)上了解了隊列的實現(xiàn)和存儲方式，對于隊列有了更深的理解。并且學會了隊列的插入和刪除操作。四、樹和二叉樹實驗八：二叉樹建立及其先序遍歷（一）實驗?zāi)康模罕敬螌嶒灥哪康氖鞘煜涞母鞣N物理表示方法及各種遍歷方式( 其中.以二叉樹為側(cè)重點 ) ，解樹在計算機科學及其他工程中的應(yīng)用。（二）實驗內(nèi)容：按先序遍歷順序輸入二叉樹的各個結(jié)點值，采用二叉鏈表的存儲結(jié)構(gòu)存儲該二叉樹，并按先序遍歷輸出二叉樹的各結(jié)點的值及深度。（三）實驗程序 :#include#include#include#define ERROR 0#define OK 1#define OVERFLOW -2#define MAX

20、100000000int k;char strMAX;typedef int status;typedef struct Binodechar data;int deep;Binode *parent;Binode *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!=NUL

21、L)T-lchild-deep=T-deep+1;if(T-rchild!=NULL)T-rchild-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 m

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

23、f 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=NULL;else T=(BiThrTree)malloc(sizeof(BiThrNode);T-data=ch;T-

24、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-RTag=Thread;pre-rchild=T;pre=T;InThreading(T-rchild);return OK;status InOrderThreading(BiThrTree &Thrt

25、,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);pre-RTag=Thread;pre-rchild=Thrt;Thrt-rchild=pre;.return OK;status InOrderTraverse_Thr(BiThrTree Thrt) BiThrTree p=Thrt-lchild; wh

26、ile(p!=Thrt)while(p-LTag=Link)p=p-lchild;printf(%c,p-data);while(p-RTag=Thread & p-rchild!=Thrt)p=p-rchild;printf(%c,p-data);p=p-rchild;return OK;int main()BiThrTree Thrt,T;CreateThrTree(T);InOrderThreading(Thrt,T);InOrderTraverse_Thr(Thrt);puts();return 0;.（四）運行結(jié)果：（五）實驗總結(jié)：1. 問題與解決方法 在編寫程序時， 遇到了一個程序

27、保存后編譯正確卻運行不了， 之后請教了我們班的同學， 才知道是第一個函數(shù)出了問題， 改了之后就好了。 2. 收獲和體會 做程序編寫時，必須要細心，有時候問題出現(xiàn)了，可能會一直查不出來。 自己也不容易 發(fā)現(xiàn)。在編寫這個程序時， 我就出現(xiàn)了這個問題，之后一定要盡量避免此類問題出現(xiàn)。3.尚存在的問題這幾個子函數(shù)的名稱都是邊看著書邊寫的，還沒有完全脫離書本，真正變成自己建的東西。還要加強記憶。五、圖實驗十二：圖的建立與遍歷（一）實驗?zāi)康模?、掌握圖的意義；2、掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結(jié)構(gòu)；3、理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲結(jié)構(gòu)。（二）實驗內(nèi)容：按鄰接矩陣的方法創(chuàng)建圖，分別用

28、深度優(yōu)先和廣度優(yōu)先方法遍歷圖。（三）實驗程序 :#include.#includeint n,m,tou,wei,team1000,biao200,ji200; struct nodeint a105,sum;e105;void DFS(int x) int i,j,p,q;for(i=0;iex.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;iwei)p=teamwei+;for(j=0;jep.sum;j+)if(biaoep.aj=0) biaoep.aj

29、=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(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;in;i+)if(jii=0)if(i=0)printf(%d,i);els

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

31、）實驗?zāi)康模?. 理解構(gòu)造無向連通圖的最小生成樹的 Prim 算法；2. 能用 Prim 算法求出最小生成樹。（二）實驗內(nèi)容：農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長！ 他其中一個競選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場。當然，他需要你的幫助。約翰已經(jīng)給他的農(nóng)場安排了一條高速的網(wǎng)絡(luò)線路，他想把這條線路共享給其他農(nóng)場。為了用最小的消費，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場。你將得到一份各農(nóng)場之間連接費用的列表，你必須找出能連接所有農(nóng).場并所用光纖最短的方案。每兩個農(nóng)場間的距離不會超過100000。（三）實驗程序 :#include#include#define OK 1#define ERROR 0#

32、define OVERFLOW -1#define MAX_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;iG.vexnum;i+).G.vexsi=i;fo

33、r(j=0;jG.vexnum;j+)scanf(%d,&G.arcsij);return OK;Status mininum(int num)int i,w=1;for(i=1;inum;i+)if(closedgei.lowcost) w=i;break;for(i+;iclosedgei.lowcost)w=i; return w;Status MiniSpanTree_PRIM(MGraph &G,int v)int i,j,w,sum=0;for(i=0;iG.vexnum;i+)closedgei.adjvex=v;closedgei.lowcost=G.arcsvi;.for(i=1;iG.vexnum;i+)w=mininum(G.vexnum);sum+=closedgew.lowcost;closedgew.lowcost=0;for(j=1;jG.vexnum;j+)if(closedgej.lowcost &(G.arcswjclosedgej.lowcost)closedgej.adjvex=w;closedgej.lowcost=G.arcswj;printf(%dn,sum);return OK;int main()MGraph G;CreateGraph(G);MiniSpanTree_PRIM(G,0);return 0;.（