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

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

2、alloc.h>/庫頭文件-動態(tài)分配內(nèi)存空間typedef int elemtype;/定義數(shù)據(jù)域的類型typedef struct linknode/定義結(jié)點類型 elemtype data;/定義數(shù)據(jù)域 struct linknode *next;/定義結(jié)點指針nodetype;2）創(chuàng)建單鏈表nodetype *create()/建立單鏈表，由用戶輸入各結(jié)點data域之值，/以0表示輸入結(jié)束 elemtype d;/定義數(shù)據(jù)元素d nodetype *h=NULL,*s,*t;/定義結(jié)點指針 int i=1; cout<<"建立一個單鏈表"<&l

3、t;endl; while(1) cout <<" 輸入第"<< i <<"結(jié)點data域值：" cin >> d; if(d=0) break;/以0表示輸入結(jié)束 if(i=1)/建立第一個結(jié)點 h=(nodetype*)malloc(sizeof(nodetype);/表示指針h h->data=d;h->next=NULL;t=h;/h是頭指針 else/建立其余結(jié)點 s=(nodetype*) malloc(sizeof(nodetype); s->data=d;s->nex

4、t=NULL;t->next=s; t=s;/t始終指向生成的單鏈表的最后一個節(jié)點 i+; return h; 3）輸出單鏈表中的元素void disp(nodetype*h)/輸出由h指向的單鏈表的所有data域之值 nodetype *p=h; cout<<"輸出一個單鏈表:"<<endl<<" " if(p=NULL)cout<<"空表" while(p!=NULL) cout<<p->data<<" "p=p->nex

5、t; cout<<endl;4）計算單鏈表的長度int len(nodetype *h)/返回單鏈表的長度 int i=0; nodetype *p=h; while(p!=NULL) p=p->next;i+; return i;5）尋找第i個節(jié)點nodetype *find(nodetype *h,int i)/返回第i個節(jié)點的指針 nodetype *p=h; int j=1; if(i>len(h)|i<=0) return NULL;/i上溢或下溢c else while (p!=NULL&&j<1)/查找第i個節(jié)點，并由p指向該節(jié)

6、點 j+;p=p->next; return p; 6）單鏈表的插入操作nodetype *ins(nodetype *h,int i,elemtype x)/在單鏈表head中第i個節(jié)點/（i>=0）之后插入一個data域為x的節(jié)點 nodetype *p,*s; s=(nodetype*)malloc(sizeof(nodetype);/創(chuàng)建節(jié)點s s->data=x;s->next=NULL; if(i=0)/i=0:s作為該單鏈表的第一個節(jié)點 s->next=h;h=s; else p=find(h,i);/查找第i個節(jié)點，并由p指向該節(jié)點 if(p!=N

7、ULL) s->next=p->next; p->next=s; return h; 7）單鏈表的刪除操作nodetype *del(nodetype *h,int i)/刪除第i個節(jié)點 nodetype *p=h, *s; int j=1; if(i=1)/刪除第1個節(jié)點 h=h->next;free(p); else p=find(h,i-1);/查找第i-1個節(jié)點，并由p指向該節(jié)點 if(p!=NULL&&p->next!=NULL) s=p->next;/s指向要刪除的節(jié)點 p->next=s->next; free(s)

8、; else cout<<"輸入i的值不正確"<<endl; return h;8）釋放節(jié)點空間void dispose(nodetype *h)/釋放單鏈表的所有節(jié)點占用的空間 nodetype *pa=h,*pb; if(pa!=NULL) pb=pa->next; if(pb=NULL)/只有一個節(jié)點的情況 free(pa); else while (pb!=NULL)/有兩個及以上節(jié)點的情況 free(pa);pa=pb;pb=pb->next; free(pa); 9)主程序模塊:#include"slink.h&qu

9、ot;/包含頭文件slinkvoid main() nodetype *head;/定義節(jié)點指針變量 head=create();/創(chuàng)建一個單鏈表 disp(head);/輸出單鏈表 cout<<"單鏈表長度:"<<len(head)<<endl; ins(head, 2,0);/在第二個節(jié)點之后插入以0為元素的節(jié)點 disp(head);/輸出新鏈表 del(head,2);/刪除第二個節(jié)點 disp(head);/輸出新鏈表5實驗結(jié)果建立一個單鏈表：輸入第1結(jié)點data域值：1輸入第2結(jié)點data域值：2輸入第3結(jié)點data域值：3輸

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

11、打印出程序的運行結(jié)果，并分析程序的運行結(jié)果。3.實驗內(nèi)容利用棧的基本操作實現(xiàn)一個判斷算術(shù)表達式中包含圓括號、方括號是否正確配對的程序。具體完成如下：（1） 定義棧的順序存取結(jié)構(gòu)。（2） 分別定義順序棧的基本操作（初始化棧、判棧空否、入棧、出棧等）。（3） 定義一個函數(shù)用來判斷算術(shù)表達式中包含圓括號、方括號是否正確配對。其中，括號配對共有四種情況：左右括號配對次序不正確；右括號多于左括號；左括號多于右括號；左右括號匹配正確。（4） 設(shè)計一個測試主函數(shù)進行測試。（5） 對程序的運行結(jié)果進行分析。實驗代碼：#include <stdio.h >#define MaxSize 100typ

12、edef struct    int dataMaxSize;    int top;SqStack;void InitStack(SqStack *st) /初始化棧    st->top=-1;int StackEmpty(SqStack *st) /判斷棧為空    return (st->top=-1);void Push(SqStack *st,int x) /元素進棧    if(st->top=MaxSize-1)

13、        printf("棧上溢出!n");    else            st->top+;        st->datast->top=x;    void Pop(SqStack *st) /退棧    if(

14、st->top=-1)        printf("棧下溢出n");    else    st->top-;int Gettop(SqStack *st) /獲得棧頂元素    if(st->top=-1)            printf("?？課"); 

15、0;      return 0;        else        return st->datast->top;void Display(SqStack *st) /打印棧里元素    int i;    printf("棧中元素：");    for(i=st->top;i>

16、=0;-i)        printf("%d ",st->datai);    printf("n");int main() /測試    SqStack L;    SqStack *st=&L;    InitStack(st);    printf("棧空：%dn",StackEmpty(st)

17、;    for(int i=1;i<10;+i)        Push(st,i);    Display(st);    printf("退一次棧n");    Pop(st);    printf("棧頂元素:%dn",Gettop(st);    Pop(st);  

18、60; Display(st);    return 0;實驗結(jié)果：實驗三 串的基本操作和簡程序1 實驗?zāi)康恼莆沾静僮鳎撼跏蓟?、?lián)接、替換、子串等運算在堆分配存儲儲結(jié)構(gòu)上的程序設(shè)計方法。2 實驗要求（1） 認真閱讀和掌握和本實驗相關(guān)的教材內(nèi)容。（2） 認真閱讀和掌握本章相關(guān)內(nèi)容的算法并設(shè)計程序序。（3） 上機運行程序。（4） 保存和打印出程序的運行結(jié)果，并結(jié)合程序進行分析。實驗代碼：#include<stdio.h>#define MaxSize 50typedef struct char dataMaxSize; /存放字符串 int lengt

19、h; /字符串長度SqString;/將一個字符串常量賦給串svoid StrAssign(SqString &s,char cstr) int i; for(i=0;cstri!='0'i+) /這個'0'代表字符串結(jié)束標志,編譯系統(tǒng)自動加上的 s.datai=cstri; s.length=i;/字符串的復制void StrCopy(SqString &s,SqString t) int i; for(i=0;i<t.length;i+) s.datai=t.datai; s.length=t.length; printf("

20、字符串復制成功了n");/判斷字符串是否相等void StrEqual(SqString s,SqString t) int i,same=1; if(s.length!=t.length) same=0; else for(i=0;i<s.length;i+) if(s.datai!=t.datai) same=0; break; if(same=0) printf("這兩個字符串不相等n"); else printf("這兩個字符串相等n");/字符串的長度void StrLength(SqString s) printf("

21、;此字符串長度為：%dn",s.length); /合并字符串SqString Concat(SqString s,SqString t) SqString str; int i; str.length=s.length+t.length; for(i=0;i<s.length;i+) str.datai=s.datai; for(i=0;i<t.length;i+) str.datas.length+i=t.datai; return str;/求子字符串void SubStr(SqString s,int i,int j) SqString str; int k; s

22、tr.length=0; if(i<=0|i>s.length|j<0|i+j-1>s.length) printf("子字符串復制失敗n"); for(k=i-1;k<i+j-1;k+) str.datak-i+1=s.datak; str.length=j; printf("子字符串復制成功 長度為：%dn",j); printf("下面輸出此子字符串：n"); for(i=0;i<j;i+) printf("%c",str.datai); printf("n&qu

23、ot;);/插入字符串SqString InserStr(SqString s1,int i,SqString s2) int j; SqString str; str.length=0; if(i<=0|i>s1.length+1) printf("字符串插入失敗n"); return str; for(j=0;j<i-1;j+) str.dataj=s1.dataj; for(j=0;j<s2.length;j+) str.datai-1+j=s2.dataj; for(j=i-1;j<s1.length;j+) str.datas2.le

24、ngth+j=s1.dataj; str.length=s1.length+s2.length; printf("插入字符串成功 長度為：%dn",str.length); return str;/刪除字符串SqString DeleStr(SqString s,int i,int j) int k; SqString str; str.length=0; if(i<=0|i>s.length|i+j>s.length+1) printf("字符串刪除失敗n"); return str; for(k=0;k<i-1;k+) str

25、.datak=s.datak; for(k=i+j-1;k<s.length;k+) str.datak-j=s.datak; str.length=s.length-j; printf("刪除子字符串成功 剩余長度為：%dn",str.length); return str;/替換字符串void RepStr(SqString s,int i,int j,SqString t) int k; SqString str; str.length=0; if(i<=0|i>s.length|i+j-1>s.length) printf("字符串

26、替換失敗了n"); for(k=0;k<i-1;k+) str.datak=s.datak; for(k=0;k<t.length;k+) str.datai+k-1=t.datak; for(k=i+j-1;k<s.length;k+) str.datat.length+k-j=s.datak; str.length=s.length-j+t.length; printf("替換字符串成功 新字符串長度為：%dn",str.length);/字符串的輸出void DispStr(SqString s) int i; if(s.length>

27、;0) printf("下面輸出這個字符串n"); for(i=0;i<s.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; /s1是待復制的字符串變量 print

28、f("請輸入一個字符串t:n"); scanf("%s",t.data); StrAssign(t,t.data); StrCopy(s1,t); /復制字符串 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); SubSt

29、r(str,22,7); /求子字符串 str=DeleStr(str,15,4); /刪除字符串 DispStr(str); StrLength(str); printf("請插入一個字符串s2n"); scanf("%s",s2.data); StrAssign(s2,s2.data); str=InserStr(str,15,s2); /插入字符串 DispStr(str); StrLength(str); printf("順序字符串的基本運算到此結(jié)束了n");實驗結(jié)果：實驗四  編程建立二叉樹，對樹進行插入刪除及遍歷

30、的程序1.實驗?zāi)康模?） 進一步掌握指針變量的用途和程序設(shè)計方法。（2） 掌握二叉樹的結(jié)構(gòu)特征，以及鏈式存儲結(jié)構(gòu)的特點及程序設(shè)計方法。（3） 掌握構(gòu)造二叉樹的基本方法。（4） 掌握二叉樹遍歷算法的設(shè)計方法。3 實驗要求（1）認真閱讀和掌握和本實驗相關(guān)的教材內(nèi)容。（2）掌握一個實際二叉樹的創(chuàng)建方法。（3）掌握二叉鏈存儲結(jié)構(gòu)下二叉樹操作的設(shè)計方法和遍歷操作設(shè)計方法。4 實驗內(nèi)容（1）定義二叉鏈存儲結(jié)構(gòu)。（2）設(shè)計二叉樹的基本操作（初始化一棵帶頭結(jié)點的二叉樹、左結(jié)點插入、右結(jié)點插入、中序遍歷二叉樹等）。（3）按照建立一棵實際二叉樹的操作需要，編寫建立二叉樹、遍歷二叉樹的函數(shù)。（4）編寫測試主函數(shù)并上

31、機運行。打印出運行結(jié)果，并結(jié)合程序運行結(jié)果進行分析。實驗代碼：#include<iostream.h>typedef struct bitnode char data; struct bitnode *lchild,*rchild;binode,*bitree;void createbitree(bitree *T) char ch; cin>>ch; if(ch='0')(*T)=NULL; else(*T)=new bitnode;(*T)->data=ch;createbitree(&(*T)->lchild);createbi

32、tree(&(*T)->rchild);void inorderout(bitree T) if(T)inorderout(T->lchild);cout<<T->data<<endl;inorderout(T->rchild);void postorder(bitree T) if(T)postorder(T->lchild);postorder(T->rchild);cout<<T->data<<endl;int countleaf(bitree bt) if(!bt)return 0; if

33、(bt->lchild=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);實驗五 建立有序表并進行折半查找1. 實驗?zāi)康恼莆者f歸算法求解問題的基本思想和程序?qū)崿F(xiàn)方法。2實驗要求（1）

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

