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

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告全集實(shí)驗(yàn)一 線性表基本操作和簡(jiǎn)單程序1 實(shí)驗(yàn)?zāi)康模?） 掌握使用 visual c+ 6.0 上機(jī)調(diào)試程序的基本方法；（2） 掌握線性表的基本操作：初始化、插入、刪除、取數(shù)據(jù)元素等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和 鏈表存儲(chǔ)結(jié)構(gòu)上的程序設(shè)計(jì)方法。2 實(shí)驗(yàn)要求（1） 認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材容。（2） 認(rèn)真閱讀和掌握本章相關(guān)容的程序。（3） 上機(jī)運(yùn)行程序。（4） 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。（5） 按照你對(duì)線性表的操作需要，重新改寫主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果實(shí)驗(yàn)代碼：1）頭文件模塊#include iostream.h/頭文件#include/庫(kù)頭文件

2、-動(dòng)態(tài)分配存空間typedef int elemtype;/定義數(shù)據(jù)域的類型 typedef struct linknode/定義結(jié)點(diǎn)類型elemtype data;/定義數(shù)據(jù)域struct linknode *next;/定義結(jié)點(diǎn)指針 nodetype;2）創(chuàng)建單鏈表.nodetype *create()/建立單鏈表，由用戶輸入各結(jié)點(diǎn) data 域之值， /以 0 表示輸入結(jié)束elemtype d;/定義數(shù)據(jù)元素 dnodetype *h=null,*s,*t;/定義結(jié)點(diǎn)指針int i=1;cout建立一個(gè)單鏈表endl;while(1)cout 輸入第 i d;if(d=0) break;

