[数据结构与算法]C/C++：链表的基本操作（核心代码:分部解析中有注释的部分）

我以一个图书管理系统的题目为例

▲ 可以只看核心代码就好（分部解析中有注释的部分）

目录

一、例题题目

二、完整代码

三、分部解析（链表的各种基本操作）

1-图书信息录入（初始化、创建链表）

初始化链表

创建链表

运行结果

?

2-图书信息排序【链表排序（改变链表节点的连接顺序，实现选择插入排序）】

3-图书信息插入（链表的插入）

4-图书信息修改

5-图书信息删除（链表结点删除）

6-图书信息查找

7-图书信息统计

?8-退出系统

四、题目中的部分函数

遍历链表

得到书本实例

一、例题题目

使用链表编程实现图书信息（书名、单价）管理

功? 能：

1.图书信息录入：从键盘输入n(n<10)本书的书名和单价用于构造图书链表，然后输出所有图书信息；

2.图书信息排序：按照单价从高到低的顺序进行排序后输出图书信息；

3.图书信息插入：实现新增图书信息（图书信息插入链表后，单价排序保持降序）并输出图书信息；

4.图书信息查找：实现图书按名查找并输出结果；

5.图书信息删除：实现按书名删除图书信息后输出图书信息；

6.图书信息修改：实现按书名修改图书单价后输出图书信息；

7.图书信息统计：实现统计图书数量及图书总价并输出结果。

要? 求：1.编写函数实现各功能要求（可写一个函数用于输出图书信息）；

2.在主函数中设计一个菜单，选择相关功能后按要求输入数据并调用各函数实现；

二、完整代码（较长可以先不看，建议直接看分部解析的核心代码）

