數(shù)據(jù)結(jié)構(gòu)與算法試驗大綱88538

1、數(shù)據(jù)結(jié)構(gòu)與算法實驗大綱（一）遠程教育輔導教師基本條件（要求）1,熟練掌握C語言及其調(diào)試開發(fā)環(huán)境；2 .具有用C語言編寫調(diào)試中等規(guī)模以上（數(shù)百行源碼）程序的經(jīng)驗；3,掌握數(shù)據(jù)結(jié)構(gòu)與算法課程有關的知識，具有較好的算法設計和分析的能力4 .有一定的教學經(jīng)驗。（二）算法實驗要求綜述根據(jù)目前遠程教育計算機專業(yè)的學生的實際情況和他們的C語言基礎，嚴格按照本科教學要求進行算法實驗上機并完成相應的實驗報告，對多數(shù)學生是有一定困難的.為適應不同基礎的學生循序漸進地學習，我們把實驗要求分成四個層次，希望學生不斷往更高層次要求自己，最終能達到本課程的實驗基本要求.這四個層次的要求是：1 .以熟練使用c語言的開發(fā)環(huán)境

2、（如TC2.0或VC6.0）為主，進行簡單問題的程序設計和調(diào)試分析二,編寫主程序調(diào)用調(diào)試教材中描述并在課堂中詳細講解過的算法三,完成習題中的算法設計題并書寫實驗報告四,獨立完成一個小的應用系統(tǒng)并規(guī)范書寫實驗報告，以進一步提高算法描述和算法分析的能力以上一至三層次作為本課程的基本實驗要求，第四層次作為有能力的學生的提高要求。實驗輔導教師也可以根據(jù)當?shù)貙W生的具體情況，本著能提高學生兩個能力（C語言的編程和調(diào)試能力，算法設計和分析能力）的目的，循序漸進地引導學生掌握算法和程序的上機實驗并參考題集的實驗報告范例書寫實驗報告。按教學計劃，本課程實驗課時為15學時，安排6-7次實驗。由于課時數(shù)有限，要求學

3、生在實驗前作好充分準備，否則很難在兩個學時內(nèi)完成相關的上機與調(diào)試。上機前的準備工作主要有兩項：一是仔細閱讀理解書中的相關算法，需要寫解題算法的還要在紙上寫好算法；二是準備好要調(diào)試算法的數(shù)據(jù)，并寫好調(diào)用算法的主程序。實驗1至實驗6都分為A、B兩個實驗。A實驗對應第二層次的能力培養(yǎng)訓練，B實驗對應第三層次的能力培養(yǎng)訓練。下面就每一層次的要求作如下說明。2 .以熟練使用c語言的開發(fā)環(huán)境（如TC2.0或VC6.0）為主，進行一般問題的程序設計和調(diào)試分析該能力實際上是預修課C語言的要求，由于有相當部分學生C語言掌握不是很好，影響了數(shù)據(jù)結(jié)構(gòu)算法的描述和理解,所以開始應該注意彌補C語言的能力,根據(jù)經(jīng)驗，C語

4、言中函數(shù)定義與調(diào)用（形參和實參的對應等），指針，類型定義與使用、結(jié)構(gòu)的定義和使用、動態(tài)內(nèi)存的申請等難點卻是數(shù)據(jù)結(jié)構(gòu)算法描述的重點，C語言的這些障礙嚴重影響了學生對數(shù)據(jù)結(jié)構(gòu)與算法的理解，也影響了學習數(shù)據(jù)結(jié)構(gòu)的興趣,所以實驗指導教師在鼓勵學生主動補習C語言知識的同時，有意識安排一些符合學生基礎的程序設計練習作為本課程實驗的前導補充.與本課程的相公的算法題目可以推后幾周上機.本實驗教學計劃的預備實驗（即實驗0）是為完成該任務而設計的。如果學生的困難比較大，盡量在教學計劃時間以外鼓勵學生多做上機，打好基礎。3 .編寫主程序調(diào)用調(diào)試教材中描述并在課堂中詳細講解過的算法為加深對課堂講解的算法的理解，選擇部

