Lei宝啊：个人主页

愿所有美好不期而遇

---

---

 

前言：

 

接下来我们将会了解最基础的链表--->单链表

以及最方便也是最爽的链表--->带头双向循环链表。

 

 若有看不懂之处，可画图或者借鉴这里：反转单链表，对于数据结构而言，无非就是增删查改，当我们能够熟练应用以及画图后，其OJ题和以下代码都是小卡拉米。

 

无头单向不循环链表

单链表图：

 

头文件：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int DataType;typedef struct STLNode
{DataType data;struct STLNode* next;
}STLNode;void STL_Print(STLNode* phead);
void STL_PushBack(STLNode** pphead, DataType x);
void STL_PushFront(STLNode** pphead, DataType x);
void STL_PopBack(STLNode** pphead);
void STL_PopFront(STLNode** pphead);
STLNode* STL_Find(STLNode* phead, DataType x);
void STL_InsertAfter(STLNode* pos, DataType x);
void STL_EraseAfter(STLNode* pos);
void STL_Destroy(STLNode** pphead);

Test文件：

#include "STLNode.h"void Test1(STLNode* phead);int main()
{STLNode* plist = NULL;Test1(plist);return 0;
}void Test1(STLNode* phead)
{STL_PushBack(&phead, 1);STL_PushBack(&phead, 2);STL_PushBack(&phead, 3);STL_Print(phead);STL_PushFront(&phead, 11);STL_PushFront(&phead, 22);STL_PushFront(&phead, 33);STL_Print(phead);STLNode* ret = STL_Find(phead, 1);STL_InsertAfter(ret, 666);STL_Print(phead);STL_EraseAfter(ret);STL_Print(phead);STL_Destroy(&phead);STL_Print(phead);//STL_PopBack(&phead);//STL_PopBack(&phead);//STL_Print(phead);//STL_PopFront(&phead);//STL_PopFront(&phead);//STL_Print(phead);}

函数源文件：

对于以下函数中部分有对phead和pphead的检查，部分没有，原因是这样的：

对于是否需要对其进行断言，我们是要看他为NULL时合不合理，合理就不断言，不合理就断言，例如STL_Printf函数中，当phead为NULL时，说明该链表是空的，直接打印NULL就可以，这是很合理的。而对于STL_PushBack函数来说，phead为NULL同样合理，因为phead为NULL我们尾插其实也就相当于头插，很合理，但是对于pphead来说，他作为plist的地址，就算plist为NULL，pphead是不应该为NULL的，所以他为NULL就非常不合理，我们要对其进行断言检查。

#include "STLNode.h"void STL_Print(STLNode* phead)
{while (phead){printf("%d->", phead->data);phead = phead->next;}printf("NULL\n");}STLNode* Malloc(DataType x)
{STLNode* temp = (STLNode*)malloc(sizeof(STLNode));if (temp == NULL){perror("malloc fail");exit(-1);}temp->data = x;temp->next = NULL;return temp;
}void STL_PushBack(STLNode** pphead, DataType x)
{assert(pphead);STLNode* temp = Malloc(x);if (*pphead == NULL){*pphead = temp;}else{STLNode* cur = *pphead;while (cur->next != NULL){cur = cur->next;}cur->next = temp;}
}void STL_PushFront(STLNode** pphead, DataType x)
{assert(pphead);STLNode* temp = Malloc(x);temp->next = *pphead;*pphead = temp;}void STL_PopBack(STLNode** pphead)
{assert(pphead);assert(*pphead);STLNode* cur = *pphead;STLNode* temp = *pphead;if (cur->next == NULL){free(cur);*pphead = NULL;}else{while (cur->next){temp = cur;cur = cur->next;}free(cur);temp->next = NULL;}}void STL_PopFront(STLNode** pphead)
{assert(pphead);assert(*pphead);STLNode* cur = *pphead;*pphead = (*pphead)->next;free(cur);}STLNode* STL_Find(STLNode* phead, DataType x)
{if (phead == NULL){printf("NULL\n");return;}while (phead != NULL){if (phead->data == x){return phead;}phead = phead->next;}printf("Can not find\n");return;
}void STL_InsertAfter(STLNode* pos, DataType x)
{assert(pos);STLNode* temp = Malloc(x);temp->next = pos->next;pos->next = temp;}void STL_EraseAfter(STLNode* pos)
{assert(pos);assert(pos->next);STLNode* cur = pos->next;pos->next = pos->next->next;free(cur);
}void STL_Destroy(STLNode** pphead)
{assert(pphead);if (*pphead == NULL){return;}STLNode* temp = *pphead;STLNode* cur = *pphead;while (temp){cur = temp->next;free(temp);temp = cur;}*pphead = NULL;
}

---

---

 

带头双向循环链表

图：

 

头文件：

这个链表最爽的地方在于，他可以很轻松地找到尾，不管是尾插还是头插都非常爽，非常方便，如果我们想在半小时内写完这个链表，那么就可以对尾插和头插复用LTInsert函数，对于尾删和头删复用LTErase函数,也就是说，这两个函数是核心函数，有了他们，迅速写完该链表成为现实。

尾插的复用：LTInsert(phead,x);

头插的复用：LTInsert(phead->next,x);

尾删的复用：LTErase(phead->prev);

头删的复用：LTErase(phead->next);

​​#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int DataType;typedef struct LTNode
{DataType data;struct LTNode* prev;struct LTNode* next;
}LTNode;LTNode* Init();
LTNode* Malloc(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);
void LTPrintf(LTNode* phead);
void LTPushBack(LTNode* phead, DataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, DataType x);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, DataType x);   //在pos位置前插入节点
void LTErase(LTNode* pos);                //删除pos位置节点
void LTDestroy(LTNode* phead);

 Test文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "LTNode.h"void Test1();int main()
{Test1();return 0;
}void Test1()
{LTNode* plist = NULL;plist = Init();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPushBack(plist, 6);LTPrintf(plist);LTPopBack(plist);LTPopBack(plist);LTPopBack(plist);LTPrintf(plist);LTPushFront(plist, 10);LTPushFront(plist, 20);LTPushFront(plist, 30);LTPrintf(plist);LTPopFront(plist);LTPrintf(plist);LTNode *pos = LTFind(plist, 10);LTInsert(pos, 66);LTPrintf(plist);LTErase(pos);LTPrintf(plist);LTDestroy(plist);plist = NULL;}

函数源文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "LTNode.h"LTNode* Malloc(DataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;return newnode;
}LTNode* Init()
{LTNode* newnode = Malloc(0);newnode->next = newnode;newnode->prev = newnode;return newnode;
}void LTPrintf(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}putchar('\n');
}void LTPushBack(LTNode* phead, DataType x)
{assert(phead);LTNode *newnode = Malloc(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* newtail = tail->prev;newtail->next = phead;phead->prev = newtail;free(tail);
}void LTPushFront(LTNode* phead, DataType x)
{assert(phead);LTNode* newnode = Malloc(x);LTNode* old_next = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = old_next;old_next->prev = newnode;}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);
}LTNode* LTFind(LTNode* phead, DataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}printf("nothing!\n");return NULL;
}void LTInsert(LTNode* pos, DataType x)
{assert(pos);LTNode* newnode = Malloc(x);LTNode* posprev = pos->prev;posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* 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(cur);
}