目录

• 1.链表的概念
• 2.链表的结构
• • 1️⃣链表中单个结点的结构
  • 2️⃣链表的整体结构
• 3.链表的分类
• 4.链表的实现
• • 1️⃣单向无头非循环
  • 2️⃣双向带头循环

1.链表的概念

链表，是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。

2.链表的结构

1️⃣链表中单个结点的结构

数据域： 存储当前结点的数据（可以是不同类型）
指针域： 存储指向下一结点的指针

2️⃣链表的整体结构

• 逻辑结构

• 物理结构
  

💭如图二，链表在内存中的实际结构并不一定是连续的，每一个结点都是一块独立的空间，而结点之间依靠指针链接起来，成为链表。因此图一中的箭头并不是实际存在的，而是为了方便理解而建立的逻辑结构。

注意：
1.综上所述，链表的逻辑结构是连续的，而物理结构是不连续的；
2.链表结点的空间一般在堆上申请；
3.从堆上申请的空间是按一定策略来分配的，两次申请的空间可能连续，也可能不连续；
4.单向链表最后一个结点的指针域中的指针为NULL。

3.链表的分类

链表的种类有：单向与双向、带头和不带头、循环和非循环。
这些种类组合起来一共有8种类型的链表结构。

🔎虽然链表有许多种类型的结构，而我们最常用的却只有两种：

• 单向无头非循环
• 双向带头循环

1. 单向无头非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 双向带头循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，使用起来很简单。

4.链表的实现

下面用C语言代码实现两种常用的链表结构：

1️⃣单向无头非循环

🌲SList.h

#pragma once
#include 
#include 
#include typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLN;SLN* SListNodeApply(SLDataType x);//申请一个(data为x的)结点
void SListDestroy(SLN** pphead);//销毁链表
void SListPrint(SLN* phead);//打印链表
SLN* SListFind(SLN* phead,SLDataType x);//查找结点void SListFrontPush(SLN** pphead, SLDataType x);//头插
void SListBackPush(SLN** pphead, SLDataType x);//尾插
//
void SListFrontPop(SLN** pphead);//头删
void SListBackPop(SLN** pphead);//尾删
//
void SListInsert(SLN** pphead, SLN* pos, SLDataType x);//在pos位置(前)插入新值
void SListErase(SLN** pphead, SLN* pos);//删除pos位置的值

