下载文档原格式
实验一线性表操作一、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。
2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。
3熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
4熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。
二、实验要求1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容基本题:1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。
加强、提高题：2、编写一个求解Josephus问题的函数。
用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。
然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。
最后分析所完成算法的时间复杂度。
定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。
（可以选做其中之一）加强题：（1）采用数组作为求解过程中使用的数据结构。
提高题：（2）采用循环链表作为求解过程中使用的数据结构。
运行时允许指定任意n、s、m数值，直至输入n = 0退出程序。
实验二栈、队列、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。
二、实验要求1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容基本题（必做）：1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。
2、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。
加强题：3设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。
数据结构与算法设计实验指导书西华大学计算机与软件工程学院计算机系2019.2前言《数据结构与算法设计》是计算机类相关专业的一门核心基础课程，也是计算机程序设计的重要理论技术基础，更是考研专业课之一。
主要介绍线性结构、树结构、图结构、集合四种基本逻辑结构及存储实现，在此基础上介绍一些典型的算法设计技术和时间效率分析。
课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。
通过学习，要求学生掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。
学习该课程，实验是一个关键的环节；在理解算法的基础上，上机实验是最佳途径。
因此，实验环节的好坏是能否学好本课程的关键。
为了更好地配合学生实验，特编写本实验指导书。
第1章实验指导1.1 实验意义实验是对学生的一种全面综合训练。
是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常，实验题中的问题比平时的习题复杂得多，也更接近实际。
实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上知识变“活”，起到深化理解和灵活掌握教学内容的目的。
平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。
此外，还有很重要的一点是：机器是比任何教师都严厉的检查者。
1.2 实验步骤常用软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。
虽然数据结构课程中的实验题目远不如实际问题中的复杂程度高，但为培养一个软件工作者所应具备的科学工作方法和作风，也应该遵循以下五个步骤来完成实验题目：1．问题分析和任务定义设计之前，首先应该充分分析和理解问题，明确问题要求做什么，限制条件是什么等。
《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数（小时）1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。
二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。
上机时签到；下机时验收签字。
三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。
实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。
数据结构实验指导书适用所有开设数据结构实验的专业雷文赵攀编写概述一、课程目的《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。
通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，实验题中的问题比平时的练习题要复杂，也更接近实际，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
本课程实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。
二、实验名称与学时分配三、实验要求⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。
⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。
对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。
⒊算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。
⒋测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
三、实验考核每次实验结束后，均应上交实验报告。
数据结构课程实验成绩单独考核，占1个学分。
实验报告应包括如下内容：1、问题描述：简述题目要解决的问题是什么。
南阳理工学院数据结构上机实验指导书（2011版）软件学院·软件工程教研室2011.3目录实验1 线性表应用 (2)实验2 栈和队列的应用 (3)实验3 线性表应用 (6)实验4 图论及其应用 (17)实验5 查找 (19)实验6 排序 (22)实验1 线性表应用一、实验目的1.了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。
2.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。
3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、实验内容及步骤1.利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2.掌握程序分文件（头文件和实现文件）书写的方式。
3.分别用顺序表和链表实现课本算法 2.2：合并两个非递减有序序列，并对其时间性能做出分析。
P21#include"c1.h"typedef int ElemType;#include"c2-1.h"#include"bo2-1.c"#include"func2-3.c" /* 包括equal()、comp()、print()、print2()和print1()函数 */void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法2.2 */{ /* 已知线性表La和Lb中的数据元素按值非递减排列。
*//* 归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列 */ int i=1,j=1,k=0;int La_len,Lb_len;ElemType ai,bj;InitList(Lc); /* 创建空表Lc */La_len=ListLength(La);Lb_len=ListLength(Lb);while(i<=La_len&&j<=Lb_len) /* 表La和表Lb均非空 */{GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}} /* 以下两个while循环只会有一个被执行 */while(i<=La_len) /* 表La非空且表Lb空 */{GetElem(La,i++,&ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len) /* 表Lb非空且表La空 */{GetElem(Lb,j++,&bj);ListInsert(Lc,++k,bj);}}void main(){SqList La,Lb,Lc;int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};InitList(&La); /* 创建空表La */for(j=1;j<=4;j++) /* 在表La中插入4个元素 */ListInsert(&La,j,a[j-1]);printf("La= "); /* 输出表La的内容 */ListTraverse(La,print1);InitList(&Lb); /* 创建空表Lb */for(j=1;j<=7;j++) /* 在表Lb中插入7个元素 */ListInsert(&Lb,j,b[j-1]);printf("Lb= "); /* 输出表Lb的内容 */ListTraverse(Lb,print1);MergeList(La,Lb,&Lc);printf("Lc= "); /* 输出表Lc的内容 */ListTraverse(Lc,print1);}实验2 栈和队列的应用一、实验目的1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
数据结构实验指导书目录实验规则 (2)实验环境 (2)实验报告要求 (3)实验一单链表（一） (4)实验二单链表（二） (5)实验三栈 (6)实验四二叉树 (7)实验五最短路径 (8)实验六内部排序 (9)实验规则为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则：1、实验前必须充分预习，完成指定的预习任务。
预习要求如下：（1）认真阅读指导书，进行必要的设计与计算。
（2）熟悉实验内容。
（3）预先复习，并按要求编写程序。
（4）未完成预习任务者不得进入实验室。
2、遵守以下纪律：（1）在实验室不得做和实验无关的事情。
（2）进行任课老师指定内容以外的实验，必须经指导教师同意。
（3）遵守纪律，不迟到。
（4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。
实验环境本实验在386以上的微机上进行，运行环境为VC6.0。
实验报告要求1、实验题目2．实验目的3．实验环境4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案6．实验思考：（学生对本次实验的收获的总结）一、实验目的掌握线性表的链式存储结构及其基本操作。
二、预习要求1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。
2、根据要求，编写程序准备上机调试。
三、实验内容实现一个简单的学生信息管理系统，该系统的功能有：1、利用单链表建立学生基本信息表2、浏览每个学生的信息3、根据学号查询某个学生的基本信息4、添加学生信息到单链表中5、删除一个学生的信息四、实现提示设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。
一、实验目的掌握线性表的链式存储结构及其基本操作。
二、预习要求1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。
2、根据要求，编写程序准备上机调试。
数学与计算机科学学院计算机科学与技术专业
《数据结构》课程实验
指导手册
目录
实验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.实验环境配置
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实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。
实验一学生成绩管理系统设计一、问题描述某班有30个学生，每个学生的只要信息包含学号、姓名、各科（计算机、英语、数学等）成绩。
要求通过计算机对这些数据信息进行管理，设计出一个学生成绩管理系统。
二、实验目的1、掌握线性表的基本运算（插入、删除、修改等）。
2、进一步学习C语言程序设计方法与技巧。
三、实验内容与要求学生信息表如下1、要求同学们首先建立学生的姓名、学号、课程表，将每个学生的姓名、学号录入，成绩下来后根据学号将录入每人的成绩；2、班上若有退学或留级的，将删除该学生的信息；3、若有新插入本班的则将该学生的信息加到该表中；4、日常可能由于各种原因需要浏览所有学生的成绩信息，也有可能修改学生信息。
5、以上所有的功能都是随机的。
需要设计一个合理的输入输出界面或者功能菜单。
四、相关算法与分析学生成绩管理系统设计主要涉及到的是数据结构中线性表的相关知识，包括线性表的插入、删除、查找等基本运算，该实验正是课本中相关内容的综合。
学生在实验中首先设计一个合理的输入输出界面，然后将各种运算应用到程序中就可以。
线性表的基本运算可以采用顺序存储结构实现也可以采用链式存储结构实现。
下面给出了设计的参考范例。
#include "stdafx.h"#include "stdlib.h"#include "string.h"#define maxlen 100typedef struct student{char name[10],no[10];int math,eng,comp;}elemtype;/*******************************************************/ /**********以下是线性表顺序存储结构的插入算法begin******/ /*******************************************************/ int insert(elemtype a[],int *n,int i,elemtype x){int j;if(i<0||i>*n){printf("\n when insert, the position is invalid");return 0;}elseif(*n==maxlen-1){printf("\n the list is full!");return 0;}else{for(j=*n-1;j>=i;j--) a[j+1]=a[j];//元素后移a[i]=x; //插入元素(*n)++; //表长加1return 1;}}/****************************************************//**********线性表顺序存储结构的插入算法end***********//****************************************************//*###################################################//**********线性表顺序存储结构的删除算法begin*********//****************************************************/int del(elemtype a[],int *n,int i){int j;if(i<0||i>*n-1){printf("\n when del, the position is invalid!");return 0;}else{for(j=i+1;j<=*n-1;j++) a[j-1]=a[j];//元素前移；(*n)--;return 1;}}/****************************************************/ /**********线性表顺序存储结构的删除算法end*********/ /****************************************************///主函数如下：main(){elemtype stu[maxlen],x;int i,sel,p,q;int *len,temp;char kch[10];printf("\n\n 1-------------初始化\n");printf(" 2-------------录入成绩\n");printf(" 3-------------插入\n");printf(" 4-------------删除\n");printf(" 5-------------修改\n");printf(" 6-------------显示\n");printf(" 0-------------退出\n");len=&temp;*len=-1;do{printf("\n Input your choice:");scanf("%d",&sel);getchar();switch(sel){case 1: printf("\n input the list's length: ");scanf("%d",len);getchar();for(i=0;i<=*len-1;++i){printf("\n Enter No, Name");stu[i].math=0;stu[i].eng=0;stu[i].comp=0;gets(stu[i].no);gets(stu[i].name);}break;case 2: printf("\n input the class name and score");gets(kch);if(strcmp(kch,"math")==0)for(i=0;i<=*len-1;++i) scanf("%d",&stu[i].math);else if(strcmp(kch,"eng")==0)for(i=0;i<=*len-1;++i) scanf("%d",&stu[i].eng);else if(strcmp(kch,"comp")==0)scanf("%d,&stu[i].comp");break;case 3: printf("\n input the inser position:");scanf("%d",&p);printf("\n input the information: no,name, math,english,computer");getchar();scanf("%d%d%d",&x.math,&x.eng,&p);insert(stu,len,p,x);break;case 4: printf("\n input the delete position:");scanf("%d",&p);del(stu,len,p);break;case 5: printf("\ninput the modify element position:");scanf("%d",p);printf("\n input the new information:no,name,math,eng,comp");scanf("%s%s%d%d",stu[p].no,stu[p].name,&stu[p].math,&stu[p].eng,&stu[p].comp);break;case 6:printf("\n input the start and end position:");scanf("%d%d",&p,&q);printf("\n no name math english computer");if(p>=0&&q<=*len-1)for(i=p;i<=q;++i)printf("\n%8s;%8s;%8u;%8u\n",stu[i].no,stu[i].name,stu[i].math,stu[i].eng,stu[i].comp);elseprintf("\n the position is wrong");break;case 0: exit(0);}}while(sel!=0);}五、实验进一步的要求及思考题1、可以在实验要求的基础上，进行功能扩展，增加一些统计功能，比方求平均成绩，求各科的平均成绩，求每个人的总成绩，对成绩进行排序等等。
2、本指导书给出的范例程序是采用线性表顺序存储结构实现的，同学可以尝试线性表链式存储结构实现。
实验二利用栈实现迷宫的求解一、问题的描述这是实验心理学中的一个经典问题，心理学家把一只动物从一个无顶盖的大盒子的入口处赶进迷宫。
迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引动物在迷宫中寻找通路以到达出口。
二、实验目的1、掌握数据结构栈的基本运算。
2、掌握程序设计中回溯法的应用。
3、理解迷宫问题的本质。
4、回顾C语言程序设计的相关技巧和方法。
三、实验内容与要求四、相关算法与分析1、求解的思想：回溯法是一种不断试探且及时纠正错误的搜索方法。
下面的求解过程采用回溯法。
从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。
