当前位置： 首页 > news >正文

大丰做网站需要多少钱百度贴吧官网首页

news 2025/7/20 20:39:46
大丰做网站需要多少钱,百度贴吧官网首页,建网站 可以看到访客吗,做服装最好的网站目录 ​编辑 1. 顺序表的问题及思考 2.链表的概念结构和分类 2.1 概念及结构 2.2 分类 3. 单链表的实现 3.1 新节点的创建 3.2 打印单链表 3.3 头插 3.4 头删 3.5 尾插 3.6 尾删 3.7 查找元素X 3.8 在pos位置修改 3.9 在任意位置之前插入 3.10 在任意位置删除…

目录

​编辑

1.  顺序表的问题及思考

2.链表的概念结构和分类

2.1 概念及结构

2.2 分类

3. 单链表的实现

3.1 新节点的创建

3.2 打印单链表

3.3 头插

3.4 头删

3.5 尾插

3.6 尾删

3.7 查找元素X

3.8 在pos位置修改

3.9 在任意位置之前插入

3.10 在任意位置删除

3.11 单链表的销毁

4. 完整代码

5. 完结散花

                                            悟已往之不谏，知来者犹可追  

创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟

1.  顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

2.链表的概念结构和分类

2.1 概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。

2.2 分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单项或者双向

 2. 带头或者不带头

 3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

下面我就来实现一下无头单向非循环链表~

3. 单链表的实现

这里我就具体实现一下接口~（SList.h)

#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件被多次引用
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListDataType;//便于改变数据类型//定义一个结构体类型的节点
typedef struct SListNode
{SListDataType data;struct SListNode* next;//存储下一个节点的地址
}SListNode;//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x);//2. 打印单链表
void PrintSList(SListNode* phead);//3. 头插
void SListPushFront(SListNode** phead, SListDataType x);//4. 头删
void  SListPopFront(SListNode** phead);//5. 尾差
void SListPushBack(SListNode** phead, SListDataType x);//6. 尾删
void  SListPopBack(SListNode** phead);//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x);//8. 在pos位置修改
void SListModify(SListNode* pos, SListDataType x);//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x);//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos);//11. 销毁单链表
void SListDestroy(SListNode** phead);

3.1 新节点的创建

(1)代码实现

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间if (NewNode == NULL)//判断空间是否开辟成功{perror("malloc fail");return NULL;}NewNode->data = x;//赋值NewNode->next = NULL;//置空return NewNode;
}

3.2 打印单链表

(1)代码实现

