线性表-链式存储

由上节我们可以发现顺序存储中插入和删除的时间复杂度为O（n），存入和读取为O（1），所以它适合不经常插入和删除的场合。

优点：可以快速地存取表中任意位置的元素

缺点：插入和删除时需要移动大量的元素，容易造成存储空间的“碎片”

线性表的链式存储结构

不同于顺序存储时需要连续的存储空间，链式存储可以用任意的未被存储的存储单元存储线性表的数据元素。顺序存储时每个元素只需要存储一个位置，链式存储除了存储元素信息外，还要存储它后继元素的地址（用指针实现）。

下图为线性表的链式存储结构示意图：

一个结点由两部分组成，数据域和指针域，由名字可知分别存储数据和后继结点的地址。

链表也跟线性表相似，有头有尾，链表中的头结点称为头指针，最后一个结点的指针为空（null）。

头结点的数据域一般不存储任何信息，无论链表是否为空，头指针均不为空，头指针是 链表的必要元素。

在链表的插入过程中可以分为三种情况：头插法，尾插法和普通从中间插入的方法，根据下面的图我们来看一下程序的代码：

Status insertHead(LinkList *L, ElemType e) {
	//头插法插入元素
	Node *n = (Node*)malloc(sizeof(Node));
	n->data = e;
	if (L->data == 0) {//在链表为空的情况下，如果第一个元素的进入是头插法，那么它是目前的尾指针
		r = L;//重新初始化尾指针
		n->next = r->next;
		r->next = n;
		r = n;
	}
	else {
		n->next = L->next;
		L->next = n;
	}
	L->data++;
	return OK;
}
Status insertTail(LinkList *L, ElemType e) {
	//尾插法插入元素
	Node *n = (Node*)malloc(sizeof(Node));
	n->data = e;
	n->next = r->next;
	r->next = n;
	r = n; 
	L->data++;
	return OK;
}

下面为正常插入时的代码：

Node *n = (Node*)malloc(sizeof(Node));
		n->data = e;
		Node *p = L;
		for (int i = 1; i < position; i++) {
			p = p->next;
		}
		n->next = p->next;
		p->next = n;
		L->data++;

同样的，删除也有三种情况，我们来看一下代码：

Status deleteHead(LinkList *L, ElemType *e) {
	//删除头元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	Node *n = L->next;
	L->next = n->next;
	*e = L->data;
	free(n);
	L->data--;
	if (L->data == 0) {
		r = L;
	}
	return OK;
}

Status deleteTail(LinkList *L, ElemType *e) {
	//删除尾元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	Node *p = L;
	while (p->next != r) {
		p = p->next;
	}
	Node *n = p->next;
	p->next = n->next;
	*e = n->data;
	free(n);
	L->data--;
	r = p;
	return OK;
}

正常删除元素时如图所示：

Node *p = L;
		for (int i = 1; i < position; i++) {
			p = p->next;
		}
		Node *n = p->next;
		p->next = n->next;
		*e = n->data;
		free(n);
		L->data--;

综上：

线性表的链式存储和上节的顺序存储比较，根据时间复杂度，我们可以总结：若线性表需要频繁查找，很少进行插入和删除操作，宜采用顺序存储结构。 若需要频繁插入和删除时，宜采用链式存储结构。

下面还有实现的其他功能，我把整个代码放上来，大家可以运行理解一下！

强调一下，小编是用vs2017编译运行的，如果大家使用的编译器不一样，可以做一些修改。

