数据结构实验

《数据结构课程实验》考核方式采用上机情况、程序质量、实习报告相结合的形式，满分为100分。1．上机情况（30%）

包括出勤情况、调试表现、是否上网、玩游戏。

2．程序质量（50%）

3．实习报告（20%）实验一线性表实验目的：本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。同学录管理系统[问题描述]

同学录管理系统一般包括通讯者结点信息的插入、查询、删除、更新以及通讯录信息的输出等功能。而通讯者的信息一般包括编号、姓名、性别、电话等项。[基本要求]利用单向链表存储结构实现通讯录的建立；通讯者信息的插入、查询、修改和删除；通讯录链表的输出功能。

[测试数据]

至少为10个数据。

[实现提示]

现假设链表结点仅含有一个数据域和一个指针域。数据域为了描述通讯者的相关信息，定义一个通讯者的结点类型：#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct{charnum[5];charname[9];charsex[3];charphone[13];}datatype;typedefstructnode{datatypedata;structnode*next;}ListNode,*LinkList;ListNode*p;LinkListhead;实验二栈与队列一、实验目的1．掌握栈及其基本操作的实现。2．掌握队列及其基本操作的实现。二、实验要求1．实验前做好充分准备，包括复习第三章所学内容，事先预习好本次实验内容。2．实验时记录实验结果，按要求完成各题。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型栈与队列2（1）顺序栈的定义及其操作算法的实现；必做设计性（2）链式队列定义及其操作算法的实现；选做设计性（3）循环队列定义及其操作算法的实现；必做设计性（4）利用栈实现进制转换选做综合性说明：（a）实验内容1）与3）为必做内容。（b）实验内容2）与4）为选做内容。四、实验内容与要求1、实验题目一：顺序栈的定义及其操作算法的实现要求：编程实现顺序栈表的类型定义及顺序表的初始化操作、入栈操作、出栈操作、取栈顶元素操作、输出操作等，并对其进行验证。2、实验题目二：链式队列的定义及其相关操作算法的实现要求：编程实现链式队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。3、实验题目三：循环队列定义及其操作算法的实现要求：编程实现循环队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。4、实验题目四：利用栈实现进制转换要求：利用栈（顺序栈或链式栈）实现进制转换问题实验三二叉树一、实验目的1．掌握二叉树的链式存储结构及其相关操作的实现。2．掌握二叉树的先序、中序、后序的递归遍历算法。3．理解二叉树的各种非递归遍历算法的实现。二、实验要求1．实验前做好充分准备，包括复习第六章所学内容，事先预习好本次实验内容。2．实验时记录实验结果，按要求完成各题。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型二叉树4（1）二叉树的创建、递归遍历及其它基本操作的实现。必做设计性（2）二叉树非递归遍历算法的实现。选做设计性（3）哈夫曼树及哈夫曼编码的算法实现。选做综合性说明：（1）实验内容1）为必做内容。（2）实验内容2）与实验内容3）为选做内容。四、实验内容与要求1、实验题目一：（1）二叉树的创建、递归遍历及其它基本操作的实现。要求：定义用二叉链表表示的二叉树，并实现二叉树的创建、遍历（先序、中序后序）的递归算法及求深度操作等，并对其进行验证。2、实验题目二：二叉树非递归遍历算法的实现要求：在题目一的基础上，实现二叉树的非递归遍历算法（先序、中序、后序或按层），并对其进行验证。3、实验题目三：哈夫曼树及哈夫曼编码的算法实现要求：编程实现哈夫曼树的创建及利用哈夫曼树求解哈夫曼编码。实验四排序一、实验目的1．掌握插入排序（直接插入排序、Shell排序）算法的实现方法。2．掌握交换排序（冒泡排序、快速排序）算法的实现方法。3．掌握选择排序（简单的选择排序、堆排序）算法的实现方法。4．掌握二路归并排序算法的实现方法。5．通过排序算法在实际应用中的运用，增强程序设计能力。二、实验要求1．实验前做好充分准备，包括复习所学内容，事先预习好本次实验内容。2．实验时记录实验结果，按要求完成各个设计题目。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型排序2（1）直接插入排序算法、Shell排序算法必做设计性（2）冒泡排序、快速排序算法必做设计性（3）简单选择排序算法、堆排序算法选做设计性（4）班级学生成绩管理（利用某种排序方法实现按某个或某些关键字排序）选做综合性四、实验内容与要求1、实验题目一：直接插入排序算法、SHELL排序算法要求：利用顺序表作为排序表，分别利用直接插入排序及Shell排序方法对其进行排序。2、实验题目二：冒泡排序、快速排序算法要求：利用顺序表作为排序表，分别利用冒泡排序与快速排序方法对其进行排序并加以验证。3、实验题目三：简单选择排序算法、堆排序算法要求：利用顺序表作为排序表，分别利用简单选择排序与堆排序方法对其进行排序