数据结构试验指导书

1、计算机专业实验教林数据结构（C语言描述）实验鵬辱书田军峰夏克俭编北京科技大学信息工程学院计算机系、计算机实验室二OO六年四月前言数据结构是信息工程学院计算机科学与技术系计算机专业及其他院系 相关专业的一门重要专业基础课，也是一门本科生必修课。在计算机科学的各领 域中，都会或多或少的用到数据结构的相关知识，学好数据结构这门课程，对从 事讣算机技术及相关领域的工作人员来说是非常重要，尤其对从事软件开发的工 程师来说更为重要。数据结构的某些知识和相关算法比较抽象，理解和熟练掌握有一定的难 度。学习这门课程，实验是非常重要的环节，因为通过实验能有效的理解所学的 数据结构的知识点和算法。根据北京科技大学

2、本科教学讣划（05版）规定，数 据结构这门课程共有课堂教学42学时，课内上机实验12学时，课外上机28 学时，合计80小时，实验学时占到总学时的50%,可见实验课在本门课程中的 重要性。在以前的教学过程中，同学们对实验重视不够，尤其没有很好的理解一 些重要的算法。为了帮助同学们更好的理解数据结构的知识要点和算法，根据数 据结构实验教学大纲，参考多年的教学实验实践，收集、整理并编写了这本实 验指导书，希望同学们能通过这本书的指导和上机实验，掌握数据结构及其算法。要想学好数据结构，C语言及相关计算机知识的掌握也是必不可少的。特 别是C语言中关于数组、结构和指针部分尤其要熟练掌握。本书是按照教学的章

3、节顺序安排每个实验，每个实验都有实验准备、实验 目的、实验内容、实验提示等部分组成。本书参考了计算机专业课数据结构任课教师夏克俭老师提供的实验习 题，并山夏克俭老师审定。在此感谢各位任课老师的辛苦工作和宝贵意见。山于 时间仓促，疏漏与不当之处在所难免，真诚希望得到使用本书的教师和学生的批 评指正。编者 2006年4月2路汲漫其修远兮汙将上下而求索-百度文库目录刖吕2目录3实验一顺序线性表的基本操作4实验二单链表的基本操作5实验三栈的顺序表示与实现6实验四栈的链式表示和实现6实验五 队列的顺序表示与实现8实验六队列的链式表示与实现8实验七二叉树的基本操作10实验八哈夫曼树的构造及编码实验10实验

4、九二叉排序树的基本操作11附录一：数据结构实验教学大纲12附录二：数据结构实验报告格式133实验一顺序线性表的基本操作【实验目的】1. 熟悉C语言的上机环境，进一步掌握C语言的结构特点。2. 掌握线性表的顺序存储结构的定义及C语言的实现。3. 掌握顺序线性表的建立、插入、删除、查找等基本操作。【实验内容】把从键盘输入的n个整数以顺序存储的方式建立一个线性表，然后输出该表 及该表的长度；删除笫m个结点后重新输出该表及长度；在表中的第k个结点 后插入2个结点后重新输出该表。【实验安排】由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。 建议课时安排如下：课外6学时，课内2学时【实验

5、提示】1. 采用C语言的数组类型实现线性表的顺序存储，用C语言的结构体类型 定义顺序表结点：、#define MAXSIZE 10typedef int elemtype; 线性表中存放整形元素typedef struct elemtype vecMAXSIZE;int len; sequenList;2. 为了方便调试及编程，可以分析题目，将整个实验分解成若干个小的函 数，最后由主函数分别调用子函数即可，建议编写下列子函数：CreateList/建立顺序表函数Print Li st输出顺序表函数GetLenList/顺序表长度函数Insert/在顺序表中插入结点函数Delete/在顺序表删除

6、结点函数3. 进行实验结果测试时，要注意分别对头结点、尾结点及空表分别进行测 试，另外要对满表进行测试，看是否有溢出情况发生。实验二单链表的基本操作【实验目的】I. 掌握单链表的链式存储结构的定义及c语言的实现。3. 掌握单链表的建立、插入、删除、查找、合并等基本操作。【实验内容】分别把从键盘输入的nl个整数和n2个整数以链式存储的方式建立两个单链 表，然后输出两表及两表的长度；删除第1个链中的笫m个结点后后重新输出 该表及长度；在第2表中的第k个结点后插入2个结点后重新输出该表；最后将 两个表合并后重新输出新表及长度，最后输出相邻两结点data值之和为最大的 第一结点。【实验安排】建议课时安

7、排如下：课外4学时，课内2学时【实验提示】1. 采用C语言的定义表结点如下：typedef int elemtype;typedef struct elemtype data; /数据域struct node *next; 指针域 linkList;2. 为了方便调试及编程，可以分析题目，将整个实验分解成若干个小的函 数，最后由主函数分别调用子函数即可，建议编写下列子函数：CreateList/建立表函数Print Li st/输出表函数GetLenList/求表长度函数Insert插入结点函数Delete删除结点函数MergeList合并表函数Adjmax(L)求值函数3. 进行实验结果测试

