1、- 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、热门选修课。随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。 我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去
3、了解数据结构原理， 练习编写代码的能力，以及抽象能力。从课程性质上讲， “数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编 写的程序结构清楚和正确易读，符合软件工程的规范。2 数据结构与算法实验概要2.1 实验要求书写类 C 语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。2.2
4、 实验仪器设备硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供- 3 -P及以上的微机。2.3 实验项目内容简介1、线性表基本操作 （1 ） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现（2 ）以线性表的各种操作（建立、插入、删除等）的实现为重点（3 ） 通过本次实习帮助学生加深对 c+的使用（特别是函数参数、指针类型、链表的使用） 。2、栈、队列以及递归算法的设计（1 ）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们（2 ）训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方
5、法3、树、图及其应用 （1 ） 树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。（2 ） 要求我们熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。（3 ）训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。4、查找和排序本次实习旨在集中对几个专门的问题做较为深入的探讨和理解重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能
6、性和寻找、构造高效算法的方法。3 数据结构设计与算法设计3.1 线性表的操作3.1.1 实验目的1熟悉 C+语言的上机环境，掌握 C+语言的基本结构。2会定义线性表的顺序存储结构。 （链式存储结构）3熟悉对顺序表（单链表）的一些基本操作。- 4 -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!=NUL
7、L 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; - 5 -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 if (qPre
8、!=NULL free(p); Node* CreateListAhead(int a,int n) Node *s,*pHead; int i; pHead=(Node*)malloc(sizeof(Node); pHead-data=0; - 6 -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,*p
9、Tail; 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) - 7 - 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 *pH
10、ead,*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); - 8 -while(getchar()!=a) ; 运行结果：3.2 二叉树的操作3.2.1 实验目的理解并熟悉掌握创建二叉树和实现二叉树的三种遍历3.2.2 实验内容创建二叉树并实现二叉树的三中遍历操作源程序代码：
11、#include#include #include typedef int DataType; typedef struct Node- 9 -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(CreatBiTree(void Visit(char ch)/访问根节点printf(“%c “,ch);void PreOrder(BitTree root) /*先序遍历二叉树, root 为指向二叉树 (或某一子树)根结点的指针*/if (root!=NULL)Visit(root -data); /*访问根结点*/PreOrder(root -LChild); /*先序遍历左子树*/PreOrder(root -RChild); /*先序遍历右子树*/