这是这道例题的完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Book {
	char name[50];
	float price;
	struct Book* next;
}Book;
void menu();
Book* initLinkList();
void createLinkList(Book* head);
void sortLnkList(Book* head);
void insetBook(Book* head);
void changeBook(Book* head);
Book* findBook(Book* head, char* name);
void countBook(Book* head);
void showList(Book* head);
Book getBook();
void deleteBook(Book* head);
int main() {
	menu();
	Book* head = initLinkList();//得到表头
	if (head == NULL) {
		printf("空间不足，初始化链表失败！\n");
		return 0;
	}
	int operationCode;
	while (1) {
		printf("\n请输入功能编号：");
		scanf("%d", &operationCode);
		switch (operationCode)
		{
		case 1://1-图书信息录入
			createLinkList(head);
			printf("\n图书信息录入完成！\n");
			showList(head);
			break;
		case 2://2-图书信息排序
			sortLnkList(head);
			showList(head);
			break;
		case 3://3-图书信息插入
			insetBook(head);
			showList(head);
			break;
		case 4://4-图书信息修改
			changeBook(head);
			break;
		case 5://5-图书信息删除
			deleteBook(head);
			break;
		case 6://6-图书信息查找
			printf("请输入您想查找的书名：");
			char name[50];
			scanf("%s", name);
			if (findBook(head, name) != NULL) {
				Book* book = findBook(head,name);
				printf("\n查找结果：%s\t\t%.2f\n", book->name, book->price);
			}
			else {
				printf("\n查无此书！\n");
			}
			break;
		case 7://7-图书信息统计
			countBook(head);
			break;
		case 8://8-退出系统
			printf("\n已退出\n");
			exit(1);
			break;
		default:
			printf("\n请输入正确的功能编号！\n");
			break;
		}
	}
	return 0;
}
void menu() {
	printf("\
	1 - 图书信息录入\n\
	2 - 图书信息排序\n\
	3 - 图书信息插入\n\
	4 - 图书信息修改\n\
	5 - 图书信息删除\n\
	6 - 图书信息查找\n\
	7 - 图书信息统计\n\
	8 - 退出系统\n");
}
Book* initLinkList() {
	Book* head = (Book*)malloc(sizeof(Book));
	if (head != NULL) {
		strcpy(head->name, "thisHead");
		head->price = 0;
		head->next = NULL;
		return head;
	}
	return NULL;
}
void insetBook(Book* head) {
	Book* p = head;
	Book* q = (Book*)malloc(sizeof(Book));
	if (q != NULL) {
		*q = getBook();
		while (p->next->price > q->price) {
			p = p->next;
			if (p->next == NULL) {
				break;
			}
		}
		q->next = p->next;
		p->next = q;
	}
	else {
		printf("空间不足！\n");
	}
}
Book getBook() {
	Book book;
	char name[50];
	float price;
	printf("请输入书名和单价，用空格也隔开:\n");
	scanf("%s%f", name, &price);
	strcpy(book.name, name);
	book.price = price;
	return book;
}
void sortLnkList(Book* head) {
	Book* inset = head,*p,*q;
	while (1) {
		if (inset->next == NULL)break;
		p = inset;
		while (1){
			if (p->next == NULL)break;
			q = p->next;
			if (q->price > inset->next->price) {
				p->next = q->next;
				q->next = inset->next;
				inset->next = q;
			}
			else {
				p = p->next;
			}
		}
		inset = inset->next;
	}
}
void showList(Book* head) {
	Book* p = head->next;
	printf("所有图书信息如下:\n书名\t\t单价\n");
	for (p; p != NULL; p = p->next) {
		printf("%s\t\t%.2f\n", p->name, p->price);
	}
}
void createLinkList(Book* head) {
	int bookNumber;
	printf("请输入图书数量:");
	scanf("%d", &bookNumber);
	for (int i = 0; i < bookNumber; i++) {
		printf("第%d本 ", i + 1);
		Book* p = (Book*)malloc(sizeof(Book));
		if (p != NULL) {
			*p = getBook();
			p->next = head->next;
			head->next = p;
		}
		else {
			printf("空间不足！\n");
		}

	}
}
Book* findBook(Book* head, char* name) {
	Book* p = head->next;
	for (p; p != NULL; p = p->next) {
		if (strcmp(p->name, name) == 0) {
			return p;
		}
	}
	return NULL;
}
void changeBook(Book* head) {
	float changePrice;
	printf("请输入您想修改图书信息的书名:");
	char name[50];
	scanf("%s", name);
	Book* p = findBook(head, name);
	if (p != NULL) {
		printf("该图书信息为:%s\t\t%.2f\n", p->name, p->price);
		printf("输入修改的单价:");
		scanf("%f", &changePrice);
		p->price = changePrice;
		printf("\n修改成功:%s\t\t%.2f\n\n", p->name, p->price);
		sortLnkList(head);
		showList(head);
	}
	else {
		printf("\n暂无该图书信息！\n");
	}
}
void deleteBook(Book* head) {
	printf("请输入要删除的图书书名：");
	char name[50];
	scanf("%s", name);
	if (findBook(head, name) != NULL) {
		Book* p = head;
		for (p->next; p->next != NULL; p = p->next) {
			if (strcmp(p->next->name, name) == 0) {
				Book* deleteTag = p->next;
				p->next = p->next->next;
				free(deleteTag);
				if (p->next == NULL)break;
			}
		}
		printf("\n删除成功！\n");
		showList(head);
	}
	else {
		printf("\n无此书！\n");
	}
}
void countBook(Book* head) {
	Book* p = head->next;
	int totalBookNumber = 0;
	float totalPrice = 0;
	for (p; p != NULL; p = p->next) {
		totalBookNumber++;
		totalPrice += p->price;
	}
	printf("\n统计结果如下：\n");
	showList(head);
	printf("图书总数量:%d\n图书总价为:%.2f\n", totalBookNumber, totalPrice);
}

三、分部解析（链表的各种基本操作）

1-图书信息录入（初始化、创建链表）

初始化链表

//先定义一个结构体用作结点
typedef struct Book {
	char name[50];
	float price;
	struct Book* next;
}Book;

Book* head = initLinkList();//得到头结点

//生成并返回一个头结点
Book* initLinkList() {
	Book* head = (Book*)malloc(sizeof(Book));//请求一块空间
	if (head != NULL) {
        //初始化头结点
		strcpy(head->name, "thisHead");//非必要
		head->price = 0;//非必要
		head->next = NULL;//必要
		return head;
	}
	else {
		printf("空间不足，初始化链表失败！\n");
		return NULL;
	}
}

创建链表

