數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)講義

1、信息學(xué)院本科實(shí)驗(yàn)教學(xué)講義（實(shí)驗(yàn)）課程名稱：數(shù)據(jù)結(jié)構(gòu)貴州財(cái)經(jīng)學(xué)院教務(wù)處制2015 年 6 月目 錄實(shí)驗(yàn)項(xiàng)目一 線性表實(shí)驗(yàn)3一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求3二、實(shí)驗(yàn)準(zhǔn)備3三、實(shí)驗(yàn)基本操作流程及說明4實(shí)驗(yàn)項(xiàng)目二 棧和隊(duì)列實(shí)驗(yàn)12一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求12二、實(shí)驗(yàn)準(zhǔn)備12三、實(shí)驗(yàn)基本操作流程及說明13實(shí)驗(yàn)項(xiàng)目三 數(shù)組和串實(shí)驗(yàn)17一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求17二、實(shí)驗(yàn)準(zhǔn)備18三、實(shí)驗(yàn)基本操作流程及說明18四、實(shí)驗(yàn)測評(píng)與考核24實(shí)驗(yàn)項(xiàng)目四 樹和二叉樹實(shí)驗(yàn)25一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求25二、實(shí)驗(yàn)準(zhǔn)備25三、實(shí)驗(yàn)基本操作流程及說明26實(shí)驗(yàn)項(xiàng)目五 圖實(shí)驗(yàn)29一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求29二、實(shí)驗(yàn)準(zhǔn)備30三、實(shí)驗(yàn)基本操作

2、流程及說明30實(shí)驗(yàn)項(xiàng)目六 查找實(shí)驗(yàn)41一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求41二、實(shí)驗(yàn)準(zhǔn)備42三、實(shí)驗(yàn)基本操作流程及說明42實(shí)驗(yàn)項(xiàng)目七排序?qū)嶒?yàn)47一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求47二、實(shí)驗(yàn)準(zhǔn)備48三、實(shí)驗(yàn)基本操作流程及說明48實(shí)驗(yàn)項(xiàng)目八 綜合實(shí)驗(yàn)53一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求53二、實(shí)驗(yàn)準(zhǔn)備53三、實(shí)驗(yàn)基本操作流程及說明54實(shí)驗(yàn)測評(píng)與考核58實(shí)驗(yàn)項(xiàng)目一 線性表實(shí)驗(yàn)一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求（一）實(shí)驗(yàn)內(nèi)容線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)浇Y(jié)構(gòu)、基本操和應(yīng)用。（二）實(shí)驗(yàn)?zāi)繕?biāo)1使學(xué)生對(duì)線性表的順序存儲(chǔ)結(jié)構(gòu)、基本操作和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。使學(xué)生對(duì)線性表的線性表的鏈?zhǔn)浇Y(jié)構(gòu)、基本操作和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握

3、和應(yīng)用的目的。（三）實(shí)驗(yàn)要求實(shí)驗(yàn)前認(rèn)真預(yù)習(xí)實(shí)驗(yàn)內(nèi)容。實(shí)驗(yàn)時(shí)自覺遵守課堂紀(jì)律，嚴(yán)格按操作規(guī)程操作，既要獨(dú)立操作又要與其他同學(xué)配合，在實(shí)驗(yàn)過程中必須按照實(shí)驗(yàn)內(nèi)容認(rèn)真做完實(shí)驗(yàn)，并認(rèn)真填寫相關(guān)實(shí)驗(yàn)報(bào)告。二、實(shí)驗(yàn)準(zhǔn)備（一）運(yùn)行環(huán)境說明PC計(jì)算機(jī)，Windows 2000(或Windows XP) 及以上版本，C（二）基礎(chǔ)數(shù)據(jù)設(shè)置及說明計(jì)算機(jī)，Windows 2000(或Windows XP) 及以上版本，C均能正常運(yùn)行。說明以下概念1、線性表：2、順序表：3、鏈表：三、實(shí)驗(yàn)基本操作流程及說明（一）系統(tǒng)界面及說明 常用程序設(shè)計(jì)語言C與C+的上機(jī)調(diào)試環(huán)境為：Microsoft Visual C+6.0。為了

4、詳細(xì)說明Microsoft Visual C+6.0的使用以及如何在該環(huán)境下調(diào)試C語言程序，下面通過一個(gè)非常簡單的示例程序來介紹。 （二）操作步驟1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include#include#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的順序表長度*/#define INCREM 5 /*溢出時(shí)，順序表長度的增量*/typedef int ElemType; /*定義表元素的類型*/typedef struct SqlistElemType *slist; /*存儲(chǔ)空間的基地址*

