实验一、线性表基本操作
一、实验目的
1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。
2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。
二、实验内容
1. 线性表的顺序存储表示（结构）及实现。
参照教材P23页例2-1，编程实现顺序表的存储与操作。 注意几个问题：
（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含?动态分配?一维数组的结构体，这种方法比较灵活抽象。在此本书中采用的是含?静态?一维数组和线性表长的结构体： typedef struct
{ DataType list[MaxSize]; /* 一维数组 子域 */ int size; /*顺序表长度 子域 */ }SeqList; /* 顺序存储的结构体类型 */
（2）要求编写一个完整程序，实现顺序表的存储与基本操作。在主函数中采用简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术（参照P75页例3-5）。其中菜单形式为：
********************************************* 1、建立顺序表
2、求当前数据元素个数
3、在i位置插入元素x
4、删除第i个元素，并返回其值 5、取i位置数据元素
6、结束程序运行
*********************************************
请输入您的选择 (1,2,3,4,5,6)：
2. 线性表的链表存储表示（结构）及实现。
参照教材P35页例2-3，编程实现单链表（带头结点）的存储与操作。 注意几个问题：
（1）关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中可以不相邻,既地址不连续。不同的教材的表示基本是一致的。 typedef struct Node
{ DataType data; /* 数据子域 */ struct Node *next; /* 指针子域 */ }SLNode; /* 结点结构类型 */
（2）要求编写一个完整程序，实现顺序表的存储与基本操作。在主函数中采用简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术（参照P75页例3-5）。其中菜单形式为：
********************************************* 1、建立单链表
2、求当前数据元素个数
3、在i位置插入元素x
4、删除第i个元素，并返回其值 5、取i位置数据元素
6、结束程序运行
*********************************************
请输入您的选择 (1,2,3,4,5,6)：
3. 设计循环单链表。 要求：（1）循环单链表的操作包括初始化、求数据元素个数、插入、删除、取数据元素。
（2）设计一测试主函数，实际运行验证所设计的循环单链表的正确性。
实验二、线性表的应用
一、实验目的
1. 深入了解与掌握链表的逻辑结构特性 2. 熟练掌握利用线性解决一些实际应用问题。
二、实验内容
1. 编程实现任意一元多项式加法（教材P47习题2-26）。
2. 单链表合并（可适当参照P43页例2-7）。
（1）创建两个类型为字符型的带头结点的有序单链表L1和L2。
（2）将L1和L2合并到一新链表L3中，使得L3表中元素值也有序，统计L3中元素个数并显示出来。
（3）要求：屏幕上可以显示L1和L2元素列表，以及合并后单链表L3元素列表。
实验三、栈和队列的应用
一、实验目的
1. 掌握栈的存储结构，并能在现实生活中灵活运用。
2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 3. 了解和掌握递归程序设计的基本原理和方法。
二、实验内容
1、中值表达式求值问题。 要求：（1）先设计一个函数把中缀算术表达式转换为后缀算述表达式。 （2）再设计一个函数实现后缀表达式的求值计算。 （3）设计一个主函数进行测试。
2、利用循环队列模拟舞伴配对问题：
（1）在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。
（2）假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。
（3）要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。
实验四、串操作
一、实验目的
1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。
2. 熟悉C语言的字符和把字符串处理的原理和方法。 3. 掌握字符串匹配算法
二、实验内容
1、字符串的操作。 基本要求：
（1）字符串采用动态数组存储，建立两个字符串string1和string2，输出两个字符串。 （2）将字符串string2的头n个字符添加到string1的尾部，输出结果。 （3）查找字符串string3在string1中的位置，若string3在string1中不存在，则插入string3在string1的m位置上，输出结果。 测试数据：
（1）string1: “typedefstructArcBox” string2: “VertexTypedata” string3: “data”
（2）string1: “structArcBox” string2: “VertexType” string3: “Box”
2、字符串加密。
问题描述：一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： abcdefghi jklmnopqrstuvwxyz ngzqtcobmuhelkpdawxfyivrs j 则字符串“encrypt”被加密为”tkzwsdf”。 基本要求：
（1）编写一个算法将输入的文本串进行加密后输出。
（2）编写一个算法，将输入的已加密的文本串解密后输出。 （3）编写一个主函数进行测试。 测试数据
（1）需加密文本串为“encrypt”，加密后应为”tkzwsdf”。 （2）需解密文本串为”tkzwsdf”，解密后应为“encrypt”。