3、/以 0 表示輸入結(jié)束if(i=1)/建立第一個(gè)結(jié)點(diǎn)h=(nodetype*)malloc(sizeof(nodetype);/ 表示指針 h h-data=d;h-next=null;t=h;/h 是頭指針else/建立其余結(jié)點(diǎn)s=(nodetype*) malloc(sizeof(nodetype); s -data=d;s-next=null;t-next=s;t =s;/t 始終指向生成的單鏈表的最后一個(gè)節(jié)點(diǎn).i+;return h;3）輸出單鏈表中的元素void disp(nodetype*h)/輸出由 h 指向的單鏈表的所有 data 域之值 nodetype *p=h;cout輸

4、出一個(gè)單鏈表:endl ;if(p=null)cout空表;while(p!=null)coutdatanext;coutnext;i+;return i;5）尋找第 i 個(gè)節(jié)點(diǎn)nodetype *find(nodetype *h,int i)/返回第 i 個(gè)節(jié)點(diǎn)的指針nodetype *p=h;int j=1;if(ilen(h)|i=0)return null;/i 上溢或下溢 celsewhile (p!=null&jnext;return p;.6）單鏈表的插入操作nodetype *ins(nodetype *h,int i,elemtype x)/在單鏈表 head 中第 i 個(gè)節(jié)

5、點(diǎn) /（i=0）之后插入一個(gè) data 域?yàn)?x 的節(jié)點(diǎn)nodetype *p,*s;s=(nodetype*)malloc(sizeof(nodetype);/ 創(chuàng)建節(jié)點(diǎn) s s-data=x;s-next=null;if(i=0)/i=0:s 作為該單鏈表的第一個(gè)節(jié)點(diǎn)s-next=h;h=s;elsep=find(h,i);/查找第 i 個(gè)節(jié)點(diǎn)，并由 p 指向該節(jié)點(diǎn)if(p!=null)s-next=p-next;p-next=s;return h;7）單鏈表的刪除操作.nodetype *del(nodetype *h,int i)/刪除第 i 個(gè)節(jié)點(diǎn)nodetype *p=h, *s;

6、int j=1;if(i=1)/刪除第 1 個(gè)節(jié)點(diǎn)h=h-next;free(p); elsep=find(h,i-1);/查找第 i-1 個(gè)節(jié)點(diǎn)，并由 p 指向該節(jié)點(diǎn) if(p!=null&p-next!=null)s=p-next;/s 指向要?jiǎng)h除的節(jié)點(diǎn) p-next=s-next;free(s);else cout輸入 i 的值不正確next;if(pb=null)/只有一個(gè)節(jié)點(diǎn)的情況free(pa);elsewhile (pb!=null)/有兩個(gè)及以上節(jié)點(diǎn)的情況free(pa);pa=pb;pb=pb-next;free(pa);9)主程序模塊:#includeslink.h/包含頭

7、文件 slinkvoid main().nodetype *head;/定義節(jié)點(diǎn)指針變量head=create();/創(chuàng)建一個(gè)單鏈表disp(head);/輸出單鏈表cout單鏈表長(zhǎng)度:len(head)endl;ins(head, 2,0);/在第二個(gè)節(jié)點(diǎn)之后插入以 0 為元素的節(jié)點(diǎn) disp(head);/輸出新鏈表del(head,2);/刪除第二個(gè)節(jié)點(diǎn)disp(head);/輸出新鏈表5實(shí)驗(yàn)結(jié)果建立一個(gè)單鏈表：輸入第 1 結(jié)點(diǎn) data 域值：1輸入第 2 結(jié)點(diǎn) data 域值：2輸入第 3 結(jié)點(diǎn) data 域值：3輸入第 4 結(jié)點(diǎn) data 域值：4輸入第 5 結(jié)點(diǎn) data 域值：

8、5輸入第 6 結(jié)點(diǎn) data 域值：6輸入第 7 結(jié)點(diǎn) data 域值：7輸入第 8 結(jié)點(diǎn) data 域值：8輸入第 9 結(jié)點(diǎn) data 域值：9輸入第 10 結(jié)點(diǎn) data 域值 0：輸出一個(gè)單鏈表：.1 2 3 4 5 6 7 8 9單鏈表長(zhǎng)度：9輸出一個(gè)單鏈表：1 0 2 3 4 5 6 7 8 9輸出一個(gè)單鏈表： 1 2 3 4 5 6 7 8實(shí)驗(yàn)二順序棧的實(shí)現(xiàn)1.實(shí)驗(yàn)?zāi)康恼莆枕樞驐５幕静僮鳎撼跏蓟瘲?、判棧空否、入棧、出棧、取棧頂?shù)據(jù)元素等運(yùn)算以及程 序?qū)崿F(xiàn)方法。2.實(shí)驗(yàn)要求（1） 認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材容。（2） 分析問題的要求，編寫和調(diào)試完成程序。（3） 保存和打印出程

9、序的運(yùn)行結(jié)果，并分析程序的運(yùn)行結(jié)果。3.實(shí)驗(yàn)容利用棧的基本操作實(shí)現(xiàn)一個(gè)判斷算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)是否正確配對(duì)的程 序。具體完成如下：（1） 定義棧的順序存取結(jié)構(gòu)。（2） 分別定義順序棧的基本操作（初始化棧、判?？辗瘛⑷霔?、出棧等）。（3） 定義一個(gè)函數(shù)用來(lái)判斷算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)是否正確配對(duì)。其中，括號(hào)配對(duì)共有四種情況：左右括號(hào)配對(duì)次序不正確；右括號(hào)多于左括號(hào)；左括號(hào)多于右括號(hào)；左 右括號(hào)匹配正確。（4） 設(shè)計(jì)一個(gè)測(cè)試主函數(shù)進(jìn)行測(cè)試。（5） 對(duì)程序的運(yùn)行結(jié)果進(jìn)行分析。實(shí)驗(yàn)代碼：.#include #define maxsize 100typedef structint dat