🌲SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Slist.h"SLN* SListNodeApply(SLDataType x)//申请一个(data为x的)结点
{SLN* pt = (SLN*)malloc(sizeof(SLN));if (pt == NULL){perror("SLNApply-malloc fail");exit(-1);}//pt->data = x;pt->next = NULL;return pt;
}void SListDestroy(SLN** pphead)//销毁链表
{assert(pphead);SLN* cur = *pphead;SLN* prev = *pphead;while (cur != NULL){cur = cur->next;free(prev);prev = cur;}*pphead = NULL;
}void SListPrint(SLN* phead)//打印链表(int型)
{while (phead != NULL){printf("%d->", phead->data);phead = phead->next;}printf("NULL\n");
}void SListFrontPush(SLN** pphead, SLDataType x)//头插
{assert(pphead);SLN* newnode = SListNodeApply(x);//newnode->next = *pphead;*pphead = newnode;
}void SListBackPush(SLN** pphead, SLDataType x)//尾插
{assert(pphead);SLN* newnode = SListNodeApply(x);//if (*pphead == NULL){*pphead = newnode;}else{SLN* cur = *pphead;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}
}void SListFrontPop(SLN** pphead)//头删
{assert(pphead);assert(*pphead);//移动phead,并将原来phead指向的空间释放SLN* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);tmp = NULL;
}void SListBackPop(SLN** pphead)//尾删
{assert(pphead);assert(*pphead);//SLN* cur = *pphead;SLN* prev = cur;while (cur->next != NULL){prev = cur;cur = cur->next;}//prev->next = NULL;free(cur);cur = NULL;
}SLN* SListFind(SLN* phead, SLDataType x)//查找结点(第一个data==x的结点)
{SLN* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SListInsert(SLN** pphead, SLN* pos, SLDataType x)//在pos位置(前)插入新结点
{assert(pphead);assert(pos);if (pos == *pphead){SListFrontPush(pphead, x);}else{SLN* newnode = SListNodeApply(x);SLN* cur = *pphead;SLN* prev = *pphead;while (cur != pos){prev = cur;cur = cur->next;}prev->next = newnode;newnode->next = pos;}
}void SListErase(SLN** pphead, SLN* pos)//删除pos位置的值
{assert(pphead);assert(pos);//if (pos == *pphead){SListFrontPop(pphead);}else{SLN* cur = *pphead;SLN* prev = NULL;while (cur != pos){prev = cur;cur = cur->next;//检查 pos不为该链表中结点的指针assert(cur);}prev->next = cur->next;free(cur);cur = NULL;}
}

2️⃣双向带头循环

🌲DList.h

#define _CRT_SECURE_NO_WARNINGS 1
//带头+双向+循环的链表
#pragma once 
#include 
#include 
#include 
#include typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;ListNode* ListCreate();//创建哨兵位
void ListDestroy(ListNode* phead);//销毁链表
void ListPrint(ListNode* phead);//打印链表
//
void ListPushBack(ListNode* phead,LTDataType x);//尾插
void ListPopBack(ListNode* phead);//尾删
void ListPushFront(ListNode* phead, LTDataType x);//头插
void ListPopFront(ListNode* phead);//头删
//
ListNode* ListFind(ListNode* phead, LTDataType x);//查找（找出第一个x）
void ListInsert(ListNode* pos, LTDataType x);//在pos位置前面插入元素
void ListErase(ListNode* pos);//删除pos位置的元素

🌲DList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"ListNode* ListCreate()//创建哨兵位
{ListNode* phead = (ListNode*)malloc(sizeof(ListNode));if (phead == NULL){perror("malloc fail");exit(-1);}//phead->next = phead;phead->prev = phead;//return phead;
}ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}void ListDestroy(ListNode* phead)//销毁链表
{assert(phead);//设置结束条件phead->prev->next = NULL;//迭代ListNode* cur = phead;while (cur){ListNode* del = cur;cur = cur->next;free(del);}//在函数外需要自行置空phead指针
}void ListPrint(ListNode* phead)//打印链表
{assert(phead);//迭代ListNode* cur = phead->next;printf("phead<=>");if (cur == phead)//链表为空{printf("NULL\n");}else//链表不为空{while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");}
}bool ListEmpty(ListNode* phead)
{return phead->next == phead;
}void ListPushBack(ListNode* phead, LTDataType x)//尾插
{assert(phead);创建新结点//ListNode* newnode = BuyListNode(x);链接//newnode->prev = phead->prev;//newnode->next = phead;//phead->prev->next = newnode;//phead->prev = newnode;ListInsert(phead, x);
}void ListPopBack(ListNode* phead)//尾删
{assert(phead);assert(!ListEmpty(phead));//控制链表不能为空//ListNode* tail = phead->prev;//tail->prev->next = phead;//phead->prev = tail->prev;//free(tail);//tail = NULL;ListErase(phead->prev);
}void ListPushFront(ListNode* phead, LTDataType x)//头插
{assert(phead);创建新结点//ListNode* newnode = BuyListNode(x);链接//ListNode* first = phead->next;//phead->next = newnode;//newnode->prev = phead;//newnode->next = first;//first->prev = newnode;ListInsert(phead, x);
}void ListPopFront(ListNode* phead)//头删
{assert(phead);assert(!ListEmpty(phead));//控制链表不能为空////ListNode* first = phead->next;//ListNode* second = phead->next->next;//phead->next = second;//second->prev = phead;//free(first);//first = NULL;ListErase(phead->next);
}ListNode* ListFind(ListNode* phead, LTDataType x)//查找(找出第一个x)
{assert(phead);//ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListInsert(ListNode* pos, LTDataType x)//在pos位置前面插入元素
{assert(pos);//创建新结点ListNode* newnode = BuyListNode(x);//插入pos->prev->next = newnode;newnode->prev = pos->prev;pos->prev = newnode;newnode->next = pos;
}void ListErase(ListNode* pos)//删除pos位置的元素
{assert(pos);//pos->prev->next = pos->next;pos->next->prev = pos->prev;//free(pos);//在函数外需要自行置空pos指针
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！