數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書C語言版羅先文樣本

——信息管理系

《數(shù)據(jù)構(gòu)造》實(shí)驗(yàn)指引書《DATASTRUCTURES》羅先文LUOXIANWEN

西南大學(xué)信息管理系Iinformationdept.SouthWest

January24，

寫在上機(jī)實(shí)習(xí)之前上機(jī)實(shí)踐是學(xué)生對(duì)本門課程所學(xué)知識(shí)一種全面、綜合能力訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成必不可少一種教學(xué)環(huán)節(jié)，也是對(duì)課堂教學(xué)與實(shí)踐教學(xué)效果一種檢查。普通，實(shí)習(xí)題中問題比平時(shí)習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)著眼于原理與應(yīng)用結(jié)合，使學(xué)生學(xué)會(huì)如何把書上學(xué)到知識(shí)運(yùn)用于解決實(shí)際問題過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計(jì)工作所必須基本技能；另一方面，能使書上知識(shí)變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容目。平時(shí)練習(xí)較偏重于如何編寫功能單一“小”算法，而實(shí)習(xí)題是軟件設(shè)計(jì)綜合訓(xùn)練，涉及問題分析，總體構(gòu)造設(shè)計(jì)，顧客界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧，多人合伙，以至一整套軟件工程規(guī)范訓(xùn)練和科學(xué)作風(fēng)培養(yǎng)。此外，尚有很重要一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)肅主考者。為了達(dá)到上述目，本篇安排了7個(gè)主實(shí)習(xí)單元，各單元訓(xùn)練重點(diǎn)在于基本數(shù)據(jù)構(gòu)造，而不強(qiáng)調(diào)面面俱到。各實(shí)習(xí)單元與教科書各章具備緊密相應(yīng)關(guān)系，在個(gè)別實(shí)習(xí)單元中安排有難度差別不等各種實(shí)習(xí)題，以便學(xué)生選做。此外，每個(gè)實(shí)習(xí)題采用了統(tǒng)一格式，實(shí)驗(yàn)?zāi)俊?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)規(guī)定、程序?qū)崿F(xiàn)、程序運(yùn)營(yíng)狀況和源程序清單等5個(gè)某些構(gòu)成。在每個(gè)實(shí)習(xí)單元都提供了一種完整實(shí)當(dāng)代碼，僅供同窗們參照，絕大多數(shù)同窗在上機(jī)實(shí)習(xí)時(shí)千萬不要機(jī)械照抄本附錄所提供范文。而是應(yīng)當(dāng)自己獨(dú)立思考和設(shè)計(jì)你算法和程序，并爭(zhēng)取在規(guī)定期間內(nèi)如期完畢上機(jī)工作任務(wù)。對(duì)于個(gè)別成績(jī)較差同窗，實(shí)在是沒法完畢任務(wù)建議你不妨抄一遍附錄中樣題，以增強(qiáng)你感性結(jié)識(shí)，強(qiáng)化你實(shí)踐基本，提高你實(shí)踐能力。本附錄樣題所有用c語言編寫，并所有上機(jī)調(diào)試通過，但由于時(shí)間比較倉促，樣題中提供算法和程序并不是最佳算法和程序，相信不少同窗一定有能力設(shè)計(jì)出更好算法和程序。隨著計(jì)算機(jī)學(xué)科不斷發(fā)展，可以使用語言工具越來越豐富，在本篇中實(shí)習(xí)示例還只是應(yīng)用面向過程語言進(jìn)行設(shè)計(jì)和編寫程序，同樣實(shí)習(xí)題，讀者也可以用面向?qū)ο笳Z言來實(shí)現(xiàn)。咱們但愿實(shí)習(xí)報(bào)告示例能起到一種拋磚引玉作用，在通過同窗們努力學(xué)習(xí)和積極使用后來，更多更優(yōu)良設(shè)計(jì)范例能不斷涌現(xiàn)。文中存在不當(dāng)之處，敬請(qǐng)各位不吝賜教！

目錄《數(shù)據(jù)構(gòu)造》實(shí)驗(yàn)大綱 4實(shí)驗(yàn)一、線性表操作 2實(shí)驗(yàn)二、棧和隊(duì)列應(yīng)用 6實(shí)驗(yàn)三、多維數(shù)組和串 12實(shí)驗(yàn)四、樹和二叉樹操作 17實(shí)驗(yàn)五、圖操作 23實(shí)驗(yàn)六、各種查找操作 30實(shí)驗(yàn)七、各種排序操作 37

《數(shù)據(jù)構(gòu)造》實(shí)驗(yàn)大綱一.

課程名稱：數(shù)據(jù)構(gòu)造及算法分析課程編號(hào)：課程學(xué)時(shí)：70課程學(xué)分：3.5實(shí)驗(yàn)時(shí)數(shù)：20二.

所屬實(shí)驗(yàn)室名稱：計(jì)算機(jī)中心三.

實(shí)驗(yàn)教材及參照書：【1】數(shù)據(jù)構(gòu)造題集（C語言版）清華大學(xué)出版社【2】DATASTRUCTURESWITHC++清華大學(xué)出版社【3】本材料之后附錄四.

