C语言数据结构学习：单链表

C语言数据结构学习：

汇总入口：C语言数据结构学习：[汇总]

单链表

1. 基础了解

学习之前先了解线性表、顺序表和链表

线性表的两个特点：

1. 有限的序列
2. 序列中的每一个元素都有唯一的前驱和后继，除了开头和结尾两个节点

顺序表的特点：

1. 分配一块连续的内存去存放这些数据，例如数组

链表：

1. 内存是不连续的，元素会各自被分配一块内存，内存和内存之间用指针进行项链

2. 单链表

1. 一个节点包括：data、next
   • next指向下一个节点的位置
2. 一般包含 1个链表包含头结点 和 n个数据节点

3. 单链表操作：

1. 增加

   1. 头插法：一个新的节点，next指向原先的链表头
   2. 尾插法：原先的链表尾指向，一个新的节点。

2. 删除：

   只需要找到对应节点，将对应节点的前一个节点指向这个节点的**后继，**只操作一个指针

4. 代码示例

1. 定义新的类型：Node，用于创建节点

   #include <stdio.h>
   #include <stdlib.h>
   
   /* 定义新的类型Node，用于创建节点 */
   typedef struct Node {
   	int data;			//data
   	struct Node* next;	//存放下一个节点结构体的位置
   }Node;
   

2. 初始化头节点函数

   /* 初始化头结点 */
   Node* initlist() {
   	/* 开辟空间 */
   	Node* list = (Node*)(malloc(sizeof(Node)));
   	/* 初始化 */
   	list->data = 0;
   	list->next = NULL;
   	return list;
   }
   

3. 增加、删除函数

   /* 头插法 */
   void headInsert(Node* list, int data){
   	Node* node = (Node*)(malloc(sizeof(Node)));
   	node->data = data;
   	node->next = list->next;		//指向头结点指向的节点
   	list->next = node;				//头结点指向新的节点
   
   	list->data++;					//当前链表中插入了一个元素
   }
   
   /* 尾插法 */
   void tailInsert(Node* list, int data) {
   	Node* current = list;			//保存头结点的地址
   	Node* node = (Node*)(malloc(sizeof(Node)));
   	node->data = data;
   	node->next = NULL;				//指向NULL
   	while (current->next)			//如果current的后继不为NULL、则进入while
   	{
   		current = current->next;	//否则current会指向下一个节点
   	}
   	current->next = node;			//将current指向的最后一个节点 与新节点连接
   
   	list->data++;					//当前链表中插入了一个元素
   }
   
   /* 删除 */
   void delete (Node* list, int data) {
   	Node* current = list;			//保存头结点地址
   	Node* previous = list;			//用于保存上一个结点地址
   	current = current->next;		//使current指向第一个（数据）节点的位置
   	while (current){				//如果current不为空指针则进入while
   		if (current->data == data){	//如果是我要删除的data
   			previous->next = current->next;//把上一个节点的next链接到下一个节点
   			free(current);			//释放当前节点
   			list->data--;			//当前链表中删除了一个元素
   			break;
   		}
   		previous = current;			//保存当前位置
   		current = current->next;	//指向下一个节点
   	}
   }
   

4. 打印列表函数

   /* 打印链表 */
   void printList(Node* list){
   	Node* current = list;			//保存头结点地址
   	current = current->next;		//使current指向第一个（数据）节点的位置
   	while (current) {				//如果current不为空指针则进入while
   		printf("%d ", current->data);
   		current = current->next;	//指向下一个节点
   	}
   	printf("\\n");
   }
   

5. 测试

   /* 测试 */
   void main()
   {
   	printf("Hello World!!\\n");
   	/* 初始化链表 */
   	Node* list = initlist();
   	/* 头插法 */
   	headInsert(list, 1);
   	headInsert(list, 2);
   	headInsert(list, 3);
   	headInsert(list, 4);
   	headInsert(list, 5);
   	/* 尾插法 */
   	tailInsert(list, 6);
   	tailInsert(list, 7);
   	tailInsert(list, 8);
   	tailInsert(list, 9);
   	tailInsert(list, 10);
   
   	/* 删除 */
   	delete(list, 1);
   	delete(list, 6);
   
   	/* 打印 */
   	printList(list);
   	return 0;
   }