數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)題

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)題內(nèi)容概要：對(duì)于計(jì)算機(jī)學(xué)科而言，實(shí)踐非常重要，它是檢驗(yàn)讀者對(duì)理論知識(shí)的掌握程度，同時(shí)加深讀者對(duì)所學(xué)知識(shí)的理解和運(yùn)用，本附錄為讀者布置了七道上機(jī)實(shí)驗(yàn)題，分別對(duì)應(yīng)于教材的第二章至第四章及第六章至第九章的內(nèi)容。實(shí)驗(yàn)一線性表實(shí)驗(yàn)?zāi)康模菏煜語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一一單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一一單鏈表中的各種基本操作。實(shí)驗(yàn)內(nèi)容：順序線性表的建立、插入及刪除。鏈?zhǔn)骄€性表的建立、插入及刪除。實(shí)驗(yàn)步驟：建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L=（21,23,14,5,56,17,31},然后在第i個(gè)位置插入元素68o建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。實(shí)現(xiàn)提示：由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。在此，我們利用c語(yǔ)言的結(jié)構(gòu)體類型定義順序表：#defineMAXSIZE1024typedefintelemtype;/*線性表中存放整型元素*/typedefstruct{elemtypevec[MAXSIZE];intlen;/*順序表的長(zhǎng)度*/}sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。注意如何取到第1個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：typedefintelemtype;typedefstructnode{elemtypedata;//數(shù)據(jù)域structnode*next;//指針域}linklist;注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)mallocQ,如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：p=(lniklist*)malloc(sizeof(luiklist));?語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為Iniklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)丘ee(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值(NULL)o思考與提高：如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。在main函數(shù)里如果去掉1=&&語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？實(shí)驗(yàn)二棧實(shí)驗(yàn)?zāi)康模赫莆諚５捻樞虮硎竞蛯?shí)現(xiàn)實(shí)驗(yàn)內(nèi)容：編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。實(shí)驗(yàn)步驟：初始化順序棧插入元素刪除棧頂元素取棧頂元素遍歷順序棧置空順序棧實(shí)現(xiàn)提示：/*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedefstruct{Datatypestack[MAXNUM];inttop;JSqStack;/*初始化順序棧函數(shù)*/voidInitStack(SqStack*p){q=(SqStack*)malloc(sizeof(SqStack)/★申請(qǐng)空間★/}/*入棧函數(shù)*/voidPush(SqStack*pfDatatypex){if(p->top<MAXNUM-l)(p->top=p->top+l;/*棧頂+1"p->stack[p->top]=x;/★數(shù)據(jù)入?！?/*出棧函數(shù)*/DatatypePop(SqStack*p)

