數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院：數(shù)理與信息工程學(xué)院姓名：班級(jí)：學(xué)號(hào)：.一、線性表實(shí)驗(yàn)一：順序表的刪除（一）實(shí)驗(yàn)?zāi)康模?. 掌握使用 C+上機(jī)調(diào)試線性表的基本方法；2. 掌握線性表的基本操作：插入、刪除、查找等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。（二 ) 實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)一個(gè)線性表，對(duì)一個(gè) n 不超過(guò) 1000 的線性表進(jìn)行刪除操作。（三）實(shí)驗(yàn)程序：#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);（四）運(yùn)行結(jié)果：（五）實(shí)驗(yàn)總結(jié)：初次接觸數(shù)據(jù)結(jié)構(gòu)，心理有些期待，也有些畏懼。因?yàn)闆]學(xué)習(xí)過(guò)這種程序，心里總擔(dān)心著能不能把它學(xué)好呢？當(dāng)我們把該章節(jié)學(xué)完就嘗試著做這個(gè)實(shí)驗(yàn)，說(shuō)實(shí)話

3、突然從理論到實(shí)驗(yàn)還是消化不了呢，后來(lái)，通過(guò)慢慢的揣摩和問(wèn)老師和同學(xué)，慢慢的做完了。實(shí)驗(yàn)二：鏈表及其多項(xiàng)式相加（一）實(shí)驗(yàn)?zāi)康模?. 掌握使用 C+上機(jī)調(diào)試線性表的基本方法；.2. 掌握線性表的基本操作：插入、刪除、查找等運(yùn)算在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。3. 掌握基于鏈表的多項(xiàng)式相加的算法。（二）實(shí)驗(yàn)內(nèi)容：通過(guò)有序?qū)斎攵囗?xiàng)式的各個(gè)項(xiàng)，利用單鏈表存儲(chǔ)該一元多項(xiàng)式，并建立的 2 個(gè)存儲(chǔ)一元多項(xiàng)式的單鏈表， 然后完成 2 個(gè)一元多項(xiàng)式的相加，并輸出相加后的多項(xiàng)式。（三）實(shí)驗(yàn)程序 :#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（四）運(yùn)行結(jié)果：（五）實(shí)驗(yàn)總結(jié)：在學(xué)習(xí) C語(yǔ)言的時(shí)候，我就對(duì)指針類型概念很模糊， 更加不用說(shuō)怎樣運(yùn)用他了。這個(gè)線性表的鏈?zhǔn)酱鎯?chǔ)也是這樣的。

7、掌握了指針應(yīng)該怎么指向，做實(shí)驗(yàn)并不是想像中的這么難， 只要你自己理清楚了自己的思緒，一步一步的來(lái)，不要太急于成功了，那么，到了最后，你就會(huì)發(fā)現(xiàn)真的很容易。二、棧實(shí)驗(yàn)三： 括號(hào)匹配判斷算法（一）實(shí)驗(yàn)?zāi)康模?. 掌握使用 C+上機(jī)調(diào)試棧的基本方法；2. 深入了解棧的特性，掌握棧的各種基本操作。.（二）實(shí)驗(yàn)內(nèi)容：假設(shè)在表達(dá)式中（）或（ ）等為正確的格式，（ ）或（ ）或 ( )均為不正確的格式。基于棧設(shè)計(jì)一個(gè)判斷括號(hào)是否正確匹配的算法。（三）實(shí)驗(yàn)程序 :#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;（四）運(yùn)行結(jié)果：實(shí)驗(yàn)五：四則運(yùn)算表達(dá)式求值（一）實(shí)驗(yàn)?zāi)康模?. 掌握順序棧的實(shí)現(xiàn)；2. 掌握順序棧的應(yīng)用；.3. 利用棧實(shí)現(xiàn)算法優(yōu)先算法。（二）實(shí)驗(yàn)內(nèi)容：按中綴形式輸入一個(gè)四則運(yùn)算的表達(dá)式， 利用算法優(yōu)選算法把其轉(zhuǎn)換為后綴表達(dá)式輸出，并求表達(dá)式的值。（三）實(shí)驗(yà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;（四）運(yùn)行結(jié)果：（五

