《數(shù)據(jù)結(jié)構(gòu)與算法》實驗要求與指導(dǎo)

1、數(shù)據(jù)結(jié)構(gòu)與算法實驗要求與指導(dǎo)（二）算法實驗要求綜述我們把實驗要求分成四個層次 , 希望學(xué)生不斷往更高層次要求自己 , 最終能達到本課程 的實驗基本要求 .這四個層次的要求是：一. 以熟練使用 c 語言的開發(fā)環(huán)境 （如 TC2.0 或 VC6.0） 為主，進行簡單問題的程序設(shè)計 和調(diào)試分析二 . 編寫主程序調(diào)用調(diào)試教材中描述并在課堂中詳細(xì)講解過的算法三 . 完成習(xí)題中的算法設(shè)計題并書寫實驗報告四. 獨立完成一個小的應(yīng)用系統(tǒng)并規(guī)范書寫實驗報告， 以進一步提高算法描述和算法分 析的能力以上一至三層次作為本課程的基本實驗要求，第四層次作為有能力的學(xué)生的提高要求。 實驗輔導(dǎo)教師也可以根據(jù)當(dāng)?shù)貙W(xué)生的具體情

2、況 , 本著能提高學(xué)生兩個能力 （C 語言的編程和 調(diào)試能力 , 算法設(shè)計和分析能力 ）的目的 , 循序漸進地引導(dǎo)學(xué)生掌握算法和程序的上機實驗 , 并參考題集的實驗報告范例書寫實驗報告。按教學(xué)計劃， 本課程實驗課時為 15學(xué)時，安排 6-7 次實驗。由于課時數(shù)有限， 要求學(xué)生 在實驗前作好充分準(zhǔn)備，否則很難在兩個學(xué)時內(nèi)完成相關(guān)的上機與調(diào)試。上機前的準(zhǔn)備工作 主要有兩項：一是仔細(xì)閱讀理解書中的相關(guān)算法，需要寫解題算法的還要在紙上寫好算法； 二是準(zhǔn)備好要調(diào)試算法的數(shù)據(jù)，并寫好調(diào)用算法的主程序。實驗1至實驗6都分為A、B兩個實驗。A實驗對應(yīng)第二層次的能力培養(yǎng)訓(xùn)練，B實驗對應(yīng)第三層次的能力培養(yǎng)訓(xùn)練。下

3、面就每一層次的要求作如下說明。一. 以熟練使用c語言的開發(fā)環(huán)境（如TC2.0或VC6.0）為主，進行一般問題的程序設(shè)計 和調(diào)試分析該能力實際上是預(yù)修課 C語言的要求，由于有相當(dāng)部分學(xué)生C語言掌握不是很好，影響了 數(shù)據(jù)結(jié)構(gòu)算法的描述和理解所以開始應(yīng)該注意彌補C語言的能力根據(jù)經(jīng)驗，C語言中函數(shù)定義與調(diào)用（形參和實參的對應(yīng)等） ， 指針， 類型定義與使用、結(jié)構(gòu)的定義和使用、動態(tài) 內(nèi)存的申請等難點卻是數(shù)據(jù)結(jié)構(gòu)算法描述的重點 ， C 語言的這些障礙嚴(yán)重影響了學(xué)生對數(shù)據(jù) 結(jié)構(gòu)與算法的理解，也影響了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的興趣. 所以實驗指導(dǎo)教師在鼓勵學(xué)生主動補習(xí)C 語言知識的同時 ， 有意識安排一些符合學(xué)生基礎(chǔ)的程

4、序設(shè)計練習(xí)作為本課程實驗的前導(dǎo)補 充. 與本課程的相公的算法題目可以推后幾周上機.本實驗教學(xué)計劃的預(yù)備實驗（即實驗0）是為完成該任務(wù)而設(shè)計的。如果學(xué)生的困難比較大，盡量在教學(xué)計劃時間以外鼓勵學(xué)生多做上機，打好基礎(chǔ)。二. 編寫主程序調(diào)用調(diào)試教材中描述并在課堂中詳細(xì)講解過的算法 為加深對課堂講解的算法的理解，選擇部分（尤其是基礎(chǔ)部分，如線性表，堆棧與隊列等的順序和鏈?zhǔn)酱鎯Φ淖畛Ｓ玫幕静僮鳎┧惴ㄟM行上機調(diào)試，如第二章的InitList_Sq 、Listlnsert_Sq 和 ListDelete_Sq 組算法和第三章的 InitStack 、GotTop、Push 和 Pop 組算法等。 這些算法

