2013級本科數(shù)據(jù)結(jié)構(gòu)實驗指導書

PAGE-《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導書

實驗一線性表的實驗一、實驗?zāi)康?、掌握用VisualC++6.0上機調(diào)試順序表的基本方法。2、掌握順序表的基本操作，插入、刪除、查找、以及有序順序表的合并等算法的實現(xiàn)。3、掌握用VisualC++6.0上機調(diào)試單鏈表的基本方法。4、掌握單鏈表的插入、刪除、查找、求表長以及有序單鏈表的合并算法的實現(xiàn)。5、進一步掌握循環(huán)單鏈表和雙鏈表的插入、刪除、查找算法的實現(xiàn)。二、實驗內(nèi)容(一)完成下列程序，該程序生成一個如表1所示的順序表，并在第2個位置插入如表2所示的數(shù)據(jù)元素，刪除在第3個位置的數(shù)據(jù)元素，顯示順序表的每個元素。要求生成順序表時，從鍵盤上讀取數(shù)據(jù)元素，用順序存儲結(jié)構(gòu)實現(xiàn)存儲。表1學號姓名性別年齡2013001張珊女192013002李思女192013004王強男202013005趙括男212013006劉剛男20表22013003陳琪女19typedefstruct{DataTypelist[MaxSize]; intsize;}SeqList;voidListInitiate(SeqList*L) {L->size=0; /*定義初始數(shù)據(jù)元素個數(shù)*/}intListLength(SeqListL) {returnL.size;}intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1]; L->list[i]=x; /*插入x*/ L->size++; /*元素個數(shù)加1*/ return1;}intListDelete(SeqList*L,inti,DataType*x) {intj;*x=L->list[i]; /*保存刪除的元素到x中*/for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];L->size--; /*數(shù)據(jù)元素個數(shù)減1*/return1;}intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("參數(shù)i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}（二）已知順序表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb表中的數(shù)據(jù)元素，合并成為一個新的順序表lc，要求lc中的數(shù)據(jù)元素仍按非遞減有序排列，并且不破壞la和lb表。（三）完成下列程序，該程序構(gòu)建如表3所示的帶頭結(jié)點的單鏈表h，在單鏈表h中第3個數(shù)據(jù)元素之前插入如表4所示的數(shù)據(jù)元素，刪除第4個數(shù)據(jù)元素。要求生成單鏈表時，從鍵盤上讀取數(shù)據(jù)元素，用鏈式存儲結(jié)構(gòu)實現(xiàn)存儲。表3員工編號姓名性別職位001張珊女文員002李思女銷售員004王強男經(jīng)理005趙括男秘書006劉剛男文員表42013003陳琪女19typedefstructNode{DataTypedata;structNode*next;}SLNode;voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL; }intListLength(SLNode*head){SLNode*p=head;intsize=0; while(p->next!=NULL) {p=p->next; size++; }returnsize;}intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1; while(p->next!=NULL&&j<i-1){p=p->next;j++; }if(j!=i-1){printf(“插入位置參數(shù)錯！”); return0;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q; return1;}intListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;j=-1;while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){p=p->next; j++;}if(j!=i-1){printf(“插入位置參數(shù)錯！”); return0;}s=p->next;*x=s->data;p->next=p->next->next;free(s);return1;}intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next; j++; }if(j!=i){printf(“取元素位置參數(shù)錯！”); return0;}*x=p->data;return1;}voidDestroy(SLNode**head){SLNode*p,*p1;p=*head;while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}（四）已知單鏈表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb中的數(shù)據(jù)元素,合并為一個新的單鏈表lc,lc中的數(shù)據(jù)元素仍按非遞減有序排列。要求不破壞la表和lb表的結(jié)構(gòu)。（五）約瑟夫環(huán)程序：設(shè)有N個人圍坐一圈，現(xiàn)從某個人開始報數(shù)，數(shù)到M的人出列，接著從出列的下一個人開始重新報數(shù)，數(shù)到M的人以出列，如此下去，直到所有人都出列為此。試設(shè)計確定他們的出列次序序列的程序。要求選擇單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬整個過程，并依次輸出列的各人的編號。如n=8,m=4時，若從第一個人，設(shè)每個人的編號依次為1，2，3，…開始報數(shù)，則得到的出列次序為4，8，5，2，1，3，7，6，實驗二棧、隊列的實現(xiàn)及應(yīng)用一、實驗?zāi)康?、掌握棧和隊列的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，以便在實際背景下靈活運用。2、掌握棧和隊列的特點，即先進后出與先進先出的原則。3、掌握棧和隊列的基本操作實現(xiàn)方法。二、實驗內(nèi)容（一）完成下列程序，該程序?qū)崿F(xiàn)棧的順序存儲結(jié)構(gòu)，構(gòu)建順序棧（棧中的元素依次為R，S，Y，F(xiàn)，C，T），依次進行進棧和出棧操作，判斷棧空和棧滿操作，返回棧頂元素操作。要求生成順序棧時，從鍵盤上讀取數(shù)據(jù)元素。typedefstruct{DataTypestack[MaxStackSize]; inttop;}SeqStack;voidStackInitiate(SeqStack*S) {S->top=0; }intStackNotEmpty(SeqStackS){if(S.top<=0)return0;elsereturn1;}intStackPush(SeqStack*S,DataTypex){if(S->top>=MaxStackSize){printf("堆棧已滿無法插入!\n"); return0;}else{S->stack[S->top]=x; S->top++;return1;}}intStackPop(SeqStack*S,DataType*d){if(S->top<=0){printf("堆棧已空無數(shù)據(jù)元素出棧!\n"); return0;}else{S->top--;*d=S->stack[S->top];return1;}}intStackTop(SeqStackS,DataType*d){if(S.top<=0){printf("堆棧已空!\n"); return0;}else{*d=S.stack[S.top-1]; return1;}}（二）完成下列程序，該程序?qū)崿F(xiàn)棧的鏈式存儲結(jié)構(gòu)，構(gòu)建鏈棧（棧中的元素依次為China，Japan，F(xiàn)rance，India，Australia），依次進行進棧和出棧操作，判斷?？蘸蜅M操作，返回棧頂元素操作。要求生成鏈棧時，從鍵盤上讀取數(shù)據(jù)元素。typedefstructsnode{DataTypedata;structsnode*next;}LSNode;voidStackInitiate(LSNode**head){*head=(LSNode*)malloc(sizeof(LSNode)); (*head)->next=NULL;}intStackNotEmpty(LSNode*head){if(head->next==NULL)return0;elsereturn1;}intStackPush(LSNode*head,DataTypex){LSNode*p;p=(LSNode*)malloc(sizeof(LSNode));p->data=x;p->next=head->next;head->next=p;return1;}intStackPop(LSNode*head,DataType*d){LSNode*p=head->next;if(p==NULL){printf("堆棧已空出錯！"); return0;}head->next=p->next;*d=p->data; free(p);return1;}intStackTop(LSNode*head,DataType*d){LSNode*p=head->next; if(p==NULL) { printf("堆棧已空出錯！"); return0; } *d=p->data; return1;}voidDestroy(LSNode*head){LSNode*p,*p1;p=head; while(p!=NULL) {p1=p; p=p->next; free(p1); }}（三）利用順序棧實現(xiàn)數(shù)制轉(zhuǎn)換，輸入十進制整數(shù)，分別將其轉(zhuǎn)換為八進制數(shù)和二進制數(shù)。（四）完成下列程序，該程序?qū)崿F(xiàn)循環(huán)隊列的存儲和基本操作，構(gòu)建循環(huán)隊列（隊列中的元素依次為John，Mary，Linda，Mike，Paul），依次進行判斷隊列是否為空和滿操作、入隊和出隊操作、取得隊首元素操作。typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}SeqCQueue;voidQueueInitiate(SeqCQueue*Q){Q->rear=0; Q->front=0;Q->count=0;}intQueueNotEmpty(SeqCQueueQ){if(Q.count!=0) return1;elsereturn0;}intQueueAppend(SeqCQueue*Q,DataTypex){if(Q->count>0&&Q->rear==Q->front){printf("隊列已滿無法插入!\n"); return0;}else{Q->queue[Q->rear]=x; Q->rear=(Q->rear+1)%MaxQueueSize; Q->count++; return1;}}intQueueDelete(SeqCQueue*Q,DataType*d){if(Q->count==0){printf("隊列已空無數(shù)據(jù)元素出隊列!\n"); return0;}else{*d=Q->queue[Q->front]; Q->front=(Q->front+1)%MaxQueueSize; Q->count--; return1;}}intQueueGet(SeqCQueueQ,DataType*d){if(Q.count==0){printf("隊列已空無數(shù)據(jù)元素可取!\n"); return0;}else{*d=Q.queue[Q.front]; return1;}}實驗三二叉樹的操作及應(yīng)用一、實驗?zāi)康?、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結(jié)構(gòu)特性，以及各種存儲結(jié)構(gòu)的特點和適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。二、實驗內(nèi)容（一）完成下列程序，該程序以二叉鏈表作存儲結(jié)構(gòu)，構(gòu)建如圖1所示的二叉樹，并依次進行二叉樹的前序、中序、后序及層次遍歷。圖1typedefstructNode{DataTypedata; structNode*leftChild; structNode*rightChild;}BiTreeNode;/*初始化*/voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}voidPreOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*前序遍歷二叉樹t，訪問操作為Visit()函數(shù)*/{if(t!=NULL){Visit(t->data); PreOrder(t->leftChild,Visit); PreOrder(t->rightChild,Visit);}}voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*中序t*/{if(t!=NULL) {InOrder(t->leftChild,Visit); Visit(t->data); InOrder(t->rightChild,Visit); }}voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*后序*/{if(t!=NULL) {PostOrder(t->leftChild,Visit); PostOrder(t->rightChild,Visit); Visit(t->data); }}（二）完成下列程序，該程序以二叉鏈表作存儲結(jié)構(gòu)，構(gòu)建如圖2所示二叉樹，計算二叉樹深度、所有結(jié)點總數(shù)、葉子結(jié)點數(shù)、雙孩子結(jié)點個數(shù)、單孩子結(jié)點個數(shù)。圖2intBTreeDepth(BiTreeNode*BT){intleftdep,rightdep;if(BT==NULL) return(0);else{ leftdep=BTreeDepth(BT->leftChild); rightdep=BTreeDepth(BT->rightChild); if(leftdep>rightdep) return(leftdep+1); else return(rightdep+1);}}intnodecount(BiTreeNode*BT){if(BT==NULL) return(0);else return(nodecount(BT->leftChild)+nodecount(BT->rightChild)+1);}intleafcount(BiTreeNode*BT){if(BT==NULL) return(0);elseif(BT->leftChild==NULL&&BT->rightChild==NULL) return(1);else return(leafcount(BT->leftChild)+leafcount(BT->rightChild));}intnotleafcount(BiTreeNode*BT){if(BT==NULL) return(0);elseif(BT->leftChild==NULL&&BT->rightChild==NULL) return(0);else return(notleafcount(BT->leftChild)+notleafcount(BT->rightChild)+1);}intonesoncount(BiTreeNode*BT){if(BT==NULL) return(0);elseif((BT->leftChild==NULL&&BT->rightChild!=NULL)||(BT->leftChild!=NULL&&BT->rightChild==NULL)) return(onesoncount(BT->leftChild)+onesoncount(BT->rightChild)+1);else return(onesoncount(BT->leftChild)+onesoncount(BT->rightChild));}inttwosoncount(BiTreeNode*BT){if(BT==NULL) return(0);elseif(BT->leftChild==NULL||BT->rightChild==NULL) return(twosoncount(BT->leftChild)+twosoncount(BT->rightChild));elseif(BT->leftChild!=NULL&&BT->rightChild!=NULL) return(twosoncount(BT->leftChild)+twosoncount(BT->rightChild)+1);}（三）用非遞歸方式遍歷圖2所示的二叉樹（先序、中序或后序），輸出遍歷序列。實驗四圖的操作及應(yīng)用一、實驗?zāi)康?、理解圖的基本概念及術(shù)語。2、掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法。3、熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列。4、理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹。二、實現(xiàn)內(nèi)容（一）完成下列程序，該程序構(gòu)造如圖1所示的圖的鄰接矩陣存儲結(jié)構(gòu)。圖1/*鄰接矩陣*/typedefstruct{SeqListVertices; intedge[MaxVertices][MaxVertices]; intnumOfEdges; }AdjMGraph;voidInitiate(AdjMGraph*G,intn) {inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)G->edge[i][j]=0; elseG->edge[i][j]=MaxWeight;}G->numOfEdges=0; /*邊的條數(shù)置為0*/ListInitiate(&G->Vertices); /*順序表初始化*/}voidInsertVertex(AdjMGraph*G,DataTypevertex){ListInsert(&G->Vertices,G->Vertices.size,vertex);}voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight){if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size){printf("參數(shù)v1或v2越界出錯!\n"); exit(1);}G->edge[v1][v2]=weight;G->numOfEdges++;}typedefstruct{introw; //行下標 intcol; //列下標 intweight; //權(quán)值}RowColWeight;voidCreatGraph(AdjMGraph*G,DataTypeV[],intn,RowColWeightE[],inte)/*在圖G中插入n個頂點信息V和e條邊信息E*/{inti,k; Initiate(G,n); /*頂點順序表初始化*/ for(i=0;i<n;i++) InsertVertex(G,V[i]); /*頂點插入*/ for(k=0;k<e;k++) InsertEdge(G,E[k].row,E[k].col,E[k].weight); }（二）完成下列程序，該程序構(gòu)造如圖1所示的圖的鄰接表存儲結(jié)構(gòu)。/*鄰接表的存儲結(jié)構(gòu)*/typedefstructNode{ intdest; /*鄰接邊的弧頭頂點序號*/ structNode*next;}Edge; /*鄰接邊單鏈表的結(jié)點結(jié)構(gòu)體*/typedefstruct{ DataTypedata; /*頂點數(shù)據(jù)元素*/ intsorce; /*鄰接邊的弧尾頂點序號*/ Edge*adj; /*鄰接邊的頭指針*/}AdjLHeight; /*數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體*/typedefstruct{AdjLHeighta[MaxVertices]; /*鄰接表數(shù)組*/intnumOfVerts; /*頂點個數(shù)*/intnumOfEdges; /*邊個數(shù)*/}AdjLGraph; /*鄰接表結(jié)構(gòu)體*/（三）完成下列程序，該程序分別創(chuàng)建一個如圖2所示的圖a和b，分別打印出這兩個圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結(jié)點信息序列。00165948372(a)603451278(b)圖2/*深度優(yōu)先遍歷*/voidDepthFSearch(AdjMWGraphG,intv,intvisited[],voidVisit(DataTypeitem)){intw;Visit(G.Vertices.list[v]); visited[v]=1; w=GetFirstVex(G,v); while(w!=-1) {if(!visited[w])DepthFSearch(G,w,visited,Visit); w=GetNextVex(G,v,w); }}/*廣度優(yōu)先遍歷*/voidBroadFSearch(AdjMWGraphG,intv,intvisited[],voidVisit(DataTypeitem)){DataTypeu,w; SeqCQueuequeue;Visit(G.Vertices.list[v]); visited[v]=1; QueueInitiate(&queue); QueueAppend(&queue,v); while(QueueNotEmpty(queue)) {QueueDelete(&queue,&u); w=GetFirstVex(G,u); while(w!=-1) {if(!visited[w]) {Visit(G.Vertices.list[w]);visited[w]=1; QueueAppend(&queue,w); } w=GetNextVex(G,u,w); } }}（四）完成下列程序，該程序用Prim算法求圖1所示的圖的最小生成樹。typederstruct{VerTvertex; intweight;}MinSpanTree;voidPrim(AdjMWGraphG,MinSpanTreecloseVertex[]){VerTx;intn=G.Vertices.size,minCost; int*lowCost=(int*)malloc(sizeof(int)*n); inti,j,k; for(i=1;i<n;i++) lowCost[i]=G.edge[0][i]; /*從頂點0出發(fā)構(gòu)造最小生成樹*/ ListGet(G.Vertices,0,&x); closeVertex[0].vertex=x; lowCost[0]=-1; for(i=1;i<n;i++){/*尋找當前最小權(quán)值的邊所對應(yīng)的弧頭頂點k*/minCost=MaxWeight; for(j=1;j<n;j++) {if(lowCost[j]<minCost&&lowCost[j]>0) {minCost=lowCost[j]; k=j; } } ListGet(G.Vertices,k,&x); closeVertex[i].vertex=x; closeVertex[i].weight=minCost; lowCost[k]=-1; for(j=1;j<n;j++) {if(G.edge[k][j]<lowCost[j]) lowCost[j]=G.edge[k][j]; } }}實驗五查找與排序一、實驗?zāi)康?、掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法。2、熟練掌握順序表的查找方法和有序順序表的折半查找算法。3、掌握常用的排序方法，并能用高級語言實現(xiàn)排序算法。4、深刻理解排序的定義和各種排序方法的特點，并能加以靈活運用。5、了解各種方法的排序過程及依據(jù)的原則，并掌握各種排序方法的時間復(fù)雜度的分析方法。二、實驗內(nèi)容（一）完成下列程序，該程序?qū)崿F(xiàn)順序表（表中元素依次為(31，38，54，56，75，80，55，63)）的順序查找，要求查找的元素依次為80,42，在輸出結(jié)果中顯示查找成功與查找不成功信息。typedefstruct{KeyTypekey;}DataType;/*順序查找*/intSeqSearch(DataTypea[],intn,KeyTypekey){inti=0; while(i<n&&a[i].key!=key)i++; if(a[i].key==key)returni; elsereturn-1;}（二）完成下列程序，該程序有序順序表（表中元素依次為(31，38，54，56，75，80，97)）的二分查找。要求查找的元素依次為80,42，在輸出結(jié)果中顯示查找成功與查找不成功信息。/*二分查找*/intBiSearch(DataTypea[],intn,KeyTypekey){intlow=0,high=n-1; //確定初始查找區(qū)間上下界 intmid;while(low<=high) { mid=(low+high)/2;//確定查找區(qū)間中心下標 if(a[mid].key==key)returnmid; //查找成功 elseif(a[mid].key<key)low=mid+1; elsehigh=mid-1; } return-1; //查找失敗}（三）完成下列程序，該程序分別用各種排序方法對表（表中元素依次為（11,4,18,29,33,9,21,5,19））進行排序。voidInsertSort(DataTypea[],intn)//用直接插入法對a[0]--a[n-1]排序{inti,j; DataTypetemp; for(i=0;i<n-1;i++) {temp=a[i+1]; j=i; while(j>-1&&temp.key<=a[j].key) {a[j+1]=a[j]; j--; } a[j+1]=temp; }}voidShellSort(DataTypea[],intn,intd[],intnumOfD)//用希爾排序法對元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]為希爾增量值{inti,j,k,m,span; DataTypetemp; for(m=0;m<numOfD;m++) //共numOfD次循環(huán) {span=d[m]; //取本次的增量值 for(k=0;k<span;k++) //共span個小組 { //組內(nèi)是直接插入排序，區(qū)別是每次不是增1而是增span for(i=k;i<n-span;i=i+span) {temp=a[i+span]; j=i; while(j>-1&&temp.key<=a[j].key) {a[j+span]=a[j]; j=j-span; } a[j+span]=temp; } } }}voidSelectSort(DataTypea[],intn)//直接選擇排序{inti,j,small; DataTypetemp; for(i=0;i<n-1;i++) {small=i; //設(shè)第i個數(shù)據(jù)元素關(guān)鍵字最小 for(j=i+1;j<n;j++) //尋找關(guān)鍵字最小的數(shù)據(jù)元素 if(a[j].key<a[small].key)small=j;//記住最小元素的下標if(small!=i)//當最小元素的下標不為i時交換位置 { temp=a[i]; a[i]=a[small]; a[small]=temp; } }}/*堆排序*/voidCreatHeap(DataTypea[],intn,inth){inti,j,flag; DataTypetemp; i=h; //i為要建堆