数据结构——链表

【本节内容】

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;
}

运行结果：