5、/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 e);/* */int PrintList_sq(Sqlist *L); /*輸出順序表的元素*/int ListDelete_sq(Sqlist *L,int i); /*刪除第i個(gè)元素*/int ListLocate(Sqlist *L,Ele

6、mType 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; /*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(

7、!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*/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*

8、)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+; return OK;/*ListInsert*/*在順序表中刪除第i個(gè)元素*/int ListDelete_sq(Sqlist *L,int i)/*在順序表中查找指定值元素，返回其序號(hào)*/int ListLocate(Sqlist *L,ElemT

9、ype e) 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); scanf(%d,%d,&m,&k);

10、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 int ElemType; /*定義

11、表元素的類型*/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=(LinkList)malloc(sizeo

12、f(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*/void PrintList(LinkList L) LNode *p; p=L-next; /*p指向單鏈表的第1個(gè)元素*/ while(p!=NULL) printf(%5d,p-data); p=p-next; /*PrintList*/int GetElem(LinkList L,int i,ElemType *

13、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(please input n:); /*輸入單鏈表的元素個(gè)數(shù)*/ scanf(%d,&n); if(n0) printf(n1-Create LinkList:n); L=CreateList(n); printf(n2-Print LinkList

14、: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); return 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)測評(píng)與考核學(xué)生實(shí)驗(yàn)報(bào)告撰寫要求：1、考核實(shí)

15、驗(yàn)項(xiàng)目概念考核學(xué)生所須掌握實(shí)驗(yàn)項(xiàng)目的相關(guān)概念。 202、考核實(shí)驗(yàn)項(xiàng)目設(shè)計(jì)考核學(xué)生按實(shí)驗(yàn)項(xiàng)目規(guī)定的內(nèi)容編寫可執(zhí)行源代碼的能力。40% 3、考核實(shí)驗(yàn)結(jié)果考核學(xué)生能否根據(jù)實(shí)驗(yàn)項(xiàng)目完成后，設(shè)計(jì)的思路是否合理。20考核學(xué)生實(shí)驗(yàn)項(xiàng)目所編寫的執(zhí)行源代碼是否是獨(dú)立完成。20%學(xué)生實(shí)驗(yàn)成績?cè)u(píng)定規(guī)則及方法：1、實(shí)驗(yàn)報(bào)告格式要求學(xué)生須按實(shí)驗(yàn)報(bào)告格式要求逐項(xiàng)填寫。評(píng)分為：20分2、實(shí)驗(yàn)項(xiàng)目的設(shè)計(jì)學(xué)生須按實(shí)驗(yàn)項(xiàng)目規(guī)定的內(nèi)容編寫實(shí)驗(yàn)室的原理；程序流程圖；可執(zhí)行的源代碼，評(píng)分為：40分3、實(shí)驗(yàn)結(jié)果運(yùn)行結(jié)果，以屏幕拷貝形式填入實(shí)驗(yàn)報(bào)告中的實(shí)驗(yàn)結(jié)果欄內(nèi)。 評(píng)分為：20分4、實(shí)驗(yàn)項(xiàng)目結(jié)果是獨(dú)立完成。評(píng)分為：20分其他說明：1、對(duì)

16、于實(shí)驗(yàn)中的設(shè)計(jì)內(nèi)容，學(xué)生最好在實(shí)驗(yàn)課前做一些設(shè)計(jì)工作2、實(shí)驗(yàn)報(bào)告按規(guī)范格式書寫，在下次上課時(shí)交實(shí)驗(yàn)項(xiàng)目二 棧和隊(duì)列實(shí)驗(yàn)一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求（一）實(shí)驗(yàn)內(nèi)容棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)、基本操作和應(yīng)用。（二）實(shí)驗(yàn)?zāi)繕?biāo)使學(xué)生對(duì)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)、基本操作和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。要求學(xué)生對(duì)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的基本操作均作驗(yàn)證性實(shí)驗(yàn)，對(duì)棧和列的應(yīng)用各作一個(gè)設(shè)計(jì)性實(shí)驗(yàn)，并寫出實(shí)驗(yàn)報(bào)告。（三）實(shí)驗(yàn)要求實(shí)驗(yàn)前認(rèn)真預(yù)習(xí)實(shí)驗(yàn)內(nèi)容，實(shí)驗(yàn)時(shí)自覺遵守課堂紀(jì)律，嚴(yán)格按操作規(guī)程操作，既要獨(dú)立操作又要與其他同學(xué)配合，在實(shí)驗(yàn)過程中必須按照實(shí)驗(yàn)內(nèi)容認(rèn)真做完實(shí)驗(yàn)，并認(rèn)真填寫相關(guān)實(shí)

