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去评论区留言，我会及时回复