17、）實(shí)驗(yàn)總結(jié)：在這兩個(gè)實(shí)驗(yàn)中，主要是要分析清楚出現(xiàn)不同情況下要進(jìn)行的操作，調(diào)理清晰了才能編寫好程序。 我剛開始也不是很分得清。 后來(lái)在同學(xué)的幫助下，對(duì)這點(diǎn)有了進(jìn)一步的了解。 而我的耐心所以在出現(xiàn)的指向的問(wèn)題上總是很煩，這一點(diǎn)需要改正。三、隊(duì)列實(shí)驗(yàn)四：循環(huán)隊(duì)列插入與刪除操作（一）實(shí)驗(yàn)?zāi)康模?. 深入了解隊(duì)列的特性，掌握隊(duì)列的各種基本操作（二）實(shí)驗(yàn)內(nèi)容：.實(shí)現(xiàn)環(huán)形隊(duì)列 (MAXN不超過(guò) 100001)，能夠進(jìn)行進(jìn)隊(duì)出隊(duì)操作（三）實(shí)驗(yàn)程序 :#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);（四）運(yùn)行結(jié)果：（五）實(shí)驗(yàn)總結(jié)：通過(guò)這個(gè)實(shí)驗(yàn)的上

19、機(jī)操作，我從實(shí)質(zhì)上了解了隊(duì)列的實(shí)現(xiàn)和存儲(chǔ)方式，對(duì)于隊(duì)列有了更深的理解。并且學(xué)會(huì)了隊(duì)列的插入和刪除操作。四、樹和二叉樹實(shí)驗(yàn)八：二叉樹建立及其先序遍歷（一）實(shí)驗(yàn)?zāi)康模罕敬螌?shí)驗(yàn)的目的是熟悉樹的各種物理表示方法及各種遍歷方式( 其中.以二叉樹為側(cè)重點(diǎn) ) ，解樹在計(jì)算機(jī)科學(xué)及其他工程中的應(yīng)用。（二）實(shí)驗(yàn)內(nèi)容：按先序遍歷順序輸入二叉樹的各個(gè)結(jié)點(diǎn)值，采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)該二叉樹，并按先序遍歷輸出二叉樹的各結(jié)點(diǎn)的值及深度。（三）實(shí)驗(yàn)程序 :#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;（四）運(yùn)行結(jié)果：.實(shí)驗(yàn)十： 中序線索二叉樹（一）實(shí)驗(yàn)?zāi)康模?. 理解線索的含義，掌握線索二叉樹的算法；2. 了解中序線索及其遍歷的實(shí)現(xiàn)過(guò)程。（二）實(shí)驗(yàn)內(nèi)容：建立中序線索二叉樹，并按中序遍歷該二叉樹。（三）實(shí)驗(yàn)程序 : #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;.（四）運(yùn)行結(jié)果：（五）實(shí)驗(yàn)總結(jié)：1. 問(wèn)題與解決方法 在編寫程序時(shí)， 遇到了一個(gè)程序

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

28、深度優(yōu)先和廣度優(yōu)先方法遍歷圖。（三）實(shí)驗(yàn)程序 :#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);.（四）運(yùn)行結(jié)果：( 五）實(shí)驗(yàn)總結(jié)： 圖的存儲(chǔ)結(jié)構(gòu)相比表和樹都要復(fù)雜，其操作過(guò)程也較難進(jìn)行掌握。僅僅是創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)便分為矩陣、 臨接鏈表、 十字鏈表等， 對(duì)于每一種存儲(chǔ)結(jié)構(gòu)又分為有向與無(wú)向之分。 然而，深度優(yōu)先和廣度優(yōu)先是兩種算法， 其算法思想并不依賴與元素的存儲(chǔ)方式，也就是說(shuō)算法思想不會(huì)因?yàn)榇鎯?chǔ)結(jié)構(gòu)的改變而發(fā)生改變， 當(dāng)然對(duì)于不同的存儲(chǔ)結(jié)構(gòu)僅僅是代碼的表現(xiàn)形式不同而已， 正所謂一同百通， 只要熟悉存儲(chǔ)結(jié)構(gòu)的特點(diǎn)又對(duì)算法思想爛熟于心便可無(wú)往不勝。實(shí)驗(yàn)十三：最小生成樹Prim 算法（一

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