17、驗(yàn)報(bào)告。二、實(shí)驗(yàn)準(zhǔn)備（一）運(yùn)行環(huán)境說明見實(shí)驗(yàn)項(xiàng)目一的運(yùn)行環(huán)境說明。（二）基礎(chǔ)數(shù)據(jù)設(shè)置及說明見實(shí)驗(yàn)項(xiàng)目一的基礎(chǔ)數(shù)據(jù)設(shè)置及說明。說明一下概念1、順序棧：2、鏈棧：3、循環(huán)隊(duì)列：4、鏈隊(duì)三、實(shí)驗(yàn)基本操作流程及說明（一）系統(tǒng)界面及說明見實(shí)驗(yàn)項(xiàng)目一的系統(tǒng)界面及說明。（二）操作步驟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 /*存儲(chǔ)空間初始分配量*/#define STACKINCREMENT 5 /*

18、存儲(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(SqStack *S); /*創(chuàng)建棧*/void PrintStack(SqStack *

19、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,ElemType *e) /*Pop*/int CreateStack(SqStack *S)

20、 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) printf(%3d,e);/*Pop_and_Print*/int main() S

21、qStack 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#define M 20#define elemtype chartypedef

22、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-top+1; st-stackst-top=x; void pop(stacknod

23、e *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); else printf(not match)!n); return 0;l 輸入：2

24、+(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)測評(píng)與考核學(xué)生實(shí)驗(yàn)報(bào)告撰寫要求：1、考核實(shí)驗(yàn)項(xiàng)目概念考核學(xué)生所須掌握實(shí)驗(yàn)項(xiàng)目的相關(guān)概念。 202、考核實(shí)驗(yàn)項(xiàng)目設(shè)計(jì)考核學(xué)生按實(shí)驗(yàn)項(xiàng)目規(guī)定的內(nèi)容編寫可執(zhí)行源代碼的能力。40% 3、考核實(shí)驗(yàn)結(jié)果考核學(xué)生能否根據(jù)實(shí)驗(yàn)項(xiàng)目完成后，設(shè)計(jì)的思路是否合理。20考核學(xué)生實(shí)驗(yàn)項(xiàng)目所編寫的執(zhí)行源代碼是否是獨(dú)立完成。20%學(xué)生實(shí)驗(yàn)成績?cè)u(píng)定規(guī)則及方法：1、實(shí)驗(yàn)報(bào)告格式要求學(xué)生須按實(shí)驗(yàn)報(bào)告格式要求逐項(xiàng)填寫。評(píng)分為：20分2、實(shí)驗(yàn)項(xiàng)目的設(shè)計(jì)學(xué)生須按實(shí)驗(yàn)項(xiàng)目規(guī)定的內(nèi)容編寫實(shí)驗(yàn)室的原理

25、；程序流程圖；可執(zhí)行的源代碼，評(píng)分為：40分3、實(shí)驗(yàn)結(jié)果運(yùn)行結(jié)果，以屏幕拷貝形式填入實(shí)驗(yàn)報(bào)告中的實(shí)驗(yàn)結(jié)果欄內(nèi)。 評(píng)分為：20分4、實(shí)驗(yàn)項(xiàng)目結(jié)果是獨(dú)立完成。評(píng)分為：20分其他說明：1、對(duì)于實(shí)驗(yàn)中的設(shè)計(jì)內(nèi)容，學(xué)生最好在實(shí)驗(yàn)課前做一些設(shè)計(jì)工作2、實(shí)驗(yàn)報(bào)告按規(guī)范格式書寫，在下次上課時(shí)交實(shí)驗(yàn)項(xiàng)目三 數(shù)組和串實(shí)驗(yàn)一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求（一）實(shí)驗(yàn)內(nèi)容數(shù)組的使用、串的模式匹配算法（二）實(shí)驗(yàn)?zāi)繕?biāo)使學(xué)生對(duì)數(shù)組運(yùn)算和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。使學(xué)生對(duì)串的模式匹配算法和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。（三）實(shí)驗(yàn)要求實(shí)驗(yàn)前認(rèn)真預(yù)習(xí)實(shí)驗(yàn)內(nèi)容，實(shí)驗(yàn)時(shí)自覺遵守課堂紀(jì)律，嚴(yán)格按操作規(guī)程操作，既要獨(dú)立操作又要

