南昌大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（1）姓名： 學(xué)號(hào)： 專業(yè)班級(jí)： 實(shí)驗(yàn)?zāi)康模簬椭鷮W(xué)生掌握線性表的基本操作在順序和鏈表這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，尤以鏈表的操作和應(yīng)用作為重點(diǎn)。問(wèn)題描述：1、 構(gòu)造一個(gè)空的線性表l。2、 在線性表l的第i個(gè)元素之前插入新的元素e；3、 在線性表l中刪除第i個(gè)元素，并用e返回其值。實(shí)驗(yàn)要求：1、 分別利用順序和鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的存儲(chǔ)，并設(shè)計(jì)出在不同的存儲(chǔ)結(jié)構(gòu)中線性表的基本操作算法。2、 在實(shí)驗(yàn)過(guò)程中，對(duì)相同的操作在不同的存儲(chǔ)結(jié)構(gòu)下的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行分析。文法是一個(gè)四元 算法分析：#include#include#includeusing nam

2、espace std;#define list_init_size 100#define listincrement 10typedef structint *elem;int length;int listsize;sqlist;int initlist_sq(sqlist &l)l.elem=(int *)malloc(list_init_size*sizeof(int);if(!l.elem)return(0);l.length=0;l.listsize=list_init_size;return(1);int listcreat_sq(sqlist &l,int n,int a)int

3、 i;for(i=0;in;i+)l.elemi=ai;l.length=n;return (1);int listinsert_sq(sqlist &l,int i,int e)int *p;int *q;int *newbase;void listprint_sq(sqlist &l);if(il.length+1)coutdata error!=l.listsize)newbase=(int *)malloc(l.listsize+listincrement)*sizeof(int);if(!newbase)couterror!=q;-p)*(p+1)=*p;*q=e;+l.length

4、;cout insert order:endl;listprint_sq(l);return(2);int listdelete_sq(sqlist &l,int i,int e)int *p;int *q;int j;void listprint_sq(sqlist &l);if(il.length)coutdata error!endl;return(0);p=&(l.elemi-1);e=*p;q=l.elem+l.length-1;for(+p;p=q;+p)*(p-1)=*p;l.length-;cout deleted order:endl;listprint_sq(l);retu