5、分（尤其是基礎部分，如線性表，堆棧與隊列等的順序和鏈式存儲的最常用的基本操作）算法進行上機調(diào)試，如第二章的InitList_Sq、ListInsert_Sq和ListDelete_Sq一組算法和第三章的InitStack、GotTop、Push和Pop一組算法等。這些算法是后面章節(jié)更復雜算法的基礎（如樹和圖中的算法），算法的積累過程象滾雪球，所以基礎必不可少。調(diào)試這些算法要注意兩點。一是適當修改教材算法中的非C語言的語句和增加部分局部變量的定義。由于算法的描述是類C語言的，所以要改為完整的C語言的函數(shù)。不過需要修改（增加）的地方不多。二是書寫一個主程序來調(diào)用并調(diào)試描述算法的函數(shù)。主程序的設計要

6、根據(jù)算法的功能和調(diào)試需要來編寫。本實驗教學計劃的實驗1至實驗6的A實驗是為完成該任務而設計的。4 .完成習題中的算法設計題并書寫實驗報告我們在題集的每章的算法設計題中選擇少量“小問題”的算法設計練習，以培養(yǎng)和提高學生自己動手寫算法的能力。這些算法或者與教材中基本算法類似，或者是延伸，或者是它們的應用。做這些算法設計題時，要注意過程的完整性：題目理解、功能分析、算法思想、描述算法的C函數(shù)、調(diào)用算法的主程序、運行結(jié)果、調(diào)試過程的體會等等，都盡可能書寫出來。養(yǎng)成書寫文檔的好習慣。本實驗教學計劃的實驗1至實驗6的B實驗是為完成該任務而設計的。5 .完成一個小的應用系統(tǒng)并規(guī)范書寫實驗報告，以進一步提高算

7、法描述和算法分析的能力本實驗教學計劃沒有列出相應的實驗內(nèi)容。有余力的學生可以選擇一到二個題集中的實習題做。（三）算法實驗內(nèi)容與指導實驗0:C語言中函數(shù)定義與調(diào)用、指針和類型的定義與使用、結(jié)構(gòu)的定義、動態(tài)內(nèi)存的申請等預備知識（1）實驗目的：回顧復習C語言的重點與難點，熟悉C程序調(diào)試環(huán)境，掌握一個完整程序的構(gòu)成，為以后的實驗打下基礎。（2）實驗要求：熟練掌握C語言及其上機調(diào)試環(huán)境（如TC2.0或VC6.0）的操作使用。（3）實驗內(nèi)容：根據(jù)學生基礎，選擇若干編程題（如C語言中函數(shù)定義與調(diào)用、指針和類型的定義與使用、結(jié)構(gòu)的定義、動態(tài)內(nèi)存的申請等），進行編譯、連接和運行調(diào)試。掌握動態(tài)跟蹤調(diào)試方法。（4）

8、實驗指導：可以選擇簡單的問題編程，不要求算法的難度，但要能使用相關C語言成分。把注意力集中在編譯和連接錯誤的修改，運行數(shù)據(jù)的輸入輸出和結(jié)果分析上。實驗1:線性表的順序表示與鏈式表示的插入與刪除1. A實驗：算法調(diào)試(1) 實驗目的：加深理解線性表的順序表示與鏈式表示的意義和區(qū)別，理解用它們表示時插入與刪除操作的算法。(2) 實驗要求：理解In1List_Sq、ListInsert_Sq、ListDelete_Sq和InitList_L、ListInsert_L、ListDelete_L等算法。(3) 實驗內(nèi)容：設計一組輸入數(shù)據(jù)并編寫主程序分別調(diào)用上述算法(順序表示的算法為InitList_Sq

9、、ListInsert_Sq、ListDelete_Sq等，鏈式表示的算法為InitList_L、ListInsert_L、ListDelete_L等)，調(diào)試程序并對相應的輸出作出分析；修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結(jié)果，加深對有關算法的理解。(4) 實驗指導：順序表示和鏈式表示可以分成兩個程序來調(diào)試(見示例程序1和2)c教材中的算法一般要作少許修改才能運行，這些修改包括：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ù)的