實(shí)驗(yàn)內(nèi)容和目：掌握四種基本數(shù)據(jù)構(gòu)造：集合、線性構(gòu)造、樹形構(gòu)造、網(wǎng)狀構(gòu)造在求解實(shí)際問題中應(yīng)用，以及培養(yǎng)書寫規(guī)范文檔技巧。學(xué)習(xí)基本查找和排序技術(shù)。規(guī)定學(xué)生具備編制相稱規(guī)模程序能力。養(yǎng)成一種良好程序設(shè)計(jì)風(fēng)格。五.

考核方式：上機(jī)考試、編程并運(yùn)營(yíng)通過。六.

實(shí)驗(yàn)環(huán)境：硬件最低規(guī)定：586微型計(jì)算機(jī)，主頻450MHZ以上，內(nèi)存64MB以上，硬盤10G，有軟驅(qū)。每個(gè)學(xué)生每次上機(jī)實(shí)驗(yàn)使用一臺(tái)計(jì)算機(jī)。軟件：C語言或VisualC++6.0七.

實(shí)驗(yàn)項(xiàng)目及安排

序號(hào)實(shí)驗(yàn)名稱類別學(xué)時(shí)目與安排備注必選選開1鏈表、數(shù)組?

4插入、刪除、合并、排序、查找

2棧與隊(duì)列?

4

3遞規(guī)算法?

4漢諾塔問題

4樹及應(yīng)用?

4遞規(guī)、非遞規(guī)遍歷

5圖及應(yīng)用?

4遍歷算法、最小生成樹

6排序查找?

4排序、查找算法比較分析

7串及應(yīng)用

?4匹配算法

8線索樹

?4中序線索化操作

實(shí)驗(yàn)一、線性表操作一、實(shí)驗(yàn)?zāi)?．掌握用C語言調(diào)試程序基本辦法。2．掌握線性表基本運(yùn)算，如插入、刪除等。二、實(shí)驗(yàn)內(nèi)容1．線性表在順序存儲(chǔ)構(gòu)造上插入元素，刪除元素運(yùn)算2．線性表在鏈?zhǔn)酱鎯?chǔ)構(gòu)造上建鏈表，插入結(jié)點(diǎn)，刪除結(jié)點(diǎn)運(yùn)算三、實(shí)驗(yàn)規(guī)定1．

C++/C完畢算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。2．

撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)成果和數(shù)據(jù)。3．

分析算法，規(guī)定給出詳細(xì)算法分析成果，涉及時(shí)間復(fù)雜度和空間復(fù)雜度，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。四、程序?qū)崿F(xiàn)寫出每個(gè)操作算法（操作過程）五、程序運(yùn)營(yíng)狀況寫出輸入數(shù)據(jù)及運(yùn)營(yíng)成果六、源程序清單。

程序1：順序存儲(chǔ)線性表和運(yùn)算#include<stdio.h>#defineMAXSIZE100intlist[MAXSIZE];intn;/*insertinaseqlist*/intsq_insert(intlist[]，int*p_n，inti，intx){intj; if(i<0||i>*p_n)return(1); if(*p_n==MAXSIZE)return(2); for(j=*p_n+1；j>i；j--) list[j]=list[j-1]; list[i]=x; (*p_n)++; return(0); }/*deleteinaseqlist*/intsq_delete(intlist[]，int*p_n，inti) {intj; if(i<0||i>=*p_n)return(1); for(j=i+1；j<=*p_n；j++) list[j-1]=list[j]; (*p_n)--; return(0); }

