數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告

1、XIDIAN UNIVERSITY數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告學(xué)院：電子工程學(xué)院專業(yè)：信息對抗技術(shù) 姓名:學(xué)號：教師：饒鮮日期：目錄實(shí)驗(yàn)一 線性表 - 4 -一、實(shí)驗(yàn)?zāi)康?-.4. -二、實(shí)驗(yàn)代碼 -.4. -三、實(shí)驗(yàn)結(jié)果 -.1. 1 -四、個人思路 -.1. 2 -實(shí)驗(yàn)二 棧和隊(duì)列 - 12 -一、實(shí)驗(yàn)?zāi)康?-.1. 2 -二、實(shí)驗(yàn)代碼 -.1. 3 -三、實(shí)驗(yàn)結(jié)果 -.2. 1 -四、個人思路 -.2. 2 -實(shí)驗(yàn)三 數(shù)組 - 22 -一、實(shí)驗(yàn)?zāi)康?-.2. 2 -二、實(shí)驗(yàn)代碼 -.2. 3 -三、實(shí)驗(yàn)結(jié)果 -.2. 5 -四、個人思路 -.2. 5 -實(shí)驗(yàn)四 樹 - 26 -一、實(shí)驗(yàn)?zāi)康?-.

2、2. 6 -二、實(shí)驗(yàn)代碼 -.2. 6 -三、實(shí)驗(yàn)結(jié)果 -.3. 5 -四、個人思路 -.3. 5 -實(shí)驗(yàn)一 線性表一、實(shí)驗(yàn)?zāi)康? 熟悉線性表的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)2 掌握線性表的基本運(yùn)算3 能夠利用線性表的基本運(yùn)算完成線性表應(yīng)用的運(yùn)算二、實(shí)驗(yàn)代碼1.設(shè)有一個線性表 E=ei, e2,，en-i, en，設(shè)計(jì)一個算法，將線性表逆置，即使元素排列 次序顛倒過來，成為逆線性表E = en, en-i ,，e2 , ei ，要求逆線性表占用原線性表空間，并且用順序表和單鏈表兩種方法表示，分別用兩個程序來完成。(文件夾：習(xí)題i)代碼：單鏈表代碼：pp#include#include#include 單鏈

3、表結(jié)構(gòu)類型定義 .h#include 建立單鏈表 .h#include 輸出單鏈表 .h#include 單鏈表逆置 .hvoid main()linklist*head;creat(head);print(head);invert(head);typedef char datatype;typedef struct nodedatatype data;struct node *next;linklist;void creat(linklist*&head)void print(linklist *head)linklist*p=head-next;while(p!=NULL)coutdata

4、next;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í)驗(yàn)結(jié)果。順序表代碼：pp#include#include#include 順序表結(jié)構(gòu)類型定義 .h#include 建立順序表 .h#include 輸出順序表 .h#include 順序表逆置 .hvoid main()sequenlist*L;creat(L);print(L);invert(L);typedef char datatype;const int maxsize=10

