数据布局——链表

发表于 2026-1-18 21:35:59

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

【本节内容】

1.链表

1.链表的概念及布局

概念：链表是一种物理存储布局上非一连、非序次的存储布局，数据元素的逻辑序次是通过链表中的指针链接序次实现的。就像我们一节一节的小火车一样，靠中心的链子链接在一起。

实际中数据布局中

1.2 链表的分类

实际中链表的布局非常多样，以下情况组合起来就有8种链表布局：

1. 单向大概双向

2. 带头大概不带头

3. 循环大概非循环

固然有这么多的链表的布局，但是我们实际中最常用还是两种布局：

1. 无头单向非循环链表：布局简单，一样平常不会单独用来存数据。实际中更多是作为其他数据布局的子布局，如哈希桶、图的毗邻表等等。别的这种布局在笔试口试中出现许多。
2. 带头双向循环链表：布局最复杂，一样平常用在单独存储数据。实际中利用的链表数据布局，都是带头双向循环链表。别的这个布局固然布局复杂，但是利用代码实现以后会发现布局会带来许多上风，实现反而简单了，背面我们代码实现了就知道了。

1、无头+单向+非循环链表增删查改实现
SList.h

#pragma once
#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 SLPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLPopFront(SLTNode** pphead);//头删
void SLPopBack(SLTNode** pphead);//尾删
void SLErase(SLTNode** pphead, SLTNode* pos);// 删除pos位置的值
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos位置插入
SLTNode* STFind(SLTNode* phead, SLTDataType x);//查找与x值相同的节点位置

复制代码

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
void SLTPrint(SLTNode* phead)//打印链表
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuyLTNode(SLTDataType x)//初始化节点
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLPushFront(SLTNode** pphead, SLTDataType x)//头插
{
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
SLTNode* newnode = BuyLTNode(x);
// 1、空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
// 2、非空链表
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLPopFront(SLTNode** pphead)//头删
{
// 判空
assert(*pphead);
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
}
void SLPopBack(SLTNode** pphead)//尾删
{
assert(*pphead);
// 一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
// 多个节点
else
{
SLTNode* tail = *pphead;
// 找尾
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
SLTNode* STFind(SLTNode* phead, SLTDataType x)//查找与x值相同的节点位置
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在pos位置插入
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void SLErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置的值
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}

复制代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
int main()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLPushFront(&plist, 0);
SLPopBack(&plist);
SLPopFront(&plist);
SLTNode* pos = STFind(plist, 1);
SLErase(&plist, pos);
SLTPrint(plist);
return 0;
}

复制代码

运行效果：

2.双向链表：
DList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
LTNode* LTInit();//初始化双向链表
void LTPrint(LTNode* phead);//打印双向链表
bool LTEmpty(LTNode* phead);//判断链表是否为空
void LTPushBack(LTNode* phead, LTDataType x);//双向链表尾插
void LTPushFront(LTNode* phead, LTDataType x);//双向链表头插
void LTPopBack(LTNode* phead);//双向链表尾删
void LTPopFront(LTNode* phead);//双向链表头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找与x值相同的节点
void LTInsert(LTNode* pos, LTDataType x);// 在pos位置插入
void LTErase(LTNode* pos);// 删除pos位置的值
void LTDestroy(LTNode* phead);//销毁双向链表

复制代码

DList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"DList.h"
LTNode* BuyLTNode(LTDataType x)//初始化节点
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()//初始化双向链表
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)//打印双向链表
{
assert(phead);
printf("guard<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}
bool LTEmpty(LTNode* phead)//判断双向链表是否为空
{
assert(phead);
return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)//双向链表尾插
{
assert(phead);
LTInsert(phead, x);
}
void LTPushFront(LTNode* phead, LTDataType x)//双向链表头插
{
LTInsert(phead->next, x);
}
void LTPopBack(LTNode* phead)//双向链表尾删
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)//双向链表头删
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->next);
}
LTNode* LTFind(LTNode* phead, LTDataType x)//查找与x值相同的节点
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)// 在pos位置插入
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void LTErase(LTNode* pos)//删除pos位置的值
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
void LTDestroy(LTNode* phead)//销毁双向链表
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}

复制代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"
int main()
{
LTNode* plist = LTInit();
printf("%d\n",LTEmpty(plist));
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPopFront(plist);
LTPopBack(plist);
LTNode* pos = LTFind(plist,2);
LTErase(pos);
LTPrint(plist);
LTDestroy(plist);
return 0;
}

复制代码

运行效果：

PS：看到这里了，码字不易，给个一键三连鼓励一下吧！有不敷大概错误之处接待在批评区指出！

数据布局——链表

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

浏览过的版块

九天猎人