voidmain() {inti,x,temp; printf("pleaseinputthenumberforn\n"); printf("n="); scanf("%d",&n); for(i=0；i<=n；i++) {printf("list[%d]=",i); scanf("%d",&list[i]);}

printf("Thelistbeforeinsertionis\n"); for(i=0；i<=n；i++)printf("%d",list[i]); printf("\n"); printf("pleaseinputthepositionwhereyouwanttoinsertavalue\nposition="); scanf("%d",&i); printf("pleaseinputthevalueyouwanttoinsert.\nx="); scanf("%d",&x); temp=sq_insert(list,&n,i,x); switch(temp) {case0:printf("Theinsertionissuccessful!\n"); printf("Thelistisafterinsertionis\n"); for(i=0；i<=n；i++)printf("%d",list[i]); printf("\n"); printf("%d\n",n); break; case1: case2:printf("Theinsertionisnotsuccessful!\n");break;} /*deleting*/ printf("Thelistbeforedeletingis\n"); for(i=0；i<=n；i++)printf("%d",list[i]); printf("\n"); printf("pleaseinputthepositionwhereyouwanttodeleteavalue\nposition="); scanf("%d",&i); temp=sq_delete(list,&n,i); switch(temp) {case0:printf("Thedeletingissuccessful!\n"); printf("Thelistisafterdeletingis\n"); for(i=0；i<=n；i++)printf("%d",list[i]); printf("\n"); printf("%d",n); break; case1:printf("Thedeletingisnotsuccessful!");break;} }程序2鏈?zhǔn)酱鎯?chǔ)線性表和運(yùn)算#include<stdio.h>#include<malloc.h>structnode{ chardata; structnode*next; };typedefstructnodeNODE;/*Thisfunctioncreatesalink_listwithNnodes.*/NODE*create_link_list(intn){inti; NODE*head，*p，*q; if(n==0)returnNULL; head=(NODE*)malloc(sizeof(NODE)); p=head;printf("Pleaseinput%dcharsforthelinklist\n",n); for(i=0；i<n；i++) {scanf("%c"，&(p->data)); q=(NODE*)malloc(sizeof(NODE)); printf("test3\n"); p->next=q; p=q;} scanf("%c",&(p->data)); getchar(); p->next=NULL; return(head);}/*Thisfunctioninsertsanodewhosevalueisb*//*beforethenodewhosevalueisa，ifthenodeisnotexist,*//*theninsertitattheendofthelist*/voidinsert(NODE**p_head，chara，charb) {NODE*p，*q; q=(NODE*)malloc(sizeof(NODE)); q->data=b; q->next=NULL; if(*p_head==NULL)*p_head=q; else {p=(NODE*)malloc(sizeof(NODE)); p=*p_head; while(p->data!=a&&p->next!=NULL) p=p->next; q->next=p->next; p->next=q;} }/*Thefunctiondeletesthenodewhosevalueisa,*//*ifsuccess，return0，orreturn1*/intdeletenode(NODE**p_head，chara) {NODE*p，*q; q=*p_head; if(q==NULL)return(1); if(q->data==a) {*p_head=q->next; free(q); return(0);} else {while(q->data!=a&&q->next!=NULL) {p=q; q=q->next;} if(q->data==a) {p->next=q->next; free(q); return(0);} elsereturn(1);} }voidmain(){ NODE*my_head,*p; /*createalinklistwithmnodes*/ intm; charch_a,ch_b; printf("pleaseinputthenumberofnodesforthelink_list\nm="); scanf("%d",&m); getchar(); printf("test1\n"); my_head=(NODE*)malloc(sizeof(NODE)); my_head=create_link_list(m); /*Outputthelinklist*/ printf("Thelinklistislike:\n"); p=my_head; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n"); /*insertanodewhosevalueisbbeforea*/ printf("Pleaseinputthepositionfora\nch_a="); getchar(); scanf("%c",&ch_a); getchar(); printf("Pleaseinputthevaluethatyouwanttoinsert\nch_b="); scanf("%c",&ch_b); getchar(); insert(&my_head,ch_a,ch_b); printf("Thelinklistafterinsertionislike:\n"); p=my_head; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n"); /*deleteanodewhosevalueisa*/ printf("Pleaseinputthepositionforaa="); scanf("%c",&ch_a); getchar(); deletenode(&my_head,ch_a); printf("Thelinklistafterdeletingislike:\n"); p=my_head; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}

實(shí)驗(yàn)二、棧和隊(duì)列應(yīng)用一、實(shí)驗(yàn)?zāi)?、掌握棧特點(diǎn)(先進(jìn)后出FILO)及基本操作,如入棧、出棧等，棧順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造，以便在實(shí)際問題背景下靈活應(yīng)用。2、掌握隊(duì)列特點(diǎn)(先進(jìn)先出FIFO)及基本操作,如入隊(duì)、出隊(duì)等，隊(duì)列順序存儲(chǔ)構(gòu)造、鏈?zhǔn)酱鎯?chǔ)構(gòu)造和循環(huán)隊(duì)列實(shí)現(xiàn)，以便在實(shí)際問題背景下靈。二、實(shí)驗(yàn)內(nèi)容1．順序棧實(shí)現(xiàn)和運(yùn)算2．鏈棧實(shí)現(xiàn)和運(yùn)算3．順序隊(duì)列實(shí)現(xiàn)和運(yùn)算4．鏈?zhǔn)疥?duì)列實(shí)現(xiàn)和運(yùn)算5．循環(huán)隊(duì)列實(shí)現(xiàn)和運(yùn)算三、實(shí)驗(yàn)規(guī)定1．用C++/C完畢算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。2．撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)成果和數(shù)據(jù)。3．分析算法，規(guī)定給出詳細(xì)算法分析成果，涉及時(shí)間復(fù)雜度和空間復(fù)雜度，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。四、程序?qū)崿F(xiàn)寫出每個(gè)操作算法（操作過程）程序運(yùn)營(yíng)狀況五、寫出輸入數(shù)據(jù)及運(yùn)營(yíng)成果六、源程序清單。

程序1：順序棧實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#defineMAXN26charstack[MAXN];inttop=0;

intpush(charx) {if(top>=MAXN) return(1); stack[top++]=x; return(0);}

intpop(char*p_y) {if(top==0) return(1); *p_y=stack[--top]; return(0);}

voidmain(){inti; charch_x,ch_y; printf("inputthecharyouwanttopush\n"); scanf("%c",&ch_x); while(ch_x!='0') if(push(ch_x)==1)printf("failure!\n"); else {printf("success!\n"); printf("inputacharforch_xtopush\nch_x="); getchar(); scanf("%c",&ch_x);} i=0; while(stack[i]!='\0') {printf("%c"，stack[i]); i++;}

if(pop(&ch_y)==1)printf("failure!\n"); else {printf("success!\n"); printf("Thepopcharis%c\n",ch_y);} for(i=top-1；i>=0；i--) printf("%c"，stack[i]);}程序2：鏈棧實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<malloc.h>structnode{chardata; structnode*link;};typedefstructnodeNODE;NODE*top=NULL;