26、與其他同學(xué)配合，在實(shí)驗(yàn)過程中必須按照實(shí)驗(yàn)內(nèi)容認(rèn)真做完實(shí)驗(yàn)，并認(rèn)真填寫相關(guān)實(shí)驗(yàn)報(bào)告。二、實(shí)驗(yàn)準(zhǔn)備（一）運(yùn)行環(huán)境說明見實(shí)驗(yàn)項(xiàng)目一的運(yùn)行環(huán)境說明。（二）基礎(chǔ)數(shù)據(jù)設(shè)置及說明見實(shí)驗(yàn)項(xiàng)目一的基礎(chǔ)數(shù)據(jù)設(shè)置及說明。三、實(shí)驗(yàn)基本操作流程及說明（一）系統(tǒng)界面及說明見實(shí)驗(yàn)項(xiàng)目一的系統(tǒng)界面及說明。（二）操作步驟1、運(yùn)行下列程序，通過修改N的值，說明函數(shù)功能。并和教材P89程序3-24函數(shù)功能進(jìn)行比較，說明比較結(jié)構(gòu)。/*求1000!的值，值中2的個(gè)數(shù)，階乘值的位數(shù) 大數(shù)的階乘 分析：階乘的定義就是n! = (n-1)!*n，但是有基本的初始條件的，即0! = 1 因此1! = 1*0! = 1 * 1 = 1; 2!

27、= 2*1! = 2 * 1 = 2; 依次類推，但是當(dāng)n足夠大時(shí)，整型根本無法裝下n的階乘，如果用C+語言的整型或浮點(diǎn)型變量來實(shí)現(xiàn)的話，根本不可能，會(huì)產(chǎn)生溢出階乘也無非是乘法和加法罷了，如4!= 24;可以用數(shù)組來存各位，數(shù)組的起始長度是1，每當(dāng)遇到超過長度時(shí)，就自加1，不過這里要稍微處理下的，以倒過來存，以便做乘法的，可以這樣來存。 4! 存 4 2 此時(shí)4!的長度為24的長度2 5! = 5 * 4!，可以用5去乘以4等于20，20取余20%10=0，如果大于10則需向高位進(jìn)位5*4/10，下一位的結(jié)果就等于下一位乘以5*2加上剛才的進(jìn)位得12，12對(duì)10余2保存，12整除10得1 最后

28、移位反過來存0 2 1 5! 存 0 2 1 此時(shí)5!的長度為120的長度3 6! =6*5! 6*0=0 在對(duì)10取余的0 保存，無進(jìn)位，然后6*2=12，12對(duì)10整除=1作為進(jìn)位數(shù)，12對(duì)10取余=2保存，最后6*1+1（上一次的進(jìn)位）=7保存 最后保存0 2 7 6! 存 0 2 7 此時(shí)5!的長度為720的長度3 .依次類推 1000!=1000*999! */#include using namespace std; #define N 1000 / 所需求的N的階乘static int aN*3; / 保存階乘的各位，從a1開始存儲(chǔ)，方向存放階乘值，輸出時(shí)倒序輸出int main

29、() int i,j; /循環(huán)控制變量 int len = 1; /階乘值的位數(shù) int tem,carry; /tem為乘積加進(jìn)位值，carry為上次乘積的進(jìn)位值 int count_2=0;/記錄階乘值中2的個(gè)數(shù) a1 = 1; /1的階乘 for (i = 2;i=N;i+) /求階乘的方法 carry = 0; /新一輪乘積要將進(jìn)位重新置0 for (j=1;j=1;i-) /輸出各位，逆序輸出 coutai; if(ai=2) count_2+; coutendl; coutN的階乘共 len位endl; coutN!中2的個(gè)數(shù)為：count_2endl; return 0; 2、#

30、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;for(

31、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(s2.da

32、ta); 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 s,su

33、b; 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=0;is

34、ublen;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;break;

35、 while(n); return 0;l 運(yùn)行程序輸入：1studentstudents2Computer Data Stuctures104運(yùn)行結(jié)果：3、（選做題）實(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

36、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

37、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

38、); 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)測評(píng)與考核學(xué)生實(shí)驗(yàn)報(bào)告撰寫要求：1、考核實(shí)驗(yàn)項(xiàng)目概念考核學(xué)生所須掌握實(shí)驗(yàn)項(xiàng)目的相關(guān)概念。 2

