链表
- 链表就是将零碎的内存组织起来
静态链表
image
#include <stdio.h>
typedef struct node{
int data;
struct node *next;
} Node;
int main()
{
/*
静态链表:
*/
// 定义三个结构体
Node a;
Node b;
Node c;
// 让三个结构体保存数据
a.data = 1;
b.data = 3;
c.data = 5;
// 将三个结构体链接在一起
a.next = &b;
b.next = &c;
// 如果指针没有值,那么可以赋值为NULL,明确告诉系统该指针没有值;
c.next = NULL;
// 定义链表的头指针
Node *head = &a;
printf("a.data = %i\n", a.data);
return 0;
}
动态链表
- 空链表
- 只有头指针和一个节点,并且节点没有数据, 也没有下一个节点
#include <stdio.h> #include <stdlib.h> typedef struct node{ int data; struct node *next; } Node; Node *creatList(); void insertNode(Node *head, int num); void printList(Node *head); int main() { // 1. 创建空链表 Node *head = creatList(); // 插入节点,并保存数据 insertNode(head, 1); insertNode(head, 3); insertNode(head, 5); // 打印链表 printList(head); return 0; } // 1.创建空链表 /** * @brief creatList 创建空链表 * @return 返回头指针 */ Node *creatList(){ // 定义头指针并开辟一个空节点 Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL; // 返回头指针 return head; }
头插法
-
规则:
- 1.让新节点的下一个节点 等于 头结点的下一个节点(头节点next的内容)
- node->next = head->next;
- 2.让头结点的下一个节点等于新的节点(地址)
- head->next = node;
- 规律
- : 新的节点永远都是插入到了头结点的后面
- 1.让新节点的下一个节点 等于 头结点的下一个节点(头节点next的内容)
-
图示:
- 1.创建空链
- image
- 2.第一步:让头结点的下一个节点 等于 新的节点
- image
- 3.让头结点的下一个节点 等于 新的节点
- image
- 4.继续插入链表:
- image
- 5.第一步:让头结点的下一个节点 等于 新的节点
- image
- 6.第二步:让头结点的下一个节点 等于 新的节点
- image
- 7.结果如图
- image
- 以此类推
/ 头插法插法插入链表 /** * @brief insertListF 头插法给链表插入新的节点 * @param head 链表的头指针 * @param num 需要新节点保存的数据 */ void insertListF(Node *head , int num){ // 创建一个新的节点 Node *node = (Node *)malloc(sizeof(Node)); // 将数据保持到新节点中 node->data = num; // 让新节点的下一个节点 等于 头节点的下一个节点 node->next = head->next; // 让头结点的下一个节点 等于 新节点 head->next = node; }
尾插法
-
规则:
- 1.定义变量记录新节点的上一个节点
- 2.将新节点添加到上一个节点后面
- 3.让新节点成为下一个节点的上一个节点
-
图示:
- 1.创建空链
- image
- 2.定义变量记录新节点的上一个节点
- 3.将新节点添加到上一个节点后面
- image
- 4.让新节点成为下一个节点的上一个节点
- image
- 5.继续插入
- image
- 6.将新节点添加到上一个节点后面
- image
- 7.让新节点成为下一个节点的上一个节点
- image
- 以此类推
// 尾插法插入链表 /** * @brief insertListR 尾插法给链表插入新的节点 * @param head 链表的头指针 * @param num 需要新节点保存的数据 */ void insertListR(Node *head , int num){ // 定义一个变量保存最后一个节点 Node *pre = head; while(pre != NULL && pre->next != NULL){ pre = pre->next; } // 创建一个新的节点 Node *node = (Node *)malloc(sizeof(Node)); // 将数据保持到节点中 node->data = num; node->next = NULL; // 将新节点添加到上一个节点后面 pre->next = node; // 让新节点称为下一个节点的上一个节点(就是尾节点) pre = node; }
输出链表
// 输出链表
/**
* @brief printList 遍历链表
* @param head 链表的头指针
*/
void printList(Node *head){
// 取出头节点的下一个节点: 默认头节点为空
Node *cur = head->next;
// 判断是否为NULL, 如果不为NULL就开始遍历
while (cur != NULL) {
// 取出当前数据
printf("data = %i\n", cur->data);
// 让当前节点往后移动
cur = cur->next;
}
}
摧毁链表
// 摧毁链表
/**
* @brief destroyList 摧毁链表
* @param head 链表的头指针
*/
void destroyList(Node *head){
Node *cur = NULL;
while(head != NULL){
cur = head->next;
free(head);
head = cur;
}
}
链表的长度
// 计算链表的长度
/**
* @brief listLength 计算链表的长度
* @param head 链表的头指针
* @return
*/
int listLength(Node *head){
// 定义变量记录节点的个数
int count = 0;
// 注意点: 要先去除头结点
Node *cur = head->next;
while (cur != NULL) {
count++;
cur = cur->next;
}
return count; // 返回长度
}
查找节点
/**
* @brief findNode 查找节点
* @param head 链表需要的头指针
* @param key 需要查找的key
* @return 符合要求的节点, 如果找不到返回NULL
*/
Node *findNode(Node *head, int key){
head = head->next;
while(head != NULL){
if(head->data == key){
return head;
}else{
head = head->next;
}
}
return NULL;
}
删除节点
// 删除节点
void deleteNode(Node *head, Node *node){
// 找到需要删除的节点的上一个节点
while (head->next != node) {
head = head->next;
}
// 将删除节点上一个节点next改为, 删除节点的下一个节点
head->next = node->next;
free(node);
}
链表排序
/**
* @brief sortList 链表排序
* @param head 传入头指针
*/
void sortList(Node *head){
// 排序
int len = listLength(head);
Node *cur = NULL;
for(int i = 0; i < len - 1; i++){
cur = head->next;
for(int j = 0; j < len - i -1; j++){
// printf("*");
if(cur->data > cur->next->data){
int temp = cur->data;
cur->data = cur->next->data;
cur->next->data = temp;
}
cur = cur->next;
}
// printf("\n");
}
}
链表反转
- 思路就是将链表从头节点拆开, 一分为二, 然后用头插法插入
- 图示
- 1.链表的原始位置:
- image
- 2.将链表拆开
- image
- 3.头插法思想重新插入 ; 新节点的下一个节点等于头结点的下一个节点
- image
- 让头节点的下一个 等于 当前节点
- image
- 使pre = cur;
- image
- 用头插法, 以此类推, cur = pre->next;
void reverseList(Node *head){
// 思路:将链表从头结点拆开 一分为二, 并记录当前位置
// pre 是记录新节点的地址; cur记录是剩余链表的首地址
Node *pre, *cur;
pre = head->next;
// 让head 成为空链表
head->next = NULL;
// 重新插入节点
while(pre){
// 保存剩余的空链表防止后面的链表丢失
cur = pre->next;
// 按头插法进行插入, 因为头插法是逆序输出
// 新节点的下一个节点 等于 头节点的下一个节点
pre->next = head->next;
// 头节点的下一个节点 等于 头结点
head->next = pre;
// 让新节点成为下一个节点的上一个节点
pre = cur;
}
}
