数据结构实验指导书(1)

1、数据结构实验指导语郑州轻工业学院2016.02.20内容前言1实验01顺序表3的基本操作实验02单链表的基本操作11实验03堆栈19的基本操作实验04队列21的基本操作实验05二叉树的基本运算23实验06霍夫曼编码24实验07图26的两种存储和遍历实验08最小生成树、拓扑排序和最短路径29实验09二叉排序树的基本操作31实验10哈希表生成32实验11常见内部排序算法34附件：实验报告模板36先前的评论数据结构是计算机相关专业的核心基础课程，是编译原理、操作系统、数据库系统等系统程序和大规模应用开发的重要基础，也是许多高校研究生入学考试的专业课程之一。主要介绍了三种逻辑结构的特点：线性结构、树形

2、结构和图形结构，以及它们在计算机中的存储方法。在此基础上，介绍了一些典型算法及其时空效率分析。本课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和操作，从而训练学生设计能有效表达和简化算法的数据结构，从而提高他们的编程能力。通过学习，要求学生掌握各种数据结构的特点、存储表示和典型算法的设计思想和程序实现，并根据实际问题选择合适的数据表示和存储方案，设计简单、高效、实用的算法，为后续的课程学习和软件开发打下良好的基础。此外，本课程的学习过程也是复杂编程的训练过程。通过算法设计和计算机实践的训练，培养学生的数据抽象和编程能力。学习本课程，练习和实验是两个关键环节。学生理解算

3、法，计算机实验是最好的方法之一。因此，实验环节的质量是学生学好数据结构的关键。为了更好地配合学生的实验，实验教学是特别准备的。一、实验目的本课程的实验主要是原理与应用相结合。一方面，它能使学生更好地理解数据结构的概念以及计算机中几种常用数据结构的存储和实现方法，增强学生的实践能力；另一方面，培养学生从实际问题中抽象出相应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后的课程学习、大规模软件开发和实际工程问题的软件开发打下良好的基础。二、实验要求1.每次实验前，学生必须根据实验内容认真准备实验程序和调试所需的输入数据。2.在教师的帮助下，我们可以完成实验内容，得到正确的实验结果。3.实

4、验结束后，总结实验内容，写实验报告。4、遵守实验室的规章制度，不缺席，按时上下飞机。5.实验期间，必须完成数据结构的相关内容，不允许在网上聊天或玩游戏。如果发现上述现象，计算机资格将被取消，并从通常的结果中扣除10分。6.实验报告失败一次，扣5分。如果测试报告失败两次或两次以上，正常分数将记录为零。第三，实验环境VC 6.0或其他与c语言相关的编译环境。四.说明1.本实验所有算法中的元素类型应根据实际需要合理选择。2.实验题目中有*的要求较高，学生可以自己选择；其余为基本内容，应尽可能完成(至少70%，否则实验不合格)。3.数据结构是许多高校研究生入学考试的专业课程之一。我希望对研究生入学考试

5、感兴趣的学生能够在学习过程中注意对各种算法的理解，为研究生入学考试做一些准备4.写出实验的经验和实验中未解决的问题。5.实验程序应构建为多文件程序。对应于每个算法的函数原型声明存储在头文件*中。h，相应的函数实现存储在源文件*中。c；main()函数存储在另一个源文件中，其中包含头文件*。六.绩效评估措施1、期末考试占70分，闭卷。2、平时考评占30分。其中，实验环节占20分(实验准备、计算机、报告、验收等)。)；10分(出勤、作业、考试等。)。七.文献学1.数据结构 (C语言版)严为民等清华大学出版社2，数据结构题集 (C语言版)严为民等清华大学出版社3.数据结构与算法分析C语言描述，马克艾

6、伦维斯著，机械工业出版社，2012实验01顺序表的基本操作实验时间：2小时实验类型：计算机背景知识：序列表的插入、删除和应用。目的要求：1.掌握顺序存储结构的特点。2.掌握顺序存储结构的常用算法。实验内容：编写一个完整的程序，实现序列表的生成、插入、删除和输出等基本操作。(1)建立包含n个数据元素的序列表。(2)输出顺序表。(3)删除序列表中具有值x的节点或具有给定位置I的节点。(4)将表中的所有奇数排列在偶数之前，即奇数在表的前面，偶数在表的后面。(5)输入整数元素序列，利用有序表插入算法建立有序表。(6) *使用算法5建立两个非递减有序表A和B，并将它们合并成一个非递减有序表C(7)在主功

