计算机数据结构实验指导.pdf

《计算机数据结构实验指导.pdf》由会员分享，可在线阅读，更多相关《计算机数据结构实验指导.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 数据结构实验一 C 语言结构体与指针 一、实验目的 巩固复习前期所学C 语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。二、实验内容 1.实现病历查询功能。具体要求如下：定义一个结构体描述病人病历信息(病历号,姓名,症状)；完成功能如下：1）输入功能：输入 5 个病人的信息；2）查询功能：输入姓名，在 5 个病历中进行查找，如果找到则显示该人的信息，如果没有找到，则显示“查无此人”。假设病历类型名为 patient,要求使用指针，并使用以下两个函数（函数的实现自行完成）：void readin(patient*p);/用来输入病人信息。void search(patien

2、t*p,char*x);/根据姓名查询病人病历信息，并打印出来。提示：请注意输入函数的用法。2.设计一个函数，计算 S=1-2+3-4+5-6+/-N的值，并计算你所设计的函数的时间复杂度。三、实验源代码 此处写程序源代码，请在程序中适当注释，便于老师更快地看懂你的程序。四、实验结果 此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。五、实验心得 此处写出完成此实验后有什么收获，碰到什么因难，又是如何解决的。请不要写“这门课好难学”、“一点也不会”之类的话语，因为这对你学习并没有帮助。关键是通过实验发现自己不会的知识点，然后攻克它！数据结构实验二

3、 顺序表的运用 一、实验目的 1、掌握建立顺序表的基本方法。2、掌握顺序表的插入、删除算法的思想和实现，并能灵活运用 二、实验内容 用顺序表实现病历信息的管理与查询功能。具体要求如下：1.利用教材中定义顺序表类型存储病人病历信息(病历号,姓名，症状)；要求使用头文件。2.设计顺序表定位查找算法，完成的功能为：在线性表 L 中查找数据元素 x，如果存在则返回线性表中和 x 值相等的第 1 个数据元素的序号；如果不存在，则返回-1。函数定义为 int ListFind(SequenceList L,char*x)请在主函数中测试查找是否存在姓名为x 的病人，并根据返回的序号打印出病人信息。数据结构

4、实验三 有序单链表 一、【实验目的】1、掌握建立单链表的基本方法。2、掌握单链表的插入、删除算法的思想和实现 二、【实验内容】仿照教材中的单链表实现例子，自己设计一个有序单链表，单链表中的数据元素为整型并递增有序。有序单链表的定义：逻辑结构：有序线性表，数据元素递增有序 存储结构：链式 操作集合：初始化、插入、删除、撤销 (1)ListInitiate(L)初始化线性表，生成一个空表L。(2)ListInsert(L,x)在有序表 L 中插入数据元素 x,使得新表仍然有序。(3)ListDelete(L,x)删除有序表 L 中的数据元素 x，若删除成功则返回 1，不成功则返回 0。(4)Des

5、troy(L)撤销单链表 要求：1.有序单链表的操作集合有如下操作：初始化、插入、删除、撤销，使用头文件单链表的代码。2.编写主函数 main()验证所设计的有序单链表是否能正确插入、删除。提示：1.插入操作时，从链表的第一个数据元素结点开始，逐个比较每个结点的 data域值和 x 的值，当 data小于等于 x 时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把 x 存入，然后把新结点插入；当比较到最后一个结点仍有 data小于等于 x 时，则把新结点插入单链表尾。2.删除操作时，从链表的第一个数据元素结点开始，逐个比较每个结点的 data域值和 x 的值，当 dat

6、a小于等于 x 时，进行下一个结点的比较；否则就找到了要删除的结点，删除结点后释放结点。如果到了表尾还没有找到值为 x 的结点，则链表中没有要删除的元素。实验四 线性表综合应用 一、【实验目的】1、掌握线性表的两种存储结构的灵活运用。二、【实验内容】约瑟夫环（Josephus）问题的求解 具体描述是：设有编号为 1，2，n的 n(n0)个人围成一个圈，从第 K个人开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，如此下去，直到所有人全部出圈为止。当任意给定 n 和 m 后，设计算法求 n 个人出圈的次序。请根据以上描述，选择合适

7、的存储结构，完成 约瑟夫环的求解。请打印出出圈人的序号。提示：约瑟夫环问题主要可分解为建环、删除两个操作。可使用课上给出的头文件。三、实验源代码 实验五 栈 一、实验目的：1 掌握堆栈的存储方式和基本操作 2 掌握堆栈后进先出运算原则在解决实际问题中的应用 二、实验内容：1.利用栈结构，编写程序将十进制数转换成二进制数或八进制数。说明：十进制数值转换成二进制使用辗转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以 2，并保留其余数；重复此操作，直到该十进制数值为 0 为止。最后将所有的余数反向输出就是所对应的二进制数值。十进制数值转换成八进制算法类似。转换算法要求用一个函数完成。2

