数据结构实验报告

-0-数据结构实验报告实验名称数据结构与算法专业班级数学与应用数学1201班学号1304120306姓名谢伟指导老师陈明-1-目录1前言…………………………………………………………………….22数据结构与算法实验概要…………………………………………….22.1实验要求…………………………………………………………22.2主要仪器设备…………………...............................................22.3实验内容与简介…………………………………………………23数据结构设计与算法设计…………………………………………….33.1线性表的操作……………………………………………….......33.2二叉树的操作……………………………………………….......83.3图的遍历操作……………………………………………….....123.4栈的基本操作………………………………………………….193.5哈希表设计…………………………………………………….284实验总结与心得体会………………………………………………...395参考文献……………………………………………………………..40-2-1前言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去了解数据结构原理，练习编写代码的能力，以及抽象能力。从课程性质上讲，“数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读，符合软件工程的规范。2数据结构与算法实验概要2.1实验要求书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。2.2实验仪器设备硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PⅢ及以上的微机。2.3实验项目内容简介1、线性表基本操作（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现（2）以线性表的各种操作（建立、插入、删除等）的实现为重点（3）通过本次实习帮助学生加深对c++的使用（特别是函数参数、指针类型、链表的使-3-用）。2、栈、队列以及递归算法的设计（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们（2）训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法3、树、图及其应用（1）树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。（2）要求我们熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。（3）训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。4、查找和排序本次实习旨在集中对几个专门的问题做较为深入的探讨和理解重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。3数据结构设计与算法设计3.1线性表的操作3.1.1实验目的1．熟悉C++语言的上机环境，掌握C++语言的基本结构。2．会定义线性表的顺序存储结构。（链式存储结构）3．熟悉对顺序表（单链表）的一些基本操作。3.1.2实验内容单链表的基础操作包括：查找、插入、删除、创建链表等。源程序代码：#includestdlib.h#includestdio.htypedefstructNode-4-{intdata;structNode*next;}Node;Node*Serach(Node*pHead,intx){Node*p=pHead;while(p!=NULL&&p-data!=x)p=p-next;returnp;}voidInsert(Node*p,intx){Node*s;s=(Node*)malloc(sizeof(Node));s-data=x;s-next=p-next;p-next=s;}voidDeleteFollowNode(Node*p){Node*q;q=p-next;if(q!=NULL){p-next=q-next;free(q);}-5-}voidDelete(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(inta[],intn){Node*s,*pHead;inti;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=a[i];s-next=pHead-next;-6-pHead-next=s;}returnpHead;}Node*CreateListTail(inta[],intn){Node*s,*pHead,*pTail;inti;pHead=(Node*)malloc(sizeof(Node));pHead-data=0;pHead-next=NULL;pTail=pHead;for(i=0;in;i++){s=(Node*)malloc(sizeof(Node));s-data=a[i];s-next=NULL;pTail-next=s;pTail=s;}returnpHead;}voidPrint(Node*h){Node*p;p=h-next;while(p!=NULL){-7-printf(%d,,p-data);p=p-next;}printf(\n);}voidmain(){inta[]={3,2,1,4,5};Node*pHead,*p;pHead=CreateListTail(a,5);Print(pHead);p=Serach(pHead,4);printf(%d\n,p-data);p=pHead-next-next;Insert(p,9);Print(pHead);p=pHead-next-next-next;Delete(p,pHead);Print(pHead);while(getchar()!='a');}运行结果：-8-3.2二叉树的操作3.2.1实验目的理解并熟悉掌握创建二叉树和实现二叉树的三种遍历3.2.2实验内容创建二叉树并实现二叉树的三中遍历操作源程序代码：#includestdio.h#includemalloc.h#includeconio.htypedefintDataType;typedefstructNode{DataTypedata;structNode*LChild;structNode*RChild;}BitNode,*BitTree;-9-voidCreatBiTree(BitTree*bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点//{charch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));(*bt)-data=ch;CreatBiTree(&((*bt)-LChild));CreatBiTree(&((*bt)-RChild));}}voidVisit(charch)//访问根节点{printf(%c,ch);}voidPreOrder(BitTreeroot)/*先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/{if(root!=NULL){Visit(root-data);/*访问根结点*/PreOrder(root-LChild);/*先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树*/}}voidInOrder(BitTreeroot)/*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/-10-{if(root!=NULL){InOrder(root-LChild);/*中序遍历左子树*/Visit(root-data);/*访问根结点*/InOrder(root-RChild);/*中序遍历右子树*/}}voidPostOrder(BitTreeroot)/*后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/{if(root!=NULL){PostOrder(root-LChild);/*后序遍历左子树*/PostOrder(root-RChild);/*后序遍历右子树*/Visit(root-data);/*访问根结点*/}}intPostTreeDepth(BitTreebt)//后序遍历求二叉树的高度递归算法//{inthl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt-LChild);//求左子树的深度hr=PostTreeDepth(bt-RChild);//求右子树的深度max=hlhr?hl:hr;//得到左、右子树深度较大者return(max+1);//返回树的深度}elsereturn(0);//如果是空树，则返回0-11-}voidPrintTree(BitTreeBoot,intnLayer)//按竖向树状打印的二叉树//{inti;if(Boot==NULL)return;PrintTree(Boot-RChild,nLayer+1);for(i=0;inLayer;i++)printf();printf(%c\n,Boot-data);PrintTree(Boot-LChild,nLayer+1);}voidmain(){BitTreeT;inth;intlayer;inttreeleaf;layer=0;printf(请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):\n);CreatBiTree(&T);printf(先序遍历序列为:);PreOrder(T);printf(\n中序遍历序列为:);InOrder(T);printf(\n后序遍历序列为:);PostOrder(T);h=PostTreeDepth(T);printf(\nThedepthofthistreeis:%d\n,h);PrintTree(T,layer);-12-getch();}