voidpush_l(charx) {NODE*p; p=(NODE*)malloc(sizeof(NODE)); p->data=x; p->link=top; top=p;}intpop_l(char*p_y) {NODE*p; if(top==NULL) return(1); *p_y=top->data; p=top; top=top->link; free(p); return(0);}

voidmain(){ NODE*p; charch_x,ch_y;

printf("inputthecharyouwanttopush\n"); scanf("%c",&ch_x); while(ch_x!='0') {push_l(ch_x); getchar(); scanf("%c",&ch_x);}

p=(NODE*)malloc(sizeof(NODE)); p=top; while(p!=NULL) {printf("%c",p->data); p=p->link;} printf("\n");

if(pop_l(&ch_y)==1)printf("failure!\n"); else {printf("success!\n"); printf("Thepopcharis%c\n",ch_y);}

p=(NODE*)malloc(sizeof(NODE)); p=top; while(p!=NULL) {printf("%c",p->data); p=p->link;} printf("\n");}程序3：順序隊(duì)列實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#defineMAXN26charq[MAXN];inthead=-1，tail=-1;

inten_queue(charx) {if(tail==MAXN-1) return(1); q[++tail]=x; return(0);}

intde_queue(char*p_y) {if(head==tail) return(1); *p_y=q[++head]; return(0);}

voidmain(){inti; charch_x,ch_y; printf("inputthecharyouwanttoenqueue\n"); scanf("%c",&ch_x); while(ch_x!='0') if(en_queue(ch_x)==1)printf("failure!\n"); else {printf("success!\n"); printf("inputacharforch_xtoenqueue\nch_x="); getchar(); scanf("%c",&ch_x);} i=1; while(q[i]!='\0') {printf("%c"，q[i]); i++;} if(de_queue(&ch_y)==1)printf("failure!\n"); else {printf("success!\n"); printf("Thedequeuecharis%c\n",ch_y);} for(i=head+1；i<=tail；i++) printf("%c"，q[i]);}程序4：鏈?zhǔn)疥?duì)列實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<malloc.h>"structnode{chardata; structnode*link;};typedefstructnodeNODE;NODE*head，*tail;

voiden_queue_l(charx) {NODE*p; p=(NODE*)malloc(sizeof(NODE)); p->data=x; p->link=NULL; if(head==NULL) head=p; else tail->link=p; tail=p;}intde_queue_l(char*p_y) {NODE*p; if(head==NULL) return(1); *p_y=head->data; p=head; head=head->link; free(p); return(0);}

voidmain(){ NODE*p; charch_x,ch_y; printf("inputthecharyouwanttoenqueue\n"); scanf("%c",&ch_x); while(ch_x!='0') {en_queue_l(ch_x); getchar(); scanf("%c",&ch_x);}

p=(NODE*)malloc(sizeof(NODE)); p=head; while(p!=NULL) {printf("%c",p->data); p=p->link;} printf("\n"); if(de_queue_l(&ch_y)==1)printf("failure!\n"); else {printf("success!\n"); printf("Thedequeuecharis%c\n",ch_y);} p=(NODE*)malloc(sizeof(NODE)); p=head; while(p!=NULL) {printf("%c",p->data); p=p->link;} printf("\n");}程序5：循環(huán)隊(duì)列實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<string.h>#defineMAXN26charq[MAXN];inthead=0，tail=0;

inten_c_q(charx) {tail=(tail+1)%MAXN; if(tail==head) {if(tail==0)tail=MAXN-1; elsetail--; return(1);} q[tail]=x; return(0);}

intde_c_q(char*p_y) {if(head==tail) return(1); head=(head+1)%MAXN; *p_y=q[head]; return(0);}

voidmain(){inti; charch_x,ch_y; printf("inputthecharyouwanttoenqueue\n"); scanf("%c",&ch_x); while(ch_x!='0') if(en_c_q(ch_x)==1)printf("failure!\n"); else {printf("success!\n"); printf("inputacharforch_xtoenqueue\nch_x="); getchar(); scanf("%c",&ch_x);} i=1; while(q[i]!='\0') {printf("%c"，q[i]); i++;} if(de_c_q(&ch_y)==1)printf("failure!\n"); else {printf("success!\n"); printf("Thedequeuecharis%c\n",ch_y);} for(i=head+1；i<=tail；i++) printf("%c"，q[i]);}

實(shí)驗(yàn)三、多維數(shù)組和串一、實(shí)驗(yàn)?zāi)?．掌握稀疏矩陣特點(diǎn)(三元組存儲(chǔ)辦法)。2．掌握串運(yùn)算（賦值，比較，聯(lián)結(jié)，插入子串，模式匹配……等）。二、實(shí)驗(yàn)內(nèi)容1．稀疏矩陣存儲(chǔ)及轉(zhuǎn)置運(yùn)算2．串基本操作三、實(shí)驗(yàn)規(guī)定1．用C++/C完畢算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。2．撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)成果和數(shù)據(jù)。3．分析算法，規(guī)定給出詳細(xì)算法分析成果，涉及時(shí)間復(fù)雜度和空間復(fù)雜度，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。四、程序?qū)崿F(xiàn)寫出每個(gè)操作算法（操作過程）程序運(yùn)營(yíng)狀況五、寫出輸入數(shù)據(jù)及運(yùn)營(yíng)成果六、源程序清單。

