链表的引入
对于顺序表存在一些缺陷:
中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素
增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间
对于链表而言,能够避免上述问题的出现。头部插入数据不需要挪动大量的数据,按需申请释放空间,不会造成空间的浪费。
链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
现实中 数据结构中(箭头实际上并不存在,这里只是形象化):
链表的种类有很多
以下情况组合起来就有8种链表结构:
单向或者双向 :
带头或者不带头:
循环或者非循环:
面对这么多种类的链表,我们该如何选择?虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了
话不多说,直接进入我们单链表的实现:
单链表的接口我们需要实现:
-
打印销毁
-
头插尾插创建新结点(由于后面会频繁使用,故将其封装成函数)
-
尾删头删查找
-
在pos之前插入、在pos之后插入
-
删除pos、删除pos之后的位置
我们还是老样子,通过三个部分组成:
**SList.h:**包括头文件的引用,结构体的声明定义,接口函数的声明。
**SList.c:**对SList.h中接口函数进行实现。
**test.c:**主函数进行测试:通过void TestSList()函数对SList.c的函数进行调用,测试有没有错误。
注意:对于一些问题的所在,我已经通过注释进行相关说明。注释才是精髓。
SList.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SLTNode* next;
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//创建新结点
SLTNode* BuySLTNode(SLTDataType x);
//销毁
void SListDestory(SLTNode** pphead);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SLTNode**pphead);
//头删
void SListPopFront(SLTNode**pphead);
//查找
SLTNode* SListFind(SLTNode* pphead,SLTDataType x);
//在pos之前插入
void SListInsert(SLTNode** pphead,SLTNode*pos,SLTDataType x);
//在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos
void SListErase(SLTNode** pphead,SLTNode*pos);
//删除pos后面位置,了解
void SListEraseAfter(SLTNode* pos);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//打印
void SListPrint(SLTNode* phead)
{
//phead不需要断言。因为phead有可能有空,没有数据
//而顺序表的结构体不可能为空,所以要进行断言
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//创建新结点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("mail fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//销毁
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾插——有无结点。需要找前一个
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
//空,改变的是SListNode*,需要二级指针
//非空。尾插要改变的是结构体SListNode,只需要结构体的指针
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//尾删——有无结点。需要找前一个
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
/*while (tail->next->next!=NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;*/
}
}
//头删
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
/*if (*pphead == NULL)
{
return;
}*/
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
assert(pphead);
SLTNode* cur = pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos之前插入,需要找前一个
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
assert(prev);
}
prev->next = newnode;
newnode->next = pos;
}
}
//在pos后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos位置,需要找前一个
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//检查pos不是链表中的结点
assert(prev);
}
prev->next = pos->next;
free(pos);
}
}
//删除pos后面位置
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//头插、头删
void TestSList1()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListDestory(&plist);
}
//尾插、尾删
void TestSList2()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListDestory(&plist);
}
//查找、在pos之前插入
void TestSList3()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
//修改
pos->data *= 10;
printf("找到了\n");
}
else
{
printf("找不到\n");
}
pos = SListFind(plist, 1);
if (pos)
{
SListInsert(&plist, pos, 10);
}
SListPrint(plist);
SListDestory(&plist);
}
//删除pos位置、删除pos后面的位置
void TestSList4()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
pos = SListFind(plist, 1);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
}
int main()
{
//TestSList1();
//TestSList2();
//TestSList3();
TestSList4();
return 0;
}
以上就是单链表的相关操作,我们不难发现,单链表的优势在于头插头删
而对于一些操作:如尾插尾删而言,我们都需要去找前一个位置,这是比较麻烦的。单链表我们就先介绍到这里了。
这里同时也有一个问题存在:
删除当前位置我们需要去找前一个位置,这效率是比较低的,我们如何改进这个问题❓
找pos位置删除,而就是不找前一个位置(即要求是O(1)):替换法删除,把pos的值和下一个节点的值进行交换,再把pos进行释放掉。但是有一个缺陷:pos不能是尾节点。尾节点没有下一项。
那如果在pos位置之前插入,要求为O(1)呢:
直接插入到pos后面,然后进行交换。
总结
- 我们从链表的引入开始,了解了为什么链表会出现,同时认识了链表的概念和结构。本篇博客主要介绍了单链表的操作,以及解决了一个问题。本次就先到这里结束了。