數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)

數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版).word資料.數(shù)據(jù)結(jié)構(gòu)實驗指導書（C語言版）2017年9月數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第1頁。

數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第1頁。.word資料.目錄1、順序表的實現(xiàn) 12、鏈棧的實現(xiàn) 33、前序遍歷二叉樹 54、圖的深度優(yōu)先遍歷算法 75、散列查找 9數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第2頁。數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第2頁。.word資料.1、順序表的實現(xiàn)1.實驗目的⑴掌握線性表的順序存儲結(jié)構(gòu)；⑵驗證順序表及其基本操作的實現(xiàn)；⑶理解算法與程序的關(guān)系，能夠?qū)㈨樞虮硭惴ㄞD(zhuǎn)換為對應的程序。2.實驗容⑴建立含有若干個元素的順序表；⑵對已建立的順序表實現(xiàn)插入、刪除、查找等基本操作。3.實現(xiàn)提示定義順序表的數(shù)據(jù)類型——順序表結(jié)構(gòu)體SeqList，在SeqList基礎(chǔ)上實現(xiàn)題目要求的插入、刪除、查找等基本操作，為便于查看操作結(jié)果，設計一個輸出函數(shù)依次輸出順序表的元素。簡單起見，本實驗假定線性表的數(shù)據(jù)元素為int型，要求學生：（1）將實驗程序調(diào)試通過后，用模板類改寫；（2）加入求線性表的長度等基本操作；（3）重新給定測試數(shù)據(jù)，驗證拋出異常機制。4.實驗程序在編程環(huán)境下新建一個工程“順序表驗證實驗”，并新建相應文件，文件包括順序表結(jié)構(gòu)體SeqList的定義，例程序如下：#defineMaxSize100/*假設順序表最多存放100個元素*/typedefintDataType;/*定義線性表的數(shù)據(jù)類型，假設為int型*/typedefstruct{DataTypedata[MaxSize];/*存放數(shù)據(jù)元素的數(shù)組*/intlength;/*線性表的長度*/}SeqList;文件包括建立順序表、遍歷順序表、按值查找、插入操作、刪除操作成員函數(shù)的定義，例程序如下：intCreatList(SeqList*L,DataTypea[],intn){if(n>MaxSize){printf("順序表的空間不夠，無法建立順序表\n");return0;}for(inti=0;i<n;i++)L->data[i]=a[i];L->length=n;return1;數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第3頁。}數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第3頁。voidPrintList(SeqList*L){for(inti=0;i<L->length;i++)printf("%d",L->data[i]);/*輸出線性表的元素值，假設為int型*/}intLocate(SeqList*L,DataTypex){for(inti=0;i<L->length;i++)if(L->data[i]==x)returni+1;/*返回序號*/return0;/*退出循環(huán)，說明查找失敗*/}intInsert(SeqList*L,inti,DataTypex){if(L->length>=MaxSize){printf("上溢錯誤，插入失敗\n");return0;}if(i<1||i>L->length+1){printf("位置錯誤，插入失敗\n");return0;}for(intj=L->length;j>=i;j--)/*j表示元素序號*/L->data[j]=L->data[j-1];L->data[i-1]=x;L->length++;return1;}intDelete(SeqList*L,inti,DataType*ptr){if(L->length==0){printf("下溢錯誤，刪除失敗\n");return0;}if(i<1||i>L->length){printf("位置錯誤，刪除失敗\n");return0;}*ptr=L->data[i-1];/*取出位置i的元素*/for(intj=i;j<L->length;j++)/*j表示元素所在數(shù)組下標*/L->data[j-1]=L->data[j];L->length--;return1;}在定義了順序表的存儲結(jié)構(gòu)SeqList并實現(xiàn)了基本操作后，程序中就可以使用SeqList類型來定義變量，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成相應的功能。例程序如下：#include<stdio.h>#include<stdlib.h>/*將順序表的存儲結(jié)構(gòu)定義和各個函數(shù)定義放到這里*/intmain()數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第4頁。{數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第4頁。intr[5]={1,2,3,4,5},i,x;SeqListL;/*定義變量L為順序表類型*/Creat(&L,r,5);/*建立具有5個元素的順序表*/printf("當前線性表的數(shù)據(jù)為：");PrintList(&L);/*輸出當前線性表12345*/Insert(&L,2,8);/*在第2個位置插入值為8的元素*/printf("執(zhí)行插入操作后數(shù)據(jù)為：");PrintList(&L);/*輸出插入后的線性表182345*/printf("當前線性表的長度為：%d\n",Length(&L));/*輸出線性表的長度6*/printf("請輸入查找的元素值：");scanf("%d",&x);i=Locate(&L,x);if(0==i)printf("查找失敗\n");elseprintf("元素%d的位置為：%d\n",x,i);printf("請輸入查找第幾個元素值：",&i);scanf("%d",&i);if(Get(&L,i,&x)==1)printf("第%d個元素值是%d\n",i,x);elseprintf("線性表中沒有第%d個元素\n",i);printf("請輸入要刪除第幾個元素：");scanf("%d",&i);if(Delete(&L,i,&x)==1){/*刪除第i個元素*/printf("刪除第%d個元素是%d，刪除后數(shù)據(jù)為：",i,x);PrintList(&L);/*輸出刪除后的線性表*/}elseprintf("刪除操作失敗\n");return0;}2、鏈棧的實現(xiàn)1.實驗目的⑴掌握棧的存儲結(jié)構(gòu)；⑵驗證鏈棧及其基本操作的實現(xiàn)；⑶驗證棧的操作特性。2.實驗容⑴建立一個空棧；⑵對已建立的棧進行插入、刪除、取棧頂元素等基本操作。3.實現(xiàn)提示數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第5頁。定義鏈棧中的結(jié)點結(jié)構(gòu)（鏈棧中結(jié)點結(jié)構(gòu)基于單鏈表相同），定義鏈棧的數(shù)據(jù)類型——鏈棧結(jié)構(gòu)體，包括入棧、出棧、取棧頂元素等基本操作。本節(jié)的實驗采用模板實現(xiàn)，要求學生：數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第5頁。（1）假設棧元素為字符型，修改主函數(shù)；（2）重新設計測試數(shù)據(jù)，考查棧的上溢、下溢等情況，修改主函數(shù)。4.實驗程序在編程環(huán)境下新建一個工程“鏈棧驗證實驗”，并新建相應文件，文件包括鏈棧結(jié)構(gòu)體的定義，例程序如下：typedefintDataType;/*棧元素的數(shù)據(jù)類型，假設為int型*/typedefstructNode{DataTypedata; /*存放棧元素的數(shù)據(jù)域*/structNode*next; /*存放下一個結(jié)點的地址*/}Node;Node*top; /*棧頂指針*/文件包括鏈棧初始化、入棧、出棧、獲取棧頂元素、判空操作成員函數(shù)的定義，例程序如下：voidInitStack(Node*top){top=NULL;}voidPush(Node*top,DataTypex){Node*s=(Node*)malloc(sizeof(Node));/*申請一個結(jié)點s*/s->data=x;s->next=top;top=s;/*將結(jié)點s插在棧頂*/}intPop(Node*top,DataType*ptr){Node*p=top;if(top==NULL){printf("下溢錯誤，刪除失敗\n");return0;}*ptr=top->data;/*存儲棧頂元素*/top=top->next;/*將棧頂結(jié)點摘鏈*/free(p);return1;}intGetTop(Node*top,DataType*ptr)數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第6頁。{數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第6頁。if(top==NULL){printf("下溢錯誤，取棧頂失敗\n");return0;}*ptr=top->data;return1;}intEmpty(Node*top){if(top==NULL)return1;/*?？談t返回1*/elsereturn0;}在定義了鏈棧的存儲結(jié)構(gòu)并實現(xiàn)了基本操作后，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成相應的功能。例程序如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>/*將單鏈表的結(jié)點結(jié)構(gòu)定義和鏈棧的各個函數(shù)定義放到這里*/intmain(){DataTypex;Node*top=NULL;/*定義鏈棧的棧頂指針并初始化*/InitStack(top);/*初始化鏈棧*/printf("對15和10執(zhí)行入棧操作，");Push(top,15);Push(top,10);if(GetTop(top,&x)==1)printf("當前棧頂元素為：%d\n",x);/*輸出當前棧頂元素10*/if(Pop(top,&x)==1) printf("執(zhí)行一次出棧操作，刪除元素：%d\n",x);/*輸出出棧元素10*/if(GetTop(top,&x)==1)printf("當前棧頂元素為：%d\n",x);/*輸出當前棧頂元素15*/printf("請輸入待插入元素：");scanf("%d",&x);Push(&S,x);if(Empty(top)==1) printf("棧為空\n");elseprintf("棧非空\n");/*棧有2個元素，輸出棧非空*/DestroyStack(top);return0;}3、前序遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第7頁。1.實驗目的數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第7頁。⑴掌握二叉樹的邏輯結(jié)構(gòu)；⑵掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)；⑶驗證二叉樹的二叉鏈表存儲及遍歷操作。2.實驗容⑴建立一棵含有n個結(jié)點的二叉樹，采用二叉鏈表存儲；⑵輸出前序遍歷該二叉樹的遍歷結(jié)果。3.實現(xiàn)提示定義二叉樹的數(shù)據(jù)類型——二叉樹結(jié)點結(jié)構(gòu)體BiNode，在BiNode基礎(chǔ)上實現(xiàn)題目要求的建立二叉鏈表、前序遍歷等基本操作。建立二叉鏈表可以采用擴展二叉樹的一個遍歷序列，例如前序序列，將擴展二叉樹的前序序列由鍵盤輸入，建立該二叉樹的二叉鏈表存儲。簡單起見，本實驗假定二叉樹的數(shù)據(jù)元素為char型，要求學生：（1）將實驗程序調(diào)試通過后，用模板類改寫；（2）加入層序遍歷二叉樹等基本操作。4.實驗程序在編程環(huán)境下新建一個工程“二叉鏈表驗證實驗”，并新建相應文件，文件包括二叉樹結(jié)構(gòu)體的定義，例程序如下：typedefcharDataType;typedefstructBiNode{DataTypedata;structBiNode*lchild,*rchild;}BiNode;BiNode*root;文件包括建立二叉鏈表、前序遍歷操作成員函數(shù)的定義，例程序如下：BiNode*CreatBiTree(BiNode*root){charch;cin>>ch;/*輸入結(jié)點的數(shù)據(jù)信息*if(ch=='#')root=NULL;/*遞歸結(jié)束，建立一棵空樹*/else{root=(BiNode*)malloc(sizeof(BiNode));/*生成新結(jié)點*/root->data=ch;/*新結(jié)點的數(shù)據(jù)域為ch*/root->lchild=Creat(root->lchild);/*遞歸建立左子樹*/root->rchild=Creat(root->rchild);/*遞歸建立右子樹*/}returnroot;}數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第8頁。數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第8頁。voidPreOrder(BiNode*root){if(root==NULL)return; /*遞歸調(diào)用的結(jié)束條件*/else{printf("%c",root->data); /*訪問根結(jié)點的數(shù)據(jù)域，為char型*/PreOrder(root->lchild); /*前序遞歸遍歷root的左子樹*/PreOrder(root->rchild); /*前序遞歸遍歷root的右子樹*/}}在定義了二叉樹的存儲結(jié)構(gòu)并實現(xiàn)了基本操作后，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成相應的功能。例程序如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>/*將二叉鏈表的結(jié)點結(jié)構(gòu)定義和各個函數(shù)定義放到這里*/intmain(){ BiNode*root=NULL; /*定義二叉樹的根指針變量*/root=CreatBiTree(root);/*建立一棵二叉樹*/ printf("該二叉樹的根結(jié)點是：%c\n",root->data);printf("\n該二叉樹的前序遍歷序列是："); PreOrder(root); return0;}4、圖的深度優(yōu)先遍歷算法1.實驗目的⑴掌握圖的邏輯結(jié)構(gòu)；⑵掌握圖的鄰接矩陣存儲結(jié)構(gòu)；⑶驗證圖的鄰接矩陣存儲及其深度優(yōu)先遍歷操作的實現(xiàn)。2.實驗容⑴建立無向圖的鄰接矩陣存儲；⑵對建立的無向圖，進行深度優(yōu)先遍歷；3.實現(xiàn)提示定義鄰接矩陣存儲的無向圖結(jié)構(gòu)體MGraph，在其基礎(chǔ)上實現(xiàn)題目要求的圖建立、深度優(yōu)先遍歷等基本操作。數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第9頁。4.實驗程序數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第9頁。在編程環(huán)境下新建一個工程“圖的深度優(yōu)先遍歷驗證實驗”，并新建相應文件，文件包括圖的鄰接矩陣結(jié)構(gòu)體MGraph的定義，例程序如下：#defineMaxSize10/*假設圖中最多頂點個數(shù)*/typedefcharDataType;/*圖中頂點的數(shù)據(jù)類型，假設為char型*/typedefstruct/*定義鄰接矩陣存儲結(jié)構(gòu)*/{DataTypevertex[MaxSize];/*存放頂點的一維數(shù)組*/intedge[MaxSize][MaxSize];/*存放邊的二維數(shù)組*/intvertexNum,edgeNum;/*圖的頂點數(shù)和邊數(shù)*/}MGraph;文件包括建立圖、圖的深度優(yōu)先遍歷操作成員函數(shù)的定義，例程序如下：voidCreatGraph(MGraph*G,DataTypea[],intn,inte){inti,j,k;G->vertexNum=n;G->edgeNum=e;for(i=0;i<G->vertexNum;i++)/*存儲頂點信息*/G->vertex[i]=a[i];for(i=0;i<G->vertexNum;i++)/*初始化鄰接矩陣*/for(j=0;j<G->vertexNum;j++)G->edge[i][j]=0;for(k=0;k<G->edgeNum;k++)/*依次輸入每一條邊*/{scanf("%d%d",&i,&j);/*輸入邊依附的頂點編號*/G->edge[i][j]=1;G->edge[j][i]=1;/*置有邊標志*/}}voidDFraverse(MGraph*G,intv)/*全局數(shù)組變量visited[n]已初始化為0*/{printf("%c",G->vertex[v]);visited[v]=1;for(intj=0;j<G->vertexNum;j++)if(G->edge[v][j]==1&&visited[j]==0)DFSTraverse(G,j);}在定義了圖的鄰接矩陣存儲結(jié)構(gòu)并實現(xiàn)了基本操作后，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成相應的功能。例程序如下：#include<stdio.h>數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第10頁。#include<stdlib.h>數(shù)據(jù)結(jié)構(gòu)實驗指導書(C版)全文共12頁，當前為第10頁。intvisited[MaxSize]={0};/*全局數(shù)組變量visited初始化*//*把鄰接矩陣的存儲結(jié)構(gòu)定義和各個函數(shù)定義放到這里*/intmain(){ inti;charch[]={'A','B','C','D','E'}; MGraphMG;CreatGraph(&