网站开发时ie11的兼容,做网站怎么弄,个人建站流程详解,昆明网上房地产官网数据结构之单链表
线性表
线性表的顺序存储结构#xff0c;有着较大的缺陷
插入和删除操作需要移动大量元素。会耗费很多时间增容需要申请空间#xff0c;拷贝数据#xff0c;释放旧空间。会有不小的消耗即使是使用合理的增容策略#xff0c;实际上还会浪费许多用不上的…数据结构之单链表
线性表
线性表的顺序存储结构有着较大的缺陷
插入和删除操作需要移动大量元素。会耗费很多时间增容需要申请空间拷贝数据释放旧空间。会有不小的消耗即使是使用合理的增容策略实际上还会浪费许多用不上的空间。如我只需要101个空间存放数据而100进行2倍增容后有200个空间这样实际上浪费了99块空间。
线性表的链式存储结构就可以解决这些问题首先链式存储结构并不需要增容而是使用多少数据申请多少空间这一点就避免了时间和空间的浪费。
顺序存储结构和链式存储结构
存储方式
顺序存储结构使用一段连续的空间依次存储数据链式存储结构使用一个个存储单元存放数据
时间性能 插入和删除 顺序存储结构O(N) 链式存储结构O(1)
空间性能
顺序存储结构需要预分配空间给小了不够用给打了浪费链式存储结构不需要预分配空间只要有新的元素插入才会开辟内存单元
使用场景
具体在什么场景使用不同的线性表存储结构呢 若线性表需要频繁的查找很少进行插入和删除操作时可以采用顺序存储结构。 若线性表中的元素个数变化较大或不知道有多大时可以采用链式存储结构。 单链表在插入和删除不需要移动元素只需改变指针的指向即可。
单链表
概念单链表是在物理存储结构上不连续逻辑结构上连续的线性表。它是通过指针链接就像火车的一节一节车厢一样通过挂钩链接在一起车厢就是单链表的一个一个节点里面用来存放数据。
而在单链表里“车厢”内有些什么的呢单链表是一种数据结构“车厢”里肯定存放在数据而单链表又是通过指针链接在以起就像车厢的钩子一样链接它在物理存储结构上不是连续的所以“车厢”里还有一个指针变量用来存放下一节“车厢”的地址。 typedef int SLNodeDatatpye;
struct SListNode
{SLNodeDatatpye data;//存放数据struct SListNode* next;//存放单链表类型的指针
};存放的数据类型单链表不会只用来存放整形数据这里只是以整形举例所以需要对类型重命名方便对后面的类型进行修改需要修改数据类型的只需要动动 typedef int SLNodeDatatpye;这串代码。 功能实现
typedef int SLNodeDatatpye;
struct SListNode
{SLNodeDatatpye data;struct SListNode* next;
};
typedef struct SListNode SL;//创建节点
SL* SLBuyNode(SLNodeDatatpye x);//打印
void SLPrint(SL** pphead);//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);//查找返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);//销毁链表
void SLDestory(SL** pphead);创建节点和打印
实现单链表的功能第一步需要为它创建节点以用来存放数据。实现打印功能将链表的数据打印出来方便更好的观查链表存储数据的情况配合着调试功能可以更加完善的查找观测在实现完一个功能它执行的结果是否与预期相符合若发生错误又可以借助调试功能更好、更快的查找bug。
//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{SL* newnode (SL*)malloc(sizeof(SL));if (newnode NULL){perror(malloc);return;}newnode-data x;newnode-next NULL;return newnode;//忘记返回newnode的地址了
}
//打印
void SLPrint(SL** phead)
{//assert(phead);SL* pcur phead;while (pcur)//pcur ! NULL{printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}创建节点很容易理解一个单链表的节点用来存放数据和下一个节点的地址在创建节点时使用malloc函数开辟一个内存单元然后判断开辟空间是否成功接着将传递过来的参数放在 newnode-data x;里。
newnode-next NULL;置为空即可这只是一个节点没有与其余节点有任何关联借助插入函数来实现像火车一样一节一节车厢链接在一起的效果。
打印单链表时应注意
循环体单链表的循环通过next指针来实现结束条件是最后一个节点的next指针为空。
pcur pcur-next;通过 pcur-next赋值给 pcur来来遍历每一个节点。重述将pcur的下一个节点的地址赋给pcur此时pcur就等于下一个节点直达循环到最后一个节点在最后一个节点data 4 pcur pcur-next;为空指针将其赋给 pcur此时它为空指针跳出循环。 查找数据
查找数据为什么传递二级指针这里是为了保持函数接口的一致性后续实现的插入、删除、销毁操作都需要传递二级指针同时也是减少对函数的混淆当函数量较多时这个函数传一级指针另一个函数传递二级指针四处分散容易让使用者看了傻眼~。
//查找返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{assert(*pphead pphead);SL* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}查找数据的基本的逻辑与打印类似都需要使用循环遍历链表 循环内增加了一个条件判断用于判断这个节点的数据是否等于形参x相等就说明找到了 “找到了”将当前节点的地址返回即可若跳出循环后还是没有找到对应的节点将返回NULL空指针。
assert断言是防止传递过来的链表的节点是空指针在函数内对进行解引用导致程序报错。
插入数据
在插入数据时需要考虑插入的数据会对影响那些节点
特别注意的一点插入数据会对单链表进行改变在传递参数的时候需要对取pliat的地址而plist又是一个指针变量所以函数需要使用二级指针来接收。
节点函数参数*plist(第一个节点)**ppheadplist(指向第一个节点的指针)*ppheadplist(指向第一个节点的指针的地址)pphead
void test()
{SL* plist NULL;SLPushFront(plist, 1);SLPushFront(plist, 2);
}//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{assert(pphead);SL* newnode SLBuyNode(x);newnode-next *pphead;*pphead newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{assert(pphead);if (*pphead NULL){*pphead SLBuyNode(x);}else{SL* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next SLBuyNode(x);}
}需要对头插、尾插分两种场景一是没有节点传递过来的是空链表二是有节点传递的不是空链表。
实现头插、尾插先认为传递的不是一个空链表基于此来实现然后对空链表的情况做出判断和处理。这样做会更容易上手先实现最主要的功能然后再检擦其完整性。
assert断言是防止传递过来的链表的节点是空指针在函数内对进行解引用导致程序报错。
头插
需要创建一个节点SL* newnode SLBuyNode(x);使用上述的函数创建一个新节点将其放在链表的第一个位置newnode-next *pphead; 将新插入的节点置为新的头(让*pphead指向新的节点)*pphead newnode;。 千万别忘了需要将*pphead置为新的头否则此时它指向的是下一个节点的位置会影响到后续对链表的操作。
**最后取特殊情况**当链表为空时上述头插是否支持。很明显我们将 *pphead NULL的情况带入头插函数SL* newnode SLBuyNode(x);第一步正常创建节点newnode-next *pphead;第二步正常由于只有一个节点所以 newnode-next NULL没有问题*pphead newnode;第三步将*pphead置为新的头这步没有问题也不存在对空指针解引用的情况。
最后通过运行代码观测 尾插
尾插同理也是将链表默认不为空的情况实现。
想要进行尾插首先得有一个指针指向最后一个节点然后将创建的新节点插入。定义一个指针pcur使用循环遍历到最后一个节点。跳出循环完成最后一步尾插代码~pcur-next SLBuyNode(x);。
当链表为空时这不就是头插吗这样我们使用一个if语句判断*pphead是否为空为空就调用头插函数不为空就循环到最后一个节点然后插入~
指定位置插入
指定位置插入实际上与尾插代码差别不大就改变了跳出while循环的的条件。
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{assert(pphead);assert(pos);SL* newnode SLBuyNode(x);SL* pcur *pphead;if (*pphead pos)//这不就是头插吗{newnode-next pos;*pphead newnode;}else{while (pcur-next ! pos){pcur pcur-next;}pcur-next newnode;newnode-next pos;}
}首先想要实现指定位置插入传入的链表和pos不可能为空使用一个assert断言进行判断。
同样将指定位置插入分为两种情况一是 *pphead pos 二是 *pphead pos
这里可以将pos看似空指针NULL那指定位置插入之前不就是尾插吗细节上不就是在 pos这个指针上处理它也很简单。
在指针pos之前插入数据会影响到的节点pcur pos 在pcur和pos之前插入newnodepcur newnode pos 这里需要将pcur和pos之间的”线“断开然后使 newnode-next pos;newnode-next pos;这不就完成了插入操作。
删除数据
在删除数据时需要考虑删除这个节点会影响到那些节点
删除数据需要注意的是 *pphead 和 pphead不能为空删除数据也不可能删除空函数里对空指针解引用也会报错。 头删
头删的逻辑简单一保存*pphead之后的节点 SL* pcur (*pphead)-next;二、然后释放第一个节点 free(*pphead);三、最后将 pcur 赋给 *pphead更新头节点的位置。
尾删
尾删需要考虑最后一个节点和最后一个节点之前的节点所以需要使用pdst指针指向倒数第二个节点以及pcur指针指向最后一个节点。在循环时以 pcur-next ! NULL为结束条件在循环体内要保证 pdst指针在pcur指针后这种做法保证了pdst指针在pcur指针后而pcur指针指向的也是最后一个节点。
SL* pdst *pphead; SL* pcur pdst-next; //头删
void SLPopFront(SL** pphead)
{assert(*pphead pphead);SL* pcur (*pphead)-next;free(*pphead);*pphead pcur;
}
//尾删
void SLPopBack(SL** pphead)
{assert(*pphead pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SL* pdst *pphead;SL* pcur pdst-next;while (pcur-next){pcur pcur-next;pdst pdst-next;}pdst-next NULL;free(pcur);pcur NULL;}
}指定位置删除数据
指定位置删除数据与指定位置插入数据类似与尾删也比较类似。首先想要指定位置删除数据 *pphead和pphead以及pos都不可能为空否则这还删什么?传递过来的东西都是空的。
删除指定位置的数据时需要从它会影响那些节点pos会影响到 pcur pos pos-next。
*pphead 刚好等于pos 的情况和 *pphead ! pos的情况。当 *pphead ! pos时 需要使用循环将定义的pcur指针指向pos之前的节点所以结束条件是 pcur-next ! pos 当跳出循环时开始销毁在销毁前需要将 pos-next;赋给 pcur-next否则直接删除pos节点无法将pso的后继节点与它前驱节点链接链表断开了~ 讲pcur与pos-next链接上后释放pos即可。
当*pphead pos时pos指向的时第一个节点的位置此时不就是头删吗这是直接调用头删函数就完成了。
//指定位置删除
void SLErase(SL** pphead, SL* pos)
{assert(*pphead pphead);assert(pos);SL* pcur *pphead;if (*pphead pos)//头删{//free(*pphead);//*pphead NULL;SLPopFront(pphead);}else{while (pcur-next ! pos){pcur pcur-next;}pcur-next pos-next;free(pos);pos NULL;}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{assert(pos-next pos);// pos pos-next pos-next--nextSL* del pos-next;// pos del del-nextpos-next del-next;free(del);del NULL;
}删除pos之后的节点逻辑简单与删除pos节点类似。第一步同样是需要考虑删除pos之后·的节点会影响到那些节点。
删除pos之后的节点会影响 pos pos-next pos-next--next这三个节点所以传递过来的 pos 和 pos-next不能为空否则就是对空指针解引用导致程序异常。
在删除时需要注意删除和将pos 与 pos-next–next链接的顺序 先链接在删除
将pos-next保存赋给del指针将pos与 del-next链接释放del指针
销毁链表
销毁链表需要使用free对每一个节点进行释放。
//销毁链表
void SLDestory(SL** pphead)
{//循环销毁所有节点assert(*pphead pphead);SL* pcur *pphead;while (pcur){SL* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}销毁链表需要对每一个节点进行释放而只使用一个指针pcur释放当前的节点就找不到下一个节点了这里需要使用两个指针。
一个指针用来释放pcur一个指针用来指向待释放之后的节点next。 当释放完pcur节点后更新pcur的位置 pcur next;用来释放下一个节点next指针也需要更新用来指向下一个节点 next pcur-next;用来对pcur进行更新。直到pcur指向空指针时释放完所有节点跳出循环。而 *pphead还没有置为空这时候时野指针最后一步 *pphead NULL;。
源码
SListNode.h
#pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef int SLNodeDatatpye;
struct SListNode
{SLNodeDatatpye data;struct SListNode* next;
};
typedef struct SListNode SL;//创建节点
SL* SLBuyNode(SLNodeDatatpye x);//打印
void SLPrint(SL* phead);//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);//查找返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);//不需要二级指针保证接口一直所以传递二级//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);//销毁链表
void SLDestory(SL** pphead);SListNode.c
#define _CRT_SECURE_NO_WARNINGS#include SListNode.h
//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{SL* newnode (SL*)malloc(sizeof(SL));if (newnode NULL){perror(malloc);return;}newnode-data x;newnode-next NULL;return newnode;
}//打印
void SLPrint(SL* phead)
{//assert(phead);SL* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{assert(pphead);SL* newnode SLBuyNode(x);newnode-next *pphead;*pphead newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{assert(pphead);if (*pphead NULL){*pphead SLBuyNode(x);}else{SL* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next SLBuyNode(x);}
}
//头删
void SLPopFront(SL** pphead)
{assert(*pphead pphead);SL* pcur (*pphead)-next;free(*pphead);*pphead pcur;
}
//尾删
void SLPopBack(SL** pphead)
{assert(*pphead pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SL* pdst *pphead;SL* pcur pdst-next;while (pcur-next){pcur pcur-next;pdst pdst-next;}pdst-next NULL;free(pcur);pcur NULL;}
}
//查找返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{assert(*pphead pphead);SL* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{assert(pphead);assert(pos);SL* newnode SLBuyNode(x);SL* pcur *pphead;if (*pphead pos){newnode-next pos;*pphead newnode;}else{while (pcur-next ! pos){pcur pcur-next;}pcur-next newnode;newnode-next pos;}
}
//指定位置删除
void SLErase(SL** pphead, SL* pos)
{assert(*pphead pphead);assert(pos);if (*pphead pos)//头删{//free(*pphead);//*pphead NULL;SLPopFront(pphead);}else{SL* pcur *pphead;while (pcur-next ! pos){pcur pcur-next;}pcur-next pos-next;free(pos);pos NULL;}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{assert(pos-next pos);// pos pos-next pos-next--nextSL* del pos-next;// pos del del-nextpos-next del-next;free(del);del NULL;
}//销毁链表
void SLDestory(SL** pphead)
{assert(*pphead pphead);SL* pcur *pphead;while (pcur){SL* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