#include<stdio.h>
#include<stdlib.h>
#define OK 1  //返回状态 成功
#define ERROR 0  //返回状态 失败
#define TRUE 1  
#define FALSE 0  
typedef int ElemType;
typedef int Status;
typedef struct Node {
	ElemType data;//数据域
	struct Node *next;//指针域（存储后继结点地址）
}Node, LinkList;
Node *r;//尾指针
Status init(LinkList *L) {
	//初始化
	L->data = 0;
	L->next = NULL;
	r = L;
	for (int i = 1; i <= 5; i++) {
		Node *n = (Node*)malloc(sizeof(Node));
		n->data = i;
		/*n->next = r->next;
		r->next = n;
		r = n;*/
		n->next = L->next;
		L->next = n;
		if (L->data == 0) {
			r = n;
		}
		L->data++;
	}
	return OK;
}
Status insertHead(LinkList *L, ElemType e) {
	//头插法插入元素
	Node *n = (Node*)malloc(sizeof(Node));
	n->data = e;
	if (L->data == 0) {//在链表为空的情况下，如果第一个元素的进入是头插法，那么它是目前的尾指针
		r = L;//重新初始化尾指针
		n->next = r->next;
		r->next = n;
		r = n;
	}
	else {
		n->next = L->next;
		L->next = n;
	}
	L->data++;
	return OK;
}
Status insertTail(LinkList *L, ElemType e) {
	//尾插法插入元素
	Node *n = (Node*)malloc(sizeof(Node));
	n->data = e;
	n->next = r->next;
	r->next = n;
	r = n; 
	L->data++;
	return OK;
}
Status insert(LinkList *L, int position, ElemType e) {
	//插入元素
	if (position<1 || position>L->data + 1) {
		printf("插入位置非法！\n");
		return ERROR;
	}
	if (position == 1) {
		insertHead(L, e);//头插法
	}
	else if (position == L->data + 1) {
		insertTail(L, e);//尾插法
	}
	else {//正常插入
		Node *n = (Node*)malloc(sizeof(Node));
		n->data = e;
		Node *p = L;
		for (int i = 1; i < position; i++) {
			p = p->next;
		}
		n->next = p->next;
		p->next = n;
		L->data++;
	}
	return OK;
}
Status deleteHead(LinkList *L, ElemType *e) {
	//删除头元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	Node *n = L->next;
	L->next = n->next;
	*e = L->data;
	free(n);
	L->data--;
	if (L->data == 0) {
		r = L;
	}
	return OK;
}
Status deleteTail(LinkList *L, ElemType *e) {
	//删除尾元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	Node *p = L;
	while (p->next != r) {
		p = p->next;
	}
	Node *n = p->next;
	p->next = n->next;
	*e = n->data;
	free(n);
	L->data--;
	r = p;
	return OK;
}
Status delete_L(LinkList *L, int position, ElemType *e) {
	//删除元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	if (position<1 || position>L->data) {
		printf("删除位置非法!\n");
		return ERROR;
	}
	if (position == 1) {//删头
		deleteHead(L, e);
	}
	else if (position == L->data) {//删尾
		deleteTail(L, e);
	}
	else {
		Node *p = L;
		for (int i = 1; i < position; i++) {
			p = p->next;
		}
		Node *n = p->next;
		p->next = n->next;
		*e = n->data;
		free(n);
		L->data--;
	}
	return OK;
}
Status getHead(LinkList *L, ElemType *e) {
	//获取头元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	*e = L->next->data;
	return OK;
}
Status getTail(LinkList *L, ElemType *e) {
	//获取尾元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	*e = r->data;
	return OK;
}
Status get(LinkList *L, int position, ElemType *e) {
	//获取位置所在元素
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	if (position<1 || position>L->data) {
		printf("位置非法！\n");
		return ERROR;
	}
	Node *p = L;
	for (int i = 1; i <= position; i++) {
		p = p->next;
	}
	*e = p->data;
	return OK;
}
Status get_locate(LinkList *L, ElemType e) {
	//获取元素所在位置
	int position = 0;
	if (L->data == 0) {
		printf("单链表为空!\n");
		return ERROR;
	}
	Node *p = L;
	while (1) {
		if (p == NULL) {
			printf("无此元素！\n");
			return ERROR;
		}
		if (p->data == e) {
			return position;
		}
		p = p->next;
		position++;
	}
	return OK;
}
int size(LinkList *L) {
	//获取长度
	return L->data;
}
void clear(LinkList *L) {
	//清空线性表
	if (L->data == 0) {
		printf("单链表为空!\n");
	}
	Node *p;
	while (L->next != NULL) {
		p = L->next;     //从头结点开始清空
		L->next = p->next;
		free(p);
		L->data--;
	}
	r = L;
	printf("该线性表已清空！\n");
}
Status empty(LinkList *L) {
	//判空线性表
	if (L -> data == 0) {
		return TRUE;
	}
	return FALSE;
}
void print(LinkList *L) {
	//打印线性表
	if (L->data == 0) {
		printf("[]\n");
		return;
	}
	printf("[");
	Node *p = L;
	while (1) {
		p = p->next;
		if (p->next == NULL) {
			printf("%d]", p->data);
			break;
		}
		else {
			printf("%d,", p->data);
		}
	}
	printf("\n");
}
int main()
{
	LinkList L;//创建一个头结点
	printf("----------线性表-------\n");
	printf("1、初始化操作\n");
	printf("2、插入元素\n");
	printf("3、删除元素\n");
	printf("4、获取头元素\n");
	printf("5、获取尾元素\n");
	printf("6、获取位置所在元素\n");
	printf("7、获取元素所在位置\n");
	printf("8、获取长度\n");
	printf("9、清空列表\n");
	printf("10、判空列表\n");
	printf("11、打印列表\n");
	printf("12、退出\n");
	printf("13、返回主菜单\n");
	printf("-------------------------\n");
	int choice;
	int position;
	ElemType e;
	while (1) {
		printf("请选择你想要的选项：\n");
		scanf_s("%d", &choice);
		switch (choice) {
			case 1:
				init(&L);
				break;
			case 2:
				printf("请输入要插入的位置：\n");
				scanf_s("%d", &position);
				printf("请输入要插入的元素：\n");
				scanf_s("%d", &e);
				insert(&L, position, e);
				break;
			case 3:
				printf("请输入要删除的位置：\n");
				scanf_s("%d", &position);
				if (delete_L(&L, position, &e)) {
					printf("删除的元素为：%d\n",e);
				}
				break;
			case 4:
				if (getHead(&L, &e)) {
					printf("该线性表的头元素为：%d\n", e);
				}
				break;
			case 5:
				if (getTail(&L, &e)) {
					printf("该线性表的尾元素为：%d\n", e);
				}
				break;
			case 6:
				printf("请输入查询的位置：");
				scanf_s("%d", &position);
				if (get(&L, position, &e) != ERROR) {
					printf("该位置的元素为：%d\n",e);
				}
				break;
			case 7:
				printf("请输入查询的元素：");
				scanf_s("%d", &e);	
				position = get_locate(&L, e);
				if ((position  != ERROR)) {
					printf("该元素的位置为：%d\n", position);
				}
				break;
			case 8:
				printf("该线性表长度为：%d\n", size(&L));
				break;
			case 9:
				clear(&L);
				break;
			case 10:
				if (empty(&L) == TRUE) {
					printf("单链表为空!\n");
				}
				else {
					printf("单链表不为空!\n");
				}
				break;
			case 11:
				print(&L);
				break;
			case 12:
				printf("已退出！\n");
				return 0;
			case 13:
				main();
				break;
			default:
				printf("输入错误！\n");
		}
	}
    return 0;
}