8、.假设算术表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（）或（()）等为正确格式，而(或()或()均为不正确的格式。请使用栈结构，写一算法检验某表达式中的括号是否匹配，并测试你的算法是否正确。测试表达式为：(1)(1+2)*3-1+(1+2*3)-1(2)(1+2)*3-1+(1+2)*3-1 三、实验源代码 四、实验结果 五、实验心得 实验六 队列 一、实验目的 1 掌握队列的顺序存储结构 2 掌握队列先进先出运算原则在解决实际问题中的应用 二、实验内容 仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队

9、列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。以下是队列操作函数的定义：(1)QueueInitiate(Q)初始化队列 Q (2)QueueNotEmpty(Q)队列 Q 非空否 (3)QueueAppend(Q,x)入队列，在队列 Q 的队尾插入数据元素 x。(4)QueueDelete(Q,d)出队列，把队列 Q 的队头元素删除并由参数 d 带回。提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。三、实验源代码 四、实验结果（测试数据）五、实验心得 数据结构实验七 栈和队列的应用 一、实验目的 1、掌

10、握顺序堆栈的类型定义方法。2、掌握顺序堆栈上实现的几种基本操作。3、掌握顺序队列的类型定义方法。4、掌握顺序队列上实现的几种基本操作。二、实验内容 设计算法判断一个字符序列是否是回文，要求采用队列和堆栈结构。提示：设字符数组 str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。三、实验源代码 四、实验结果 实验八 串的应用 一、【实验目的】1、掌握串的顺序存储结构 2、掌握顺序串的基本操作方法（插入、删除等）。3、掌握 Brute-Force算法 二、【实验内容】1、编

11、写函数 BFIndex(String S,int start,String T)，实现 Brute-Force 算法，其中 S 为主串，start为子串在主串中的查找位置，T 为子串。程序可参考书本例子。2、设串采用静态数组存储结构，编写函数实现串的替换 Replace(S,start,T,V),即要求在主串 S 中，从位置 start开始查找是否存在子串 T。若主串 S 中存在子串 T，则用子串 V 替换子串 T，且函数返回 1；若主串 S 中不存在子串 T，则函数返回 0。并要求设计主函数进行测试。（以下是部分代码，请同学自己完善）SString.h#include#define MaxS

12、ize 100 typedef struct char strMaxSize;int length;String;int Insert(String*S,int pos,String T)/*在串 S 的 pos位置插入子串 T*/int i;if(pos length+T.length MaxSize)printf(数组空间不足无法插入！);return 0;else for(i=S-length-1;i=pos;i-)S-stri+T.length=S-stri;/*为插入做准备*/for(i=0;i strpos+i=T.stri;/*插入*/S-length+=T.length;/*产

13、生新的元素个数*/return 1;int Delete(String*S,int pos,int len)int i;if(S-length=0)printf(数组中未存放字符无元素可删!n);return 0;else if(pos 0|len S-length)printf(参数 pos和 len出错);return 0;else for(i=pos+len;i length-1;i+)S-stri-len=S-stri;/*依次前移*/S-length-=len;/*产生新的长度值*/return 1;主程序#include#include#define Maxlength 100#i

14、ncludeSString.h int BFIndex(String*S,int start,String T)自己完成 int Replace(String*s,int start,String t,String v)自己完成 void main(void)String myString1,myString2,myString3;int i,start=0;printf(请输入主串 myString1n);scanf(%s,myString1.str);printf(请输入子串 myString2n);scanf(%s,myString2.str);printf(请输入子串 myString

15、3n);scanf(%s,myString3.str);myString1.length=strlen(myString1.str);myString2.length=strlen(myString2.str);myString3.length=strlen(myString3.str);if(Replace(&myString1,start,myString2,myString3)=0)printf(不成功n);else for(i=0;imyString1.length;i+)printf(%c,myString1.stri);三、【实验源代码】四、【实验结果】五、【实验心得】实验九 数组

16、的应用 一、【实验目的】1、掌握数组的抽象数据类型 2、掌握动态数组的设计方法 3、理解动、静态数组的对比 4、掌握特殊矩阵的压缩存储及运算 5、掌握稀疏矩阵的压缩存储 二、【实验内容】1、设矩阵 A、矩阵 B 和矩阵 C 为 n 阶对称矩阵，矩阵元素为整数类型，要求：（1）若 A、B 和 C 采用压缩存储方式，请编写函数实现矩阵加法运算 C=A+B的函数（2）编写压缩矩阵的元素输出函数，按矩阵格式输出。（3）以下面的数据为测试例子，编写一个主程序调用以上两个函数进行测试，输出矩阵A,B,C。21435 3221B 三、【实验源代码】四、【实验结果】五、【实验心得】数据结构实验十 递归算法的实

17、现 一、实验目的 1、掌握递归原理 2、掌握一些常用问题的递归算法设计 二、实验内容 1.有这样一个故事：猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，见只剩下一个桃子了。那么你知道猴子第一天共摘了多少个桃子吗？1)请用递归和非递归算法分别实现猴子吃桃问题的求解。2)求解过程请用函数实现。要求能够计算：如果在第 N 天只剩下一个桃子了，那么第一天共摘了多少个桃子。2.编写折半查找算法的递归实现和非递归实现。提示：将要查找的元素 key与查找区间正中元素相比，若

