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

1、本科實(shí)驗(yàn)報(bào)告 課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)b 實(shí)驗(yàn)項(xiàng)目： 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 實(shí)驗(yàn)地點(diǎn)： 教室 專(zhuān)業(yè)班級(jí)： 軟件1331 學(xué)號(hào)：2013005976 學(xué)生姓名： 孫濤 指導(dǎo)教師： 楊崇艷 2014年 12月 16日實(shí)驗(yàn)一線性表一目的與要求 本次實(shí)習(xí)的主要目的是為了使學(xué)生熟練掌握線性表的基本操作在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，提高分析和解決問(wèn)題的能力。要求仔細(xì)閱讀并理解下列例題，上機(jī)通過(guò)，并觀察其結(jié)果，然后獨(dú)立完成后面的實(shí)習(xí)題。二例題 問(wèn)題描述 用鏈表形式存儲(chǔ)一個(gè)字符串，插入、刪除某個(gè)字符，最后按正序、逆序兩種方式輸出字符串。輸入初始字符串，插入位置，插入字符，刪除字符。輸出已建立鏈表（字符串），插入字

2、符后鏈表，刪除字符后鏈表，逆轉(zhuǎn)后鏈表。存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)算法的基本思想建立鏈表：當(dāng)讀入字符不是結(jié)束符時(shí)，給結(jié)點(diǎn)分配存儲(chǔ)空間，寫(xiě)數(shù)據(jù)域，將新結(jié)點(diǎn)插到表尾；插入字符：根據(jù)讀入的字符在鏈表中找插入位置，將新結(jié)點(diǎn)插入到該位置之前；刪除字符：根據(jù)讀入的刪除字符在鏈表中找到被刪結(jié)點(diǎn)后，將其從鏈表中刪除；鏈表逆轉(zhuǎn)：從鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始對(duì)所有結(jié)點(diǎn)處理，將每個(gè)結(jié)點(diǎn)的前驅(qū)變?yōu)樗暮罄^；打印鏈表：從鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始，依次打印各個(gè)結(jié)點(diǎn)的數(shù)據(jù)域。參考源程序#define null 0typedef struct node char a; struct node *link;node,*nodelink;vo

3、id readlink(nodelink head) nodelink p,q; char c; p=head; printf(input a linktable(a string):); scanf(%c,&c); if (c=n) printf(this string is empty。); while(c!=n) q=(nodelink)malloc(sizeof(node); q-a=c; p-link=q; p=q; scanf(%c,&c); p-link=null;void writelink(nodelink head) nodelink q; if (head-link=nu

4、ll) printf( this link is empty。n); for(q=head-link;q;q=q-link) printf(%c,q-a); printf(n); int insert(nodelink head,char k1,char k2) nodelink p,q; p=head-link; while(p-a!=k1&p) p=p-link; if(p) q=(nodelink)malloc(sizeof(node); q-a=k2; q-link=p-link; p-link=q; return 1; else printf(there is no %cn,k1);

5、 return 0;int delete(nodelink head,char k) nodelink p,q; q=head; p=head-link; while(p-a)!=k)&p) q=q-link; p=p-link; if(p) q-link=p-link; return 1; else printf(there is no %cn,k); return 0;void opside(nodelink head)nodelink p,q; p=head-link; while(p-link) q=p-link; p-link=q-link; q-link=head-link; he

6、ad-link=q; main() char k1,k2,k3; nodelink head; head=(nodelink)malloc(sizeof(node); head-link=null; readlink(head); if (head-link!=null) printf(build link is :); writelink(head); if (head-link!=null) printf(please input a char you want to insert after:); k1=getch(); printf(%cn,k1); printf(please inp

7、ut a char you want to insert:); k2=getch(); printf(%cn,k2); if (insert(head,k1,k2) printf(after %c insert %c,link is:,k1,k2); writelink(head); printf(please input a char you want to delete:); k3=getch(); printf(%cn,k3); if (delete(head,k3) printf(after delete %c,link is:,k3); writelink(head); if (he

8、ad-link!=null) printf(opsite result is :); opside(head); writelink(head); free(head); 運(yùn)行情況三實(shí)習(xí)題 1設(shè)順序表a中的數(shù)據(jù)元素遞增有序，試寫(xiě)一程序，將x插入到順序表的適當(dāng)位置上，使該表仍然有序。2用單鏈表ha 存儲(chǔ)多項(xiàng)式a（x ）=a0+a1x1+a2x2+anxn(其中ai為非零系數(shù))，用單鏈表hb 存儲(chǔ)多項(xiàng)式b（x ）=b0+b1x1+b2x2+bmxm(其中bj為非零系數(shù))，要求計(jì)算c（x ）= a（x ）+b（x ），結(jié)果存到單鏈表hc中。試寫(xiě)出程序。29includestdio.h #includ

9、e static int n;static int m;static int max;struct polynomial/多項(xiàng)式系數(shù)結(jié)構(gòu)體float data;struct polynomial* next;struct polynomial* creat_h(int k)/創(chuàng)建多項(xiàng)式系數(shù)的鏈表struct polynomial* l;struct polynomial* p; p=(struct polynomial*)malloc(sizeof(struct polynomial);l=p;float temp;int i;printf(請(qǐng)依次輸入系數(shù)(中間用空格隔開(kāi))：n);for(i=

10、0;idata=temp;if(i=k)p-next=null;break;p-next=(struct polynomial*)malloc(sizeof(struct polynomial);p=p-next;return l;struct polynomial* calculate(struct polynomial* pa,struct polynomial* pb)/計(jì)算兩個(gè)多項(xiàng)式相加struct polynomial* pc; struct polynomial* l;int i;max=n=m? n:m;pc=(struct polynomial*)malloc(sizeof(s

11、truct polynomial);l=pc;for(i=0;inext=null;break;pc-next=(struct polynomial*)malloc(sizeof(struct polynomial);pc=pc-next;pc=l;while(pa!=null&pb!=null)pc-data=pa-data+pb-data;pc=pc-next;pa=pa-next;pb=pb-next;if(pa=null)/pa的長(zhǎng)度小于pbwhile(pb!=null)pc-data=pb-data;pc=pc-next;pb=pb-next;else if(pb=null)/pb的

12、長(zhǎng)度小于pawhile(pa!=null)pc-data=pa-data;pc=pc-next;pa=pa-next;return l;int main() int i;struct polynomial *ha,*hb,*hc;printf(請(qǐng)輸入多項(xiàng)式a的最高次系n:n);scanf(%d,&n);ha=creat_h(n);printf(請(qǐng)輸入多項(xiàng)式b的最高次系m:n);scanf(%d,&m);hb=creat_h(m); hc=calculate(ha,hb);printf(系數(shù): 次數(shù):n);for(i=0;idata,i);if(i=max)break;hc=hc-next;re

13、turn 0;#i運(yùn)行情況 3設(shè)有n個(gè)人圍坐在一個(gè)圓桌周?chē)?，現(xiàn)從第s個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到第m的人出列，然后從出列的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到m的人又出列，如此重復(fù)，直到所有的人全部出列為止。josephus問(wèn)題是：對(duì)于任意給定的n，m，s，求出按出列次序得到的n個(gè)人員的順序表。#include stdio.h#include malloc.h#include conio.htypedef struct nodeint a;struct node *link;node,*nodelink;void make(nodelink head,int n)int i;nodelink p,q;p=head

14、;for(i=0;ia=i+1;p-link=q;q-link=head-link;p=p-link;/構(gòu)造循環(huán)鏈表void remake(nodelink head,nodelink link,int n,int m,int s)int i;nodelink p,q,r;p=head-link;q=p;for(i=1;ilink;if(p=head-link)for(i=1;ilink;r=link;dofor(i=1;ilink;q-link=p-link;p-link=null;r-link=p;r=r-link;p=q-link;while(p!=p-link);r-link=p;r-

15、link-link=null;/輪流出列void write(nodelink link,int n)int i;nodelink p;p=link-link;for(i=0;ilink)printf(%d ,p-a);/輸出按出列順序得到的順序表void main()loop:nodelink head,link;int m,n,s;head=(nodelink)malloc(sizeof(node);/保存初始順序link=(nodelink)malloc(sizeof(node);/保存出列順序printf(輸入總?cè)藬?shù)n:);scanf(%d,&n);make(head,n);print

16、f(輸入開(kāi)始的人s:);scanf(%d,&s);printf(輸入要數(shù)的數(shù)字m:);scanf(%d,&m);remake(head,link,n,m,s);write(link,n);printf(nn);goto loop;/達(dá)到循環(huán)使用的目的運(yùn)行情況實(shí)驗(yàn)二樹(shù)一目的與要求 熟悉樹(shù)的各種表示方法和各種遍歷方式，掌握有關(guān)算法的實(shí)現(xiàn)，了解樹(shù)在計(jì) 算機(jī)科學(xué)及其它工程技術(shù)中的應(yīng)用。二例題 問(wèn)題描述 任意給定一棵二叉樹(shù)。試設(shè)計(jì)一個(gè)程序，在計(jì)算機(jī)中構(gòu)造該二叉樹(shù)，并對(duì)它 進(jìn)行遍歷。輸入一棵二叉樹(shù)的結(jié)點(diǎn)若無(wú)子樹(shù)，則可將其子樹(shù)看作 “.”，輸入時(shí)，按照前序序列的順序輸入該結(jié)點(diǎn)的內(nèi)容。對(duì) 下圖，其輸入序列為a

17、bd.eh.cf.i.g.。輸出若為空二叉樹(shù)，則輸出：this is a empty binary tree。若二叉樹(shù)不空，按后序序列輸出，對(duì)上例，輸出結(jié)果為：dhebifgca。存儲(chǔ)結(jié)構(gòu)采用二叉鏈表存儲(chǔ)。算法的基本思想采用遞歸方法建立和遍歷二叉樹(shù)。首先建立二叉樹(shù)的根 結(jié)點(diǎn)，然后建立其左右子樹(shù)，直到空子樹(shù)為止。后序遍歷二叉樹(shù)時(shí)，先遍歷左子樹(shù)，后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。參考源程序#include#includestruct nodechar info; struct node *llink,*rlink; ;typedef struct node node;node *creat() cha

18、r x; node *p;scanf(%c,&x);printf(%c,x); if(x!=.) p=(node *)malloc(sizeof(node); p-info=x; p-llink=creat(); p-rlink=creat(); else p=null;return p;void run(node *t)if(t)run(t-llink); run(t-rlink); printf(%c,t- info); main() node *t; printf(please input a tree:n);t=creat();printf(n); if(!t) printf(this

19、 is a empty binary tree.); else printf(the result of post travese is:n ); run(t); printf(n);return 0;三實(shí)習(xí)題 1 編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。#include#includestruct bitree char data; struct bitree *lchild; struct bitree *rchild; struct bitree* creatbitree() char x; struct bitree* p; scanf(%c,&x); if(x!=.) p=(str

20、uct bitree*)malloc(sizeof(struct bitree); p-data=x; p-lchild=creatbitree(); p-rchild=creatbitree(); else p=null; return p;int leafnum(struct bitree *t) if(!t) return 0; else if(!t-lchild&!t-rchild) return 1; else return leafnum(t-lchild)+leafnum(t-rchild); int main() int num; struct bitree* t; print

21、f(請(qǐng)按先序序列輸入二叉樹(shù)n); t=creatbitree(); while(t=null) printf(empoty,again:n); t=creatbitree(); num=leafnum(t); printf(n二叉樹(shù)葉子結(jié)點(diǎn)為:%dn,num); return 0; 2 編寫(xiě)遞歸算法，在二叉樹(shù)中求位于先序序列中第k個(gè)位置的結(jié)點(diǎn)。#include#include#includestatic int m=0;static int n=0;int k;struct bitree char data; struct bitree* lchild; struct bitree* rchi

22、ld;struct bitree* creatbitree() char x; struct bitree* p; scanf(%c,&x); if(x!=.) p=(struct bitree*)malloc(sizeof(struct bitree); p-data=x; m+; p-lchild=creatbitree(); p-rchild=creatbitree(); else p=null; return p;void search(struct bitree* t) if(t) n+; if(n=k) printf(位于先序序列第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)為：%cn,t-data); sea

23、rch(t-lchild); search(t-rchild); int main() struct bitree* t; char temp; printf(請(qǐng)按先序序列輸入二叉樹(shù)（如：ab.表示a為根結(jié)點(diǎn)，b為左子樹(shù)的二叉樹(shù)）n); t=creatbitree(); while(t=null) printf(你輸入的對(duì)叉樹(shù)為空，請(qǐng)重新輸入：n); temp=getchar(); t=creatbitree(); printf(請(qǐng)輸入k的值：n); scanf(%d,&k); while(km) printf(你輸入的k值不合理，請(qǐng)重新輸入：n); scanf(%d,&k); search(

24、t); system(pause); return 0;3 將上述例題用非遞歸程序?qū)崿F(xiàn)。（1）#include#includestatic int m=0;struct bitree char data; struct bitree* lchild; struct bitree* rchild;struct statck struct bitree* *base; struct bitree* *top; ;void initstatck(struct statck &p) p.base=(struct bitree* *)malloc(m*sizeof(struct bitree*); p.

25、top=p.base; void push(struct statck &s,struct bitree* e) *(s.top)+=e;void pop(struct statck &s,struct bitree* &e) e=*-s.top; int statckempty(struct statck s) if(s.top=s.base) return 1; else return 0; struct bitree* creatbitree() char x; struct bitree* p; scanf(%c,&x); if(x!=.) p=(struct bitree*)mall

26、oc(sizeof(struct bitree); p-data=x; m+; p-lchild=creatbitree(); p-rchild=creatbitree(); else p=null; return p;int leafnum(struct bitree* t) int i=0; int flag; struct statck l; initstatck(l); while(t|!statckempty(l) if(t) push(l,t); t=t-lchild; if(t=null) flag=1; else pop(l,t); t=t-rchild; if(t=null&

27、flag=1) i+; flag=0; return i;int main() int num; char temp; struct bitree* t; printf(請(qǐng)按先序序列輸入二叉樹(shù)（如：ab.表示a為根結(jié)點(diǎn)，b為左子樹(shù)的二叉樹(shù)）n); t=creatbitree(); while(t=null) printf(你輸入的對(duì)叉樹(shù)為空，請(qǐng)重新輸入：n); temp=getchar(); t=creatbitree(); num=leafnum(t); printf(n你所輸入的二叉樹(shù)的葉子個(gè)數(shù)為：%dn,num); system(pause); return 0;2、#include#i

28、ncludestatic int m=0;static int n=0;int k;struct bitree char data; struct bitree* lchild; struct bitree* rchild;struct statck struct bitree* *base; struct bitree* *top; ;void initstatck(struct statck &p) p.base=(struct bitree* *)malloc(m*sizeof(struct bitree*); p.top=p.base; void push(struct statck

29、&s,struct bitree* e) *(s.top)+=e;void pop(struct statck &s,struct bitree* &e) e=*-s.top; int statckempty(struct statck s) if(s.top=s.base) return 1; else return 0; struct bitree* creatbitree() char x; struct bitree* p; scanf(%c,&x); if(x!=.) p=(struct bitree*)malloc(sizeof(struct bitree); p-data=x;

30、m+; p-lchild=creatbitree(); p-rchild=creatbitree(); else p=null; return p;void search(struct bitree* t) struct statck l; initstatck(l); while(t|!statckempty(l) if(t) n+; if(n=k) printf(位于先序序列第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)為：%cn,t-data); push(l,t); t=t-lchild; else pop(l,t); t=t-rchild; int main() struct bitree* t; char te

31、mp; printf(請(qǐng)按先序序列輸入二叉樹(shù)（如：ab.表示a為根結(jié)點(diǎn)，b為左子樹(shù)的二叉樹(shù)）n); t=creatbitree(); while(t=null) printf(你輸入的對(duì)叉樹(shù)為空，請(qǐng)重新輸入：n); temp=getchar(); t=creatbitree(); printf(請(qǐng)輸入k的值：n); scanf(%d,&k); while(km) printf(你輸入的k值不合理，請(qǐng)重新輸入：n); scanf(%d,&k); search(t); system(pause); return 0;實(shí)驗(yàn)三圖一目的與要求 熟悉圖的存儲(chǔ)結(jié)構(gòu)，掌握有關(guān)算法的實(shí)現(xiàn)，了解圖在計(jì)算機(jī)科學(xué)及其

32、他工程技術(shù)中的應(yīng)用。二例題 問(wèn)題描述給定一個(gè)圖，設(shè)計(jì)一個(gè)程序，找出一條從某一頂點(diǎn)a到另一頂點(diǎn)b邊數(shù)最少的一條路徑。輸入圖的頂點(diǎn)個(gè)數(shù)n，圖中頂點(diǎn)之間的關(guān)系及要找的路徑的起點(diǎn)a和終點(diǎn)b。輸出若a到b無(wú)路徑，則輸出“there is no path”，否則輸出a到b路徑上各頂點(diǎn)。存儲(chǔ)結(jié)構(gòu)圖采用鄰接矩陣的方式存儲(chǔ)。 算法的基本思想采用廣度優(yōu)先搜索的方法，從頂點(diǎn)a開(kāi)始，依次訪問(wèn)與a鄰接的頂點(diǎn)va1,va2,.,vak, 訪問(wèn)遍之后,若沒(méi)有訪問(wèn)b，則繼續(xù)訪問(wèn)與va1鄰接的頂點(diǎn)va11,va12,.,va1m，再訪問(wèn)與va2鄰接頂點(diǎn).，如此下去，直至找到b，最先到達(dá)b點(diǎn)的路徑，一定是邊數(shù)最少的路徑。實(shí)現(xiàn)時(shí)采

33、用隊(duì)列記錄被訪問(wèn)過(guò)的頂點(diǎn)。每次訪問(wèn)與隊(duì)頭頂點(diǎn)相鄰接的頂點(diǎn)，然后將隊(duì)頭頂點(diǎn)從隊(duì)列中刪去。若隊(duì)空，則說(shuō)明到不存在通路。在訪問(wèn)頂點(diǎn)過(guò)程中，每次把當(dāng)前頂點(diǎn)的序號(hào)作為與其鄰接的未訪問(wèn)的頂點(diǎn)的前驅(qū)頂點(diǎn)記錄下來(lái)，以便輸出時(shí)回溯。例題參考源程序#includeint number;typedef struct int q20; int f,r; queue;int nodelist2020;queue q;int z20;int a,b,n,i,j,x,y;int finished;void enq(queue *q,int x) q-qq-r=x; if(q-r=19) q-r=0; else q-r+;

34、if(q-r=q-f) printf(overflow!n);front(queue *q) if(q-r=q-f) printf(underflow!n); else return(q-qq-f);void deq(queue *q) if(q-r=q-f) printf(underflow!n); else if(q-f=19) q-f=0; else q-f+; int qempty(queue q) if(q.f=q.r) return 1; else return 0;void readgraph() printf(nplease input n:); scanf(%d,&n); p

35、rintf(please input nodelistij:n); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&nodelistij); printf(n); printf(list-link is bulitn); for(i=1;i=n;i+) for(j=1;j=n;j+) printf(%3d,nodelistij); printf(n); void shortest(int a,int b) if(a=b) nodelistaa=2; else enq(&q,a); nodelistaa=2; finished=0; while(!qempty

36、(q)&!finished) a=front(&q); deq(&q); j=1; while(j=n)&!finished) if(nodelistaj=1)&(nodelistjj!=2) enq(&q,j); nodelistjj=2; zj=a; if(j=b)/*&(nodelistaj=1)*/ finished=1; if(!finished) j+; if (!finished) printf(there is no path.); void writepath(int a,int b) i=b; while(i!=a) printf(%d - ,i); i=zi; printf(%d,a);main() readgraph(); printf(please input a:); scanf(%d,&a); printf(please input b:); scanf(%d,&b); q.f=0; q.r=0; shortest(a,b); if (finished) wr