《数据结构》课程上机实验指导书
实验一
【实验名称】顺序表的基本算法
【实验目的】
创建一个顺序表，掌握线性表顺序存储的特点。
设计和验证顺序表的查找、插入、删除算法。
【实验要求】
（1）从键盘读入一组整数，按输入顺序形成顺序表。
并将创建好的顺序表元素依次打印在屏幕上。
设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。
当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。
（4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。
【实验步骤】、实验前先写好算法。
1 上机编写程序。
2、编译。
3、调试。
4、
综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct
{
datatype items[listsize];
int length;
}SpList;
实验二
【实验名称】单链表的基本算法
【实验目的】
创建一个单链表，掌握线性表链式存储的特点。
设计和验证链表的查找、插入、删除、求表长的算法。
【实验要求】
（1）从键盘读入一组整数，按输入顺序形成单链表。
并将创建好的单链表元素依次打印在屏幕上。
（注意：选择头插法或者尾插法！）
设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。
当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。
（4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。
【实验步骤】、实验前先写好算法。
1 、上机编写程序。
2 编译。
3、调试。
4、
综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node
{
Datatype ch;
struct Node *next;
}LNode, *Pnode, *Linklist;
实验三
【实验名称】回文判断的算法
【实验目的】
利用栈和队列的操作来实现对字符序列是否是一个回文序列的判断。
设计和验证入栈、出栈及入队、出队的算法。
【实验要求】
（1）从键盘读入一组字符序列，按输入顺序入队列到链式队列A中。
并将创建好的A队列中元素依次遍历，打印在屏幕上。
将字符序列从A（2）队列出队列，压入到一个顺序栈B中。
再将字符序列从顺序栈B中出栈，所有元素依次遍历，打印在屏幕上。
（3）
将A，B的元素值逐一比较，判断是否一致。
若一致则是回文，并将判定结果打（4）印到屏幕上。
注意：指定采用顺序栈和链队列的结构来实现。
【实验步骤】
1、设计算法
2、编写程序
3、编译
4、调试
例程：栈的各种操作如算法3-3，3-4，队列的操作比如算法3-15，3-16等等。
可能用到的字符串函数，比如strlen（），strcmp（）等。
顺序栈：
typedef struct{
char items[stacksize];
int top;
}SqStack;
链队列：
typedef struct QNode{
char data;
struct QNode *next;
}LQNode , *PQNode;
typedef struct{
PQNode front ,rear;
}LinkQueue;
实验四
【实验名称】哈希查找
【实验目的】
验证哈希查找算法
【实验要求】
（1）先创建一个数组类型的顺序表，以—1作为结束。
从键盘输入一组数据元素后，按顺序表的遍历输出，并打印显示。
（2）再以哈希函数方式，将数据元素放入哈希表中，并将哈希表输出，并打印显示。
采注意：哈希表的下标和数据内容都显示到屏幕上。
用线性探测法处理冲突。
．
（3）输入需要查找的任意元素的关键字，查找并输出该元素的位置下标序列号。
若有冲突，显示它原来
的下标位置和新的下标位置。
若没有，也将找不到的信息反馈出来。
注意：用线性探测法处理冲突。
【实验步骤】
1、设计算法
2、编写程序
3、编译
4、调试
例程：
参考书上的算法P274-277的多个算法。
比如：哈希表的地址区间为0-17，哈希函数为h(key)=K。
采用线性探测法处理冲突。
若给定关键字序列：26，25，72，38，8，18，59。
请问搜索59在几号下标位置，需要查找多少次？
实验五
【实验名称】排序操作
【实验目的】
验证各种排序算法。
在调试中体会排序过程。
【实验要求】
（1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。
（2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序。
【实验步骤】
1、设计算法
2、编写程序
3、编译
4、调试
例程：冒泡排序法、直接选择排序法、直接插入排序
实验六（综合）
【实验名称】学生成绩表的操作
【实验目的】
加强线性表操作的训练。
【实验要求】
（1）先创建一个数组类型或链表类型的线性表，其中每个数据元素包括的数据项内容有：学生学号，姓名，及语文，数学，英语三门课程的分数。
（2）利用键盘输入数字在主函数中选择菜单的功能，可以对学生成绩表进行多项操作，比如：增加一个学生的信息，删除一个学生的信息，查找一个学生的信息，或者按某门课程分数进行学生的排序等等。
（3）每个操作完成后，在屏幕上将该线性表的数值完全输出。
【实验步骤】
5、设计算法
6、编写程序
7、编译
8、调试
线性表的各种操作例程：
数据结构课程实验报告要求
实验题目
班级姓名学号日期一、需求分析
1．程序的功能；
2．输入输出的要求；
3．测试数据。
二、概要设计
1．本程序所用的抽象数据类型的定义；
2．主程序的流程及各程序模块之间的层次关系。
三、详细设计
1．采用c语言定义相关的数据类型；
2．写出各模块的伪码算法；
3．画出函数的调用关系图。
四、调试分析
1．调试中遇到的问题及对问题的解决方法；
2．算法的时间复杂度和空间复杂度。
五、源程序（带注释）
使用说明及测试结果六、．。