5、rn(1);void listprint_sq(sqlist &l)int i;for(i=0;il.length;i+)coutsetw(5)l.elemi;coutendl;int main()sqlist l;int e=0,i;int a8;int insert_position=0;int insert_number=0;int delete_position=0;if(initlist_sq(l)=1)coutyes!endl;elsecoutsorry!endl;coutinput 8 numbers initialize the lianbiao:endl;for(i=0;ia

6、i;listcreat_sq(l,8,a);coutthe original order:endl;listprint_sq(l);coutinput the insert number insert_number;coutinput the insert position insert_position;listinsert_sq(l,insert_position,insert_number);coutinput the delete positiondelete_position;listdelete_sq(l,delete_position,e);(2).鏈表實(shí)現(xiàn)線性表的建立、插入和刪

7、除操作程序：#include#include#includeusing namespace std;typedef struct lnodeint data;struct lnode *next;lnode, *linklist;int listcreate_l(linklist &l,int n)void listprint_l(linklist &l);int i; linklist p;l=(linklist)malloc(sizeof(lnode);l-next=null;for(i=n;i0;-i)p=(linklist)malloc(sizeof(lnode);cinp-data;

8、p-next=l-next;l-next=p;coutthe original order:endl;listprint_l(l);return(1);int listinsert_l(linklist &l,int i,int e)linklist p=l;linklist s;int j=0;void listprint_l(linklist &l);while(p&jnext;+j;if(!p|ji-1)coutdata error!data=e;s-next=p-next;p-next=s;cout inserted order:next&jnext;+j;if(!(p-next)|j

9、i-1)coutdata error!next;p-next=q-next;e=q-data;coutdeleted order:next;while(p)coutsetw(5)data;p=p-next;coutendl;int main()linklist l;int number;int e;int insert_position=0;int insert_number=0;int delete_position=0;coutinput the number of node that you want to create:number;coutinput the reversed dat

10、a to inliliaze the lianbiao:(按逆序輸入數(shù)據(jù)初始化鏈表)endl;listcreate_l(l,number);coutinput the insert numberinsert_number;coutinput the insert position.insert_position;listinsert_l(l,insert_position,insert_number);coutinput the delete positiondelete_position;listdelete_l(l,delete_position,e);實(shí)驗(yàn)內(nèi)容和過(guò)程：實(shí)驗(yàn)結(jié)果：總結(jié)和感想

11、：閱讀完刪除本文本框要求：根據(jù)本格式填寫實(shí)驗(yàn)報(bào)告，標(biāo)題用黑小四，正文字體用五號(hào)字體，word文本以“數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)(1)_學(xué)號(hào)_姓名”命名。實(shí)驗(yàn)?zāi)康模荷钊肓私鈼：完?duì)列的特性，學(xué)會(huì)在實(shí)際問(wèn)題下靈活運(yùn)用它們。問(wèn)題描述：表達(dá)式求值運(yùn)算是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧應(yīng)用的一個(gè)典型例子。設(shè)計(jì)并演示用算符優(yōu)先級(jí)對(duì)算術(shù)表達(dá)式的求解過(guò)程。實(shí)驗(yàn)要求：1、算法優(yōu)先級(jí)別如下：+, -, *, /, (, ), #+ , , , , , ,- , , , , , ,* , , , , , ,/ , , , , , ,( , , , , , , , , , , ,# , , , , , , =2、以字符序列的形

12、式從終端輸入語(yǔ)法正確、不含變量的算術(shù)表達(dá)式，利用給出的算符優(yōu)先級(jí)關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算的求解過(guò)程。文法是一個(gè)四元算法分析：實(shí)驗(yàn)內(nèi)容和過(guò)程：#include#include#includeusing namespace std;char a7=+,-,*,/,(,),#;char b77=, , , , ,=s.stacksize)s.base=(char *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(char);if(!s.base)return 0; s.top=s.base+s.stacksize;s.stacksize+=

13、stackincrement;*s.top+ =e;return 1;char pop(sqstack &s)char e;if(s.top=s.base)return 0;e= * -s.top;return e;int in(char c)int i;for(i=0;i=6;i+)if(ai=c)return 1;return 0;char precede(char c1,char c2)int i=0;int j=0;while(ai!=c1)i+;while(aj!=c2)j+;return bij;char operate(char x,char c,char y)int i=0;i

