实验一 线性表实验 1
实验二 栈、队列实验 3
实验三 串和数组实验 5
实验四 树实验 5
实验五 图实验 6
实验六 查表实验 7
实验七 内排序实验 8
实验一 线性表实验
【实验目的】
1.掌握顺序表、单链表、循环链表、双向链表的构造原理及其基本运算的实现算法。
2.了解线性表的顺序存储和链式存储结构的特点和适用情形。
【实验学时】
6学时
【实验内容】
题目一：编写一个程序，实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化顺序表L。
（2）依次采用尾插法插入a,b,c,d,e元素。
（3）输出顺序表L及L的长度。
（4）判断顺序表L是否为空。
（5）输出顺序表L的第3个元素。
（6）输出元素d的位置。
（7）在第4个元素位置上插入f元素。
（8）删除L的第3个元素。
（9）输出顺序表L。
（10）释放顺序表L。
题目二：编写一个程序，实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化单链表H。
（2）依次采用尾插法插入a,b,c,d,e元素。
（3）输出单链表H及H的长度。
（4）判断单链表H是否为空。
（5）输出单链表H的第3个元素。
（6）输出元素d的位置。
（7）在第4个元素位置上插入f元素。
（8）删除H的第3个元素。
（9）输出单链表L。
（10）释放单链表L。
题目三：编写一个程序，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（题目三、四选做1个）
（1）初始化双链表H。
（2）依次采用尾插法插入a,b,c,d,e元素。
（3）输出双链表H及H的长度。
（4）判断双链表H是否为空。
（5）输出双链表H的第3个元素。
（6）输出元素d的位置。
（7）在第4个元素位置上插入f元素。
（8）删除H的第3个元素。
（9）输出双链表L。
（10）释放双链表L。
题目四：编写一个程序，实现循环单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化循环单链表H。
（2）依次采用尾插法插入a,b,c,d,e元素。
（3）输出循环单链表H及H的长度。
（4）判断循环单链表H是否为空。
（5）输出循环单链表H的第3个元素。
（6）输出元素d的位置。
（7）在第4个元素位置上插入f元素。
（8）删除H的第3个元素。
（9）输出循环单链表L。
（10）释放循环单链表L。
实训项目：
1.将单链表按某个基准划分。编写一个程序，以给定值x为基准将单链表分割为两部分，所有小于x的结点排在大于或等于x的结点之前。并分析时间复杂度。
2.用单链表表示的两个集合（假设同一个集合中不存在重复的元素），求它们的并、交和差
运算。
3.实现两个多项式相加运算。（2、3选做一个）
4.用单链表实现两个大整数相加运算。要求：（选做）
（1）将用户输入的十进制整数字符串转化为带头结点的单链表，每个结点存放一个整数位。
（2）求两个整数单链表相加的结果单链表
（3）求结果单链表的中间位，如234的中间位是“3”，2345的中间位是“3”。
5.P86 的2.18 约瑟夫问题。
6.列车时刻表管理系统
案例描述：一个火车要对进出本站的列车信息进行计算机管理，包括建立、增加、删除、查询、修改车次信息等。列车信息有车次、开点、到点、始发站、终点站等。已知进出该站的列车车次变化较多。
实验二 栈、队列实验
【实验目的】
1.掌握栈的顺序及链式存储和基本运算的实现方法
2.掌握队列的顺序及链式存储和基本运算的实现方法
3.了解栈和队列的应用
【实验学时】
8学时
【实验内容】
题目一：编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化栈S。
（2）判断栈S是否非空。
（3）依次进栈元素a,b,c,d,e 。
（4）输出栈的长度。
（5）输出从栈顶到栈底的元素。
（6）输出出栈序列。
（7）释放栈。
题目二：编写一个程序，实现循环队列的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化队列Q。
（2）判断队列Q是否非空。
（3）依次进队列元素a,b,c。
（4）出队一个元素，输出该元素。
（5）输出队列Q的元素个数。
（6）依次进入队列元素d,e,f。
（7）输出出队序列。
（8）释放队列。
要求：其中队列的插入和删除算法按照P134 的3.24改写。
【实训项目】：
1.P132：3.10，3.14，3.19。
2.利用栈对只含二目运算符的中缀算术表达式求值，并将该中缀表达式转换为后缀表达式。算术运算符包括：*、/、+、-，优先级从高到低。
3.用栈求解下图所示迷宫的所有路径，并输出最短路径长度及该最短路径。
4.P133的3.17：八皇后问题，可以用递归方法实现，或者借助栈实现。（选做）
5.病人看病模拟程序
编写一个程序，反映病人到医院看病，排队看医生的情况。在病人排队过程中，主要重复两件事：
（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊
（2）护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊
要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下：
●排队――输入排队病人的病历号，加入病人排队队列中；
●就诊――病人排队队列中最前面的病人就诊，并将其从队列中删除；
●查看排队――从对首到队尾列出所有的排队病人的病历号；
●不再排队，余下依次就诊――从对首到队尾列出所有的排队病人的病历号，并退出运行；
●下班――退出运行。
实验三 串和数组实验
【实验目的】
1.掌握串的顺序存储结构
2.掌握串的基本算法及应用
3.掌握模式匹配的各种算法
4.掌握数组和广义表的基本算法
【实验学时】
8学时
【二叉树的遍历及应用实验报告实验内容】
1.采用顺序存储结构存储串，编写一个程序，采用简单模式匹配方法求串s中出现的第一个最长重复子串的下标和长度。例如：s=“aababcabcdabcde”，最长重复子串为：abcd
2.编写一个程序，利用KMP算法求子串t在主串是中出现的次数，并以s=”aaabbdaabbde”,t=“aabbd”为例，显示其匹配过程。（匹配过程的显示选做）。
3.实现稀疏矩阵的基本运算。假设n*n的稀疏矩阵A采用三元组表示，设计一个程序，实现如下功能：
（1）生成如下两个稀疏矩阵的三元组a和b；
1 0 3 0 3 0 0 0
0 1 0 0 0 4 0 0
0 0 1 0 0 0 1 0
0 0 1 1 0 0 0 2
发表评论