算法與數(shù)據(jù)結(jié)構(gòu)實驗報告.docVIP

金陵科技學(xué)院實驗報告學(xué) 生 實 驗 報 告 冊課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)實驗項目名稱： 順序表 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 工科樓A205 實驗日期： 2013年10月16日 實驗成績： 批改教師： 批改時間： 實驗1 順序表一、實驗?zāi)康暮鸵笳莆枕樞虮淼亩ㄎ?、插入、刪除等操作。二、實驗儀器和設(shè)備Turbo C 2.0三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1） 編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。（2） 編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回1。編寫主函數(shù)測試結(jié)果。（3） 在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進行插入操作；從第一個元素開始找到第一個大于該新結(jié)點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結(jié)點x插入到i位置。（4） 刪除順序表中所有等于X的數(shù)據(jù)元素。2、選做題（5） 已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。程序清單：1、#define maxsize 100typedef 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 100typedef struct int datamaxsize; int last;sequenlist;main() int x,i,s=-1; sequenlist l=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 100typedef struct int datamaxsize; int last;sequenlist;main() int i,x,j; sequenlist l=1,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;ix) break; for(j=l.last;j=i-1;j-) l.dataj+1=l.dataj; l.datai-1=x; l.last+; printf(the list after insertion is:n); for(j=0;j=l.last;j+) printf(%3d,l.dataj);4、#define maxsize 100typedef 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.datai-1=x) for(j=i;j=L.last+1;j+) L.dataj-1=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);四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）1、輸出結(jié)果：The list is： 2 5 6 8 2 8 4 32、輸出結(jié)果：The list is： 2 5 6 7 9 8 4 3 Please input the number：8 5The list is： 2 5 6 7 9 8 4 3 Please input the number：1 -13、輸出結(jié)果：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 94、輸出結(jié)果：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 input a number x：11 Not found！五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：讀取數(shù)據(jù)元素時，誤將=寫成=，導(dǎo)致錯誤。實驗過程中，順序表的賦值沒有弄懂，以致輸出多個0或者少輸出。格式運算符也要正確控制，否則系統(tǒng)會停止工作。實驗體會：通過實驗掌握了順序表的基本操作，如初始化、插入、讀取元素、刪除等等。并了解到線性表順序存儲結(jié)構(gòu)的特點，即邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，然而從另一方面來看，在做插入和刪除時需要移動大量元素。本次實驗基本完成了實驗要求的目的，順序表的初始化，定義，插入，查找等，更好的了解了順序表基本操作的算法，以及更直觀的了解了數(shù)據(jù)結(jié)構(gòu)在C語言環(huán)境下的體現(xiàn)。實驗項目名稱： 單鏈表 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 工科樓A205 實驗日期： 2013年10月23日 實驗成績： 批改教師： 批改時間： 實驗2 單鏈表一、實驗?zāi)康暮鸵?、實驗?zāi)康恼莆諉捂湵淼亩ㄎ?、插入、刪除等操作。2、實驗要求（1）注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進行物理刪除，以便釋放其內(nèi)存空間。（2）鏈表不能實現(xiàn)直接定位，一定注意指針的保存，防止丟失。二、實驗儀器和設(shè)備Turbo C 2.0三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1） 編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。（2） 在遞增有序的單鏈表中插入一個新結(jié)點x，保持單鏈表的有序性。解題思路：首先查找插入的位置然后進行插入操作；從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保留插入位置之前結(jié)點的指針才能完成插入操作。（3） 編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。2、選做題已知指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單：1、#includetypedef 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); s-data=ch; r-next=s; r=s; scanf(%c,&ch); r-next=NULL; r=head-next; while(r!=NULL) printf(%c,r-data); r=r-next; 2、#include stdio.h#include stdlib.htypedef 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(sizeof(linklist); s-data=x; r-next=s; r=s; scanf(%d,&x); r-next=NULL; printf(Please input the insert value:); scanf(%d,&y); p=head-next; while(p!=NULL) if (p-datanext; else break; q=malloc(sizeof(linklist); q-data=y; m=head; while(m-next!=p) m=m-next; q-next=p; m-next=q; n=head-next; printf(the list are:); while(n!=NULL) printf(%3d,n-data); n=n-next; 3、#include stdio.h#include stdlib.htypedef 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(linklist); s-data=a; r-next=s; r=s; scanf(%d,&a); r-next=NULL; printf(n The linklist before changed is:n ); p=head-next; while(p) printf(%d,p-data); p=p-next; p=head-next; q=p-next; while(q!=NULL) t=q-next; q-next=p; p=q; q=t; head-next-next=NULL; head-next=p; printf(nAfter changed:n); p=head-next; while(p!=NULL) printf(%d,p-data); p=p-next; 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）1、輸入：1 2 3 a b c $輸出結(jié)果：1 2 3 a b c 2、輸入：input the order numbers : 1 3 5 7 8 9 0Please input the insert value:：4 輸出結(jié)果：the list are: 1 3 4 5 7 8 93、輸入：Input some numbers:1 3 4 5 8 0 輸出結(jié)果：The linklist before changed is: 13458After changed: 85431五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：編寫成功后運行時，沒有加入$導(dǎo)致程序運行不成功，不能夠退出。后注意到這個問題才繼續(xù)運行下去。實驗體會：在編寫程序時，設(shè)置了結(jié)束字符一定要牢牢記住，并且在輸入時觀察仔細類型是什么，以及是否是輸入一串有順序的數(shù)字，編寫成功不難，但是要規(guī)范格式，不能僅僅以完成程序為目的。而完成這一章的實驗也讓我了解了，順序表便于查找不便于插入刪除，而鏈表恰恰相反，鏈表的插入刪除只需要移動指針，而順序表要從后往前依次移動，二者各有優(yōu)劣。實驗項目名稱： 堆棧和隊列 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 工科樓A205 實驗日期： 2013年10月30日 實驗成績： 批改教師： 批改時間： 實驗3 堆棧和隊列一、實驗?zāi)康暮鸵螅?）掌握應(yīng)用棧解決問題的方法。（2）掌握利用棧進行表達式求和的算法。（3）掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。二、實驗儀器和設(shè)備Turbo C 2.0三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1） 判斷一個算術(shù)表達式中開括號和閉括號是否配對。（2） 測試“漢諾塔”問題。（3） 假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文”。2、選做題在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預(yù)計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。程序清單：1、typedef int datatype;#define M 100typedef struct char dataM; int top; seqstack;main() char strM; int result=0,i=0; seqstack s; s.top=0; gets(str); while(stri!=0) 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、#includevoid hanoi(int n,char a,char b,char c) if(n=1) printf(n Move disk %d from pile %c to pile %c,n,a,c); else hanoi(n-1,a,c,b); printf(n Move disk %d from pile %c to pile %c,n,a,c); hanoi(n-1,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,C);3、#include#define M 100typedef 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=i-1; if(n%2=0) i+; else i=i+2; while(in & s.datas.top=stri) i+; s.top-; if(i=n) printf(Yesn); else printf(Non);四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）1、輸入：（a）輸出結(jié)果：Match！輸入：（a輸出結(jié)果：Missing right！輸入：a）輸出結(jié)果：Missing left！2、輸入：3 輸出結(jié)果：Move disk 1 from pile A to pile CMove disk 2 from pile A to pile BMove disk 1 from pile C to pile BMove disk 3 from pile A to pile CMove disk 1 from pile B to pile AMove disk 2 from pile B to pile CMove disk 1 from pile A to pile C3、輸入：qwewq 輸出結(jié)果：Yes 輸入：qwerewr 輸出結(jié)果No五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：在本章棧和隊列中編程，有許多的if語句，編寫時一不小心就會少加一個花括號，以致編寫不成功。在本章漢諾塔問題中，使用了棧以及函數(shù)的遞歸，這其中的過程一直不是很了解，在經(jīng)過老師的講解后，理解了大致過程。實驗體會：遞歸函數(shù)是編程中經(jīng)常會用到的一種函數(shù)，它可以實現(xiàn)許多我們在平時言語和解釋上解決不了的問題，我們需要理解并且可以熟練的使用它，這對我們之后的編程會有很大的幫助。而漢諾塔利用棧是一種很經(jīng)典的遞歸的算法，這讓我們理解棧和遞歸。實驗項目名稱： 串 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 工科樓A205實驗日期： 2013年11月6日 實驗成績： 批改教師： 批改時間： 實驗4 串一、實驗?zāi)康暮鸵笳莆沾拇鎯皯?yīng)用。二、實驗儀器和設(shè)備Turbo C 2.0三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1） 編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。（2） 編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。解題思路：可以將第一題程序改進成一個子函數(shù)，在本題中循環(huán)調(diào)用。（3） 設(shè)字符串采用單字符的鏈?zhǔn)酱鎯Y(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。2、選做題假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計為從鍵盤輸入。程序清單：1、#define maxsize 100typedef struct char chmaxsize; int curlen;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;i=s.curlen) printf(Not find!n);2、#define maxsize 100typedef struct char 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、#include#includetypedef 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); s-data=ch; if(head=NULL) head=s; else r-next=s; r=s; ch=getchar(); if(r!=NULL) r-next=NULL; q=head; while(q) printf(%c,q-data); q=q-next; k+; printf(n Now input two int for stratpostion and length for deleted:); scanf(%d %d,&b,&l); if(bk-1|b+lk) printf(Error!n); return; p=head; for(i=0;inext; printf(%c %d %d %d n,p-data,b,l,k); for(i=b-1;inext;p-next=q-next;free(q); q=head; while(q) printf(%c,q-data); q=q-next; printf(n);四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）1、輸入：s 輸出結(jié)果：ch=s.ch1=s2、輸入：a 輸出結(jié)果：ch=s.ch0=a ch=s.ch2=a ch=s.ch5=a3、輸入：asdfghjkl$ 2 5 輸出結(jié)果：s 2 5 9 askl五、實驗體會（遇到問題及解決辦法，編程后的心得體會）實驗體會：本章第一題可以作為第二題的子函數(shù)，使用調(diào)用；也可以從開頭查找對應(yīng)的字符到結(jié)尾，最后全部輸出。前兩題使用順序串，后面一題是鏈串。串的存儲結(jié)構(gòu)包含有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。在串的順序存儲結(jié)構(gòu)中，表示串的長度通常有兩種方法：一種方法是設(shè)置一個串的長度參數(shù)，其優(yōu)點在于便于在算法中用長度參數(shù)控制循環(huán)過程；另一種方法是在串值得末尾添加結(jié)束標(biāo)記，此種方法的優(yōu)點在于便于系統(tǒng)自動實現(xiàn)。在串的存儲過程中，串值用雙引號引起來，系統(tǒng)將自動在串值得末尾添加結(jié)束標(biāo)記0字符。實驗項目名稱： 二叉樹 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 工科樓A205 實驗日期： 2013年11月13日 實驗成績： 批改教師： 批改時間： 實驗5 二叉樹一、實驗?zāi)康暮鸵螅?）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。二、實驗儀器和設(shè)備Turbo C 2.0三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1） 建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。（2） 在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點的個數(shù)。（3） 在第一題基礎(chǔ)上，求二叉樹中結(jié)點總數(shù)。（4） 在第一題基礎(chǔ)上，求二叉樹的深度。2、選做題已知一棵完全二叉樹存于順序表sa中，sa.elem1sa.last存儲結(jié)點的值。試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進行建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結(jié)點的左孩子是編號為2i的結(jié)點，第i個結(jié)點的右孩子是編號為2i+1的結(jié)點。程序清單：1（1）#include#include#define maxsize 100typedef 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); ch=getchar(); while(ch!=#) s=NULL; if(ch!=) s=malloc(sizeof(bitree); s-data=ch; s-lchild=NULL; s-rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s & Qfront)if(rear%2=0) Qfront-lchild=s;else Qfront-rchild=s; if(rear%2=1) front+; ch=getchar(); return root;void preorder(t)bitree *t; if(t) printf(%c,t-data); preorder(t-lchild); preorder(t-rchild); void inorder(t)bitree *t; if(t) inorder(t-lchild); printf(%c,t-data); inorder(t-rchild); void postorder(t)bitree *t; if(t) postorder(t-lchild); postorder(t-rchild); printf(%c,t-data); 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）#include#include#define maxsize 100typedef 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); ch=getchar(); while(ch!=#) s=NULL; if(ch!=) s=malloc(sizeof(bitree); s-data=ch; s-lchild=NULL; s-rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s & Qfront)if(rear%2=0) Qfront-lchild=s;else Qfront-rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int left(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t-lchild=NULL & t-rchild=NULL) return 1; else num1=left(t-lchild); num2=left(t-rchild); return(num1+num2); main() bitree *root; clrscr(); root=Creatree(); printf(lefts is %dn,left(root);（3）#include#include#define maxsize 100typedef 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); ch=getchar(); while(ch!=#) s=NULL; if(ch!=) s=malloc(sizeof(bitree); s-data=ch; s-lchild=NULL; s-rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s & Qfront)if(rear%2=0) Qfront-lchild=s;else Qfront-rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int nodes(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t-lchild=NULL &t-rchild=NULL) return 1; else num1=nodes(t-lchild); num2=nodes(t-rchild); return (num1+num2+1); main() bitree *root; clrscr(); root=Creatree(); printf(nodes is %dn,nodes(root);（4）#include#include#define maxsize 100typedef 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); ch=getchar(); while(ch!=#) s=NULL; if(ch!=) s=malloc(sizeof(bitree); s-data=ch; s-lchild=NULL; s-rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s & Qfront)if(rear%2=0) Qfront-lchild=s;else Qfront-rchild=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(t-lchild); dep2=depth(t-rchild); if(dep1dep2) return (dep1+1); else return(dep2+1); main() bitree *root; clrscr(); root=Creatree(); printf(depth is %dn,depth(root);四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）（1）Now Creat the bitree,input baseing the order top to bottom,left to right:abc#preorder is:abcinorder is:abcpostorder is:cba（2）Now Creat the bitree,input baseing th