10、amaxsize;int top;sqstack;void initstack(sqstack *st) /初始化棧 st-top=-1;int stackempty(sqstack *st) /判斷棧為空 return (st-top=-1);void push(sqstack *st,int x) /元素進(jìn)棧 if(st-top=maxsize-1)printf(棧上溢出!n);else.st-top+;st-datast-top=x;void pop(sqstack *st) /退棧if(st-top=-1)printf(棧下溢出n);elsest-top-;int gettop(sqs

11、tack *st) /獲得棧頂元素 if(st-top=-1)printf(?？課);return 0;elsereturn st-datast-top;void display(sqstack *st) /打印棧里元素.int i;printf(棧中元素：);for(i=st-top;i=0;-i)printf(%d ,st-datai);printf(n);int main() /測(cè)試sqstack l;sqstack *st=&l;initstack(st);printf(?？眨?dn,stackempty(st); for(int i=1;i10;+i)push(st,i);displ

12、ay(st);printf(退一次棧n);pop(st);printf(棧頂元素:%dn,gettop(st); pop(st);display(st);.return 0;實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)三串的基本操作和簡(jiǎn)程序1 實(shí)驗(yàn)?zāi)康恼莆沾静僮鳎撼跏蓟?、?lián)接、替換、子串等運(yùn)算在堆分配存儲(chǔ)儲(chǔ)結(jié)構(gòu)上的程序設(shè)計(jì)方法。 2 實(shí)驗(yàn)要求（1） 認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材容。（2） 認(rèn)真閱讀和掌握本章相關(guān)容的算法并設(shè)計(jì)程序序。（3） 上機(jī)運(yùn)行程序。（4） 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。實(shí)驗(yàn)代碼：#include#define maxsize 50typedef struct.char dat

13、amaxsize; /存放字符串int length; /字符串長(zhǎng)度sqstring;/將一個(gè)字符串常量賦給串 svoid strassign(sqstring &s,char cstr)int i;for(i=0;cstri!=0;i+) /這個(gè) 0 代表字符串結(jié) 束標(biāo)志,編譯系統(tǒng)自動(dòng)加上的s.datai=cstri;s.length=i;/字符串的復(fù)制void strcopy(sqstring &s,sqstring t)int i;for(i=0;it.length;i+)s.datai=t.datai;s.length=t.length;printf(字符串復(fù)制成功了n);/判斷字符串

14、是否相等.void strequal(sqstring s,sqstring t)int i,same=1;if(s.length!=t.length)same=0;elsefor(i=0;is.length;i+)if(s.datai!=t.datai)same=0;break;if(same=0)printf(這兩個(gè)字符串不相等 n); elseprintf(這兩個(gè)字符串相等 n); /字符串的長(zhǎng)度void strlength(sqstring s).printf(此字符串長(zhǎng)度為：%dn,s.length); /合并字符串sqstring concat(sqstring s,sqstrin

15、g t)sqstring str;int i;str.length=s.length+t.length;for(i=0;is.length;i+)str.datai=s.datai;for(i=0;it.length;i+)str.datas.length+i=t.datai;return str;/求子字符串void substr(sqstring s,int i,int j)sqstring str;int k;str.length=0;if(is.length|js.length).printf(子字符串復(fù)制失敗 n); for(k=i-1;ki+j-1;k+)str.datak-i+1

16、=s.datak;str.length=j;printf(子字符串復(fù)制成功 長(zhǎng)度為：%dn,j); printf(下面輸出此子字符串： n); for(i=0;ij;i+)printf(%c,str.datai);printf(n);/插入字符串sqstring inserstr(sqstring s1,int i,sqstring s2) int j;sqstring str;str.length=0;if(is1.length+1)printf(字符串插入失敗n);return str;for(j=0;ji-1;j+).str.dataj=s1.dataj;for(j=0;js2.leng

17、th;j+)str.datai-1+j=s2.dataj;for(j=i-1;js1.length;j+)str.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;printf(插入字符串成功 長(zhǎng)度為：%dn,str.length); return str;/刪除字符串sqstring delestr(sqstring s,int i,int j)int k;sqstring str;str.length=0;if(is.length|i+js.length+1)printf(字符串刪除失敗n); return str;for(k=

18、0;ki-1;k+)str.datak=s.datak;for(k=i+j-1;ks.length;k+).str.datak-j=s.datak;str.length=s.length-j;printf( 刪 除 子 字 符 串 成 功 為：%dn,str.length);return str;剩 余 長(zhǎng) 度/替換字符串void repstr(sqstring s,int i,int j,sqstring t) int k;sqstring str;str.length=0;if(is.length|i+j-1s.length) printf(字符串替換失敗了 n);for(k=0;ki-1

19、;k+)str.datak=s.datak;for(k=0;kt.length;k+)str.datai+k-1=t.datak;for(k=i+j-1;k0)printf( 下面輸出這個(gè)字符串n); for(i=0;is.length;i+)printf(%c,s.datai);printf(n);elseprintf(目前空字符串 無(wú)法輸出n);void main()sqstring s;char a=wen xian liang; /字符串常量 a strassign(s,a);dispstr(s);.strlength(s);sqstring s1,s2,t; /s1 是待復(fù)制的字符串

