需要一个网站文创产品设计创意图片

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

需要一个网站,文创产品设计创意图片,wordpress 分类 php,上海基础微网站开发之前在顺序表那一篇文章中#xff0c;提到顺序表具有的缺点#xff0c;比如头插#xff0c;头删时间复杂度为O(n)#xff0c;realloc增容有消耗等。而在链表中#xff0c;这些问题将得到解决。所以在这一篇文章里#xff0c;我们将会讲解链表的定义与性质#xff0c;以及…  之前在顺序表那一篇文章中提到顺序表具有的缺点比如头插头删时间复杂度为O(n)realloc增容有消耗等。而在链表中这些问题将得到解决。所以在这一篇文章里我们将会讲解链表的定义与性质以及最简单的链表 – 单链表的结构以及基础方法的实现。 目录 1  链表 1 链表的概念 2 结点节点 3 链表结点的结构 4 链表的性质  2  单链表 1 单链表的头插、尾插 2 单链表的头删、尾删 3 单链表在指定位置之前、之后插入数据  重点一 链表 1  链表 1 链表的概念 链表是一种物理结构上非连续、非顺序的存储结构数据元素的逻辑结构通过链表中的指针链接 次序实现的 一个链表这里举例为单链表的逻辑结构如图所示 2 结点节点 从上面那个链表的结构的图来看结点就是指上面那个链表中每个独立存在的一个方块所以一个结点里面包含了两部分内容一个是这个结点里面存储的数据域另一个是指向在一个结点的指针域用来找到下一个结点然后这里的plist是一个指向链表中第一个结点的指针里面存储的是第一个结点的地址可以通过plist来找到后面的结点从结点的结构来看知道了plist也就是链表第一个结点的地址我们就可以顺着结点中的指针依次找到每一个结点。 3 链表结点的结构 上面知道了结点的定义结点的结构就很容易实现了就是一个保存结点数据的数据域还有一个指向下一个结点的指针 #typedef int ListDataType; typedef struct ListNode {ListDataType data;//结点数据struct ListNode* next;//指向下一个结点的指针 }ListNode; 4 链表的性质  1 由于链表每个结点都是独立的一块空间结点之间是通过指针连在一起所以链表在物理结构上不一定是连续的但是在逻辑结构上是连续的所以是属于线性表的2 每个结点是动态开辟的而动态开辟的空间都是在内存里一个叫做堆区的空间开辟的3 由于每个结点是独立申请的所以每个结点的物理地址不一定连续 重点二 单链表 2  单链表 单链表是链表的一种其结点的结构就是上面那个图那样每个结点里面就只有一个数据域还有指向下一个结点的指针域所以对于单链表来说只能通过前面的结点找到后面的结点是不能通过后面的结点找到后面的结点的。 单链表的结构 typedef int SLTDataType;//singal list node – 单链表结点typedef struct SListNode {SLTDataType data;//结点的数据struct SListNode* next;//指向下一个结点的指针 }SLTNode; 对于一个单链表来说它的基础方法有链表的头插头删尾插尾删打印查找在指定位置之前插入数据删除pos这里的pos是一个节点的地址结点在指定位置之后插入数据删除pos之后的节点 销毁链表同样我们先讲解每一种方法的画图实现之后再附上代码。 1 单链表的头插、尾插 既然是插入结点那么就肯定会需要新开辟一个结点而且只要插入结点就需要开辟新结点所以可以把开辟新结点写成一个函数buyNode开辟新结点的功能也很容易实现只要用malloc函数动态开辟出一个结点大小的空间然后再让结点的data值赋值为想要开辟新结点的值然后再让next指针为NULL就开辟出了一个新结点。 链表的头插的实现如图 但是我们在实现头插的过程中发现phead形参链表的头节点会改变指向会从指向旧链表的头节点改为指向插入的新结点要想让传过来的实参头插后链表新的首节点这里必须改变实参也就是原来链表头节点指针的指向形参改变影响实参所以这里必须传指针变量的地址也就是二级指针。 尾插的实现也类似如图 在第二步里面需要通过头节点来找到尾节点通过头节点找到尾节点的实现思路为先创建一个节点指针变量 ptail 指向首结点之后再让循环判断 ptail 的next指针为不为NULL如果不为NULL那就让ptail走向下一个结点注意这里判断条件不能是ptail为不为NULL如何是这个判断条件那么ptail就会走向NULL后面势必会造成对NULL指针的解引用代码为 SLTNode* ptail phead; while (ptail-next ! NULL) {ptail ptail-next; } 那么尾插是否需要传二级指针呢 其实不管是头插还是尾插都需要考虑一种特殊情形那就是链表为空的情况就是指向头结点的指针为NULL如果链表为空上面的两种情况都会造成对空指针的解引用所以如果链表为空那就让指向头节点的指针指向新开辟的结点newnode就可以了但是这里改变的只是形参所以如果想要让实参也变为指向newnode的指针就必须传指针的地址也就是二级指针了。这里如果看不懂的话可以看下面的代码理解一下。 所以上面找尾节点的代码应该为 //传过来的二级指针为SLTNode** pphead指向头节点的指针为pphead SLTNode ptail pphead; while (ptail ! NULL) {ptail ptail-next; } 2 单链表的头删、尾删 既然是删除结点那么就需要判断链表为不为空也就是判断传过来的指向首节点的指针为不为NULL如果为NULL就不能删除结点。 头删的过程如图 头删也需要注意传递的参数也需要是二级指针因为形参的改变要影响实参 。 尾删的过程如下 寻找prev和ptail的代码如下 //传过来的为二级指针**pphead SLTNode ptail *pphead, *prev NULL; while (ptail-next ! NULL) {prev ptail;ptail ptail-next; } 头删和尾删的时候需要注意一种极端情况那就是只有一个结点的情况(*pphead)-next NULL如果只有一个结点那么prev指针就是NULL指针那么就会出现NULL指针的解引用但是对于头删的代码来说就不会出现这种情况可以结合下面的代码。所以尾删只有一个结点的情况需要特殊处理其实删除只有一个结点的链表尾删和头删都是一样的所以链表只有一个结点时尾删也就是头删。 3 单链表在指定位置之前、之后插入数据  同样的既然是插入数据就需要和头插、尾插一样开辟新的节点这里与头插、尾插开辟新节点逻辑相同不再赘述。这里的位置指的是一个节点这里叫做pos节点那么实现逻辑如下图所示 在pos节点之前插入数据 找到pos节点之前的prev节点的逻辑类似于尾插中找到尾节点具体逻辑为先将prev节点指定为首节点如果prev的next指针不指向pos节点那就让prev走到它的next指针写成代码为 //pphead为首节点 SLTNode prev *pphead;while(prev-next ! pos) {prev prev-next; }我们来考虑一下特殊情况那就是如果pos节点就是首节点的话pos pphead如果继续按照这个逻辑的话prev节点是首届点而pos节点也是首节点那么prev的next指针始终不等于pos所以最终会造成对NULL指针的解引用所以如果pos是首节点这时候需要特殊处理一下仅需要调用一下头插的函数就可以了可以结合下面代码思考一下。 在pos节点之后插入数据 我们再来考虑一下特殊情况就是如果pos是尾节点的情况如果再按这个逻辑的话会发现是没有问题的不会出现对于NULL指针的解引用情况。但是有一个点需要注意就是在第二步里面一定要先让newnode的next指针先改变再让pos的next指针改变因为pos的next指针如果先改变的话那就找不到pos的下一个节点了且newnode会指向自己的。 还有就是我们可以看到在pos节点之后插入数据实现逻辑是没有用到首节点的所以对于该函数实现的时候只需要传pos参数和插入的数据 X 两个参数就可以了。 那么在指定位置之前和之后插入数据是否需要判断单链表是否为空呢实际上是不需要的因为在pos节点之前、之后插入数据就保证了该单链表是非空的所以只需要判断pos节点是否为NULL就可以了。 4 删除指定位置pos节点删除指定位置pos之后的节点 既然是删除节点那就需要判断链表是否为空判断逻辑与头删、尾删相同不再赘述这两个方法实现逻辑如下 删除pos节点 我们来考虑一下特殊情况那就是如果pos节点是首节点、尾节点时。如果pos是尾节点根据这个逻辑来实现的话发现是没有问题的但是如果pos是首节点那么根据我们之前找prev节点的逻辑会出现对NULL指针的解引用的所以pos是首节点的情况需要特殊处理一下只需要调用一下头删的代码就可以了。 删除pos节点之后的节点 该方法的实现时有一个地方需要注意就是要删除的节点也就是pos的下一个节点不能为NULL且该方法的实现只需要传递一个pos参数就可以了。 5 打印、查找、销毁 打印函数和查找函数的逻辑比较好实现只要遍历整个单链表然后打印每个节点的值或者比较节点的值要和查找的值相不相等就可以了如果查找到了就返回对应节点的地址如果没有查找到就返回NULL。 销毁链表也很简单只要从首节点开始遍历然后销毁每一个节点就可以了只不过需要注意在释放当前节点之前需要先把下一个节点的地址存起来避免找不到下一个节点了。 6 代码实现  SList.h #includestdio.h #includestdlib.h #includeassert.htypedef int SLTDataType;//singal list node – 单链表结点typedef struct SListNode {SLTDataType data;//结点的数据struct SListNode next;//指向下一个结点的指针 }SLTNode;//打印 void SLTPrint(SLTNode* phead); //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x); //头删 void SLTPopFront(SLTNode** pphead); //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); //尾删 void SLTPopBack(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTDataType** pphead, SLTNode* pos, SLTDataType x); //删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos之后的结点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SLTDestroy(SLTNode** pphead); SList.c文件 #includeSList.h//开辟结点的函数 SLTNode* buyNode(SLTDataType x) {SLTNode* newnode (SLTNode)malloc(sizeof(SLTNode));//开辟失败if (newnode NULL){perror(malloc fail\n);//打印错误信息exit(1);}newnode-data x;newnode-next NULL;return newnode; }//打印 void SLTPrint(SLTNode phead) {SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n); }//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);//传过来的不能是空指针if ((*pphead) NULL){pphead buyNode(x);}else{SLTNode newnode buyNode(x);//让新开辟的结点next指针指向链表第一个结点newnode-next *pphead;//再让指向第一个结点的指针指向新开辟的结点*pphead newnode;} }//头删 void SLTPopFront(SLTNode** pphead) {//传过来的指针不能为空并且链表不能为空assert(pphead pphead);//得先让首结点指向首结点的下一个结点要不然会成野指针SLTNode next (*pphead)-next;free(*pphead);*pphead next; }//尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//如果是空链表的话就让指针指向新的结点if (*pphead NULL){pphead buyNode(x);}//链表不为空得先找到尾节点else{SLTNode ptail pphead;while (ptail-next){ptail ptail-next;}//ptail为尾结点SLTNode newnode buyNode(x);ptail-next newnode;} } //尾删 void SLTPopBack(SLTNode** pphead) {//传过来的地址不能为NULL并且链表为空assert(pphead *pphead);//如果链表中只有一个结点那就是头删除if ((pphead)-next NULL){SLTPopFront(pphead);}else{//得先找到尾节点和尾节点的前一个结点SLTNode ptail pphead;SLTNode prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;} }//查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-data x)return pcur;pcur pcur-next;}return NULL; }//在指定位置之前插入数据 void SLTInsert(SLTDataType** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//如果pos节点就是首节点if (pos pphead){//头插SLTPushFront(pphead, x);}//如果pos不是首节点else{SLTNode prev pphead;SLTNode newnode buyNode(x);while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;} }//删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead *pphead);assert(pos);//如果pos节点是首节点if (pos pphead){SLTPopFront(pphead);}else{SLTNode prev pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}}//在指定位置之后插入数据 void SLTInsertAfter(SLTNode pos, SLTDataType x) {assert(pos);SLTNode* newnode buyNode(x);//一定得先让newnode-next pos-next//再让pos-next newnodenewnode-next pos-next;pos-next newnode; }//删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) {//pos的下一个结点不能为空否则不能删除assert(pos pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL; }//销毁链表 void SLTDestroy(SLTNode** pphead) {assert(pphead pphead);SLTNode pcur pphead;//先存下一个结点SLTNode next pcur-next;while (pcur){next pcur-next;free(pcur);pcur next;}pphead NULL; } test.c #includeSList.hvoid Test() {SLTNode plist NULL;测试头插/SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist);///测试头删//SLTPopFront(plist);/SLTPopFront(plist);SLTPopFront(plist);SLTPopFront(plist);///SLTPopFront(plist);//测试尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);//测试尾删/SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);///SLTPopBack(plist);//测试查找/* SLTNode* pfind SLTFind(plist, 10);if (pfind NULL){printf(没找到\n);}else{printf(找到了\n);}/SLTNode pfind SLTFind(plist, 1);if (pfind NULL){printf(没找到\n);}else{printf(找到了\n);}//测试在指定位置之前插入数据//可以测试在1,2,4节点之前插入数据//SLTInsert(plist, pfind, 5);//测试在指定节点之后插入数据//可以测试在1,2,4节点之后插入数据//SLTInsertAfter(pfind, 5);//测试删除pos节点//可以测试删除1,2,4节点//SLTErase(plist, pfind);//测试删除pos之后的节点//可以测试删除1,2,3之后的节点//SLTEraseAfter(pfind);//可以使用调试测试销毁是否成功//如果销毁成功下面打印结果就是NULLSLTDestroy(plist);//打印SLTPrint(plist); }int main() {Test();return 0; } 单链表是链表里面结构最简单的一种链表链表共分为8类在双向链表里面会讲解但是由于结构最简单所以遍历只能从头开始遍历且在方法实现中涉及的细节点很多。同时单链表中为什么传二级指针也需要自己理解。总之如果刚开始学习单链表并不会很容易理解但是一旦理解了相信会对指针的理解更加深刻。