数据结构
简单的员工管理系统
问题描述
每个员工的信息包括:编号,姓名,性别,出生年月,学历,职务,电话,住址。
系统功能包括:
(1) 查询:按特定条件查找员工。
(2) 修改:按编号对某个员工的某项信息进行修改。
(3) 插入:加入新员工的信息。
(4) 删除:按编号删除已离职的员工的信息。
(5) 排序:按特定条件对所有员工的信息进行排序。
算法分析与设计
选用哈希表作为数据的存取结构,哈希表构造采用除余数法,冲突处理则采用线性探测再散列法,排序采用快速排序法。
基本员工结构描述如下:
typedef struct employ{ /*员工结构描述*/
int id; /*编号*/
char name[8]; /*姓名*/
char sex[2]; /*性别(fm,m)*/
int birth_y; /*出生年(19XX)*/
int birth_m; /*出生月*/
char level[6]; /*学历*/
char duty[8]; /*职务*/
char tel[11]; /*电话*/
char add[20]; /*住址*/
}employ;
员工的编号既id作为哈希法查找的关键字
int H(int key) /*哈希函数*/
{
return key%Max;
}
查询函数:
int find_emp(employ emp[],int flag); /*查询*/
employ emp[] /*待查询哈希表*/
int flag /*查询类型*/
flag=0 无条件查询
flag=1 按编号查询
flag=2 按姓名查询
flag=3 按性别查询
flag=4 按生日查询
flag=5 按学历查询
flag=6 按职务查询
flag=7 按电话查询
使用哈希法定位员工的存储位置
修改函数:
int edit_emp(employ emp[],int edit_id); /*修改*/
employ emp[] /*待查询哈希表*/
int edit_id /*待修改员工的编号*/
使用哈希法定位待编辑员工的存储位置
插入函数:
void ins_emp(employ emp[]); /*插入*/
employ emp[] /*待查询哈希表*/
首先录入员工基本资料,然后把员工编号带入哈希函数计算出存储位置,如果冲突,采用线性探测再散列法计算新的存储位置,直到没有冲突为止。
删除函数:
int del_emp(employ emp[],int del_id); /*删除*/
employ emp[] /*待操作哈希表*/
int del_id /*待删除员工的编号*/
使用哈希法定位待删除员工的存储位置
排序函数:
int sort_emp(employ emp[],int flag); /*排序*/
employ emp[] /*待排序哈希表*/
int flag /*排序类型*/
在此排序类型flag为0既为按员工编号排序
排序采用快速排序法,具体实现函数说明如下:
int QKPass(employ emp[],int left,int right) /*一趟快速排序算法*/
对记录数组emp中的emp[left]至emp[right]部分进行一趟排序,并得到基准的位置,使得排序后的结果满足其之后(前)的记录的关键字均不小于(大于)基准记录
void QKSort(employ emp[],int left,int right) /*快速排序*/
对记录数组emp[left…right]用快速排序法进行排序
其它具体描述参见程序源代码内的注释
程
序
源
代
码
程序源文件分为两部分:
fansy.h
头文件存放所有函数的实现代码
fansy.c
程序的实现代码,须包含前头文件
/*******************************************************/
/* F.S.Studio 1999--2004 */
/* Fansy */
/* http://fansy.nease.net */
/* */
/* 员工管理系统 */
/* DEMO */
/* fansy.h */
/**************************************2004.06.06*******/
#include "string.h"
#define Max 100
#define NULL 0
typedef struct employ{ /*员工结构描述*/
int id; /*编号*/
char name[8]; /*姓名*/
char sex[2]; /*性别(fm,m)*/
int birth_y; /*出生年(19XX)*/
int birth_m; /*出生月*/
char level[6]; /*学历*/
char duty[8]; /*职务*/
char tel[11]; /*电话*/
char add[20]; /*住址*/
}employ;
int H(int key) /*哈希函数*/
{
return key%Max;
}
/*************************************************************************/
void print_emp(employ p) /*职工资料输出*/
{
printf("/nThe id is:%d",p.id);
printf("/nThe name is:%s",p.name);
printf("/nThe sex is:%s",p.sex);
printf("/nThe birth year is:%d",p.birth_y);
printf("/nThe birth month is:%d",p.birth_m);
printf("/nThe educational level is:%s",p.level);
printf("/nThe duty is:%s",p.duty);
printf("/nThe telephone number is:%s",p.tel);
printf("/nThe address is:%s",p.add);
}
/*************************************************************************/
int find_emp(employ emp[],int flag) /*查询*/
{
int i;
i=0;
switch(flag)
{
case 0: { /*无条件查询*/
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
}
i++;
}
return 1;
}
case 1: { /*按编号查询*/
int t_id,d;
printf("/nPlease input the id:");
scanf("%d",&t_id);
i=H(t_id); /*计算哈希地址*/
for(d=1;emp[i].id!=NULL;d++)
{
if(emp[i].id==t_id)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
return 1;
}
else i=H(t_id+d); /*线性探测再散列*/
}
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
case 2: { /*按姓名查询*/
char t_name[8];
int f;
printf("/nPlease input the name:");
scanf("%s",t_name);
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL&&strcmp(emp[i].name,t_name)==0)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
f=1;
}
i++;
}
if(f)
return 1;
else
{
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
}
case 3: { /*按性别查询*/
char t_sex[2];
int f;
printf("/nPlease input the sex:");
scanf("%s",t_sex);
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL&&strcmp(emp[i].sex,t_sex)==0)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
f=1;
}
i++;
}
if(f)
return 1;
else
{
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
}
case 4: { /*按生日查询*/
int t_birth_y;
int t_birth_m;
int f;
printf("/nPlease input the birthday:");
scanf("%d,%d",&t_birth_y,&t_birth_m);
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL&&(emp[i].birth_y==t_birth_y||emp[i].birth_m==t_birth_m))
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
f=1;
}
i++;
}
if(f)
return 1;
else
{
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
}
case 5: { /*按学历查询*/
char t_level[6];
int f;
printf("/nPlease input the educational level:");
scanf("%s",t_level);
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL&&strcmp(emp[i].level,t_level)==0)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
f=1;
}
i++;
}
if(f)
return 1;
else
{
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
}
case 6: { /*按职务查询*/
char t_duty[8];
int f;
printf("/nPlease input the duty:");
scanf("%s",t_duty);
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL&&strcmp(emp[i].duty,t_duty)==0)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
f=1;
}
i++;
}
if(f)
return 1;
else
{
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
}
case 7: { /*按电话查询*/
char t_tel[11];
printf("/nPlease input the telephone number:");
scanf("%s",t_tel);
while(i<Max) /*遍历哈希表*/
{
if(emp[i].id!=NULL&&strcmp(emp[i].tel,t_tel)==0)
{
print_emp(emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
return 1;
}
i++;
}
printf("/nCann't find the record!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
}
}
};
/*************************************************************************/
int edit_emp(employ emp[],int edit_id) /*修改*/
{
int i=0,d;
i=H(edit_id); /*计算哈希地址*/
for(d=1;emp[i].id!=NULL;d++)
{
if(emp[i].id==edit_id)
{ /*职工资料修改*/
printf("/nPlease input new name:");
scanf("%s",emp[i].name);
printf("/nPlease input new sex:");
scanf("%s",emp[i].sex);
printf("/nPlease input new birth year:");
scanf("%d",&emp[i].birth_y);
printf("/nPlease input new birth month:");
scanf("%d",&emp[i].birth_m);
printf("/nPlease input new educational level:");
scanf("%s",emp[i].level);
printf("/nPlease input new duty:");
scanf("%s",emp[i].duty);
printf("/nPlease input new telephone number:");
scanf("%s",emp[i].tel);
printf("/nPlease input new address:");
scanf("%s",emp[i].add);
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
return 1;
}
else i=H(edit_id+d); /*线性探测再散列*/
}
printf("/nCann't find the id!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
};
/*************************************************************************/
void ins_emp(employ emp[]) /*插入*/
{
int i,d;
employ t_emp;
printf("/nPlease input id:"); /*职工资料输入*/
scanf("%d",&t_emp.id);
printf("/nPlease input name:");
scanf("%s",t_emp.name);
printf("/nPlease input sex:");
scanf("%s",t_emp.sex);
printf("/nPlease input birth year:");
scanf("%d",&t_emp.birth_y);
printf("/nPlease input birth month:");
scanf("%d",&t_emp.birth_m);
printf("/nPlease input educational level:");
scanf("%s",t_emp.level);
printf("/nPlease input duty:");
scanf("%s",t_emp.duty);
printf("/nPlease input telephone number:");
scanf("%s",t_emp.tel);
printf("/nPlease input address:");
scanf("%s",t_emp.add);
i=H(t_emp.id); /*计算哈希地址*/
for(d=1;emp[i].id!=NULL;d++) /*查找插入位置*/
{
i=H(t_emp.id+d); /*线性探测再散列*/
}
emp[i]=t_emp; /*插入节点*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
};
/**********************************************************************/
int del_emp(employ emp[],int del_id) /*删除*/
{
int i,d;
i=H(del_id); /*计算哈希地址*/
for(d=1;emp[i].id!=NULL;d++)
{
if(emp[i].id==del_id)
{
emp[i].id=NULL; /*删除节点*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
return 1;
}
else i=H(del_id+d); /*线性探测再散列*/
}
printf("/nCann't find the id!!!/nPush any key to continue.../n"); /*未查找到*/
getch();
return 0;
};
/**********************************************************************/
int QKPass(employ emp[],int left,int right) /*一趟快速排序算法*/
{
employ x=emp[left];
while(left<right)
{
while(left<right&&emp[right].id>x.id)
right--;
if(left<right)
{
emp[left]=emp[right];
left++;
}
while(left<right&&emp[left].id<x.id)
left++;
if(left<right)
{
emp[right]=emp[left];
right--;
}
}
emp[left]=x;
return left;
}
void QKSort(employ emp[],int left,int right) /*快速排序*/
{
int pos;
if(left<right)
{
pos=QKPass(emp,left,right);
QKSort(emp,left,pos-1);
QKSort(emp,pos+1,right);
}
}
/**********************************************************************/
int sort_emp(employ emp[],int flag) /*排序*/
{
int i=0,k;
switch(flag)
{
case 0: { /*按编号排序*/
employ t_emp[Max];
for(k=0;k<Max;k++)
t_emp[k]=emp[k];
QKSort(t_emp,0,Max);
while(t_emp[i].id!=NULL) /*遍历排序表*/
{
print_emp(t_emp[i]); /*输出*/
printf("/nOperation success!!!/nPush any key to continue.../n");
getch();
i++;
}
return 1;
}
}
}
/**********************************************************************/
void read_file(){}; /*从文件读取员工信息*/
/**********************************************************************/
void write_file(){}; /*把员工信息写入文件*/
/**********************************************************************/
#include "stdio.h"
#include "fansy.h"
main()
{
employ emp[Max]; /*建立哈希表*/
int item,k;
for(k=0;k<Max;k++) /*初始化 */
emp[k].id=NULL;
for(;;)
{
clrscr();
printf("/t/t****************************************/n");
printf("/t/t** F.S.Studio 1999--2004 **/n");
printf("/t/t** Fansy **/n");
printf("/t/t** **/n");
printf("/t/t** http://fansy.nease.net **/n");
printf("/t/t****************************************/n/n/n");
printf("/t/t########################################/n");
printf("/t/t## ##/n");
printf("/t/t## 1.Inquire employee information ##/n");
printf("/t/t## 2.Edit employee information ##/n");
printf("/t/t## 3.Insert new employee ##/n");
printf("/t/t## 4.Delete employee information ##/n");
printf("/t/t## 5.Sort employee information ##/n");
printf("/t/t## ##/n");
printf("/t/t## 0.Exit... ##/n");
printf("/t/t## ##/n");
printf("/t/t########################################/n");
printf("/t/tSelect item number:");
scanf("%d",&item);
switch(item)
{
case 1:{
int sel;
printf("/t/t<< 0.No condition >>/n");
printf("/t/t<< 1.By id >>/n");
printf("/t/t<< 2.By name >>/n");
printf("/t/t<< 3.By sex >>/n");
printf("/t/t<< 4.By birthday >>/n");
printf("/t/t<< 5.By educational level >>/n");
printf("/t/t<< 6.By duty >>/n");
printf("/t/t<< 7.By telephone number >>/n");
printf("/t/tSelect item number:");
scanf("%d",&sel);
find_emp(emp,sel);
break;
}
case 2:{
int idd;
printf("/nPlease input the id which you want to edit:");
scanf("%d",&idd);
edit_emp(emp,idd);
break;
}
case 3:{
ins_emp(emp);
break;
}
case 4:{
int idd;
printf("/nPlease input the id which you want to delete:");
scanf("%d",&idd);
del_emp(emp,idd);
break;
}
case 5:{
sort_emp(emp,0);
break;
}
case 0: return 1;
}
}
}
测试结果说明
运行界面:
****************************************
** F.S.Studio 1999—2004 **
** Fansy **
** **
** http://fansy.nease.net **
****************************************
########################################
## ##
## 1.Inquire employee information ##
## 2.Edit employee information ##
## 3.Insert new employee ##
## 4.Delete employee information ##
## 5.Sort employee information ##
## ##
## 0.Exit... ##
## ##
########################################
Select item number:
插入:
Select item number:3
Please input id:1001
Please input name:fansy
Please input sex:m
Please input birth year:1984
Please input birth month:08
Please input educational level:high
Please input duty:student
Please input telephone number:83858359
Please input address:xust
Operation success!!!
Push any key to continue...
查询:
Select item number:1
<< 0.No condition >>
<< 1.By id >>
<< 2.By name >>
<< 3.By sex >>
<< 4.By birthday >>
<< 5.By educational level >>
<< 6.By duty >>
<< 7.By telephone number >>
Select item number:
继续查询:
Select item number:1
Please input the id:1001
The id is:1001
The name is:fansy
The sex is:m
The birth year is:1984
The birth month is:8
The educational level is:high
The duty is:student
The telephone number is:83858359
The address is:xust
Operation success!!!
Push any key to continue...
具体运行结果请自行操作……