1、算法與數據結構實驗報告 學 生 實 驗 報 告 冊 課程名稱:算法與數據結構 實驗項目名稱: 順序表 實驗學時: 2 同組學生姓名: 實驗地點: 工科樓 a205 實驗日期: 2021 年 10 月 16 日 實驗成績: 批改教師: 批改時間: 實驗 1 順序表 一、實驗目得與要求 掌握順序表得定位、插入、刪除等操作。 二、實驗儀器與設備 turbo c 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1） 編寫程序建立一個順序表,并逐個輸出順序表中所有數據元素得值。編寫主函數測試結果。 （2） 編寫順序表定位操作子函數,在順序表中查找就是否存在數據元素 x。如果存在,返回順序

2、表中與x值相等得第1個數據元素得序號(序號從0開始編號);如果不存在,返回1。編寫主函數測試結果。 （3） 在遞增有序得順序表中插入一個新結點 x,保持順序表得有序性。 解題思路:首先查找插入得位置,再移位,最后進行插入操作;從第一個元素開始找到第一個大于該新結點值 x 得元素位置 i 即為插入位置;然后將從表尾開始依次將元素后移一個位置直至元素 i;最后將新結點 x 插入到 i 位置。 （4） 刪除順序表中所有等于 x 得數據元素。 2、選做題 （5） 已知兩個順序表a與b按元素值遞增有序排列,要求寫一算法實現將a與 b 歸并成一個按元素值遞減有序排列得順序表(允許表中含有值相同得元素)。

3、程序清單: : 1、#define maxsize 100 typedef struct int datamaxsize; int last; sequenlist; main int i; sequenlist l=2,5,6,8,2,8,4,3,7; printf(nthe list is:); for(i=0;i=l、last;i+) printf(%2d,l、datai); 2、#define maxsize 100 typedef struct int datamaxsize; int last; sequenlist; main int x,i,s=1; sequenlist l=

4、2,5,6,7,9,8,4,3,7; printf(nthe list is:); for(i=0;i=l、last;i+) printf(%2d,l、datai); printf(nplease input the number :); scanf(%d,x); for(i=0;i=l、last;i+) if(l、datai=x) s=i;break; printf(%d,s); 3、#define maxsize 100 typedef struct int datamaxsize; int last; sequenlist; main int i,x,j; sequenlist l=1,

5、3,5,6,7,9,5; printf(nthe list is:); for(i=0;i=l、last;i+) printf(%2d,l、datai); printf(ninput the insert number:); scanf(%d,x); for(i=1;i=l、last;i+) if(l、datai1x) break; for(j=l、last;j=i1;j) l、dataj+1=l、dataj; l、datai1=x; l、last+; printf(the list after insertion is:n); for(j=0;j=l、last;j+) printf(%3d,

6、l、dataj); 4、#define maxsize 100 typedef struct int datamaxsize; int last; sequenlist; main int i,j,x=0,k=0; sequenlist l=1,3,5,7,2,4,6,8,2,9,9; printf(n the list is:); for(i=0;i=l、last;i+) printf(%3d,l、datai); printf(nplease input a number x:); scanf(%d,x); for(i=1;i=l、last+1;i+) if(l、datai1=x) for(

7、j=i;j=l、last+1;j+) l、dataj1=l、dataj; l、last; i; k=1; if(k=1) printf(the list after deletion is:n); for(j=0;j=l、last;j+) printf(%3d,l、dataj); else printf(not found!n); 四、實驗結果與分析(程序運行結果及其分析) 1、輸出結果:the list is: 2 5 6 8 2 8 4 3 2、輸出結果:the list is: 2 5 6 7 9 8 4 3 please input the number:8 5 the list is

8、: 2 5 6 7 9 8 4 3 please input the number:1 1 3、輸出結果:the list is: 1 3 5 6 7 9 input the insert number:8 the list after insertion is: 1 3 5 6 7 8 9 4、輸出結果:the list is: 1 3 5 7 2 4 6 8 2 9 please input a number x:5 the list after deletion is: 1 3 7 2 4 6 8 2 9 the list is: 1 3 5 7 2 4 6 8 2 9 please i

9、nput a number x:11 not found！ 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:讀取數據元素時,誤將=寫成=,導致錯誤。實驗過程中,順序表得賦值沒有弄懂,以致輸出多個 0 或者少輸出。格式運算符也要正確控制,否則系統會停止工作。 實驗體會:通過實驗掌握了順序表得基本操作,如初始化、插入、讀取元素、刪除等等。并了解到線性表順序存儲結構得特點,即邏輯關系上相鄰得兩個元素在物理位置上也相鄰,然而從另一方面來瞧,在做插入與刪除時需要移動大量元素。本次實驗基本完成了實驗要求得目得,順序表得初始化,定義,插入,查找等,更好得了解了順序表基本操作得算法,以及更直觀

