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;			//datastruct 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;				//指向NULLwhile (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不为空指针则进入whileif (current->data == data){	//如果是我要删除的dataprevious->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不为空指针则进入whileprintf("%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;
   }