文章目录
- 目录
- 1. 链表的概念及结构
- 2. 实现单链表
- 2.1 链表的打印
- 2.2 链表的尾插
- 2.3 链表的头插
- 2.4 链表的尾删
- 2.5 链表的头删
- 2.6 查找
- 2.7 在指定位置之前插入数据
- 2.8 在指定位置之后插入数据
- 2.9 删除pos节点
- 2.10 删除pos之后的节点
- 2.11 销毁链表
- 3. 链表的分类
目录
- 链表的概念及结构
- 实现单链表
- 链表的分类
1. 链表的概念及结构
概念:
链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的(链表在逻辑上是连续的,在物理结构上不一定连续) 。
链表是由一个一个节点(结点)组成的,一个节点由两个部分组成:要存储的数据 + 指针(结构体指针)
因此,只要定义节点的结构,就等于定义了链表:
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
2. 实现单链表
2.1 链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
2.2 链表的尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
//链表为空,新节点作为phead
if (NULL == phead)
{
phead = newnode;
return;
}
//链表不为空,找尾节点
SLTNode* ptail = phead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail就是尾节点
ptail->next = newnode;
}
这样写是错误的!当一开始链表为空时,尾插的节点就变成了第一个节点,因此要把phead中的NULL改为第一个节点的地址,所以要传phead的地址,而不是传值。
应该这样写:
//因为头插、尾插、指定位置插入都需要申请新节点,所以单独封装成一个函数
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (NULL == newnode)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空,新节点作为phead
if (NULL == *pphead)
{
*pphead = newnode;
return;
}
//链表不为空,找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail就是尾节点
ptail->next = newnode;
}
2.3 链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
2.4 链表的尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点,有多个节点
if (NULL == (*pphead)->next)
{
free(*pphead);
*pphead = NULL;
return;
}
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
//销毁尾节点
free(ptail);
ptail = NULL;
}
2.5 链表的头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//链表不能为空
assert(*pphead);
//让第二个节点成为新的头
//把旧的头节点释放掉
SLTNode* next = (*pphead)->next;//->的优先级高于*
free(*pphead);
*pphead = next;
}
2.6 查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur) //等价于pcur != NULL
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
2.7 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//要加上链表不能为空
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//pos刚好是头节点
if (pos == *pphead)
{
//头插
SLTPushFront(pphead, x);
return;
}
//pos不是头节点的情况
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
2.8 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
2.9 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
//pos刚好是第一个节点,没有前驱节点,执行头删
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
2.10 删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//pos->next不能为空
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
2.11 销毁链表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
完整代码:
//SList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//链表的头插、尾插
//void SLTPushBack(SLTNode* phead, SLTDataType x);//err
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
//SList.c
#include "SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//因为头插、尾插、指定位置插入都需要申请新节点,所以单独封装成一个函数
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (NULL == newnode)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空,新节点作为phead
if (NULL == *pphead)
{
*pphead = newnode;
return;
}
//链表不为空,找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail就是尾节点
ptail->next = newnode;
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点,有多个节点
if (NULL == (*pphead)->next)
{
free(*pphead);
*pphead = NULL;
return;
}
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
//销毁尾节点
free(ptail);
ptail = NULL;
}
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//链表不能为空
assert(*pphead);
//让第二个节点成为新的头
//把旧的头节点释放掉
SLTNode* next = (*pphead)->next;//->的优先级高于*
free(*pphead);
*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur) //等价于pcur != NULL
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//要加上链表不能为空
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//pos刚好是头节点
if (pos == *pphead)
{
//头插
SLTPushFront(pphead, x);
return;
}
//pos不是头节点的情况
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
//pos刚好是第一个节点,没有前驱节点,执行头删
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//pos->next不能为空
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
//Test.c
//int removeElement(int* nums, int numsSize, int val)
//{
// //定义两个变量
// int src = 0, dst = 0;
//
// while (src < numsSize)
// {
// //nums[src] == val,src++
// //否则赋值,src和dst都++
// if (nums[src] == val)
// {
// src++;
// }
// else
// {
// //说明src指向位置的值不等于val
// nums[dst] = nums[src];
// dst++;
// src++;
// }
// }
//
// //此时dst的值刚好是数组的新长度
// return dst;
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
// int l1 = m - 1;
// int l2 = n - 1;
// int l3 = m + n - 1;
//
// while (l1 >= 0 && l2 >= 0)
// {
// //从后往前比大小
// if (nums1[l1] > nums2[l2])
// {
// nums1[l3--] = nums1[l1--];
// }
// else
// {
// nums1[l3--] = nums2[l2--];
// }
// }
//
// //要么是l1 < 0,要么是l2 < 0
// while (l2 >= 0)
// {
// nums1[l3--] = nums2[l2--];
// }
//}
#include "SList.h"
void SListTest01()
{
//一般不会这样去创建链表,这里只是为了给大家展示链表的打印
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
SLTNode* plist = node1;
SLTPrint(plist);
}
void SListTest02()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
//SLTPushBack(NULL, 5);
//SLTPushFront(&plist, 5);
//SLTPrint(plist);
//SLTPushFront(&plist, 6);
//SLTPrint(plist);
//SLTPushFront(&plist, 7);
//SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
}
void SListTest03()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
//头删
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
//SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
//SLTNode* FindRet = SLTFind(&plist, 3);
if (FindRet)
{
printf("找到了!\n");
}
else
{
printf("未找到!\n");
}
SLTInsert(&plist, FindRet, 100);
SLTPrint(plist);
SLTInsertAfter(FindRet, 100);
SLTPrint(plist);
删除指定位置的节点
//SLTErase(&plist, FindRet);
//SLTPrint(plist);
SListDesTroy(&plist);
}
int main()
{
//SListTest01();
//SListTest02();
SListTest03();
return 0;
}
3. 链表的分类
链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构:
链表说明:
注:
- 之前代码里写的 SList 意思是 single linked list --> 单链表(不带头单向不循环链表)
- 刚才在单链表中提到的“头节点”指的是第一个有效的节点;“带头”链表里的“头”指的是无效的节点
- “带头”中的“头”:放哨的;头节点:哨兵位(不保存任何有效的数据)
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:单链表和双向带头循环链表。
- 无头单向非循环链表:结构简单,⼀般不会单独用来存数据,实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等;另外这种结构在笔试面试中出现很多。
- 带头双向循环链表:结构最复杂,⼀般用在单独存储数据,实际中使用的链表数据结构,都是带头双向循环链表;另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。