10、得了解了數據結構在 c 語言環境下得體現。 實驗項目名稱: 單鏈表 實驗學時: 2 同組學生姓名: 實驗地點: 工科樓 a205 實驗日期: 2021 年 10 月 23 日 實驗成績: 批改教師: 批改時間: 實驗 2 單鏈表 一、實驗目得與要求 1、實驗目得 掌握單鏈表得定位、插入、刪除等操作。 2、實驗要求 (1)注意鏈表得空間就是動態分配得,某結點不用之后要及時進行物理刪除,以便釋放其內存空間。 (2)鏈表不能實現直接定位,一定注意指針得保存,防止丟失。 二、實驗儀器與設備 turbo c 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1） 編寫程序建立一個單鏈表,并

11、逐個輸出單鏈表中所有數據元素。 （2） 在遞增有序得單鏈表中插入一個新結點 x,保持單鏈表得有序性。 解題思路:首先查找插入得位置然后進行插入操作;從第一個結點開始找到第一個大于該新結點值得結點即為插入位置;然后在找到得此結點之前插入新結點;注意保留插入位置之前結點得指針才能完成插入操作。 （3） 編寫實現帶頭結點單鏈表就地逆置得子函數,并編寫主函數測試結果。 2、選做題 已知指針 la 與 lb 分別指向兩個無頭結點單鏈表得首元結點。要求編一算法實現,從表 la 中刪除自第 i 個元素起共 len 個元素后,將它們插入到表 lb中第 j 個元素之前。 程序清單: : 1、#includest