7、能中设计一个简单的菜单，分别对上述算法进行测试。(8) *综合培训：利用序列表实现班级学生信息管理(数据录入、插入、删除、排序、搜索等)。)。实验表明：1.请建立一个多文件程序。对应于算法1到6的函数原型声明存储在头文件SqList.h中，并且对应的函数实现存储在源文件SqList.c中；main()函数存储在另一个源文件中，它包含头文件SqList.h2.类型定义#define MAXSIZE 100 /表中元素的最大数量typedef int元素类型；/元素类型typedef结构ElemType *elem。/线性表整数长度；/表的实际长度int listsize/当前分配的存储容量SqL

8、ist。/序列表的类型名3.建立序列表时，可以使用随机函数自动生成数据。注意这个问题：1.插入和删除期间元素的移动原因、方向和顺序。2.理解函数形式和实际参数之间的传递关系。部分源代码：DS.h#包括#包括#包括#包括#定义真1#定义FALSE 0#定义好1#define ERROR 0类型定义int状态；SqList.h#ifndef SQLIST_H_INCLUDED#定义SQLIST_H_INCLUDED#包括DS . htypedef int元素类型；#定义LIST_INIT_SIZE 50typedef结构ElemType *elem。整数长度；int listsizeSqList。

9、void菜单()；状态初始化列表_ Sq(SqLiST L)；/*初始化序列表*/状态创建列表_ Sq(SqLiST L)；/*创建序列表*/void PrintList _ Sq(SqLiST L)；/*输出序列表*/状态删除列表_Sq(SqList L，int i，ElEMType e)；/*删除ith元素*/状态DeleteListX_Sq(SqList L，ElEMType x)；/*删除值为x *的元素状态调整列表_ Sq(SqLiST L)；/*奇数先于偶数*/状态顺序列表_sq(SqList L，int n)；/*插入生成增量有序表的方法*/void MergeLiST _ Sq

10、(SqLiST 1a，SqList Lb，SqLiST Lc)；/*两个非递减有序表A和B，并将其合并为一个非递减有序表C*/#endif /SQLIST_H_INCLUDEDSqList.cpp#include SqList.h void菜单()printf( t t t序列表的基本操作 n n )；Printf(ttt1。建立序列表 n ；Printf(ttt2。时间顺序表 n )；Printf(ttt3。删除ith元素 n )；Printf(ttt4。删除值为x的元素；Printf(ttt5。奇数在偶数之前 n ；Printf(ttt6。插值方法生成的增量有序表 n ；printf(tt

11、t7 .两个非递减有序表a音的唱名和Lb合并成非递减有序表)；printf(ttt0).退出 n n )；/*初始化顺序表*/状态初始化列表_Sq(SqList L)l。elem=(ElEMType *)malloc(LIST _ INIT _ SIZE * sizeof(ElEMType)；如果(！L.elem)出口(OVERFLOW).l。长度=0。L.listsize=LIST _ INIT _ SIZE返回确定；/*建立顺序表*/状态创建列表_Sq(SqList L)国际、国内；printf(请输入顺序表长度：)；scanf(% d ，n)；if(n LIST _ INIT _ SIZ

12、E INITlist _ Sq(L)printf(请输入%d个元素“，n)；对于(1=0；I n；扫描( %d ，l . elemI)；l。长度=n。返回确定；其他返回错误/*输出顺序表*/void PrintList_Sq(SqList L)国际；printf(顺序表中元素为： n )；对于(1=0；长度；printf(% d ，l . elemI)；printf( n )；/*删除第i个元素*/状态删除列表_Sq(SqList L，int i，ElemType e)ElemType *p，*q .if(i1)| |(ILl . length)返回错误p=(l . elemI-1)；e=*

13、p；q=l . elem l . length-1；(p；p=q；p)*(p-1)=* p；-长度；返回确定；/*删除值为x的元素，删除成功返回好的，删除失败返回错误*/状态DeleteListX_Sq(SqList L，ElemType x)ElemType *p，*q ./*请补充完整代码*/*奇数排在偶数之前*/状态调整列表_Sq(SqList L)ElemType *p，*q .int temp/*请补充完整代码*/*插入法生成递增有序表，有序表生成成功返回好的，失败返回错误*/状态顺序列表_sq(SqList L，int n)int i，j，x；/*x表示每次待插入的元素*/*请补充完整代码*/*两个非递减有序表A和b、并把它们合并成一个非递减有序表C*/void MergeList_Sq(SqList La，SqList Lb，SqList Lc)ElemType *pa，*pb，*pc，*pa_last，* pb _ lastpa=La.elempb=Lb.el