14、nt m,n;char d;m=x-0;n=y-0;while(c!=ai)i+;switch(ai)case +:d=(m+n)+0;break;case -:d=(m-n)+0;break;case *:d=m*n+0;break;case /:d=m/n+0;break;return d;int main()sqstack optr,opnd;char c;char theta;char x1,x2;initstack(optr);push(optr,#);initstack(opnd);c=cin.get();while(c!=#|gettop(optr)!=#)if(!in(c)pu

15、sh(opnd,c);c=cin.get();elseswitch(precede(gettop(optr),c)case :theta=pop(optr);x2=pop(opnd);x1=pop(opnd);push(opnd,operate(x1,theta,x2);break;cout(int(gettop(opnd)-0)endl;實(shí)驗(yàn)結(jié)果：總結(jié)和感想：雖然書上有算法，但是自己真正去編寫的時(shí)候才發(fā)現(xiàn)其實(shí)還是有難度的，關(guān)鍵有一個(gè)ascii碼的轉(zhuǎn)換問(wèn)題，什么時(shí)候變整型，什么時(shí)候變字符型符合條件。實(shí)驗(yàn)?zāi)康模荷钊胙芯繑?shù)組的存儲(chǔ)表示和實(shí)現(xiàn)技術(shù)，著重掌握對(duì)稀疏矩陣的表示方法及其運(yùn)算的實(shí)現(xiàn)。問(wèn)題描述

16、：稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用稀疏特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高效率。通過(guò)對(duì)稀疏矩陣的存儲(chǔ)表示，實(shí)現(xiàn)矩陣的基本操作。實(shí)驗(yàn)要求：1、 要求矩陣的輸入形式采用三元組表示，以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣。2、 設(shè)計(jì)矩陣的逆置算法，實(shí)現(xiàn)矩陣的逆置。3、 實(shí)現(xiàn)兩個(gè)稀疏矩陣的相加、相減和相乘等運(yùn)算。4、 要求運(yùn)算結(jié)果的矩陣則以通常的陣列形式出現(xiàn)。文法是一個(gè)四元實(shí)驗(yàn)內(nèi)容和過(guò)程：輸入數(shù)據(jù)：2 1 00 0 00 0 32 0 01 0 00 0 3-12 1 00 0 00 0 30 0 00 0 00 0 2+=2 1 00 0 00 0 52 1 00 0 30

17、 00 00 2+=0 00 6源代碼：#include #include using namespace std; const int maxsize=12500; const int maxrc=10; typedef struct int i,j; int e; triple; typedef struct triple datamaxsize+1; int mu,nu,tu; tsmatrix; typedef struct triple datamaxsize+2; int rposmaxrc+1; int mu,nu,tu; rlsmatrix; template bool inp

18、uttsmatrix(p & t,int y) cout輸?入?矩?陣的?行d列d非?零?元a個(gè)?數(shù)y:t.mut.nut.tu; cout輸?入?非?零?元a的?位?置?和值:endl; int k=1; for(;kt.datak.it.datak.jt.datak.e; return true; template bool outputsmatrix(p t) int m,n,k=1; for(m=0;mt.mu;m+) for(n=0;nt.nu;n+) if(t.datak.i-1)=m&(t.datak.j-1)=n) cout.width(4); coutt.datak+.e;

19、else cout.width(4); cout0; coutendl; return true; bool transposesmatrix( ) tsmatrix m,t; /定義?預(yù)轉(zhuǎn)aa置?的?矩?陣 inputtsmatrix(m, 0); /輸?入?矩?陣 int nummaxrc+1; int cpotmaxrc+1; / 構(gòu)11建輔助數(shù)yy組 int q,p,t; t.tu=m.tu; t.mu=m.nu; t.nu=m.mu; if(t.tu) for(int col=1;col=m.nu;col+) numcol=0; for(t=1;t=m.tu;t+) +numm.da

20、tat.j; cpot1=1; for(int i=2;i=m.nu;i+) cpoti=cpoti-1+numi-1; / 求出?每?一?列dd中dd非?零?元aa素?在三yy元aa組中dd出?現(xiàn)?的?位?置? for(p=1;p=m.tu;p+) int col=m.datap.j; q=cpotcol; t.dataq.i=col; t.dataq.j=m.datap.i; t.dataq.e=m.datap.e; +cpotcol; cout輸?入?矩?陣的?轉(zhuǎn)a置?矩?陣為aendl; outputsmatrix(t); return true; bool count(rlsmatr

21、ix &t) int nummaxrc+1; int col;for(int col=1;col=t.mu;col+) numcol=0; for(col=1;col=t.tu;col+) +numt.datacol.i; t.rpos1=1; for(int i=2;i=t.mu;i+) t.rposi=t.rposi-1+numi-1; return true; bool multsmatrix ( ) rlsmatrix m,n,q; inputtsmatrix(m,1); inputtsmatrix(n,1); count(m); count(n); if(m.nu!=n.mu) re

22、turn false; q.mu=m.mu; q.nu=n.nu; q.tu=0; / q初?始?化 int ctempmaxrc+1; int arow,tp,p,brow,t,q,ccol; if(m.tu*n.tu) for( arow=1;arow=m.mu;arow+) /memset(ctemp,0,n.nu); for(int x=1;x=n.nu;x+) ctempx=0; q.rposarow=q.tu+1; if(arowm.mu) tp=m.rposarow+1; else tp=m.tu+1; for(p=m.rposarow;ptp;p+) brow=m.datap.

23、j; if(brown.mu) t=n.rposbrow+1; else t=n.tu+1; for(q=n.rposbrow;qt;q+) ccol=n.dataq.j; ctempccol += m.datap.e*n.dataq.e; for(ccol=1;ccolmaxsize) return false; q.dataq.tu.e=ctempccol; q.dataq.tu.i=arow; q.dataq.tu.j=ccol; outputsmatrix(q); return true; bool addsmatrix() tsmatrix m,n,q;inputtsmatrix(m

24、, 2);inputtsmatrix(n, 2);if(m.mu=0)|(m.nu=0)|(m.tu=0)|(n.mu=0)|(n.nu=0)|(n.tu=0) return 0; if(m.mu!=n.mu|m.nu!=n.nu) return 0; q.mu=m.mu; q.nu=m.nu; q.tu=0; int x=0,y=0; for(int i=1;i=q.mu;i+) for(int j=1;j=q.nu;j+) for(int p=1;p=m.tu;p+) if(i=m.datap.i)&(j=m.datap.j) x=m.datap.e; break; else x=0; /

25、for p for(int q=1;q=n.tu;q+) if(i=n.dataq.i)&(j=n.dataq.j) y=n.dataq.e; break; else y=0; /for q if(x+y)!=0) q.dataq.tu+1.i=i; q.dataq.tu+1.j=j; q.dataq.tu+1.e=x+y; q.tu+; /if /for j /for i outputsmatrix(q); return 1;int main() cout請(qǐng)?選?擇?要a進(jìn)?行d的?操作endl; cout1:矩?陣的?轉(zhuǎn)a置?endl; cout2:矩?陣的?加法endl; cout3:矩

26、?陣的?乘?法endl; cout4:退?出?程序endl; char c=getchar(); if(c=1) transposesmatrix( ); else if(c=2) addsmatrix(); else if(c=3) multsmatrix (); else exit(0); /退?出? return 0;實(shí)驗(yàn)結(jié)果：總結(jié)和感想：蠻大難度的，代碼量比較長(zhǎng)，感覺(jué)還有許多都不怎么懂，照書上的碼下來(lái)的，還是要多練習(xí)才行。實(shí)驗(yàn)?zāi)康模簶?shù)是數(shù)據(jù)結(jié)構(gòu)中應(yīng)用極為廣泛的非線性結(jié)構(gòu)，本單元的實(shí)驗(yàn)達(dá)到熟悉二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)的特性，以及如何應(yīng)用樹(shù)結(jié)構(gòu)解決具體問(wèn)題。問(wèn)題描述：首先，掌握二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)