5、是后面章節(jié)更復(fù)雜算法的基礎(chǔ) （如樹和圖中的算法） ，算法的積累過程象 滾雪球，所以基礎(chǔ)必不可少。調(diào)試這些算法要注意兩點。一是適當(dāng)修改教材算法中的非C語言的語句和增加部分局部變量的定義。由于算法的描述是類C語言的，所以要改為完整的 C語言的函數(shù)。不過需要修改（增加）的地方不多。二是書寫一個主程序來調(diào)用并調(diào)試描述算法的函數(shù)。主程序的設(shè)計 要根據(jù)算法的功能和調(diào)試需要來編寫。本實驗教學(xué)計劃的實驗 1至實驗6的A實驗是為完成該任務(wù)而設(shè)計的。三. 完成習(xí)題中的算法設(shè)計題并書寫實驗報告我們在題集的每章的算法設(shè)計題中選擇少量“小問題”的算法設(shè)計練習(xí)，以培養(yǎng)和 提高學(xué)生自己動手寫算法的能力。這些算法或者與教材中

6、基本算法類似，或者是延伸，或者 是它們的應(yīng)用。做這些算法設(shè)計題時，要注意過程的完整性：題目理解、功能分析、算法思想、描述算 法的C函數(shù)、調(diào)用算法的主程序、運行結(jié)果、調(diào)試過程的體會等等，都盡可能書寫出來。養(yǎng) 成書寫文檔的好習(xí)慣。本實驗教學(xué)計劃的實驗 1至實驗6的B實驗是為完成該任務(wù)而設(shè)計的。四完成一個小的應(yīng)用系統(tǒng)并規(guī)范書寫實驗報告，以進一步提高算法描述和算法分析的能力本實驗教學(xué)計劃沒有列出相應(yīng)的實驗內(nèi)容。有余力的學(xué)生可以選擇一到二個題集中 的實習(xí)題做。（三）算法實驗內(nèi)容與指導(dǎo)實驗0: C語言中函數(shù)定義與調(diào)用、指針和類型的定義與使用、結(jié)構(gòu)的定義、動態(tài)內(nèi)存的申請等預(yù)備知識（1）實驗?zāi)康模夯仡檹?fù)習(xí)C語

7、言的重點與難點，熟悉C程序調(diào)試環(huán)境，掌握一個完整程序的構(gòu)成，為以后的實驗打下基礎(chǔ)。（2）實驗要求：熟練掌握C語言及其上機調(diào)試環(huán)境（如TC2.0或VC6.0）的操作使用。（3）實驗內(nèi)容：根據(jù)學(xué)生基礎(chǔ)，選擇若干編程題（如 C語言中函數(shù)定義與調(diào)用、指針和類型的定義與使用、 結(jié)構(gòu)的定義、動態(tài)內(nèi)存的申請等），進行編譯、連接和運行調(diào) 試。掌握動態(tài)跟蹤調(diào)試方法。（4）實驗指導(dǎo)：可以選擇簡單的問題編程，不要求算法的難度，但要能使用相關(guān)C語言成分。把注意力集中在編譯和連接錯誤的修改，運行數(shù)據(jù)的輸入輸出和結(jié)果分析上。實驗1 :線性表的順序表示與鏈?zhǔn)奖硎镜牟迦肱c刪除1. A實驗：算法調(diào)試（1）實驗?zāi)康模杭由罾斫饩€性

8、表的順序表示與鏈?zhǔn)奖硎镜囊饬x和區(qū)別，理解用它們表 示時插入與刪除操作的算法。（2）實驗要求：理解 InitList_Sq、Listlnsert_Sq、ListDelete_Sq 和 InitList_L、Listlnsert_L 、ListDelete_L等算法。（3）實驗內(nèi)容：設(shè)計一組輸入數(shù)據(jù)并編寫主程序分別調(diào)用上述算法（順序表示的算法為 In itList_Sq 、ListI nsert_Sq、ListDelete_Sq 等，鏈?zhǔn)奖硎镜?算法為InitList_L、ListInsert_L 、ListDelete_L 等），調(diào)試程序并對相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗證輸出的

