一、实验目的和要求
1.理解链表的逻辑结构特性,深入掌握链式存储结构;
2.掌握各种基本运算,实现存储空间动态管理;
3.解决一些实际的复杂问题。
二、实验内容
本实验采用的数据是:
typedef struct
{
int no;
char name[10];
int depno;
float salary;
}EmpType;
typedef struct node
{
EmpType data;
struct node *next;
}EmpList;
系统任务概述
链式存储方式——链表可以实现存储空间的动态管理。
在链式存储中,每个存储节点不仅包含元素本身的信息(称为数据域),而且包含有远古之间逻辑关系的信息,即一个节点中包含有后继节点的地址信息,这称为指针域,这样可以通过一个节点的指针域方便地找到后继节点的位置。
职工信息链表的主要功能就是职工信息的保存,其中包括对信息的输入、显示、修改、删除、平均工、排序等。
功能需求
ReadFile(EmpList *&L):读取emp.dat文件中所有职工记录并建立带头节点的职工单链表L;
InputEmp(EmpList *&L): 采用头插法插入节点,完成添加一个职工记录。
Display(EmpList *L): 显示单链表中L所有职工记录。
Sortno(EmpList *&L):采用直接插入法对单链表L按no递增有序排序。
Sortdepno(EmpList *&L):采用直接插入法对单链表L按depno递增有序排列。
Sortsalary(EmpList *&L):采用直接插入法对单链表L按salary递增有序排列。
DelAll(EmpList *&L):清除职工文件中全部记录并释放单链表L中除头节点外的所有节点。
SaveFile(EmpList *L):将职工单链表L中的所有数据存入到职工文件emp.dat中。
change(EmpList *&L):修改职工文件中的职工信息。
通过输入要修改的职工编号,*p扫描要找的节点,再输入新的信息。
aver(EmpList *L):求职工文件中职工的平均工资。
总体设计
详细设计
exci1.cpp文件包含如下函数:
ReadFile(EmpList *&L):读取emp.dat文件中所有职工记录并建立带头节点的职工单链表L,若存在emp.dat文件,,则采用尾插法建立单链表L,使用尾指针始终指向当前链表的尾节点,将新节点插到当前链表的表尾上;若不存在该文件,则输出“不能创建emp.dat 文件”,最后输出职工单链表的记录个数。
InputEmp(EmpList *&L):采用头插法插入节点*p,创建新的存储空间,将添加的数据存放在新结点的数据域中,然后将新节点插入到当前链表的表头,完成添加一个职工记录。
Display(EmpList *L):逐一扫描链表的每个数据节点,并显示个节点的data域值,即显示单链表中L所有职工记录。
Sortno(EmpList *&L):采用直接插入法对单链表L按no递增有序排序。
先使p指向第2个数据节点,在表中通过比较找插入*p节点的前驱节点*pre,然后在*pre节点之后插入*p节点。
然后扫描单链表L余下节点*p(直到p==NULL为止),实现递增有序排序。
Sortdepno(EmpList *&L):采用直接插入法对单链表L按depno递增有序排列。
Sortsalary(EmpList *&L):采用直接插入法对单链表L按salary递增有序排列。
DelAll(EmpList *&L):清除职工文件中全部记录并释放单链表L中除头节点外的所有节点。
先使p指向L->next,pre指向*p的前驱节点,扫描单链表L,当p!=NULL时,释放*pre节点,pre、p再同步后移一个节点,直到p==NULL时,pre指向尾结点,并释放。
此时,除头节点外单链表全部节点释放。
SaveFile(EmpList *L):将职工单链表L中的所有数据存入到职工文件emp.dat中。
可拓展功能如下:
change(EmpList *&L):修改职工文件中的职工信息。
通过输入要修改的职工编号,*p扫描要找的节点,再输入新的信息。
aver(EmpList *L):求职工文件中职工的平均工资。
E-R图
职工信息=姓名+编号+部门号+工资
三、编写程序(详见文件夹)
本实验采用顺序存储方式。
void DelAll(EmpList *&L) // 全清
void ReadFile(EmpList *&L) // 读取void SaveFile(EmpList *L) //保存
void InputEmp(EmpList *&L) //输入
void Sortno(EmpList *&L) // 排序
void Sortdepno(EmpList *&L) //排序
void Sortsalary(EmpList *&L) //排序
void Display(EmpList *L) //显示
void change(EmpList *&L) //修改
void aver(EmpList *L,float i) //求平均工资四、实验结果及分析
菜单界面
.输入1.输入职工信息
.输入2,显示职工信息
输入3,按no排序
4.输入4,按depno排序
输入5,按salary排序
输入6,修改职工信息
输入7,求职工平均工资,
输入9,全清。
.
输入0,退出。
五、实验小结
通过这次试验,我简单地了解了链表的各种运算,对单链表有了基本的认识,掌握了链表的动态存储方式,希望以后能更深入地了解单链表的更多操作。