线性表的链式存储结构：定义、单链表存储结构、给链表头结点分配空间、初始化链表数据、输出链表、在某个位置上插入数据、头插法、尾插法、删除某个位置上的数据、删除某个数据、删除整个链表计算链表的长度

1、线性表链式存储结构定义
1.1特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
1.2为了表示每个数据ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们吧存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
1.3链表中第一个结点的存储位置叫做头指针；线性表的最后一个结点指针为空（通常用符号NULL或“^”表示）。
1.4在单链表的第一个结点前附设一个结点，称为头结点。

2、头指针与头结点的异同
2.1头指针
（1）头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
（2）头指针具有标识作用，所以常用头指针冠以链表的名字；
（3）无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
2.2头结点
（1）头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可以存放链表的长度）；
（2）有了头结点，对在第一个元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了；
（3）头结点不一定是链表必须要素。

3、功能实现代码
（1）线性表的单链表存储结构

typedef struct Node
{/*线性表的单链表存储结构*/
	ElenType data;
	struct Node *next;
}Node;
typedef struct Node *LinkList;/*定义指针*/

（2）线性表的初始化：分配空间
L为二级指针，通过此操作来给头结点分配空间。

void Initialize(LinkList *L)
{/*初始化链表指针：分配空间*/
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
}

（3）输出链表中的数据
A. P指向头结点之后的存储数据的结点p = L->next;
B. 判断头结点的下一个结点是否为空，若为空则输出“链表为空！”的信息；
C. 若不为空，则遍历输出数据，printf("%d ", p->data); p = p->next;直到结点为空时退出循环。

void Display(LinkList L)
{/*输出链表中的数据*/
	LinkList p = L->next;
	if (!p)
		printf("链表为空！\n");
	else
	{
		while (p)
		{
			printf("%d  ", p->data);
			p = p->next;
		}
		putchar('\n');
	}
}

（4）初始化链表：输入初始化的数据
A. P指向链表头结点L ，p = L;
B. 输入需要创建的数据个数；
C. 给结点q分配空间q = (LinkList)malloc(sizeof(Node));
D. 输入数据，然后结点p的指针指向结点q，结点p再更新指向结点q，p->next = q; p = p->next;
E. 循环创建结点，直到j>i时退出循环；
F. 将最后一个结点的指针置空p->next = NULL;

void create(LinkList L)
{/*初始化链表：输入初始化的数据*/
	int i,j=1;
	LinkList p, q;
	p = L;
	printf("请输入需要初始化的数据个数：");
	scanf_s("%d", &i);
	while (j <= i)
	{
		q = (LinkList)malloc(sizeof(Node)); 
		printf("请输入第%d个数据：",j);
		scanf_s("%d", &q->data);
		p->next = q;
		p = p->next;
		j++;
	}
	p->next = NULL;
}

（5）插入数据：在某个位置插入数据
A. 指针p指向链表头结点，p = L;
B. 遍历寻找需要插入位置的前一个位置p = p->next;，当查找到该位置或者不存在该位置时退出循环；
C. 如果插入位置之前的位置为空或者不存在该位置，则返回ERROR；
D. 否则给结点q分配空间，输入数据，q = (LinkList)malloc(sizeof(Node)); q->data = e;
E. 将结点q的指针置指向插入位置的那一个结点q->next = p->next;使得结点q取代这一个位置；
F. 插入位置前一个结点的指针指向结点q，p->next = q;

