數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗報告.doc

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗報告 學(xué) 院：電子工程學(xué)院 專 業(yè)：信息對抗技術(shù) 姓 名： 學(xué) 號： 教 師：饒 鮮 日 期：目 錄實(shí)驗一 線性表- 2 -一、實(shí)驗?zāi)康? 2 -二、實(shí)驗代碼- 2 -三、實(shí)驗結(jié)果- 8 -四、個人思路- 9 -實(shí)驗二 棧和隊列- 9 -一、實(shí)驗?zāi)康? 9 -二、實(shí)驗代碼- 10 -三、實(shí)驗結(jié)果- 15 -四、個人思路- 16 -實(shí)驗三 數(shù)組- 16 -一、實(shí)驗?zāi)康? 16 -二、實(shí)驗代碼- 16 -三、實(shí)驗結(jié)果- 18 -四、個人思路- 18 -實(shí)驗四 樹- 18 -一、實(shí)驗?zāi)康? 18 -二、實(shí)驗代碼- 19 -三、實(shí)驗結(jié)果- 24 -四、個人思路- 25 - 40 -實(shí)驗一 線性表一、實(shí)驗?zāi)康? 熟悉線性表的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)2 掌握線性表的基本運(yùn)算3 能夠利用線性表的基本運(yùn)算完成線性表應(yīng)用的運(yùn)算二、實(shí)驗代碼1 設(shè)有一個線性表E=e1, e2, , en-1, en，設(shè)計一個算法，將線性表逆置，即使元素排列次序顛倒過來，成為逆線性表E= en, en-1 , , e2 , e1 ，要求逆線性表占用原線性表空間，并且用順序表和單鏈表兩種方法表示，分別用兩個程序來完成。（文件夾：習(xí)題1）代碼：單鏈表代碼：/單鏈表逆置主文件.cpp#include#include#include單鏈表結(jié)構(gòu)類型定義.h#include建立單鏈表.h#include輸出單鏈表.h#include單鏈表逆置.hvoid main()linklist*head;creat(head);print(head);invert(head);/調(diào)用單鏈表逆置的函數(shù)print(head);/單鏈表結(jié)構(gòu)類型定義.htypedef char datatype;typedef struct nodedatatype data;struct node *next;linklist;/建立單鏈表.hvoid creat(linklist*&head)/采用尾插法建立具有結(jié)點(diǎn)的單鏈表char ch;linklist *s,*r;head=new linklist;r=head;while(ch=getchar()!=*)s=new linklist;s-data=ch;r-next=s;r=s;r-next=NULL;/輸出單鏈表.hvoid print(linklist *head)linklist*p=head-next;while(p!=NULL)coutdatanext;coutnext; q=p-next; while(q!=NULL) r=q-next; q-next=p; p=q; q=r; head-next-next=NULL; head-next=p; 單鏈表結(jié)果截圖見下方實(shí)驗結(jié)果。順序表代碼：/順序表逆置主文件.cpp#include#include#include順序表結(jié)構(gòu)類型定義.h#include建立順序表.h#include輸出順序表.h#include順序表逆置.hvoid main()sequenlist*L;creat(L);print(L);invert(L);/調(diào)用順序表逆值的函數(shù)print(L);/順序表的結(jié)構(gòu)類型定義.htypedef char datatype;const int maxsize=1024;typedef struct datatype datamaxsize; int last;sequenlist;/建立順序表.hvoid creat(sequenlist*&L)L=new sequenlist;L-last=0;char ch;while(ch=getchar()!=*)L-dataL-last=ch;L-last+;/輸出順序表.hvoid print(sequenlist*L)for(int i=0;ilast;i+)coutdatai ;coutlast-1; while(idatai; L-datai=L-dataj; L-dataj=mid; i+;j-; 順序表實(shí)驗截圖見下方實(shí)驗結(jié)果。2 已知由不具有頭結(jié)點(diǎn)的單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（字母、數(shù)字和其他字符），試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。（文件夾：習(xí)題2）代碼：/分解單鏈表主程序文件.cpp#include#include#include單鏈表結(jié)構(gòu)類型定義.h#include建立單鏈表.h#include輸出單鏈表.h#include輸出循環(huán)鏈表.h#include在循環(huán)鏈表中插入.h#include分解單鏈表.hvoid main() linklist *head,*letter,*digit,*other; creat(head); print1(head); letter=new linklist; letter-next=letter; digit=new linklist; digit-next=digit; other=new linklist; other-next=other; resolve(head,letter,digit,other);/調(diào)用分解單鏈表的函數(shù) print2(letter); print2(digit); print2(other);/單鏈表結(jié)構(gòu)類型定義typedef char datatype;typedef struct node datatype data; struct node *next;linklist;void creat(linklist*&head)/建立單鏈表 datatype x; linklist *s,*r; head=new linklist; r=head; cinx; while(x!=$) s=new linklist; s-data=x; r-next=s; r=s; cinx; r-next=NULL;void print1(linklist*head)/輸出單鏈表 linklist *p=head-next; while(p!=NULL) coutdata; p=p-next; coutnext; while(p!=head) coutdata; p=p-next; coutnext!=h) q=q-next; q-next=p; p-next=h;/分解單鏈表.hvoid resolve(linklist* head,linklist* letter,linklist* digit,linklist* other)linklist* p = head-next,*t;head-next =NULL;while (p!=NULL)t = p; p=p-next;if (t-data =0 & t-data data =a & t-data data =A & t-data quelen=0；隊滿的條件：sq-quelen=m。（文件夾：習(xí)題3）/循環(huán)隊列入隊出隊的主程序文件.cpp#include#include#include#include循環(huán)隊列的結(jié)構(gòu)類型定義.h#include置空隊.h#include入隊.h#include出隊.hvoid main() qu *sq;datatype x, *p;int key;sq=new qu;setnull(sq);do coutkey;switch(key) case 1: coutx;enqueue(sq,x);break;case 2: p=dequeue(sq);if(p!=NULL) cout*pquelen=0) printf(隊列為空，請先進(jìn)行入隊操作n);return 0; else temp=(datatype*)malloc(sizeof(datatype); sq-quelen-; *temp=sq-sequ(sq-rear-sq-quelen+m)%m; coutquelen=m) printf(隊列已滿，請先進(jìn)行出隊操作n); else sq-quelen+; sq-rear=(sq-rear+1)%m; sq-sequsq-rear=x; coutrear=m-1;sq-quelen=0;實(shí)驗截圖見下方實(shí)驗結(jié)果。2. 設(shè)單鏈表中存放有n個字符，試編寫算法，判斷該字符串是否有中心對稱的關(guān)系，例如xyzzyx是中心對稱的字符串。（提示：將單鏈表中的一半字符先依次進(jìn)棧，然后依次出棧與單鏈表中的另一半字符進(jìn)行比較。）（文件夾：習(xí)題4）/判字符串中心對稱的主程序文件.cpp#include#include單鏈表順序棧結(jié)構(gòu)類型定義.h#include置棧空.h#include求單鏈表長度.h#include輸出單鏈表.h#include建立單鏈表.h#include順序棧入棧.h#include順序棧出棧.h#include判字符串是否中心對稱.h void main()linklist *head;stack *s;datatypestr80;cinstr;creat(head,str);printlink(head);setnull(s);if(symmetry(head,s) cout字符串str中心對稱n;else cout字符串strdata=*p;r-next=s; r=s;p+; r-next=NULL;/判斷字符是否中心對稱.hint symmetry(linklist*head,stack*s) int n=length(head)/2; linklist*p=head-next; datatype x; for(inti=0;idata); p=p-next; if(length(head)%2=1) p=p-next; while(p!=NULL) x=pop(s); if(x=p-data) p=p-next; else return 0; return 1; /求單鏈表長度.hint length(linklist*head) linklist *p=head-next;int n=0;while(p!=NULL) n+; p=p-next; return n;/輸出單鏈表.hvoidprintlink(linklist*head) linklist *p=head-next;while(p!=NULL) coutdata; p=p-next; couttop-;temp=s-elementss-top+1;return temp;/順序棧入棧.hvoid push(stack*s,datatype e)s-top+;s-elementss-top=e;/置?？?hvoidsetnull(stack *&s)s=new stack;s-top=-1;截圖見下方實(shí)驗結(jié)果。3、 實(shí)驗結(jié)果四、個人思路隊列是一個先進(jìn)先出的線性表，入隊時，先判斷隊列是否已滿，如果不滿將元素插入到隊尾，然后判斷rear是否指向sequm，如果是，指向隊尾指針rear+1，否者rear=sequ0，隊列內(nèi)元素個數(shù)quelen+1。出隊時頭指針front后移一位，如果front=sequm，front指向sequ0，否則front+，quelen-1，從而實(shí)現(xiàn)入隊與出隊的操作。 要判斷字符串是否中心對稱，首先獲取棧的長度N，將前N/2個元素（N為偶數(shù)）或前(N-1）/2個元素（N為奇數(shù)）順序壓入棧中，然后依次出棧（先進(jìn)后出），與另一半元素依次對應(yīng)比較，全為真則可判斷字符串中心對稱。 實(shí)驗三 數(shù)組一、實(shí)驗?zāi)康? 熟悉數(shù)組的結(jié)構(gòu)2 掌握矩陣的進(jìn)行運(yùn)算二、實(shí)驗代碼 若在矩陣Amn中存在一個元素Ai-1j-1，其滿足Ai-1j-1是第i行元素中最小值，且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點(diǎn)。用二維數(shù)組存儲矩陣Amn ，設(shè)計算法求出矩陣中所有馬鞍點(diǎn)。（文件夾：習(xí)題5）/找馬鞍點(diǎn)的主程序文件.cpp#include#include數(shù)組的結(jié)構(gòu)類型定義.h#include找馬鞍點(diǎn).husing namespace std;void main()array*pa=new array; int i, j; for (i=0;im;i+) for (j=0;jpa-Aij; minmax(pa);getchar();/數(shù)組的結(jié)構(gòu)類型定義.hconstint m=3;constint n=3;typedefstructint Amn;int maxm,minn;array;/找馬鞍點(diǎn).hvoidminmax(array*p) inti,j,have=0; for(i=0;imini=p-A0i; for(j=1;jAijmini)p-mini=p-Aij; for (j=0;jmaxj=p-A0j; for(i=1;iAijp-maxj) p-maxj=p-Aij; for(i=0;im;i+)for(j=0;jmini=p-maxj) printf(矩陣中存在馬鞍點(diǎn):n);printf(行號:%d,列號:%d,數(shù)值:%dn,i+1,j+1,p-Aij); have=1; if(!have) printf(矩陣中沒有馬鞍點(diǎn)！n); 三、實(shí)驗結(jié)果4、 個人思路 若稱元素為該矩陣的一個馬鞍點(diǎn)，即說明該元素是第i行元素中最小值，且又是第j列元素中最大值。用兩個循環(huán)遍歷所有元素，第一個循環(huán)遍歷行，第二個循環(huán)遍歷列，將Ai-1j-1與對應(yīng)行和列的每一個元素比較，如果第i行的某元素比Ai-1j-1小或第j列的某元素比Ai-1j-1大則跳出內(nèi)層循環(huán)，實(shí)現(xiàn)尋找馬鞍點(diǎn)的要求。實(shí)驗四 樹一、實(shí)驗?zāi)康? 熟悉二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)2 掌握二叉樹的建立、深度優(yōu)先遞歸遍歷等算法3 能夠利用遍歷算法實(shí)現(xiàn)一些應(yīng)用二、實(shí)驗代碼1 已知二叉樹采用二叉鏈表存儲結(jié)構(gòu)，編寫一個算法交換二叉樹所有左、右子樹的位置，即結(jié)點(diǎn)的左子樹變?yōu)榻Y(jié)點(diǎn)的右子樹，右子樹變?yōu)樽笞訕洹＃ㄎ募A：習(xí)題6）/交換左右子樹的主程序文件.cpp#include#include#include二叉鏈表的結(jié)構(gòu)類型定義.h#include二叉樹的建立.h#include二叉樹的輸出.h#include交換左右子樹.hvoid main()bitree * pb;/指針pb=creattree();/創(chuàng)建一棵樹,pb指向這棵樹的根節(jié)點(diǎn)preorder(pb);/打印這棵樹coutendl;swap(pb);/交換這棵樹的所有子樹preorder(pb);/打印這顆新樹coutdata=ch;s-lchild=NULL;s-rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;/二叉樹的輸出.hvoid preorder(bitree*p)if(p!=NULL)coutdata;if(p-lchild!=NULL|p-rchild!=NULL)coutlchild);if(p-rchild!=NULL)coutrchild);coutlchild;pb-lchild=pb-rchild;pb-rchild=t;swap(pb-lchild);swap(pb-rchild); 實(shí)驗運(yùn)行結(jié)果截圖見下方實(shí)驗結(jié)果。2 采用二叉鏈表結(jié)構(gòu)存儲一棵二叉樹，編寫一個算法刪除該二叉樹中數(shù)據(jù)值為x的結(jié)點(diǎn)及其子樹，并且輸出被刪除的子樹。（文件夾：習(xí)題7）/刪除二叉樹結(jié)點(diǎn)的主程序文件.cpp#include#include#include#include#include二叉鏈表的結(jié)構(gòu)類型定義.h#include二叉樹的建立.h#include二叉樹的輸出.h/#include刪除結(jié)點(diǎn)和子樹.hvoid main()bitree * root;/創(chuàng)建指針datatype x;/定義變量xCreateBiTree(root);/創(chuàng)建一顆二叉樹，使指針root指向這顆二叉樹的根節(jié)點(diǎn)preorder(root);/打印這顆二叉樹 PrintBiTree(root,2);coutx;/輸入一個字符存儲到變量x中root=delsubtree(root,x);/從指針root所指向的根節(jié)點(diǎn)開始在這顆二叉樹的所有節(jié)點(diǎn)中/尋找節(jié)點(diǎn)內(nèi)容與變量x內(nèi)容相同的節(jié)點(diǎn),若沒找到則不改變這顆樹/若找到這樣的節(jié)點(diǎn)，那么刪除一顆以找到節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹preorder(root);/打印變化之后的二叉樹coutdata=ch;s-lchild=NULL;s-rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;intCreateBiTree(bitree *&T) charch;scanf(%c,&ch);if (ch= ) T=NULL;else if (!(T=(bitree*)malloc(sizeof(bitree) exit(0); T-data = ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return 1;/二叉樹的輸出.hvoid preorder(bitree*p)if(p!=NULL)coutdata;if(p-lchild!=NULL|p-rchild!=NULL)coutlchild);if(p-rchild!=NULL)coutrchild);coutrchild,n+1);for (i=1;idata);PrintBiTree(T-lchild,n+1);/刪除節(jié)點(diǎn)及其子樹.hbitree*delsubtree(bitree*T,datatype x)if (T!=NULL)/