建设事业单位网站多少钱,昆明有多少做网站的公司,店面设计分析,单页wordpress主题本篇主要总结单链表是如何实现的#xff0c;数据结构是如何管理数据的#xff0c;详细的介绍每一步是如何实现以及各种注意事项。#x1f680;1.单链表的实现#x1f680;#x1f36d;1.1单链表的尾插#x1f36d;1.2单链表的头插#x1f36d;1.3单链表的打印#x1f3…
本篇主要总结单链表是如何实现的数据结构是如何管理数据的详细的介绍每一步是如何实现以及各种注意事项。1.单链表的实现1.1单链表的尾插1.2单链表的头插1.3单链表的打印1.4单链表的尾删1.5单链表的头删1.6单链表的查找1.7单链表的插入1.8单链表的删除1.单链表的实现
单链表能实现什么功能呢数据结构对数据的管理无外乎增删查改让我们一一实现它吧
#include stdio.h
#include stdlib.h
#include assert.htypedef int SLTData;//在单链表要使用的数据类型可根据需要改动
typedef struct SLTNode 重定义单链表类型名
{SLTData data;//单链表中结点一般都含有两个元素一个数据struct SLTNode* next;//一个指向该该结点类型的指针
}SLTNode;//结点
SLTNode* BuySLTNode(SLTData x);//生成新结点的函数
void SLTPrint(SLTNode* pphead);//单链表的打印
void SLTPushBack(SLTNode** pphead,SLTData x);//单链表的尾插
void SLTPushFront(SLTNode** pphead, SLTData x);//单链表的头插
void SLTPopBack(SLTNode** pphead);//单链表的尾删
void SLTPopFront(SLTNode** pphead);//单链表的头删
SLTNode* SLTFind(SLTNode** pphead, SLTData x);//单链表的查找
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTData x);//在pos位置前面插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//在pos位置之前删除
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTData x);//在pos位置之后插入
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//在pos位置之后删除1.1单链表的尾插
单链表的尾插。我们要注意到我们传给尾插函数的是二级指针也就是指向链表的指针的指针为什么要传二级指针呢 因为我们要在该函数内部修改指向链表的指针让它指向别的的地方去这就将它修改了要想将该变量真正的修改成功从内到外都要修改我们就得传它的指针不然在函数内部修改成功但在函数外部没有修改那又有什么用呢 其实这就是典型的形参的改变不影响实参只不过如果这里的实参是指向结点的指针然后尾插函数接收参数也是指向结点的指针那修改形参就无法改变实参必须将指向结点的指针的地址传过去然后用二级指针来接收这样对形参的修改才可以改变实参。 并且一开始我们还要进行对该二级指针断言防止有人传错指针又传入一级指针类型。
好让我们回到这个尾插函数。 尾插一个结点我们首先要需要生成一个新的结点newnode. 我们首先想前面有一系列结点而尾插只要在最后一个结点的后面接上即可这时我们需要是最后一个结点的地址。 所以我们需要找尾。注意找尾while里进行的条件是tail-next!NULL,这样才能找到最后一个结点 而不能写成while(tail!NULL),这样找到的不是最后一个结点而是最后一个结点的后面。
接着我们再分析如果前面没有结点那么直接将新生成的结点与指向链表的指针链接起来即可。
void SLTPushBack(SLTNode** pphead, SLTData x)//尾插
{assert(pphead);SLTNode* newNode BuySLTNode(x);//生成一个新结点//如果前面没有结点if (*pphead NULL){*pphead newNode;//直接将新结点赋给指向链表的指针}else{//假设前面有结点//找尾SLTNode* tail *pphead;while(tail-next! NULL){tail tail-next;//往后走}tail-next newNode;//最后将新结点与最后一个结点链接}
}1.2单链表的头插
单链表的头插。 首先对二级指针断言看是否合法 先假设前面有结点然后生成新结点进行头插。 头插就是将指向链表的指针一开始指向新结点再让原先第一个结点与新结点链接起来。 然后再假设前面没有结点分析没有结点和有结点都可以。
void SLTPushFront(SLTNode** pphead, SLTData x)//头插
{assert(pphead);//断言判断SLTNode* newNode BuySLTNode(x);//生成新结点//假设前面有结点.发现有结点和没有结点一样newNode-next *pphead;//将原先第一个结点与新结点链接起来*pphead newNode;//再让新结点与指向链表的指针连接起来
}1.3单链表的打印
单链表的打印。 其实本质也是循环打印只不过不同与顺序表的下标循环链表是没有顺序的根据结点的next来进行循环 我们一般不让形参改动而是重新将形参赋给给一个新元素这样使用起来更好因为如果在使用的过程中又需要头地址的地方就可以直接使用。 利用cur进行遍历。注意这里循环的条件是curNULL 而不能写成cur-next!NULL,如果写成这样那么最后一个元素就无法打印出来了因为最后一个结点的next就为NULL 到最后一个结点就结束了
void SLTPrint(SLTNode* phead)//打印单链表
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);//打印每个结点的数据cur cur-next;}printf(NULL\n);}1.4单链表的尾删
单链表的尾删。 我们要想删除数据就要进行判断是否删除过头每次删除之前都要进行断言判断一旦删除过头就立刻停止。 所以这里我们除了对二级指针断言之外还需要对指向链表的指针进行断言也就是一级指针对二级指针解引用即可。
首先我们假设前面有结点然后尾删也就是删除最后一个结点同时还需要将前一个结点的next置NULL 不然就变成野指针了。 这里有两种方法来找到前面一个结点的next。 一种是再定义一个指针prev来记录tail遍历链表的前面结点的位置。 最后tail找到尾结点释放tail再将prev的next置为NULL即可。
另一种是通过不去找真正的尾结点而实现。 也就是while(tail-next-next) 这里找的不是真正尾结点而是尾结点前面的。 最后释放tail-next即可 再将tail-next置为NULL.
接着就是假设前面只要一个结点时该怎么删呢直接释放即可。
void SLTPopBack(SLTNode** pphead)//尾删
{assert(pphead);//暴力检查是否删过头assert(*pphead);//假设前面只有一个结点时。if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* tail *pphead;SLTNode* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}1.5单链表的头删
头删与尾删一样都需要对二级指针和一级指针进行断言判断。 假设前面有结点进行头删就是让指向链表的指针指向第二个结点将第一个结点删除掉。
假设前面没有结点分析发现都适用。
void SLTPopFront(SLTNode** pphead)//头删
{assert(pphead);assert(*pphead);//暴力检查//假设前面只有一个结点//和//假设前面有结点SLTNode* first *pphead;*pphead first-next;//将第二个结点与指向链表的指针链接free(first);//删除第一个结点first NULL;}1.6单链表的查找
单链表的查找就是根据所给的数据进行遍历没有什么好的方法 如果与给的数据相同则返回该地址。如果找不到就返回NULL。
通常查找与修改连在一起先查找到该结点的数据然后对该数据进行修改。
SLTNode* SLTFind(SLTNode** pphead, SLTData x)//查找
{assert(pphead);SLTNode* cur *pphead;while (cur){if (cur-next x){return cur;}cur cur-next;}return NULL;
}1.7单链表的插入
与上面的讲的单链表的头插和尾插不一样这里讲的是给定位置pos然后将数据插入想要插入的位置不过对于单链表的插入通常都是在位置pos的前面插入数据而不是在pos的后面插入数据我们分别来看看这两种插入的不同
在pos前面插入就想要pos前面结点的地址了并且遍历循环的条件也发生变化。 插在pos的前面 1.如果链表有结点那我们将新结点与pos位置前面的结点链接起来再让pos与新结点链接起来。
如果没有结点就相当于头插了。
2.插在pos的后面
插在后面都不要遍历找了直接将新结点放在pos的后面将pos的next与新结点链接再将新结点与pos链接
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTData x)//在pos位置前面插入
{assert(pphead);assert(pos);//如果没有结点if (pos *pphead){SLTpushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySLTNode(x);prev-next newnode;newnode-next pos;}
}
void SLTInsertAfter( SLTNode* pos, SLTData x)//在pos位置之后插入
{assert(pos);SLTNode* newnode BuySLTNode(x);newnode-next pos-next;pos-next newnode;
}
1.8单链表的删除
单链表的删除分为在pos位置的前面删除还是在后面删除 不过首先都需要对二级指针和一级指针断言。 1.在pos位置之前删除 假设前面有结点删除pos前面的结点需要前面结点位置的地址 找到后将该结点点释放。
假设前面只有一个结点相当于头删。
2.在pos位置之后删除 首先要将pos后面的结点的位置记录下来 然后将后面的结点与pos链接起来将pos后面的结点释放
void SLTErase(SLTNode** pphead, SLTNode* pos)//在pos位置之前删除
{assert(pphead);assert(pos);if (*pphead pos){SLTpopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev-next pos-next;}free(pos);pos NULL;}
}void SLTEraseAfter( SLTNode* pos)//在pos位置之后删除
{assert(pos);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}
文章转载自： http://www.morning.gqfjb.cn.gov.cn.gqfjb.cn http://www.morning.phlrp.cn.gov.cn.phlrp.cn http://www.morning.dnzyx.cn.gov.cn.dnzyx.cn http://www.morning.rgfx.cn.gov.cn.rgfx.cn http://www.morning.jzxqj.cn.gov.cn.jzxqj.cn http://www.morning.qrndh.cn.gov.cn.qrndh.cn http://www.morning.xsklp.cn.gov.cn.xsklp.cn http://www.morning.lddpj.cn.gov.cn.lddpj.cn http://www.morning.ybhjs.cn.gov.cn.ybhjs.cn http://www.morning.trrhj.cn.gov.cn.trrhj.cn http://www.morning.dfffm.cn.gov.cn.dfffm.cn http://www.morning.kyjyt.cn.gov.cn.kyjyt.cn http://www.morning.gwdkg.cn.gov.cn.gwdkg.cn http://www.morning.jwqqd.cn.gov.cn.jwqqd.cn http://www.morning.mfmrg.cn.gov.cn.mfmrg.cn http://www.morning.nwgkk.cn.gov.cn.nwgkk.cn http://www.morning.zympx.cn.gov.cn.zympx.cn http://www.morning.bkfdf.cn.gov.cn.bkfdf.cn http://www.morning.npbnc.cn.gov.cn.npbnc.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.wnjbn.cn.gov.cn.wnjbn.cn http://www.morning.bnylg.cn.gov.cn.bnylg.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.kfrhh.cn.gov.cn.kfrhh.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.rcntx.cn.gov.cn.rcntx.cn http://www.morning.jfgmx.cn.gov.cn.jfgmx.cn http://www.morning.mrfjr.cn.gov.cn.mrfjr.cn http://www.morning.xbptx.cn.gov.cn.xbptx.cn http://www.morning.ffdyy.cn.gov.cn.ffdyy.cn http://www.morning.zkrzb.cn.gov.cn.zkrzb.cn http://www.morning.mbpfk.cn.gov.cn.mbpfk.cn http://www.morning.hmbxd.cn.gov.cn.hmbxd.cn http://www.morning.xczyj.cn.gov.cn.xczyj.cn http://www.morning.lmrjn.cn.gov.cn.lmrjn.cn http://www.morning.bpyps.cn.gov.cn.bpyps.cn http://www.morning.jbqwb.cn.gov.cn.jbqwb.cn http://www.morning.lmfmd.cn.gov.cn.lmfmd.cn http://www.morning.kpfds.cn.gov.cn.kpfds.cn http://www.morning.lmdkn.cn.gov.cn.lmdkn.cn http://www.morning.rlwgn.cn.gov.cn.rlwgn.cn http://www.morning.sqlh.cn.gov.cn.sqlh.cn http://www.morning.qczjc.cn.gov.cn.qczjc.cn http://www.morning.lthgy.cn.gov.cn.lthgy.cn http://www.morning.pxmyw.cn.gov.cn.pxmyw.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.rgsnk.cn.gov.cn.rgsnk.cn http://www.morning.tnwgc.cn.gov.cn.tnwgc.cn http://www.morning.ysmw.cn.gov.cn.ysmw.cn http://www.morning.fgkrh.cn.gov.cn.fgkrh.cn http://www.morning.nytqy.cn.gov.cn.nytqy.cn http://www.morning.htjwz.cn.gov.cn.htjwz.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.qnyf.cn.gov.cn.qnyf.cn http://www.morning.jxzfg.cn.gov.cn.jxzfg.cn http://www.morning.tgtwy.cn.gov.cn.tgtwy.cn http://www.morning.tdxnz.cn.gov.cn.tdxnz.cn http://www.morning.rfbq.cn.gov.cn.rfbq.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.hlxxl.cn.gov.cn.hlxxl.cn http://www.morning.lxwjx.cn.gov.cn.lxwjx.cn http://www.morning.psxfg.cn.gov.cn.psxfg.cn http://www.morning.zgdnz.cn.gov.cn.zgdnz.cn http://www.morning.rknsp.cn.gov.cn.rknsp.cn http://www.morning.htqrh.cn.gov.cn.htqrh.cn http://www.morning.rtbhz.cn.gov.cn.rtbhz.cn http://www.morning.cwgn.cn.gov.cn.cwgn.cn http://www.morning.mwpcp.cn.gov.cn.mwpcp.cn http://www.morning.lnyds.cn.gov.cn.lnyds.cn http://www.morning.xnqjs.cn.gov.cn.xnqjs.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn http://www.morning.tpnx.cn.gov.cn.tpnx.cn http://www.morning.lctrz.cn.gov.cn.lctrz.cn http://www.morning.qieistand.com.gov.cn.qieistand.com http://www.morning.fqpgf.cn.gov.cn.fqpgf.cn http://www.morning.tztgq.cn.gov.cn.tztgq.cn http://www.morning.zhishizf.cn.gov.cn.zhishizf.cn http://www.morning.mpmtz.cn.gov.cn.mpmtz.cn http://www.morning.hpnhl.cn.gov.cn.hpnhl.cn http://www.morning.bgzgq.cn.gov.cn.bgzgq.cn
