一、问题引入

单链表的实现【01】：Student-Management-System 只体现了项目功能实现，未对代码部分做出说明。
故新增随笔进行补充说明代码部分。

重构代码，迭代版本：Student Mangement System(Version 2.0)

二、解决过程

基于单链表实现就离不开链表的几个重要概念：头结点、首元结点、头指针

2-1 链表概念

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等

本随笔基于单链表实现，这里重点介绍它。

? 不带附加结点（即头结点）的单链表

? 带附加结点（即头结点）的单链表

• 首元结点：指链表中存储第一个数据元素a1的结点

• 头结点：在首元结点之前附设的一个结点，其指针域指向首元结点

• 头指针：指向链表中第一个结点的指针

  若链表设有头结点，则头指针所指结点为线性表的头结点；

  若链表不设头结点，则头指针所指结点为该线性表的首元结点

? 链表增加头结点的作用如下：

(1)便于首元结点的处理增加了头结点后，首元结点的地址保存在头结点（即其“前驱” 结点）的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。

(2)便于空表和非空表的统一处理当链表不设头结点时，假设L 为单链表的头指针，它应该指向首元结点，则当单链表为长度n 为0 的空表时， L 指针为空（判定空表的条件可记为：L== NULL)。

? 为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList 与LNode* , 两者本质上是等价的。通常习惯上用LinkList 定义单链表，强调定义的是某个单链表的头指针；用LNode *定义指向单链表中任意结点的指针变量

2-2 链表实现

• 结构体定义

#define ERROR -1     // 错误
#define OK 0         // 成功
#define OVERFLOW -2  // 溢出

#define TRUE 1       // 真
#define FALSE 0      // 假

typedef struct
{
	char stu_name[10];     // 学生姓名
	char stu_sex[10];      // 学生性别
	int  stu_age;          // 学生年龄
	int  stu_id;           // 学生学号
}Student_T;

typedef Student_T ElemType;

typedef struct LNode_T
{
	ElemType data;         // 结点数据域
	struct LNode_T *next;  // 结点指针域
}LNode_T, *LinkList_T;     //LinkList_T 为指向结构体LNode_T的指针类型

• 单链表的初始化

int list_init(LinkList_T *L)
{
	// 构造一个空的单链表
	// 生成新结点作为头结点,用头指针*L(即单链表L)指向头结点
	*L = (LNode_T *)malloc(sizeof(LNode_T));
	if (NULL == *L)
		exit(OVERFLOW);
	memset(*L, 0, sizeof(LNode_T));
	(*L)->next = NULL;
	return OK;
}

• 单链表的销毁

int list_destory(LinkList_T *L)
{
	// 释放所有结点（包括头结点）空间
	LNode_T *temp;
	while (*L)
	{
		temp = *L;
		*L = (*L)->next;
		free(temp);
	}
	return OK;
}

• 单链表的查找(匹配学号查找结点)

LNode_T * list_locate(LinkList_T L, int stu_id)
{
	// p指向首元结点
	LNode_T *p = L->next;
	LNode_T *q = NULL;
	while (p != NULL)
	{
		if (stu_id == p->data.stu_id)
		{
			q = p;
			break;
		}
		p = p->next;
	}
	return q;
}

• 单链表的结点更新

int list_update(LinkList_T L, int stu_id, const char *stu_name)
{
	int result = ERROR;
	LNode_T *p_node = list_locate(L, stu_id);
	if (NULL != p_node)
	{
		strcpy(p_node->data.stu_name, stu_name);
		result = OK;
	}
	return result;
}

• 单链表的删除(匹配学号删除结点)

int list_delete(LinkList_T *L, int stu_id)
{
	// p指向头结点
	LNode_T *p;
	LNode_T *q;
	int is_found = ERROR;
	for (q = NULL, p = *L; p != NULL; q = p, p = p->next)
	{
		if (stu_id == p->data.stu_id)
		{
			q->next = p->next;
			free(p);
			is_found = OK;
			break;
		}
	}
	return is_found;
}

• 创建单链表（尾插法）

int list_create_r(LinkList_T *L, ElemType elem)
{
	// r指向头结点
	LNode_T *r = (*L);
	while (r->next != NULL)
	{
		r = r->next;
	}
	LNode_T *p = (LNode_T *)malloc(sizeof(LNode_T));
	p->data = elem;
	p->next = NULL;
	r->next = p;
	return OK;

• 单链表的遍历

int list_traverse(LinkList_T L)
{
	// p指向首元结点
	LNode_T *p;
	for (p = L->next; p != NULL; p = p->next)
	{
		printf("%d %s %s %d\n", p->data.stu_id, p->data.stu_name,
			p->data.stu_sex, p->data.stu_age);
	}
	return OK;
}

三、反思总结

单链表的实现过程，需要考虑是否附加头结点，有头结点和没有头结点的实现会有所不同

单链表的操作可以独立封装，根据具体的应用场景可以进行二次封装

四、参考引用

数据结构第二版：C语言版 【严蔚敏】 第二章 线性表（链表）