数据结构上机实验指导书.docx

《数据结构上机实验指导书.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构上机实验指导书实验指导上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。其任务是训练学生实现基本的数据结构，培养学生设计复杂程序的能力，并熟悉实验报告规范。通过实验学习，使学生能够学会分析计算机加工的数据对象的特性，以便选择合理的数据结构和存储方式，设计出相应问题的求解算法，提高分析问题和解决问题的能力。结合课程学习，安排了3个实习单元，各单元的训练重点在于基本的数据结构，而不强调面面俱到。

2、各实习单元与教科书的各章具有紧密的对应关系，在个别实习单元中安排有难度差别不等的多个实习题选做。此外，每个实习题采取了统一的格式，实验目的、实验内容、实验性质、实验要求、程序实现、程序运行情况、撰写、提交实验报告等7个部分组成。 实验一、线性表操作一、实验目的1．掌握用程序设计语言调试程序的基本方法。2．掌握线性表的基本运算，如插入、删除等。二、实验内容1．顺序表、线性链表的插入、删除、合并等操作；2．利用单向链表作为存储结构，实现一元稀疏多项式的加、减运算。三、实验性质   设计性实验。四、实验要求1．

3、C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，并简要给出算法设计小结和心得。五、程序实现写出每个操作的算法（操作过程）。六、程序运行情况写出输入数据及运行结果。七、撰写、提交实验报告及源程序清单。　实验二、栈和队列及其应用一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2、掌握队列的特点(先进先出FIFO)及基本操作，如入队、出队等，队

4、列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。二、实验内容1．利用栈，演示数制转换问题。2．利用栈，演示用算符优先法对算术表达式求值的过程。选作内容：1.地图着色问题。2.迷宫求解问题。三、实验性质   设计型实验。四、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，并简要给出算法设计小结和心得。五、程序实现写出每个操作的算法（操作过程），程序运行情况。六、写出输入数据及运行结果七、

5、撰写、提交实验报告及源程序清单。　实验三、串和数组一、实验目的1．掌握稀疏矩阵的特点(三元组存储方法)。2．掌握串的运算（赋值，比较，联结，插入子串，模式匹配……等）。二、实验内容1．用堆分配存储表示串，实现串的复制、比较、连接、求子串、串定位和串替换等基本操作。2．用三元组顺序表表示稀疏矩阵，实现两个稀疏矩阵的相加、相减和相乘运算。选作内容：简单的行编辑程序。三、实验性质   设计型实验。四、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法

6、，要求给出具体的算法分析结果，并简要给出算法设计小结和心得。五、程序实现写出每个操作的算法（操作过程）程序运行情况六、写出输入数据及运行结果（可参见教材）。七、撰写、提交实验报告及源程序清单。　实验四、二叉树一、实验目的1．进一步掌握树的结构及非线性特点，递归特点和动态性。2．进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。二、实验内容1．写一个简单的哈夫曼编码和译码系统。选作内容：1.实现二叉树的遍历，实现先序、中序和后序递归遍历算法。2.实现二叉树中序遍历的非递归算法和层

7、序遍历算法。三、实验性质   设计型实验。四、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，并简要给出算法设计小结和心得。五、程序实现写出每个操作的算法（操作过程），程序运行情况。六、写出输入数据及运行结果（可参见教材）七、撰写、提交实验报告及源程序清单。 实验五、图一、实验目的1．进一步掌握图的结构及非线性特点，递归特点和动态性。2．进一步巩固图的三种存储结构和二种遍历方法、最小生成树的两种求解算法。二、实验

8、内容1．以邻接链表为存储结构，实现图的深度优先和广度优先遍历算法。2. 设计合适的存储结构，用克鲁斯卡尔算法求网的最小生成树。选作内容1.用邻接矩阵作为存储结构，实现图的深度优先和广度优先遍历算法，并与邻接链表作为存储结构的图遍历算法进行分析比较。三、实验性质   设计型实验。四、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，并简要