int InsertionLocation(LinkList L, int i,ElenType e)
{/*插入数据：在某个位置插入数据*/
	int j=1;
	LinkList q, p;
	p = L;
	while (p&&j < i)
	{/*寻找需要插入的位置*/
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	q = (LinkList)malloc(sizeof(Node));
	q->data = e;
	q->next = p->next;
	p->next = q;
	return OK;
}

（6）插入数据：头插法
A. 指针p指向链表头结点L；
B. 创建新的结点q = (LinkList)malloc(sizeof(Node));
C. 将插入数据赋予新的结点q->data = e;
D. 新结点的指针指向头结点之后的第一个结点q->next = p->next;
E. 头结点指向新的结点p->next = q;

void InsertionHead(LinkList L,ElenType e)
{/*插入数据：头插法*/
	LinkList p = L, q;
	q = (LinkList)malloc(sizeof(Node));
	q->data = e;
	q->next = p->next;
	p->next = q;
}

（7）插入数据：尾插法
A. 指针p指向链表头结点L；
B. 遍历结点p的下一个结点是否为空p = p->next;当为空时退出循环；
C. 创建新的结点q = (LinkList)malloc(sizeof(Node));
D. 将插入数据赋予新的结点q->data = e;
E. 将q的指针置空q->next = NULL;
F. 最后一个结点的指针指向新节点q，p->next = q;

void InsertionTail(LinkList L, ElenType e)
{/*插入数据：尾插法*/
	LinkList p=L, q;
	while (p->next)
		p = p->next;
	q = (LinkList)malloc(sizeof(Node));
	q->data = e;
	q->next = NULL;
	p->next = q;
}

（8）删除数据：删除某个位置上的数据
A. 指针p指向链表头结点L；
B. 遍历寻找需要删除的结点之前的那个结点p = p->next;直到找到该结点或者不存在这个结点时退出循环；
C. 如果不存在删除节点则返回ERROR；
D. 否则，结点q指向待删除的结点q = p->next;
E. 待删除结点前面的结点的指针指向待删除结点后面的那一个结点p->next = q->next;
F. 释放待删除结点的空间free(q);

int DeleteLocation(LinkList *L, int i)
{/*删除某个位置上的数据*/
	LinkList q, p = *L;
	int j = 1;
	while (j++ < i && p)
		p = p->next;
	if (j > i + 1 || !p)
		return ERROR;
	q = p->next;
	p->next = q->next;
	free(q);
	return OK;
}

（9）删除数据：删除某个数据——方式一

int DeleteDataOne(LinkList L, ElenType e)
{/*删除某个数据*/
	LinkList p=L , q;
	while (p->next)
	{/*结点不为空则运行*/
		if (p->next->data == e)
		{/*判断下一个结点是否符合要求*/
			q = p->next;/*q继承下一个符合要求的结点*/
			p->next = q->next;/*p指向下下个结点*/
			free(q);/*释放q的空间*/
			return OK;
		}
		p = p->next;/*若没有查找到符合要求结点，则结点后移*/
	}
	printf("不存在该数据！\n");
	return ERROR;
}

（9）删除数据：删除某个数据——方式二

int DeleteDataTwo(LinkList L, ElenType e)
{/*删除某个数据*/
	LinkList p = L, q = L->next;
	while (q)
	{
		if (q->data == e)
		{
			p->next = q->next;
			free(q);
			return OK;
		}
		p = q;
		q = q->next;
	}
	printf("不存在该数据！\n");
	return ERROR;
}

（10）删除整个链表

int ClearList(LinkList *L)
{/*删除整个链表*/
	LinkList p, q;
	p = (*L)->next;
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return OK;
}

（11）计算链表的长度

int Length(LinkList L)
{/*计算链表的长度*/
	LinkList p = L;
	int length = 0;;
	while (p->next)
	{
		length++;
		p = p->next;
	}
	return length;
}

（12）完整测试代码（编译环境Visual Studio 2017）

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef int ElenType;/*线性表中存储的数据类型*/

typedef struct Node
{/*线性表的单链表存储结构*/
	ElenType data;
	struct Node *next;
}Node;
typedef struct Node *LinkList;/*定义指针*/

void Initialize(LinkList *L)
{/*初始化链表指针：分配空间*/
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
}

void Display(LinkList L)
{/*输出链表中的数据*/
	LinkList p = L->next;
	if (!p)
		printf("链表为空！\n");
	else
	{
		while (p)
		{
			printf("%d  ", p->data);
			p = p->next;
		}
		putchar('\n');
	}
}

void create(LinkList L)
{/*初始化链表：输入初始化的数据*/
	int i,j=1;
	LinkList p, q;
	p = L;
	printf("请输入需要初始化的数据个数：");
	scanf_s("%d", &i);
	while (j <= i)
	{
		q = (LinkList)malloc(sizeof(Node)); 
		printf("请输入第%d个数据：",j);
		scanf_s("%d", &q->data);
		p->next = q;
		p = p->next;
		j++;
	}
	p->next = NULL;
}

int InsertionLocation(LinkList L, int i,ElenType e)
{/*插入数据：在某个位置插入数据*/
	int j=1;
	LinkList q, p;
	p = L;
	while (p&&j < i)
	{/*寻找需要插入的位置*/
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	q = (LinkList)malloc(sizeof(Node));
	q->data = e;
	q->next = p->next;
	p->next = q;
	return OK;
}

void InsertionHead(LinkList L,ElenType e)
{/*插入数据：头插法*/
	LinkList p = L, q;
	q = (LinkList)malloc(sizeof(Node));
	q->data = e;
	q->next = p->next;
	p->next = q;
}

void InsertionTail(LinkList L, ElenType e)
{/*插入数据：尾插法*/
	LinkList p=L, q;
	while (p->next)
		p = p->next;
	q = (LinkList)malloc(sizeof(Node));
	q->data = e;
	q->next = NULL;
	p->next = q;
}

void InsertionMenu(LinkList L)
{/*插入数据菜单*/
	int i, j,e;
	printf("请选择插入数据的方式：1、在某个位置插入数据\t2、头插法\t3：尾插法\n请选择：");
	scanf_s("%d", &i);
	switch (i)
	{
	case 1:
		printf("请输入插入的位置：");
		scanf_s("%d", &j);
		printf("请输入插入的数据：");
		scanf_s("%d", &e);
		InsertionLocation(L, j, e);
		break;
	case 2:
		printf("请输入插入的数据：");
		scanf_s("%d", &e);
		InsertionHead(L, e);
		break;
	case 3:
		printf("请输入插入的数据：");
		scanf_s("%d", &e);
		InsertionTail(L, e);
		break;
	default:
		printf("不存在该功能选项！\n");
		break;
	}
	printf("插入数据后的链表中的数据为：");
	Display(L);
}

int DeleteLocation(LinkList *L, int i)
{/*删除某个位置上的数据*/
	LinkList q, p = *L;
	int j = 1;
	while (j++ < i && p)
		p = p->next;
	if (j > i + 1 || !p)
		return ERROR;
	q = p->next;
	p->next = q->next;
	free(q);
	return OK;
}

int DeleteDataOne(LinkList L, ElenType e)
{/*删除某个数据*/
	LinkList p=L , q;
	while (p->next)
	{/*结点不为空则运行*/
		if (p->next->data == e)
		{/*判断下一个结点是否符合要求*/
			q = p->next;/*q继承下一个符合要求的结点*/
			p->next = q->next;/*p指向下下个结点*/
			free(q);/*释放q的空间*/
			return OK;
		}
		p = p->next;/*若没有查找到符合要求结点，则结点后移*/
	}
	printf("不存在该数据！\n");
	return ERROR;
}

int DeleteDataTwo(LinkList L, ElenType e)
{/*删除某个数据*/
	LinkList p = L, q = L->next;
	while (q)
	{
		if (q->data == e)
		{
			p->next = q->next;
			free(q);
			return OK;
		}
		p = q;
		q = q->next;
	}
	printf("不存在该数据！\n");
	return ERROR;
}

void DeleteMenu(LinkList L)
{/*删除结点菜单*/
	int i,j;
	printf("请选择删除结点的方式：1、删除某个位置上的数据\t2：删除某个数据—方式一\t3：删除某个数据—方式二\n请选择：");
	scanf_s("%d", &i);
	switch (i)
	{
	case 1:
		printf("请输入删除的位置：");
		scanf_s("%d", &j);
		DeleteLocation(&L, j);
		break;
	case 2:
		printf("请输入删除的数据：");
		scanf_s("%d", &j);
		DeleteDataOne(L, j);
		break;
	case 3:
		printf("请输入删除的数据：");
		scanf_s("%d", &j);
		DeleteDataTwo(L, j);
		break;
	default:
		printf("不存在该功能选项！\n");
		break;
	}
	printf("删除数据后的链表中的数据为：");
	Display(L);
}

int ClearList(LinkList *L)
{/*删除整个链表*/
	LinkList p, q;
	p = (*L)->next;
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return OK;
}

int Length(LinkList L)
{/*计算链表的长度*/
	LinkList p = L;
	int length = 0;;
	while (p->next)
	{
		length++;
		p = p->next;
	}
	return length;
}

void menu()
{/*程序菜单*/
	printf("程序的功能菜单：\n0：菜单\n1：创建链表\n2：插入数据\n3：删除结点\n4：单链表的整表删除\n5：计算链表的长度\n6：退出程序\n");
}

int main(void)
{
	int i = 0;
	LinkList L;
	while (i != 6)
	{
		switch (i)
		{
		case 0:
			menu();
			break;
		case 1:
			Initialize(&L);
			create(L);
			printf("链表中的数据为：");
			Display(L);
			break;
		case 2:
			InsertionMenu(L);
			break;
		case 3:
			DeleteMenu(L);
			break;
		case 4:
			ClearList(&L);
			Display(L);
			break;
		case 5:
			printf("链表的长度为：%d\n", Length(L));
			break;
		default:
			printf("不存在该功能选项！\n");
			break;
		}
		printf("请输入需要执行的选项：");
		scanf_s("%d", &i);
	}
	printf("感谢您的使用！\n");
	return 0;
}

运行结果图：