數(shù)據(jù)結(jié)構(gòu)實驗報告.docx

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱 數(shù)據(jù)結(jié)構(gòu)與算法 專業(yè)班級 數(shù)學(xué)與應(yīng)用數(shù)學(xué)1201班學(xué) 號 1304120306姓 名 謝 偉指導(dǎo)老師 陳 明目 錄1前言.22數(shù)據(jù)結(jié)構(gòu)與算法實驗概要.2 2.1實驗要求2 2.2主要儀器設(shè)備.2 2.3實驗內(nèi)容與簡介23數(shù)據(jù)結(jié)構(gòu)設(shè)計與算法設(shè)計.3 3.1線性表的操作.3 3.2二叉樹的操作.8 3.3圖的遍歷操作.12 3.4棧的基本操作.19 3.5哈希表設(shè)計.284實驗總結(jié)與心得體會.395參考文獻(xiàn). 401前言數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學(xué)科的核心課程，而且已經(jīng)成為其他理工專業(yè)的熱門選修課。隨著計算機科學(xué)的技術(shù)和發(fā)展，計算機的功能和運算速度不斷地提高，其應(yīng)用于信息處理的范圍日益擴大。與之相應(yīng)的，計算機的加工處理對象也從簡單的數(shù)據(jù)發(fā)展到一般的符號，進(jìn)而發(fā)展到更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)的表示和操作都涉及到算法，如何描述數(shù)據(jù)的結(jié)構(gòu)和討論有關(guān)的算法，又涉及到程序設(shè)計語言。因此，它不僅是計算機學(xué)科的核心課程，而且已經(jīng)成為其他理工專業(yè)的熱門選修課。 我們通過對這門基礎(chǔ)課程的學(xué)習(xí)，要學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適合的邏輯結(jié)構(gòu)，儲存結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法時間分析和空間分析的技術(shù)。通過實際操作去了解數(shù)據(jù)結(jié)構(gòu)原理， 練習(xí)編寫代碼的能力，以及抽象能力。從課程性質(zhì)上講，“數(shù)據(jù)結(jié)構(gòu)”是一門專業(yè)技術(shù)基礎(chǔ)課。它的要求是學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)，存儲結(jié)構(gòu)及相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。另一方面，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計的訓(xùn)練過程，要求編 寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。2數(shù)據(jù)結(jié)構(gòu)與算法實驗概要 2.1實驗要求書寫類C語言的算法，并將算法轉(zhuǎn)變?yōu)槌绦驅(qū)崿F(xiàn)。正確理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯特性和存儲表示和基本操作的算法實現(xiàn)。針對問題的不同選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法設(shè)計的能力和動手實驗的技能。 2.2實驗儀器設(shè)備硬件要求：在多媒體教室講解及演示。為保證教學(xué)順利進(jìn)行，要求實驗室提供P及以上的微機。 2.3實驗項目內(nèi)容簡介 1、線性表基本操作（1）熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實現(xiàn)（2）以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為重點（3）通過本次實習(xí)幫助學(xué)生加深對c+的使用（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。2、棧、隊列以及遞歸算法的設(shè)計（1）掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們（2）訓(xùn)練的要點是“?！钡挠^點及其典型用法；問題求解的狀態(tài)表示及其遞歸算法；由遞歸程序到非遞歸程序的轉(zhuǎn)化方法 3、樹、圖及其應(yīng)用 （1）樹和圖是兩種非線性數(shù)據(jù)結(jié)構(gòu)，廣義表的實質(zhì)是樹結(jié)構(gòu)，而稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故本單元是本課的實習(xí)重點。（2）要求我們熟悉各種存儲結(jié)構(gòu)的特性，以及如何應(yīng)用樹和圖結(jié)構(gòu)求解具體問題。（3）訓(xùn)練的要點是：遞歸算法的設(shè)計方法；表達(dá)式的求值技術(shù)；哈夫曼方法及其編譯碼技術(shù)；完整的應(yīng)用系統(tǒng)的用戶界面設(shè)計和操作定義方法；矩陣乘法的特殊操作順序；路徑遍歷（樹、圖的遍歷）技術(shù)。4、查找和排序本次實習(xí)旨在集中對幾個專門的問題做較為深入的探討和理解重點在掌握各種內(nèi)部排序算法、查找算法的思想和實現(xiàn)。學(xué)生在實習(xí)中體會查找和內(nèi)部排序算法思想，理解開發(fā)高效算法的可能性和尋找、構(gòu)造高效算法的方法。3數(shù)據(jù)結(jié)構(gòu)設(shè)計與算法設(shè)計 3.1線性表的操作 3.1.1實驗?zāi)康?熟悉C+語言的上機環(huán)境，掌握C+語言的基本結(jié)構(gòu)。2會定義線性表的順序存儲結(jié)構(gòu)。（鏈?zhǔn)酱鎯Y(jié)構(gòu)）3熟悉對順序表（單鏈表）的一些基本操作。 3.1.2實驗內(nèi)容 單鏈表的基礎(chǔ)操作 包括： 查找、插入、刪除、創(chuàng)建鏈表等。 源程序代碼：#include #include typedef struct Node int data; struct Node *next; Node; Node *Serach(Node *pHead,int x) Node *p=pHead; while(p!=NULL & p-data!=x) p=p-next; return p; void Insert(Node *p,int x) Node *s; s=(Node*)malloc(sizeof(Node); s-data=x; s-next=p-next; p-next=s; void DeleteFollowNode(Node *p) Node *q; q=p-next; if(q!=NULL) p-next=q-next; free(q); void Delete(Node *p,Node *pHead) if (p=NULL) return; Node *qPre=pHead; while(qPre!=NULL&qPre-next!=p) qPre=qPre-next; if (qPre!=NULL&p!=NULL) qPre-next=p-next; free(p); Node* CreateListAhead(int a,int n) Node *s,*pHead; int i; pHead=(Node*)malloc(sizeof(Node); pHead-data=0; pHead-next=NULL; for(i=n-1;i=0;i-) s=(Node*)malloc(sizeof(Node); s-data=ai; s-next=pHead-next; pHead-next=s; return pHead; Node* CreateListTail(int a,int n) Node *s,*pHead,*pTail; int i; pHead=(Node*)malloc(sizeof(Node); pHead-data=0; pHead-next=NULL;pTail=pHead; for(i=0;idata=ai; s-next=NULL; pTail-next=s; pTail=s; return pHead; void Print(Node *h) Node *p; p=h-next; while(p!=NULL) printf(%d,p-data); p=p-next; printf(n); void main() int a=3,2,1,4,5; Node *pHead,*p; pHead=CreateListTail(a,5); Print(pHead); p=Serach(pHead,4); printf(%dn,p-data); p=pHead-next-next; Insert(p,9); Print(pHead); p=pHead-next-next-next; Delete(p,pHead); Print(pHead); while(getchar()!=a) ; 運行結(jié)果： 3.2二叉樹的操作 3.2.1實驗?zāi)康?理解并熟悉掌握創(chuàng)建二叉樹和實現(xiàn)二叉樹的三種遍歷 3.2.2實驗內(nèi)容 創(chuàng)建二叉樹并實現(xiàn)二叉樹的三中遍歷操作 源程序代碼：#include#include #include typedef int DataType; typedef struct Node DataType data; struct Node *LChild; struct Node *RChild;BitNode,*BitTree;void CreatBiTree(BitTree *bt)/用擴展先序遍歷序列創(chuàng)建二叉樹，如果是#當(dāng)前樹根置為空，否則申請一個新節(jié)點/ char ch; ch=getchar(); if(ch=.)*bt=NULL; else *bt=(BitTree)malloc(sizeof(BitNode); (*bt)-data=ch; CreatBiTree(&(*bt)-LChild); CreatBiTree(&(*bt)-RChild); void Visit(char ch)/訪問根節(jié)點 printf(%c ,ch);void PreOrder(BitTree root) /*先序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結(jié)點的指針*/ if (root!=NULL) Visit(root -data); /*訪問根結(jié)點*/ PreOrder(root -LChild); /*先序遍歷左子樹*/ PreOrder(root -RChild); /*先序遍歷右子樹*/ void InOrder(BitTree root) /*中序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結(jié)點的指針*/ if (root!=NULL) InOrder(root -LChild); /*中序遍歷左子樹*/ Visit(root -data); /*訪問根結(jié)點*/ InOrder(root -RChild); /*中序遍歷右子樹*/ void PostOrder(BitTree root) /* 后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結(jié)點的指針*/ if(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹*/ PostOrder(root -RChild); /*后序遍歷右子樹*/ Visit(root -data); /*訪問根結(jié)點*/ int PostTreeDepth(BitTree bt) /后序遍歷求二叉樹的高度遞歸算法/ int hl,hr,max; if(bt!=NULL) hl=PostTreeDepth(bt-LChild); /求左子樹的深度 hr=PostTreeDepth(bt-RChild); /求右子樹的深度 max=hlhr?hl:hr; /得到左、右子樹深度較大者 return(max+1); /返回樹的深度 else return(0); /如果是空樹，則返回0void PrintTree(BitTree Boot,int nLayer) /按豎向樹狀打印的二叉樹 / int i; if(Boot=NULL) return; PrintTree(Boot-RChild,nLayer+1); for(i=0;idata); PrintTree(Boot-LChild,nLayer+1);void main() BitTree T; int h; int layer; int treeleaf; layer=0; printf(請輸入二叉樹中的元素(以擴展先序遍歷序列輸入,其中.代表空子樹):n); CreatBiTree(&T); printf(先序遍歷序列為:); PreOrder(T); printf(n中序遍歷序列為:); InOrder(T); printf(n后序遍歷序列為:); PostOrder(T); h=PostTreeDepth(T); printf(nThe depth of this tree is:%dn,h); PrintTree(T,layer); getch(); 運行結(jié)果： 3.3圖的遍歷操作 3.3.1實驗?zāi)康?該實驗主要完成對圖的創(chuàng)建，并實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷 3.3.2實驗內(nèi)容 編寫程序完成圖的創(chuàng)建，并實現(xiàn)圖的深度和廣度優(yōu)先遍歷 源程序代碼：#include #include #include #define maxvex 30struct edgenode int adjvex;char info;struct edgenode*next;struct vexnodechar data;struct edgenode*link;typedef struct vexnode adjlistmaxvex; adjlist tu1;void creategraph(adjlist g,int n) int e,i,s,d; struct edgenode*p,*q; printf(the point(n) and edge(e):); scanf(%d,%d,&n,&e); for(i=1;i=n;i+)getchar(); printf(tthe %d information:,i); scanf(%c,&gi.data); gi.link=NULL; for(i=1;int :,i); scanf(%d,%d,&s,&d); p=(struct edgenode*)malloc(sizeof(struct edgenode);q=(struct edgenode*)malloc(sizeof(struct edgenode);p-adjvex=d;p-info=gd.data; q-adjvex=s; q-info=gs.data;p-next=gs.link; gs.link=p;q-next=gd.link;gd.link=q; int visitedmaxvex;void dfs(adjlist adj,int v)int i;struct edgenode*p; visitedv=1;printf(now is at point %d,v); p=adjv.link;printf(the data is %c n,adjv.data);getch();while(p)if(visitedp-adjvex=0)dfs(adj,p-adjvex);p=p-next;int quenemaxvex;void bfs(adjlist adj,int vi)int m=maxvex; int front=0,rear=1,v;struct edgenode*p;visitedvi=1; printf(now visit the point:%dn,vi); getch();quenerear=vi; while(front!=rear)front=(front+1)%m;v=quenefront;p=adjv.link;while(p)if(visitedp-adjvex=0)visitedp-adjvex=1;printf(now visit the point:%dn,p-adjvex); getch();rear=(rear+1)%m;quenerear=p-adjvex; p=p-next; void main()int i;system(cls);creategraph(tu1,0); for(i=1;imaxvex;i+)visitedi=0; dfs(tu1,1);getch();for(i=1;imaxvex;i+)visitedi=0;bfs(tu1,1); 運行結(jié)果： 3.4棧的基本操作 3.4.1實驗?zāi)康?熟練掌握棧的結(jié)構(gòu)，以及這種數(shù)據(jù)結(jié)構(gòu)的特點；2 能夠在兩種存儲結(jié)構(gòu)上實現(xiàn)棧的基本運算，特別注意棧滿和?？盏呐袛鄺l件及描述方法； 3.4.2實驗內(nèi)容 1) 采用雙棧，一個棧用來保存運算符，一個棧用來保存數(shù)據(jù)2) 符號優(yōu)先級設(shè)置 i（+ -） 棧外運算符優(yōu)先級：可以計算，計算結(jié)果壓入數(shù)據(jù)棧當(dāng)棧內(nèi)運算符優(yōu)先級 棧外運算符優(yōu)先級：棧外運算符壓入運算符棧 當(dāng)棧內(nèi)運算符優(yōu)先級 = 棧外運算符優(yōu)先級：只可能是左括出棧即可源程序代碼：#include #include using namespace std;/符號數(shù)組char symbol7 = +, -, *, /, (, ), #;/棧內(nèi)元素的優(yōu)先級int in7 = 3, 3, 5, 5, 1, 6, 0;/棧外元素的優(yōu)先級int out7 = 2, 2, 4, 4, 6, 1, 0;/* * 通過符號字符獲取它的數(shù)組下標(biāo) */int get(char c)switch(c)case +:return 0;case -:return 1;case *:return 2;case /:return 3;case (:return 4;case ):return 5;case #:return 6;default: return 6;/* * 比較棧內(nèi)運算符c1和棧外運算符c2的優(yōu)先級 */char precede(char c1, char c2)int i1 = get(c1);int i2 = get(c2);if(ini1 outi2)return ;else if(ini1 outi2)return ;elsereturn =;/* * 計算基本表達(dá)式的值 */int figure(int a, int theta, int b)switch(theta)case 0:return a + b;case 1:return a - b;case 2:return a * b;default:return a / b;/* * 計算表達(dá)式的值 */int EvaluateExpression(const char *exp)stack data; /數(shù)據(jù)棧stack oper; /符號棧oper.push(get(#);int sum = 0;int flag = 1; /表示正負(fù)號 1,表示正 0,表示負(fù)int a, theta, b;if(!(+ = *exp | - = *exp | ( = *exp | isdigit(*exp)cout 表達(dá)式出錯1 :b = data.top();data.pop();a = data.top();data.pop();theta = oper.top();oper.pop();data.push(figure(a, theta, b);break;case :oper.push(get(*exp);if(*exp)exp+;break;case = :oper.pop();if(*exp)exp+;break;index = oper.top();return data.top();int main()cout EvaluateExpression(8+6)*2-8)/2) endl;system(pause);return 0; 運行結(jié)果： 3.5哈希表的設(shè)計 3.5.1實驗?zāi)康?熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其他結(jié)構(gòu)表的實質(zhì)性差別。 3.5.2實驗內(nèi)容 程序的功能是對一批關(guān)鍵字集合采用除留余數(shù)和拉鏈法解決沖突來建立相應(yīng)的哈希表。 源程序代碼：#include #include #define uint8_t unsigned char#define uint16_t unsigned short#define uint32_t unsigned long#define HASH_TABLE_LEN100typedef struct _Link_Node uint16_t id;uint16_t data; struct _Link_Node *next; Link_Node,*Link_Node_Ptr; typedef struct _Hash_Header struct _Link_Node *next; Hash_Header,*Hash_Header_Ptr;Hash_Header_Ptr Hash_TableHASH_TABLE_LEN;uint8_t hash_func(uint16_t id)uint8_t pos = 0;pos = id % HASH_TABLE_LEN;return pos;Link_Node_Ptr init_link_node(void)Link_Node_Ptr node;node = (Link_Node_Ptr) malloc(sizeof(Link_Node);node-next = NULL;return node;Hash_Header_Ptr init_hash_header_node(void)Hash_Header_Ptr node;node = (Hash_Header_Ptr) malloc(sizeof(Hash_Header);node-next = NULL;return node;void init_hash_table(void)uint8_t i = 0;for (i = 0;i next = NULL;void append_link_node(Link_Node_Ptr new_node)Link_Node_Ptr node;uint8_t pos = 0;new_node-next = NULL;pos = hash_func(new_node-id);if (Hash_Tablepos-next = NULL)Hash_Tablepos-next = new_node;elsenode = Hash_Tablepos-next;while (node-next != NULL)node = node-next;node-next = new_node;Link_Node_Ptr search_link_node(uint16_t id,uint8_t *root)Link_Node_Ptr node;uint8_t pos = 0;pos = hash_func(id);node = Hash_Tablepos-next;if (node = NULL)return 0;if (node-id = id)*root = 1;return node;else*root = 0;while (node-next != NULL)if (node-next-id = id)return node;elsenode = node-next;return 0;void delete_link_node(Link_Node_Ptr node)Link_Node_Ptr delete_node;delete_node = node-next;node-next = delete_node-next;free(delete_node);delete_node = NULL;void delete_link_root_node(Link_Node_Ptr node)uint8_t pos = 0;pos = hash_func(node-id);if (node != NULL)Hash_Tablepos-next = node-next;free(node);node = NULL;uint16_t get_node_num(void)Link_Node_Ptr node;uint16_t i = 0;uint16_t num = 0;for (i = 0;i next;while (node != NULL)num+;node = node-next;return num;Link_Node_Ptr get_node_from_index(uint16_t index,uint8_t *root) Link_Node_Ptr node;uint16_t i = 0;uint16_t num = 0;for (i = 0;i next;if (node = NULL)continue;num+; if (num = index) *root = 1; return node; while (node-next != NULL)num+; if (num = index) *root = 0; return node; node = node-next; return 0;void drop_hash()Link_Node_Ptr node;uint16_t i = 0;Link_Node_Ptr node_next;for (i = 0;i next;while (1) if (node = NULL)Hash_Tablei-next = NULL;break;node_next = node-next;free(node); node = node_next;void printf_hash()Link_Node_Ptr node;uint8_t root = 0;uint8_t i = 0;uint8_t num = 0;printf(-打印hash表-n);num = get_node_num();for (i = 1;i id);elseprintf(普通節(jié)點:節(jié)點號%d,id為%dn,i,node-next-id);int main()Link_Node_Ptr node;uint8_t temp = 0;uint8_t root = 0;uint8_t i = 0;init_hash_table();node = init_link_node();node-id = 1;node-data = 2;append_link_node(node); printf(1節(jié)點數(shù)為%dn,get_node_num();node = init_link_node();node-id = 100;node-data = 101;append_link_node(node);node = init_link_node();node-id = 1002;node-data = 1001;append_link_node(node);node = init_link_node();node-id = 10000;node-data = 10001;append_link_node(node);node = init_link_node();node-id = 1000;node-data = 10001;append_link_node(node);node = init_link_node();node-id = 2;node-data = 10001;append_link_node(node); printf(2節(jié)點數(shù)為%dn,get_node_num();node = search_link_node(100,&temp);if (node != 0)if (temp = 0)printf(刪除普通節(jié)點:所需查詢id的值為%d,數(shù)據(jù)為%dn,node-next-id,node-next-data); delete_link_node(node);elseprintf(刪除根節(jié)點所需查詢id的值為%d,數(shù)據(jù)為%dn,node-id,node-data);delete_link_root_node(node);elseprintf(查詢失敗n);node = search_link_node(1001,&temp);if (node != 0)if (temp = 0)printf(所需查詢id的值為%dn,node-next-data);else printf(所需查詢id的值為%dn,node