解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，相当于C语言中具体的函数设计。
⒋ 测试用例设计：准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌ 上机调试并分析结果：对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪。最后，详细记录实验过程，并对实验结果进行分析，并于一周内提交实验报告。
四、实验报告要求
1．实验报告格式：实验报告首页按学校统一印刷的实验报告模版书写。
2．实验报告内容：实验基本信息按照实验报告模版要求内容填写，不得有空项。其中：
?
实验内容按任课教师下达的实验任务填写：包括实验目的、任务、具体实验题目和要求；
?
实验过程与实验结果应包括如下主要内容： ? 算法设计思路简介
? 核心算法设计描述：可以用自然语言、伪代码或
流程图等方式
? 算法的实现和测试结果：包括算法时的输入、输
出，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。
4
?
附录可包括源程序清单或其它说明（如功能模块之间的调用与被调用关系等）
实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分
?
五、实验内容
实验一 线性表应用
一. 实验目的
1、掌握用Turbo C或VC++上机调试线性表的基本方法； 2、掌握线性表的基本操作，如插入、删除、查找，以及线性
表合并等运算在顺序存储结构和链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。 二. 实验学时：
课内实验学时：2学时 课外实验学时：4学时 三．备选实验题目
1． 单链表基本操作练习（实验类型：验证型）
1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：
1…建立链表 2…连接链表
5
3…输出链表 0…结束
2）实验要求：在程序中定义下述函数，并实现所要求的函数功能：
CreateLinklist( ): 从键盘输入数据，创建一个单链表 ContLinklist( )：将前面建立的两个单链表首尾相连 OutputLinklist( )：输出显示单链表 3）实验提示:
? 单链表数据类型定义（C语言） # include
typedef int ElemType； //元素类型 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;
? 为了算法实现简单，最好采用带头结点的单向链表。 4）注意问题:
? 重点理解链式存储的特点及指针的含义。 ? 注意比较顺序存储与链式存储的各自特点。 ? 注意比较带头结点、无头结点链表实现插入、删除算法时的区别。
? 单链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。
2． 顺序表基本操作练习（实验类型：验证型） 1）问题描述：
? 从键盘输入一组整型元素序列，建立顺序表。 ? 实现该顺序表的遍历。
6
? 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。
? 判断该顺序表中元素是否对称,对称返回1,否则返回0。 2）实验要求：
? 对应问题描述，在程序中定义4个相应的函数，实现上面要求的函数功能：
? 在主程序中设计一个简单的菜单，调用上述4个函数 3）实验提示:
? 顺序表存储数据类型定义（C语言）
# define MAXSIZE 100 //表中元素的最大个数 typedef int ElemType； //元素类型 typedef struct list{
ElemType elem[MAXSIZE]; //静态线性表 int length; //表的实际长度 }SqList; //顺序表的类型名 4）注意问题:
? 插入、删除时元素的移动原因、方向及先后顺序。 ? 理解不同的函数形参与实参的传递关系。 3． 约瑟夫环问题（实验类型：综合型）
1）问题描述：有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。
7
2）实验要求: 采用顺序和链式两种存储结构实现 3) 实现提示：
? 用顺序表来存储围座者的序号和密码(顺序存储结构).
? 用number 和code分别表示围座者的序号和密码.
假设围座者人数为 j,当前使用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1) mod j.
? 当我们要在线性表的顺序存储结构上的第i个位
置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
? 用链式存储解决此问题时可以采用循环链表. 4）注意问题:
? 顺序存储和链式存储实现此算法时计算出列位置的不同方法，人员出列后所做操作的区别。
4． 一元稀疏多项式简单的计算器（实验类型：综合型） 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器
2）实验要求:
? 采用单链表存储结构一元稀疏多项式 ? 输入并建立多项式 ? 输出多项式
? 实现多项式加、减运算
8