x=p->stack[p->top];/★將棧頂元素賦給x*/p->top=p->top-l;/★棧頂_[★//*獲取棧頂元素函數(shù)★/DatatypeGetTop(SqStack*p){x=p->stack[p->top];}/*遍歷順序棧函數(shù)*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)printf("第*d個(gè)數(shù)據(jù)元素是:%6d\nu,izp->stack[i]);/★置空順序棧函數(shù)★/voidsetEmpty(SqStack*p){p->top=-1;}思考與提高:voidsetEmpty(SqStack*p){p->top=-1;}思考與提高:讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別?實(shí)驗(yàn)三隊(duì)列實(shí)驗(yàn)?zāi)康模赫莆贞?duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。實(shí)驗(yàn)步驟：初始化并建立鏈隊(duì)列入鏈隊(duì)列出鏈隊(duì)列遍歷鏈隊(duì)列實(shí)現(xiàn)提示：/*定義鏈隊(duì)列*/typedefstructQnode{Datatypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;JLqueue;/*初始化并建立鏈隊(duì)列函數(shù)?/voidcreat(Lqueue*q){h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始彳匕申請(qǐng)空間★/h->next=NULL;q->front=h;q->rear=h;for(i=l;i<=n;i++)/*利用循環(huán)快速輸入數(shù)據(jù)*/{scanf(H%d,f,&x);Lappend(qzx);/*利用入鏈隊(duì)列函數(shù)快速輸入數(shù)據(jù)*/)/*入鏈隊(duì)列函數(shù)★/voidLappend(Lqueue*qfintx){s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;/*出鏈隊(duì)列函數(shù)*/DatatypeLdelete(Lqueue*q){p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);/★釋放空間★//*遍歷鏈隊(duì)列函數(shù)★/voiddisplay(Lqueue*q){while(p!=NULL)/★利用條件判斷是否到隊(duì)尾★/(printf(n%d-->nzp->data);p=p->next;思考與提高:鏈棧只有一個(gè)top指針，對(duì)于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針?實(shí)驗(yàn)四樹及二叉樹

實(shí)驗(yàn)?zāi)康?通過(guò)實(shí)驗(yàn)，掌握二叉樹的建立與存儲(chǔ)通過(guò)實(shí)驗(yàn)，掌握二叉樹的遍歷方法實(shí)驗(yàn)內(nèi)容：練習(xí)二叉樹的建立與存儲(chǔ)練習(xí)二叉樹的遍歷實(shí)驗(yàn)步驟：建立自己的頭文件BmTiee.h,內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。建立二叉樹，并通過(guò)調(diào)用函數(shù)，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。實(shí)現(xiàn)提示：建立二叉樹的代碼如下：BinTNode*CreateBinTree()//輸入二叉樹的先序遍歷序列，創(chuàng)建二叉鏈表{BinTNode*t;//如果讀入0,創(chuàng)建空樹charch;ch=getchar();if(ch==,0//如果讀入0,創(chuàng)建空樹t=(BinTNode*)malloc(sizeof(BinTNode));〃申請(qǐng)根結(jié)點(diǎn)空間t->data=ch;//將結(jié)點(diǎn)數(shù)據(jù)ch放入跟結(jié)點(diǎn)的數(shù)據(jù)域t->lchild=CreateBinTree();//建左子樹t->rchild=CreateBinTree();//建右子樹}returnt;}思考與提高：如何用孩子兄弟表示法存儲(chǔ)樹?熟悉并掌握哈夫曼樹及其應(yīng)用。實(shí)驗(yàn)五圖實(shí)驗(yàn)?zāi)康模赫莆請(qǐng)D的基本存儲(chǔ)方法；掌握有關(guān)圖的操作算法并用高級(jí)語(yǔ)言實(shí)現(xiàn)；熟練掌握?qǐng)D的兩種搜索路徑的遍歷方法。實(shí)驗(yàn)內(nèi)容：假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一些區(qū)域中的重要場(chǎng)所，孤代表己有的公交線路，孤上的權(quán)表示該線路上的票價(jià)(或搭乘所需時(shí)間)，試設(shè)計(jì)一個(gè)簡(jiǎn)易交通指南系統(tǒng)，指導(dǎo)前來(lái)咨詢者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一場(chǎng)所到達(dá)另一場(chǎng)所。實(shí)驗(yàn)步驟：定義結(jié)點(diǎn)結(jié)構(gòu)，定義圖結(jié)構(gòu)。存儲(chǔ)圖信息；定義求某頂點(diǎn)到其他所有頂點(diǎn)最短路徑的函數(shù)；寫出主函數(shù)。實(shí)現(xiàn)提示：intcreatcost(intcost[][MAX__VEX])/★建立圖的鄰接矩陣rcost數(shù)組表示圖的鄰接矩陣★/{intvexnum,arcnumAi,j,kFvlzv2zw;/★輸入圖的頂點(diǎn)數(shù)和弧數(shù)(或邊數(shù))*/printf(?\n請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))：scanf(M%dz%dM,&vexnumA&arcnum);for(i=l;i<=vexnum;i++)for(j=l;j<=vexnum;j++)cost[i][j]=9999;/★設(shè)9999代表無(wú)限大★/for(k=l;k<=arcnum;k++)(printf(nvlFv2,w=H);scanf(n%d,*d,&vl,&v2,&w);/★輸入所有邊或所有弧的一對(duì)頂點(diǎn)VI,V2*/cost[vl][v2]=w;)return(vexnum);}voiddijkstra(intcost[][MAX_VEX]rintvexnum)/*Dijkstra算法求從源點(diǎn)出發(fā)的最扁路徑*/{intpath[MAX_VEX],s[MAX_VEX],dist[MAX_VEX]zi/j/wzvzminAvl;/★s數(shù)組用于記系頂點(diǎn)V是否妾確定了最短路徑頂點(diǎn)V已經(jīng)確定了最短路徑，S[V]=0,頂點(diǎn)V尚未確定最短路徑。dist數(shù)組表示當(dāng)前求出的從V0到Vi的最短路徑。path是路徑數(shù)組，其中path[i]表示從源點(diǎn)到頂點(diǎn)Vi之間的最短路徑上Vi的前驅(qū)頂點(diǎn)'如有路徑(vl,v3,v5)，則path[5]=3*/printf(,f輸入源點(diǎn)vl:H);scanf(”％d”，&vl);/*輸入源點(diǎn)Vl*/for(i=l;i<=vexnum;i++)(dist[i]=cost[vl][i];/*初始時(shí)，從源點(diǎn)Vl到各頂點(diǎn)的最短路徑為相應(yīng)弧上的權(quán)*/s[i]=0;/*初始化*/if(cost[vl][i]<9999)path[i]=vl;/*初始化，path記錄當(dāng)前最短路徑，即頂點(diǎn)的直接前趨*/)s[vl]=l;/★將源點(diǎn)加入S集合中★/for(i=l;i<=vexnum;i++)(min=9999;/★本例設(shè)各邊上的權(quán)值均小于9999★/for(j=1;j<=vexnum;j++)/★從S集合外找出距離源點(diǎn)最近的頂點(diǎn)w*/if((s[j]==0)&&(dist[j]<min))min=dist[j];w=j;}s[w]=l;/★將w加入S集合'即w已是求出最短路徑的頂點(diǎn)x/for(v=l;v<=vexnum;v++)/★根據(jù)w修改dist[]*/if(s[v]==0)/★修改未加入的頂點(diǎn)的路徑長(zhǎng)度"if(dist[w]+cost[w][v]<dist[v])dist[v]=dist[w]+cost[w][v];/*修改V-S集合中各頂點(diǎn)的最短路徑長(zhǎng)度*/path[v]=w;/*修改V-S集合中各頂點(diǎn)的最短路徑*7})printf(”源點(diǎn)1到其他各頂點(diǎn)的路徑與值：\n",vl);for(i=2;i<=vexnum;i++)/*輸出從某源點(diǎn)到其他各頂點(diǎn)的最短路徑*/if(s[i]==l)w=i;while(w!=vl)(printf(,,%d<—,,zv;);w=path[w];/*通過(guò)找到前驅(qū)頂點(diǎn)，反向輸出最短路徑*/}printf(n%d,\w);printf(”%d\n'\dist[i]);}elseprintf(n%d<―%dMrvl);printf(u9999\n”);/★不存在路徑時(shí)，路徑長(zhǎng)度設(shè)為9999*/思考與提高：判斷兩點(diǎn)是否可達(dá)。練習(xí)圖的拓?fù)渑判驅(qū)嶒?yàn)六查找實(shí)驗(yàn)?zāi)康模赫莆詹檎业牟煌椒?，并能用高?jí)語(yǔ)言實(shí)現(xiàn)查找算法：熟練掌握二叉排序樹的構(gòu)造和查找方法。了解靜態(tài)查找表及哈希表查找方法。實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)一個(gè)算法讀入一串整數(shù)，然后構(gòu)造二叉排序樹，進(jìn)行查找。實(shí)驗(yàn)步驟：從空的二叉樹開始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就建立一個(gè)新結(jié)點(diǎn)插入到當(dāng)前己生成的二叉排序樹中。在二叉排序樹中查找某一結(jié)點(diǎn)。用其它查找算法進(jìn)行排序(課后自己做)。實(shí)現(xiàn)提示：typedefstructNode/★二叉排序樹結(jié)點(diǎn)結(jié)構(gòu)★/(KeyTypekey;/*關(guān)鍵字值*/structnode*lchildz*rchild;/★左右指針★/JBSTNode;voidInsertBST(BSTNode**bstfintkey)/*若在二叉排序樹中不存在關(guān)鍵字等于key的記錄，插入該記錄*/(BSTNode*s;if(*bst==NULL)/*遞歸結(jié)束條件★/(s=(BSTNode*)malloc(sizeof(BSTNode));/*申請(qǐng)新的結(jié)點(diǎn)s*/s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;}elseif(key<(*bst)->key)InsertBST(&((*bst)->lchild),key);/★將s插入左子樹★/elseif(key>(*bst)->key)InsertBST(&((*bst)->rchild),key);/*將s插入右子樹★/}voidCreateBST(BSTNode**bst)/★從鍵盤輸入記錄的值，創(chuàng)建相應(yīng)的二叉排序樹★/(intkey;*bst=NULL;scanf(n%d,fF&key);while(key!=0)/★輸入0時(shí)結(jié)束*/(InsertBST(bstfkey);scanf(n%d,fz&key);)}BSTNode*SearchBST(BSTNode*bst,intkey)/?在根指針bst所指二叉排序樹中，遞歸查找某關(guān)鍵*等于key的記錄，若查找成功，返回指向該記錄結(jié)點(diǎn)指針，否則返回空指針"if(!bst)

elseif(bst->key==key)returnbst;/★查找成功★/elsekey);/*在左子樹繼續(xù)查找★/key);/*key);/*在左子樹繼續(xù)查找★/key);/*在右子樹繼續(xù)查找★/returnSearchBST(bst->lchildzelsereturnSearchBST(bst->rchildz思考與提高:用其它的查找方法完成該算法。2.比較各種算法的時(shí)間及空間復(fù)雜度。實(shí)驗(yàn)七排序?qū)嶒?yàn)?zāi)康模赫莆粘Ｓ玫呐判蚍椒?，并掌握用高?jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法；深刻理解排序的定義和