太原网站建设公司招聘,不定期更新域名,wordpress点赞 1,o2o商城网站开发目录
1. 顺序表的缺陷
2. 单链表
2.1 单链表的基本结构与接口函数
2.2 重要接口
创建新节点的函数#xff1a;
2.2.1 尾插
2.2.2 头插
2.2.3 尾删
2.2.4 头删
2.2.5 查找
2.2.6 插入
2.2.7 删除
2.2.8 从pos后面插入
2.2.9 从pos后面删除
3. 链表的缺陷与优势
2.2.1 尾插
2.2.2 头插
2.2.3 尾删
2.2.4 头删
2.2.5 查找
2.2.6 插入
2.2.7 删除
2.2.8 从pos后面插入
2.2.9 从pos后面删除
3. 链表的缺陷与优势
4. 链表与顺序表比较
写在最后 1. 顺序表的缺陷
为什么会有链表
我们都有顺序表来存储数据了
因为顺序表是有缺陷的
1. 中间头部插入删除数据需要挪动数据效率低下。
2. 空间不够需要扩容扩容会有一定的消耗也可能会造成空间的浪费。
这时候我们就要用到链表。
2. 单链表
链表是一种物理存储结构上非连续、非顺序的存储结构
数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
如下图 2.1 单链表的基本结构与接口函数
基本结构
#pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;//打印链表
void SLPrint(SLNode* phead);//尾插
void SLPushBack(SLNode** pphead, SLDataType x);//头插
void SLPushFront(SLNode** pphead, SLDataType x);//尾删
void SLPopBack(SLNode** ppheadx);//头删
void SLPopFront(SLNode** pphead);//查找
SLNode* SLFind(SLNode* phead, SLDataType x);//插入
void SLInsert(SLNode** phead, SLNode* pos, SLDataType x);//删除
void SLErase(SLNode** phead, SLNode* pos);//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x);//从pos后面删除
void SLEraseAfter(SLNode* pos);2.2 重要接口
创建新节点的函数
//建立一个新节点重复操作写成函数复用
SLNode* BuyNewNode(SLDataType x)
{//malloc一个链表节点大小的空间SLNode* newnode (SLNode*)malloc(sizeof(SLNode));//检查if (newnode NULL){perror(malloc::fail);return;}//赋值newnode-data x;newnode-next NULL;return newnode;
}
2.2.1 尾插
//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{//检查二级指针pphead地址是否为空 //方便检查是否传空指针了assert(pphead);//创建节点SLNode* newnode BuyNewNode(x);//如果链表为空if (*pphead NULL){*pphead newnode;}else//如果链表不为空{//找尾SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}//尾插tail-next newnode;}
}2.2.2 头插
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{//检查二级指针pphead地址是否为空 //方便检查是否传空指针了assert(pphead);//创建节点SLNode* newnode BuyNewNode(x);//头插newnode-next *pphead;*pphead newnode;
}
2.2.3 尾删
//尾删
void SLPopBack(SLNode** pphead)
{//检查二级指针pphead地址是否为空 //方便检查是否传空指针了assert(pphead);//检查链表是否为空assert(*pphead);//头删的情况链表只有一个数据if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//找尾SLNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}//尾删free(tail-next);tail-next NULL;}
}
2.2.4 头删
//头删
void SLPopFront(SLNode** pphead)
{//检查二级指针pphead地址是否为空 //方便检查是否传空指针了assert(pphead);//检查链表是否为空assert(*pphead);//头删SLNode* cur (*pphead)-next;free(*pphead);*pphead NULL;*pphead cur;
}
2.2.5 查找
//查找
SLNode* SLFind(SLNode* phead, SLDataType x)
{//创建指针遍历链表SLNode* cur phead;//查找while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
2.2.6 插入
//插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{//检查查找的地址是否为空assert(pos);//pos的位置if (pos *pphead){SLPushFront(pphead, x);}else//在链表中间{SLNode* prev *pphead;//查找pos对应位置while (prev-next ! pos){prev prev-next;}//插入SLNode* newnode BuyNewNode(x);prev-next newnode;newnode-next pos;}
}
2.2.7 删除
//删除
void SLErase(SLNode** pphead, SLNode* pos)
{//检查二级指针pphead地址是否为空 //方便检查是否传空指针了assert(pphead);//检查查找的地址是否为空assert(pos);//检查链表是否为空这里其实不断言也可以assert(*pphead);//头删的情况if (*pphead pos){SLPopFront(pphead);}else{//查找SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//删除prev-next pos-next;free(pos);pos NULL;}
}
2.2.8 从pos后面插入
//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{//检查查找的地址是否为空assert(pos);//创建节点SLNode* newnode BuyNewNode(x);//再pos后面插入newnode-next pos-next;pos-next newnode;
}
2.2.9 从pos后面删除
//从pos后面删除
void SLEraseAfter(SLNode* pos)
{//检查查找的地址和要删除的地址是否为空assert(pos);assert(pos-next);//在pos后面删除prev记住要删除的节点然后freeSLNode* prev pos-next;pos-next prev-next;free(pos-next);prev NULL;
}
这就是单链表的基本框架和接口了
如果感兴趣你也可以使用接口函数玩一玩。
3. 链表的缺陷与优势
但是链表是有缺陷的
我们可以看到
1. 链表想要访问一个节点就得遍历链表
2. 链表的尾删也需要遍历链表
3. 而链表的优势是头删很方便是O(1)。
4. 链表与顺序表比较
我们就能跟顺序表比较一下
1. 顺序表头插需要挪动数据是O(N)
2. 但是顺序表能随机访问。
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
