苏州市姑苏区建设局网站,wordpress 加宽文章页,wordpress企业主体,网站甚而模板思维导图#xff1a; 一#xff0c; 链表
1.1节点的结构
链表是啥样的啊#xff1f;顾名思义链表就是一种用链子链接起来的表。那这种表是怎么样的啊#xff1f;
这样的呗#xff1a; 现在#xff0c;我们知道了链表的形状了。那我们该如何用编程语言来形成这一种形状…思维导图 一 链表
1.1节点的结构
链表是啥样的啊顾名思义链表就是一种用链子链接起来的表。那这种表是怎么样的啊
这样的呗 现在我们知道了链表的形状了。那我们该如何用编程语言来形成这一种形状呢
首先一个链表节点是这样的: 毫无疑问链表也需要存储一些数据不然要链表来干嘛)。而且链表还有一条尾巴当然这是为了形象而画出来的这条尾巴又要如何形成呢现在让我们来想一想尾巴的作用是什么啊当然是为了找到下一个节点啊那我们要找到下一个节点的话我们应该用什么去找呢当然是下一个节点的地址啊那放地址我们是不是应该要用指针啊那好,现在我们已经清楚的知道了这一个节点的结构组成了。画图如下 现在我们再往下推。首先我们这一个结构里面含有两种不同类型的数据。不同类型的数据应该用什么数据结构来存储呢明显是结构体。那我的指针指向的下一个节点是不是又是一个结构体或者空指针呢那这个指针是不是又可以定义为结构体指针呢答案是肯定的
经过以上分析现在我们就可以把代码写出来了
代码
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;//这里的typedef是为了在后面对这个结构体更好的使用 1.2节点的生成
现在我们已经把节点的结构搞明白了我们就要进入第二阶段了。我们要把上面的结构的节点生成一下。生成节点用什么啊malloc啊
生成节点代码
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));//动态开辟空间if (newnode NULL) {printf(malloc fail\n);return NULL;}newnode-data x;//在数据区内放入数据newnode-next NULL;//先置空指针区return newnode;//将新节点返回
}
1.3打印链表
打印链表该怎么做呢
其实很简单这样做就行了
代码:
void SListPrint(SListNode* plist) {SListNode* cur plist;while (cur) {printf(%d-, cur-data);cur cur-next;}printf(-NULL\n);//当链表为空的时候就打印一个NULL来提示一下
}
1.4在链表中插入数据 现在我们的链表的设计已经写好了但是这个链表是一个空链表。现在我们就要来给这个链表插入数据。当然插入数据的方法有很多种。像头插尾插中间插入等等……。现在我们就来一 一实现一下。
1.4.1头插 头插的方法就是生成一个新的节点然后让新的节点成为新的头节点连接*pplist。然后再移动*pplist的位置让它指向新的节点。 void SListPushFront(SListNode** pplist, SLTDateType x) {SListNode* newhead BuySListNode(x);newhead-next *pplist;*pplist newhead;
}
其实这里的头插逻辑基本上没有什么难度。但是这里使用一级指针还是二级指针才是需要花时间去理解的可以看到我们这里使用的是二级指针为什么呢一句话——“你要改变谁就要用谁的指针”。因为在test文件里面我用的是结构体的指针
SListNode* plist NULL;
所以我要改变外面的plist的话就要用plist的指针了因为指针的指针就是二级指针所以我这里就用了二级指针(解答完毕
1.4.2中间插入 先来讲一下我的中间插入的逻辑我的插入是在我要找到的数据的后一个位置插入所以找到位置很重要所以我会写一个查找数据位置的函数 代码;
SListNode* SListFind(SListNode* plist, SLTDateType x) {assert(plist);SListNode* pos plist;while (pos) {if (pos-data x) {return pos;//找到了就返回结束循环}pos pos-next;}printf(你要找的值不存在\n);return NULL;//找不到就返回空
} 写完了寻找节点的函数以后我们就可以来写一个中间插入的函数来。代码如下 void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);//要对pos断言一下因为这是中间插入链表中有节点才能中间插入SListNode* newnode BuySListNode(x);SListNode* next pos-next;//记录一下pos指向的下一个节点因为pos-next要被改变!pos-next newnode;newnode-next next;}
1.4.3尾插 尾插啥是尾插啊顾名思义尾插便是找到链表的尾巴然后再来插入具体的逻辑可以参见代码。 void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newtail BuySListNode(x);SListNode* tail *pplist;if (tail NULL) {//如果链表为空那就直接让*pplist指向newtail*pplist newtail;}else {while (tail-next) {//这里找的是尾节点所以当tail-next为空时就找到了尾节点了tail tail-next;}tail-next newtail;}
} 1.5在链表中删除节点 和链表的插入一样链表节点的删除也有三种。分别是头删尾删中间删除 1.5.1头删 头删顾名思义便是删除头节点。思路很简单就是调整一下plist的指向让plist指向下一个节点然后释放上一个节点就可以了。 代码
void SListPopFront(SListNode** pplist) {assert(pplist);//pplist不可能为空所以这里要预防一下assert(*pplist);//空链表不能删SListNode* del *pplist;*pplist (*pplist) -next;free(del);del NULL;
}
1.5.2中间删除 这个操作的实现也是需要和 SListFind搭配使用的前面我已经将 SListFind写好了。这里我就不再写了我在这里直接写中间删除的函数就好了。当然这个中间删除函数与前面的中间插入一样都只是删除中间的节点而不会删除头节点与尾节点。所以依照这个思路我们便可以将代码写出来 代码
void SListEraseAfter(SListNode* pos) {assert(pos);//中间删除不会删除头节点更不会删除不存在的值。assert(pos-next);//也不能删除空指针SListNode* del pos-next;pos-next del-next;free(del);del NULL;
}
1.5.3尾删 顾名思义尾删就是把链表的尾节点删除掉。删除的逻辑就是找到链表的尾节点的前面一个节点然后将这一个节点中的指向改为空。并把尾节点给释放掉。 代码
void SListPopBack(SListNode** pplist) {assert(pplist);//指针的地址不可能为NULLassert(*pplist);//空链表不能尾删if ((*pplist)-next NULL) {free(*pplist);*pplist NULL;}else {SListNode* tail *pplist;while (tail-next-next) {tail tail-next;}SListNode* del tail-next;tail-next NULL;free(del);del NULL;}
}
1.6销毁链表 因为我们的链表是malloc出来的一块一块的空间所以当我们的链表用完以后就要对这些一块一块的空间进行释放。说所以我们又要写一个函数来销毁链表。 代码
void SListDestroy(SListNode** pplist) {assert(pplist);assert(*pplist);//链表未创建不能销毁SListNode* cur NULL;while (*pplist) {cur (*pplist)-next;free(*pplist);*pplist cur;}*pplist NULL;printf(链表销毁成功!\n);
}
总结
到这里我们就已经把我能讲的一些关于链表的知识我所知道的关于链表的知识给讲完了。但是我还是想要总结一下 1.在我们要操作链表时比如想要增删时就要用二级指针。 2.当一个变量不可能为空指针时要对它进行assert断言。 3.当一个变量为空时会导致错误时也要对这个变量进行assert断言。 好了总结完毕
