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

1、.wd.wd.wd.數(shù)據(jù)構(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ǔ)構(gòu)造和鏈表存儲(chǔ)構(gòu)造上的程序設(shè)計(jì)方法。2 實(shí)驗(yàn)要求1 認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。2 認(rèn)真閱讀和掌握本章相關(guān)內(nèi)容的程序。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ù)頭文件-動(dòng)態(tài)分配內(nèi)

2、存空間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()/建設(shè)單鏈表，由用戶輸入各結(jié)點(diǎn)data域之值，/以0表示輸入完畢 elemtype d;/定義數(shù)據(jù)元素d nodetype *h=NULL,*s,*t;/定義結(jié)點(diǎn)指針 int i=1; cout建設(shè)一個(gè)單鏈表endl; while(1) cout 輸入第 i d; if(d=0) break;/以0表示輸

3、入完畢 if(i=1)/建設(shè)第一個(gè)結(jié)點(diǎn) h=(nodetype*)malloc(sizeof(nodetype);/表示指針h h-data=d;h-next=NULL;t=h;/h是頭指針 else/建設(shè)其余結(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輸出一個(gè)單鏈表:endl

4、 ; 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上溢或下溢c else while (p!=NULL&jnext; return p; 6單鏈表的插入操作nodetype *ins(nodetype *h,int i,elemtype x)/在單鏈表head中第i個(gè)節(jié)點(diǎn)/i=0之后插入一個(gè)

5、data域?yàn)閤的節(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; else p=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; int j=1; if(i=1)

6、/刪除第1個(gè)節(jié)點(diǎn) h=h-next;free(p); else p=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); else while (pb!=NULL)/有兩個(gè)及以上節(jié)點(diǎn)的情況 free(pa);pa=pb;pb=pb-next; free(pa); 9)主程序模塊:#includeslink.h/包含頭文件slinkvoid

7、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é)果建設(shè)一個(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域值：5輸入第6結(jié)點(diǎn)data域值：6輸入第7結(jié)點(diǎn)data域值：7

8、輸入第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)的教材內(nèi)容。2 分析問題的要求，編寫和調(diào)試完成程序。3 保存和打印出程序的運(yùn)行結(jié)果，并分析程序的運(yùn)行結(jié)果。3.實(shí)驗(yàn)內(nèi)容利用棧的 基本操作實(shí)現(xiàn)一個(gè)判斷算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)是否

9、正確配對(duì)的程序。具體完成如下：1 定義棧的順序存取構(gòu)造。2 分別定義順序棧的 基本操作初始化棧、判?？辗瘛⑷霔?、出棧等。3 定義一個(gè)函數(shù)用來判斷算術(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 struct int dataMaxSize; int top;SqStack;void InitStack(SqStack *st) /初始化棧 st-top=

10、-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); else st-top-;int Gettop(SqStack *st) /獲得棧頂元素 if(st-top=-1) printf(?？課); return 0; els

11、e return 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); Display(st); printf(退一次棧n); Pop(st); printf(棧頂元素:

12、%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ǔ)構(gòu)造上的程序設(shè)計(jì)方法。2 實(shí)驗(yàn)要求1 認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。2 認(rèn)真閱讀和掌握本章相關(guān)內(nèi)容的算法并設(shè)計(jì)程序序。3 上機(jī)運(yùn)行程序。4 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)展分析。實(shí)驗(yàn)代碼：#include#define MaxSize 50typedef struct char dataMaxSize; /存放字符串 int length; /字符串長(zhǎng)度SqString;

13、/將一個(gè)字符串常量賦給串svoid StrAssign(SqString &s,char cstr) int i; for(i=0;cstri!=0;i+) /這個(gè)0代表字符串完畢標(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);/判斷字符串是否相等void StrEqual(SqString s,SqString

14、t) int i,same=1; if(s.length!=t.length) same=0; else for(i=0;is.length;i+) if(s.datai!=t.datai) same=0; break; if(same=0) printf(這兩個(gè)字符串不相等n); else printf(這兩個(gè)字符串相等n);/字符串的長(zhǎng)度void StrLength(SqString s) printf(此字符串長(zhǎng)度為：%dn,s.length); /合并字符串SqString Concat(SqString s,SqString t) SqString str; int i; str.l

15、ength=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=s.datak; str.lengt

16、h=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.length;j+) st

17、r.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(

18、k=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(刪除子字符串成功 剩余長(zhǎng)度為：%dn,str.length); return str;/替換字符串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); else printf(目前空字符串 無法輸出n);void main() SqString s; char a=wen xian liang; /字符串常量a StrAssign(s,a); DispStr(s); StrLength(s); SqString s1,s2,t; /s

20、1是待復(fù)制的字符串變量 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

21、(str,15,4); /刪除字符串 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)算到此完畢了n);實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)四 編程建設(shè)二叉樹，對(duì)樹進(jìn)展插入刪除及遍歷的程序1.實(shí)驗(yàn)?zāi)康? 進(jìn)一步掌握指針變量的用途和程序設(shè)計(jì)方法。2 掌握二叉樹的構(gòu)造特征，以及鏈?zhǔn)酱鎯?chǔ)構(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)的教材內(nèi)容。2掌握一個(gè)實(shí)際二叉樹的創(chuàng)立方法。3掌握二叉鏈存儲(chǔ)構(gòu)造下二叉樹操作的設(shè)計(jì)方法和遍歷操作設(shè)計(jì)方法。4 實(shí)驗(yàn)內(nèi)容1定義二叉鏈存儲(chǔ)構(gòu)造。2設(shè)計(jì)二叉樹的 基本操作初始化一棵帶頭結(jié)點(diǎn)的二叉樹、左結(jié)點(diǎn)插入、右結(jié)點(diǎn)插入、中序遍歷二叉樹等。3按照建設(shè)一棵實(shí)際二叉樹的操作需要，編寫建設(shè)二叉樹、遍歷二叉樹的函數(shù)。4編寫測(cè)試主函數(shù)并上機(jī)運(yùn)行。打印出運(yùn)行結(jié)果，并結(jié)合程序運(yùn)行結(jié)果進(jìn)展分析。實(shí)驗(yàn)代碼：#includetypedef struct bitnode char data; struct bitnode *lchil

23、d,*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-lchild);posto

24、rder(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)五 建設(shè)有序表并進(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保存和打印程序的運(yùn)行結(jié)

25、果，并對(duì)運(yùn)行結(jié)果進(jìn)展分析。3.實(shí)驗(yàn)內(nèi)容1 分析掌握折半查找算法思想，在此根基上，設(shè)計(jì)出遞歸算法和循環(huán)構(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í)間效率的分析比照。實(shí)驗(yàn)代碼：#include#include#define MAX_LENGTH 100typedef int KeyType; typedef structin

26、t 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; else if(keyST.elemmid.key) high = mid-1; else low=mid+1; return

27、 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);elseprintf(Find the key,t

28、he position is %dn,result);實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)六建設(shè)一組記錄并進(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)內(nèi)容1 編寫基于順序隊(duì)列的插入排序函數(shù)。2 設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，實(shí)現(xiàn)對(duì)基于順序隊(duì)列構(gòu)造的插入排序算法的測(cè)試。3 分析程序的運(yùn)行結(jié)果。實(shí)驗(yàn)代碼：#include#include#define MAXSIZE 100typedef struct int key;sortkey;typedef struct sortkey 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-elem0.key; /*插入