數(shù)據(jù)結構實驗報告.docx

數(shù)據(jù)結構實驗報告實驗名稱 數(shù)據(jù)結構與算法 專業(yè)班級 數(shù)學與應用數(shù)學1201班學 號 1304120306姓 名 謝 偉指導老師 陳 明目 錄1前言.22數(shù)據(jù)結構與算法實驗概要.2 2.1實驗要求2 2.2主要儀器設備.2 2.3實驗內(nèi)容與簡介23數(shù)據(jù)結構設計與算法設計.3 3.1線性表的操作.3 3.2二叉樹的操作.8 3.3圖的遍歷操作.12 3.4棧的基本操作.19 3.5哈希表設計.284實驗總結與心得體會.395參考文獻. 401前言數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已經(jīng)成為其他理工專業(yè)的熱門選修課。隨著計算機科學的技術和發(fā)展，計算機的功能和運算速度不斷地提高，其應用于信息處理的范圍日益擴大。與之相應的，計算機的加工處理對象也從簡單的數(shù)據(jù)發(fā)展到一般的符號，進而發(fā)展到更復雜的數(shù)據(jù)結構。數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，數(shù)據(jù)結構的表示和操作都涉及到算法，如何描述數(shù)據(jù)的結構和討論有關的算法，又涉及到程序設計語言。因此，它不僅是計算機學科的核心課程，而且已經(jīng)成為其他理工專業(yè)的熱門選修課。 我們通過對這門基礎課程的學習，要學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適合的邏輯結構，儲存結構及其相應的算法，并初步掌握算法時間分析和空間分析的技術。通過實際操作去了解數(shù)據(jù)結構原理， 練習編寫代碼的能力，以及抽象能力。從課程性質(zhì)上講，“數(shù)據(jù)結構”是一門專業(yè)技術基礎課。它的要求是學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構，存儲結構及相應的算法，并初步掌握算法的時間分析和空間分析的技術。另一方面，數(shù)據(jù)結構的學習過程也是復雜程序設計的訓練過程，要求編 寫的程序結構清楚和正確易讀，符合軟件工程的規(guī)范。2數(shù)據(jù)結構與算法實驗概要 2.1實驗要求書寫類C語言的算法，并將算法轉(zhuǎn)變?yōu)槌绦驅(qū)崿F(xiàn)。正確理解各種數(shù)據(jù)結構的邏輯特性和存儲表示和基本操作的算法實現(xiàn)。針對問題的不同選擇合適的數(shù)據(jù)結構，提高算法設計的能力和動手實驗的技能。 2.2實驗儀器設備硬件要求：在多媒體教室講解及演示。為保證教學順利進行，要求實驗室提供P及以上的微機。 2.3實驗項目內(nèi)容簡介 1、線性表基本操作（1）熟悉線性表的基本運算在兩種存儲結構（順序結構和鏈式結構）上的實現(xiàn)（2）以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為重點（3）通過本次實習幫助學生加深對c+的使用（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。2、棧、隊列以及遞歸算法的設計（1）掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們（2）訓練的要點是“?！钡挠^點及其典型用法；問題求解的狀態(tài)表示及其遞歸算法；由遞歸程序到非遞歸程序的轉(zhuǎn)化方法 3、樹、圖及其應用 （1）樹和圖是兩種非線性數(shù)據(jù)結構，廣義表的實質(zhì)是樹結構，而稀疏矩陣的十字鏈表存儲結構也是圖的一種存儲結構，故本單元是本課的實習重點。（2）要求我們熟悉各種存儲結構的特性，以及如何應用樹和圖結構求解具體問題。（3）訓練的要點是：遞歸算法的設計方法；表達式的求值技術；哈夫曼方法及其編譯碼技術；完整的應用系統(tǒng)的用戶界面設計和操作定義方法；矩陣乘法的特殊操作順序；路徑遍歷（樹、圖的遍歷）技術。4、查找和排序本次實習旨在集中對幾個專門的問題做較為深入的探討和理解重點在掌握各種內(nèi)部排序算法、查找算法的思想和實現(xiàn)。學生在實習中體會查找和內(nèi)部排序算法思想，理解開發(fā)高效算法的可能性和尋找、構造高效算法的方法。3數(shù)據(jù)結構設計與算法設計 3.1線性表的操作 3.1.1實驗目的1熟悉C+語言的上機環(huán)境，掌握C+語言的基本結構。2會定義線性表的順序存儲結構。（鏈式存儲結構）3熟悉對順序表（單鏈表）的一些基本操作。 3.1.2實驗內(nèi)容 單鏈表的基礎操作 包括： 查找、插入、刪除、創(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) ; 運行結果： 3.2二叉樹的操作 3.2.1實驗目的 理解并熟悉掌握創(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)建二叉樹，如果是#當前樹根置為空，否則申請一個新節(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為指向二叉樹(或某一子樹)根結點的指針*/ if (root!=NULL) Visit(root -data); /*訪問根結點*/ PreOrder(root -LChild); /*先序遍歷左子樹*/ PreOrder(root -RChild); /*先序遍歷右子樹*/ void InOrder(BitTree root) /*中序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結點的指針*/ if (root!=NULL) InOrder(root -LChild); /*中序遍歷左子樹*/ Visit(root -data); /*訪問根結點*/ InOrder(root -RChild); /*中序遍歷右子樹*/ void PostOrder(BitTree root) /* 后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結點的指針*/ if(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹*/ PostOrder(root -RChild); /*后序遍歷右子樹*/ Visit(root -data); /*訪問根結點*/ 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(); 運行結果： 3.3圖的遍歷操作 3.3.1實驗目的 該實驗主要完成對圖的創(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); 運行結果： 3.4棧的基本操作 3.4.1實驗目的1熟練掌握棧的結構，以及這種數(shù)據(jù)結構的特點；2 能夠在兩種存儲結構上實現(xiàn)棧的基本運算，特別注意棧滿和棧空的判斷條件及描述方法； 3.4.2實驗內(nèi)容 1) 采用雙棧，一個棧用來保存運算符，一個棧用來保存數(shù)據(jù)2) 符號優(yōu)先級設置 i（+ -） 棧外運算符優(yōu)先級：可以計算，計算結果壓入數(shù)據(jù)棧當棧內(nèi)運算符優(yōu)先級 棧外運算符優(yōu)先級：棧外運算符壓入運算符棧 當棧內(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ù)組下標 */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 =;/* * 計算基本表達式的值 */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;/* * 計算表達式的值 */int EvaluateExpression(const char *exp)stack data; /數(shù)據(jù)棧stack oper; /符號棧oper.push(get(#);int sum = 0;int flag = 1; /表示正負號 1,表示正 0,表示負int a, theta, b;if(!(+ = *exp | - = *exp | ( = *exp | isdigit(*exp)cout 表達式出錯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; 運行結果： 3.5哈希表的設計 3.5.1實驗目的 熟練掌握哈希表的構造方法，深刻理解哈希表與其他結構表的實質(zhì)性差別。 3.5.2實驗內(nèi)容 程序的功能是對一批關鍵字集合采用除留余數(shù)和拉鏈法解決沖突來建立相應的哈希表。 源程序代碼：#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