9、結(jié)果，加深對有關(guān)算法的理解。(4) 實驗指導(dǎo)：順序表示和鏈?zhǔn)奖硎究梢苑殖蓛蓚€程序來調(diào)試(見示例程序1和2)教材中的算法一般要作少許修改才能運行，這些修改包括：1、算法函數(shù)中局部變量的定義，如ListInsert_Sq 中的 i,newbase,p,q 等；2、 可能出現(xiàn)的“類” C語言的語句，必須改為C語言語句，如數(shù)據(jù)交換語句x y;3、 如果采用TC作為C語言調(diào)試環(huán)境，算法函數(shù)的“引用”類型參數(shù)要改為指針類型參數(shù)并修改程序中的使用方法，如List In sert_Sq 中的參數(shù)&L要改為*L。程序中使用L方法的修改見示例程序1。一個簡單程序通常主要由三部分構(gòu)成：1、常量定義( #define

10、 )，類型定義 (typedef) 及函數(shù)原型定義 (#include) ；2、算法函數(shù)，即 InitList_Sq 、 ListInsert_Sq 、 ListDelete_Sq 等；3、主函數(shù)。示例程序1， InitList_Sq 、 ListInsert_Sq 、 ListDelete_Sq 在 TC2.0 中的調(diào)試：#include stdio.h#include malloc.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define

11、LIST_INIT_SIZE 10#define LISTINCREMENT 4typedef int Status;typedef int ElemType;typedef structElemType *elem;int length;int listsize;SqList;Status InitList_Sq(SqList *L)L-elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L-elem) return(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;return

12、 OK;Status ListInsert_Sq(SqList *L,int i,ElemType e)ElemType *q,*p,*newbase;if (iL-length+1) return ERROR;if (L-length=L-listsize)newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) return(OVERFLOW); L-elem=newbase;L-listsize+=LISTINCREMENT;q=&(L-elemi-1);for

