链表C

链表Linked List
是一种在物理上非非连续，非顺序的数据结构，由若干个节点组成

链表在内存中的存储与数组的存储方式并不相同

• 链表：每一个节点都位于内存中不同的位置，依靠指针在逻辑上是他们串连起来
• 数组：在创建的时候会直接分配一段连续内存空间

以一串连续的数字来举例子
{1,2,3,4,5,6,7,8,9,0}

将这串数字分别采用链表和数组的方式存储，可以看到在给数组分配内存时是直接分配了一整块内存用来存储，在链表中是链表中是每一个数据都随机分配一个内存地址，使用连接线(指针)连接起来

数组：

链表:
这里只用单向链表做一个示例

如果将单向链表抽象出来，在逻辑上就像这张图一样一个节点连接一个节点

链表的组成

• 节点：一个链表由若干个节点组成
• 头节点指针：链表需要一个头指针，用来指向链表的起始位置
• 尾节点指针：不必须，本文只是将最后一个节点的next指向NULL，如有需要可自行添加

链表的优势和劣势

优势：链表能够灵活地插入，删除节点，所以更适用于插入，更新，删除操作更多场景。
劣势：链表的查找操作，需要从头遍历整个链表，性能低下，不适用与读操作多的场景。

链表的操作

链表单个节点的结构体

typedef struct LNode{
	int data;
	struct LNode* next;
} LNode,*LinkList;

初始化

链表初始化了一个空的头节点，这个头节点一般不存储任何数值或者可以用来存储链表长度等一些信息，有头节点的情况下可以方便我们做数据插入和删除

void InitLink(LinkList *head) {
	*head = (LinkList)malloc(sizeof(LNode));
	(*head)->next = NULL;
}

初始化后的链表如图所示，只有一个头节点，没有后继节点

查

在链表中做查找并不能像数组一样，给定指定下标就可以直接获取下标对应的数据，必须从头节点开始，一个一个查找，直到到达指定位置

/*
	链表节点的查找
	
	@param head 查找的链表的头指针
	@param index 需要查找的链表节点的索引
	@param *data 指定索引对应的数据
	
	@return 成功或失败的状态
*/
int GetElem(LinkList head, int index, Elemtype* data) {
	
	LinkList p;
	int i;
	p = head->next;//指向头节点的下一个节点
	
	for (i = 1; i < index; i++) { 
		p = p->next;
	}
	
	if (i > index || !p) { //如果位置或者节点异常则退出，给出一个异常的状态码
		return 0;
	}
	
	else { //如果没有异常则将数据赋值给*data并给一个正确的状态码
		*data = p->data;
		return 1;
	}
}

增

添加节点

/*
	链表节点的添加
	
	@param head 查找的链表的头指针
	@param index 需要查找的链表索引
	@param data 新节点的数据
	
	@return 成功或失败的状态
*/

int InsertLink(LinkList head, int index, int data) {
	LinkList p = head;
	int i = 0;
	while (i < post-1) { //寻找位置
		p = p->next;
		i++;
	}
	if (!p || i > post) { //如果位置或节点异常范围异常状态码
		return 0;
	}
	else { //如果无异常则直接添加节点并返回正确的状态码
		LinkList s = (LinkList)malloc(sizeof(LNode));
		s->data = elem;
		s->next = p->next;
		p->next = s;
		return 1;
	}
}

添加的节点的过程如下过程所示：

1. 创建一个空的节点s，给他添加数据
2. 将p的后继节点都存储到s的后继节点中
3. p->next不再指向原来的后继节点
4. p->next指向新的s节点
   

最后结果如下：

删

删除某个节点

/*
	链表节点的删除
		
	@param head 查找的链表的头指针
	@param index 需要查找的链表索引
	@param *data 需要删除的节点的数据，如果有需要可以提取出来
	
	@return 成功或失败的状态
*/

int LinkDelete(LinkList head, int index, int* data) {
	LinkList p = head,tmp_node;
	int i = 0;
	
	while (p->next && i < index - 1) { //寻找需要删除的节点的前一个节点
		p = p->next;
		i++;
	}
	
	if (!p->next || i > index - 1) { //如果位置或节点异常范围异常状态码
		return ERROR;
	}
	else { //如果无异常则删除节点并返回正确的状态码
		tmp_node = p->next;
		p->next = tmp_node->next;
		*elem = tmp_node->data;
		
		free(tmp_node);
		return OK;
	}
}

删除的节点的过程如下过程所示：

1. 将p->next节点存储再一个临时节点tmp_node中
2. 将临时节点tmp_node的下一个节点存储在p->next节点中，就相当于再链表中跳过了tmp_node节点
3. 如果有需要可以将tmp_node中的数据提取出来，返回到主函数中
4. 释放掉tmp_node

最后结果如下：

改

/*
	链表节点数据的更改
	
	@param head 查找的链表的头指针
	@param index 需要查找的节点的索引
	@param data 需要改懂得数据
	
	@return 成功或失败的状态
*/
int ChanegElem(LinkList head, int index, int data) {
	
	LinkList p;
	int i;
	p = head->next;//指向头节点的下一个节点
	
	for (i = 1; i < index; i++) { 
		p = p->next;
	}
	
	if (i > index || !p) { //如果位置或者节点异常则退出，给出一个异常的状态码
		return 0;
	}
	
	else { //如果没有异常则将数据赋值给p->data并给一个正确的状态码
		p->data = data;
		return 1;
	}
}