资源描述
数据结构上机实验指导数据结构课程上机实验指导书实验一【实验名称】顺序表的基本算法 【实验目的】创建一个顺序表,掌握线性表顺序存储的特 点。设计和验证顺序表的查找、 插入、删除算法。 【实验要求】(1)从键盘读入一组整数, 按输入顺序形成 顺序表。并将创建好的顺序表元素依次 打印在屏幕上。(2)设计一个带选择菜单的主函数, 菜单中 具备任意选择删除、插入、查找数据元 素的功能。(3)当选择删除功能时, 从键盘读入欲删除 的元素位置或元素值, 按指定方式删除; 当选择插入功能时,从键盘读入新元素 值和被插入位置,在指定位置插入;当 选择查找功能时,从键盘读入欲查找的 元素值,返回其位置序号。(4)每种操作结束后,都能在屏幕上打印出 此时顺序表元素的遍历结果。实验步骤】1、实验前先写好算法。2、上机编写程序。3、编译。4、调试。例程:书上参考算法 2-1, 2-4, 2-5,2-6,2-8! 带菜单的主函数参考书上 2.5 综合实例! 注意:顺序表的结构体!typedef structdatatype itemslistsize; 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 NodeDatatype 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 structchar itemsstacksize; int top;SqStack;链队列: typedef struct QNodechar data;struct QNode *next; LQNode , *PQNode; typedef structPQNode front ,rear; LinkQueue;实验四【实验名称】哈希查找 【实验目的】验证哈希查找算法【实验要求】(1)先创建一个数组类型的顺序表,以 1 作为结束。从键盘输入一组数据元素后, 按顺序表的遍历输出,并打印显示。(2)再以哈希函数方式, 将数据元素放入哈 希表中,并将哈希表输出,并打印显示。 采用线性探测法处理冲突。注意:哈希表 的下标和数据内容都显示到屏幕上。(3)输入需要查找的任意元素的关键字, 查 找并输出该元素的位置下标序列号。 若有 冲突,显示它原来的下标位置和新的下标 位置。若没有,也将找不到的信息反馈出 来。注意:用线性探测法处理冲突。【实验步骤】1、设计算法2、编写程序3、编译4、调试 例程: 参考书上的算法 P274-277 的多个算法。 比如:哈希表的地址区间为 0-17,哈希函数为 h(key)=K%17 。采用线性探测法处理冲突。 若给 定关键字序列: 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 算法的时间复杂度和空间复杂度。五、源程序(带注释)六、使用说明及测试结果
展开阅读全文