搜索
《数据结构》实验指导书齐晓轩编沈阳大学信息工程学院目录实验一：C语言运行环境、算法设计1实验二：顺序表的基本操作3实验三：线性链表的基本操作5实验四：顺序栈的基本操作6实验五：队列的基本操作7实验六：串的基本操作8实验七：数组和矩阵11实验八：二叉树的基本操作12实验九：图13实验十：查找14实验十一：排序15-1-课程编号：1241331课程类别：基础必修课适用层次：本科适用专业：计算机科学与技术计算机科学与技术（电子商务）课程总学时：80适用学期：第4学期实验学时：30开设实验项目数：11撰写人：齐晓轩审核人：刘天惠教学院长：范立南实验一：C语言运行环境、算法设计一、实验目的与要求1．熟悉TC环境的组成及使用方法。2．了解C语言程序从编辑、编译、连接到运行并得到运行结果的过程。3．学习把算法改成C程序的方法。二、实验类型验证型三、实验原理及说明算法是指为了完成某一特定功能的指令序列，它阐述程序设计的总体思路。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1．在开始实验之前，先建立自己的工作目录，可用自己的班级加学号或姓名命名。2．熟悉VC环境的组成及使用。3．了解算法设计。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。编写自大到小依次输出顺序读入的三个数X、Y和Z的值的程序，并在TC或VC++环境下调试通过，最后写出程序的运行结果。要求:包括主函数，排序函数和输出函数三部分。在主程序中任意输入三个数，调用排序函数进行排序，在输出函数中输出排序结果。六、注意事项注意算法在C语言编程环境中无法直接运行，需要改成C程序才能正确执行。七、预习与思考题1．程序和算法的区别。-2-实验二：顺序表的基本操作一、实验目的与要求1．理解和掌握顺序表的结构类型定义方法。2．掌握建立顺序表的基本方法。3．掌握显示顺序表元素的基本方法。二、实验类型设计型三、实验原理及说明1．顺序表即线性表的顺序存储结构，是指用一组地址连续的存储空间来依次存放逻辑位置相邻的元素的存储结构。在线性表的顺序存储结构上插入、删除元素需要移动原有元素。2．线性表的顺序存储结构是随机存储结构，适合进行查找运算。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1建立一个顺序表，要求从键盘输入整数，并将该顺序表的元素从屏幕显示出来，并完成查询元素功能。选做题：2、在第1题基础上添加插入和删除元素功能。六、注意事项注意线性表顺序存储结构的特点。七、预习与思考题1．线性表的顺序存储结构适合进行哪些运算？-3-实验三：线性链表的基本操作一、实验目的与要求1．理解和掌握单链表的类型定义方法和结点生成方法。2．掌握利用头插法和尾插法建立单链表、显示单链表元素等的算法。二、实验类型设计型三、实验原理及说明1．链表即线性表的链式存储结构，是指用一组地址不一定连续的存储空间来存放数据元素，数据元素之间的逻辑关系需要指针来存储。2．在线性表的链式存储结构上插入、删除元素不需要移动原有元素。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1、设计程序实现单链表的基本操作，在此程序中可以演示单链表的创建和输出链表数据。要求：数据个数和数据从键盘输入。2、在第1题基础上添加插入、删除和查找元素功能。六、注意事项注意线性表链式存储结构的特点。八、预习与思考题1．线性表的链式存储结构适合进行哪些运算。-4-实验四：顺序栈的基本操作一、实验目的与要求1．掌握顺序栈的类型定义方法。2．掌握在顺序栈上实现的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。3．掌握顺序栈的简单应用。二、实验类型设计型三、实验原理及说明1．栈属于一种运算受限的线性表，它只允许在一端进行插入和删除运算。2．栈的运算特点是先进后出。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1．设计一个抽象数据类型栈的顺序表示和实现的演示程序，其基本操作有初始化栈、判栈空否、入栈、出栈等。2．利用定义好的顺序栈将一个非负的十进制整数N转换为对应的B进制数。要求：非负的十进制整数N和B都从键盘输入；转换结果从屏幕输出。六、注意事项注意栈与队列运算特点的不同。七、预习与思考题1．利用栈如何进行表达式求值。-5-实验五：队列的基本操作一、实验目的与要求1．掌握队列的类型定义方法及基本操作的实现。2．理解和掌握循环队列解决假溢出的方法。二、实验类型设计型三、实验原理及说明1．队列属于一种运算受限的线性表，它只允许在一端进行插入，而在另一端进行删除运算。2．队列的运算特点是先进先出。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1设计一个队列的表示和实现的演示程序，其基本操作有初始化队列、判队列空否、入队列、出队列等。选做题：2设计一个循环队列的表示和实现的演示程序，其基本操作有初始化队列、判队列空否、入队列、出队列等。六注意事项注意栈与队列运算特点的不同。七、预习与思考题1．队列在实际问题中的应用。-6-实验六：串的基本操作一、实验目的与要求1．熟练掌握字符串的数据类型定义以及字符串的基本操作的定义，并能利用这些基本操作实现字符串的其他基本操作的方法。2．熟练掌握字符串串的定长顺序存储结构上实现字符串的各种操作的方法。二、实验类型设计型三、实验原理及说明1．串属于一种取值受限的线性表，它是由若干个字符组成的有限序列。2．串有3种机内表示方法：定长顺序存储表示、堆分配存储表示、串的块链存储表示。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1．实现了串的创建，输出和求串的长度功能。选做题：2．在1基础上进行改进实现求子串（输出从pos位置起长度为len的子串）或串删除（删除从pos位置起长度为len的子串）操作。六、注意事项注意串的三种存储结构的区别。七、预习与思考题1．串与线性表的异同。-7-实验七：数组和矩阵一、实验目的与要求掌握数组的各种存储方法及其上的基本操作的实现。二、实验类型设计型三、实验原理及说明存储单元是一维的结构，而数组是个多维的结构，用一组连续的存储单元存放数组中的数据元素则有一个次序约定。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤编写程序以矩阵格式输出按行压缩存储的n阶下三角矩阵。六、注意事项以行序为主序和以列序为主序存储数组中数据元素的操作不同。七、预习与思考题1．三对角矩阵的压缩存储方式。-8-实验八：二叉树的基本操作一、实验目的与要求1．了解二叉树是一种重要的非线性数据结构。2．掌握二叉树的二叉链表存储结构和遍历方法。二、实验类型设计型三、实验原理及说明1．二叉树是一种有序树。2．二叉树的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。3．二叉树常用的遍历方法有三种：先序遍历、中序遍历、后序遍历。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤从键盘上输入一组数据（以-1结束），建立一个以二叉链表形式存储的二叉树。分别实现先序、中序和后序遍历二叉树的算法。对所建立的二叉树分别进行先序、中序和后序遍历，并输出结果。六、注意事项注意二叉树是一种有序树。七、预习与思考题1．二叉树与树的区别。-9-实验九：图一、实验目的与要求1．掌握图的结构特征，以及邻接矩阵或邻接表存储结构的特点和程序设计方法。2．掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法的设计方法。二、实验类型设计型三、实验原理及说明1．图是一种非线性数据结构，图中的每个数据元素既可有多个直接前趋，也可有多个直接后继。2．图的存储结构常用的有邻接矩阵、邻接表两种。3．图的遍历常用的有两种：深度优先遍历和广度优先遍历。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1．编写一个图的深度或广度优先遍历算法，并输出程序的运行结果。六、注意事项注意所设计的算法是否适用于非连通图。七、预习与思考题1．如果图是一个非连通图，上述算法能否实现图的遍历？如何改进？-10-实验十：查找一、实验目的与要求1．理解折半查找原理。2．通过折半查找的算法实现，进一步掌握顺序查找和分块查找的算法。二、实验类型设计型三、实验原理及说明1．若查找表中元素按关键字有序，并采用顺序存储结构进行存储，可采用折半查找方法进行查找。2．分块查找是先确定待查找元素位于哪一块，然后再在某一块内查找元素的查找方法。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤建立一个有序的顺序表，实现折半查找算法。要求能进行多次查找，对每次查找，要求输出查找的结果和查找时需和表中关键字进行比较的次数。六注意事项二分查找仅适用于有序表。七、预习与思考题1．比较顺序查找、分块查找和二分查找的异同。-11-实验十一：排序一、实验目的与要求1．理解各种排序基本思想和特点。2．对已知一组数据，能写出其具体的排序过程、算法及完整程序，并上机调试。3．了解每一种排序的时间及空间复杂度。二、实验类型设计型三、实验原理及说明排序是指将待排序的数据元素按照某种规律顺序排列起来，使得它们按照关键字由小到大（或者由大到小）排列。四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤编写一个完整程序，采用两种排序方法实现对某一组无序序列的非递减排序操作。在主程序中输入初始序列，调用排序算法进行排序，输出排序结果。六、注意事项注意各种排序算法思路的不同。八、预习与思考题1．希尔排序和快速排序算法的时间复杂度。