系列文章目录：【算法与数据结构（C语言）】线性表-----链表?http://t.csdn.cn/sL6c6
目录
前言
线性表分两部分，先前一篇文章内容先是写述了顺序表概念结构以及算法实现，本篇文章内容讲述了链表的概念结构、分类与函数声明部分，对于各个函数的实现。
以下内容仅供参考，欢迎各位大佬批评指正呦~
提示：以下是本篇文章正文内容，下面案例可供参考
?一、线性表的链表?
?1.概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
? ? ? ? ? ? ? ? ? ? ? ? ? ??
?2.链表的分类
（1）单项或双向
（2）带头或不带头
（3）循环或非循环
?3.链表的实现?
// 1、无头+单向+非循环链表增删查改实现 typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个结点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x // 分析思考为什么不在pos位置之前插入？ void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 // 分析思考为什么不删除pos位置？ void SListEraseAfter(SListNode* pos);
?1.SListNode* BuySListNode(SLTDateType x)
?
SListNode* BuySListNode(SLTDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
?2.void SListPrint(SListNode* plist)
?
void SListPrint(SListNode* phead) { SListNode* cur = phead; while (cur != NULL) { //printf("[%d|%p]->", cur->data, cur->next); printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
?注：typedef关键字为一种数据类型（包括自定义的数据类型（struct等））定义一个新的名字，可用来简化一些比较复杂的类型声明。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
?3.void SLTPushBack(SLTNode** pphead, SLTDataType x)
?
void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; // 找尾 while (tail->next) { tail = tail->next; } tail->next = newnode; } }
?4.void SLTPushFront(SLTNode** pphead, SLTDataType x)
?
void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }
5.?void SLTPopBack(SLTNode** pphead)
?
void SLTPopBack(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; } }
6.?void SLTPopFront(SLTNode** pphead)
?
void SLTPopFront(SLTNode** pphead) { assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
7.?SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
?
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
8.?void SLTInsertAfter(SLTNode* pos, SLTDataType x)
?
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; }
9.?void SLTEraseAfter(SLTNode* pos)
?
void SLTEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SLTNode* nextNode = pos->next; //pos->next = pos->next->next; pos->next = nextNode->next; free(nextNode); //nextNode = NULL; } }
4.双向链表的实现
// 2、带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* next; struct ListNode* prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* plist); // 双向链表打印 void ListPrint(ListNode* plist); // 双向链表尾插 void ListPushBack(ListNode* plist, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* plist); // 双向链表头插 void ListPushFront(ListNode* plist, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* plist); // 双向链表查找 ListNode* ListFind(ListNode* plist, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的结点 void ListErase(ListNode* pos);
1.?ListNode* ListCreate()
2.?void ListDestory(ListNode* plist)
可借鉴单链表，在此处省略。
3.?void LTPrint(LTNode* phead)
?
void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
4.?void LTPushBack(LTNode* phead, LTDataType x)
?
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
5.?void LTPopBack(LTNode* phead)
?
void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; tailPrev->next = phead; phead->prev = tailPrev; free(tail); }
6.?void LTPushFront(LTNode* phead, LTDataType x)
?
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* first = phead->next; // phead newnode first phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
7.?void LTPopFront(LTNode* phead)
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTErase(phead->next); }
8.?LTNode* LTFind(LTNode* phead, LTDataType x)
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
9.?void LTInsert(LTNode* pos, LTDataType x)
?
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyListNode(x); // prev newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
10.?void LTErase(LTNode* pos)
?
void LTErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; free(pos); prev->next = next; next->prev = prev; }
?二、顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定 连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要 扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
最后
快乐的时光总是短暂的，以上就是今天要讲的内容，本文继续简单介绍了小赵同志对算法与数据结构（C语言）的链表的初步认知以及实现。欢迎家人们批评指正。小赵同志继续更新，不断学习的动力是宝子们一键三连的支持呀~
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
总结
提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。