18、 key小，则查找区间缩小至前半部份查找，若 key大，则查找区间缩小至后半部份查找；再取其中值比较，每次缩小 1/2的范围，直到查找成功或失败为止。如递归实现，考虑函数的参数应有哪些。在用循环结构实现时，函数的参数有什么变化？三、实验源代码 四、实验结果 数据结构实验十一 二叉树的建立及遍历应用 一、【实验目的】1、掌握二叉树的建立方法 2、掌握二叉树遍历的基本方法（前序、中序、后序）3、掌握递归二叉树遍历算法的应用 二、【实验内容】1.构造一棵二叉树,树的形态如下图所示，打印出前序遍历、中序遍历、后序遍 历的遍历序列。A B F C G D E 2.选择一种遍历方式计算该树中叶子结点的个数

19、，并打印出叶子结点。三、【实验源代码】四、【实验结果】五、【实验心得】实验十二 二叉树的层序遍历 一、【实验目的】1、掌握二叉树遍历的基本方法（前序、中序、后序、层序）二、【实验内容】1、二叉树如下，请完成：A B F C G D E 要求：（1）编写一个按层次（同一层自左至右）输出二叉树中所有的结点的函数。（2）编写测试主函数。实验十三 哈夫曼编码的程序设计 一、【实验目的】1、掌握哈夫曼树的建立过程 2、熟悉哈夫曼编码的实现 二、【实验内容】设有字符集A,B,C,D,各字符在电文中出现的次数集为1,3,4,7;要求 编程实现哈夫曼树的构造,并在此基础上编程实现哈夫曼编码.三、实验源代码 四

20、、实验结果（树结构及编码表）数据结构实验十四 图的操作实现 一、实验目的 1、理解图的存储结构与基本操作；2、掌握图的创建过程 二、实验内容 根据下图，采用邻接矩阵的存储结构保存此图，并打印出邻接矩阵。21435 图的创建代码参考教材 P217 页例 91.提示：首先根据给出的图结构得出该图的顶点集和边集，调用相应的函数生成图的邻接矩阵，并打印出邻接矩阵。三、【实验源代码】四、【实验结果】五、【实验心得】实验十五 图的遍历的实现 一、【实验目的】1、掌握图的遍历过程；2、理解图的存储结构与基本操作；3、熟悉图的广度优先遍历的实现 二、【实验内容】（1）采用邻接矩阵的存储结构保存教材 P202的

21、图 8.18（a）无向图；（2）编程实现该图的深度与广度优先遍历。三、实验源代码 四、实验结果（打印遍历的顺序）实验十六 排序算法的实现 一、【实验目的】(1)理解各类排序算法的实现过程；（2）理解不同排序算法的时间复杂度及适用环境；（3）了解算法性能测试的基本方法。二、【实验内容】（1）以下是一个通过随机数来测试排序算法运行时间的程序，中间留出了加入排序算法的部分。其中可以通过修改 RANDNUM 的值来更改测试的数据量：#include stdio.h#include#include#include#define RANDNUM 20000/随机数的个数 void main（）int iR

22、andNumRANDNUM;/存放随机数 time_t first，second;/记录开始和结束时间（以毫秒为单位）int i;for（i=0;iRANDNUM;i+）/产生 1 万个随机数 iRandNumi=rand（）%RANDNUM;first=clock（）;/开始时间 /此处加入排序程序 second=clock（）;/结束时间 （2）从所学的排序算法中任选四种排序算法进行测试，记录运行时间；（3）把需排序的数改为 20000，进行同样测试，并比较测试结果。提示：在程序的实现过程中要用到以下函数，请大家在实验之前自学这几个函数的用法：1）随机函数 rand（）2)时间函数 clock（）三、实验源代码 四、实验结果 记录测试结果。实验十七 动态查找算法的实现 一、【实验目的】1、掌握二叉排序树的基本概念 2、掌握二叉排序树的基本算法（查找算法、插入算法、删除算法）2、理解并掌握二叉排序数查找的平均查找长度。二、【实验内容】1、已知一个个数为 12 的数据元素序列为Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar,要求：（1）按各数据元素的顺序（字母大小顺序）构造一棵二叉排序数，并中序打印排序结果。（2）查找数据”Sept”是否存在。三、【实验源代码】四、【实验结果】五、【实验心得】