1, Problem statement

Dormitories are equivalent to the existence of home for college students in school life, and dormitories management is an important part of school logistics management. How to intuitively understand the occupancy of dormitories and the accommodation location of each student is an important topic to improve work efficiency. According to the contents of the linked list in the course of C language and data structure that we have learned, we compile dormitories management check for dormitories management personnel Inquiry software can easily meet the above requirements.
Task:

1. Prepare a dormitory management query software for the dormitory management personnel, and the program design requirements are as follows:
   • Working in an interactive way
   • Sort by keyword (name, student number, room number)
2. Query menu: (realize the following operations with binary search)
   • Search by name
   • Query by Student ID
   • Query by room number
3. Print any query result (continuous operation is allowed)

2, Outline design

2.1 overview

According to the system requirements, that is, the system has the functions of information input, display, sorting display, search, insertion, deletion, end of the program, etc., first design a detailed system flow chart, then input the source code into the program, compile and debug.
The program is divided into 10 items: input records, display records, sort and display by name, sort and display by room number, sort and display by student number, search and display by name, search and display by room number, search and display by student number, insert a record sort and display by student number and end the program.

2.2 linear table storage structure representation

typedef struct {
	char name[20];
	int num;            //Both the student number and the room number are plastic
	int room;
} stu;

typedef struct {
	int length; //Current length
	stu *elem;  //Storage base address
	int listsize;  //Currently allocated storage capacity
} linklist;

2.3 detailed design

2.3.1 system flow chart

2.3.2 three sorting methods and binary search method

2.3.2.1 bubble sorting (by name)

//Sort by name (bubble sort)
void sort1(linklist &L) { 
	int i, j;
	stu temp;
	for (i = 0; i<L.length - 1; i++)
		for (j = 0; j<L.length-1-i; j++)
			if (strcmp(L.elem[j].name, L.elem[j+1].name)>0) {
				temp = L.elem[j];
				L.elem[j] = L.elem[j+1];
				L.elem[j+1] = temp;
			}
}

2.3.2.2 sorting by half insertion (sorted by student number)

//Sort by student number (sorted by half insertion)
void sort2(linklist &L) { 
	int i, j, mid, low, high;
	stu temp;
	for (i = 1; i < L.length; i++) {
		if(L.elem[i].num<L.elem[i-1].num) {
			temp = L.elem[i];
			low = 0;
			high = i-1;
			while (low <= high) {
				mid = (low + high) / 2;
				if (temp.num < L.elem[mid].num)
					high = mid - 1;
				else
					low = mid + 1;
			}
			for (j = i - 1; j >= high+1; j--)
				L.elem[j+1]=L.elem[j];
			L.elem[high+1]=temp;
		}
	}
}

2.3.2.3 simple selection and sorting (by room number)

//Sort by room number (by simple selection)
void sort3(linklist &L) { 
	int i,j,k;
	stu temp;
	for(i=0; i<L.length-1; i++) {
		k=i;
		for(j=i+1; j<L.length; j++)
			if(L.elem[j].room<L.elem[k].room)
				k=j;
		if(k!=i){
			temp = L.elem[i];
			L.elem[i] = L.elem[k];
			L.elem[k] = temp;
		}
	}
}

2.3.2.4 binary search method (taking search by name as an example)

//Search by name from small to large (binary search)
void search1(linklist &L) { 
	if (L.length == 0) {
		printf("No student record!\n");
		Ret();
		Menu();
	} else {
		int low = 0, high = L.length, mid, flag = 0;
		printf("\n");
		printf("Search by name-->Please enter the name you want to find:");
		char a[15], ch;
		scanf("%s", a);
		while (low <= high) {
			mid = (low + high) / 2;
			if (strcmp(a, L.elem[mid].name) == 0) {
				flag = 1;
				break;
			} else if (strcmp(a, L.elem[mid].name)>0)
				low = mid + 1;
			else
				high = mid - 1;
		}
		if (flag == 1) {
			printf("Find successful-->The student information is:\n");
			printf("full name       Student number    room number\n");
			printf("%-10s %-2d %-5d\n", L.elem[mid].name, L.elem[mid].num, L.elem[mid].room);
			if (Select())
				search1(L);
			else {
				system("cls");
				Menu();
			}
		} else {
			printf("The student does not exist!");
			if (Select())    search1(L);
			else {
				system("cls");
				Menu();
			}
		}
	}
}

3, Testing and operation

3.1 system interface

3.2 list of new dormitories

3.3 sorting (taking name sorting as an example)

3.4 query (take student number query as an example)

3.5 insert student information

3.6 delete student information

