數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告.docx

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