27、和熟悉對(duì)二叉樹(shù)的基本操作。其次，以二叉樹(shù)表示算術(shù)表達(dá)式的基礎(chǔ)上，設(shè)計(jì)一個(gè)十進(jìn)制的四則運(yùn)算的計(jì)算器。-+/a*b-efcd如算術(shù)表達(dá)式：a+b*(c-d)-e/f實(shí)驗(yàn)要求：1、 如果利用完全二叉樹(shù)的性質(zhì)和二叉鏈表結(jié)構(gòu)建立一棵二叉樹(shù)，分別計(jì)算a) 統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)。b) 求二叉樹(shù)的深度。2、 十進(jìn)制的四則運(yùn)算的計(jì)算器可以接收用戶來(lái)自鍵盤的輸入。3、 由輸入的表達(dá)式字符串動(dòng)態(tài)生成算術(shù)表達(dá)式所對(duì)應(yīng)的二叉樹(shù)。4、 自動(dòng)完成求值運(yùn)算和輸出結(jié)果。算法分析：#include#include#include#includeusing namespace std;#define stack_init_size

28、100#define stackincrease 10typedef char telemtype; /表示?處|理的?數(shù)y據(jù)y類型，?這a里?是?字?符?typedef struct bitnode /二t叉?樹(shù)中d節(jié)點(diǎn)?的?數(shù)y據(jù)y結(jié)構(gòu)1，?左右孩子用?指?針?表示?telemtype data;struct bitnode * lchild,* rchild;binode,* bitree;typedef bitree selemtype;typedef bitree qelemtype;typedef struct sqstack /棧?的?定義?，?是?一?個(gè)?二t叉?樹(shù)組成的?棧?