程序1：稀疏矩陣存儲(chǔ)及轉(zhuǎn)置運(yùn)算#include<stdio.h>typedefstruct{introw; intcol; intval; }THA;#define MAX20main(){inti，j，count=1;intcol，row，val;THAs[MAX];THAt[MAX];printf("inputthenumberofrow,colandelements:");scanf("%d,%d,%d",&s[0].row,&s[0].col,&s[0].val);if(s[0].val==0)return；val=s[0].val;for(i=1;i<=val;i++);scanf("%d,%d,%d",&s[i].row,&s[i].col,&s[i].val);row=s[0].row;col=s[0].col;count=1;for(i=1；i<=col；i++) for(j=1；j<=val；j++) if(s[j].col==i){ t[count].row=s[j].col; t[count].col=s[j].row; t[count++].val=s[j].val; }t[0].row=col;t[0].col=row;t[0].val=val;for(i=0;i<=val;i++) printf("%d,%d,%d\n",t[i].row,t[i].col,t[i].val);}程序2：串實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#defineMAXN128typedefenum{fail,success}status;typedefenum{false,true}boolean;main(){intstrlen();voidstrass();booleanstrcmp();statusstrcat();statusstrins();voidpatmatch();

intt,n,i;booleanb;statusst;chars[MAXN],s1[MAXN],s2[MAXN];printf("\n1.Thelengthofstring\n");printf("2.Theassignmentofstring\n");printf("3.Astringcomparewithanotherstring:\n");printf("4.Astringconnectwithanotherstring:\n");printf("5.Astringtobeinsertedintoanotherstring\n");printf("6.Thepatternmatchofstring:");printf("Pleaseinputaopertation:");scanf("%d",&t);switch(t){case1: printf("pleaseinputastring:\n"); getchar(); gets(s); n=strlen(s); printf("thelengthis：%d",n); break; case2: printf("pleaseinputthefirststring:\n"); getchar(); gets(s1); printf("pleaseinputthesecondstring:\n"); getchar(); gets(s2); strass(s1,s2); break; case3: printf("pleaseinputthefirststring:\n"); getchar(); gets(s1); printf("pleaseinputthesecondstring：\n"); gets(s2); b=strcmp(s1,s2); if(b==true) printf("equal\n"); else printf("notequal\n"); break; case4: printf("pleaseinputthefirststring:\n"); getchar(); gets(s1); printf("pleaseinputthesecondstring:\n"); gets(s2); st=strcat(s1,s2); if(st==success) printf("answeris%s\n",s1); else printf("error!\n"); break; case5: printf("pleaseinputthefirststring:\n"); getchar(); gets(s1); printf("pleaseinputthesecondstring:\n"); gets(s2); printf("pleaseinputi:"); scanf("%d",&i); st=strins(s1,i,s2); if(st==success) printf("answeris%s\n",s1); elseprintf("error!\n"); break; case6: patmatch(); break; default：printf("Thereisn'tthisoperation!");}}intstrlen(s)chars[];{inti;for(i=0;s[i]!='\0';i++);return(i);}voidstrass(s1,s2)chars1[],s2[];{inti=0;while(s1[i]!='\0'){s2[i]=s1[i]; i++;}s2[i]='\0';printf("s2is%s",s2);}booleanstrcmp(s1,s2)chars1[],s2[];{inti=0;while(s1[i]==s2[i]&&s1[i]!='\0'&&s2[i]!='\0')i++;if(s1[i]=='\0'&&s2[i]=='\0') return(true);else return(false);}statusstrcat(s1,s2)chars1[],s2[];{inti,j,k;i=strlen(s1);j=strlen(s2);if((i+j)>=MAXN)return(fail);for(k=0;k<=j;k++)s1[i+k]=s2[k];return(success);}statusstrins(s1,i,s2)chars1[],s2[];inti;{intm,n,k;m=strlen(s1);n=strlen(s2);if(i<0||i>m||(m+n)>MAXN) return(fail);for(k=m;k>=i;k--) s1[k+n]=s1[k];for(k=0;k<n;k++) s1[i+k]=s2[k];return(success);}intsmatch(ch,n,pat,m) charch[],pat[];intn,m;{ints,p,k;for(s=0;s<=n-m;s++) { for(p=0,k=s;p<m&&ch[k]==pat[p];k++,p++); if(p==m)return(s+1);}return(-1);}voidpatmatch(){charch[MAXN],pat[MAXN];intn,m，result;printf("\ninputtheprimarystring:\n");scanf("%s",ch);printf("inputthepatternstring:\n");scanf("%s",pat);n=strlen(ch);m=strlen(pat);result=smatch(ch,n,pat,m);if(result==-1)printf("\nNomatchedfound!");elseif(result>=0)printf("\nMatchedsubstringfoundinposition%d",result);}

