单链表——初始化

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<string.h>
#define MAXSIZE 100
typedef int Elemtype;
//单链表初始化——直接在堆区创建
typedef struct Node
{
	Elemtype data;
	struct Node* next;
}Node;

Node* initList()
{
	Node* head = (Node*)malloc(sizeof(Node));
	head->data = 0;
	head->next = NULL;
	return head;
}

int main()
{
	Node* List = initList();
	return 1;
}

 单链表——头插法

//头插法
int insertHead(Node* L,Elemtype e)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = e;
	p->next = L->next;
	L->next = p;
}

int main()
{
	Node* list = initList();
	insertHead(list, 10);
	insertHead(list, 20);
}

单链表——遍历

注意：下面的L指的是头节点，头节点的next是首元节点，才是链表存数据的第一个

//遍历
void listNode(Node* L)
{
	Node* p = L->next;//L为头节点，L的next指向的是首元节点
	while (p != NULL)
	{
		printf("%d", p->data);
		p = p->next;
	}
	printf("\n");
}

单链表——尾插法

相比于头插法，要先找到尾部，找到节点next指向是NULL的节点

//尾插法
//先找到尾节点，获取尾节点
Node* get_tail(Node* L)
{
	Node* p = L;
	while (p->next !=NULL)
	{
		p = p->next;
	}
	return p;
}
//尾插
Node* insertTail(Node* tail, Elemtype e)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = e;
	tail->next = p;
	p->next = NULL;
	return p;
}

单链表——在指定位置插入数据

//在指定位置插入数据
int insertNode(Node* L, int pos, Elemtype e)//L链表，pos是插入的位置，e是插入的新数据
{
	//用来保存插入位置的前驱节点
	Node* p = L;
	int i = 0;
	//遍历链表找到插入位置的前驱节点
	while (i<pos-1)
	{
		p = p->next;
		i++;
		if (p == NULL)
		{
			return 0;
		}
	}

	Node* q = (Node*)malloc(sizeof(Node));
	q->data = e;
	q->next = p->next;
	p->next = q;
	return 1;
}

单链表——删除节点

找到要删除节点的前置节点p

用指针q记录要删除的节点

通过改变p的后继节点实现删除

释放删除节点的空间

//删除节点
int deleteNode(Node* L, int pos)
{
	//要删除节点的前驱节点
	Node* p = L;
	int i = 0;
	//遍历链表，找到要删除节点的前驱节点
	while (i < pos - 1)
	{
		p = p->next;
		i++;
		if (p == NULL)
		{
			return 0;
		}
	}
	if (p->next ==NULL)
	{
		printf("要删除的位置错误\n");
		return 0;
	}
	//q指向要删除的节点
	Node* q = p->next;
	//让要删除节点的前驱指向要删除节点的后继
	p->next = q->next;
	//释放要删除节点的空间
	free(q);
	return 1;
}

 单链表——获取链表长度

//获取链表长度
int listlength(Node* L)
{
	Node* p = L;
	int len = 0;
	while (p !=NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}

单链表——释放链表

指针p指向头节点后的第一个节点

判断指针p是否指向空节点

如果p不为空，用指针q记录指针p的后继节点

释放指针p指向的节点

指针p合指针q指向同一个节点，循环上面操作

//释放链表
void freeList(Node* L)//传进来链表，也就是头节点
{
	Node* p = L->next;
	Node* q;
	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL;//头节点指向空
}

单链表应用——反转链表

先拿first指向空值，再拿second指向1，third指向second所指向的下一个节点

 然后让second指向空值

 

 然后挪动三个指针

 再将此时的2指针指向改变

依次进行，直到second指向空值

 再安一个头节点

//反转链表
Node* reverseList(Node* head)
{
	Node *first = NULL;
	Node *second = head->next;
	Node *third;

	while(second != NULL)
	{
		third = second->next;
		second->next = first;
		first = second;
		second = third;
	}
	Node *hd = initList();
	hd->next = first;

	return hd;
}

int main(int argc, char const *argv[])
{
	Node *list = initList();
	
	Node *tail = get_tail(list);
	
	tail = insertTail(tail, 1);
	tail = insertTail(tail, 2);
	tail = insertTail(tail, 3);
	tail = insertTail(tail, 4);
	tail = insertTail(tail, 5);
	tail = insertTail(tail, 6);
	listNode(list);
	Node* reverse = reverseList(list);
	listNode(reverse);


	

	
	return 0;
}