數據結構上機實驗報告 學 院：電子工程學院 專 業：信息對抗技術 姓 名： 學 號： 教 師：饒 鮮 日 期：目 錄實驗一 線性表- 2 -一、實驗目的- 2 -二、實驗代碼- 2 -三、實驗結果- 8 -四、個人思路- 9 -實驗二 棧和隊列- 9 -一、實驗目的- 9 -二、實驗代碼- 10 -三、實驗結果- 15 -四、個人思路- 16 -實驗三 數組- 16 -一、實驗目的- 16 -二、實驗代碼- 16 -三、實驗結果- 18 -四、個人思路- 18 -實驗四 樹- 18 -一、實驗目的- 18 -二、實驗代碼- 19 -三、實驗結果- 24 -四、個人思路- 25 - 40 -實驗一 線性表一、實驗目的1 熟悉線性表的順序和鏈式存儲結構2 掌握線性表的基本運算3 能夠利用線性表的基本運算完成線性表應用的運算二、實驗代碼1 設有一個線性表E=e1, e2, , en-1, en，設計一個算法，將線性表逆置，即使元素排列次序顛倒過來，成為逆線性表E= en, en-1 , , e2 , e1 ，要求逆線性表占用原線性表空間，并且用順序表和單鏈表兩種方法表示，分別用兩個程序來完成。（文件夾：習題1）代碼：單鏈表代碼：/單鏈表逆置主文件.cpp#include#include#include單鏈表結構類型定義.h#include建立單鏈表.h#include輸出單鏈表.h#include單鏈表逆置.hvoid main()linklist*head;creat(head);print(head);invert(head);/調用單鏈表逆置的函數print(head);/單鏈表結構類型定義.htypedef char datatype;typedef struct nodedatatype data;struct node *next;linklist;/建立單鏈表.hvoid creat(linklist*&head)/采用尾插法建立具有結點的單鏈表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; 單鏈表結果截圖見下方實驗結果。順序表代碼：/順序表逆置主文件.cpp#include#include#include順序表結構類型定義.h#include建立順序表.h#include輸出順序表.h#include順序表逆置.hvoid main()sequenlist*L;creat(L);print(L);invert(L);/調用順序表逆值的函數print(L);/順序表的結構類型定義.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-; 順序表實驗截圖見下方實驗結果。2 已知由不具有頭結點的單鏈表表示的線性表中，含有三類字符的數據元素（字母、數字和其他字符），試編寫算法構造三個以循環鏈表表示的線性表，使每個表中只含有同一類的字符，且利用原表中的結點空間，頭結點可另辟空間。（文件夾：習題2）代碼：/分解單鏈表主程序文件.cpp#include#include#include單鏈表結構類型定義.h#include建立單鏈表.h#include輸出單鏈表.h#include輸出循環鏈表.h#include在循環鏈表中插入.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);/調用分解單鏈表的函數 print2(letter); print2(digit); print2(other);/單鏈表結構類型定義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。（文件夾：習題3）/循環隊列入隊出隊的主程序文件.cpp#include#include#include#include循環隊列的結構類型定義.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(隊列為空，請先進行入隊操作n);return 0; else temp=(datatype*)malloc(sizeof(datatype); sq-quelen-; *temp=sq-sequ(sq-rear-sq-quelen+m)%m; coutquelen=m) printf(隊列已滿，請先進行出隊操作n); else sq-quelen+; sq-rear=(sq-rear+1)%m; sq-sequsq-rear=x; coutrear=m-1;sq-quelen=0;實驗截圖見下方實驗結果。2. 設單鏈表中存放有n個字符，試編寫算法，判斷該字符串是否有中心對稱的關系，例如xyzzyx是中心對稱的字符串。（提示：將單鏈表中的一半字符先依次進棧，然后依次出棧與單鏈表中的另一半字符進行比較。）（文件夾：習題4）/判字符串中心對稱的主程序文件.cpp#include#include單鏈表順序棧結構類型定義.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;截圖見下方實驗結果。3、 實驗結果四、個人思路隊列是一個先進先出的線性表，入隊時，先判斷隊列是否已滿，如果不滿將元素插入到隊尾，然后判斷rear是否指向sequm，如果是，指向隊尾指針rear+1，否者rear=sequ0，隊列內元素個數quelen+1。出隊時頭指針front后移一位，如果front=sequm，front指向sequ0，否則front+，quelen-1，從而實現入隊與出隊的操作。 要判斷字符串是否中心對稱，首先獲取棧的長度N，將前N/2個元素（N為偶數）或前(N-1）/2個元素（N為奇數）順序壓入棧中，然后依次出棧（先進后出），與另一半元素依次對應比較，全為真則可判斷字符串中心對稱。 實驗三 數組一、實驗目的1 熟悉數組的結構2 掌握矩陣的進行運算二、實驗代碼 若在矩陣Amn中存在一個元素Ai-1j-1，其滿足Ai-1j-1是第i行元素中最小值，且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。用二維數組存儲矩陣Amn ，設計算法求出矩陣中所有馬鞍點。（文件夾：習題5）/找馬鞍點的主程序文件.cpp#include#include數組的結構類型定義.h#include找馬鞍點.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();/數組的結構類型定義.hconstint m=3;constint n=3;typedefstructint Amn;int maxm,minn;array;/找馬鞍點.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(矩陣中存在馬鞍點:n);printf(行號:%d,列號:%d,數值:%dn,i+1,j+1,p-Aij); have=1; if(!have) printf(矩陣中沒有馬鞍點！n); 三、實驗結果4、 個人思路 若稱元素為該矩陣的一個馬鞍點，即說明該元素是第i行元素中最小值，且又是第j列元素中最大值。用兩個循環遍歷所有元素，第一個循環遍歷行，第二個循環遍歷列，將Ai-1j-1與對應行和列的每一個元素比較，如果第i行的某元素比Ai-1j-1小或第j列的某元素比Ai-1j-1大則跳出內層循環，實現尋找馬鞍點的要求。實驗四 樹一、實驗目的1 熟悉二叉樹的鏈式存儲結構2 掌握二叉樹的建立、深度優先遞歸遍歷等算法3 能夠利用遍歷算法實現一些應用二、實驗代碼1 已知二叉樹采用二叉鏈表存儲結構，編寫一個算法交換二叉樹所有左、右子樹的位置，即結點的左子樹變為結點的右子樹，右子樹變為左子樹。（文件夾：習題6）/交換左右子樹的主程序文件.cpp#include#include#include二叉鏈表的結構類型定義.h#include二叉樹的建立.h#include二叉樹的輸出.h#include交換左右子樹.hvoid main()bitree * pb;/指針pb=creattree();/創建一棵樹,pb指向這棵樹的根節點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); 實驗運行結果截圖見下方實驗結果。2 采用二叉鏈表結構存儲一棵二叉樹，編寫一個算法刪除該二叉樹中數據值為x的結點及其子樹，并且輸出被刪除的子樹。（文件夾：習題7）/刪除二叉樹結點的主程序文件.cpp#include#include#include#include#include二叉鏈表的結構類型定義.h#include二叉樹的建立.h#include二叉樹的輸出.h/#include刪除結點和子樹.hvoid main()bitree * root;/創建指針datatype x;/定義變量xCreateBiTree(root);/創建一顆二叉樹，使指針root指向這顆二叉樹的根節點preorder(root);/打印這顆二叉樹 PrintBiTree(root,2);coutx;/輸入一個字符存儲到變量x中root=delsubtree(root,x);/從指針root所指向的根節點開始在這顆二叉樹的所有節點中/尋找節點內容與變量x內容相同的節點,若沒找到則不改變這顆樹/若找到這樣的節點，那么刪除一顆以找到節點為根節點的子樹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);/刪除節點及其子樹.hbitree*delsubtree(bitree*T,datatype x)if (T!=NULL)/