计算机数据结构实验指导

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

2、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)Destroy(L) 撤销单链表要求：1.有

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

6、点后释放结点。如果到了表尾还没有找到值为x的结点，则链表中没有要删除的元素。实验四 线性表综合应用一、【实验目的】1、掌握线性表的两种存储结构的灵活运用。二、【实验内容】约瑟夫环（Josephus）问题的求解具体描述是：设有编号为1，2，n的n(n>0)个人围成一个圈，从第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掌握队列先进先出运算原则在解决实际问题中的应用二、实验内容仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。以下是队列操作函数的定义：(1)QueueInitiate(Q) 初始化队

9、列Q (2)QueueNotEmpty(Q) 队列Q非空否 (3)QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。 (4)QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。三、实验源代码 四、实验结果（测试数据） 五、实验心得数据结构实验七 栈和队列的应用一、实验目的1、掌握顺序堆栈的类型定义方法。2、掌握顺序堆栈上实现的几种基本操作。3、掌握顺序队列的类型定义方法。4、掌握顺序队列上实现的几种基本操作。二、实验内容设计算法判

10、断一个字符序列是否是回文，要求采用队列和堆栈结构。提示：设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。三、实验源代码四、实验结果实验八 串的应用一、【实验目的】1、掌握串的顺序存储结构2、掌握顺序串的基本操作方法（插入、删除等）。3、掌握Brute-Force算法二、【实验内容】1、编写函数BFIndex(String S, int start, String T)，实现Brute-Force算法，其中S为主串，start为子串在主串中的查找位置，T为子

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

12、ing T)/*在串S的pos位置插入子串T*/int i;if(pos < 0)printf("参数pos出错！");return 0;else if(S->length + T.length > MaxSize)printf("数组空间不足无法插入！");return 0;elsefor(i = S->length-1; i >= pos; i-)S->stri+T.length = S->stri;/*为插入做准备*/for(i = 0; i < T.length; i+)S->strpos+i

13、 = T.stri;/*插入*/S->length += T.length;/*产生新的元素个数*/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 < 0 | pos+len > S->length)printf("参数pos和len出错");return 0;elsefor(i = pos+len; i

14、 <= S->length-1; i+)S->stri-len = S->stri;/*依次前移*/S->length -= len;/*产生新的长度值*/return 1;主程序#include <stdio.h>#include<string.h>#define Maxlength 100#include"SString.h"int BFIndex(String *S, int start, String T) 自己完成 int Replace(String *s,int start,String t,String

15、v)自己完成void main(void)StringmyString1 , myString2 ,myString3;int i,start=0;printf("请输入主串myString1n");scanf("%s",myString1.str );printf("请输入子串myString2n");scanf("%s",myString2.str);printf("请输入子串myString3n");scanf("%s",myString3.str);myString1

16、.length=strlen(myString1.str);myString2.length=strlen(myString2.str);myString3.length=strlen(myString3.str);if(Replace(&myString1,start,myString2,myString3)=0)printf("不成功n");elsefor(i=0;i<myString1.length ;i+)printf("%c",myString1.stri);三、【实验源代码】四、【实验结果】5、 【实验心得】实验九 数组的应用一

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

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

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

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

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

22、的广度优先遍历的实现二、【实验内容】（1）       采用邻接矩阵的存储结构保存教材P202的图8.18（a）无向图；（2）       编程实现该图的深度与广度优先遍历。三、实验源代码  四、实验结果（打印遍历的顺序）实验十六 排序算法的实现一、【实验目的】 (1) 理解各类排序算法的实现过程；（2）理解不同排序算法的时间复杂度及适用环境；（3）了解算法性能测试的基本方法。二、【实验内容】  （1）以下是一个通过随机数来测试排序算法

23、运行时间的程序，中间留出了加入排序算法的部分。其中可以通过修改RANDNUM的值来更改测试的数据量： #include "stdio.h"#include <stdlib.h>#include <time.h>#include<ctime>#define RANDNUM 20000 /随机数的个数 void main（）        int iRandNumRANDNUM;/存放随机数       time_t first，second; /记录开始和结束时间（以毫秒为单位）       int i;    for（i=0;i<RANDNUM;i+