void createLinkList(Book* head) {
	int bookNumber;
	printf("请输入图书数量:");
	scanf("%d", &bookNumber);
	for (int i = 0; i < bookNumber; i++) {
		printf("第%d本 ", i + 1);
		Book* p = (Book*)malloc(sizeof(Book));
		if (p != NULL) {
			*p = getBook();//用自定义函数getBook()得到一本书的实例
			p->next = head->next;//从头插入书本结点
			head->next = p;
		}
		else {
			printf("空间不足！\n");
		}

	}
}

运行结果

2-图书信息排序【链表排序（改变链表节点的连接顺序，实现选择插入排序）】

void sortLnkList(Book* head) {
    /*inset用于定位插入位置（已排序队列的队尾）
      p用于遍历链表
      q用于临时保存p->next的地址，改变链表节点的连接顺序时得用到，q=p->next*/
	Book* inset = head,*p,*q;
	while (1) {
		if (inset->next == NULL)break;//排序完成
		p = inset;
		while (1){
			if (p->next == NULL)break;//一轮遍历结束
			q = p->next;
            /*改变链表节点的连接顺序
            每次排序都从未排序的队列中，找最大的元素，插到已排序队列（降序）的队尾*/
			if (q->price > inset->next->price) {
                /*如果发生了插入p就已被迫后移
                无需执行p = p->next;*/
				p->next = q->next;
				q->next = inset->next;
				inset->next = q;
			}
			else {
                //如果未发生插入，则要我们自己去移动指针p
				p = p->next;
			}
		}
        //始终定位在已排序队列的队尾
		inset = inset->next;
	}
}

运行结果

3-图书信息插入（链表的插入）

void insetBook(Book* head) {
	Book* p = head;//p指向表头，用于从表头开始遍历链表
	Book* q = (Book*)malloc(sizeof(Book));
	if (q != NULL) {
		*q = getBook();//用自定义函数getBook()得到一本书的实例
        //找到插入位置
		while (p->next->price > q->price) {
			p = p->next;
			if (p->next == NULL) {
				break;
			}
		}
        //进行插入
		q->next = p->next;
		p->next = q;
	}
	else {
		printf("空间不足！\n");
	}
}

运行结果

4-图书信息修改

? ? ? ? 这个比较简单就不贴代码了：

（1）先找到要修改的目标结点

（2）修改数据

运行结果

5-图书信息删除（链表结点删除）

这个我觉得挺有细节的

void deleteBook(Book* head) {
	printf("请输入要删除的图书书名：");
	char name[50];
	scanf("%s", name);
	if (findBook(head, name) != NULL) {
		Book* p = head;
		for (p->next; p->next != NULL; p = p->next) {
            //注意这里比较的是p->next而不是p
			if (strcmp(p->next->name, name) == 0) {
				Book* deleteTag = p->next;//找到要删除的目标结点用deleteTag暂存
				p->next = p->next->next;//将到要删除的目标结点移出链表
				free(deleteTag);//释放目标结点的空间，清空数据
				if (p->next == NULL)break;/*如果p是最后一个结点就跳出，
                                          不然循环体for执行p = p->next，
                                          p为空指针（p->next != NULL语句报错）*/
			}
		}
		printf("\n删除成功！\n");
		showList(head);
	}
	else {
		printf("\n无此书！\n");
	}
}

运行结果

6-图书信息查找

这个不是很难

Book* findBook(Book* head, char* name) {
	Book* p = head->next;
    //从头到尾遍历链表
	for (p; p != NULL; p = p->next) {
		if (strcmp(p->name, name) == 0) {
			return p;
		}
	}
	return NULL;
}

运行结果

7-图书信息统计

? ? ? ? 这个也比较简单，就是遍历一遍链表

运行结果

?8-退出系统

运行结果

四、题目中的部分函数

遍历链表

void showList(Book* head) {
	Book* p = head->next;
	printf("所有图书信息如下:\n书名\t\t单价\n");
	for (p; p != NULL; p = p->next) {
		printf("%s\t\t%.2f\n", p->name, p->price);
	}
}

得到书本实例

Book getBook() {
	Book book;
	char name[50];
	float price;
	printf("请输入书名和单价，用空格也隔开:\n");
	scanf("%s%f", name, &price);
	strcpy(book.name, name);
	book.price = price;
	return book;
}