数据结构之单链表
什么是链表
链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储具体的数据，而指针域则用于指向下一个节点。
链表的特点如下：
- 链表中的节点在内存中可以随机分布，不要求连续存储。
- 每个节点通过指针将其与下一个节点连接起来，形成链式结构。
- 链表的头节点可以作为访问整个链表的入口。
根据指针的类型和指向的节点数目，链表可以分为多种类型，包括单向链表、双向链表和循环链表等。
链表相比于顺序表有以下优势：
- 插入和删除操作效率高，只需要修改指针的指向，不需要移动其他节点。
- 可以动态地分配内存空间，不需要事先定义容量。
- 适用于频繁插入和删除的场景。
然而，链表的缺点是访问元素的效率较低，需要从头节点开始遍历整个链表才能找到目标节点。此外，链表的存储空间会稍微多于顺序表，因为每个节点都需要额外的指针来连接其他节点。
链表的分类
链表可以根据指针的类型和指向的节点数目进行分类。以下是几种常见的链表有以下这些：
- 有头链表: 固定表头节点
- 无头链表:表头节点可改变
- 单向链表: 一个寻址指针
- 双向链表:两个寻址指针
- 循环链表:首位连通
有头单链表
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef struct MM
{
char name[20];
int age;
int num;
}MM;
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node* next;
}Node;
Node* create_list()
{
Node* headNode = (Node*)calloc(1, sizeof(Node));
assert(headNode);
return headNode;
}
Node* create_node(DataType data)
{
Node* newNode = (Node*)calloc(1, sizeof(Node));
assert(newNode);
newNode->data = data;
return newNode;
}
void print_list(Node* list)
{
if (list == NULL)
return;
Node* pmove = list->next;
while (pmove != NULL)
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
void push_front(Node* headNode, DataType data)
{
if (headNode == NULL)
return;
Node* newNode = create_node(data);
newNode->next = headNode->next;
headNode->next = newNode;
}
void push_back(Node* headNode,DataType data)
{
if (headNode == NULL)
return;
Node* pmove = headNode;
while (pmove->next != NULL)
{
pmove = pmove->next;
}
#if 0
Node* newNode = create_node(data);
pmove->next = newNode;
#endif
pmove->next = create_node(data);
}
void insert(Node* headNode, DataType posData, DataType data)
{
if (headNode == NULL)
return;
Node* preNode = headNode;
Node* posNode = headNode->next;
while (posNode != NULL && posNode->data != posData)
{
#if 0
preNode = preNode->next;
posNode = posNode->next;
#endif
preNode = posNode;
posNode = preNode->next;
}
//分析查找结果
if (posNode == NULL)
{
printf("未找到指定节点,无法插入!!!!\n");
}
else
{
Node* newNode = create_node(data);
preNode->next = newNode;
newNode->next = posNode;
}
}
void pop_front(Node* list)
{
if (list == NULL)
return;
Node* frontNode = list->next;
if (frontNode != NULL)
{
list->next = frontNode->next;
free(frontNode);
frontNode = NULL;
}
}
void pop_back(Node* list)
{
if (list == NULL)
return;
Node* preNode = list;
Node* tailNode = list->next;
if (tailNode != NULL)
{
while (tailNode->next != NULL)
{
preNode = tailNode;
tailNode = preNode->next;
}
free(tailNode);
tailNode = NULL;
preNode->next = NULL;
}
}
void erase(Node* list, DataType posData)
{
if (list == NULL)
return;
Node* preNode = list;
Node* posNode = list->next;
while (posNode != NULL && posNode->data != posData)
{
preNode = posNode;
posNode = preNode->next;
}
if (posNode == NULL)
{
printf("未找到指定节点,无法插入!\n");
}
else
{
preNode->next = posNode->next;
free(posNode);
posNode = NULL;
}
}
//其他
//按位序进行插入删除
Node* search(Node* list, DataType posData)
{
if (list == NULL)
return NULL;
Node* pmove = list->next;
while (pmove != NULL && pmove->data != posData)
{
pmove = pmove->next;
}
return pmove;
}
void destory(Node* list)
{
if (list == NULL)
return;
while (list->next != NULL)
{
pop_front(list);
}
free(list);
}
int main()
{
Node* list = create_list();
push_front(list, 1);
push_front(list, 2);
push_front(list, 3);
print_list(list);
push_back(list, 4);
push_back(list, 5);
push_back(list, 6);
print_list(list);
insert(list, 4, 888);
print_list(list);
pop_front(list);
pop_front(list);
print_list(list);
pop_back(list);
pop_back(list);
print_list(list);
erase(list, 888);
print_list(list);
destory(list);
list = NULL;
return 0;
}无头单链表
- 再封装写法
- 二级指针写法
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef struct MM
{
char name[20];
int age;
int num;
}MM;
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node* next;
}Node;
Node* create_list()
{
Node* headNode = (Node*)calloc(1, sizeof(Node));
assert(headNode);
return headNode;
}
Node* create_node(DataType data)
{
Node* newNode = (Node*)calloc(1, sizeof(Node));
assert(newNode);
newNode->data = data;
return newNode;
}
void print_list(Node* list)
{
if (list == NULL)
return;
Node* pmove = list->next;
while (pmove != NULL)
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
void push_front(Node* headNode, DataType data)
{
if (headNode == NULL)
return;
Node* newNode = create_node(data);
newNode->next = headNode->next;
headNode->next = newNode;
}
void push_back(Node* headNode,DataType data)
{
if (headNode == NULL)
return;
Node* pmove = headNode;
while (pmove->next != NULL)
{
pmove = pmove->next;
}
#if 0
Node* newNode = create_node(data);
pmove->next = newNode;
#endif
pmove->next = create_node(data);
}
void insert(Node* headNode, DataType posData, DataType data)
{
if (headNode == NULL)
return;
Node* preNode = headNode;
Node* posNode = headNode->next;
while (posNode != NULL && posNode->data != posData)
{
#if 0
preNode = preNode->next;
posNode = posNode->next;
#endif
preNode = posNode;
posNode = preNode->next;
}
//分析查找结果
if (posNode == NULL)
{
printf("未找到指定节点,无法插入!!!!\n");
}
else
{
Node* newNode = create_node(data);
preNode->next = newNode;
newNode->next = posNode;
}
}
void pop_front(Node* list)
{
if (list == NULL)
return;
Node* frontNode = list->next;
if (frontNode != NULL)
{
list->next = frontNode->next;
free(frontNode);
frontNode = NULL;
}
}
void pop_back(Node* list)
{
if (list == NULL)
return;
Node* preNode = list;
Node* tailNode = list->next;
if (tailNode != NULL)
{
while (tailNode->next != NULL)
{
preNode = tailNode;
tailNode = preNode->next;
}
free(tailNode);
tailNode = NULL;
preNode->next = NULL;
}
}
void erase(Node* list, DataType posData)
{
if (list == NULL)
return;
Node* preNode = list;
Node* posNode = list->next;
while (posNode != NULL && posNode->data != posData)
{
preNode = posNode;
posNode = preNode->next;
}
if (posNode == NULL)
{
printf("未找到指定节点,无法插入!\n");
}
else
{
preNode->next = posNode->next;
free(posNode);
posNode = NULL;
}
}
//其他
//按位序进行插入删除
Node* search(Node* list, DataType posData)
{
if (list == NULL)
return NULL;
Node* pmove = list->next;
while (pmove != NULL && pmove->data != posData)
{
pmove = pmove->next;
}
return pmove;
}
void destory(Node* list)
{
if (list == NULL)
return;
while (list->next != NULL)
{
pop_front(list);
}
free(list);
}
int main()
{
Node* list = create_list();
push_front(list, 1);
push_front(list, 2);
push_front(list, 3);
print_list(list);
push_back(list, 4);
push_back(list, 5);
push_back(list, 6);
print_list(list);
insert(list, 4, 888);
print_list(list);
pop_front(list);
pop_front(list);
print_list(list);
pop_back(list);
pop_back(list);
print_list(list);
erase(list, 888);
print_list(list);
destory(list);
list = NULL;
return 0;
}链表其他操作
- 有序链表的构建
- 链表归并
- 链表的反转问题
- 链表的冒泡排序
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* create_list()
{
Node* headNode = (Node*)calloc(1, sizeof(Node));
assert(headNode);
return headNode;
}
Node* create_node(int data)
{
Node* newNode = (Node*)calloc(1, sizeof(Node));
assert(newNode);
newNode->data = data;
return newNode;
}
void print_list(Node* list)
{
Node* pmove = list->next;
while (pmove != NULL)
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
//有序链表构建
void push_sort(Node* list, int data)
{
Node* newNode = create_node(data);
Node* preNode = list;
Node* posNode = preNode->next;
while (posNode != NULL && posNode->data <= data)
{
preNode = posNode;
posNode = preNode->next;
}
if (posNode == NULL && preNode == list)
{
list->next = newNode;
}
if (posNode == NULL && preNode != list)
{
preNode->next = newNode;
}
else
{
preNode->next = newNode;
newNode->next = posNode;
}
}
//冒泡排序
void bubble_sort(Node* list)
{
for (Node* p = list->next; p != NULL; p=p->next)
{
for (Node* q = list->next; q != NULL; q = q->next)
{
if (q->next != NULL && q->data < q->next->data)
{
int data = q->data;
q->data = q->next->data;
q->next->data = data;
}
}
}
}
//链表的归并
void mergeList(Node* result, Node* list1, Node* list2)
{
Node* first = list1->next;
Node* second = list2->next;
Node* tailNode = result;
while (first != NULL && second != NULL)
{
if (first->data < second->data)
{
tailNode->next = first;
tailNode = first;
first = first->next;
}
else
{
tailNode->next = second;
tailNode = second;
second = second->next;
}
}
if (first != NULL)
{
tailNode->next = first;
}
if (second != NULL)
{
tailNode->next = second;
}
}
//链表反转
void reverse_list(Node* list)
{
if (list == NULL || list->next == NULL || list->next->next == NULL)
return;
Node* preNode = NULL;
Node* curNode = list->next;
Node* surNode = curNode->next;
while (surNode != NULL)
{
curNode->next = preNode;
preNode = curNode;
curNode = surNode;
surNode = surNode->next;
}
curNode->next = preNode;
list->next = curNode;
}
int main()
{
Node* s = create_list();
push_sort(s, 9);
push_sort(s, 2);
push_sort(s, 4);
push_sort(s, 3);
print_list(s);
bubble_sort(s);
print_list(s);
Node* result = create_list();
Node* first = create_list();
push_sort(first, 1);
push_sort(first, 5);
push_sort(first, 3);
push_sort(first, 7);
Node* second = create_list();
push_sort(second, 2);
push_sort(second, 6);
push_sort(second, 4);
mergeList(result, first, second);
print_list(result);
reverse_list(s);
print_list(s);
return 0;
}相关
如果阁下正好在学习C/C++，看文章比较无聊，不妨关注下关注下小编的视频教程，通俗易懂，深入浅出，一个视频只讲一个知识点。视频不深奥，不需要钻研，在公交、在地铁、在厕所都可以观看，随时随地涨姿势。