4, Code implementation

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
#define N 40 //Initial allocation of linear table storage space
#define increase 10 //Allocation increment of linear table storage space
int choice;  //Define global variables
typedef struct {
	char name[20];
	int num;            //Both student number and room number are integer
	int room;
} stu;
stu stud;
typedef struct {
	int length; //Current length
	stu *elem;  //Storage base address
	int listsize;  //Currently allocated storage capacity
} linklist;

//Linear table initialization
void Init(linklist &L) { 
	L.length = 0;
	L.elem = (stu *)malloc(N * sizeof(stu));
	L.listsize = N;
}

//Operation menu
void Menu() { 
	printf( "**************************************\n" );
	printf( "***       Welcome to dormitory management system     ***\n" );
	printf( "**************************************\n" );
	printf( "*        1.  List of new dormitories            *\n" );
	printf( "*        2.  Sort dormitory information            *\n" );
	printf( "*        3.  Query dormitory information            *\n" );
	printf( "*        4.  Insert dormitory information            *\n" );
	printf( "*        5.  Delete dormitory information            *\n" );
	printf( "*        0.  Exit the system                *\n" );
	printf( "**************************************\n" );
	printf("Please enter the menu (0-5):");
	scanf("%d", &choice);
	if (choice<0 || choice>5) {
		system("cls");
		printf("Wrong number input,Please try again!\n");
		printf("\n");
		Menu();
	}

}

//Print student information
void Display(linklist &L) { 
	int i;
	printf("full name       Student number    room number\n");
	for (i = 0; i<L.length; i++)
		printf("%-10s %-2d %5d\n", L.elem[i].name, L.elem[i].num, L.elem[i].room);
}

//Return to the main interface
void Ret() {    
	char c;
	fflush(stdin);
	printf("\n");
	printf("Please press any key to enter the main interface:");
	scanf("%c", &c);
	system("cls");
}

//Create student information table
void Create(linklist &L) { 
	if (L.length >= L.listsize) { //Determine whether the number of students exceeds the initial value, and if so, reallocate them
		stu *newbase;
		newbase = (stu*)realloc(L.elem, (N + increase) * sizeof(stu));
		L.elem = newbase;
		L.listsize += increase;
	}
	int i = 2;
	char ch;
	printf("********Start creating student information**********\n");
	printf("\n");
	printf("Please enter the information of the first student\n");
	printf("Please enter a name:");
	fflush(stdin);      // Clear the input buffer to get the correct input data
	gets(stud.name);    //Enter a line of string (name)
	printf("Please enter student ID:");
	scanf("%d", &stud.num);
	printf("Please enter the room number:");
	scanf("%d", &stud.room);
	ch = getchar();
	strcpy(L.elem[L.length].name, stud.name);
	L.elem[L.length].num = stud.num;
	L.elem[L.length].room = stud.room;
	L.length++;
	printf("\n");
	printf("Continue to input?<y/n>:");
	scanf("%c", &ch);
	printf("\n");
	while (ch == 'y') {
		printf("Please enter the%d Student information\n", i);
		printf("Please enter a name:");
		fflush(stdin);      // Clear the input buffer to get the correct input data
		gets(stud.name);    //Enter a line of string (name)
		printf("Please enter student ID:");
		scanf("%d", &stud.num);
		printf("Please enter the room number:");
		scanf("%d", &stud.room);
		strcpy(L.elem[L.length].name, stud.name);
		L.elem[L.length].num = stud.num;
		L.elem[L.length].room = stud.room;
		i++;
		L.length=i-1;
		ch = getchar();
		printf("\n");
		printf("Continue to input?<y/n>:");
		scanf("%c", &ch);
		printf("\n");
	}
	if (ch == 'n')
		system("cls");
}

//Sort by name (bubble sort)
void sort1(linklist &L) { 
	int i, j;
	stu temp;
	for (i = 0; i<L.length - 1; i++)
		for (j = 0; j<L.length-1-i; j++)
			if (strcmp(L.elem[j].name, L.elem[j+1].name)>0) {
				temp = L.elem[j];
				L.elem[j] = L.elem[j+1];
				L.elem[j+1] = temp;
			}
}

//Sort by student number (sort by half insertion)
void sort2(linklist &L) { 
	int i, j, mid, low, high;
	stu temp;
	for (i = 1; i < L.length; i++) {
		if(L.elem[i].num<L.elem[i-1].num) {
			temp = L.elem[i];
			low = 0;
			high = i-1;
			while (low <= high) {
				mid = (low + high) / 2;
				if (temp.num < L.elem[mid].num)
					high = mid - 1;
				else
					low = mid + 1;
			}
			for (j = i - 1; j >= high+1; j--)
				L.elem[j+1]=L.elem[j];
			L.elem[high+1]=temp;
		}
	}
}