//2. 打印单链表
void PrintSList(SListNode* phead)
{if (phead == NULL){printf("NULL");//如果链表没有元素就打印NULLreturn;}SListNode* cur = phead;//循环单链表打印while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

(2) 复杂度分析

  • 时间复杂度：因为需要遍历整个链表，显然时间复杂度为O(N)。
  • 空间复杂度：打印链表不需要格外的空间，所以空间复杂度为O(1).

3.3 头插

(1)代码实现

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{assert(phead);SListNode* newnode =SListCreatNode(x);//创建一个新节点newnode->next =*phead;*phead = newnode;
}

(2) 复杂度分析

  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.4 头删

(1)代码实现

//4. 头删
void  SListPopFront(SListNode** phead)
{assert(phead);assert(*phead);//如果没有数据就不用头删，并报错SListNode* cur = (*phead)->next;free(*phead);*phead = cur;
}

(2) 复杂度分析

  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.5 尾插

(1)代码实现

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{assert(phead);if (*phead == NULL){*phead = SListCreatNode(x);//创建新节点并插入}else{SListNode* tail = *phead;while (tail->next != NULL)//找到尾节点{tail = tail->next;}tail->next = SListCreatNode(x);//创建新节点并插入}
}

(2) 复杂度分析

  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.6 尾删

(1)代码实现

//6. 尾删
void  SListPopBack(SListNode** phead)
{assert(phead);assert(*phead);//链表为空就不进行尾删SListNode* tail = *phead;if (tail->next == NULL)//如果链表就只有一个元素就进行头删{SListPopFront(phead);}else{while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

(2) 复杂度分析

  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.7 查找元素X

(1)代码实现

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{assert(phead);while (phead->next!=NULL)//注意最后一个节点是没有查找的{if (phead->data == x)return phead;phead = phead->next;}if (phead->data == x)return phead;//最后一个节点没有查找elsereturn NULL;//没找到
}

(2) 时间复杂度

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.8 在pos位置修改

(1)代码实现


//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{assert(pos);pos->data = x;
}

(2) 时间复杂度

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.9 在任意位置之前插入

(1)代码实现

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{assert(phead);assert(*phead);if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插{SListPushFront( phead,x);}else{SListNode* newnode = SListCreatNode(x);SListNode* cur = *phead;while (cur->next != pos)//找到pos前一个节点{cur = cur->next;}cur->next = newnode;newnode->next  = pos;}
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.10 在任意位置删除

(1)代码实现

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{assert(phead && *phead && pos);if (pos==*phead)//如果pos位置就是第一个节点就进行头删{SListPopFront(phead);}else{SListNode* cur = *phead;while (cur->next != pos)//找到pos前一个节点{cur = cur->next;}cur->next = pos->next;free(pos);}
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.11 单链表的销毁

(1)代码实现

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{assert(*phead && phead);SListNode* cur = *phead;while (cur!= NULL){SListNode* tmp = cur->next;free(cur);cur = tmp;}*phead = NULL;
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

4. 完整代码

SList.c

#define _CRT_SECURE_NO_WARNINGS#include"SList.h"//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间if (NewNode == NULL)//判断空间是否开辟成功{perror("malloc fail");return NULL;}NewNode->data = x;//赋值NewNode->next = NULL;//置空return NewNode;
}//2. 打印单链表
void PrintSList(SListNode* phead)
{if (phead == NULL){printf("NULL");//如果链表没有元素就打印NULLreturn;}SListNode* cur = phead;//循环单链表打印while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{assert(phead);SListNode* newnode =SListCreatNode(x);//创建一个新节点newnode->next =*phead;*phead = newnode;
}//4. 头删
void  SListPopFront(SListNode** phead)
{assert(phead);assert(*phead);//如果没有数据就不用头删，并报错SListNode* cur = (*phead)->next;free(*phead);*phead = cur;
}//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{assert(phead);if (*phead == NULL){*phead = SListCreatNode(x);//创建新节点并插入}else{SListNode* tail = *phead;while (tail->next != NULL)//找到尾节点{tail = tail->next;}tail->next = SListCreatNode(x);//创建新节点并插入}
}//6. 尾删
void  SListPopBack(SListNode** phead)
{assert(phead);assert(*phead);//链表为空就不进行尾删SListNode* tail = *phead;if (tail->next == NULL)//如果链表就只有一个元素就进行头删{SListPopFront(phead);}else{while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{assert(phead);while (phead->next!=NULL)//注意最后一个节点是没有查找的{if (phead->data == x)return phead;phead = phead->next;}if (phead->data == x)return phead;//最后一个节点没有查找elsereturn NULL;//没找到
}//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{assert(pos);pos->data = x;
}//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{assert(phead);assert(*phead);if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插{SListPushFront( phead,x);}else{SListNode* newnode = SListCreatNode(x);SListNode* cur = *phead;while (cur->next != pos)//找到pos前一个节点{cur = cur->next;}cur->next = newnode;newnode->next  = pos;}
}//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{assert(phead && *phead && pos);if (pos==*phead)//如果pos位置就是第一个节点就进行头删{SListPopFront(phead);}else{SListNode* cur = *phead;while (cur->next != pos)//找到pos前一个节点{cur = cur->next;}cur->next = pos->next;free(pos);}
}//11. 销毁单链表
void SListDestroy(SListNode** phead)
{assert(*phead && phead);SListNode* cur = *phead;while (cur!= NULL){SListNode* tmp = cur->next;free(cur);cur = tmp;}*phead = NULL;
}

5. 完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

http://www.mmbaike.com/news/40936.html

相关文章：

  • 公司外贸网站建设兰州怎么提高网站的排名
  • 企业网站源码 可去版权最新seo自动优化软件
  • 沈阳网站建设信息自贡网站seo
  • 安徽省建设厅网站证书查询快照网站
  • dns劫持网站怎么做新闻源软文发布平台
  • ps做网站首页步骤手机优化器
  • 做商城网站要什么手续南昌seo数据监控
  • 做外贸哪个网站比较好淘宝关键词怎么做排名靠前
  • 东莞网站建设企业怎么写软文
  • 安卓系统是谁开发的广州seo实战培训
  • 电商培训课程虞城seo代理地址
  • wordpress 多用户seo网络优化是什么意思
  • 上海网站推广价格网络优化的基本方法
  • 腾讯的网站是谁做的网络营销策划书范文模板
  • u盘搭建网站开发环境方法谷歌外贸平台推广需要多少钱
  • 工作室网站建设费用价格深圳网络推广服务是什么
  • 小说网站建设个人网站制作多少钱
  • 代做网站转账截图十大销售管理软件排行榜
  • 重庆的企业的网站建设沈阳百度seo排名优化软件
  • 南宁做网站哪家好百度竞价排名推广
  • 中国建设网官方网站企业登录推广引流方法与渠道
  • apple开发者账号seo关键词优化外包
  • 网站后台发了文章看不到微信seo
  • 精彩 网站小程序开发公司十大排名
  • 深圳网站建设gseo指什么
  • 与做网站有关的参考文献网络引流怎么做啊?
  • 广州网站开发制作怎样才能注册自己的网站
  • 大朗镇仿做网站百度广告代理公司
  • 广西上林县住房城乡建设网站在线建站网页制作网站建设平台
  • 重庆哪家公司做网站好沈阳关键字优化公司