2023年郑州轻工业大学软件学院数据结构实验五-查找与排序(详解+源码C语言版+运行结果)
实验要求
一、实验目的
1.掌握常用的查找和排序算法思想;
2.能够用所学过的查找和排序算法解决生活中的实际应用问题。
二、课程目标
支撑课程目标(4):能够在软件开发过程中,针对特定需求综合应用数据结构、算法分析与设计等知识解决实际问题,具有积极进取、追求卓越的创新意识。
三、实验任务
设计并实现一个新冠疫苗接种信息管理系统(假设该系统面向需要接种两剂的疫苗)。要求定义一个包含接种者的身份证号、姓名、已接种了几剂疫苗、第一剂接种时间、第二剂接种时间等信息的顺序表,系统至少包含以下功能:
(1)逐个显示信息表中疫苗接种的信息;
(2)两剂疫苗接种需要间隔14~28天,输出目前满足接种第二剂疫苗的接种者信息;
(3)给定一个新增接种者的信息,插入到表中指定的位置;
(4)分别删除指定位置和给定接种者身份证号的接种者记录信息;
(5)利用直接插入排序或者折半插入排序按照身份证号进行排序;
(6)分别利用快速排序和堆排序按照第一剂接种的时间进行排序;
(7)根据身份证号进行折半查找,若查找成功,则返回此接种者的信息;
(9)为提高检索效率,要求利用利用接种者的姓氏为关键字建立哈希表,并利用链地址法处理冲突。给定接种者的身份证号或姓名,查找疫苗接种信息,并输出冲突次数和平均查找长度;
(10)提供用户菜单,方便选择执行功能。可以设计成一级或多级菜单。所有功能都可重复执行。
思路分析
数据结构
使用结构体 info 来表示个体信息,包括身份证号、姓名、接种次数以及接种日期等。
另外,使用结构体 time1 表示日期信息。
链表:
使用链表结构(Lnode)来存储 info 数据,为创建哈希表提供了支持。
哈希表:
使用哈希表,通过数组 Hash[Max] 实现,每个数组元素是一个链表,用于存储 info 数据。
使用 Hashcode 函数计算给定姓名的哈希码,从而确定数组中的索引位置。
信息显示:
?printfinfo 和 factoPrintfInfo 函数
用于显示有关接种者的信息,包括接种日期和次数。
?
排序:
使用插入排序按照身份证号对信息进行排序(insertsort)。
使用快速排序和堆排序按照第一次接种日期对信息进行排序(quicksort 和 heapsort)。
?
搜索:
使用二分搜索(halfinterval)按照身份证号搜索信息。
用户交互:
程序提供了一个用户菜单,允许用户选择不同的功能,如显示信息、添加新记录、删除记录、排序、搜索以及哈希表操作。
?
哈希表操作:
createHashTable 初始化并填充哈希表,使用链表处理碰撞。
Hashselect 在哈希表中根据姓名搜索信息。
基于菜单的程序:
程序采用基于菜单的方法,允许用户交互式地选择不同的功能。
主循环:
主函数包含一个无限循环,在其中用户可以选择菜单中的不同选项,直到决定退出程序。
源码如下所示
#define _CRT_SECURE_NO_WARNINGS 1
#include<string.h>
#include<iostream>
#include<time.h>
using namespace std;
#define max 15
#define Max 100
int cur = 9;
int Conflict = 0;
struct time1 {
int year;
int mon;
int day;
};
struct info {
long long id;
char name[10];
int count;
struct time1 tm1;
struct time1 tm2;
int time;
};
typedef struct Lnode {
struct info data;
struct Lnode* next;
}*Linklist,Lnode;
/*
输出信息方法
*/
void printfinfo(struct info info[]) {
printf("序号\t");
printf("身份证号\t");
printf("姓名 \t");
printf("接种剂数 ");
printf("第一针\t");
printf("第二针\t\n");
for (int i = 0; i <= cur; i++) {
printf("%d\t",i+1);
printf("%lld\t",info[i].id);
printf("%s\t\t",info[i].name);
printf("%d\t", info[i].count);
printf("%d/%d/%d\t", info[i].tm1.year, info[i].tm1.mon, info[i].tm1.day);
printf("%d/%d/%d\n", info[i].tm2.year, info[i].tm2.mon, info[i].tm2.day);
}
}
/*
计算时间方法
*/
void countTime(struct info(&info)[max]) {
int pyear = 2000;
for (int i = 0; i <= cur; i++) {
info[i].time = (info[i].tm1.year - pyear) * 365 + info[i].tm1.mon * 30 + info[i].tm1.day;
}
}
/*
* 显示信息表中疫苗接种的信息
*/
void factoPrintfInfo(struct info (&info)[max]) {
countTime(info);
time_t t = time(0);
int n = 0;
struct tm* curtime = localtime(&t);
int day = curtime->tm_mday;
int mon = curtime->tm_mon;
printf("序号\t");
printf("身份证号\t");
printf("姓名 \t");
printf("接种剂数\t");
printf("第一针\t");
printf("第二针\t");
for (int i = 0; i <= cur; i++) {
if (info[i].count == 1) {
if (((mon - info[i].tm1.mon) * 30 + info[i].tm1.day - day) > 14) {
printf("%d \t", ++n);
printf("%lld\t", info[i].id);
printf("%s \t", info[i].name);
printf("%d \t", info[i].count);
printf("%d%d%d\t", info[i].tm1.year, info[i].tm1.mon, info[i].tm1.day);
printf("%d%d%d\n", info[i].tm2.year, info[i].tm2.mon, info[i].tm2.day);
}
}
}
}
/*
输入信息
*/
void inputInfo(struct info& info) {
cout << "输入信息" << endl;
cout << "身份证号:"; cin >> info.id;
cout << "姓名:"; cin >> info.name;
cout << "接种次数:"; cin >> info.count;
printf("请输入日期时间值(按照yyyy/mm/dd格式)\n");
cout << "第一次:";
scanf("%d/%d/%d", &info.tm1.year, &info.tm1.mon, &info.tm1.day);
if (info.count != 1) {
cout << "第二次:";
scanf("%d/%d/%d", &info.tm2.year, &info.tm2.mon, &info.tm2.day);
}
else {
info.tm2.year = 0;
info.tm2.mon = 0;
info.tm2.day = 0;
}
}
/*
* 输出信息:BUG已修复
*/
void printfinfo1(struct info info) {
printf("身份证号\t");
printf("姓名\t");
printf("接种剂数\t");
printf(" 第一针\t");
printf("第二针\t\n");
printf("%lld\t", info.id);
printf("%s\t", info.name);
printf("%d\t\t", info.count);
printf("%d/%d/%d\t", info.tm1.year, info.tm1.mon, info.tm1.day);
printf("%d/%d/%d\n", info.tm2.year, info.tm2.mon, info.tm2.day);
}
/*
* 添加信息
*/
int addinfo(struct info(&info)[max]) {
int n = 0;
cout << "输入要插入的位置:";
cin >> n;
n--;
if (n < max - 1 && cur < max - 1)cur++;
else {
cout << "信息库满,插入失败" << endl;
return 0;
}
if (n == cur) {
inputInfo(info[n]);
}
else {
for (int i = cur; i > n; i--) {
info[i] = info[i - 1];
}
inputInfo(info[n]);
cout << "添加成功" << endl;
return 0;
}
}
/*
通过id查找信息
*/
int selectbyId(long long id, struct info info[max]) {
for (int i = 0; i <= cur; i++) {
if (info[i].id == id) {
return i + 1;
}
return -1;
}
}
/*
* 通过索引删除
*/
int deletebyindex(int n, struct info(&info)[max]) {
n--;
if (n > cur) {
cout << "没有该记录" << endl;
return 0;
}
for (int i = n; i < cur; i++) {
info[i] = info[i + 1];
}
cur--;
cout << "删除成功" << endl;
return 1;
}
/*
* 通过id删除
*/
void deletebyId(struct info(&info)[max]) {
long long id = 0;
cout << "输入要删除的身份证号:";
cin >> id;
int n = selectbyId(id, info);
deletebyindex(n, info);//待验证
}
/*
* 插入排序
*/
void insertsort(int n, struct info(&info)[max]) {
struct info temp;//中间变量
int i = 0, j = 0;
for (i = 1; i <= n; i++) {
if (info[i].id < info[i - 1].id) {
temp = info[i];
for (j = i - 1; j >= 0 && info[j].id > temp.id; j--)
{
info[j + 1] = info[j];
}
info[j + 1] = temp;
}
}
}
/*
* 判断是否前个时间大于后个时间
*/
bool istimebiger(struct time1 t1, struct time1 t2) {
if (t1.year < t2.year)
return true;
else if (t1.year > t2.year)
return false;
else {
if (t1.mon < t2.mon)
return true;
else if (t1.mon > t2.mon)
return false;
else {
if (t1.day < t2.day)
return true;
else
return false;
}
}
}
/*
* 快排
*/
void quicksort(struct info(&info)[max], int left, int right) {
struct info temp;
struct info pivot;
countTime(info);
int i, j;
if (left > right)
return;
pivot = info[left];
i = left;
j = right;
while (i < j) {
while (pivot.time >= info[i].time && i < right)
i++;
while (pivot.time < info[j].time)
j--;
if (i < j) {
temp = info[i];
info[i] = info[j];
info[j] = temp;
}
}
info[left] = info[j];
info[j] = pivot;
quicksort(info, left, j - 1);
quicksort(info, j+1, right);
}
/*
* 二分查找
*/
void halfinterval(struct info (&info)[max]) {
insertsort(cur, info);
long long target;
cout << "输入要查找的身份证号:";
cin >> target;
int left = 0,right = cur;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (info[mid].id > target) {
right = mid - 1;
}
else if (info[mid].id < target) {
left = mid + 1;
}
else
break;
}
if (left <= right) {
printf("信息如下\n");
printfinfo1(info[mid]);
}
else
printf("查无此人\n");
}
/*
* 交换函数
*/
void swap(struct info(&info)[max], int i, int j) {
struct info temp = info[i];
info[i] = info[j];
info[j] = temp;
}
/*
* 调整函数
*/
void adjust(struct info(&info)[max], int m, int n) {
int i = m;
int j = (i * 2) + 1;
while (j <= n) {
if (j + 1 <= n && info[j].time < info[j + 1].time)
j++;
if (info[i].time > info[j].time)
return;
else {
swap(info, i, j);
i = j;
j = (i * 2) + 1;
}
}
}
/*
* 堆排序
*/
void heapsort(struct info(&info)[max], int len) {
int i;
countTime(info);
for (i = len / 2 - 1; i >= 0; i--) {
adjust(info, i, len - 1);
}
for (i = len - 1; i > 0; i--) {
swap(info, 0, i);
adjust(info, 0, i - 1);
}
}
/*
* 哈希码计算
*/
int Hashcode(char n[10]) {
int code = 0;
code = abs((int)n[0]) + abs((int)n[1]);
return code % 100;
}
/*
* intiHashTable,初始化哈希表
*/
void intiHashTable(struct Lnode(&Hash)[Max]) {
for (int i = 0; i < Max; i++)
Hash[i].next = NULL;
}
/*
* 创建哈希表
*/
void createHashTable(info info[max], Lnode (&Hash)[Max]) {
intiHashTable(Hash);
int sum = 0;
for (int i = 0; i <= cur; i++) {
struct Lnode* n = (Linklist)malloc(sizeof(Lnode));
n->data = info[i];
n->next = NULL;
int code = Hashcode(info[i].name);
if (Hash[code].next == NULL) {
Hash[code].next = n;
sum++;
}
else {
int i = 1;
Conflict++;
sum += 2;
struct Lnode* n1 = (Linklist)malloc(sizeof(Lnode));
n1 = Hash[code].next;
while (n1->next != NULL) {
sum += i++;
n1 = n1->next;
}
n1->next = n;
}
}
float num = (float)sum / (cur + 1);
cout << "冲突次数:" << Conflict << endl;
cout << "平均查找长度:" << num ;
}
/*
* Hashselect,按照姓名查找
*/
void Hashselect(char str[], Lnode(&Hash)[Max]) {
int code = Hashcode(str);
if (Hash[code].next == NULL) {
cout << "未找到该姓名的接种者信息" << endl;
return;
}
struct Lnode* current = Hash[code].next;
while (current != NULL) {
if (strcmp(current->data.name, str) == 0) {
printfinfo1(current->data);
return;
}
current = current->next;
}
cout << "未找到该姓名的接种者信息" << endl;
}
/*
* 获取身份证号对应的姓名
*/
void getnamebyid(long long id, struct info info[max], char res[10]) {
for (int i = 0; i <= cur; i++) {
if (info[i].id == id) {
strcpy(res, info[i].name);
return;
}
}
// 否则无法找到该id
strcpy(res, "无法找到此id");
}
/*
* 主函数
*/
int main() {
int n = 0;
struct info info[max] = { {123123123,"输入你的姓名",2,{2020,11,11},{2021,6,8}},
{321321321,"输入你的姓名2",2,{2020,10,29},{2021,6,7}} };
struct Lnode Hash[Max];
char res[10];
long long id;
while (true) {
cout << "+++++++++++++++++++++++" << endl;
cout << "+选择功能" << endl;
cout << "+1. 显示信息" << endl;
cout << "+2. 显示可接种者信息" << endl;
cout << "+3. 新增接种者信息" << endl;
cout << "+4. 删除接种者信息" << endl;
cout << "+5. 直接插入排序信息" << endl;
cout << "+6. 快速排序和堆排序" << endl;
cout << "+7. 折半查找" << endl;
cout << "+8. 哈希表查找" << endl;
cout << "+0. 退出" << endl;
cout << "+++++++++++++++++++++++" << endl;
cin >> n;
switch (n) {
case 0:exit(0);
case 1:printfinfo(info); break;
case 2:factoPrintfInfo(info); break;
case 3:addinfo(info); break;
case 4: {
cout << "+++++++++++++++++++++" << endl;
cout << "+选择功能" << endl;
cout << "+1. 按索引删除" << endl;
cout << "+2. 按身份证号删除" << endl;
cout << "+0. 退出" << endl;
cout << "+++++++++++++++++++++" << endl;
cin >> n;
switch (n) {
case 0:exit(0);
case 1:cout << "输入要删除的位置:"; cin >> n;
deletebyindex(n, info); break;
case 2:deletebyId(info);
}break;
}
case 5:insertsort(cur, info); printfinfo(info); break;
case 6: {
cout << "+++++++++++++++++++++" << endl;
cout << "+选择功能" << endl;
cout << "+1. 快速排序" << endl;
cout << "+2. 堆排序" << endl;
cout << "+0. 退出" << endl;
cout << "+++++++++++++++++++++" << endl;
cin >> n;
switch (n) {
case 0:exit(0);
case 1:quicksort(info, 0, cur); printfinfo(info); break;
case 2:heapsort(info, cur); printfinfo(info);
}break;
}
case 7:halfinterval(info); break;
case 8: {
cout << "+++++++++++++++++++++" << endl;
cout << "+选择功能" << endl;
cout << "+1. 按姓名查找" << endl;
cout << "+2. 按身份证号查找" << endl;
cout << "+0. 退出" << endl;
cout << "+++++++++++++++++++++" << endl;
createHashTable(info, Hash);
cin >> n;
switch (n) {
case 0:exit(0);
case 1:cout << "输入要查找的姓名:"; cin >> res; Hashselect(res, Hash); break;
case 2:cout << "输入要查找的身份证号:"; cin >> id; getnamebyid(id, info, res); Hashselect(res, Hash);
}break;
}
}
}
}
实验结果
显示信息:
?
新增信息:
?
删除信息:
?
?排序展示(略,因为都是按照id升序,无需展示)
折半查找:
哈希表查找:
?最后声明!
本代码完全免费开源!请勿非法倒卖!!严查必究!有什么BUG去评论区留言,我会及时回复
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!