10、“引用”類型參數(shù)要改為指針類型參數(shù)并修改程序中的使用方法，如ListInsert_Sq中的參數(shù)&L要改為*L。程序中使用L方法的修改見示例程序1。一個簡單程序通常主要由三部分構(gòu)成：1、常量定義(#define),類型定義(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.

11、h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstructElemType*elem;intlength;intlistsize;SqList;StatusInitList_Sq(SqList*L)L->elem=(ElemType*)malloc(LIST_INIT_SIZE*si

12、zeof(ElemType);if(!L->elem)return(OVERFLOW);L->length=0;L->listsize=LIST_INIT_SIZE;returnOK;StatusListInsert_Sq(SqList*L,inti,ElemTypee)ElemType*q,*p,*newbase;if(i<1|i>L->length+1)returnERROR;if(L->length>=L->listsize)newbase=(ElemType*)realloc(L->elem,(L->listsize+L

13、ISTINCREMENT)*sizeof(ElemType);if(!newbase)return(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;q=&(L->elemi-1);for(p=&(L->elemL->length-1);p>=q;-p)*(p+1)=*p;*q=e;+L->length;returnOK;StatusListDelete_Sq(SqList*L,inti,ElemType*e)ElemType*p,*q;if(i<1)|(i>L->

14、;length)returnERROR;p=&(L->elemi-1);*e=*p;q=(L->elem+L->length-1);for(+p;p<=q;+p)*(p-1)=*p;-L->length;returnOK;voidmain()SqListLst;inti,n=15;ElemTypee;if(InitList_Sq(&Lst)=OK)for(i=1;i<=n;i+)if(ListInsert_Sq(&Lst,i,i)!=OK)break;printf("n");for(i=0;i<Lst.len

15、gth;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;i<Lst.length;i+)printf("i,e=%d,%dn",i,Lst.elemi);elseprintf("delete_elemisfailedn");在VC6.0中的調(diào)試:示例程序2,InitList_L、ListInsert_L、

16、ListDelete_L#include"math.h"#include"malloc.h"#include"stdio.h"#defineERROR0#defineTRUE1#defineFLASE0#defineOK1#defineINFEASIBLE-1#defineOVERFLOW-2typedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;StatusListInsert_L(LinkList&L,inti,ElemTypee)LinkLists,

17、p;intj;p=L;j=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)returnERROR;s=(Lnode*)malloc(sizeof(Lnode);if(!s)returnOVERFLOW;s->data=e;s->next=p->next;p->next=s;returnOK;StatusListDelete_L(LinkList&L,inti,ElemType&e)LinkLists,p;intj;p=L;j=0;while(p->next&&j&

18、lt;i-1)p=p->next;+j;if(!(p->next)|j>i-1)returnERROR;s=p->next;p->next=s->next;e=s->data;free(s);returnOK;StatusInitList_L(LinkList&L)L=(Lnode*)malloc(sizeof(Lnode);if(L)L->next=NULL;returnOK;elsereturnERROR;intcmp(Eventa,Eventb);StatusOrderInsert_L(LinkList&L,ElemType

19、e,int(*cmp)(Eventa,Eventb)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;returnOK;intEmptyList(LinkListL)if(!L->next)return1;return0;LinkListGetHead(LinkLis

20、tL)(if(!L->next)returnNULL;returnL->next;)StatusDelFirst(LinkListL,LinkList&p)(p=L->next;if(!p)returnERROR;L->next=p->next;returnOK;)voidmain()/主程序略)2.B實驗：練習2.11(1)實驗目的：加深理解線性表的順序表示的插入操作的算法，學會使用現(xiàn)有算法來解決其他問題。(2)實驗要求：進一步理解InitList_Sq、ListInsert_Sq算法并在其他問題中的使用。(3)實驗內(nèi)容：設計一組輸入數(shù)據(jù)并編寫主程序。調(diào)

21、試程序并對相應的輸出作出分析；修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結(jié)果。(4)實驗指導：第一步，編寫主程序，首先讀入數(shù)據(jù)并保存在順序表中(可以用ListInsert_Sq進行逐個插入，也可以用循環(huán)語句直接讀入數(shù)組中)，然后讀入一個待插入的數(shù)x;再尋找x應該插入的順序表中的位置i,然后調(diào)用ListInsert_Sq插入第i個元素即可。第二步，設計調(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)試，以考驗算法在“邊界情況”下的正確性。即插入在表頭，表尾以及有重復情況的插

22、入是否正確。還可以再考慮一組遞增有序輸入數(shù)據(jù)為空表時插入元素的正確性。實驗2:順序棧的實現(xiàn)與插入刪除操作1. A實驗：基本算法調(diào)試及數(shù)制的轉(zhuǎn)換算法(1)實驗目的：加深理解順序棧的意義，理解用它的插入與刪除操作的算法。(2)實驗要求：理解InitStack、StackEmpty、Push、Pop和conversion等算法。(3)實驗內(nèi)容：用數(shù)制的轉(zhuǎn)換算法調(diào)試順序棧的基本操作算法。編寫主程序調(diào)用數(shù)制的轉(zhuǎn)換conversion算法，再由conversion調(diào)用InitStack、StackEmpty、Push、Pop算法。用不同的數(shù)轉(zhuǎn)換成不同的進制調(diào)試程序并對相應的輸出作出分析；修改輸入數(shù)據(jù),預期

23、輸出并驗證輸出的結(jié)果，加深對Push和Pop算法的理解。(4)實驗指導：建立程序的三部分構(gòu)架：1、常量定義(#define),類型定義(typedef)2、算法函數(shù)，即InitStack、StackEmpty、3、主函數(shù)。及函數(shù)原型定義(#include);Push和Pop、conversion等；conversion等在VC6.0中的調(diào)試:typedefintSElemType;typedefstructSElemType*base;/*SElemType*top;/*intstacksize;/*在棧構(gòu)造之前和銷毀之后,棧頂指針*/base的值為NULL*/當前已分配的存儲空間，以元素為單

24、位*/示例程序1,InitStack、StackEmpty、Push和Pop、SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineOVERFLOW-1#defineERROR0typedefintStatus;#include<malloc.h>#include<stdio.h>StatusInitStack(SqStack&s)s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!s.base)

25、return(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;/*InitStack*/StatusPush(SqStack&s,SElemTypee)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(OVERFLOW);s.base=l_temp

26、;s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*(s.top+)=e;returnOK;/*Push*/StatusPop(SqStack&s,SElemType&e)if(s.top=s.base)returnERROR;e=*(-s.top);returnOK;/*Pop*/intStackEmpty(SqStacks)if(s.base=s.top)return1;elsereturn0;voidconversion()SqStacks;intN,b;SElemTypee;InitStack(s);scanf(

27、"%d%d",&N,&b);while(b>=2&&N)Push(s,N%b);N=N/b;while(!StackEmpty(s)Pop(s,e);printf("%d",e);/*conversion*/voidmain(void)conversion();2.B實驗：練習3.15(1)實驗目的：加深對堆棧理解，學會靈活運用已有知識，拓廣思路。(2)實驗要求：按照對InitStack、StackEmpty、Push、Pop等算法理解，理解雙向棧的含義與意義，建立與調(diào)試對雙向棧的基本操作算法。(3)實驗內(nèi)容：設計一

28、組對雙向棧的操作算法InitStackTws、StackTwsEmpty、PushTwsPopTws并編寫一個主程序調(diào)試它們。設計一組輸入數(shù)據(jù)并對相應的輸出作出分析；著重調(diào)試空棧、滿棧時的情況。(4)實驗指導：第一步，理解雙向棧的意義是為了節(jié)省空間，減少棧溢出(滿棧)機會。第二步，寫出雙向棧的操作算法InitStackTws、StackTwsEmpty、PushTwsPopTws)第三步，編寫主程序。第四步，設計若干組數(shù)據(jù)調(diào)試來算法。實驗3:鏈式隊列與循環(huán)隊列的實現(xiàn)與插入刪除操作1.A實驗：循環(huán)隊列的實現(xiàn)算法(1)實驗目的：(2)實驗要求：(3)實驗內(nèi)容：(4)實驗指導：示例程序，InitQu

29、eue、EnQueueDeQueue等在VC6.0或TC2.0中的調(diào)試：#defineNULL0#defineERROR0#defineOVERFLOW-2#defineOK1#defineMAXSIZE10typedefintQElemType;typedefintStatus;typedefstructQElemType*base;intfront;intrear;intsize;SqQueue;StatusInitQueue(SqQueue*Q)Q->base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType);if(!Q->base)e

30、xit(OVERFLOW);Q->front=Q->rear=0;Q->size=0;StatusEnQueue(SqQueue*Q,QElemTypee)if(Q->rear+1)%MAXSIZE=Q->front)returnERROR;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXSIZE;returnOK;StatusDeQueue(SqQueue*Q,QElemType*e)if(Q->front=Q->rear)returnERROR;*e=Q->baseQ->front

31、;Q->front=(Q->front+1)%MAXSIZE;returnOK;main()SqQueueQ;QElemTypee,x;inti;InitQueue(&Q);for(i=1;i<=12;i+)scanf("%d",&e);if(EnQueue(&Q,e)=ERROR)printf("toomanynumberinput!n");)DeQueue(&Q,&x);DeQueue(&Q,&x);e=12;EnQueue(&Q,e);while(DeQueue(&a

32、mp;Q,&x)printf("e=%dn",x);)2. B實驗：練習3.28(1)實驗目的：(2)實驗要求：(3)實驗內(nèi)容：(4)實驗指導：實驗4:數(shù)組的順序存儲表示1. A實驗：數(shù)組的順序存儲表示實現(xiàn)與調(diào)試(1)實驗目的：(2)實驗要求：(3)實驗內(nèi)容：(4)實驗指導：示例程序，InitArray、DestroyArray、Assign、Value等在VC6.0中的調(diào)試:#include<malloc.h>#include<stdio.h>#include<stdarg.h># defineOK1# defineERROR-

33、1# defineOVERFLOW-2# defineNULL0# defineUNDERFLOW-3typedefintElemType;# defineMAX_ARRAY_DIM8typedefstructElemType*base;intdim;int*bounds;int*constants;Array;typedefintStatus;StatusInitArray(Array&A,intdim,.)va_listap;intelemtotal,i;if(dim<1|dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=

34、(int*)malloc(dim*sizeof(int);if(!A.bounds)return(OVERFLOW);elemtotal=1;va_start(ap,dim);for(i=0;i<dim;+i)A.boundsi=va_arg(ap,int);if(A.boundsi<0)returnUNDERFLOW;elemtotal*=A.boundsi;va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType);if(!A.base)return(OVERFLOW);A.constants=(int*)mal

35、loc(dim*sizeof(int);if(!A.constants)return(OVERFLOW);A.constantsdim-1=1;for(i=dim-2;i>=0;-i)A.constantsi=A.boundsi+1*A.constantsi+1;returnOK;StatusDestroyArray(Array&A)if(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;returnOK;)StatusLocate(ArrayA,va_listap,int&off)(inti,ind;off=0;for(i=0;i<A.dim;+i)ind=va_arg(ap,int);if(ind<0|ind>=A.boundsi)returnOVERFLOW;off+=A.constantsi*ind;)returnOK;)StatusValue(ArrayA,ElemType*e,.)va_listap;va_st