29、，?每?個(gè)?成員是?一?個(gè)?指?向二t叉?樹(shù)中d結(jié)點(diǎn)?的?指?針? selemtype *base;selemtype *top;int stacksize;sqstack;/*=棧?-adt棧?的?實(shí)現(xiàn)?，?包括初?始?化，?push，?pop其?實(shí)這a部?分?代碼?可以?不?需要a看，?無(wú)t非?是?實(shí)現(xiàn)?了?棧?的?基本?操作=*/void initstack(sqstack &s)s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype);s.top=s.base;s.stacksize=stack_init_size;/in

30、itstackvoid push(sqstack &s,selemtype e)if(s.top-s.base=s.stacksize)s.base=(selemtype *)realloc(s.base,(s.stacksize+stackincrease)*sizeof(selemtype);if(!s.base)exit(1);s.top=s.base+s.stacksize;/?貌2似?多余?s.stacksize+=stackincrease;*s.top+=e;int pop(sqstack &s,selemtype &e)if(s.base=s.top)return -1;e=*

31、-s.top;return 0;bitree precreatebitree()bitree p;char ch;ch=getchar();ch=getchar(); /此?處|讀兩?次?的?原-因是?，?每?隔?一?個(gè)?輸?入?符?號(hào)?之?間?，?有d一?個(gè)?空?格?，?需要a多讀一?次?把?空?格?跳?過(guò)y去if(ch=#) return null;p=(bitree)malloc(sizeof(binode);p-data=ch;p-lchild=precreatebitree();p-rchild=precreatebitree();return p;/precreatebitreev

32、oid visit(telemtype ch)printf(%c,ch);/visit/用?來(lái)打印?data。int preread(bitree bt)if(!bt)return 0;visit(bt-data);preread(bt-lchild);preread(bt-rchild);return 0;/preread/先序遍歷，?先將?data打印?，?再遞y歸調(diào)用?。int inread(bitree bt)if(!bt)return 0;inread(bt-lchild);visit(bt-data);inread(bt-rchild);return 0;/inread/中d序遍歷

33、，?先遞y歸調(diào)用?左孩子，?再打印?data，?再調(diào)用?右孩子。int postread(bitree bt)if(!bt)return 0;postread(bt-lchild);postread(bt-rchild);visit(bt-data);return 0;/postread/后序遍歷，?先將?左右孩子遞y歸調(diào)用?，?再打印?data。int number(bitree bt)int n1,n2;if(!bt) return 0;n1=number(bt-lchild);n2=number(bt-rchild);return 1+n1+n2;/number/求二t叉?樹(shù)結(jié)點(diǎn)?數(shù)y，

34、?遞y歸調(diào)用?，?當(dāng)頭指?針?為a空?時(shí)，?返回?0，?否?則返回?1+左孩子結(jié)點(diǎn)?數(shù)y+右孩子結(jié)點(diǎn)?數(shù)y。int leaf(bitree bt)int l1,l2;if(!bt) return 0;if(!bt-lchild&!bt-rchild) return 1;l1=leaf(bt-lchild);l2=leaf(bt-rchild);return l1+l2;/leaf/求二t叉?樹(shù)葉?子數(shù)y，?遞y歸調(diào)用?，?若?頭指?針?為a空?時(shí)，?返回?0，?若?頭指?針?左右孩子為a空?，?則返回?1，?否?則返回?左孩子葉?子數(shù)y+右孩子葉?子數(shù)y。int height(bitree b

35、t)int h1,h2;if(!bt) return 0;h1=height(bt-lchild);h2=height(bt-rchild);return 1+(h1h2?h1:h2);/height/求二t叉?樹(shù)的?高?度，?遞y歸調(diào)用?，?當(dāng)頭指?針?為a空?時(shí)，?返回?0，?否?則返回?1+（左右孩子中d高?度最?大的?）?。int wide(bitree bt,int *w,int x)if(!bt)return 0;if(bt)wx=wx+1;if(bt-lchild)wide(bt-lchild,w,x+1);if(bt-rchild)wide(bt-rchild,w,x+1);r

36、eturn 0;/wide/求二t叉?樹(shù)的?寬度，?遞y歸調(diào)用?，?先求得?其?高?度，?創(chuàng)建一?個(gè)?數(shù)y組輸?入?，?并輸?入?其?層?數(shù)y。若?雙?親非?空?wx+。調(diào)用?其?左右孩子。這a樣就可以?得?到?每?層?的?寬度，?找到?最?大值就是?二t叉?樹(shù)的?寬度。void copybitree(bitree &p,bitree q)bitree lp,rp;if(!q)p=null;elsecopybitree(lp,q-lchild);copybitree(rp,q-rchild);p=(bitree)malloc(sizeof(binode);p-data=q-data;p-lch

37、ild=lp;p-rchild=rp;/copybitree/復(fù)制?二t叉?樹(shù)，?仍?是?遞y歸調(diào)用?。從下?向上?、從左到?右創(chuàng)建，?當(dāng)頭指?針?為a空?時(shí)，?賦3值空?指?針?。int destroybitree(bitree &bt)if(!bt)return 0;if(bt-lchild)destroybitree(bt-lchild);if(bt-rchild)destroybitree(bt-rchild);if(!bt-lchild&!bt-rchild)free(bt);bt=null;return 0;return 0;/destroybitree/銷毀二t叉?樹(shù)，?遞y歸調(diào)

38、用?。如?果?頭指?針?為a空?，?返回?。調(diào)用?左右孩子，?如?果?左右孩子為a空?，?釋放?雙?親。開(kāi)a始?先判d斷?左右孩子是?否?非?空?，?程序很長(zhǎng)。經(jīng)-過(guò)y調(diào)整?，?最?后判d斷?，?使1函數(shù)y大大縮?減?了?。int calculate(bitree bt)int l,r;if(!bt-lchild&!bt-rchild)return bt-data-48;l=calculate(bt-lchild);r=calculate(bt-rchild);switch(bt-data)case +: return l+r;case -: return l-r;case *: return

39、 l*r;case /: return l/r;return 0;/calculate/計(jì)?算?二t叉?樹(shù)的?值，?遞y歸調(diào)用?。如?果?左右孩子為a空?，?返回?其?ascii碼?-48，?即其?實(shí)數(shù)y值int restore(bitree bt)if(!bt)return 0;if(bt-data=*|bt-data=/)&(bt-lchild-data=+|bt-lchild-data=-)printf();restore(bt-lchild);printf();elserestore(bt-lchild);visit(bt-data);if(bt-data=*|bt-data=/)&(bt-rchild-data=+|bt-rchild-data=-)printf();restore(bt-rchild);printf();elserestore(bt-rchild);return 0;/restoreint main()int i;bitree s10;for(i=0;ii;printf( (1)請(qǐng)?輸?入?擴(kuò)?展1先序序