35、include<stdlib.h>#define MAX_LENGTH 100typedef int KeyType; typedef structint key;ElemType; typedef structElemType elemMAX_LENGTH; / 0號單元空出 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.e

36、lemmid.key) return mid; else if(key<ST.elemmid.key) high = mid-1; else low=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("

37、%d",&ST.elemi);printf("please input keyword:");scanf("%d",&key);result=Search_Bin(ST,key);if(result=0)printf("Don't findn");elseprintf("Find the key,the position is %dn",result);實驗結(jié)果：實驗六建立一組記錄并進行插入排序1. 實驗?zāi)康模?） 掌握插入排序算法的思想。（2） 掌握順序隊列下插入排序算法的程序設(shè)

38、計方法。2. 實驗要求（1） 認真閱讀和掌握教材中插入排序算法的思想。（3） 編寫基于順序隊列的插入排序排序算法并上機實現(xiàn)。3. 實驗內(nèi)容（1） 編寫基于順序隊列的插入排序函數(shù)。（2） 設(shè)計一個測試主函數(shù)，實現(xiàn)對基于順序隊列結(jié)構(gòu)的插入排序算法的測試。（3） 分析程序的運行結(jié)果。實驗代碼：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef struct int key;sortkey;typedef struct sortkey elemMAXSIZE; int length;sortelem;void InsertSort(sortelem *p) int i,j; for(i=2;i<=p->length;i+) if(p->elemi.key<p->elemi-1.key)/*小于時，需將elemi插入有序表*/ p->elem0.key=p->elemi.key; /*為統(tǒng)一算法設(shè)置監(jiān)測*/ for(j=i-1;p->el