//Sort by room number (by simple selection)
void sort3(linklist &L) { 
	int i,j,k;
	stu temp;
	for(i=0; i<L.length-1; i++) {
		k=i;
		for(j=i+1; j<L.length; j++)
			if(L.elem[j].room<L.elem[k].room)
				k=j;
		if(k!=i){
			temp = L.elem[i];
			L.elem[i] = L.elem[k];
			L.elem[k] = temp;
		}
	}
}
//Sorting function
void Sort(linklist &L) { 
	int c;
	printf("Please enter the sorting method (1: sort by name, 2: sort by student number, 3: sort by room number):");
	scanf("%d", &c);
	switch (c) {
		case 1:
			sort1(L);
			if (L.length == 0) {
				printf("No student record!\n");
				Ret();
				Menu();
			} else {
				printf("Sort by name:\n");
				Display(L);
				Ret();  //Call back to main interface
				Menu();
			}
			break;
		case 2:
			sort2(L);
			if (L.length == 0) {
				printf("No student record!\n");
				Ret();
				Menu();
			} else {
				printf("Sort by student number:\n");
				Display(L);
				Ret();  //Call back to main interface
				Menu();
			}
			break;
		case 3:
			sort3(L);
			if (L.length == 0) {
				printf("No student record!\n");
				Ret();
				Menu();
			} else {
				printf("Sort by room number:\n");
				Display(L);
				Ret();  //Call back to main interface
				Menu();
			}
			break;
		default:
			break;
	}
}

//Choose whether to continue searching
int Select() { 
	char ch;
	scanf("%c", &ch);
	printf("Continue to find?<y/n>:");
	fflush(stdin);
	scanf("%c", &ch);
	if (ch == 'y') {
		system("cls");
		return 1;
	} else
		return 0;
}

//Search by name from small to large (binary search)
void search1(linklist &L) { 
	if (L.length == 0) {
		printf("No student record!\n");
		Ret();
		Menu();
	} else {
		int low = 0, high = L.length, mid, flag = 0;
		printf("\n");
		printf("Search by name-->Please enter the name you want to find:");
		char a[15], ch;
		scanf("%s", a);
		while (low <= high) {
			mid = (low + high) / 2;
			if (strcmp(a, L.elem[mid].name) == 0) {
				flag = 1;
				break;
			} else if (strcmp(a, L.elem[mid].name)>0)
				low = mid + 1;
			else
				high = mid - 1;
		}
		if (flag == 1) {
			printf("Find successful-->The student information is:\n");
			printf("full name       Student number    room number\n");
			printf("%-10s %-2d %-5d\n", L.elem[mid].name, L.elem[mid].num, L.elem[mid].room);
			if (Select())
				search1(L);
			else {
				system("cls");
				Menu();
			}
		} else {
			printf("The student does not exist!");
			if (Select())    search1(L);
			else {
				system("cls");
				Menu();
			}
		}
	}
}

//Search by student number from small to large (binary search)
void search2(linklist &L) { 
	if (L.length == 0) {
		printf("\n");
		printf("No student record!\n");
		Ret();
		Menu();
	} else {
		int low = 0, high = L.length, mid, flag = 0;
		int n;
		char ch;
		printf("\n");
		printf("Search by Student ID-->Please enter the student number to find:");
		scanf("%d", &n);
		while (low <= high) {
			mid = (low + high) / 2;
			if (n == L.elem[mid].num) {
				flag = 1;
				break;
			} else if (n>L.elem[mid].num)
				low = mid + 1;
			else
				high = mid - 1;
		}
		if (flag == 1) {
			printf("Find successful----->The student information is:\n");
			printf("full name       Student number    room number\n");
			printf("%-1s0 %-2d %-5d\n", L.elem[mid].name, L.elem[mid].num, L.elem[mid].room);
			if (Select())
				search2(L);
			else {
				system("cls");
				Menu();
			}
		} else {
			printf("The student does not exist!");
			if (Select())
				search2(L);
			else {
				system("cls");
				Menu();
			}
		}
	}
}