8、时，要注意分别对头结点、尾结点及空表分别进行测试。实验三栈的顺序表示与实现【实验目的】掌握栈的顺序表示和实现。【实验内容】编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序, 完成如下功能：1. 初始化顺序栈2. 插入元素3. 删除栈顶运算4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】采用C语言的定义顺序栈的存储结构：typedef struct elemtype stackMAXNUM;int top ; sequenStack;实验四栈的链式表示和实现【实验目的】 掌握栈的链式表示和实现。【实验内容】编写一个程

9、序实现链栈的下列各种基本运算:1. 初始化链栈2. 链栈置空3. 入栈4. 出栈5. 取栈顶元素6. 遍历链栈并在此基础上编写实现算术表达式求值程序(栈的运用)：设操作数：0, 1, 2,，8, 9 (可扩充)；运算符：+，*,/,(,),#(#号为结束)。输入中缀表达式，如：5+(42)*3#,将其转换成后缀表达式：5423*+#, 然后计算，本例结果为11。程序结构：类型说明；Clearstack(S)、Emptystack(S)、Push(S)、Pop(S)； 中缀到后缀转换的函数：Mid-post(En, Bn)； 后缀表达式求值的函数：Postcount(Bn)； main ()变量

10、说明；输入中缀表达式，存入En； 调用 Mid-post(E, B)； 调用 Postcount(B)； 打印表达式结果；Y 继续？! N停止【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】采用C语言的定义链栈的存储结构:typedef int elemtype;typedef struct elemtype data;Stacknode *next; stacknode;实验五队列的顺序表示与实现【实验目的】掌握队列的顺序表示和实现。【实验内容】编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程 序，完成如下功能：1. 初始化队列2. 建立顺序队列3. 入队4.

11、 出队5. 判断队列是否为空6. 取队列头元素7. 遍历队列【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】1. 采用C语言的定义顺序队列的存储结构：typedef struct elemtype suqueueMAXNUM;int front ;int rear; sequenStack;2. 注意：当头尾指针相等时，队列为空；在非空队列里，队头指针始终指 向队头元素，队尾指针指向队列的下一元素位置。实验六队列的链式表示与实现【实验LJ的】掌握队列的链式表示和实现。【实验内容】编写一个程序实现链队的各种基本运算：1. 初始化队列2. 建立链队列3. 入队4. 出队5. 判断队

12、列是否为空6. 取队列头元素7. 遍历链队列最后编写一个主程序，实现如下的图的过程:【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】1. 采用C语言的定义顺序队列的存储结构: typedef struct Qnode elemtype type data;Stiuct Qnode *next;JQnodetype;132. 为了方便实现，可以使用头结点。实验七【实验目的】1. 掌握二叉树的链式存储结构及实现方法。2. 掌握二叉树的遍历方法。3. 掌握二叉树中插入结点、删除结点的方法。4. 掌握二叉树的结点个数、叶子结点个数和树的深度的汁算方法。【实验内容】用键盘输入一字符串，按

13、照满二义树的特点生成一颗二义树，并将该二义树 分别用先序、中序和后序的方法遍历并输出遍历结果，然后输出该树的深度。【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】1. 采用C语言的定义树的存储结构：typedef struct btnode char data;struct btnode *lchild, *rchild bitree;2. 可以考虑釆用递归的方法先创建根结点，然后分别创建左右子树。在创 建二叉树的过程中，要注意结点数是根据输入的字符确定的。实验八哈夫曼树的构造及编码实验【实验目的】掌握哈夫曼树的构造方法及其编码方法。【实验内容】设电文字符集D及各字符出现的概率

14、F如下：D=a, b, c, d, e, f, g, h）（字符数 n=8）F=5, 29, 7, 8, 14, 23, 3, 11）（%）编写完成下列功能的程序： 构造关于F的Huffman树； 求出并打印D总各字符的Huffman编码。【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】在哈夫曼树编码时，一般令左分支为0,右分支为1,然后对哈夫曼树进行遍 历，输出哈夫曼编码。实验九二叉排序树的基本操作【实验目的】 掌握二义排序树的构造方法。【实验内容】设英文句子：“everyone round you can hear you when you speak.”，试编写完 成下面

15、任务的程序。（1）依次读入句中各单词，构造一棵二义排序树；（2）按LDR遍历此二叉排序树。LDR： can everyone hear round speak when you （有序）【实验安排】建议课时安排如下：课外2学时，课内1学时【实验提示】若遍历二义排序树的结果序列无序，则说明构树时发生错误。附录一：数据结构实验教学大纲课程名称：数据结构课程总学时：54课程编号：050414上机学时：12面向专业对象：计算机系本科生实验类别：专业课实验实验地点：计算机实验室实验教学的目的数据结构是计算机软件的专业基础课，与之配套的上机实验是体现理论联 系实际的重要环节。通过本实验课，学生可以将课堂、书本上所学到的软件理论、 技术与方法运用到实验任务的题目中。其目的之一是为后继课程（如“操作系统”、 “编译系统”、“数据库原理”等）的学习打下良好的基础；其二是提高学生独立 承担编程任务的能力与水平。实验教学的基本要求了解各种类型的“数据元素”、“数据结构”的描述及存储方法；将一些重要的算 法转换成c语言程疗;实现。要求将布置的程序题调试成功、在计算机上正确运 行。鼓励学生编程独创性的发挥。实验教材数据结构+算法（国防工业出版社）