12、dlib、h typedef int datattype; typedef struct node char data; struct node *next; linklist; main char ch;linklist *head,*s,*r,*p; head=malloc(sizeof(linklist); r=head; scanf(%c,ch); while(ch!="$") s=malloc(sizeof(linklist); sdata=ch; rnext=s; r=s; scanf(%c,ch); rnext=null; r=headnext; while(

13、r!=null) printf(%c,rdata); r=rnext; 2、#include stdio、h #include stdlib、h typedef struct node int data; struct node *next; linklist; main int x,y; linklist *head,*s,*r,*p,*q,*m,*n; clrscr; head=malloc(sizeof(linklist); r=head; printf(input the order numbers :); scanf(%d,x); while(x!=0) s=malloc(sizeo

14、f(linklist); sdata=x; rnext=s; r=s; scanf(%d,x); rnext=null; printf(please input the insert value:); scanf(%d,y); p=headnext; while(p!=null) if (pdatay) p=pnext; else break; q=malloc(sizeof(linklist); qdata=y; m=head; while(mnext!=p) m=mnext; qnext=p; mnext=q; n=headnext; printf(the list are:); whil

15、e(n!=null) printf(%3d,ndata); n=nnext; 3、#include stdio、h #include stdlib、h typedef struct node int data; struct node *next; linklist; main int a; linklist *head,*s,*r,*p,*q,*t; clrscr; head=malloc(sizeof(linklist); r=head; printf(input some numbers:); scanf(%d,a); while(a!=0) s=malloc(sizeof(linkli

16、st); sdata=a; rnext=s; r=s; scanf(%d,a); rnext=null; printf(n the linklist before changed is:n ); p=headnext; while(p) printf(%d,pdata); p=pnext; p=headnext; q=pnext; while(q!=null) t=qnext; qnext=p; p=q; q=t; headnextnext=null; headnext=p; printf(nafter changed:n); p=headnext; while(p!=null) printf

17、(%d,pdata); p=pnext; 四、實驗結果與分析(程序運行結果及其分析) 1、輸入:1 2 3 a b c $ 輸出結果:1 2 3 a b c 2、輸入:input the order numbers : 1 3 5 7 8 9 0 please input the insert value:4 輸出結果:the list are: 1 3 4 5 7 8 9 3、輸入:input some numbers:1 3 4 5 8 0 輸出結果:the linklist before changed is: 13458 after changed: 85431 五、實驗體會(遇到問題

18、及解決辦法,編程后得心得體會) 遇到問題:編寫成功后運行時,沒有加入$導致程序運行不成功,不能夠退出。后注意到這個問題才繼續運行下去。 實驗體會:在編寫程序時,設置了結束字符一定要牢.住,并且在輸入時觀察仔細類型就是什么,以及就是否就是輸入一串有順序得數字,編寫成功不難,但就是要規范格式,不能僅僅以完成程序為目得。而完成這一章得實驗也讓我了解了,順序表便于查找不便于插入刪除,而鏈表恰恰相反,鏈表得插入刪除只需要移動指針,而順序表要從后往前依次移動,二者各有優劣。 實驗項目名稱: 堆棧與隊列 實驗學時: 2 同組學生姓名: 實驗地點: 工科樓 a205 實驗日期: 2021 年 10 月 30

19、日 實驗成績: 批改教師: 批改時間: 實驗 3 堆棧與隊列 一、實驗目得與要求 (1)掌握應用棧解決問題得方法。 (2)掌握利用棧進行表達式求與得算法。 (3)掌握隊列得存儲結構及基本操作實現,并能在相應得應用問題中正確選用它們。 二、實驗儀器與設備 turbo c 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1） 判斷一個算術表達式中開括號與閉括號就是否配對。 （2） 測試"漢諾塔'問題。 （3） 假設稱正讀與反讀都相同得字符序列為'回文',試寫一個算法判別讀入得一個以為結束符得字符序列就是否就是"回文'。 2、選做題

20、 在順序存儲結構上實現輸出受限得雙端循環隊列得入列與出列算法。設每個元素表示一個待處理得作業,元素值表示作業得預計時間。入隊列采取簡化得短作業優先原則,若一個新提交得作業得預計執行時間小于隊頭與隊尾作業得平均時間,則插入在隊頭,否則插入在隊尾。 程序清單: : 1、typedef int datatype; #define m 100 typedef struct char datam; int top; seqstack; main char strm; int result=0,i=0; seqstack s; s、top=0; gets(str); while(stri!="0

21、") if(stri="(") s、top+; s、datas、top="(" if(stri=")") if(s、top=0) result=1; break; else s、top; i+; if(result=0 s、top=0) printf(match!n); else if(result=1) printf(missing left!n); else if(s、top0) printf(missing right!n); 2、#includestdio、h void hanoi(int n,char a,char

22、 b,char c) if(n=1) printf(n move disk %d from pile %c to pile %c,n,a,c); else hanoi(n1,a,c,b); printf(n move disk %d from pile %c to pile %c,n,a,c); hanoi(n1,b,a,c); void main int n; clrscr; printf(n please enter the number of disks to be moved:); scanf(%d,n); hanoi(n,"a","b",&qu

23、ot;c"); 3、#includestdio、h #define m 100 typedef struct char datam; int top; seqstack; main char strm; int i=0,n; seqstack s; s、top=0; gets(str); while(stri!="") i+; if(i=1) printf(yesn); return; n=i; for(i=0;in/2;i+) s、top+; s、datas、top=stri; i=i1; if(n%2=0) i+; else i=i+2; while(in s

24、、datas、top=stri) i+; s、top; if(i=n) printf(yesn); else printf(non); 四、實驗結果與分析(程序運行結果及其分析) 1、輸入:(a) 輸出結果:match！ 輸入:(a 輸出結果:missing right！ 輸入:a) 輸出結果:missing left！ 2、輸入:3 輸出結果:move disk 1 from pile a to pile c move disk 2 from pile a to pile b move disk 1 from pile c to pile b move disk 3 from pile a

25、to pile c move disk 1 from pile b to pile a move disk 2 from pile b to pile c move disk 1 from pile a to pile c 3、輸入:qwewq 輸出結果:yes 輸入:qwerewr 輸出結果 no 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:在本章棧與隊列中編程,有許多得if語句,編寫時一不小心就會少加一個花括號,以致編寫不成功。在本章漢諾塔問題中,使用了棧以及函數得遞歸,這其中得過程一直不就是很了解,在經過老師得講解后,理解了大致過程。 實驗體會:遞歸函數就是編程中經常

26、會用到得一種函數,它可以實現許多我們在平時言語與解釋上解決不了得問題,我們需要理解并且可以熟練得使用它,這對我們之后得編程會有很大得幫助。而漢諾塔利用棧就是一種很經典得遞歸得算法,這讓我們理解棧與遞歸。 實驗項目名稱: 串 實驗學時: 2 同組學生姓名: 實驗地點: 工科樓 a205 實驗日期: 2021 年 11 月 6 日 實驗成績: 批改教師: 批改時間: 實驗 4 串 一、實驗目得與要求 掌握串得存儲及應用。 二、實驗儀器與設備 turbo c 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1） 編寫輸出字符串 s 中值等于字符 ch 得第一個字符得函數,并用主函數測

27、試結果。 （2） 編寫輸出字符串 s 中值等于字符 ch 得所有字符得函數,并用主函數測試結果。 解題思路:可以將第一題程序改進成一個子函數,在本題中循環調用。 （3） 設字符串采用單字符得鏈式存儲結構,編程刪除串 s 從位置 i 開始長度為 k 得子串。 2、選做題 假設以鏈結構表示串,編寫算法實現將串 s 插入到串 t 中某個字符之后,若串t 中不存在這個字符,則將串 s 聯接在串 t 得末尾。 提示:為提高程序得通用性,插入位置字符應設計為從鍵盤輸入。 程序清單: : 1、#define maxsize 100 typedef struct char chmaxsize; int cur

28、len; seqstring; main int i; char ch; seqstring s=asdfghg,6; for(i=0;is、curlen;i+) printf(%c,s、chi); printf(nplease input aa character ch:); scanf(%c,ch); for(i=0;is、curlen;i+) if(s、chi=ch) printf(ch=s、ch%d=%cn,i,s、chi); break; if(i=s、curlen) printf(not find!n); 2、#define maxsize 100 typedef struct c

29、har chmaxsize; int curlen; seqstring; main int i,flag=0; char ch; seqstring s=abadeag,6; for(i=0;is、curlen;i+) printf(%c,s、chi); printf(nplease input aa character ch:); scanf(%c,ch); for(i=0;is、curlen;i+) if(s、chi=ch) printf(ch=s、ch%d=%cn,i,s、chi); flag+; if(flag=0) printf(not find!n); 3、#includestd

30、io、h #includestdlib、h typedef struct linknode char data; struct linknode *next; linkstring; main linkstring *head,*s,*r,*p,*q; int i,b,l,k=0; char ch; head=null;r=null; printf(n next to creat linkstring,$ as end markn); ch=getchar; while(ch!="$") s=malloc(sizeof(linkstring); sdata=ch; if(h

31、ead=null) head=s; else rnext=s; r=s; ch=getchar; if(r!=null) rnext=null; q=head; while(q) printf(%c,qdata); q=qnext; k+; printf(n now input two int for stratpostion and length for deleted:); scanf(%d %d,b,l); if(bk1|b+lk) printf(error!n); return; p=head; for(i=0;ib1;i+) p=pnext; printf(%c %d %d %d n

32、,pdata,b,l,k); for(i=b1;ib+l1;i+) q=pnext;pnext=qnext;free(q); q=head; while(q) printf(%c,qdata); q=qnext; printf(n); 四、實驗結果與分析(程序運行結果及其分析) 1、輸入:s 輸出結果:ch=s、ch1=s 2、輸入:a 輸出結果:ch=s、ch0=a ch=s、ch2=a ch=s、ch5=a 3、輸入:asdfghjkl$ 2 5 輸出結果:s 2 5 9 askl 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 實驗體會:本章第一題可以作為第二題得子函數,使用調用;

33、也可以從開頭查找對應得字符到結尾,最后全部輸出。前兩題使用順序串,后面一題就是鏈串。串得存儲結構包含有順序存儲結構與鏈式存儲結構。在串得順序存儲結構中,表示串得長度通常有兩種方法:一種方法就是設置一個串得長度參數,其優點在于便于在算法中用長度參數控制循環過程;另一種方法就是在串值得末尾添加結束標記,此種方法得優點在于便于系統自動實現。在串得存儲過程中,串值用雙引號引起來,系統將自動在串值得末尾添加結束標記0 字符。 實驗項目名稱: 二叉樹 實驗學時: 2 同組學生姓名: 實驗地點: 工科樓 a205 實驗日期: 2021 年 11 月 13 日 實驗成績: 批改教師: 批改時間: 實驗 5 二

34、叉樹 一、實驗目得與要求 (1)掌握二叉樹得生成,以及前、中、后序遍歷算法。 (2)掌握應用二叉樹遞歸遍歷思想解決問題得方法。 二、實驗儀器與設備 turbo c 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1） 建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷,輸出遍歷序列。 （2） 在第一題基礎上,求二叉樹中葉結點得個數。 （3） 在第一題基礎上,求二叉樹中結點總數。 （4） 在第一題基礎上,求二叉樹得深度。 2、選做題 已知一棵完全二叉樹存于順序表 sa 中,sa、elem1sa、last存儲結點得值。試編寫算法由此順序存儲結構建立該二叉樹得二叉鏈表。 解題思路

35、:根據完全二叉樹順序存儲得性質來確定二叉樹得父子關系即"還原'了二叉樹,之后再按照二叉樹二叉鏈表得構造方法進行建立。完全二叉樹順序存儲得一個重要性質為,第 i 個結點得左孩子就是編號為 2i 得結點,第 i個結點得右孩子就是編號為 2i+1 得結點。 程序清單: : 1(1)#includestdio、h #includestdlib、h #define maxsize 100 typedef struct node char data; struct node *lchild,*rchild; bitree; bitree *qmaxsize; bitree *creatr

36、ee char ch; int front,rear; bitree *root,*s; root=null;front=1;rear=0; printf(now creat the bitree,input baseing the order top to bottom,left to right:n); ch=getchar; while(ch!="#") s=null; if(ch!="") s=malloc(sizeof(bitree); sdata=ch; slchild=null; srchild=null; rear+; qrear=s;

37、if(rear=1) root=s; else if(s qfront) if(rear%2=0) qfrontlchild=s; else qfrontrchild=s; if(rear%2=1) front+; ch=getchar; return root; void preorder(t) bitree *t; if(t) printf(%c,tdata); preorder(tlchild); preorder(trchild); void inorder(t) bitree *t; if(t) inorder(tlchild); printf(%c,tdata); inorder(

38、trchild); void postorder(t) bitree *t; if(t) postorder(tlchild); postorder(trchild); printf(%c,tdata); main bitree *root; clrscr; root=creatree; printf(preorder is:);preorder(root); printf(n); printf(inorder is:);inorder(root); printf(n); printf(postorder is:);postorder(root); printf(n); ? (2)#inclu

39、destdio、h #includestdlib、h #define maxsize 100 typedef struct node char data; struct node *lchild,*rchild; bitree; bitree *qmaxsize; bitree *creatree char ch; int front,rear; bitree *root,*s; root=null;front=1;rear=0; printf(now creat the bitree,input baseing the order top to bottom,left to right:n)

40、; ch=getchar; while(ch!="#") s=null; if(ch!="") s=malloc(sizeof(bitree); sdata=ch; slchild=null; srchild=null; rear+; qrear=s; if(rear=1) root=s; else if(s qfront) if(rear%2=0) qfrontlchild=s; else qfrontrchild=s; if(rear%2=1) front+; ch=getchar; return root; int left(bitree *t)

41、int num1,num2; if(t=null) return 0; else if(tlchild=null trchild=null) return 1; else num1=left(tlchild); num2=left(trchild); return(num1+num2); main bitree *root; clrscr; root=creatree; printf(lefts is %dn,left(root); ? (3)#includestdio、h #includestdlib、h #define maxsize 100 typedef struct node cha

42、r data; struct node *lchild,*rchild; bitree; bitree *qmaxsize; bitree *creatree char ch; int front,rear; bitree *root,*s; root=null;front=1;rear=0; printf(now creat the bitree,input baseing the order top to bottom,left to right:n); ch=getchar; while(ch!="#") s=null; if(ch!="") s=

43、malloc(sizeof(bitree); sdata=ch; slchild=null; srchild=null; rear+; qrear=s; if(rear=1) root=s; else if(s qfront) if(rear%2=0) qfrontlchild=s; else qfrontrchild=s; if(rear%2=1) front+; ch=getchar; return root; int nodes(bitree *t) int num1,num2; if(t=null) return 0; else if(tlchild=null trchild=null

44、) return 1; else num1=nodes(tlchild); num2=nodes(trchild); return (num1+num2+1); main bitree *root; clrscr; root=creatree; printf(nodes is %dn,nodes(root); ? (4)#includestdio、h #includestdlib、h #define maxsize 100 typedef struct node char data; struct node *lchild,*rchild; bitree; bitree *qmaxsize;

45、bitree *creatree char ch; int front,rear; bitree *root,*s; root=null;front=1;rear=0; printf(now creat the bitree,input baseing the order top to bottom,left to right:n); ch=getchar; while(ch!="#") s=null; if(ch!="") s=malloc(sizeof(bitree); sdata=ch; slchild=null; srchild=null; re

46、ar+; qrear=s; if(rear=1) root=s; else if(s qfront) if(rear%2=0) qfrontlchild=s; else qfrontrchild=s; if(rear%2=1) front+; ch=getchar; return root; int depth(bitree *t) int dep1,dep2; if(t=null) return 0; else dep1=depth(tlchild); dep2=depth(trchild); if(dep1dep2) return (dep1+1); else return(dep2+1); main bitree *root; clrscr; root=creatree; printf(depth is %dn,depth(root); ? 四、實驗結果與分析(程序運行結果及其分析) (1)now creat the bitree,