//Search by room number from small to large (binary search)
void search3(linklist &L) { 
	if (L.length == 0) { //The function is: return to the main interface
		printf("\n");
		printf("No student record!\n");
		Ret();
		Menu();
	} else {
		int low = 0, high = L.length, mid, flag = 0;//Flag is used as the flag. If it is 1, it means the search is successful. Otherwise, there is no student to be searched
		int m;
		char ch;
		printf("\n");
		printf("Search by room number-->Please enter the room number to find:");
		scanf("%d", &m);
		while (low <= high) {
			mid = (low + high) / 2;
			if (m == L.elem[mid].room) {
				flag = 1;
				break;
			} else if (m>L.elem[mid].room)
				low = mid + 1;
			else
				high = mid - 1;
		}
		if (flag == 1) {
			printf("Find successful-->The student information is:\n");
			printf("full name       Student number    room number\n");
			printf("%-10s %-2d %-5d\n", L.elem[mid].name, L.elem[mid].num, L.elem[mid].room);
			if (Select())    //Call judgment function 1
				search3(L);
			else {
				system("cls");
				Menu();
			}
		} else {
			printf("The student does not exist!");
			if (Select())  //Call judgment function 2
				search3(L);
			else {
				system("cls");
				Menu();
			}
		}
	}
}

//Find function
void Search(linklist &L) { 
	int c;
	printf("Please enter the search method (1: search by name, 2: search by student number, 3: search by room number):");
	scanf("%d", &c);
	switch (c) {
		case 1:
			sort1(L);
			search1(L);
			break;//Advanced row binary search sort
		case 2:
			sort2(L);
			search2(L);
			break;
		case 3:
			sort3(L);
			search3(L);
			break;
		default:
			break;
	}
}

//Insert the student by student number
void Insert(linklist &L) { 
	int i, j, k;
	char ch;
	printf("\n");
	printf("The inserted student information is:\n");
	printf("full name:");
	fflush(stdin);// Clear the input buffer to get the correct input data
	gets(stud.name);
	printf("Student number:");
	scanf("%d", &stud.num);
	printf("room number:");
	scanf("%d", &stud.room);
	if (L.length == 0) {
		strcpy(L.elem[L.length].name, stud.name);
		L.elem[L.length].num = stud.num;
		L.elem[L.length].room = stud.room;
	}
	for (i = 0; i<L.length; i++) {
		if (stud.num<L.elem[i].num) {
			k = i;
			for (j = L.length; j>k; j--)
				L.elem[j] = L.elem[j - 1];
			strcpy(L.elem[k].name, stud.name);
			L.elem[k].num = stud.num;
			L.elem[k].room = stud.room;
			break;
		} else {
			strcpy(L.elem[L.length].name, stud.name);
			L.elem[L.length].num = stud.num;
			L.elem[L.length].room = stud.room;
		}
	}
	L.length++;
	fflush(stdin);
	printf("\n");
	printf("Continue to insert?<y/n>:");
	scanf("%c", &ch);
	if (ch == 'y') Insert(L);
	else system("cls");
}

//Delete the student by student number
void Delete(linklist &L) { 
	int i, j, k = -1;
	char ch;
	printf("\n");
	printf("\n");
	printf("Please input the student number to delete:");
	scanf("%d", &stud.num);
	for (i = 0; i<L.length; i++) {
		if (stud.num == L.elem[i].num) {
			printf("The student's information is:\n");
			printf("full name:%s \n Student ID:%d \n Room No.:%d\n", L.elem[i].name, L.elem[i].num, L.elem[i].room);
			k = i;
			for (j = k; j<L.length - 1; j++)
				L.elem[j] = L.elem[j + 1];
			printf("Successfully deleted\n");

			break;
		}
	}
	if (i >= L.length) printf("The student does not exist\n");
	if (k >= 0)L.length--;
	fflush(stdin);
	printf("\n");
	printf("Continue to delete?<y/n>:");
	scanf("%c", &ch);
	system("cls");
	if (ch == 'y') Delete(L);
	else system("cls");
}

//Main function
int main() {  
	linklist L;    //Define linear table L
	Init(L);
	Menu();        //Call the main menu function
	while (choice != 0) {
		system("cls");
		switch (choice) {
			case 1:
				Create(L);    //Call linear table creation function
				Menu();
				break;
			case 2:
				Sort(L);
				break;//Call sort function
			case 3:
				Search(L);
				break;//Call find function to find (bisection)
			case 4:
				sort2(L);      //Call the student number sorting function
				Insert(L);        //Insert by student number sequence
				system("cls");
				printf("Inserted student information:\n");
				Display(L);
				Ret();
				Menu();
				break;
			case 5:
				Delete(L);    //Call delete function
				if (L.length == 0) {
					printf("\n");
					printf("Student record has been deleted!\n");
					Ret();
					Menu();
				} else {
					printf("Show deleted student information:\n");
					Display(L);
					Ret();
					Menu();
				}
				break;
		}
	}
}