数据结构实验报告.docx

数据结构实验报告
目录
数据结构实验报告 1
第1章概述 3
实验目的 3
实验内容 3
实验环境 3
第2章项目1:职工信息系统 4
实验项目 4
存储结构设计 4
项目程序结构 5
实验数据和实验结果分析 6
实验源程序 9
第3章项目2:哈夫曼编码系统 16
实验项目 16
储存结构设计 16
项目程序结构 17
实验数据和实验结果分析 18
实验源程序 20
第4章项目3:两种算法求图的最小生成树 27
实验项目 27
储存结构设计 27
程序结构设计 27
实验数据和实验结果分析 28
实验源程序 30
第5章实验小节 34
第1章概述
实验目的
“数据结构”是计算机科学与技术专业和相关专业的一门重要的专业基础课。在计算机软件类课程体系中处于承上启下的核心地位,它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法,另一方面为进一步学****其他专业课(如算法设计与分析、操作系统、软件工程等)奠定坚实的理论与实践基础。
数据结构课程主要学****线性结构、树形结构和图形结构等各种类型数据结构的逻辑特性、基本运算算法设计和应用方法。
数据结构实验的目的是通过上机实验加深对课程内容的理解,增加对各种数据结构的感性认识,提高软件设计、编写及调试程序的能力。
实验内容
我的的实验内容如下:
(1)线性结构部分:员工信息系统。
(2)树形结构部分:哈夫曼编码系统。
(3)图形结构部分:两种算法求图的最小生成树。
实验环境
我的的实验环境采用Dev-C++ 。
第2章项目1:职工信息系统
实验项目
【问题描述】从职工数据文件()中读取数据,每个职员记录包含职员编号(no),姓名(name),部门号(depno)和工资数(salary)信息,编写一个程序,完成以下功能:输入、整理员工记录,删除所有员工记录,按编号、部门号、工资数整理员工信息记录,将员工信息记录存档到职工数据文件中。
【输入】员工信息数据文件()。
【输出】经整理的员工信息。
存储结构设计
采用带头节点的单链表存储员工信息,单链表节点的类型定义如下:
struct emp{ //定义员工信息数据类型
int no;
char name[10];
int depno;
float salary;
};
typedef struct LNode //定义单链表节点类型
{ emp data;
struct LNode *next;
}LinkList;
例如,员工“acdb”。
a
c
d
b
∧
L
一个带头节点的单链表
项目程序结构
。其中各个函数的功能说明如下:
void FunctionList():说明系统功能。
void DispList(LNode *L):输出全部员工信息。
void DestroyList(LNode *&L):释放单链表并删除职工文件中的全部记录。
bool CreateList(LNode *&L):将员工信息从数据文件中读取出来并建立单链表L。
void FDispList(LNode *L):。
bool InsertEmp(LNode *&L,emp e):新建员工信息记录。
LNode *sortList(LNode *L,int kind):按编号no或部门号depno或工资数salary对所有职工记录进行递增排序。
main():首先从数据文件读入数据,再采用尾插法建立单链表,再根据用户输入的信息完成相应的功能。
项目程序结构
单链表递增快速排序sortList()算法设计
输入:单链表L,排序关键字kind
输出:L
过程如下:
当单链表多于一个元素时调用mergeSort函数
置p=L; q=L; pre=NULL;
p!=NULL&&q->next!=NULL时循环
q=q->next->next;
pre=p;
p=p->next;
置pre=NULL;
此时可以得到一个小于key的链表和大于等于key的链表;由此递归可以对两个链表分别进行快速排序:
LNode *lhalf=mergeSort(L,kind);
LNode *rhalf=merge