网站开发流程三大部分广东智能网站建设哪家有

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

网站开发流程三大部分,广东智能网站建设哪家有,质监站网址,网店代运营公司方案关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表#xff0c;顺序表支持下标随机访问而且高速缓存命中率高#xff0c;然而可能造成空间的浪费#xff0c;同时增加数据时多次移动会造成效率低下#xff0c;那有什么解决之法呢#xff… 关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表顺序表支持下标随机访问而且高速缓存命中率高然而可能造成空间的浪费同时增加数据时多次移动会造成效率低下那有什么解决之法呢这就得引入我们链表这种数据结构 文章目录 一.何为链表 链表概念 链表的分类 二.单链表的实现 链表的打印 链表的头插和尾插 链表的尾删和头删 链表指定位置的插入和删除 链表的查找 链表的销毁注 这里要保存好下一个结点地址销毁后就能继续遍历 三.单链表的分析以及与顺序表的比较 单链表的优缺点 单链表与顺序表的比较 一.何为链表 链表概念 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。 特点物理结构不一定连续逻辑结构连续 我们的链表结构类似我们的火车有头有尾中间每个结点被有序链接与火车不同的是链表的结点可能不是紧挨着的。 类似这样我们可以得出 1.每个结点由数据和下一结点地址两部分组成而每个结点构成了一个链表。 2.每个结点保存的是下一个结点的地址这样就能找到下一个结点最后为空就停止 3.每个结点的地址不是连续的可以体现出链表的物理结构不一定连续 注我们的结点一般是在堆区开辟的因为此时你在程序结束前不free就会一直存在这块空间同时可根据需要灵活申请结点存数据。 这样我们就可以用一个结构体封装每个结点 typedef int Datatype; typedef struct ListNode {Datatype x;struct ListNode* next; }Node;注 这里我们可以用typedef来重命名我们要存储的数据类型这样对于不同数据的操作我们只要改typedef即可。 链表的分类 我们根据链表三个特点1.带头不带头 2.单向还是双向 3.循环还是不循环 组合成了如上的8种链表 本篇博客我们要实现的是单向不带头不循环链表单链表至于什么是带头双向循环我们下回双链表再进行讲解 二.单链表的实现 无头单向不循环链表的增删差改 链表的打印 链表数据的打印 这个接口就很好的体现了结点结构保存指针的妙处了~ //链表的打印 void SLTPrint(Node* phead) {asser(phead);Node* cur phead;while (cur){printf(%d , cur-x);cur cur-next;} }链表的头插和尾插 链表的尾插 对于链表的尾插要注意几个问题1.申请新结点 2.链表是否为空 解决方法1.对于链表为空直接让申请的新节点作为头节点 2.对于不为空的链表首先要找到尾结点再进行插入 3.对于申请新节点我们后续的头插也要使用我们可以封装成一个接口同时结点在堆区申请调用完接口就不会释放了。 //申请新节点 Node* BuyNode(Datatype x) {Node* newnode (Node)malloc(sizeof(Node));if (newnode NULL){perror(malloc failed);return;}newnode-next NULL;newnode-x x;return newnode; }void SLTPushBack(Node** pphead, Datatype x) {assert(pphead);//申请新节点Node newnode BuyNode(x);//链表为空if (NULL *pphead){pphead newnode;return;}//链表不为空1.找尾巴结点2.插入新节点Node ptail pphead;while (ptail-next){ptail ptail-next;}ptail-next newnode; }思考这里为什么传二级指针如果不传二级指针呢 void SLTNPushBack(Node pphead, Datatype x) {//申请新节点Node* newnode BuyNode(x);//链表为空if (NULL pphead){pphead newnode;return;}//链表不为空1.找尾巴结点2.插入Node* ptail pphead;while (ptail-next){ptail ptail-next;}ptail-next newnode; } int main() {Node* n1 NULL;SLTNPushBack(n1,1);return 0; }经过观察传一级指针版本的调用前后我们发现n1这个指针变量存储的值并没发生改变究其原因如下图
链表的头插 , *对于链表的头插要注意的问题1.申请新节点 2.链表释放为空 * 解决方法1.链表为空时申请的新结点作为头结点 2.链表不为空时让newnode-next指向原来头节点,再让newnode成为新的头节点。 void SLTPushFront(Node** pphead, Datatype x) {assert(pphead);//申请新节点Node* newnode BuyNode(x);//链表为空if (NULL *pphead){*pphead newnode;return;}newnode-next *pphead;*pphead newnode; }链表的尾删和头删 链表的尾删 对于链表的尾删我们需要分三种情况 1.链表为空时此时删不了直接退出 2.链表只有一个结点时释放头节点置phead为空 3.链表有多个结点时我们需要遍历链表找到尾结点的前置结点先释放尾节点再将前置结点的next置为空 注不能先将前置结点的next置为空再释放尾结点此时就找不到尾结点的地址了。 //链表的尾删和头删 void SLTPopBack(Node** pphead) {assert(pphead);assert(*pphead);//判断链表不为空if ((*pphead)-next NULL){free(*pphead);pphead NULL;return;}Node pre *pphead;while (pre-next-next){pre pre-next;}free(pre-next);pre-next NULL; }链表的头删 对于链表的头删分为两种情况就可以了因为有了phead很方便~ 1.链表为空时删不了直接断言下 2.链表不为空时记录头节点的下一个位置先释放头节点再更换phead指向的位置 注这里也不能先更新phead再释放头结点 void SLTPopFront(Node** pphead) {assert(pphead);assert(pphead);Node pNext (*pphead)-next;free(*pphead);pphead pNext; }链表指定位置的插入和删除 1.链表为空时无法插入 2.pos位置结点刚好是头结点直接头插或头删 3.pos位置结点不是头节点需要找到pos位置的前置结点记录位置。 void NodeInpos(Node** pphead, Node pos, Datatype x) {assert(pphead);//pos不为空 -》 链表一定不能为空assert(pos);assert(pphead);//建立一个新节点Node newnode BuyNode(x);//pos刚好是头结点的情况if (pphead pos){//运用头插NodeinFront(pphead,x);return;}//pos刚好不是头结点//1.先找出pos前面的结点pre 2.newnode-next pre-next 3.pre-next newnodeNode pre pphead;while (pre-next ! pos){pre pre-next;}newnode-next pre-next;pre-next newnode; }void NodeDelpos(Node** pphead, Node pos) {assert(pphead);assert(pos);assert(*pphead);//pos刚好是第一个结点 执行头删if (pphead pos){NodeDelFront(pphead);return;}//pos不是第一个结点 1.先找到那个pos前面结点pre 2.pre-next pos-next 3.freeNode pre pphead;while (pre-next ! pos){pre pre-next;}pre-next pos-next;free(pos);pos NULL; }链表的查找 Node NodeFind(Node** phead, Datatype x) {assert(phead);//遍历链表Node* pcur *phead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//找不到则返回NULL }这里建议用一个临时变量来遍历~ 链表的销毁 void NodeDestroy(Node** pphead) {assert(pphead);assert(pphead);//1.创一个临时变量存pcur-next的地址Node pcur pphead;while (pcur){Node next pcur-next;free(pcur);pcur next;}*pphead NULL; }注 这里要保存好下一个结点地址销毁后就能继续遍历 三.单链表的分析以及与顺序表的比较 单链表的优缺点 通过实现我们的单链表我们发现单链表有以下优点 1.单链表不存在空间浪费(根据需求灵活在堆上申请新结点) 2.单链表的任意插入和删除效率高 分析: 这里是已经确定插入的位置对于链表只需改变指针的指向就能实现插入和删除时间复杂度是O(1)而数组插入和删除需要遍历数组时间复杂度是O(N) 单链表也不是万能的它在一些应用场景也发挥不出来作用 1.不支持随机访问 2.缓存命中率低 3.查找效率低 总结链表适用于频繁任意插入和删除的场景不适用于随机访问和查找 单链表与顺序表的比较 单链表顺序表物理空间不一定连续物理空间一定连续不支持随机访问支持下标随机访问插入和删除效率高 O(1)插入和删除效率低 O(N)缓存命中率低缓存命中率高无空间的浪费可能造成数据丢失和空间浪费缓存利用率高 综上 我们可以根据场景需求选择不同的结构灵活运用数据~ 本次分享到这结束了下篇我们将讲解双向链表不妨来个一键三连捏