20、變量 printf(請(qǐng)輸入一個(gè)字符串 t:n); scanf(%s,t.data);strassign(t,t.data);strcopy(s1,t); /復(fù)制字符串strlength(s1);dispstr(s1);printf(下面判斷字符串 s1 和字符串 s 是否相等n); strequal(s,s1);printf(下面將字符串 s1 和字符串 s 合并一起n); sqstring str;str=concat(s,s1); /合并字符串dispstr(str);strlength(str);substr(str,22,7); /求子字符串 str=delestr(str,15,4)

21、; /刪除字符串 dispstr(str);strlength(str);printf( 請(qǐng)插入一個(gè)字符串 s2n); scanf(%s,s2.data);strassign(s2,s2.data);.str=inserstr(str,15,s2); /插入字符串 dispstr(str);strlength(str);printf(順序字符串的基本運(yùn)算到此結(jié)束了n); 實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)四編程建立二叉樹，對(duì)樹進(jìn)行插入刪除及遍歷的程序.1.實(shí)驗(yàn)?zāi)康模?） 進(jìn)一步掌握指針變量的用途和程序設(shè)計(jì)方法。（2） 掌握二叉樹的結(jié)構(gòu)特征，以及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)及程序設(shè)計(jì)方法。（3） 掌握構(gòu)造二叉樹的基本方法。（

22、4） 掌握二叉樹遍歷算法的設(shè)計(jì)方法。3 實(shí)驗(yàn)要求（1） 認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材容。（2） 掌握一個(gè)實(shí)際二叉樹的創(chuàng)建方法。（3） 掌握二叉鏈存儲(chǔ)結(jié)構(gòu)下二叉樹操作的設(shè)計(jì)方法和遍歷操作設(shè)計(jì)方法。4 實(shí)驗(yàn)容（1） 定義二叉鏈存儲(chǔ)結(jié)構(gòu)。（2） 設(shè)計(jì)二叉樹的基本操作（初始化一棵帶頭結(jié)點(diǎn)的二叉樹、左結(jié)點(diǎn)插入、右結(jié)點(diǎn)插入、 中序遍歷二叉樹等）。（3） 按照建立一棵實(shí)際二叉樹的操作需要，編寫建立二叉樹、遍歷二叉樹的函數(shù)。（4） 編寫測(cè)試主函數(shù)并上機(jī)運(yùn)行。打印出運(yùn)行結(jié)果，并結(jié)合程序運(yùn)行結(jié)果進(jìn)行分析。 實(shí)驗(yàn)代碼：#includetypedef struct bitnodechar data;struct

23、bitnode *lchild,*rchild;binode,*bitree;void createbitree(bitree *t)char ch;cinch;.if(ch=0)(*t)=null;else(*t)=new bitnode;(*t)-data=ch;createbitree(&(*t)-lchild);createbitree(&(*t)-rchild);void inorderout(bitree t)if(t)inorderout(t-lchild);coutdatarchild);void postorder(bitree t)if(t)postorder(t-lchi

24、ld);postorder(t-rchild);coutdatalchild=null&bt-rchild=null)return 1;return(countleaf(bt-lchild)+countleaf(bt-rchild);void main()bitree bt;createbitree(&bt);inorderout(bt);cout endl;postorder(bt);countleaf(bt);.實(shí)驗(yàn)五 建立有序表并進(jìn)行折半查找1. 實(shí)驗(yàn)?zāi)康恼莆者f歸算法求解問題的基本思想和程序?qū)崿F(xiàn)方法。2實(shí)驗(yàn)要求（1） 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法思想。（2） 編寫和調(diào)試完成程序。（3） 保

