网站建设的分析,石家庄网站到首页排名,换服务器后网站首页不收录,上海本地app推荐#x1f60a;W…Y#xff1a;个人主页 在学习之前看一下美丽的夕阳#xff0c;也是很不错的。 如果觉得博主的美景不错#xff0c;博客也不错的话#xff0c;关注一下博主吧#x1f495; 在上一期中#xff0c;我们说完了顺序表#xff0c;并且提出顺序表中的问题 1. 中… W…Y个人主页 在学习之前看一下美丽的夕阳也是很不错的。 如果觉得博主的美景不错博客也不错的话关注一下博主吧 在上一期中我们说完了顺序表并且提出顺序表中的问题 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢 今天的链表就会解决这些顺序表中出现的问题。那什么是链表呢
目录
链表
链表的概念及结构
链表的分类
无头(无哨兵位)单链表实现
单链表结构
创建节点 打印链表内容
头插
尾插
头删 尾删
查找需要内容具体位置
其他功能 链表
链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
链表如同小火车一节与一节相关联 注意 1.链式结构在逻辑上是连续的但在物理上不一定连续。 2.节点都是从堆上申请的。 3.从堆上申请空间是按一定策略分配的申请的空间可能连续可能不连续。 假设在32位系统上结点中值域为int类型则一个节点的大小为8个字节则也可能有下述链表
链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 下面就是对无哨兵位单链表实现
无头(无哨兵位)单链表实现
单链表结构
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
使用typedef将int 与结构体重命名更好的使用清晰定义next指针需要指向下一个结构的地址方便链接。
单链表是只有一个指针指向后面节点当头部指针向后移动时就找不到前面的节点了所以在创建单链表时我们要创建一个结构体指针变量固定在头位置确保这个单链表完整性 我们在主函数中创建SLTNode* plist NULL; plist要等于链表中的第一个结构体的地址防止找不到链表的头部。 创建节点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
} 将需要存放的数据传入创建节点函数使用malloc在堆中创建需要的空间。在这里我们必须对创建的空间进行检测是否创建成功否则直接将退出程序。
创建出的空间也是结构体我们需要给data赋需要存储的数据将next赋值为空否则将成为野指针。将创建好的空间进行返回即可。 打印链表内容
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
创建一个可以遍历的指针进行逐一遍历打印即可。
头插
头插在进行过程中一定会改变plist指向的节点无论链表是否为空过程都是相同的所以我们在头插时一定会改变指针plist指向的内容所以这是我们就得传入plist的地址进行调用修改这时我们就得使用二级指针进行操作。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
先将*pphead指向的空间赋给新创建的空间中的next再使用二级指针将头指针的内容修改为新空间的地址即可。
尾插
在创建尾插函数时我们就要考虑链表是否为空当我们在链表为空时进行尾插就必须改变头指针所以尾插这个函数应该分情况进行
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);if (*pphead NULL){//改变的结构体的指针所以要用二级指针*pphead newnode;}SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}//改变的为结构体所以用一级指针tail-next newnode;
} 再往后插入就不需要对头指针做动作了。 所以这里我们一定要把问题想周全要不然程序就会报错甚至直接崩溃。
头删
void SLTPopFront(SLTNode** pphead);
{assert(*pphead);SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
} 头删时我们应该先创建一个临时指针指向需要释放的空间如果直接释放空间我们就使链表直接“断裂”找不到下一个节点地址。
当我们进行头删时需要判断链表是否为空链表再进行释放。在头删时头指针的地址就应该指向下一个节点地址我们应该提前进行标记在释放完成后将下一个节点地址再次付给头指针即可。 尾删
尾删和尾插都要考虑很多尾删要考虑两种情况1.只有一个节点2.有很多节点。当只剩最后一个节点时我们删除时就要改变头指针将头指针置空。我们一般使用两个指针一个指向尾节点一个指向尾节点前一个节点。当尾节点释放后我们使用另一个指针将其next置空即可。
void SLTPopBack(SLTNode** pphead)
{assert(*pphead NULL);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}
} 假设只剩最后一个节点 在空链表时我们一定要进行判断assert(*pphead)防止出错。
查找需要内容具体位置
当我们想要知道我们存储的数据在哪个位置时我们就需要进行查找返回其地址即可
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* find phead;while (find){if (find-data x)return find;find find-next;}printf(没找到\n);return NULL;
}
这里我们依旧使用暴力查找法进行逐一对比查找
单链表的基本功能我们已经形成我们已经完成了头插、尾插、头删、尾删。单链表的基本内容和注意事项已经强调。我们其实还可以继续完善单链表使其功能更加强大在这里博主就不过多的说明了其中的原理和注意事项和前面差不多。
现在我将剩下一些功能逐一展现供大家参考
其他功能
//在pos之前插入x
void SLTNInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
在pos之前插入x
void SLTNInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead pos);SLTNode* newnode BuySListNode(x);SLTNode* find *pphead;SLTNode* finding NULL;if (*pphead pos){newnode-next *pphead;*pphead newnode;return;}elsewhile (find ! pos){finding find;find find-next;}finding-next newnode;newnode-next find;
}
在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}
删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(ppheadpos);SLTNode* find *pphead;SLTNode* finding NULL;while (find ! pos){finding find;find find-next;}if (*pphead pos){SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;}else{finding-next find-next;free(find);find NULL;}
}
删除pos之后的数据
void SLTErasetAfter(SLTNode* pos)
{assert(pos);if (pos-next NULL){printf(后面没有数可以删除\n);return;}else{pos-next pos-next-next;free(pos);pos NULL;}
}以上就是复现无头单链表的全部内容有兴趣的可以继续打磨添加一些新功能。
本期内容到这里就结束了觉得博主内容有用的关注一下博主一健三连是对博主最大的鼓励再次感谢大家观看
