《数据结构实验.doc》由会员分享，可在线阅读，更多相关《数据结构实验.doc（48页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法（C语言描述）实验指导书 谢颂华 编武汉理工大学物理科学与技术系光电专业教研室二一年四月前 言数据结构与算法是电子信息科学与技术专业的一门学科基础课，也是一门本科生必修课。在计算机科学的各领域中，都会或多或少的用到数据结构的相关知识，学好数据结构这门课程，对从事计算机技术、电子技术及相关领域的工作人员来说是非常重要。数据结构与算法主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算
2、法的能力。数据结构与算法是一门理论和实践相结合的课程，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。目 录实验一 线性表的基本操作1实验二 栈和队列及其应用3实验三 二叉树的基本操作5实验四 内部排序的基本操作7附录：数据结构与算法实验报告格式9 参考答案 10 3实验一 线性表的基本操作【实验目的】1. 熟悉C语言的上机环境，进一步掌握C语言的结构特点。2. 掌握线性表（顺序表和链表）的顺序和链式存储结构的定义及C语言的实现。3. 掌握线性表（顺序表和链表）的建立、插入、删除、查找等基本操作。【实验内容
3、】1. 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：(1) 从键盘输入10个整数，产生顺序表，并输入结点值。(2) 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。(3) 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。(4) 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。2. 报数问题：编号为1，2，n的n个人围坐在一圆桌旁，每人持有一个正整数的编号。从第一个人开始报数
4、，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，则退席的人的编号依次为6，1，7，5，3，2，4。【实验安排】由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。建议课时安排如下：课外 6学时 ，课内2学时【实验提示】1. 采用C语言的数组类型实现线性表的顺序存储，用C语言的结构体类型定义顺序表结点：、#define ListSize 100/表空间大小可根据实际需要而定，假设为100typedef int DataType;/DataType可以是任何相应
5、的数据类型如int, float或chartypedef structDataType dataListSize;/向量data用于存放表结点int length;/当前的表长度SeqList;2. 为了方便调试及编程，可以分析题目，将整个实验分解成若干个小的函数，最后由主函数分别调用子函数即可，建议编写下列子函数： CreateList / 建立顺序表函数 PrintList / 输出顺序表函数 GetLenList / 顺序表长度函数 LocateList /顺序表的查找 InsertList / 在顺序表中插入结点函数 DeleteList / 在顺序表删除结点函数 如：/顺序表的建立：
6、void CreateList(SeqList *L,int n)int i;for (i=0;idata=ch;CreateBinTree(&(*T)-lchild );/*构造左子树 */CreateBinTree(&(*T)-rchild );/*构造右子树 */3. huffman树的构造方法(1) 给定w1,w2,.,wn, 构成F=T1,T2,.,Tn, 每个树只有一个根结点;(2) 选择两个根结点最小的二叉树,作为lchild和rchild, 构成一新的二叉树;, 直至一棵树止。4. huffman树的存储结构 typedef struct int weight;int pare
7、nt, lchild, rchild; HTNode ,*HuffmanTree; / 动态分配数组存储huffman树实验四 内部排序的基本操作【实验目的】1. 掌握排序的有关概念和特点。2. 熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。3. 关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。4. 了解各种排序方法的优缺点和适用范围。【实验内容】1. 从键盘输入上述8个整数，存放在数组quick8中，并输出值。2. 输出各种排序算法每一趟排序的结果，观察关键字次序的变化。3. 如果上述8个整数按照
8、升序输入，即k1= 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 ，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。4. 如果上述8个整数按照降序输入，即k2= 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。5. 测试各排序算法的执行时间，比较执行效率。6. 随机产生3万个数，对其进行排序，观察其结果。【实验安排】建议课时安排如下：课外 2学时 ，课内2学时【实验提示】1. 采用C语言的定义记录类型的存储结构：typedef int InfoType;#define n 10/假设的文件长度，即待排序的记录数目typedef int KeyType;/假设的关键字类型typedef struct /记录类型KeyType key;/关键字项InfoType otherinfo;/其它数据项，类型InfoType依赖于具体应用而定义 RecType;typedef Rec
