《數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)蔚敏著_數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)及報(bào)告書（2014） / 學(xué)年 第 學(xué)期姓 名：_學(xué) 號(hào)：_班 級(jí)：_指導(dǎo)教師：_實(shí)驗(yàn)一 順序表與鏈表一、實(shí)驗(yàn)?zāi)康?、掌握線性表中元素的前驅(qū)、后續(xù)的概念。2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。3、對線性表相應(yīng)算法的時(shí)間復(fù)雜度進(jìn)行分析。4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)（優(yōu)缺點(diǎn)）。 二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、線性表：2、順序表：3、鏈表：三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include#include#define error 0#define ok 1#define init_size 5 /*初始分

2、配的順序表長度*/#define increm 5 /*溢出時(shí)，順序表長度的增量*/typedef int elemtype; /*定義表元素的類型*/typedef struct sqlistelemtype *slist; /*存儲(chǔ)空間的基地址*/int length; /*順序表的當(dāng)前長度*/int listsize; /*當(dāng)前分配的存儲(chǔ)空間*/sqlist;int initlist_sq(sqlist *l); /* */int createlist_sq(sqlist *l,int n); /* */int listinsert_sq(sqlist *l,int i,elemtype

3、 e);/* */int printlist_sq(sqlist *l); /*輸出順序表的元素*/int listdelete_sq(sqlist *l,int i); /*刪除第i個(gè)元素*/int listlocate(sqlist *l,elemtype e); /*查找值為e的元素*/int initlist_sq(sqlist *l) l-slist=(elemtype*)malloc(init_size*sizeof(elemtype); if(!l-slist) return error; l-length=0; l-listsize=init_size; return ok;

4、/*initlist*/int createlist_sq(sqlist *l,int n) elemtype e; int i; for(i=0;in;i+) printf(input data %d,i+1); scanf(%d,&e); if(!listinsert_sq(l,i+1,e) return error; return ok;/*createlist*/*輸出順序表中的元素*/int printlist_sq(sqlist *l) int i; for(i=1;ilength;i+) printf(%5d,l-slisti-1); return ok;/*printlist*

5、/int listinsert_sq(sqlist *l,int i,elemtype e) int k;if(il-length+1) return error; if(l-length=l-listsize) l-slist=(elemtype*)realloc(l-slist,(init_size+increm)*sizeof(elemtype); if(!l-slist) return error; l-listsize+=increm; for(k=l-length-1;k=i-1;k-) l-slistk+1= l-slistk; l-slisti-1=e; l-length+;

6、return ok;/*listinsert*/*在順序表中刪除第i個(gè)元素*/int listdelete_sq(sqlist *l,int i)if(il-length)return error;if(l-length = 0)return error;for(int j=i; jlength; j+)l-slistj-1 = l-slistj;l-length-;return ok;/*在順序表中查找指定值元素，返回其序號(hào)*/int listlocate(sqlist *l,elemtype e) int length = l-length;for(int i=0; islisti = e

7、)return i;return error;int main() sqlist sl; int n,m,k; printf(please input n:); /*輸入順序表的元素個(gè)數(shù)*/ scanf(%d,&n); if(n0) printf(n1-create sqlist:n); initlist_sq(&sl); createlist_sq(&sl,n); printf(n2-print sqlist:n); printlist_sq(&sl); printf(nplease input insert location and data:(location,data)n); scan

8、f(%d,%d,&m,&k); listinsert_sq(&sl,m,k); printf(n3-print sqlist:n); printlist_sq(&sl); printf(n); else printf(error); return 0;l 運(yùn)行結(jié)果l 算法分析2、為第1題補(bǔ)充刪除和查找功能函數(shù)，并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。刪除算法代碼：l 運(yùn)行結(jié)果l 算法分析查找算法代碼：l 運(yùn)行結(jié)果l 算法分析3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include#include#define error 0#define ok 1typedef in

9、t elemtype; /*定義表元素的類型*/typedef struct lnode /*線性表的單鏈表存儲(chǔ)*/ elemtype data; struct lnode *next;lnode,*linklist;linklist createlist(int n); /* */void printlist(linklist l); /*輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/int getelem(linklist l,int i,elemtype *e); /* */linklist createlist(int n) lnode *p,*q,*head; int i; head=(linkl

10、ist)malloc(sizeof(lnode); head-next=null; p=head; for(i=0;idata); /*輸入元素值*/ q-next=null; /*結(jié)點(diǎn)指針域置空*/ p-next=q; /*新結(jié)點(diǎn)連在表末尾*/ p=q; return head;/*createlist*/int insertlist(linklist l, elemtype e, int i)/insert before ith elementlnode* p = l;int j = 0;while(p & jnext;j+;if(!p | ji)return error;lnode* s

11、 = (linklist) malloc(sizeof(lnode);s-data = e;s-next = p-next;p-next = s;return ok;int deletelist(linklist l, elemtype& e, int i)/刪除第i個(gè)元素，并由e返回其值lnode* p = l;int j = 0;while(p-next & jnext;j+;if(!(p-next) & j next;p-next = q-next;e = q-data;free(q);return ok;void printlist(linklist l) lnode *p; p=l-

12、next; /*p指向單鏈表的第1個(gè)元素*/ while(p!=null) printf(%5d,p-data); p=p-next; /*printlist*/int getelem(linklist l,int i,elemtype *e) lnode *p;int j=1; p=l-next; while(p&jnext;j+; if(!p|ji) return error; *e=p-data; return ok;/*getelem*/int main() int n,i;elemtype e; linklist l=null; /*定義指向單鏈表的指針*/ printf(pleas

13、e input n:); /*輸入單鏈表的元素個(gè)數(shù)*/ scanf(%d,&n); if(n0) printf(n1-create linklist:n); l=createlist(n); printf(n2-print linklist:n); printlist(l); printf(n3-getelem from linklist:n); printf(input i=); scanf(%d,&i); if(getelem(l,i,&e) printf(no%i is %d,i,e); else printf(not exists); else printf(error); retur

14、n 0;l 運(yùn)行結(jié)果l 算法分析4、為第3題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。插入算法代碼：l 運(yùn)行結(jié)果l 算法分析刪除算法代碼：l 運(yùn)行結(jié)果l 算法分析以下為選做實(shí)驗(yàn)：5、循環(huán)鏈表的應(yīng)用（約瑟夫回環(huán)問題）n個(gè)數(shù)據(jù)元素構(gòu)成一個(gè)環(huán)，從環(huán)中任意位置開始計(jì)數(shù)，計(jì)到m將該元素從表中取出，重復(fù)上述過程，直至表中只剩下一個(gè)元素。提示：用一個(gè)無頭結(jié)點(diǎn)的循環(huán)單鏈表來實(shí)現(xiàn)n個(gè)元素的存儲(chǔ)。l 算法代碼6、設(shè)一帶頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)算法將表中值相同的元素僅保留一個(gè)結(jié)點(diǎn)。提示：指針p從鏈表的第一個(gè)元素開始，利用指針q從指針p位置開始向后搜索整個(gè)鏈表，刪除與之值相同的元素；指針p繼續(xù)

15、指向下一個(gè)元素，開始下一輪的刪除，直至pnull為至，既完成了對整個(gè)鏈表元素的刪除相同值。l 算法代碼四、實(shí)驗(yàn)小結(jié)五、教師評語實(shí)驗(yàn)二 棧和隊(duì)列一、實(shí)驗(yàn)?zāi)康?、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；2、掌握隊(duì)列的結(jié)構(gòu)特性及其入隊(duì)、出隊(duì)的操作，掌握循環(huán)隊(duì)列的特點(diǎn)及其操作。二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、順序棧：2、鏈棧：3、循環(huán)隊(duì)列：4、鏈隊(duì)三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀下面程序，將函數(shù)push和函數(shù)pop補(bǔ)充完整。要求輸入元素序列1 2 3 4 5 e，運(yùn)行結(jié)果如下所示。#include#include#define error 0#define ok 1#define stack_int_size 10

16、 /*存儲(chǔ)空間初始分配量*/#define stackincrement 5 /*存儲(chǔ)空間分配增量*/typedef int elemtype; /*定義元素的類型*/typedef struct elemtype *base; elemtype *top; int stacksize; /*當(dāng)前已分配的存儲(chǔ)空間*/sqstack;int initstack(sqstack *s); /*構(gòu)造空棧*/int push(sqstack *s,elemtype e); /*入棧*/int pop(sqstack *s,elemtype *e); /*出棧*/int createstack(sqst

17、ack *s); /*創(chuàng)建棧*/void printstack(sqstack *s); /*出棧并輸出棧中元素*/int initstack(sqstack *s) s-base=(elemtype *)malloc(stack_int_size *sizeof(elemtype); if(!s-base) return error; s-top=s-base; s-stacksize=stack_int_size; return ok;/*initstack*/int push(sqstack *s,elemtype e) /*push*/int pop(sqstack *s,elemty

18、pe *e) /*pop*/int createstack(sqstack *s) int e; if(initstack(s) printf(init success!n); else printf(init fail!n); return error; printf(input data:(terminated by inputing a character)n); while(scanf(%d,&e) push(s,e); return ok;/*createstack*/void printstack(sqstack *s) elemtype e; while(pop(s,&e) pr

19、intf(%3d,e);/*pop_and_print*/int main() sqstack ss; printf(n1-createstackn); createstack(&ss); printf(n2-pop&printn); printstack(&ss); return 0; l 算法分析：輸入元素序列1 2 3 4 5，為什么輸出序列為5 4 3 2 1？體現(xiàn)了棧的什么特性？2、在第1題的程序中，編寫一個(gè)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的數(shù)制轉(zhuǎn)換算法函數(shù)（要求利用棧來實(shí)現(xiàn)），并驗(yàn)證其正確性。l 實(shí)現(xiàn)代碼l 驗(yàn)證3、閱讀并運(yùn)行程序，并分析程序功能。#include#include#include

20、#define m 20#define elemtype chartypedef struct elemtype stackm; int top;stacknode;void init(stacknode *st);void push(stacknode *st,elemtype x);void pop(stacknode *st);void init(stacknode *st) st-top=0;void push(stacknode *st,elemtype x) if(st-top=m) printf(the stack is overflow!n); else st-top=st-t

21、op+1; st-stackst-top=x; void pop(stacknode *st)if(st-top0) st-top-; else printf(“stack is empty!n”);int main() char sm; int i; stacknode *sp; printf(create a empty stack!n); sp=(stacknode*)malloc(sizeof(stacknode); init(sp); printf(input a expression:n); gets(s); for(i=0;itop=0) printf(match)!n); el

22、se printf(not match)!n); return 0;l 輸入：2+(c-d)*6-(f-7)*a)/6l 運(yùn)行結(jié)果：l 輸入：a-(c-d)*6-(s/3-x)/2l 運(yùn)行結(jié)果：l 程序的基本功能：以下為選做實(shí)驗(yàn)：4、假設(shè)一帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)（不設(shè)隊(duì)頭指針），試編寫相應(yīng)的置空隊(duì)列、入隊(duì)列、出隊(duì)列的算法。實(shí)現(xiàn)代碼：四、實(shí)驗(yàn)小結(jié)五、教師評語實(shí)驗(yàn)三 串的模式匹配一、實(shí)驗(yàn)?zāi)康?、了解串的基本概念2、掌握串的模式匹配算法的實(shí)現(xiàn) 二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、模式匹配：2、bf算法：3、kmp算法：三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)

23、行結(jié)果。#include#include#define maxsize 100typedef structchar datamaxsize;int length;sqstring;int strcompare(sqstring *s1,sqstring *s2); /*串的比較*/void show_strcompare();void strsub(sqstring *s,int start,int sublen,sqstring *sub); /*求子串*/void show_substring();int strcompare(sqstring *s1,sqstring *s2)int i

24、;for(i=0;ilength&ilength;i+)if(s1-datai!=s2-datai)return s1-datai-s2-datai;return s1-length-s2-length;void show_strcompare() sqstring s1,s2; int k; printf(n*show compare*n); printf(input string s1:); gets(s1.data); s1.length=strlen(s1.data); printf(input string s2:); gets(s2.data); s2.length=strlen(

25、s2.data); if(k=strcompare(&s1,&s2)=0) printf(s1=s2n); else if(k0) printf(s1s2n); printf(n*show over*n);void strsub(sqstring *s,int start,int sublen,sqstring *sub)int i;if(starts-length|sublens-length-start+1)sub-length=0;for(i=0;idatai=s-datastart+i-1;sub-length=sublen;void show_substring() sqstring

26、 s,sub; int start,sublen,i; printf(n*show substring*n); printf(input string s:); gets(s.data); s.length=strlen(s.data); printf(input start:); scanf(%d,&start); printf(input sublen:); scanf(%d,&sublen); strsub(&s,start,sublen,&sub); if(sub.length=0) printf(error!n); else printf(substring is :); for(i

27、=0;isublen;i+) printf(%c,sub.datai); printf(n*show over*n);int main() int n; do printf(n-string-n); printf(1. strcomparen); printf(2. substringn); printf(0. exitn); printf(ninput choice:); scanf(%d,&n); getchar(); switch(n) case 1:show_strcompare();break; case 2:show_substring();break; default:n=0;b

28、reak; while(n); return 0;l 運(yùn)行程序輸入：1studentstudents2computer data stuctures104運(yùn)行結(jié)果：2、實(shí)現(xiàn)串的模式匹配算法。補(bǔ)充下面程序，實(shí)現(xiàn)串的bf和kmp算法。#include#include#define maxsize 100typedef structchar datamaxsize;int length;sqstring;int index_bf(sqstring *s,sqstring *t,int start);void getnext(sqstring *t,int next);int index_kmp(sq

29、string *s,sqstring *t,int start,int next);void show_index();int index_bf(sqstring *s,sqstring *t,int start)補(bǔ)充代碼.void getnext(sqstring *t,int next)int i=0,j=-1;next0=-1;while(ilength)if(j=-1)|(t-datai=t-dataj)i+;j+;nexti=j;elsej=nextj; int index_kmp(sqstring *s,sqstring *t,int start,int next)補(bǔ)充代碼.voi

30、d show_index() sqstring s,t; int k,nextmaxsize=0,i; printf(n*show index*n); printf(input string s:); gets(s.data); s.length=strlen(s.data); printf(input string t:); gets(t.data); t.length=strlen(t.data); printf(input start position:); scanf(%d,&k); printf(bf:nthe result of bf is %dn,index_bf(&s,&t,k

31、); getnext(&t,next); printf(kmp:n); printf(next:); for(i=0;it.length;i+) printf(%3d,nexti); printf(n); printf(the result of kmp is %dn,index_kmp(&s,&t,k,next); printf(n*show over*n);int main()show_index();return 0;輸入：abcaabbabcabaacbacbaabcabaa1運(yùn)行結(jié)果：四、實(shí)驗(yàn)小結(jié)五、教師評語實(shí)驗(yàn)四 二叉樹一、實(shí)驗(yàn)?zāi)康?、掌握二叉樹的基本特性2、掌握二叉樹的先序、中序

32、、后序的遞歸遍歷算法 3、理解二叉樹的先序、中序、后序的非遞歸遍歷算法4、通過求二叉樹的深度、葉子結(jié)點(diǎn)數(shù)和層序遍歷等算法，理解二叉樹的基本特性二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、二叉樹：2、遞歸遍歷：1、 非遞歸遍歷：4、層序遍歷：三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果，并畫出二叉樹的形態(tài)。#include#include#define max 20typedef struct btnode /*節(jié)點(diǎn)結(jié)構(gòu)聲明*/char data ; /*節(jié)點(diǎn)數(shù)據(jù)*/struct btnode *lchild;struct btnode *rchild ; /*指針*/*bitree;void

33、 createbitree(bitree *t) /* 先序遍歷創(chuàng)建二叉樹*/char s;bitree q;printf(nplease input data:(exit for #);s=getche();if(s=#)*t=null; return;q=(bitree)malloc(sizeof(struct btnode);if(q=null)printf(memory alloc failure!); exit(0);q-data=s;*t=q;createbitree(&q-lchild); /*遞歸建立左子樹*/createbitree(&q-rchild); /*遞歸建立右子樹

34、*/void preorder(bitree p) /* 先序遍歷二叉樹*/ if ( p!= null ) printf(%c, p-data); preorder( p-lchild ) ; preorder( p-rchild) ; void inorder(bitree p) /* 中序遍歷二叉樹*/ if( p!= null ) inorder( p-lchild ) ; printf(%c, p-data); inorder( p-rchild) ; void postorder(bitree p) /* 后序遍歷二叉樹*/ if ( p!= null ) postorder( p

35、-lchild ) ; postorder( p-rchild) ; printf(%c, p-data); void preorder_n(bitree p) /*先序遍歷的非遞歸算法*/ bitree stackmax,q; int top=0,i; for(i=0;idata); if(q-rchild!=null) stacktop+=q-rchild; if(q-lchild!=null) q=q-lchild; else if(top0) q=stack-top; else q=null; void release(bitree t) /*釋放二叉樹空間*/ if(t!=null)

36、 release(t-lchild); release(t-rchild); free(t); int main() bitree t=null; createbitree(&t); printf(nnpreorder the tree is:); preorder(t); printf(nninorder the tree is:); inorder(t); printf(nnpostorder the tree is:); postorder(t); printf(nn先序遍歷序列（非遞歸）:); preorder_n(t); release(t); return 0;l 運(yùn)行程序輸入：a

37、bc#de#g#f#運(yùn)行結(jié)果：2、在上題中補(bǔ)充求二叉樹中求結(jié)點(diǎn)總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計(jì)遍歷的結(jié)點(diǎn)數(shù)），并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。算法代碼：3、在上題中補(bǔ)充求二叉樹中求葉子結(jié)點(diǎn)總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計(jì)遍歷的葉子結(jié)點(diǎn)數(shù)），并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。算法代碼：4、在上題中補(bǔ)充求二叉樹深度算法，并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。算法代碼：選做實(shí)驗(yàn)：（代碼可另附紙）2、 補(bǔ)充二叉樹層次遍歷算法。（提示：利用隊(duì)列實(shí)現(xiàn)）5、補(bǔ)充二叉樹中序、后序非遞歸算法。四、實(shí)驗(yàn)小結(jié)五、教師評語實(shí)驗(yàn)五 圖的表示與遍歷一、實(shí)驗(yàn)?zāi)康?、掌握圖的鄰接矩陣和鄰接表表示2、掌握

38、圖的深度優(yōu)先和廣度優(yōu)先搜索方法 3、理解圖的應(yīng)用方法二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、深度優(yōu)先搜索遍歷：2、廣度優(yōu)先搜索遍歷：3、拓?fù)渑判颍?、最小生成樹：5、最短路徑：三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果。#include#define n 20#define true 1#define false 0int visitedn; typedef struct /*隊(duì)列的定義*/ int datan; int front,rear;queue;typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsn; int arcsn

39、n;graph;void creategraph(graph *g); /*建立一個(gè)無向圖的鄰接矩陣*/void dfs(int i,graph *g); /*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/void tdfs(graph *g); /*深度優(yōu)先搜索整個(gè)圖*/void bfs(int k,graph *g); /*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/void tbfs(graph *g); /*廣度優(yōu)先搜索整個(gè)圖*/void init_visit(); /*初始化訪問標(biāo)識(shí)數(shù)組*/void creategraph(graph *g) /*建立一個(gè)無向圖的鄰接矩陣*/ int i,j; char v; g

40、-vexnum=0; g-arcnum=0; i=0; printf(輸入頂點(diǎn)序列(以#結(jié)束)：n); while(v=getchar()!=#) g-vexsi=v; /*讀入頂點(diǎn)信息*/ i+; g-vexnum=i; /*頂點(diǎn)數(shù)目*/ for(i=0;ivexnum;i+) /*鄰接矩陣初始化*/ for(j=0;jvexnum;j+) g-arcsij=0; printf(輸入邊的信息：n); scanf(%d,%d,&i,&j); /*讀入邊i,j*/ while(i!=-1) /*讀入i,j為1時(shí)結(jié)束*/ g-arcsij=1; g-arcsji=1; scanf(%d,%d,&i

41、,&j); void dfs(int i,graph *g) /*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/ int j; printf(%c,g-vexsi); visitedi=true; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) dfs(j,g);void tdfs(graph *g) /*深度優(yōu)先搜索整個(gè)圖*/ int i; printf(n從頂點(diǎn)%c開始深度優(yōu)先搜索序列：,g-vexs0); for(i=0;ivexnum;i+) if(visitedi!=true) dfs(i,g);void bfs(int k,graph *g) /*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/ int