5、24;typedef struct datatype datamaxsize;int last;sequenlist;void creat(sequenlist*&L)L=new sequenlist;L-last=0;char ch;while(ch=getchar()!=*)L-dataL-last=ch;L-last+;void print(sequenlist*L)for(int i=0;ilast;i+) coutdatai coutlast-1;while(idatai;L-datai=L-dataj;L-dataj=mid;i+;j-;順序表實(shí)驗(yàn)截圖見下方實(shí)驗(yàn)結(jié)果。2 已知由不具

6、有頭結(jié)點(diǎn)的單鏈表表示的線性表中， 含有三類字符的數(shù)據(jù)元素 （字母、 數(shù)字和其他字符），試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。（文件夾：習(xí)題2）代碼：pp#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)

7、;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);void insert(linklist*h,linklist*p) linklist *q=h;while(q-next!=h) q=q-next; q-next=p;p-next=h;void resolve(linklist* head,linklist* letter,li

8、nklist* 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 ；隊(duì)滿的條件： sq-quelen=m 。(文件夾：習(xí)題 3)pp#include#include#include#include 循環(huán)隊(duì)列的結(jié)構(gòu)類型定義 .h#include 置空隊(duì) .h#include 入隊(duì) .h#include 出隊(duì) .hvoid m

9、ain() 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( 隊(duì)列為空，請先進(jìn)行入隊(duì)操作 n);return 0;elsetemp=(datatype*)malloc(sizeof(datatype);sq-quelen-;*temp=sq-sequ(sq-rear-sq-quelen+m)%m;coutquelen

10、=m)n);printf( 隊(duì)列已滿，請先進(jìn)行出隊(duì)操作 else sq-quelen+; sq-rear=(sq-rear+1)%m; sq-sequsq-rear=x; coutrear=m-1;sq-quelen=0;實(shí)驗(yàn)截圖見下方實(shí)驗(yàn)結(jié)果。2. 設(shè)單鏈表中存放有 n 個字符，試編寫算法，判斷該字符串是否有中心對稱的關(guān)系，例如 xyzzyx 是中心對稱的字符串。 （提示：將單鏈表中的一半字符先依次進(jìn)棧，然后依次出棧與 單鏈表中的另一半字符進(jìn)行比較。）（文件夾：習(xí)題4）pp#include#include 單鏈表順序棧結(jié)構(gòu)類型定義 .h#include 置?？?.h#include 求單鏈表

11、長度 .h#include 輸出單鏈表 .h#include 建立單鏈表 .h#include 順序棧入棧 .h#include 順序棧出棧 .h#include 判字符串是否中心對稱 .hvoid 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; int symmet

12、ry(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;int length(linklist*head) linklist *p=head-next;int n=0;p=p-next; while(p!=NULL) n+; return

13、n;voidprintlink(linklist*head) linklist *p=head-next; while(p!=NULL) coutdata; p=p-next;couttop-;temp=s-elementss-top+1;return temp;void push(stack*s,datatype e)s-top+; s-elementss-top=e;voidsetnull(stack *&s)s=new stack;s-top=-1;截圖見下方實(shí)驗(yàn)結(jié)果。三、實(shí)驗(yàn)結(jié)果謂鋰文鹽I詞蜀SXDwbu航僵坯限列人叭出的主隍序交比GFEnter the Pta：l入隊(duì)成功f1.Ent

14、&r QueueEnter the Data：2入別成珈1 iEntar Qiwue 2 De leteEntei* the AtA= 3AEWjt1iUnter Queue 2-Delete Enter the Data：3人隊(duì)咸咖2-DelcteQueueQiiahaQueuel.Quitsl!. Enter QuLeuie2 _DeleteU ue ue-1 .(iuit ：1Enter the Jata： 人隊(duì)咸咖11.Enter Queue2_DeleteQue lie-i.Quit：lEnter the Data：1入隊(duì)成功！1 a En tBi* Queue2.DeleteQue

15、 li e-1.Quit =1Eriitav t：hio D-a.ta1隊(duì)列己滿，請先進(jìn)行出隊(duì)撓作1 HEnit&r ueue 出隊(duì)成咖11hEnter QueueZ.DeleteQueue1.Quit Z2 .Da lateQueue-1.Quit：2岀隊(duì)成咖-1.Ent&r QueuB2 .DaleteQueue-1.Quit：2岀隊(duì)咸咖1. En tor Quotio2-DelotoQuo no-1.Quit?2出隊(duì)成咖J1.Ent&r Queue2.De let*Queue-丄.Qult：E出隊(duì)成卯11.Enter Queuie 出Ik成珈2 .DeleteQueue-1.4uit=2

16、i . En tri* Queue2 _DeleteQue ue-1.Quit:21臥列為空諳先進(jìn)行入秋攜作239S763了符$2398?6護(hù)不是申心對稱|TrE 3； airij/ key t o con I Iriue四、個人思路隊(duì)列是一個先進(jìn)先出的線性表，入隊(duì)時，先判斷隊(duì)列是否已滿，如果不滿將元素插入到隊(duì)尾，然后判斷rear是否指向sequm,如果是，指向隊(duì)尾指針rear+1，否者rear=sequO，隊(duì)列內(nèi)元素個數(shù)quelen+1。出隊(duì)時頭指針front后移一位，如果 front=sequm， front指向sequ0，否則front+，quelen-1，從而實(shí)現(xiàn)入隊(duì)與出隊(duì)的操作。要判

17、斷字符串是否中心對稱，首先獲取棧的長度N，將前N/2個元素（N為偶數(shù)）或前（N-1） /2個元素（N為奇數(shù)）順序壓入棧中，然后依次出棧（先進(jìn)后出），與另一半元素依 次對應(yīng)比較，全為真則可判斷字符串中心對稱。實(shí)驗(yàn)三數(shù)組一、實(shí)驗(yàn)?zāi)康? .熟悉數(shù)組的結(jié)構(gòu)2.掌握矩陣的進(jìn)行運(yùn)算、實(shí)驗(yàn)代碼且又xn ，若在矩陣Amxn中存在一個元素 Ai-1j-1,其滿足Ai-1j-1是第i行元素中最小值, 是第 j 列元素中最大值，則稱此元素為該矩陣的一個馬鞍點(diǎn)。用二維數(shù)組存儲矩陣 設(shè)計(jì)算法求出矩陣中所有馬鞍點(diǎn)。（文件夾：習(xí)題5）pp#include#include 數(shù)組的結(jié)構(gòu)類型定義 .h#include 找馬鞍點(diǎn)

18、.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();constint m=3;constint n=3;typedefstructint Amn;int maxm,minn;array;voidminmax(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-

19、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í)驗(yàn)結(jié)果四、個人思路若稱元素為該矩陣的一個馬鞍點(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)

20、層循環(huán)，實(shí)現(xiàn)尋找馬鞍點(diǎn)的要求。實(shí)驗(yàn)四 樹一、實(shí)驗(yàn)?zāi)康? 熟悉二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)2 掌握二叉樹的建立、深度優(yōu)先遞歸遍歷等算法3 能夠利用遍歷算法實(shí)現(xiàn)一些應(yīng)用二、實(shí)驗(yàn)代碼右子樹的位6)1 已知二叉樹采用二叉鏈表存儲結(jié)構(gòu)， 編寫一個算法交換二叉樹所有左、 置，即結(jié)點(diǎn)的左子樹變?yōu)榻Y(jié)點(diǎn)的右子樹，右子樹變?yōu)樽笞訕洹?文件夾：習(xí)題pp#include#include#include 二叉鏈表的結(jié)構(gòu)類型定義 .h#include 二叉樹的建立 .h#include 二叉樹的輸出 .h#include 交換左右子樹 .hvoid main()bitree * pb;constintmaxsize=1024;t

