系列文章目录
前言
顺序表的问题及思考
问题:
- 中间/头部的插入删除,时间复杂度为O(N)
- 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
思考:
如何解决以上问题呢?下面给出了链表的结构来看看
一、链表的概念及结构
1.链表的概念
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
2.链表的结构
链表包括数据域和指针域:
数据结构中:
二、链表的种类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
- 单向、双向
- 带头、不带头
- 循环、非循环
4. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
5. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了
三、链表的实现
1.自定义链表结点struct SListNode
代码如下:
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data; //数据域
struct SListNode* next; //指针域
}SLTNode;
2.链表打印数据SListPrint
代码如下:
void SListPrint(SLTNode* plist)
{
assert(plist);
SLTNode* cur = plist;
while (cur !=NULL)
{
printf("%d--> ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
3.链表创建结点BuyListNode
代码如下:
SLTNode* BuyListNode(SLTDateType num) //创建一个结点
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
assert(node);
node->data = num;
node->next = NULL;
return node;
}
4.链表尾部插入数据SListPushBack
代码如下:
void SListPushBack(SLTNode** pplist, SLTDateType num) //尾部插入数据,会改变第一个结点,所以传二级指针
{
assert(pplist);
SLTNode* newnode = BuyListNode(num); //创建一个新结点
if (*pplist == NULL) //考虑当前一个结点都没有情况
{
*pplist = newnode;
}
else
{
SLTNode* tail = *pplist;
while (tail->next != NULL) //遍历找到尾结点
{
tail = tail->next;
}
tail->next = newnode; //把新结点的地址给前一个结点的指针
}
}
5.链表头部插入数据SListPushFront
代码如下:
void SListPushFront(SLTNode** pplist, SLTDateType num)
{
assert(pplist);
SLTNode* newnode = BuyListNode(num);
newnode->next = *pplist;
*pplist = newnode;
}
6.链表尾部删除数据SListPopBack
代码如下:
void SListPopBack(SLTNode** pplist)
{
//1.没有结点
//2.1个结点
//3.多个结点
if (pplist == NULL)
{
return;
}
else if ((*pplist)->next == NULL)
{
free(pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
7.链表头部删除数据SListPopFront
代码如下:
void SListPopFront(SLTNode** pplist)
{
if (*pplist == NULL)
{
return;
}
else
{
SLTNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
}
8.链表查找数据SListFindKey
代码如下:
SLTNode* SListFindKey(SLTNode* plist, SLTDateType num)
{
SLTNode* cur = plist;
while (cur != NULL)
{
if (cur->data == num)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
9.链表在pos位置之后插入数据SListInsertAfter
代码如下:
void SListInsertAfter(SLTNode* pos, SLTDateType num)
{
assert(pos);
SLTNode* newnode = BuyListNode(num);
newnode->next = pos->next;
pos->next = newnode;
}
10.链表在pos位置之前插入数据SListInsertBefore
代码如下:
void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDateType num)
{
assert(pos&&pplist);
SLTNode* newnode = BuyListNode(num);
if (pos == *pplist)
{
newnode->next = pos;
*pplist = newnode;
}
SLTNode* prev = NULL;
SLTNode* cur = pplist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = newnode;
newnode->next = pos;
}
11.链表在pos位置之后删除数据SListEarseAfter
代码如下:
void SListEarseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* cur = pos->next;
pos->next = cur->next;
}
}
总结
以上就是今天要讲的内容,本文仅仅简单介绍了链表的各种方法的实现,而链表提供了方法能使我们快速便捷地处理数据的函数和方法,我们务必掌握。另外,如果有需要源码的私信我即可。还有,,如果上述有任何问题,请懂哥指教,不过没关系,主要是自己能坚持,更希望有一起学习的同学可以帮我指正,但是如果可以请温柔一点跟我讲,爱与和平是永远的主题,爱各位了。