實(shí)驗(yàn)四、樹和二叉樹操作一、實(shí)驗(yàn)?zāi)?．進(jìn)一步掌握樹構(gòu)造及非線性特點(diǎn)，遞歸特點(diǎn)和動(dòng)態(tài)性。2．進(jìn)一步鞏固對(duì)指針使用和二叉樹三種遍歷辦法、建立辦法及用廣義表進(jìn)行輸入輸出。二、實(shí)驗(yàn)內(nèi)容1．二叉樹實(shí)現(xiàn)和運(yùn)算2．線索二叉樹實(shí)現(xiàn)3．哈夫曼樹實(shí)現(xiàn)三、實(shí)驗(yàn)規(guī)定1．用C++/C完畢算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。2．撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)成果和數(shù)據(jù)。3．分析算法，規(guī)定給出詳細(xì)算法分析成果，涉及時(shí)間復(fù)雜度和空間復(fù)雜度，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。四、程序?qū)崿F(xiàn)寫出每個(gè)操作算法（操作過程）程序運(yùn)營(yíng)狀況五、寫出輸入數(shù)據(jù)及運(yùn)營(yíng)成果六、源程序清單。

程序1：二叉樹實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefstructbtnode {chardata；/*supposethedatafield'stypeischar*/ structbtnode*lchild；/*leftpointerfield*/ structbtnode*rchild；/*rightpointerfield*/ }NODE;voidmain(){ NODE*root,*q,n; NODE*create(NODE*p); voidpreorder(NODE*root); voidinorder(NODE*root); voidpostorder(NODE*root);intt; q=&n; root=create(q); printf("Atthefirst,wecreateatree\n"); printf("Pleaseinputnodesoftree\n"); if(root==NULL)printf("It'sanemptytree!\n"); else { printf("\n1.Thepreordetraverse\n"); printf("2.Theinordertraverse\n"); printf("3.Thepostordertraverse\n"); printf("Pleasechooseakindoforder\n"); scanf("%d",&t); switch(t) { case1：preorder(root)；break; case2：inorder(root)；break; case3:postorder(root)；break; default：printf("Theerror!"); } }}

NODE*create(NODE*p)/*createthestructureofbinarytree*/{ charch; NODE*t;scanf("%c",&ch); if(ch=='')p=NULL; else {p->data=ch; t=(NODE*)malloc(sizeof(NODE)); p->lchild=create(t); t=(NODE*)malloc(sizeof(NODE)); p->rchild=create(t); } returnp;}voidpreorder(NODE*root)/*travelthetreeusingpreorder*/{ if(root!=NULL) {printf("%c"，root->data); preorder(root->lchild); preorder(root->rchild); }return;}voidinorder(NODE*root)/*travelthetreeusinginorder*/{ if(root!=NULL) { inorder(root->lchild); printf("%c"，root->data); inorder(root->rchild); } return;}voidpostorder(NODE*root)/*travelthetreeusingpostorder*/{ if(root!=NULL) { postorder(root->lchild); postorder(root->rchild); printf("%c"，root->data); }return;}程序2：線索二叉樹實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<stdlib.h>#include<malloc.h>structbtnode { chardata；/*datafield*/ intlbit；/*leftflagfield*/ intrbit；/*rightflagfield*/ structbtnode*lchild；/*leftpointerfield*/ structbtnode*rchild；/*rightpointerfieldò**/ };typedefstructbtnodeNODE;NODE*pre;voidmain(){NODE*create(NODE*p);voidinthread(NODE*root);NODE*q,*root;q=(NODE*)malloc(sizeof(NODE));printf("\nAtfirst,wecreateatree!\n");printf("Pleaseinputthedataofthetree!\n");root=create(q);inthread(root);}NODE*create(NODE*p)/*createastructureofbinarytree*/{ charch; NODE*t；/*supposethetypeofthedataisint*/ scanf("%c",&ch); if(ch=='') p=NULL; else {p->data=ch; p->lbit=0; t=(NODE*)malloc(sizeof(NODE)); p->lchild=create(t); t=(NODE*)malloc(sizeof(NODE)); p->rchild=create(t); } returnp;}voidinthread(NODE*root){voidinthreading(NODE**p);voidinvodth(NODE**h);NODE*t;t=((NODE*)malloc(sizeof(NODE)));t->lbit=0；t->rbit=1;t->rchild=t;if(root==NULL) t->lchild=t;else{pre=t; inthreading(&root)；/*producethethreadtreeusinginorder*/ t->lchild=root；/*thelastnodeformthethread*/ pre->rchild=t; pre->rbit=1; t->rchild=pre;}invodth(&t);}voidinthreading(NODE**p){ if((*p)!=NULL){inthreading(&((*p)->lchild))；/*leftsubtreeformthethread*/ if(((*p)->lchild)==NULL) {(*p)->lbit=1; (*p)->lchild=pre; } if(pre->rchild==NULL) {pre->rbit=1; pre->rchild=*p; } pre=*p; inthreading(&((*p)->rchild));/*rightsubtreeformthethread*/ }}voidinvodth(NODE**h)/*travelthebinarytreeusingtheinorderthread*/{NODE*p;p=(*h)->lchild;while(p!=(*h)){while(p->lbit==0) p=p->lchild; if(p->lbit==1) printf("%c",p->data); while(p->rbit==1&&p->rchild!=(*h)) { p=p->rchild; printf("%c",p->data); } p=p->rchild; }}