25、存和打印程序的運(yùn)行結(jié)果，并對(duì)運(yùn)行結(jié)果進(jìn)行分析。3.實(shí)驗(yàn)容（1） 分析掌握折半查找算法思想，在此基礎(chǔ)上，設(shè)計(jì)出遞歸算法和循環(huán)結(jié)構(gòu)兩種實(shí)現(xiàn)方法 的折半查找函數(shù)。（2） 編寫程序?qū)崿F(xiàn)：在保存于數(shù)組的 1000 個(gè)有序數(shù)據(jù)元素中查找數(shù)據(jù)元素 x 是否存在。數(shù)據(jù)元素 x 要包含兩種情況：一種是數(shù)據(jù)元素 x 包含在數(shù)組中；另一種是數(shù)據(jù)元素 x 不包含 在數(shù)組中（3） 數(shù)組中數(shù)據(jù)元素的有序化既可以初始賦值時(shí)實(shí)現(xiàn)，也可以設(shè)計(jì)一個(gè)排序函數(shù)實(shí)現(xiàn)。 （4） 根據(jù)兩種方法的實(shí)際運(yùn)行時(shí)間，進(jìn)行兩種方法時(shí)間效率的分析對(duì)比。實(shí)驗(yàn)代碼：#include#include.#define max_length 100typede

26、f int keytype;typedef structint key;elemtype;typedef structelemtype elemmax_length; / 0 號(hào)單元空出 int length;sstable;int search_bin(sstable st,keytype key)int low,high,mid;low = 1;high = st.length;while(low =high)mid = (low+high)/2;if(key =st.elemmid.key)return mid;elseif(keyst.elemmid.key)high = mid-1;

27、elselow=mid+1;return 0;void main()int i,result;sstable st;keytype key;printf(please input length:);scanf(%d,&st.length);for(i=1;i=st.length;i+)printf(please input st.elem:);.scanf(%d,&st.elemi);printf(please input keyword:);scanf(%d,&key);result=search_bin(st,key);if(result=0)printf(dont findn);else

28、printf(find the key,the position is %dn,result); 實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)六建立一組記錄并進(jìn)行插入排序1. 實(shí)驗(yàn)?zāi)康模?） 掌握插入排序算法的思想。（2） 掌握順序隊(duì)列下插入排序算法的程序設(shè)計(jì)方法。2. 實(shí)驗(yàn)要求（1） 認(rèn)真閱讀和掌握教材中插入排序算法的思想。（3） 編寫基于順序隊(duì)列的插入排序排序算法并上機(jī)實(shí)現(xiàn)。3. 實(shí)驗(yàn)容（1） 編寫基于順序隊(duì)列的插入排序函數(shù)。.（2） 設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，實(shí)現(xiàn)對(duì)基于順序隊(duì)列結(jié)構(gòu)的插入排序算法的測(cè)試。 （3） 分析程序的運(yùn)行結(jié)果。實(shí)驗(yàn)代碼：#include#include#define maxsize 100typede

29、f structint key;sortkey;typedef structsortkey elemmaxsize;int length;sortelem;void insertsort(sortelem *p)int i,j;for(i=2;ilength;i+)if(p-elemi.keyelemi-1.key)/*小于時(shí)，需將 elemi插入有序表*/ p-elem0.key=p-elemi.key; /*為統(tǒng)一算法設(shè)置監(jiān)測(cè)*/for(j=i-1;p-elem0.keyelemj.key;j-)p-elemj+1.key=p-elemj.key;/*記錄后移*/.p-elemj+1.key=p-elem