内容发布更新时间 : 2024/6/29 13:37:43星期一 下面是文章的全部内容请认真阅读。

《数据结构》课程上机实验指导书

实验一

【实验名称】顺序表的基本算法 【实验目的】

创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】

（1） 从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 （2） 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素的功能。 （3） 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；当选择插入

功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。

（4） 每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】

1、 实验前先写好算法。 2、 上机编写程序。 3、 编译。 4、 调试。

例程：书上参考算法2-1，2-4，2-5，2-6，2-8！带菜单的主函数参考书上2.5综合实例！ 注意：顺序表的结构体！ typedef struct { datatype items[listsize]; int length; }SpList;

实验二

【实验名称】单链表的基本算法 【实验目的】

创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。 【实验要求】

（1） 从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。

（注意：选择头插法或者尾插法！）

（2） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找数据元素，

和求单链表表长等几项功能。

（3） 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，

从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。

（4） 每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】

1、 实验前先写好算法。 2、 上机编写程序。 3、 编译。 4、 调试。

例程：书上参考算法2-10，2-12，2-13，2-15，2-17！带菜单的主函数参考书上2.5综合实例！ 另外，注意，指针的初始化！指针的操作必须谨慎！ 链表的结构体如下： typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist;

实验三

【实验名称】回文判断的算法 【实验目的】

利用栈和队列的操作来实现对字符序列是否是一个回文序列的判断。设计和验证入栈、出栈及入队、出队的算法。 【实验要求】

（1） 从键盘读入一组字符序列，按输入顺序入队列到链式队列A中。并将创建好的A队列中元

素依次遍历，打印在屏幕上。

（2） 将字符序列从A队列出队列，压入到一个顺序栈B中。

（3） 再将字符序列从顺序栈B中出栈，所有元素依次遍历，打印在屏幕上。

（4） 将A，B的元素值逐一比较，判断是否一致。若一致则是回文，并将判定结果打印到屏幕上。

注意：指定采用顺序栈和链队列的结构来实现。

【实验步骤】 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） 输入需要查找的任意元素的关键字，查找并输出该元素的位置下标序列号。若有冲突，显示

它原来的下标位置和新的下标位置。若没有，也将找不到的信息反馈出来。