程序3：哈夫曼樹實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<stdlib.h>#include<malloc.h>#definem100structptree/*definethetypeofbinarytree*/{intw;structptree*lchild;structptree*rchild;};structpforest/*definethetypeofchainbelt*/{structpforest*link;structptree*root;};intWTL=0;voidmain(){structptree*hafm(intw[m],intn);voidtravel(structptree*head,intn);structptree*head;intn,i,w[m];printf("pleaseinputthesumofnode\n");scanf("%d",&n);printf("pleaseinputweightofeverynode\n");for(i=1;i<=n;i++)scanf("%d",&w[i]);head=hafm(w,n);travel(head,0);printf("ThelengthofthebestpathisWTL=%d",WTL);}voidtravel(structptree*head,intn){structptree*p;p=head;if(p!=NULL) {if((p->lchild)==NULL&&(p->rchild)==NULL) {printf("%d",p->w); printf("thehopsofthenodeis：%d\n",n); WTL=WTL+n*(p->w); } travel(p->lchild,n+1); travel(p->rchild,n+1); }}structptree*hafm(intw[m],intn){structpforest*inforest(structpforest*f，structptree*t);structpforest*p1,*p2,*f;structptree*ti,*t,*t1,*t2;inti;f=(structpforest*)malloc(sizeof(structpforest));f->link=NULL;for(i=1;i<=n;i++)/*producentreesthathaveonlyrootnode*/{ti=(structptree*)malloc(sizeof(structptree));ti->w=w[i];ti->lchild=NULL;ti->rchild=NULL;f=inforest(f,ti);}while(((f->link)->link)!=NULL)/*atleasthavetwobinarytrees*/{p1=f->link;p2=p1->link;f->link=p2->link；/*takeoutfrontaltwotrees*/t1=p1->root;t2=p2->root;free(p1);free(p2);t=(structptree*)malloc(sizeof(structptree));t->w=t1->w+t2->w；/*weightbeadded*/t->lchild=t1;t->rchild=t2；/*producethenewbinarytree*/f=inforest(f,t);}p1=f->link;t=p1->root;return(t);}structpforest*inforest(structpforest*f，structptree*t){structpforest*p，*q，*r;structptree*ti;r=(structpforest*)malloc(sizeof(structpforest));r->root=t;q=f;p=f->link;while(p!=NULL)/*lookforthepositiontobeinserted*/{ ti=p->root; if(t->w>ti->w) {q=p; p=p->link; }elsep=NULL；/*forceexitthecycle*/}r->link=q->link;q->link=r;return(f);}

實(shí)驗(yàn)五、圖操作一、實(shí)驗(yàn)?zāi)?．進(jìn)一步掌握?qǐng)D構(gòu)造及非線性特點(diǎn)，遞歸特點(diǎn)和動(dòng)態(tài)性。2．進(jìn)一步鞏固圖三種存儲(chǔ)構(gòu)造和二種遍歷辦法、最小生成樹兩種求解算法。二、實(shí)驗(yàn)內(nèi)容1．圖遍歷2．最小生成樹3．最短途徑4．每一對(duì)頂點(diǎn)之間最短途徑5．拓?fù)渑判蛉?shí)驗(yàn)規(guī)定1．用C++/C完畢算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。2．撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)成果和數(shù)據(jù)。3．分析算法，規(guī)定給出詳細(xì)算法分析成果，涉及時(shí)間復(fù)雜度和空間復(fù)雜度，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。四、程序?qū)崿F(xiàn)1．寫出每個(gè)操作算法（操作過程）2．程序運(yùn)營(yíng)狀況五、寫出輸入數(shù)據(jù)及運(yùn)營(yíng)成果六、源程序清單。