21、ypedef char datatype;typedefstruct nodedatatype data; struct node *lchild,*rchild;bitree;bitree*creattree()charch;bitree*Qmaxsize;intfront,rear;bitree*root,*s;root=NULL;front=1;rear=0;while(ch=getchar()!=#)s=NULL;if(ch!=)s=new bitree;s-data=ch;s-lchild=NULL; s-rchild=NULL;rear+;Qrear=s;if(rear=1)roo

22、t=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;void 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);x的結(jié)實(shí)驗(yàn)運(yùn)行

23、結(jié)果截圖見下方實(shí)驗(yàn)結(jié)果。2采用二叉鏈表結(jié)構(gòu)存儲一棵二叉樹， 編寫一個算法刪除該二叉樹中數(shù)據(jù)值為點(diǎn)及其子樹，并且輸出被刪除的子樹。(文件夾：習(xí)題7)pp#include#include#include#include #include 二叉鏈表的結(jié)構(gòu)類型定義 .h#include 二叉樹的建立 .h #include 二叉樹的輸出 .hIIvoid main()bitree * root; constintmaxsize=1024; typedef char datatype; typedefstruct node datatype data;struct node *lchild,*rchil

24、d; bitree;bitree*creattree()datatypech; bitree*Qmaxsize; intfront,rear; bitree*root,*s;root=NULL; front=1;rear=0;while(ch=getchar()!=$)s=NULL;if(ch!=)s=new bitree;s-data=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

25、(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;void 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);bitree*delsubtree(bitree*T,datatype x)if (T!=NULL)/ 如果根節(jié)點(diǎn)不為空if (T-data=x)/ 如果根節(jié)點(diǎn)為要刪除的節(jié)點(diǎn)de