數(shù)據(jù)結構實驗報告全集_第1頁
數(shù)據(jù)結構實驗報告全集_第2頁
數(shù)據(jù)結構實驗報告全集_第3頁
數(shù)據(jù)結構實驗報告全集_第4頁
數(shù)據(jù)結構實驗報告全集_第5頁
已閱讀5頁，還剩19頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、1 / 25數(shù)據(jù)結構實驗報告全集實驗一 線性表基本操作和簡單程序1 實驗目的1 掌握使用 Visual C+ 6.0上機調(diào)試程序的基本方法；2 掌握線性表的基本操作：初始化、插入、刪除、取數(shù)據(jù)元素等運算在順序存儲結構和鏈表存儲結構上的程序設計方法。2 實驗要求1 認真閱讀和掌握和本實驗相關的教材內(nèi)容。2 認真閱讀和掌握本章相關內(nèi)容的程序。3 上機運行程序。4 保存和打印出程序的運行結果 , 并結合程序進行分析。5 按照你對線性表的操作需要 , 重新改寫主程序并運行 ,打印出文件清單和運行結果實驗代碼：頭文件庫頭文件 動態(tài)分配內(nèi)存空間定義數(shù)據(jù)域的類型定義結點類型定義數(shù)據(jù)域定義結點指針1 頭文件模

2、塊#include iostream.h>/ #include<malloc.h>/ typedef int elemtype;/ typedef struct linknode/ elemtype data;/struct linknode *next;/ nodetype;2 創(chuàng)建單鏈表nodetype *create<>/ 建立單鏈表 , 由用戶輸入各結點 data 域之值 , / 以 0 表示輸入結束elemtype d;/定義數(shù)據(jù)元素 dnodetype *h=NULL,*s,*t;/ 定義結點指針 int i=1;cout<<"

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

4、nodetype*> malloc<sizeof<nodetype>> s->data=d;s->next=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<

5、<" 空表 "while<p!=NULL>cout<<p->data<<" "p=p->next;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

6、=h;int j=1;if<i>len<h>|i<=0>return NULL;/i 上溢或下溢 celsewhile <p!=NULL&&j<1>/ 查找第 i 個節(jié)點 , 并由 p 指向該節(jié)點 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*&

7、gt;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;elsep=find<h,i>/ 查找第 i 個節(jié)點 , 并由 p 指向該節(jié)點if<p!=NULL>s->next=p->next;p->next=s;return h;7 單鏈表的刪除操作nodetype *del<nodetype *h,int i>/ 刪除第 i 個節(jié)點nodetype

8、*p=h, *s;int j=1;if<i=1>/ 刪除第 1 個節(jié)點h=h->next;free<p>elsep=find<h,i-1>/ 查找第 i-1 個節(jié)點 , 并由 p 指向該節(jié)點3 / 25if<p!=NULL&&p->next!=NULL>s=p->next;/s 指向要刪除的節(jié)點 p->next=s->next;free<s>else cout<<" 輸入 i 的值不正確 "<<endl;return h;8 釋放節(jié)點空間void

9、 dispose<nodetype *h>/ 釋放單鏈表的所有節(jié)點占用的空間 nodetype *pa=h,*pb;if<pa!=NULL>pb=pa->next;if<pb=NULL>/ 只有一個節(jié)點的情況 free<pa>else有兩個及以上節(jié)點的情況while <pb!=NULL>/free<pa>pa=pb;pb=pb->next;free<pa>包含頭文件 slink定義節(jié)點指針變量創(chuàng)建一個單鏈表9>主程序模塊 :#include"slink.h"/ void m

10、ain<>nodetype *head;/ head=create<>/disp<head>/ 輸出單鏈表cout<<" 單鏈表長度 :"<<len<head><<endlins<head, 2,0>/ 在第二個節(jié)點之后插入以 0 為元素的節(jié)點 disp<head>/ 輸出新鏈表del<head,2>/ 刪除第二個節(jié)點 disp<head>/ 輸出新鏈表5實驗結果建立一個單鏈表： 輸入第 1 結點 data 域值： 1輸入第 2 結點 data

11、 域值： 2輸入第 3 結點 data 域值： 3輸入第 4 結點 data 域值： 4輸入第 5 結點 data 域值： 5輸入第 6 結點 data 域值： 6輸入第 7 結點 data 域值： 7輸入第 8 結點 data 域值： 8輸入第 9 結點 data 域值： 9輸入第 10 結點 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. 實驗目的掌握順序棧的基本操作：初始化棧、判棧空否、入棧、出棧、取棧頂數(shù)據(jù)元素等運算以

