《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)大綱

數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)大綱一、實(shí)驗(yàn)?zāi)康耐ㄟ^該課程的實(shí)驗(yàn)練習(xí)，使學(xué)生能夠進(jìn)一步掌握各種數(shù)據(jù)結(jié)構(gòu)以及建立在此基礎(chǔ)上的算法的基本知識(shí)；進(jìn)一步理解各種基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)；進(jìn)一步掌握數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系；培養(yǎng)學(xué)生設(shè)計(jì)有效的算法及設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的能力。解決或者答疑同學(xué)們?cè)诶碚撜n程學(xué)習(xí)過程中所遇到的問題。二、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)O：C語言中函數(shù)定義與調(diào)用、指針和類型的定義與使用、結(jié)構(gòu)的定義、動(dòng)態(tài)內(nèi)存的申請(qǐng)等預(yù)備知識(shí)（1） 實(shí)驗(yàn)?zāi)康模夯仡檹?fù)習(xí)C語言的重點(diǎn)與難點(diǎn)，熟悉C程序調(diào)試環(huán)境，掌握一個(gè)完整程序的構(gòu)成，為以后的實(shí)驗(yàn)打下基礎(chǔ)。（2） 實(shí)驗(yàn)要求：熟練掌握C語言及其上機(jī)調(diào)試環(huán)境（如TC2.0或VC6.0）的操作使用。（3） 實(shí)驗(yàn)內(nèi)容：根據(jù)學(xué)生基礎(chǔ)，選擇若干編程題（如C語言中函數(shù)定義與調(diào)用、指針和類型的定義與使用、結(jié)構(gòu)的定義、動(dòng)態(tài)內(nèi)存的申請(qǐng)等），進(jìn)行編譯、連接和運(yùn)行調(diào)試。掌握動(dòng)態(tài)跟蹤調(diào)試方法。（4） 實(shí)驗(yàn)指導(dǎo)：可以選擇簡(jiǎn)單的問題編程，不要求算法的難度，但要能使用相關(guān)C語言成分。把注意力集中在編譯和連接錯(cuò)誤的修改，運(yùn)行數(shù)據(jù)的輸入輸出和結(jié)果分析上。實(shí)驗(yàn)1：線性表的順序表示與鏈?zhǔn)奖硎镜牟迦肱c刪除A實(shí)驗(yàn)：算法調(diào)試（1） 實(shí)驗(yàn)?zāi)康模杭由罾斫饩€性表的順序表示與鏈?zhǔn)奖硎镜囊饬x和區(qū)別，理解用它們表示時(shí)插入與刪除操作的算法。（2） 實(shí)驗(yàn)要求：理解InitList_Sq、ListInsert_Sq、ListDelete_Sq和InitList_L、ListInsert_L、ListDelete_L等算法。（3） 實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)一組輸入數(shù)據(jù)并編寫主程序分別調(diào)用上述算法（順序表示的算法為InitList_Sq、ListInsert_Sq、ListDelete_Sq等，鏈?zhǔn)奖硎镜乃惴镮nitList_L、ListInsert_L、ListDelete_L等），調(diào)試程序并對(duì)相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗(yàn)證輸出的結(jié)果，加深對(duì)有關(guān)算法的理解。（4） 實(shí)驗(yàn)指導(dǎo)：順序表示和鏈?zhǔn)奖硎究梢苑殖蓛蓚€(gè)程序來調(diào)試（見示例程序1和2）。教材中的算法一般要作少許修改才能運(yùn)行，這些修改包括：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ù)并修改程序中的使用方法，如Listlnsert_Sq中的參數(shù)&L要改為*L。程序中使用L方法的修改見示例程序1。一個(gè)簡(jiǎn)單程序通常主要由三部分構(gòu)成：1、 常量定義(#define),類型定義(typedef)及函數(shù)原型定義(#include)；2、 算法函數(shù)，即InitList_Sq、ListInsert_Sq、ListDelete_Sq等；3、 主函數(shù)。示例程序1,InitList_Sq、Listlnsert_Sq、ListDelete_Sq在VC6.0中的調(diào)試:#include"stdio.h"#include"malloc.h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_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;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+LISTINCREMENT)*sizeof(ElemType));if(!newbase)return(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}q=&(L->elem[i-1]);for(p=&(L->elem[L->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->length))returnERROR;p=&(L->elem[i-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.length;i++)printf("i,e=%d,%d\n",i,Lst.elem[i]);getch();if(ListDelete_Sq(&Lst,10,&e)==OK){printf("delete_elem=%d\n",e);getch();for(i=0;i<Lst.length;i++)printf("i,e=%d,%d\n",i,Lst.elem[i]);}elseprintf("delete_elemisfailed\n");}}示例程序2,InitList_L、Listlnsert_L、ListDelete_L在VC6.0中的調(diào)試:#include"math.h"#include"malloc.h"#include"stdio.h"#defineERROR0#defineTRUE1#defineFLASE0#defineOK1#defineINFEASIBLE-1#defineOVERFLOW-2typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;StatusListInsert_L(LinkList&L,inti,ElemTypee){LinkLists,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<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,ElemTypee,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(LinkListL){if(!L->next)returnNULL;returnL->next;}StatusDelFirst(LinkListL,LinkList&p){p=L->next;if(!p)returnERROR;L->next=p->next;returnOK;}voidmain(){//主程序略}B實(shí)驗(yàn)：練習(xí)2.11設(shè)數(shù)據(jù)表va中的數(shù)據(jù)元素遞增有序，試寫一個(gè)程序，將x插入到順序表的適當(dāng)位置，以保持該表的有序性。實(shí)驗(yàn)?zāi)康模杭由罾斫饩€性表的順序表示的插入操作的算法，學(xué)會(huì)使用現(xiàn)有算法來解決其他問題。實(shí)驗(yàn)要求：進(jìn)一步理解InitList_Sq、ListInsert_Sq算法并在其他問題中的使用。實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)一組輸入數(shù)據(jù)并編寫主程序。調(diào)試程序并對(duì)相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗(yàn)證輸出的結(jié)果。實(shí)驗(yàn)指導(dǎo)：第一步，編寫主程序，首先讀入數(shù)據(jù)并保存在順序表中(可以用ListInsert_Sq進(jìn)行逐個(gè)插入，也可以用循環(huán)語句直接讀入數(shù)組中)，然后讀入一個(gè)待插入的數(shù)X；再尋找x應(yīng)該插入的順序表中的位置i,然后調(diào)用Listlnsert_Sq插入第i個(gè)元素即可。第二步，設(shè)計(jì)調(diào)試數(shù)據(jù)，例如一組遞增有序輸入數(shù)據(jù)(1,3,5,6,7,9,12)以及一個(gè)待插入的數(shù)x=8。調(diào)試程序。能夠正確插入后再考驗(yàn)算法的“健壯性”第三步，再取x=0或x=15或x=6進(jìn)行調(diào)試，以考驗(yàn)算法在“邊界情況”下的正確性。即插入在表頭,表尾以及有重復(fù)情況的插入是否正確。還可以再考慮一組遞增有序輸入數(shù)據(jù)為空表時(shí)插入元素的正確性。程序示例：#include"stdio.h"#include"malloc.h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_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;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+LISTINCREMENT)*sizeof(ElemType));if(!newbase)return(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}q=&(L->elem[i-1]);for(p=&(L->elem[L->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->length))returnERROR;p=&(L->elem[i-1]);*e=*p;q=(L->elem+L->length-1);for(++p;p<=q;++p)*(p-1)=*p;--L->length;returnOK;}intFindPos_Sq(SqListLst,ElemTypee)){//確定e在有序表中的位置(第i個(gè)元素之前)inti;for(i=Lst.langth-1;i>=0;i--)if(Lst.elem[i]<=e)returni+2;return1;}voidmain(){SqListLst;inti,n=15;ElemTypee;if(InitList_Sq(&Lst)==OK){printf("輸入n個(gè)有序整數(shù)\n");for(i=1;i<=n;i++){scanf(“%d”,&e);if(ListInsert_Sq(&Lst,i,e)!=OK)break;}printf("n個(gè)有序整數(shù)為：\n");for(i=0;i<Lst.length;i++)printf("i,e=%d,%d\n",i,Lst.elem[i]);getch();printf("輸入要插入的整數(shù)x:\n");scanf("%d",&e);if(i=FindPos_Sq(Lst,e)){ //確定e在有序表中的位置if(ListInsert_Sq(&Lst,i,e)!=OK)printf("Insertingelementisfailed\n");}else{printf("插入的數(shù)x以后，整數(shù)序列成為：\n");for(i=0;i<Lst.length;i++)printf("i,e=%d,%d\n",i,Lst.elem[i]);}}實(shí)驗(yàn)2：順序棧的實(shí)現(xiàn)與插入刪除操作A實(shí)驗(yàn):基本算法調(diào)試及數(shù)制的轉(zhuǎn)換算法實(shí)驗(yàn)?zāi)康模杭由罾斫忭樞驐５囊饬x，理解用它的插入與刪除操作的算法。實(shí)驗(yàn)要求：理解InitStack、StackEmpty、Push、Pop和conversion等算法。實(shí)驗(yàn)內(nèi)容：用數(shù)制的轉(zhuǎn)換算法調(diào)試順序棧的基本操作算法。編寫主程序調(diào)用數(shù)制的轉(zhuǎn)換conversion算法，再由conversion調(diào)用InitStack、StackEmpty、Push、Pop算法。用不同的數(shù)轉(zhuǎn)換成不同的進(jìn)制調(diào)試程序并對(duì)相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗(yàn)證輸出的結(jié)果，加深對(duì)Push和Pop算法的理解。實(shí)驗(yàn)指導(dǎo)：建立程序的三部分構(gòu)架：1、 常量定義(#define),類型定義(typedef)及函數(shù)原型定義(#include)；2、 算法函數(shù)，即InitStack、StackEmpty、Push和Pop、conversion等；3、 主函數(shù)。示例程序1,InitStack、StackEmpty、Push和Pop、conversion等在VC6.0中的調(diào)試：typedefintSElemType;typedefstruct{SElemType*base;/*在棧構(gòu)造之前和銷毀之后，base的值為NULL*/SElemType*top;/*棧頂指針*/intstacksize;/*當(dāng)前已分配的存儲(chǔ)空間，以元素為單位*/}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)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)/*棧滿，追加存儲(chǔ)空間*/{l_temp=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!l_temp)return(OVERFLOW);s.base=l_temp;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("%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();}三、實(shí)驗(yàn)選題、報(bào)告要求與評(píng)分一）實(shí)驗(yàn)選題本次的考核實(shí)驗(yàn)報(bào)告可以選擇以下任一實(shí)驗(yàn)，也可以自擬題目的實(shí)驗(yàn)。1、第1個(gè)可選題目設(shè)計(jì)一個(gè)模擬簡(jiǎn)單整數(shù)計(jì)算器的程序。該程序可以接受整數(shù)數(shù)據(jù)，運(yùn)算符可以接受包含（,）,+,-,*,/,%,和A（求幕運(yùn)算符,aAb=ab）的中綴表達(dá)式，并求出結(jié)果。如果表達(dá)式正確，則輸出表達(dá)式的結(jié)果；如果表達(dá)式非法，則輸出錯(cuò)誤信息。輸入要求：程序從“input.txt”.文件中讀取信息，在這個(gè)文件中如果有多個(gè)中綴表達(dá)式，則每個(gè)表達(dá)式獨(dú)占一行，程序的讀取操作在文件的結(jié)尾處停止。輸出要求：對(duì)于每一個(gè)表達(dá)式，將其結(jié)果放在“output.txt”文件的每一行中。這些結(jié)果可能是值（精確到小數(shù)點(diǎn)后兩位），也可能是錯(cuò)誤信息“ERRORININFIXNOTATION，輸入例子：499+599+699*1(3*5*(4+8)%2)2人2人31+2(2/0(2-4)A32%22%5輸出例子:1797256ERRORININFIXNOTATIONERRORININFIXNOTATION-8022、 第2個(gè)可選題目完成字符文章（長(zhǎng)度可達(dá)數(shù)兆）進(jìn)行Huffman編碼的算法的完整程序。對(duì)給定的文本文件，進(jìn)行編碼和解碼。具體的要求可以自主確定。3、 第3個(gè)可選題目有哪些排序算法，請(qǐng)?jiān)O(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)并實(shí)現(xiàn)排序算法，至少選擇兩種或以上的排序算法進(jìn)行實(shí)現(xiàn)，分析其算法復(fù)雜度，通過實(shí)測(cè)數(shù)據(jù)對(duì)比其運(yùn)行效率。二）實(shí)驗(yàn)報(bào)告格式與內(nèi)容的要求：實(shí)驗(yàn)報(bào)告首先要求有一個(gè)清晰醒目的報(bào)告標(biāo)題，例如：“《數(shù)據(jù)結(jié)構(gòu)與算法》期末實(shí)驗(yàn)XXXXXXXXXX”。報(bào)告至少要求具備以下四部分內(nèi)容：一、 簡(jiǎn)介這一部分需簡(jiǎn)單介紹題目?jī)?nèi)容，即該實(shí)驗(yàn)到底要做什么。如果涉及明確的算法，最好再簡(jiǎn)單介紹一下算法產(chǎn)生的背景。基本要求：實(shí)驗(yàn)內(nèi)容必須覆蓋完備。二、 算法說明這一部分需詳細(xì)描述解決問題所需要用到的算法和重要的數(shù)據(jù)結(jié)構(gòu)，即該實(shí)驗(yàn)到底應(yīng)該怎么做?；疽螅核刑幚韱栴}中所用到的關(guān)鍵算法都要描述清楚，而不是僅描述主函數(shù)。算法和數(shù)據(jù)結(jié)構(gòu)用偽碼和圖示描述，千萬不要只寫源代碼加注釋。這一部分的目的是讓讀者在短時(shí)間內(nèi)對(duì)作者解決問題的整體思路有個(gè)清楚的了解，表達(dá)方式必須比源代碼通俗易懂。如果讀者感覺還不如直接讀源代碼來得明白，這一部分就失去了意義。三、 測(cè)試結(jié)果這一部分需根據(jù)題目類型設(shè)計(jì)提供相應(yīng)