单链表

1.概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +[ 指针](https://baike.baidu.com/item/ 指针/2878304)(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

2.数据结构

typedef int ElemType;
//单链表的数据结构
typedef struct LinkNode {
	ElemType val;
	LinkNode* next;
}LinkNode;

3.单链表的初始化

//链表的初始化
LinkNode* InitLinkList()
{
	return BuyNode(-1);
}

4.生成结点

//生成一个LinkNode结点
LinkNode* BuyNode(ElemType elem)
{
	LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
	assert(p != NULL);
	memset(p, 0, sizeof(LinkNode));
	p->val = elem;
	return p;
}

5.释放结点

void FreeNode(LinkNode* p)
{
	if (NULL == p) { return; }
	free(p);
	p = NULL;
}

6.插入

// 在pos后插入一个新的值
void Insert(LinkNode* pos, ElemType elem)
{
	if (NULL == pos) { return; }
	LinkNode* p = BuyNode(elem);
	p->next = pos->next;
	pos->next = p;
}
//头插入
void PushFront(LinkNode* head, ElemType elem)
{
	if (head == NULL) { return; }
	Insert(head, elem);
}
//尾部插入
void PushBack(LinkNode* head, ElemType elem)
{
	if (head == NULL) { return; }
	int len = GetLength(head);
	LinkNode* p = FindIndex(head, len - 1);
	Insert(p, elem);
}

7.查找

//根据值查找
LinkNode* FindValue(LinkNode* head, ElemType elem)
{
	if (head == NULL) { return NULL; }
	head = head->next;
	for (; head!= NULL && head->val != elem; head = head->next);
	return head;
}

8.删除

//删除一个结点
void Delete(LinkNode* head, ElemType elem)
{
	if (head == NULL) { return; }
	while (head->next != NULL && head->next->val != elem)
	{
		head = head->next;
	}
	if (head->next != NULL)
	{
		LinkNode* p = head->next;
		head->next = p->next;
		FreeNode(p);
		p = NULL;
	}
}

9.修改

//按照索引修改值
void Alter(LinkNode* head, int index, ElemType elem)
{
	if (head == NULL) { return; }
	LinkNode* p = FindIndex(head,index);
	if (p != NULL)
	{
		p->val=elem;
	}
}

10.获取长度

//获取链表的长度
int GetLength(LinkNode* head)
{
	if (NULL == head) { return -1; }
	int len = 0;
	while (head->next != NULL)
	{
		len++;
		head = head->next;
	}
	return len;
}

11.打印

//单链表的打印
void Print(LinkNode* head)
{
	if (NULL == head) { return; }
	while (head->next != NULL)
	{
		printf("%d  ", head->next->val);
		head = head->next;
	}
	printf("\n");
}

12.销毁

//销毁单链表
void Destory(LinkNode** head)
{
	while (*head != NULL)
	{
		LinkNode* p = *head;
		*head = (*head)->next;
		FreeNode(p);
		p = NULL;
		
	}
}

一起学习，一起成长