12、及程序?qū)崿F(xiàn)方法。2. 實驗要求1 認真閱讀和掌握和本實驗相關的教材內(nèi)容。2 分析問題的要求 ,編寫和調(diào)試完成程序。3 保存和打印出程序的運行結果 , 并分析程序的運行結果。3. 實驗內(nèi)容利用棧的基本操作實現(xiàn)一個判斷算術表達式中包含圓括號、方括號是否正確配對的程序。具體完成如下：1 定義棧的順序存取結構。2 分別定義順序棧的基本操作初始化棧、判?？辗瘛⑷霔?、出棧等。3 定義一個函數(shù)用來判斷算術表達式中包含圓括號、方括號是否正確配對。其中, 括號配對共有四種情況：左右括號配對次序不正確； 右括號多于左括號； 左括號多于右括號； 左右 括號匹配正確。4設計一個測試主函數(shù)進行測試。5對程序的運行結果進

13、行分析。 實驗代碼：#i nclude vstdio.h >#defi ne MaxSize 100 typedef structint dataMaxSize;int top;SqStack;void In itStackvSqStack *st> /初始化棧st->top=-1;int StackEmptyvSqStack *st> / 判斷棧為空retur n <st->top=-1>void PushvSqStack *st,i nt x> / 元素進棧 if<st->top=MaxSize-1>printf<&q

14、uot;棧上溢出!n">elsest->top+; st->datast->top=x;void PopvSqStack *st> / 退棧if<st->top=-1> printfv"棧下溢出 n">elsest->top-;int GettopvSqStack *st> / 獲得棧頂元素if<st->top=-1>prin tf<"?？?n">return 0;elsereturn st->datast->top;void Displ

15、ayvSqStack *st> /打印棧里元素int i;printfv"棧中元素：">for<i=st->top;i>=0;-i>prin tf<"%d ",st->datai>prin tf<"n">int mai n<> / 測試SqStack L;SqStack *st=&L;In itStack<st>printf<"棧空：dn",StackEmpty<st>>forvint i=1;

16、i<10;+i>Push<st,i>Display<st>printfv"退一次棧 n">Pop<st>printf<"棧頂元素:%dn",Gettop<st>>Pop<st>Display<st>return 0;實驗結果：實驗三串的基本操作和簡程序1. 實驗目的掌握串基本操作：初始化、聯(lián)接、替換、子串等運算在堆分配存儲儲結構上的程序設計方法。2. 實驗要求1認真閱讀和掌握和本實驗相關的教材內(nèi)容。2認真閱讀和掌握本章相關內(nèi)容的算法并設計程序序。3上機運

17、行程序。4保存和打印出程序的運行結果，并結合程序進行分析。實驗代碼：#include<stdio.h>#define MaxSize 50typedef structchar dataMaxSize; / 存放字符串int length; /字符串長度SqString;/ 將一個字符串常量賦給串 svoid StrAssign<SqString &s,char cstr>int i;for<i=0;cstri!='0'i+> / 這個 '0' 代表字符串結 束標志 , 編譯系統(tǒng)自動加上的s.datai=cstri;s.

18、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<" 字符串復制成功了 n">/ 判斷字符串是否相等void StrEqual<SqString s,SqString t>int i,same=1;if<s.length!=t.length> same=0;elsefor<i=0;i<s.lengt

19、h;i+> if<s.datai!=t.datai> same=0;break; if<same=0> printf<" 這兩個字符串不相等 n">elseprintf<" 這兩個字符串相等 n">/ 字符串的長度void StrLength<SqString s>printf<" 此字符串長度為： %dn",s.length>/ 合并字符串SqString Concat<SqString s,SqString t>SqString str;in

20、t 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;str.length=0; if<i<=0|i>s.length|j<0|i+j-1>s.length> printf<

21、;" 子字符串復制失敗 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">/ 插入字符串SqString InserStr<

22、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.lengt

23、h+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<

24、k=0;k<i-1;k+>str.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&

25、gt;s.length|i+j-1>s.length>printf<" 字符串替換失敗了 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<" 替 換 字 符 串 成 功 新 字 符

26、串 長 度 為： %dn",str.length>/ 字符串的輸出void DispStr<SqString s>int i;if<s.length>0>printf<" 下面輸出這個字符串 n">for<i=0;i<s.length;i+>printf<"%c",s.datai>printf<"n">elseprintf<" 目前空字符串 無法輸出 n">void main<>SqStrin

27、g s;字符串常量 achar a="wen xian liang" /StrAssign<s,a>DispStr<s>StrLength<s>SqString s1,s2,t; /s1是待復制的字符串變量printf<" 請輸入一個字符串 t:n"> scanf<"%s",t.data>StrAssign<t,t.data>StrCopy<s1,t> / 復制字符串StrLength<s1>DispStr<s1>printf&

28、lt;" 下面判斷字符串 s1 和字符串 s 是否相等 n"> StrEqual<s,s1>printf<" 下面將字符串SqString str;s1 和字符串 s 合并一起 n">str=Concat<s,s1> /合并字符串DispStr<str>StrLength<str>SubStr<str,22,7> /求子字符串str=DeleStr<str,15,4> /刪除字符串DispStr<str>StrLength<str>print

