C/C++数据结构之链表函数实现与详细解析

数据结构之链表函数实现与详细解析"/>

C/C++数据结构之链表函数实现与详细解析

个人主页：点我进入主页

专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶

欢迎大家点赞，评论，收藏。

一起努力，一起奔赴大厂。

目录

1.前言

2.链表函数的实现

3.结语

1.前言

        在前面我们讲解了关于顺序表的内容，我们知道顺序表是在内存中开辟一块连续的空间，他在访问的时候很简单，但是在对数据进行增加删除时很困难，我们是不是有一种方式让数据的增加和删除变得容易，这时候我们可以直到链表，链表是数据以不连续的方式存储起来，链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链，接次序实现的，无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2.链表函数的实现

        在函数中包含结构体的创建，创建节点，头插，尾插，头删，尾删，插入，删除，节点空间释放。详细的代码如下：

typedef struct SLNode {int data;struct SLNode*  next;
}SLNode;
//创建节点
SLNode* CreateNode(int x)
{SLNode* p = (SLNode*)malloc(sizeof(SLNode));if (p == NULL){perror("malloc");return NULL;}p->data = x;p->next = NULL;return p;
}
//尾插
void STLPushBack(SLNode **phead,int x)
{assert(phead);SLNode* p = CreateNode(x);if (*phead == NULL){*phead = p;}else{SLNode* tail = *phead;while (tail->next != NULL){tail = tail->next;}tail->next = p;}
}
//头插
void STLPushFrount(SLNode** phead, int x)
{assert(phead);SLNode* newnode = CreateNode(x);newnode->next = *phead;*phead = newnode;
}
//尾删
void STLPopBack(SLNode** phead)
{assert(phead);if (!*phead){return;}if ((*phead)->next == NULL){free(*phead);*phead = NULL;}else{SLNode* prev = *phead;SLNode* cur = (*phead)->next;while (cur->next != NULL){prev = prev->next;cur = cur->next;}free(cur);prev->next = NULL;}
}
//头删
void STLPopFrount(SLNode** phead)
{assert(phead);if (*phead == NULL){return;}SLNode* prev = (*phead)->next;free(*phead);*phead = prev;}
//查找
SLNode* STLFind(SLNode* phead, int x)
{assert(phead);SLNode* cur = phead;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
//插入
void STLInsert(SLNode **phead,SLNode *pos,int x)
{assert(phead);assert(pos);if (*phead == NULL || *phead == pos){STLPushFrount(phead, x);}else{SLNode* prev = *phead;while (prev->next != pos){prev = prev->next;}SLNode* newnode = CreateNode(x);prev->next = newnode;newnode->next = pos;}
}
//删除
void STLErase(SLNode** phead, SLNode* pos)
{assert(phead);assert(*phead);assert(pos);if (pos == *phead){*phead = pos->next;free(pos);}else{SLNode* cur = (*phead)->next;SLNode* prev = *phead;while (cur != pos){cur = cur->next;prev = prev->next;}prev->next = cur->next;free(cur);}}
//空间释放
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

3.结语

        在这次文章中我们主要针对链表进行讲解，一下有几道题目可以帮助我们进行更加深入了解链表的应用。

1. 删除链表中等于给定值 val 的所有节点。OJ链接
2. 反转一个单链表。 OJ链接
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个
中间结点。OJ链接
4. 输入一个链表，输出该链表中倒数第k个结点。OJ链接
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成
的。OJ链接
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking