數(shù)據(jù)結構實驗報告

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

2、符后鏈表，刪除字符后鏈表，逆轉(zhuǎn)后鏈表。存儲結構采用鏈式存儲結構算法的基本思想建立鏈表：當讀入字符不是結束符時，給結點分配存儲空間，寫數(shù)據(jù)域，將新結點插到表尾；插入字符：根據(jù)讀入的字符在鏈表中找插入位置，將新結點插入到該位置之前；刪除字符：根據(jù)讀入的刪除字符在鏈表中找到被刪結點后，將其從鏈表中刪除；鏈表逆轉(zhuǎn)：從鏈表的第一個結點開始對所有結點處理，將每個結點的前驅(qū)變?yōu)樗暮罄^；打印鏈表：從鏈表的第一個結點開始，依次打印各個結點的數(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); 運行情況三實習題 1設順序表a中的數(shù)據(jù)元素遞增有序，試寫一程序，將x插入到順序表的適當位置上，使該表仍然有序。2用單鏈表ha 存儲多項式a（x ）=a0+a1x1+a2x2+anxn(其中ai為非零系數(shù))，用單鏈表hb 存儲多項式b（x ）=b0+b1x1+b2x2+bmxm(其中bj為非零系數(shù))，要求計算c（x ）= a（x ）+b（x ），結果存到單鏈表hc中。試寫出程序。29includestdio.h #includ

9、e static int n;static int m;static int max;struct polynomial/多項式系數(shù)結構體float data;struct polynomial* next;struct polynomial* creat_h(int k)/創(chuàng)建多項式系數(shù)的鏈表struct polynomial* l;struct polynomial* p; p=(struct polynomial*)malloc(sizeof(struct polynomial);l=p;float temp;int i;printf(請依次輸入系數(shù)(中間用空格隔開)：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)/計算兩個多項式相加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的長度小于pbwhile(pb!=null)pc-data=pb-data;pc=pc-next;pb=pb-next;else if(pb=null)/pb的

12、長度小于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(請輸入多項式a的最高次系n:n);scanf(%d,&n);ha=creat_h(n);printf(請輸入多項式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運行情況 3設有n個人圍坐在一個圓桌周圍，現(xiàn)從第s個人開始報數(shù)，數(shù)到第m的人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到m的人又出列，如此重復，直到所有的人全部出列為止。josephus問題是：對于任意給定的n，m，s，求出按出列次序得到的n個人員的順序表。#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;/構造循環(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(輸入開始的人s:);scanf(%d,&s);printf(輸入要數(shù)的數(shù)字m:);scanf(%d,&m);remake(head,link,n,m,s);write(link,n);printf(nn);goto loop;/達到循環(huán)使用的目的運行情況實驗二樹一目的與要求 熟悉樹的各種表示方法和各種遍歷方式，掌握有關算法的實現(xiàn)，了解樹在計 算機科學及其它工程技術中的應用。二例題 問題描述 任意給定一棵二叉樹。試設計一個程序，在計算機中構造該二叉樹，并對它 進行遍歷。輸入一棵二叉樹的結點若無子樹，則可將其子樹看作 “.”，輸入時，按照前序序列的順序輸入該結點的內(nèi)容。對 下圖，其輸入序列為a

17、bd.eh.cf.i.g.。輸出若為空二叉樹，則輸出：this is a empty binary tree。若二叉樹不空，按后序序列輸出，對上例，輸出結果為：dhebifgca。存儲結構采用二叉鏈表存儲。算法的基本思想采用遞歸方法建立和遍歷二叉樹。首先建立二叉樹的根 結點，然后建立其左右子樹，直到空子樹為止。后序遍歷二叉樹時，先遍歷左子樹，后遍歷右子樹，最后訪問根結點。參考源程序#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;三實習題 1 編寫遞歸算法，計算二叉樹中葉子結點的數(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(請按先序序列輸入二叉樹n); t=creatbitree(); while(t=null) printf(empoty,again:n); t=creatbitree(); num=leafnum(t); printf(n二叉樹葉子結點為:%dn,num); return 0; 2 編寫遞歸算法，在二叉樹中求位于先序序列中第k個位置的結點。#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個結點的數(shù)據(jù)為：%cn,t-data); sea

23、rch(t-lchild); search(t-rchild); int main() struct bitree* t; char temp; printf(請按先序序列輸入二叉樹（如：ab.表示a為根結點，b為左子樹的二叉樹）n); t=creatbitree(); while(t=null) printf(你輸入的對叉樹為空，請重新輸入：n); temp=getchar(); t=creatbitree(); printf(請輸入k的值：n); scanf(%d,&k); while(km) printf(你輸入的k值不合理，請重新輸入：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(請按先序序列輸入二叉樹（如：ab.表示a為根結點，b為左子樹的二叉樹）n); t=creatbitree(); while(t=null) printf(你輸入的對叉樹為空，請重新輸入：n); temp=getchar(); t=creatbitree(); num=leafnum(t); printf(n你所輸入的二叉樹的葉子個數(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個結點的數(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(請按先序序列輸入二叉樹（如：ab.表示a為根結點，b為左子樹的二叉樹）n); t=creatbitree(); while(t=null) printf(你輸入的對叉樹為空，請重新輸入：n); temp=getchar(); t=creatbitree(); printf(請輸入k的值：n); scanf(%d,&k); while(km) printf(你輸入的k值不合理，請重新輸入：n); scanf(%d,&k); search(t); system(pause); return 0;實驗三圖一目的與要求 熟悉圖的存儲結構，掌握有關算法的實現(xiàn)，了解圖在計算機科學及其

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

33、用隊列記錄被訪問過的頂點。每次訪問與隊頭頂點相鄰接的頂點，然后將隊頭頂點從隊列中刪去。若隊空，則說明到不存在通路。在訪問頂點過程中，每次把當前頂點的序號作為與其鄰接的未訪問的頂點的前驅(qū)頂點記錄下來，以便輸出時回溯。例題參考源程序#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