29、f<" 請插入一個字符串 s2n"> scanf<"%s",s2.data>StrAssign<s2,s2.data>str=InserStr<str,15,s2> / 插入字符串 DispStr<str>StrLength<str>printf<" 順序字符串的基本運算到此結束了 n"> 實驗結果： 實驗四 編程建立二叉樹 ,對樹進行插入刪除及遍歷的程序1. 實驗目的1 進一步掌握指針變量的用途和程序設計方法。2 掌握二叉樹的結構特征 , 以及鏈式存

30、儲結構的特點及程序設計方法。3 掌握構造二叉樹的基本方法。4 掌握二叉樹遍歷算法的設計方法。3 實驗要求1 認真閱讀和掌握和本實驗相關的教材內(nèi)容。2 掌握一個實際二叉樹的創(chuàng)建方法。3 掌握二叉鏈存儲結構下二叉樹操作的設計方法和遍歷操作設計方法。4 實驗內(nèi)容1 定義二叉鏈存儲結構。2 設計二叉樹的基本操作初始化一棵帶頭結點的二叉樹、左結點插入、右結點插入、中 序遍歷二叉樹等。15 / 253 按照建立一棵實際二叉樹的操作需要,編寫建立二叉樹、遍歷二叉樹的函數(shù)。16 / 254 編寫測試主函數(shù)并上機運行。打印出運行結果 , 并結合程序運行結果進行分析。 實驗代碼：#include<iostr

31、eam.h>typedef struct bitnodechar 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> createbitree<&am

32、p;<*T>->rchild>void inorderout<bitree T>if<T># / 25inorderout<T->lchild>cout<<T->data<<endl;inorderout<T->rchild>void postorder<bitree T>if<T>postorder<T->lchild>postorder<T->rchild>cout<<T->data<<e

33、ndl;int countleaf<bitree bt>if<!bt>return 0;if<bt->lchild=NULL&&bt->rchild=NULL>return 1;return<countleaf<bt->lchild>+countleaf<bt->rchild>>void main<>bitree bt;createbitree<&bt>inorderout<bt>cout<<" "<&

34、lt;endl;postorder<bt>countleaf<bt>實驗五 建立有序表并進行折半查找1. 實驗目的 掌握遞歸算法求解問題的基本思想和程序?qū)崿F(xiàn)方法。2 實驗要求1 認真閱讀和掌握本實驗的算法思想。 2 編寫和調(diào)試完成程序。3 保存和打印程序的運行結果 , 并對運行結果進行分析。3. 實驗內(nèi)容1 分析掌握折半查找算法思想 , 在此基礎上 ,設計出遞歸算法和循環(huán)結構兩種實現(xiàn)方法的 折半查找函數(shù)。2 編寫程序?qū)崿F(xiàn)：在保存于數(shù)組的 1000 個有序數(shù)據(jù)元素中查找數(shù)據(jù)元素 x 是否存在。 數(shù)據(jù)元素 x 要包含兩種情況：一種是數(shù)據(jù)元素 x 包含在數(shù)組中；另一種是數(shù)據(jù)元

35、素 x 不包 含在數(shù)組中3 數(shù)組中數(shù)據(jù)元素的有序化既可以初始賦值時實現(xiàn), 也可以設計一個排序函數(shù)實現(xiàn)。4 根據(jù)兩種方法的實際運行時間 , 進行兩種方法時間效率的分析對比。 實驗代碼：#include<stdio.h>#include<stdlib.h>#define MAX_LENGTH 100typedef int KeyType;typedef structint key;ElemType;typedef structElemType elemMAX_LENGTH;/ 0 號單元空出int length;SSTable;int Search_Bin<SSTab

36、le 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<key<ST.elemmid.key> high = mid-1;else low=mid+1;return 0;void main<>int i,result;SSTable ST;KeyType key; printf<"p

37、lease 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&

38、lt;ST,key> if<result=0>printf<"Don't findn">elseprintf<"Find the key,the position is %dn",result> 實驗結果：實驗六建立一組記錄并進行插入排序1. 實驗目的1 掌握插入排序算法的思想。2 掌握順序隊列下插入排序算法的程序設計方法。2. 實驗要求1 認真閱讀和掌握教材中插入排序算法的思想。 3 編寫基于順序隊列的插入排序排序算法并上機實現(xiàn)。3. 實驗內(nèi)容 1 編寫基于順序隊列的插入排序函數(shù)。2 設計一個測試主函數(shù)

39、 , 實現(xiàn)對基于順序隊列結構的插入排序算法的測試。3 分析程序的運行結果。實驗代碼：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef structint key;sortkey;typedef structsortkey elemMAXSIZE;int length;sortelem;void InsertSort<sortelem *p>int i,j;for<i=2;i<=p->length;i+>21 / 25# / 25if<p->elemi.key<p->elemi-1.key>/*p->elem0.key=p->elemi.key; /*小于時 , 需將 elemi為統(tǒng)一算法設置監(jiān)測 */插入有序表 */# / 25# / 25for<j=i-1;p->elem0.key<p->elemj.key;j->記錄后移 */插入到正確位置 */p->elemj+1.key=p->el

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論