数据结构实验指导书
前言
数据结构是软件开发的基础，数据结构课程是软件工程、计算机科学与技术、网络工程、信息安全、物联网工程等专业的必修技术基础课程。该课程是在学生学习高级语言程序设计课程基础上，使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计，学会常用数据分类和数据查找的技术，对所设计的算法会做定量或定性的分析比较，培养学生的算法设计与分析的能力。通过该课程的学习，使学生学会分析数据对象特性，选择合适的数据结构、存贮结构及相应的基本处理算法；初步掌握算法的时间空间复杂度分析技巧。既为学生学习后继课程打好基础，也为将来软件开发提供理论指导。
数据结构具有很强的实践性，只有通过编程上机实验，才能真正领会数据结构的真正内涵，并灵活运用数据结构的基本知识提高自己的软件开发能力。
2
实验1：顺序表及其应用
1．实验目的：
（1）熟练掌握VC或Dev C++集成环境和程序开发步骤； （2）熟练掌握顺序表的插入、删除、查找定位等基本算法； （3）能利用顺序表解决简单的问题。
2．实验原理：
线性表是最基本最常用的一种线性结构。其特点是除了第一个元素和最后一个元素以外，其他数据元素都只有一个前驱和一个后继。一个线性表中的数据元素应具有相同的描述性质，即属于同一个数据对象。
在实际应用中，必须将线性表中的数据存放在计算机中。常用的存储方式有两种：顺序存储和链式存储，线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各个元素，使得数据元素逻辑上的相邻关系与物理上的相邻关系一致。
顺序存储的线性表又称顺序表，可以随机地存取表中的任意一个元素；也无需为表示结点之间的逻辑关系而额外增加存储空间。但是，顺序表在进行插入和删除操作时需要移动大量的元素，影响运行的效率；同时表的最大容量事先无法估计，如果对表长估计的过长，可能会浪费空间，相反则可能会发生溢出的现象。
顺序表的主要基本操作有初始化、判断表空、求表长、插入、删除和查找等。
3．实验内容：
按照如下问题描述，利用顺序表解决问题，编写相应的代码，并运行，记录运行的结果。
（1）问题描述：约瑟夫问题由古罗马的史学家约瑟夫（Josephus）提出的，问题的一种描述是：
编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向从1开始顺序报数，报到m时停止报数。报m的出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1开始报数，如此下去，直至所有人全部出列为止。试设计一个顺序求出出列顺序。
（2）基本要求：利用顺序表存储结构模拟此过程，按照出列的顺序印出各人的编号。
（3）测试数据：m的初值为20；n=7，7个人的密码依次为3，1，7，2，4，8，4，首先m值为
6（正确的出列顺序应为6，1，4，7，2，3，5）。
（4）实现提示：本程序的实现需要将每个人的信息作为一个结点，结点中存放每个人的编号和
密码，由于要反复做删除操作，所以采用数组实现时需要将删除结点之后结点向前移动或者设置删除标志。程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n<=30。
4．实验代码：（本处书写实验程序的代码，由学生完成，若代码比较长，可以仅书写关键函数或算法
的代码）
5．运行结果（选择适当的数据对程序进行测试，此处填写或粘贴程序的运行结果）
6．总结。
3