程序1：圖實(shí)現(xiàn)和運(yùn)算#include<stdio.h>#include<stdlib.h>#include<alloc.h>structnode{intvertex;structnode*next;};structheadnode{intvert;structnode*link;};main(){intt,n,i,visit[100]; intd[100]; structheadnode*adjlist(); voiddfs(); voidwfs(); structheadnode*head; printf("inputthesumofnodes:\n"); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&d[i]); head=adjlist(d,n); printf("1depthtravel\n"); printf("2widthtravel\n"); printf("pleaseinputthewayoftravelling\n"); scanf("%d",&t); switch(t) { case1: for(i=0;i<n;i++) visit[i]=0; dfs(head,1,visit); break; case2: wfs(head,n); break; default: printf("Theerror!"); }}structheadnode*adjlist(d,n) intn; int d[]; { structheadnodehead[100]; structnode*q,*p; inti,v1; for(i=0；i<n;i++) { head[i].vert=d[i]; head[i].link=NULL; printf("inputlinkedlistof\n"); scanf("%d",&v1); while(v1>=0) { p=(structnode*)malloc(sizeof(structnode)); p->vertex=v1; p->next=head[i].link; head[i].link=p; scanf("%d"，&v1); } }return(head);}voiddfs(head,k,visit) structheadnodehead[1000]; intk,visit[]; {inti; structnode*p; printf("v%d",k); visit[k]=1; p=head[k-1].link; while(p!=NULL) {if(visit[p->vertex]==0) dfs(head,p->vertex,visit); p=p->next; };return;}voidwfs(head,n)structheadnode*head;intn;{intvisit[1000],q[1000],f,r,k,u,m;structnode*p;for(k=0;k<n;k++)visit[k]=0;f=0;r=0;m=0;if(visit[m]==0) q[r]=(head+m)->vert; r=r+1; visit[m]=1;while(f!=r){u=q[f]; f=f+1; printf("v%d",u); p=(head+u-1)->link; while(p!=NULL) { if(visit[p->vertex-1]==0) {q[r]=p->vertex; r=r+1; visit[p->vertex-1]=1; } p=p->next; } }}程序2：最小生成樹#defineM30#defineMAX99#include<stdio.h>#include<stdlib.h>main(){voidprim();inti,j,n,g[100][100];printf("inputthesumofnodes:\n");scanf("%d",&n);printf("inputthecontentofadjtrix:\n");for(i=1;i<=n;i++)for(j=1;j<=n;j++) scanf("%d",&g[i][j]);prim(g,1,n);}voidprim(g,k,n)intg[100][100];intk,n;{inti,j,min,p;struct{intadjvex; intlowcost; }closedge[M];for(i=1;i<=n;i++)if(i!=k){closedge[i].adjvex=k;closedge[i].lowcost=g[k][i];}closedge[k].lowcost=0;for(i=1;i<=n;i++){p=1;min=MAX; for(j=1;j<=n;j++) if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) {min=closedge[j].lowcost; p=j; }if(min!=MAX) printf("%d%d%d\n",closedge[p].adjvex,p,min);closedge[p].lowcost=0;for(j=1;j<=n;j++)if(g[p][j]<closedge[j].lowcost) {closedge[j].lowcost=g[p][j]; closedge[j].adjvex=p; }}}程序3：最短途徑#defineM30#defineMAX99#include<stdio.h>#include<stdlib.h>main(){voidprim();inti,j,n,g[100][100];printf("inputthesumofnodes:\n");scanf("%d",&n);printf("inputthecontentofadjtrix:\n");for(i=1;i<=n;i++)for(j=1;j<=n;j++) scanf("%d",&g[i][j]);prim(g,1,n);}voidprim(g,k,n)intg[100][100];intk,n;{inti,j,min,p;struct{intadjvex; intlowcost; }closedge[M];for(i=1;i<=n;i++)if(i!=k){closedge[i].adjvex=k;closedge[i].lowcost=g[k][i];}closedge[k].lowcost=0;for(i=1;i<=n;i++){p=1;min=MAX; for(j=1;j<=n;j++) if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) {min=closedge[j].lowcost; p=j; }if(min!=MAX) printf("%d%d%d\n",closedge[p].adjvex,p,min);closedge[p].lowcost=0;for(j=1;j<=n;j++)if(g[p][j]<closedge[j].lowcost) {closedge[j].lowcost=g[p][j]; closedge[j].adjvex=p; }}}程序4：每一對(duì)頂點(diǎn)之間最短途徑（Floyd辦法）#defineM100#include<stdio.h>#include<stdlib.h>main(){voidfloyd();inti,j,n,ad[M][M],p[M][M];printf("inputthesumofnodes\n");scanf("%d",&n);for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&ad[i][j]);floyd(ad,p,n);for(i=0;i<n;i++){for(j=0;j<n;j++) printf("%d",p[i][j]); printf("\n"); }}voidfloyd(ad,p,n)intad[][M],p[][M],n;{inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++) {if(i==j) p[i][j]=0; else if(ad[i][j]<M) p[i][j]=i+1; elsep[i][j]=0; }for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(ad[i][k]+ad[k][j]<ad[i][j]) {ad[i][j]=ad[i][k]+ad[k][j]; p[i][j]=p[k][j]; }}程序5；拓?fù)渑判?defineM100#include<stdio.h>#include<stdlib.h>#include<alloc.h>structnode {intvertex; structnode*next; };structheadnode {intindegr; structnode*link; };main(){structheadnode*crtadj();structheadnode*head;voidtoposort();intn;printf("inputthesumofnodes\n");scanf("%d",&n);head=crtadj(n);toposort(head,n);}structheadnode*crtadj(n)intn;{structheadnodehead[100];structnode*p;inti,j;for(i=0;i<n;i++) {head[i].indegr=0; head[i].link=NULL; }printf("inputalldirectededges\n"); for(i=0;i<n;i++) {scanf("%d",&j); while(i!=j) {p=(structnode*)malloc(sizeof(structnode)); head[j-1].indegr=head[j-1].indegr+1; p->vertex=j; p->next=head[i].link; head[i].link=p; scanf("%d",&j); }}return(head);}voidtoposort(adjlist,n)structheadnode*adjlist;intn; { inthp,tp,j,i,k,q[M]; structnode*p; tp=0; for(i=1;i<=n;i++) if((adjlist+i-1)->indegr==0) { q[tp]=i; tp=tp+1; } hp=0; while(hp!=tp) {j=q[hp]; hp=hp+1; printf("C%d",j); p=(adjlist+j-1)->link; while(p!=NULL) {k=p->vertex; (adjlist+k-1)->indegr=(adjlist+k-1)->indegr-1; if((adjlist+k-1)->indegr==0) {q[tp]=k; tp=tp+1; } p=p->next; } }}