下载文档原格式
数据结构实验指导书一、实验目的数据结构是计算机科学中的重要基础课程，通过实验，旨在帮助学生更好地理解和掌握数据结构的基本概念、原理和算法，提高学生的编程能力和问题解决能力。
具体而言，实验的目的包括：1、加深对常见数据结构（如数组、链表、栈、队列、树、图等）的理解，掌握其特点和操作方法。
2、培养学生运用数据结构解决实际问题的能力，提高算法设计和程序实现的能力。
3、增强学生的逻辑思维能力和调试程序的能力，培养学生的创新意识和团队合作精神。
二、实验环境1、操作系统：Windows 或 Linux 操作系统。
2、编程语言：C、C+＋、Java 等编程语言中的一种。
3、开发工具：如 Visual Studio、Eclipse、Code:：Blocks 等集成开发环境（IDE）。
三、实验要求1、实验前，学生应认真预习实验内容，熟悉相关的数据结构和算法，编写好实验程序的代码框架。
2、实验过程中，学生应独立思考，认真调试程序，及时记录实验过程中出现的问题及解决方法。
3、实验完成后，学生应撰写实验报告，包括实验目的、实验内容、实验步骤、实验结果、问题分析与解决等。
四、实验内容（一）线性表1、顺序表的实现与操作实现顺序表的创建、插入、删除、查找等基本操作。
分析顺序表在不同操作下的时间复杂度。
2、链表的实现与操作实现单链表、双向链表的创建、插入、删除、查找等基本操作。
比较单链表和双向链表在操作上的优缺点。
（二）栈和队列1、栈的实现与应用实现顺序栈和链式栈。
利用栈解决表达式求值、括号匹配等问题。
2、队列的实现与应用实现顺序队列和链式队列。
利用队列解决排队问题、广度优先搜索等问题。
（三）树1、二叉树的实现与遍历实现二叉树的创建、插入、删除操作。
实现二叉树的前序、中序、后序遍历算法，并分析其时间复杂度。
2、二叉搜索树的实现与操作实现二叉搜索树的创建、插入、删除、查找操作。
分析二叉搜索树的性能。
（四）图1、图的存储结构实现邻接矩阵和邻接表两种图的存储结构。
〈数据结构〉上机实验指导数据结构是计算机科学中的一门重要课程，它研究的是数据的组织、存储和管理方式，以及对数据进行操作和处理的算法。
上机实验是数据结构课程的重要组成部分，通过实践操作，能够更好地理解和掌握数据结构的基本概念、算法和应用。
在进行〈数据结构〉上机实验之前，首先需要准备实验环境。
通常情况下，我们会使用一种编程语言来实现数据结构的相关操作，比如C++、Java等。
根据自己的实际情况和实验要求，选择一种合适的编程语言，并确保在实验环境中已经正确安装了相应的编译器或解释器。
接下来，我们可以开始进行具体的上机实验了。
下面以链表为例，介绍一下〈数据结构〉上机实验的指导步骤和要求：1. 实验目的：掌握链表的基本概念、操作和应用，理解链表与数组的区别和联系。
2. 实验原理：链表是一种动态数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。
链表的特点是插入和删除操作的时间复杂度为O(1)，但是查找操作的时间复杂度为O(n)。
3. 实验步骤：3.1 创建链表：首先，我们需要定义一个链表的结构体，包含数据和指针两个成员变量。
然后，通过动态内存分配来创建链表的节点，并将节点之间通过指针连接起来，形成一个完整的链表。
3.2 插入节点：可以在链表的任意位置插入一个新的节点。
插入节点的操作包括：创建一个新的节点，将新节点的指针指向插入位置的下一个节点，将插入位置的前一个节点的指针指向新节点。
3.3 删除节点：可以删除链表中的任意一个节点。
删除节点的操作包括：将要删除的节点的前一个节点的指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存空间。
3.4 遍历链表：可以通过遍历链表来访问链表中的每一个节点，并对节点进行相应的操作。
遍历链表的操作包括：从链表的头节点开始，依次访问每个节点，直到链表的尾节点。
3.5 查找节点：可以根据节点的值来查找链表中的某一个节点。
查找节点的操作包括：从链表的头节点开始，依次比较每个节点的值，直到找到目标节点或者链表结束。
《数据结构》实验指导书第一部分前言一、实验的目的《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。
本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。
数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。
实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。
通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。
二、实验前的准备工作1．每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C++6.0以上版本。
2．实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。
三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。
（二）新建一个项目文件1．双击Visual C++ 6.0快捷图标，进入Visual C++ 6.0集成开发环境；或者点击“开始”→“程序”→“Microsoft Visual Studio 6.0”→“Microsoft Visual C++ 6.0”进入Visual C++ 6.0集成开发环境。
2．单击“File”菜单，选择“New”命令3．创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中；4．输入源程序；5．单击“保存”按钮保存源程序。
《数据结构》实验指导书软件学院2011年9月概述实习目的和要求《数据结构》在计算机科学中是一门实践性较强的专业基础课, 上机实习是对学生的一种全面综合训练, 是与课堂听讲、自习和练习相辅相成的必不可少的一个教学环节。
实习着眼于原理与应用的结合, 使学生学会把学到的知识用于解决实际问题, 起到深化理解和灵活掌握教学内容的目的。
同时, 通过本课程的上机实习, 使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
实习包括的步骤1. 简要描述题目要求, 对问题的描述应避开算法及所涉及的数据类型, 只是对所需完成的任务做出明确的陈述, 例如输入数据的类型、值的范围以及输入的形式, 输出数据的类型、值的范围以及输出的形式。
2. 选定数据结构, 写出算法, 根据自顶向下发展算法的方法, 首先描述算法的基本思想, 然后进行算法细化, 再对所设计的算法的时间复杂性和空间复杂性进行简单分析。
3. 准备好上机所需的程序, 选定一种程序设计语言（如C 语言）, 手工编好上机程序, 并进行反复检查, 使程序中的逻辑错误和语法错误减少到最低程度。
对程序中有疑问的地方, 应做出标记, 以便在上机时给予注意。
4．上机输入和调试程序, 在调试程序过程中除了系统的问题以外, 一般应自己独立解决。
在程序调试通过后, 打印输出程序清单和运行结果。
5．上机结束后, 总结和整理实习报告。
实习报告的内容1．简述题目要解决的问题是什么, 并说明输入和输出数据的形式。
2．简述存储结构和算法的基本思想。
3．列出调试通过的源程序。
4．列出上面程序对应的运行结果。
分析程序的优缺点、时空性能以及改进思想, 写出心得体会。
实验一线性表一. 目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现, 提高分析和解决问题的能力。
要求仔细阅读并理解下列例题, 上机通过, 并观察其结果, 然后独立完成后面的实习题。
《数据结构》实验指导书实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立线性表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。
二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立单链表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。
三、用C语言编程实现两个按递增顺序排列线性表的合并1、编程实现合并按递增顺序排列的两个顺序表算法；2、编程实现合并按递增顺序排列的两个单链表算法。
【思考问题】结合实验过程，回答下列问题：1、何时采用顺序表处理线性结构的问题为最佳选择；2、何时采用链表处理线性结构的问题为最佳选择。
【实验报告要求】1、根据对线性表的理解，如何创建顺序表和单链表；2、实现顺序表插入和删除操作的程序设计思路；3、实现链表插入和删除操作的程序设计思路；4、实现两表合并操作的程序设计思路；5、调试程序过程中遇到的问题及解决方案；6、本次实验的结论与体会。
数据结构实验指导书实验一线性表[实验目的]1．了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。
2．了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。
[实验内容]1．顺序表的实践。
1)建立4个元素的顺序表list[]={2，3，4，5}，实现顺序表建立的基本操作。
2)在list[]={2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。
3)在list[]={2，3，4，9，5}中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。
2．单链表的实践。
1)建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。
2)在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。
3)在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。
[实验要点及说明]线性表（linear list）是n（n≥0）个数据元素a1，a2，…a n组成的有限序列。
其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。
通常将非空的线性表记为（a1，a2，…,a n），其中的数据元素a i（1≤i≤n）是一个抽象的符号，a i是第i个数据元素,称i为数据元素a i在线性表中的位置。
其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。
顺序表也称为线性表的顺序存储结构。
其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。
一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。
可定义顺序表如下：#define maxnumelemtype list[maxnum];int num=-1;线性表的链式存贮结构，也称为链表。
数学与计算机科学学院计算机科学与技术专业
《数据结构》课程实验
指导手册
目录
实验1：顺序表的定义及其相关操作算法的实现 (1)
实验2：链表的定义及其相关操作算法的实现 (2)
实验3：栈和队列的定义及其基本操作算法的实现 (4)
实验4：串模式匹配算法的设计与实现 (5)
实验5：二叉树的创建、遍历及其它基本操作的实现 (6)
实验6：哈夫曼树及哈夫曼编码的算法实现 (7)
实验7：查找算法的实现（1） (8)
实验8：查找算法的实现（2） (9)
实验9：几个主要排序算法的实现与比较 (10)
实验1：顺序表的定义及其相关操作算法的实现
实验2：链表的定义及其相关操作算法的实现
实验3：栈和队列的定义及其基本操作算法的实现
实验4：串模式匹配算法的设计与实现
实验5：二叉树的创建、遍历及其它基本操作的实现
实验6：哈夫曼树及哈夫曼编码的算法实现
实验7：查找算法的实现（1）
实验8：查找算法的实现（2）
实验9：几个主要排序算法的实现与比较。
数据结构上机实验指导书计算机系第一部分数据结构课程实验概述一. 实验目的《数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。
在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。
二. 实验要求2.1实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。
因此必须严格执行良好的实验步骤规范（包括上机操作规范）。
本课程实验的基本步骤是：2.1.1问题分析充分地分析和理解问题本身，明确问题要求做什么。
对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。
例如;输入、输出数据的类型、值的范围以及形式等。
同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。
2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型, 序模块定义主程和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。
在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。
编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。
对程序中的疑问应作出记号，以便上机时注意解决。
每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。
2.1.3上机前程序静态检查上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。
静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。
《数据结构》实验指导实验二：单链表的存储及操作一、实验目的1、掌握单链表抽象数据类型的定义。
2、掌握单链表的存储实现。
3、掌握单链表的操作算法实现。
4、了解单链表的应用。
二、实验学时2学时三、实验类型验证性实验四、实验需求1、硬件每位学生配备计算机一台；2、软件Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。
五、实验理论与预备知识1、数据结构的基本概念2、顺序存储结构的特点3、线性表的特点和基本运算4、线性表顺序存储结构下的操作算法六、实验任务1、单链表抽象数据类型的代码实现2、编写应用程序，用相关数据验证运算算法七、实验内容及步骤1、任务一：有一个单链表对象L,设计一个算法查找最后一个值为x 的结点的逻辑序号。
并分析算法的时间和空间复杂度。
实验步骤： (1)启动Visual Studio 2010,创立窗体应用程序。
(2) 增加单链表类，代码参考如下:public class LinkList(public string data; public LinkList next;}； class LinkListClasspublic LinkList head = new LinkList();〃单链表头结点//-单链表的基本运算算法public void CrcatcListF(string[] split) 〃头插法建立单链表 {LinkList s;int i;=null;〃将头结点的next 字段置为null for (i = 0; i < h; i++)〃循环建立数据结点{s = new LinkList();s.data = split[i];〃创立数据结点ss.next =; 〃将s 结点插入到开始结点之HU,头结点之后public void CrcatcListR(string[] split) 〃尾插法建立单链表{LinkList s, r;int i;r = head;//r 始终指向尾结点，开始时指向头结点for (i = 0; i < h; i++) 〃循环建立数据结点{s = new LinkList();s.data = splitfi];〃创立数据结点s r.next = s;〃将s 结点插入r 结点之后r.next = null;〃将尾结点的next 字段置为null〃定义单链表结点类〃存放数据元素//指向下一个结点的字段string str = LinkList p; P =；//p 指向开始结点if (p == null) str ="空串"； while (p != null)//p 不为null,输出p 结点的data 字段str += p.data + " p =p.next; 〃p 移向下一个结点 return sir;1public int ListLength() 〃求单链表数据结点个数int n = 0;LinkList p; p = head; //p 指向头结点,n 置为0（即头结点的序号为0）while (p.next != null) (n++;p = p.next; }return (n);〃循环结束,p 指向尾结点,其序号n 为结点个数public bool GetElem(int i, ref string e) 〃求单链表中某个数据元素值 {intj = O;LinkList p;p = head; while (j < i && p != null) //p 指向头结点,j 置为0（即头结点的序号为0） 〃找第i 个结点pj++； p = p.next;}if (p == null) return false; 〃不存在第i 个数据结点，返回falseelse//存在第i 个数据结点，返回true c = p.data; return true;public int LocateElcm(string c)int i= 1;LinkList p;p = ；〃p 指向开始结点,i 置为1(即开始结点的序号为1)while (p != null && p.data != e) 〃查找data 值为e 的结点，其序号为i {p = p.next; i++； }if (p == null)//不存在元素值为e 的结点，返回0return (0);public stringDispList()〃将单链表所有结点值构成一个字符串返同//按元素值查找else〃存在元素值为e的结点，返回其逻辑序号ireturn (i);} _public bool Listlnsert(int i, string e) //插入数据元素{ int j = 0;LinkList s, p;if(i< 1)//i<l 时i 错误，返回falsereturn false;p = head;//p指向头结点,j置为0(即头结点的序号为0) while (j < i - 1 && p != null)〃查找第i-1 个结点{j++；p = p.next;}if(p ==null)〃未找到第i-l个结点，返回falsereturn false;else〃找到第i-l个结点p,插入新结点并返回true(s = new LinkList();s.data = e;〃创立新结点s,其data字段置为es.ncxt = p.next;〃将s结点插入到p结点之后p.next = s;return true;}}public bool ListDele(e(inl i, ref string e) 〃删除数据元素{ int j = 0;LinkList q, p;if (i < 1)〃ivl 时i 错误，返回falsereturn false;p = head;//p指向头结点j置为0(即头结点的序号为0) while (j < i - 1 && p != null)//查找第i-l 个结点j++；public int Findlast(LinkListClass L. stringx)LinkList p = L.; inti = O,j = i; while (p != null)i++；if (p.data == x) j = i ；p = p.next; return j;}（3）设计窗体，界面参考如下:p =p.ncxt;if (p == null) return false; else 〃未找到第i-1个结点，返回fa lse〃找到第i-1个结点p q = p.next; if (q == null) return false; c = q.data; p.next= q.next;q = null; return true; 〃q 指向第i 个结点〃假设不存在第i 个结点，返回false〃从单链表中删除q 结点〃释放q 结点〃返回（rue 表示成功删除第i 个结点（4） 编写窗体中按钮等控件的代码，调用单链表类，参考如下:LinkListClass L = new LinkListClassO;private〃单链表Lvoid Forml_Load(object sender, Event Args e)(=”2,3,1,5,6,2,3,8”；}private void buttonl_Click(object sender, Event Args e)(string str = .Trini();if (str ===”操作提示:必须输入元素”；else{string[] split = (new Char[] {'});L.CreateListR(split);ed = false;ed = true;=”操作提示:成功创立单链表”；}}private void button2_Click(object sender, Event Args e)(int i;string elem;elem =;i = L.Findlast(L, elem);if(i == 0)=”操作提示:在单链表中没有找到该元素”；else=i.ToStringO;=”操作提示:在单链表中找到该元素”;（5）选择【调试】—►【开始执行（不调试）】命令或按【CtH+F5】组合键运行程序，并观察运行情况。
引言概述正文内容
1.实验环境配置
1.1硬件要求
计算机硬件配置要求
操作系统要求
附加硬件设备要求（如虚拟机等）
1.2软件要求
编程语言要求（如C/C++、Java等）开发环境配置（如IDE、编译器等）1.3实验库和工具
实验需要使用的库文件和工具
如何获取和配置实验库和工具
2.实验内容介绍
2.1实验目标和背景
数据结构实验的作用和意义
实验背景和相关应用领域介绍
2.2实验概述
实验内容的大致流程和步骤
实验中可能遇到的问题和挑战
2.3实验要求
对学生实验流程和实验结果的要求
实验过程中需要注意的事项和技巧
3.实验步骤
3.1实验准备
配置实验环境
获取实验所需数据和文件
3.2实验具体步骤
根据实验要求将数据结构知识应用到具体问题中根据实验要求实现相应的算法和数据结构
3.3实验示例代码
提供示例代码以供学生参考和学习
解析示例代码中的关键步骤和实现细节
4.实验答案
4.1实验题目
实验题目及相关说明
确定实验的具体要求和目标
4.2实验答案解析
对实验答案的具体实现进行解析
对实验中可能遇到的问题和错误进行分析和解决4.3实验答案示例
提供实验答案的示例代码
解析实验答案中的关键实现步骤和说明
5.实验总结
5.1实验成果评估
对学生实验成果进行评估
分析实验结果的优点和不足
5.2实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。
数据结构实验一c语言结构体与指针一、实验目的巩固复习前期所学c语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。
二、实验内容1•实现病历查询功能。
具体要求如下：定义一个结构体描述病人病历信息（病历号，姓名，症状）；完成功能如下：1）输入功能：输入5个病人的信息；2）查询功能：输入姓名，在5个病历中进行查找，如果找到则显示该人的信息，如果没有找到，则显示“查无此人”。
假设病历类型名为patient,要求使用指针，并使用以下两个函数（函数的实现自行完成）：void readin （patient *p） ;//用来输入病人信息。
void search （patient *p, char *x） ;//根据姓名查询病人病历信息，并打印出来。
提示：请注意输入函数的用法。
2.设计一个函数，计算S二1-2+3-4+5-6+……+/-N的值，并计算你所设计的函数的时间复杂度。
三、实验源代码此处药程序源代码，请在程序中适肖注释，便于老师更快地看懂你的程序。
四、实验结果此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。
五、实验心得此处写出完成此实验后有什么收获，碰到什么因难，乂是如何解决的。
请不要写“这门课好难学”、“一点也不会”之类的话语，因为这对你学习并没有帮助。
关键是通过实验发现自己不会的知识点，然后攻克它！少年易学老难成•-寸光阴不数据结构实验二顺序表的运用一、实验目的1、掌握建立顺序表的基本方法。
2、掌握顺序表的插入、删除算法的思想和实现，并能灵活运用二、实验内容用顺序表实现病历信息的管理与查询功能。
具体要求如下：1.利用教材中定义顺序表类型存储病人病历信息(病历号,姓名，症状)；要求使用头文件。
2.设计顺序表定位查找算法，完成的功能为：在线性表L中查找数据元素x,如果存在则返回线性表中和x值相等的笫1个数据元素的序号；如果不存在，则返回-1。
函数定义为int ListFind(SequenceList L, char *x)请在主函数中测试查找是否存在姓名为x的病人，并根据返回的序号打印出病人信息。
数据结构实验三有序单链表一、【实验目的】1、掌握建立单链表的基本方法。
2、掌握单链表的插入、删除算法的思想和实现二、【实验内容】仿照教材中的单链表实现例子，自己设计一个有序单链表，单链表中的数据元素为整型并递增有序。
有序单链表的定义：逻辑结构：有序线性表，数据元素递增有序存储结构：链式操作集合：初始化、插入、删除、撤销(l)Listlnitiate(L)初始化线性表,生成一个空表L。
(2)List Insert (L, x)在有序表L中插入数据元素x,使得新表仍然有序。
(3)ListDelete(L, x)删除有序表L中的数据元素x,若删除成功则返回1,不成功则返回Oo(4)Destroy (L)撤销单链表要求：1•有序单链表的操作集合有如下操作：初始化、插入、删除、撤销，使用头文件单链表的代码。
2.编写主函数main()验证所设计的有序单链表是否能正确插入、删除。
提示：1.插入操作时，从链表的第一个数据元素结点开始，逐个比较每个结点的data 域值和x 的值，当data小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。
2.删除操作时，从链表的第一个数据元素结点开始，逐个比较每个结点的data 域值和x 的值，当data小于等于x时，进行下一个结点的比较；否则就找到了要删除的结点，删除结点后释放结点。
如果到了表尾还没有找到值为x的结点，则链表中没有要删除的元素。
实验四线性表综合应用一、【实验目的】1、掌握线性表的两种存储结构的灵活运用。
二、【实验内容】约瑟夫环(Josephus)问题的求解具体描述是：设有编号为1, 2,……，n的n(n>0)个人围成一个圈，从第K个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数, 报到m时停止报数，报m的岀圈，……，如此下去，直到所有人全部出圈为止。
当任意给定n和m后，设计算法求n个人岀圈的次序。
请根据以上描述，选择合适的存储结构，完成约瑟夫环的求解。
请打印出出圈人的序号。
提示：约瑟夫环问题主要可分解为建环、删除两个操作。
可使用课上给出的头文 件。
三、实验源代码实验五栈一、 实验目的：1. 掌握堆栈的存储方式和基本操作2. 掌握堆栈后进先出运算原则在解决实际问题中的应用二、 实验内容：1. 利用栈结构，编写程序将十进制数转换成二进制数或八进制数。
说明：十进制数值转换成二进制使用辗转相除法将一个十进制数值转换成二进制 数值。
即用该十进制数值除以2,并保留其余数；重复此操作，直到该十进制数 值为0为止。
最后将所有的余数反向输出就是所对应的二进制数值。
十进制数值 转换成八进制算法类似。
转换算法要求用一个函数完成。
2. 假设算术表达式中允许包含 两种括号：圆括号和方括号， 其嵌套的顺序随意，即([][]) 或[(□())]等为正确格式， 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较，若相匹配，则“左括弧出栈” 否则表明不匹配 3) 表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余(2) [(1+2)*3-1]+[(1+2)*3-1]三、 实验源代码算法的设计思想: 扫描表达式， 1) 凡出现左括弧，则进栈； 2) 凡出现右括弧，首先检查栈是否空。
而[(]或()))或[())均为不正 确的格式。
请使用栈结构，写 一算法检验某表达式中的括号 是否匹配，并测试你的算法是 否正确。
测试表达式为：(1)[(1+2)-3-1]+[((1+2]*3)-1]少年易学老难成,•寸光阴不可轻-百度文廉四、实验结果五、实验心得实验六队列一、实验目的1.掌握队列的顺序存储结构2.掌握队列先进先出运算原则在解决实际问题中的应用二、实验内容仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。
其中操作包括：初始化、入队列、出队列、判断队列是否非空。
编写主函数，验证所设讣的顺序循环队列的正确性。
以下是队列操作函数的定义：(1)Queueinitiate (Q)(2)QueueNotEmpty(Q )(3)QueueAppend(Q,x 初始化队列Q队列Q非空否入队列，在队列Q的队尾插入数据元素x。
出队列，把队列Q的队头元素删除并山参数d带回。
提示：队尾的位置可山队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。
三、实验源代码四、实验结果（测试数据）年五、实验心得数据结构实验七栈和队列的应用一、实验目的1、掌握顺序堆栈的类型定义方法。
2、掌握顺序堆栈上实现的儿种基本操作。
3、掌握顺序队列的类型定义方法。
4、掌握顺序队列上实现的儿种基本操作。
二、实验内容设讣算法判断一个字符序列是否是回文，要求采用队列和堆栈结构。
提示：设字符数组str中存放了要判断的字符串。
把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等,若全部相等则该字符序列是回文,否则就不是回文。
三、实验源代码四、实验结果实验八串的应用一、【实验目的】1、掌握串的顺序存储结构2、掌握顺序串的基本操作方法(插入、删除等)。
3、掌握Brute-Force 算法二、【实验内容】1、编写函数BFIndex(String S, int start, String T)> 实现Brute-Force 算法，其中S 为主串,start为子串在主串中的査找位置，T为子串。
程序可参考书本例子。
2、设串采用静态数组存储结构，编写函数实现串的替换Replace (S, start, T, V), RP要求在主串S中，从位置start开始査找是否存在子串T。
若主串S中存在子串T,则用子串V替换子串T,且函数返回1：若主串S中不存在子串T,则函数返回0。
并要求设讣主函数进行测试。
(以下是部分代码，请同学自己完善)SString・ h^include <stdio. h>^define MaxSize 100typedef struct{char str[MaxSize];int length;} String;int Insert (String *S, int pos, String T)/*在串S的pos位宜插入子串T*/{int i;if (pos < 0){printf (“参数pos 出错！”)；return 0;}else if(S->length + T・1ength > MaxSize)printf (-数组空间不足无法插入！0;少年易学老难成. 吋光阴不可轻•百度文阵} return 0;} elsefor (i = S->length~l; i >= pos; i―)S->str[i+T・1ength] = S->str[i];ford = 0; i < T・ 1 ength; i++)S->str[pos+iZ = T・str Li]；S->length += T・length;return 1;}}int Delete(String *S, int pos, int len)int i;if(S->length <= 0){printf(-数组中未存放字符无元素可删！ \『);return 0;}else if(pos < 0 len < 0 pos+len > S->length){printf (/?参数pos 和len 岀错");return 0; /*为插入做准备*//*插入*//*产生新的元素个数*/少年易学老难成•-寸光19 else{for(i = pos+len; i <= S->length~l;S->str[i-len] = S->str[i];S->length -= len;return 1;}}主程序#inelude <stdio.h>#include<stri ng.h>#define Maxlength 100#include,,SString.h Nint BFIndex(String *S, int start, String T){自己完成}int Replace(String *s,int start,String t,String v){自己完成}void main(void){String myStringl, myString2 , myString3;int i,start=O;printf("请输入主串myStringl\n")；scanf(”％s蔦myStringl.str );printf("in输入子串myString2\n u)； scanf(,,%s,,/myString2.str);/*依次前移*/ /*产生新的长度值*/printfC'in输入子串myString3\n");scanf「％s 蔦myString3.str);myStringl length二strlen(myStringl・stij;myString2.length=strlen(myString2.str);myString3 length 二strlen(myStri ng3.str);if(Replace( &myStri ng 1, sta rt, mySt r i ng2# my St r i ng3)==0) printf("不成功\n");elsefor(i=0;i<myStringl.length ;i++) printf ("%c 舄myStringl. str[i]);}三、【实验源代码】四、【实验结果】五、【实验心得】实验九数组的应用一、【实验目的】1、掌握数组的抽象数据类型少年易学老难成.•寸光阴不可轻•百度文库2、掌握动态数组的设il•方法3、理解动、静态数组的对比4、掌握特殊矩阵的压缩存储及运算5、掌握稀疏矩阵的压缩存储二、【实验内容】1、设矩阵A、矩阵B和矩阵C为n阶对称矩阵，矩阵元素为整数类型，要求：（1）若A、B和C采用圧缩存储方式，请编写函数实现矩阵加法运算C二A+B的函数（2）编写压缩矩阵的元素输出函数，按矩阵格式输岀。
