数据结构实验报告.docx

数据结构实验报告实验名称 数据结构与算法 专业班级 数学与应用数学1201班学 号 1304120306姓 名 谢 伟指导老师 陈 明目 录1前言.22数据结构与算法实验概要.2 2.1实验要求2 2.2主要仪器设备.2 2.3实验内容与简介23数据结构设计与算法设计.3 3.1线性表的操作.3 3.2二叉树的操作.8 3.3图的遍历操作.12 3.4栈的基本操作.19 3.5哈希表设计.284实验总结与心得体会.395参考文献. 401前言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。 我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去了解数据结构原理， 练习编写代码的能力，以及抽象能力。从课程性质上讲，“数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编 写的程序结构清楚和正确易读，符合软件工程的规范。2数据结构与算法实验概要 2.1实验要求书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。 2.2实验仪器设备硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供P及以上的微机。 2.3实验项目内容简介 1、线性表基本操作（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现（2）以线性表的各种操作（建立、插入、删除等）的实现为重点（3）通过本次实习帮助学生加深对c+的使用（特别是函数参数、指针类型、链表的使用）。2、栈、队列以及递归算法的设计（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们（2）训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法 3、树、图及其应用 （1）树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。（2）要求我们熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。（3）训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。4、查找和排序本次实习旨在集中对几个专门的问题做较为深入的探讨和理解重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。3数据结构设计与算法设计 3.1线性表的操作 3.1.1实验目的1熟悉C+语言的上机环境，掌握C+语言的基本结构。2会定义线性表的顺序存储结构。（链式存储结构）3熟悉对顺序表（单链表）的一些基本操作。 3.1.2实验内容 单链表的基础操作 包括： 查找、插入、删除、创建链表等。 源程序代码：#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实验目的 理解并熟悉掌握创建二叉树和实现二叉树的三种遍历 3.2.2实验内容 创建二叉树并实现二叉树的三中遍历操作 源程序代码：#include#include #include typedef int DataType; typedef struct Node DataType data; struct Node *LChild; struct Node *RChild;BitNode,*BitTree;void CreatBiTree(BitTree *bt)/用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点/ 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)/访问根节点 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实验目的 该实验主要完成对图的创建，并实现图的深度优先遍历和广度优先遍历 3.3.2实验内容 编写程序完成图的创建，并实现图的深度和广度优先遍历 源程序代码：#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熟练掌握栈的结构，以及这种数据结构的特点；2 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； 3.4.2实验内容 1) 采用双栈，一个栈用来保存运算符，一个栈用来保存数据2) 符号优先级设置 i（+ -） 栈外运算符优先级：可以计算，计算结果压入数据栈当栈内运算符优先级 栈外运算符优先级：栈外运算符压入运算符栈 当栈内运算符优先级 = 栈外运算符优先级：只可能是左括出栈即可源程序代码：#include #include using namespace std;/符号数组char symbol7 = +, -, *, /, (, ), #;/栈内元素的优先级int in7 = 3, 3, 5, 5, 1, 6, 0;/栈外元素的优先级int out7 = 2, 2, 4, 4, 6, 1, 0;/* * 通过符号字符获取它的数组下标 */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;/* * 比较栈内运算符c1和栈外运算符c2的优先级 */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; /数据栈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实验目的 熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。 3.5.2实验内容 程序的功能是对一批关键字集合采用除留余数和拉链法解决冲突来建立相应的哈希表。 源程序代码：#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(普通节点:节点号%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节点数为%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节点数为%dn,get_node_num();node = search_link_node(100,&temp);if (node != 0)if (temp = 0)printf(删除普通节点:所需查询id的值为%d,数据为%dn,node-next-id,node-next-data); delete_link_node(node);elseprintf(删除根节点所需查询id的值为%d,数据为%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-data