信管数据结构实验.docx
- 文档编号:2963345
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:13
- 大小:20.13KB
信管数据结构实验.docx
《信管数据结构实验.docx》由会员分享,可在线阅读,更多相关《信管数据结构实验.docx(13页珍藏版)》请在冰点文库上搜索。
信管数据结构实验
数据结构实验一C语言结构体与指针
一、实验目的
巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点,加强学习数据结构语言基础。
二、实验内容
实现病历查询功能。
具体要求如下:
定义一个结构体描述病人病历信息(病历号,姓名,年龄,性别,症状);先输入5个病人的信息,然后输入姓名,在5个病历中进行查找,如果找到则显示该人的信息,如果没有找到,则显示“查无此人”。
假设病历类型名为patient,使用指针,请使用以下两个函数。
voidreadin(patient*p);//用来输入病人信息。
voidsearch(patient*p,char*x);//根据姓名查询病人病历信息,并打印出来。
三、实验源代码
此处写程序源代码,请在程序中适当注释,便于老师更快地看懂你的程序。
四、实验结果
此处写出程序运行的结果,即输入数据是什么,输出数据是什么,分析结果是否正确,如果不正确是什么原因。
五、实验心得
此处写出完成此实验后有什么收获,碰到什么因难,又是如何解决的。
请不要写“这门课好难学”、“一点也不会”之类的话语,因为这对你学习并没有帮助。
关键是通过实验发现自己不会的知识点,然后攻克它!
数据结构实验二顺序表的运用
一、实验目的
1、掌握建立顺序表的基本方法。
2、掌握顺序表的插入、删除算法的思想和实现,并能灵活运用
二、实验内容
用顺序表实现病历信息的管理与查询功能。
具体要求如下:
1.利用教材中定义顺序表类型存储病人病历信息(病历号,姓名,年龄,性别,症状);要求使用头文件,程序具有输入、输出功能。
2.设计顺序表定位查找算法,完成的功能为:
在线性表L中查找数据元素x,如果存在则返回线性表中和x值相等的第1个数据元素的序号;如果不存在,则返回-1。
函数定义为intListFind(SeqListL,char*x)
请在主函数中测试查找是否存在姓名为x的病人,并根据返回的序号打印出病人信息。
数据结构实验三有序单链表
一、【实验目的】
1、掌握建立单链表的基本方法。
2、掌握单链表的插入、删除算法的思想和实现
二、【实验内容】
仿照教材中的单链表示例,设计一个有序单链表。
有序单链表的定义:
逻辑结构:
有序线性表
存储结构:
链式
操作集合:
初始化、插入、删除、撤销
(1)ListInitiate(L)初始化线性表,生成一个空表L。
(2)ListInsert(L,x)在有序表L中插入数据元素x,使得新表仍然有序。
(3)ListDelete(L,x)删除有序表L中的数据元素x,若删除成功则返回1,不成功则返回0。
(4)Destroy(L)撤销单链表
要求:
1.有序单链表的操作集合有如下操作:
初始化、插入、删除、撤销。
2.通过主函数验证所设计的有序单链表的正确性。
提示:
1.插入操作时,从链表的第一个数据元素结点开始,逐个比较每个结点的data域值和x的值,当data小于等于x时,进行下一个结点的比较;否则就找到了插入结点的合适位置,此时申请新结点把x存入,然后把新结点插入;当比较到最后一个结点仍有data小于等于x时,则把新结点插入单链表尾。
2.删除操作时,从链表的第一个数据元素结点开始,逐个比较每个结点的data域值和x的值,当data小于等于x时,进行下一个结点的比较;否则就找到了要删除的结点,删除结点后释放结点。
如果到了表尾还没有找到值为x的结点,则链表中没有要删除的元素。
数据结构实验四栈和队列的应用
一、实验目的
1、掌握顺序堆栈的类型定义方法。
2、掌握顺序堆栈上实现的几种基本操作。
3、掌握顺序队列的类型定义方法。
4、掌握顺序队列上实现的几种基本操作。
二、实验内容
设计算法判断一个字符序列是否是回文,要求采用队列和堆栈结构。
提示:
设字符数组str中存放了要判断的字符串。
把字符数组中的字符逐个分别存入队列和堆栈,然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等,若全部相等则该字符序列是回文,否则就不是回文。
三、实验源代码
四、实验结果
数据结构实验五递归算法的实现
一、实验目的
1、掌握递归原理
2、掌握一些常用问题的递归算法设计
二、实验内容
1.有这样一个故事:
猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。
第二天早上又将剩下的桃子吃掉一半,又多吃了一个。
以后每天早上都吃了前一天剩下的一半零一个。
到第30天早上想再吃时,见只剩下一个桃子了。
那么你知道猴子第一天共摘了多少个桃子吗?
1)请用递归和非递归算法分别实现猴子吃桃问题的求解。
2)求解过程请用函数实现。
要求能够计算:
如果在第N天只剩下一个桃子了,那么第一天共摘了多少个桃子。
2.编写折半查找算法的递归实现和非递归实现,并在VC++的调试环境下观察折半查找递归程序的调用与返回过程,并记录其过程和返回值。
提示:
将要查找的元素key与查找区间正中元素相比,若key小,则查找区间缩小至前半部份查找,若key大,则查找区间缩小至后半部份查找;再取其中值比较,每次缩小1/2的范围,直到查找成功或失败为止。
如递归实现,考虑函数的参数应有哪些。
在用循环结构实现时,函数的参数有什么变化?
三、实验源代码
四、实验结果
数据结构实验六二叉树的遍历应用
一、【实验目的】
1、掌握二叉树的建立方法
2、掌握二叉树遍历的基本方法(前序、中序、后序)
3、掌握递归二叉树遍历算法的应用
二、【实验内容】
1.构造一棵二叉树,树的形态如下图所示,打印出前序遍历、中序遍历、后序遍历的遍历序列。
A
BF
CEG
D
2.选择一种遍历方式计算该树中叶子结点的个数,并打印出叶子结点。
二叉树的定义可参考以下代码
定义头文件为BiTree.h
typedefstructNode
{
ElemTypedata;/*数据域*/
structNode*leftChild;/*左子树指针*/
structNode*rightChild;/*右子树指针*/
}BiTreeNode;/*结点的结构体定义*/
/*初始化创建二叉树的头结点*/
voidInitiate(BiTreeNode**root)
{
*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
voidDestroy(BiTreeNode**root)
{
if((*root)!
=NULL&&(*root)->leftChild!
=NULL)
Destroy(&(*root)->leftChild);
if((*root)!
=NULL&&(*root)->rightChild!
=NULL)
Destroy(&(*root)->rightChild);
free(*root);
}
/*若当前结点curr非空,在curr的左子树插入元素值为x的新结点*/
/*原curr所指结点的左子树成为新插入结点的左子树*/
/*若插入成功返回新插入结点的指针,否则返回空指针*/
BiTreeNode*InsertLeftNode(BiTreeNode*curr,ElemTypex)
{
BiTreeNode*s,*t;
if(curr==NULL)returnNULL;
t=curr->leftChild;/*保存原curr所指结点的左子树指针*/
s=(BiTreeNode*)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;/*新插入结点的左子树为原curr的左子树*/
s->rightChild=NULL;
curr->leftChild=s;/*新结点成为curr的左子树*/
returncurr->leftChild;/*返回新插入结点的指针*/
}
/*若当前结点curr非空,在curr的右子树插入元素值为x的新结点*/
/*原curr所指结点的右子树成为新插入结点的右子树*/
/*若插入成功返回新插入结点的指针,否则返回空指针*/
BiTreeNode*InsertRightNode(BiTreeNode*curr,ElemTypex)
{
BiTreeNode*s,*t;
if(curr==NULL)returnNULL;
t=curr->rightChild;/*保存原curr所指结点的右子树指针*/
s=(BiTreeNode*)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;/*新插入结点的右子树为原curr的右子树*/
s->leftChild=NULL;
curr->rightChild=s;/*新结点成为curr的右子树*/
returncurr->rightChild;/*返回新插入结点的指针*/
}
/*若curr非空,删除curr所指结点的左子树*/
/*若删除成功返回删除结点的双亲结点指针,否则返回空指针*/
BiTreeNode*DeleteLeftTree(BiTreeNode*curr)
{
if(curr==NULL||curr->leftChild==NULL)returnNULL;
Destroy(&curr->leftChild);
curr->leftChild=NULL;
returncurr;
}
/*若curr非空,删除curr所指结点的右子树*/
/*若删除成功返回删除结点的双亲结点指针,否则返回空指针*/
BiTreeNode*DeleteRightTree(BiTreeNode*curr)
{
if(curr==NULL||curr->rightChild==NULL)returnNULL;
Destroy(&curr->rightChild);
curr->rightChild=NULL;
returncurr;
}
三、【实验源代码】
四、【实验结果】
五、【实验心得】
数据结构实验七图的操作实现
一、【实验目的】
1、 理解图的逻辑结构和存储结构
2、掌握图的邻接矩阵的操作实现
2、熟悉图的广度优先遍历的实现
二、【实验内容】
(1) 建立大学城及周边景点的图逻辑结构,要求包含十所高校、中心湖、生物岛、长洲岛、岭南印象园等景点。
(2) 用邻接矩阵方式输出图的存储结构。
提示:
建立图的数学模型时,可依据大学城地图及google地图,选取主要路线,建立各顶点的连通图。
此题分小组做,每个组根据自己的理解建立的图模型,不一定要一样。
实验八排序算法的实现
一、【实验目的】
1、掌握插入排序算法和交换排序算法
2、掌握各种排序算法的优劣
二、【实验内容】
1.对比数据元素个数为10000并数据元素大小杂乱时,分别采用快速排序算法,直接选择排序算法时的实际耗时。
2.对比数据元素个数为10000并数据元素为逆序排列时,分别采用快速排序算法,直接选择排序算法时的实际耗时。
3.对比数据元素个数为10000并数据元素为顺序排列时,分别采用快速排序算法,直接选择排序算法时的实际耗时。
提示:
在程序的实现过程要可以用到以下函数,请大家在实验之前自学这几个函数的用法:
1)随机函数rand()
2)时间函数time()
3)时间差函数difftime()
思考:
能否将实际耗时显示为毫秒级?
考虑clock函数。
三、【实验源代码】
四、【实验结果】
五、【实验心得】
实验九动态查找算法的实现
一、【实验目的】
1、掌握二叉排序树的基本概念
2、掌握二叉排序树的基本算法(查找算法、插入算法、删除算法)
2、理解并掌握二叉排序数查找的平均查找长度。
二、【实验内容】
1、已知一个个数为12的数据元素序列为{Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar},要求:
(1)按各数据元素的顺序(字母大小顺序)构造一棵二叉排序数,并中序打印排序结果。
(2)查找数据”Sept”是否存在。
三、【实验源代码】
四、【实验结果】
五、【实验心得】
选作实验
实验有序顺序表
一、【实验目的】
1、掌握建立顺序表的基本方法。
2、掌握顺序表的插入、删除算法的思想和实现
二、【实验内容】仿照教材中的顺序表示例,设计一个有序顺序表(数据元素从小到有序),有序顺序表数据类型定义如下:
?
逻辑结构:
有序线性表
?
存储结构:
顺序
?
操作集合:
初始化、插入、删除,具体说明如下:
(1)ListInitiate(L)初始化线性表,生成一个空表
(2)ListInsert(L,x)在有序表L中插入数据元素x,使得新表仍然有序
(3)ListDelete(L,x)在有序表L中删除数据元素x
并通过主函数验证所设计的有序顺序表的正确性。
提示:
插入操作时,从顺序表的第一个数据元素开始,逐个比较list[i]值和x的值,当list[i]值小于等于x时,进行下一个结点的比较;否则就找到了插入结点的合适位置,向后移动元素,腾出空位,插入元素x;当比较到最后一个结点仍有list[i]值小于等于x时,则把x插入到顺序表表尾。
实验线性表综合应用
一、【实验目的】
1、掌握线性表的两种存储结构的灵活运用。
二、【实验内容】
约瑟夫环(Josephus)问题的求解
具体描述是:
设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第K个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。
当任意给定n和m后,设计算法求n个人出圈的次序。
请根据以上描述,选择合适的存储结构,完成约瑟夫环的求解。
请打印出出圈人的序号。
提示:
约瑟夫环问题主要可分解为建环、删除两个操作。
可使用课上给出的头文件。
三、实验源代码
实验栈
一、实验目的:
1.掌握堆栈的存储方式和基本操作
2.掌握堆栈后进先出运算原则在解决实际问题中的应用
3.掌握使用栈的原理来解决数制转换问题。
二、实验内容:
1.利用栈结构,编写程序将十进制数转换成二进制数或八进制数。
说明:
十进制数值转换成二进制使用辗转相除法将一个十进制数值转换成二进制数值。
即用该十进制数值除以2,并保留其余数;重复此操作,直到该十进制数值为0为止。
最后将所有的余数反向输出就是所对应的二进制数值。
十进制数值转换成八进制算法类似。
转换算法要求用一个函数完成。
三、实验源代码
四、实验结果
五、实验心得
实验队列
一、实验目的
1.掌握队列的顺序存储结构
2.掌握队列先进先出运算原则在解决实际问题中的应用
二、实验内容
仿照教材顺序循环队列的例子,设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。
其中操作包括:
初始化、入队列、出队列、判断队列是否非空。
编写主函数,验证所设计的顺序循环队列的正确性。
以下是队列操作函数的定义:
(1)QueueInitiate(Q)初始化队列Q
(2)QueueNotEmpty(Q)队列Q非空否
(3)QueueAppend(Q,x)入队列,在队列Q的队尾插入数据元素x。
(4)QueueDelete(Q,d)出队列,把队列Q的队头元素删除并由参数d带回。
提示:
队尾的位置可由队头指针与计数器进行求解,请思考它们之间的关系,同时还要考虑如何实现循环队列(可借助求模运算)。
三、实验源代码
四、实验结果(测试数据)
五、实验心得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验