13、(p=&(L-elemL-length-1);p=q;-p) *(p+1)=*p; *q=e;+L-length;return OK;Status ListDelete_Sq(SqList *L,int i,ElemType *e) ElemType *p,*q;if (iL-length) return ERROR; p=&(L-elemi-1);*e=*p; q=(L-elem+L-length-1);for (+p;plength;return OK;void main()SqList Lst;int i,n=15;ElemType e;if (InitList_Sq(&Lst)=OK)

14、 for(i=1;i=n;i+)if(ListInsert_Sq(&Lst,i,i)!=OK) break; printf(n);for (i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi); getch();if (ListDelete_Sq(&Lst,10,&e)=OK) printf(delete_elem=%dn,e); getch();for (i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi);else printf(delete_elem is failedn);在 VC6.0 中

15、的調(diào)試：示例程序2,InitList_L、Listlnsert_L 、ListDelete_L#include math.h#include malloc.h#include stdio.h#define ERROR 0#define TRUE 1#define FLASE 0#define OK 1#define INFEASIBLE -1#define OVERFLOW -2typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;Status ListInsert_L(LinkList &L, int i

16、, ElemType e) LinkList s,p;int j; p = L; j = 0;while(p&jnext;+j; if(!p|ji-1) return ERROR;s = (Lnode *)malloc(sizeof(Lnode); if(!s) return OVERFLOW;s-data = e;s-next = p-next; p-next = s; return OK;Status ListDelete_L(LinkList &L, int i, ElemType &e) LinkList s,p;int j; p = L; j = 0;while(p-next & j

17、next;+j; if(!(p-next)|ji-1) return ERROR;s = p-next; p-next = s-next;e = s-data; free(s); return OK;Status InitList_L(LinkList &L) L = (Lnode *)malloc(sizeof(Lnode);if (L) L-next = NULL;return OK;elsereturn ERROR;int cmp(Event a, Event b);Status OrderInsert_L(LinkList &L, ElemType e, int (*cmp)(Even

18、t a, Event b) Lnode *p,*q;p=(Lnode *)malloc(sizeof(Lnode);if(!p)return(OVERFLOW);p-data = e;q=L;while(q-next & cmp(e,q-next-data)0)q=q-next;p-next = q-next;q-next = p;return OK;int EmptyList(LinkList L)if(!L-next) return 1;return 0;LinkList GetHead(LinkList L)if(!L-next) return NULL;return L-next;St

19、atus DelFirst(LinkList L, LinkList &p)p = L-next;if(!p) return ERROR;L-next = p-next;return OK;void mai n()/主程序略2 . B實驗：練習(xí)2.11(1) 實驗?zāi)康模杭由罾斫饩€性表的順序表示的插入操作的算法，學(xué)會使用現(xiàn)有算法來解 決其他問題。(2) 實驗要求：進一步理解Ini tList_Sq 、List In sert_Sq算法并在其他問題中的使用。(3) 實驗內(nèi)容：設(shè)計一組輸入數(shù)據(jù)并編寫主程序。調(diào)試程序并對相應(yīng)的輸出作出分析； 修改輸入數(shù)據(jù)，預(yù)期輸出并驗證輸出的結(jié)果。(4) 實驗指導(dǎo)：第

20、一步，編寫主程序，首先讀入數(shù)據(jù)并保存在順序表中(可以用ListI nsert_Sq進行逐個插入，也可以用循環(huán)語句直接讀入數(shù)組中)，然后讀入一個待插入的數(shù)x;再尋找x應(yīng)該插入的順序表中的位置i，然后調(diào)用List In sert_Sq插入第i個元素即可。第二步，設(shè)計調(diào)試數(shù)據(jù)，例如一組遞增有序輸入數(shù)據(jù)(1,3,5,6,7,9,12)以及一個待插入的數(shù)x=8。調(diào)試程序。能夠正確插入后再考驗算法的“健壯性”。第三步，再取x=0或x=15或x=6進行調(diào)試，以考驗算法在“邊界情況”下的正確性。即插入在表頭，表尾以及有重復(fù)情況的插入是否正確。還可以再考慮一組遞增有序輸入 數(shù)據(jù)為空表時插入元素的正確性。實驗2

21、:順序棧的實現(xiàn)與插入刪除操作1. A實驗：基本算法調(diào)試及數(shù)制的轉(zhuǎn)換算法(1) 實驗?zāi)康模杭由罾斫忭樞驐５囊饬x，理解用它的插入與刪除操作的算法。(2) 實驗要求：理解 In itStack 、StackEmpty、Push、Pop 和 con version 等算法。(3) 實驗內(nèi)容：用數(shù)制的轉(zhuǎn)換算法調(diào)試順序棧的基本操作算法。編寫主程序調(diào)用數(shù)制的轉(zhuǎn)換 con version 算法，再由 con version 調(diào)用 In itStack 、StackEmpty、Push、Pop 算法。用不同的數(shù)轉(zhuǎn)換成不同的進制調(diào)試程序并對相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù), 預(yù)期輸出并驗證輸出的結(jié)果，加深對Pus

22、h和Pop算法的理解。(4) 實驗指導(dǎo)： 建立程序的三部分構(gòu)架:1、常量定義(#define ),類型定義(typedef)及函數(shù)原型定義(#include);2、算法函數(shù)，即 Ini tStack 、StackEmpty、Push 和 Pop con version 等；3、主函數(shù)。示例程序1,In itStack、StackEmpty、Push 和 Pop、con version 等在 VC6.0 中的調(diào)試:typedef int SElemType;typedef struct在棧構(gòu)造之前和銷毀之后,base 的值為 NULL*/SElemType *base; /*SElemType

23、*top; /*棧頂指針 */int stacksize; /*當(dāng)前已分配的存儲空間，以元素為單位*/SqStack;#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 0typedef int Status;#include #include Status InitStack(SqStack &s) s.base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s.bas

24、e) return(OVERFLOW);s.top = s.base;s.stacksize = STACK_INIT_SIZE; return OK; /* InitStack */Status Push(SqStack &s, SElemType e) SElemType *l_temp;if (s.top - s.base = s.stacksize)/* 棧滿，追加存儲空間 */ l_temp=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT) *sizeof(SElemType);if (!l_temp) return(OV

25、ERFLOW); s.base = l_temp;s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;*(s.top+) = e; return OK; /* Push */Status Pop(SqStack &s, SElemType &e) if (s.top = s.base)return ERROR; e = *(-s.top);return OK; /* Pop */int StackEmpty(SqStack s)if(s.base = s.top) return 1; else return 0;void conversion()SqStack s;int N,b;SEIemType e;In itStack(s);sca nf(%d %d,&N,&b);while(b=2 & N)Push(s, N%b);N = N/b;while(!StackEmpty(s)Pop(s, e);prin tf(%d,e); /* con vers ion */void main (void)con versi on();2 . B實驗：練習(xí)3.15(1)