数据结构实验指导书

数据结构实验指导书数据结构实验指导书南京工程学院经济管理学院数据结构实验指导书全文共10页，当前为第1页。数据结构实验指导书全文共10页，当前为第1页。一、实验教学目标与基本要求使学生熟练地掌握常用数据结构的基本概念、逻辑结构、存储结构及运算操作（相关算法的设计）；熟悉这些数据结构在计算机科学与技术中的基本应用；为其它相关专业课程的学习打下坚实的基础。二、本实验课程的基本理论与实验技术知识基本理论：数据的逻辑结构和物理结构之，数据结构和数据类型；数据结构基本原理、重要算法、高级语言编程。基本数据结构的概念、特点、存储结构，基本数据结构的运算及算法设计。实验技术：计算机语言的应用、相关计算机技术。三、实验方法、特点与基本要求实验必须循序渐进地进行，不能急躁冒进。很多实验内容需要的基础知识比较多，所以实验准备尤其需要下功夫，只有这样才能理清实验的目的、要求，列出实验的步骤，对可能出现的问题有充分的准备。实验前必须明确实验目的，理解实验原理；了解实验环境；了解实验方法，拟定实验的操作步骤。实验过程中需认真观察，详细记录实验结果。实验后通过对实验记录的整理，从理论上加以分析归纳，以加深对所学理论知识的理解，不断总结、积累经验，从而提高动手能力。上机操作，要求独立完成全部实验作业，并与实验课结束前提交。四、实验主要仪器设备1.服务器：MS-WindowsNT/2000；2.数据库：MS-SQLServer、Access等；3.软件：Ｃ语言等；五、实验项目的设置与内容提要序号实验项目内容提要实验类型每组人数实验要求1线性表操作链表的插入和删除综合1必做2栈和队列的应用栈、队的实现和运算综合1必做3树和图操作、查找和排序操作树的遍历、图的存储算法、查找和排序算法验证1选做实验设置：（共8个，其中链表的插入和删除操作是必做，其它可选）。必做实验必须提交实验报告，可选实验可以提交实验报告，实验报告的形式由上课教师制定。实验1：顺序表基本操作一、实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。数据结构实验指导书全文共10页，当前为第2页。数据结构实验指导书全文共10页，当前为第2页。3.掌握对多函数程序的输入、编辑、调试和运行过程。二、实验要求1．预习C语言中结构体的定义与基本操作方法。2．对顺序表的每个基本操作用单独的函数实现。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三、实验内容：1．编写程序实现顺序表的下列基本操作：(1)初始化顺序表La。(2)将La置为空表。(3)销毁La。(4)在La中插入一个新的元素。(5)删除La中的某一元素。(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。(7)打印输出La中的元素值。2．编写程序完成下面的操作：(1)构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=A∪B。四、思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A∩B？实验2：单链表基本操作一、实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。二、实验要求1．预习C语言中结构体的定义与基本操作方法。2．对单链表的每个基本操作用单独的函数实现。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。数据结构实验指导书全文共10页，当前为第3页。数据结构实验指导书全文共10页，当前为第3页。1．编写程序完成单链表的下列基本操作：(1)初始化单链表La。(2)在La中插入一个新结点。(3)删除La中的某一个结点。(4)在La中查找某结点并返回其位置。(5)打印输出La中的结点元素值。2.构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。）四、思考与提高1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？实验3：顺序栈基本操作一、实验目的1．熟悉并能实现栈的定义和基本操作。2．了解和掌握栈在递归和非递归算法的应用。二、实验要求1．进行栈的基本操作时要注意栈“后进先出”的特性。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。数据结构实验指导书全文共10页，当前为第4页。（2数据结构实验指导书全文共10页，当前为第4页。（3）若是其它字符，则返回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：voidinitstack()：初始化堆栈intMake_str()：语法检查并计算intpush_operate(intoperate)：将操作码压入堆栈intpush_num(doublenum)：将操作数压入堆栈intprocede(intoperate)：处理操作码intchange_opnd(intoperate)：将字符型操作码转换成优先级intpush_opnd(intoperate)：将操作码压入堆栈intpop_opnd()：将操作码弹出堆栈intcaculate(intcur_opnd)：简单计算+，-，*，/doublepop_num()：弹出操作数3.已知函数t(n)=2*t(n/2)+n其中t(0)=0，n为整数。编写程序实现：(1)计算t(n)的递归算法。(2)用链式栈实现计算t(n)的非递归算法。四、思考与提高1．如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？2．栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？3.在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？

实验4:顺序循环队列基本操作一、实验目的1．熟悉并能实现顺序循环队列的定义和基本操作。2．了解用队列解决实际应用问题。二、实验要求1．进行队列的基本操作时要注意队列“先进先出”的特性。2．复习关于栈操作的基础知识。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三、实验内容数据结构实验指导书全文共10页，当前为第5页。1．任意输入队列长度和队列中的元素值，构造一个顺序循环队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作数据结构实验指导书全文共10页，当前为第5页。2．约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。3．(选做实验)设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。程序编写提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。四、思考与提高1．链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？2．一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？实验5：矩阵的压缩存储及相关操作一、实验目的1．掌握下三角矩阵的输入、输出、转置算法。数据结构实验指导书全文共10页，当前为第6页。数据结构实验指导书全文共10页，当前为第6页。二、实验要求1．认真阅读和掌握本实验的算法思想。 2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．所谓上（下）三角矩阵是指矩阵的下（上）三角中的元素均为常数或零的n阶矩阵。此时除了存储上（下）三角矩阵中的元素之外再加一个存储常数的空间即可。三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩到向量Sa[0……n×(n+1)/2]中，其中c存放在向量的最后一个分量中。用向量Sa[0……n×(n+1)/2]压缩存储下三角矩阵，编写程序任意输入一个下三角矩阵，对其进行转置，输出转置后的矩阵。2．用三元组顺序表压缩存储稀疏矩阵，编写程序任意输入一个稀疏矩阵，对其进行转置，输出转置后的矩阵。四、思考与提高如何计算一个三元组表表示的稀疏矩阵对角线元素之和以及两个三元组表表示的稀疏矩阵的乘积？实验6：二叉树的建立及遍历一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容数据结构实验指导书全文共10页，当前为第7页。1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度数据结构实验指导书全文共10页，当前为第7页。2.编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。四、思考与提高1．如何计算二叉链表存储的二叉树中度数为1的结点数？2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?实验7：二分查找、Hash查找算法的程序实现一、实验目的1.熟练掌握二分查找算法并能在有序表中进行查找操作。2.掌握Hash表的相关算法。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．复习顺序表及二叉树的基本操作过程。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三、实验内容1．二分查找又称为折半查找，它要求要查找的顺序表必须是有序表，即表中结点按关键字有序．并且要用顺序存储结构。基本思想是：首先将给定值key与表中中间位置记录的关键字相比较，若二者相等，则查找成功，否则根据比较的结果确定下次查找的范围是在中间记录的前半部分还是后半部分，然后在新的查找范围内进行同样的查找，如此重复下去，直到在表中找到关键字与给定值相等的记录，或者确定表中没有这样的记录。编写程序构造一个有序表La，从键盘接收一个关键字key，用二分查找法在La中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。2．编写程序实现Hash表的建立、删除、插入以及查找操作。程序应包含的主要功能函数有：数据结构实验指导书全文共10页，当前为第8页。Hash()数据结构实验指导书全文共10页