39、02、考核實(shí)驗(yàn)項(xiàng)目設(shè)計(jì)考核學(xué)生按實(shí)驗(yàn)項(xiàng)目規(guī)定的內(nèi)容編寫可執(zhí)行源代碼的能力。40% 3、考核實(shí)驗(yàn)結(jié)果考核學(xué)生能否根據(jù)實(shí)驗(yàn)項(xiàng)目完成后，設(shè)計(jì)的思路是否合理。20考核學(xué)生實(shí)驗(yàn)項(xiàng)目所編寫的執(zhí)行源代碼是否是獨(dú)立完成。20%學(xué)生實(shí)驗(yàn)成績?cè)u(píng)定規(guī)則及方法：1、實(shí)驗(yàn)報(bào)告格式要求學(xué)生須按實(shí)驗(yàn)報(bào)告格式要求逐項(xiàng)填寫。評(píng)分為：20分2、實(shí)驗(yàn)項(xiàng)目的設(shè)計(jì)學(xué)生須按實(shí)驗(yàn)項(xiàng)目規(guī)定的內(nèi)容編寫實(shí)驗(yàn)室的原理；程序流程圖；可執(zhí)行的源代碼，評(píng)分為：40分3、實(shí)驗(yàn)結(jié)果運(yùn)行結(jié)果，以屏幕拷貝形式填入實(shí)驗(yàn)報(bào)告中的實(shí)驗(yàn)結(jié)果欄內(nèi)。 評(píng)分為：20分4、實(shí)驗(yàn)項(xiàng)目結(jié)果是獨(dú)立完成。評(píng)分為：20分其他說明：1、對(duì)于實(shí)驗(yàn)中的設(shè)計(jì)內(nèi)容，學(xué)生最好在實(shí)驗(yàn)課前做一些設(shè)計(jì)工

40、作2、實(shí)驗(yàn)報(bào)告按規(guī)范格式書寫，在下次上課時(shí)交實(shí)驗(yàn)項(xiàng)目四 樹和二叉樹實(shí)驗(yàn)一、實(shí)驗(yàn)內(nèi)容、目標(biāo)及要求（一）實(shí)驗(yàn)內(nèi)容樹的先序遍歷、中序遍歷、后序遍歷、層次遍歷算法。線索化二叉樹生成和遍歷算法。（二）實(shí)驗(yàn)?zāi)繕?biāo)使學(xué)生 對(duì)二叉樹的先序遍歷、中序遍歷、后序遍歷、層次遍歷算法應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。使學(xué)生 對(duì)線索化二叉樹生成和遍歷算法、哈夫曼樹的構(gòu)造算法，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。（三）實(shí)驗(yàn)要求實(shí)驗(yàn)前認(rèn)真預(yù)習(xí)實(shí)驗(yàn)內(nèi)容，實(shí)驗(yàn)時(shí)自覺遵守課堂紀(jì)律，嚴(yán)格按操作規(guī)程操作，既要獨(dú)立操作又要與其他同學(xué)配合，在實(shí)驗(yàn)過程中必須按照實(shí)驗(yàn)內(nèi)容認(rèn)真做完實(shí)驗(yàn)，并認(rèn)真填寫相關(guān)實(shí)驗(yàn)報(bào)告。二、實(shí)驗(yàn)準(zhǔn)備（一）運(yùn)行環(huán)境說明見實(shí)

41、驗(yàn)項(xiàng)目一的運(yùn)行環(huán)境說明。（二）基礎(chǔ)數(shù)據(jù)設(shè)置及說明見實(shí)驗(yàn)項(xiàng)目一的基礎(chǔ)數(shù)據(jù)設(shè)置及說明。1、二叉樹：2、遞歸遍歷：3、非遞歸遍歷：4、層序遍歷：三、實(shí)驗(yàn)基本操作流程及說明（一）系統(tǒng)界面及說明見實(shí)驗(yàn)項(xiàng)目一的系統(tǒng)界面及說明。（二）操作步驟1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果，并畫出二叉樹的形態(tài)。#include#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;voi

42、d 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); /*遞歸建立右子

43、樹*/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-lchild