数据结构试验指导书Word格式.docx
- 文档编号:1094530
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:14
- 大小:63.48KB
数据结构试验指导书Word格式.docx
《数据结构试验指导书Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构试验指导书Word格式.docx(14页珍藏版)》请在冰点文库上搜索。
前言2
目录3
实验一顺序线性表的基本操作4
实验二单链表的基本操作5
实验三栈的顺序表示与实现6
实验四栈的链式表示和实现6
实验五队列的顺序表示与实现8
实验六队列的链式表示与实现8
实验七二叉树的基本操作10
实验八哈夫曼树的构造及编码实验10
实验九二叉排序树的基本操作11
附录一:
《数据结构》实验教学大纲12
附录二:
《数据结构》实验报告格式13
实验一
顺序线性表的基本操作
【实验目的】
1.熟悉C语言的上机环境,进一步掌握C语言的结构特点。
2.掌握线性表的顺序存储结构的定义及C语言的实现。
3.掌握顺序线性表的建立、插入、删除、查找等基本操作。
【实验内容】
把从键盘输入的n个整数以顺序存储的方式建立一个线性表,然后输出该表及该表的长度;
删除第m个结点后重新输出该表及长度;
在表中的第k个结点后插入2个结点后重新输出该表。
【实验安排】
由于该实验是数据结构的第一个实验,建议适当多安排一些时间进行熟悉。
建议课时安排如下:
课外6学时,课内2学时
【实验提示】
1.采用C语言的数组类型实现线性表的顺序存储,用C语言的结构体类型定义顺序表结点:
、
#defineMAXSIZE10
typedefintelemtype;
//线性表中存放整形元素
typedefstruct
{elemtypevec[MAXSIZE];
intlen;
}sequenList;
2.为了方便调试及编程,可以分析题目,将整个实验分解成若干个小的函数,最后由主函数分别调用子函数即可,建议编写下列子函数:
CreateList//建立顺序表函数
PrintList//输出顺序表函数
GetLenList//顺序表长度函数
Insert//在顺序表中插入结点函数
Delete//在顺序表删除结点函数
3.进行实验结果测试时,要注意分别对头结点、尾结点及空表分别进行测试,另外要对满表进行测试,看是否有溢出情况发生。
实验二单链表的基本操作
1.掌握单链表的链式存储结构的定义及C语言的实现。
3.掌握单链表的建立、插入、删除、查找、合并等基本操作。
分别把从键盘输入的n1个整数和n2个整数以链式存储的方式建立两个单链表,然后输出两表及两表的长度;
删除第1个链中的第m个结点后后重新输出该表及长度;
在第2表中的第k个结点后插入2个结点后重新输出该表;
最后将两个表合并后重新输出新表及长度,最后输出相邻两结点data值之和为最大的第一结点。
课外4学时,课内2学时
1.采用C语言的定义表结点如下:
{elemtypedata;
//数据域
structnode*next;
//指针域
}linkList;
CreateList//建立表函数
PrintList//输出表函数
GetLenList//求表长度函数
Insert//插入结点函数
Delete//删除结点函数
MergeList//合并表函数
Adjmax(L)//求值函数
3.进行实验结果测试时,要注意分别对头结点、尾结点及空表分别进行测试。
实验三栈的顺序表示与实现
掌握栈的顺序表示和实现。
编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能:
1.初始化顺序栈
2.插入元素
3.删除栈顶运算
4.取栈顶元素
5.遍历顺序栈
6.置空顺序栈
课外2学时,课内1学时
采用C语言的定义顺序栈的存储结构:
{elemtypestack[MAXNUM];
inttop;
}sequenStack;
实验四栈的链式表示和实现
掌握栈的链式表示和实现。
编写一个程序实现链栈的下列各种基本运算:
1.初始化链栈
2.链栈置空
3.入栈
4.出栈
5.取栈顶元素
6.遍历链栈
并在此基础上编写实现算术表达式求值程序(栈的运用):
设操作数:
0,1,2,……,8,9(可扩充);
运算符:
+,—,*,/,(,),#(#号为结束)。
输入中缀表达式,如:
5+(4—2)*3#,将其转换成后缀表达式:
542—3*+#,
然后计算,本例结果为11。
程序结构:
类型说明;
Clearstack(S)、Emptystack(S)、Push(S)、Pop(S);
中缀到后缀转换的函数:
Mid-post(E[n],B[n]);
后缀表达式求值的函数:
Postcount(B[n]);
main()
{变量说明;
输入中缀表达式,存入E[n];
调用Mid-post(E,B);
调用Postcount(B);
打印表达式结果;
Y继续?
N
停止
}
采用C语言的定义链栈的存储结构:
typedefstruct
Stacknode*next;
}stacknode;
实验五队列的顺序表示与实现
掌握队列的顺序表示和实现。
编写一个程序实现顺序队列的各种基本运算,并在此基础上设计一个主程序,完成如下功能:
1.初始化队列
2.建立顺序队列
3.入队
4.出队
5.判断队列是否为空
6.取队列头元素
7.遍历队列
1.采用C语言的定义顺序队列的存储结构:
{elemtypesuqueue[MAXNUM];
intfront;
intrear;
2.注意:
当头尾指针相等时,队列为空;
在非空队列里,队头指针始终指向队头元素,队尾指针指向队列的下一元素位置。
实验六队列的链式表示与实现
掌握队列的链式表示和实现。
编写一个程序实现链队的各种基本运算:
2.建立链队列
7.遍历链队列
最后编写一个主程序,实现如下的图的过程:
typedefstructQnode
{elemtypetypedata;
StructQnode*next;
}Qnodetype;
2.为了方便实现,可以使用头结点。
实验七二叉树的基本操作
1.掌握二叉树的链式存储结构及实现方法。
2.掌握二叉树的遍历方法。
3.掌握二叉树中插入结点、删除结点的方法。
4.掌握二叉树的结点个数、叶子结点个数和树的深度的计算方法。
用键盘输入一字符串,按照满二叉树的特点生成一颗二叉树,并将该二叉树分别用先序、中序和后序的方法遍历并输出遍历结果,然后输出该树的深度。
1.采用C语言的定义树的存储结构:
typedefstructbtnode
{chardata;
structbtnode*lchild,*rchild;
}bitree;
2.可以考虑采用递归的方法先创建根结点,然后分别创建左右子树。
在创建二叉树的过程中,要注意结点数是根据输入的字符确定的。
实验八哈夫曼树的构造及编码实验
掌握哈夫曼树的构造方法及其编码方法。
.设电文字符集D及各字符出现的概率F如下:
D={a,b,c,d,e,f,g,h}(字符数n=8)
F={5,29,7,8,14,23,3,11}(%)
编写完成下列功能的程序:
①构造关于F的Huffman树;
②求出并打印D总各字符的Huffman编码。
在哈夫曼树编码时,一般令左分支为0,右分支为1,然后对哈夫曼树进行遍历,输出哈夫曼编码。
实验九二叉排序树的基本操作
掌握二叉排序树的构造方法。
设英文句子:
“everyoneroundyoucanhearyouwhenyouspeak.”,试编写完成下面任务的程序。
(1)依次读入句中各单词,构造一棵二叉排序树;
(2)按LDR遍历此二叉排序树。
LDR:
caneveryonehearroundspeakwhenyou(有序)
若遍历二叉排序树的结果序列无序,则说明构树时发生错误。
《数据结构》实验教学大纲
课程名称:
数据结构课程总学时:
54
课程编号:
050414上机学时:
12
面向专业对象:
计算机系本科生实验类别:
专业课实验
实验地点:
计算机实验室
实验教学的目的
数据结构是计算机软件的专业基础课,与之配套的上机实验是体现理论联系实际的重要环节。
通过本实验课,学生可以将课堂、书本上所学到的软件理论、技术与方法运用到实验任务的题目中。
其目的之一是为后继课程(如“操作系统”、“编译系统”、“数据库原理”等)的学习打下良好的基础;
其二是提高学生独立承担编程任务的能力与水平。
实验教学的基本要求
了解各种类型的“数据元素”、“数据结构”的描述及存储方法;
将一些重要的算法转换成C语言程序实现。
要求将布置的程序题调试成功、在计算机上正确运行。
鼓励学生编程独创性的发挥。
实验教材
《数据结构+算法》(国防工业出版社)
实验项目
序号
学时
实验要求
类型
每组人数
1
链表的建立与运算
2
必修
综合
后缀表达式求值(栈技术运用)
3
队列运算
4
Huffman树及编码
5
二叉排序树的建立及遍历
说明:
5个实验项目通过4个即可通过试验。
实验考核:
实验成绩占总成绩的10%;
缺席一次扣5分,缺席2次取消考试资格。
系主任:
王成耀任课教师:
夏克俭
《数据结构》实验报告格式
1.上机试验题目
2.题目对应的数据结构知识
3.题目对应算法的描述(解题思路)
4.源程序
5.程序运行结果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试验 指导书
![提示](https://static.bingdoc.com/images/bang_tan.gif)