第三课

1，有头单链表

1.1链表的概念

链表和顺序表都是线性表的一种，但是链表的每个数据的存储是不连续的；每个元素如何连接，需明白，在基本单位结构体中分为两种数据，分别是数据域和指针域，是由每个基本单位结构体的指针域指向下一个位置的地址，从而将它们连接起来，链表在内存空间中数据存储的位置的特点是分布离散的、随机的；它们就像串珠子一样一个接一个的线性结构；

基本框架事例：
typedef int Data;
typedef struct _Node
{
	Data dara;  //数据域
	struct _Node* next;//指向后继节点的指针
}Node,List;
创建一个链表(事例)：
    List* createList()//创建一个链表
{
	List* list = calloc(1, sizeof(List));
	assert(list != NULL);
	list->next = NULL;
	list->dara = -1;//头结点里面的数据域不存储任何东西
	return list;
}

1.2头指针与头结点

头指针：指向链表第一个结点的指针，如果有头结点，那么头指针就是头结点的指针；

头结点：头结点是为了操作统一和方便而设立，即放在第一个元素的结点之前，数据域一般没有意义(也可以放链表长度)；

1.3链表的分类

有头链表、无头链表、双向链表、双向循环链表；

1.4创建一个新结点

Node* createNode(Data data)
{
	Node* newNode = malloc(sizeof(Node));//创建一个结点
	assert(newNode != NULL);
	newNode->next = NULL;
	newNode->data = data;
	return newNode;
}

1.5尾插

例子：
void push_back(List* list, Data data)
{
	Node* newNode = createNode(data);//创建一个结点
	Node* curNode = list;
	while (curNode->next!=NULL)
	{
		curNode = curNode->next;
	}
	curNode->next = newNode;//连接到新结点
}

1.6头插

例子：
    void push_front(List* list, Data data)
{
	Node* newNode = createNode(data);
	newNode->next = list->next;
	list->next = newNode;
}

1.7指定位置插入

例子：
    void insert(List* list, Node* pos, Data data)
{
	Node* newNode = createNode(data);
	Node* curNode = list;
	while (curNode->next!=pos)
	{
		curNode = curNode->next;
	}
	newNode->next = pos;
	curNode->next = newNode;
}

1.8查找

例子：
Node* find(List* list, Data data)
{
	Node* curNode = list;
	while (curNode->next!=NULL)
	{
		curNode = curNode->next;
		if (data==curNode->data)
		{
			return curNode;
		}
	} 
	return NULL;
}

1.9判断为空

#include<stdbool.h>
bool empty(List* list)
{
	return list->next == NULL;
}

1.10展示

void show_list(List* list)
{
	Node* curNode = list->next;
	while (curNode!=NULL)
	{
		printf("%d ", curNode->data);
		curNode = curNode->next;
	}
	printf("\n");
}

1.11头删

例子:
void pop_front(List* list)
{
	if (empty(list))
	{
		return;
	}
	Node* delNode =list->next;//暂存
	list->next = delNode->next;
	free(delNode);
	delNode = NULL;
}

1.12尾删

例子：
void pop_back(List* list)
{
	if (empty(list))
	{
		return;
	}
	Node* curNode = list;
	while (curNode->next->next!=NULL)
	{
		curNode = curNode->next;
	}
	free(curNode->next);
	curNode->next = NULL;
}

1.13指定位置删除

例子：
void erase_val(List* list, Data data)
{
	if (empty(list))
	{
		return;
	}
	Node* curNode = list;
	while (curNode->next!=NULL)
	{
		if (curNode->next->data==data)
		{
			Node* delNode = curNode->next;
			curNode->next = delNode->next;
			free(delNode);
			return;
		}
		if (curNode->next->next!=NULL)
		{
			curNode = curNode->next;
		}
	}
}

1.14排序

void sort(List* list)
{
    //链表不为空且不止一个结点
	if (empty(list)&&list->next->next!=NULL)
		return;
	for (Node* i = list->next; i->next!=NULL ; i=i->next)
	{
		for (Node* curNode = list->next; curNode->next!= NULL; curNode = curNode->next)
		{
			if (curNode->data>curNode->next->data)
			{
				Data t = curNode->data;
				curNode->data=curNode->next->data;
				curNode->next->data = t;
			}
		}
	}
}

1.15清除

void clear(List* list)
{
	if (empty(list))
	{
		return;
	}
	while (list->next!=NULL)
	{
		pop_front(list);
	}
}

1.16销毁

void destory(List** list)
{
	clear(*list);
	free(*list);
	*list = NULL;
}

1.17反转

void reverse(List* list)
{
	if (empty(list))
	{
		return;
	}
	Node* curNode = list->next;//当前处理结点的位置
	Node* prevNode = NULL;//保存上一个结点的位置
	Node* nextNode = NULL;//保存下一个结点的位置；
	while (curNode!=NULL)
	{
		nextNode = curNode->next;
		curNode->next = prevNode;
		prevNode = curNode;
		curNode = nextNode;
	}
	list->next = prevNode;
}

1.18全选和缩放快捷键

全选：Ctrl+a;
缩放(打开缩放)：Ctrl+m+m