单链表逻辑结构梳理

1.1链表的概念及结构概念链表是一种物理存储结构上的非连续非连续的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的种类包含单向双向带头不带头循环非循环。在八种链表结构中最常用的包含无头单向非循环链表以及带头双向循环链表。无头单项非循环链表结构简单一般不会单独来存储数据。实际中更多是作为其他数据结构的子结构入哈希桶图的邻接表等等带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。虽然这个结构复杂但是使用代码以后会发现该结构会带来很多优势。在SList.h该文件中写文件声明以及结构体的定义#includestdlib.h #includeassert.h #includestdio.h //定义结点的结构 //数据指向下一个节点的指针 typedef int SLDataType; typedef struct SListNode { SLDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode*pphead); //尾插 void SLTPushBack(SLTNode**pphead, SLDataType x); //头插 void SLTPushFront(SLTNode**pphead, SLDataType x); void SLTPopBack(SLTNode** pphead); //头删 void SLPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode**pphead, SLTNode* pos, SLDataType x); //在指定位置之后插入数据 void SLTInsertAter(SLTNode* pos, SLDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); // 删除pos 之后的节点 void SLTEraseAfter(SLTNode * pos); void SListDesTroy(SLTNode** pphead);在这里使用typedef重新定义int类型在之后对于链表的使用如果存储其他类型的数据的时候就可以直接在这里修改定义变量的时候就使用SLDatatype。使用struct结构体成员变量分为data以及SListNode*next。前者是在链表节点中存储的数据而后者则是用来链接节点之间的桥梁。在具体解释各个接口之前要解释的是如何在使用之前创建节点SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode)); node1-data 1; SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode)); node2-data 2; SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode)); node3-data 3; SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode)); node4-data 4;//建立了四个节点并储存从1到4四个数字 //将四个节点连接起来 node1-next node2; node2-next node3; node3-next node4; node4-next NULL;在这里首先定义SLTNode*类型的node1变量该指针指向的是malloc后的空间的地址然后解引用该地址将成员变量data进行赋值将数据存储在节点中然后将节点链接在一起将后一个节点的地址赋值给前一个节点的成员变量next。链表数据的打印void SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur)//pcur!NULL{printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);}该接口使用传地址修改的方式然后将传参地址重新赋给一个新的SLTNode*pcur来接收地址避免对原地址进行修改。尾节点的next指针最终指向NULL所以在这里的while循环结束条件就是当pcur最终指向空然后是对pcur循环赋值更新不断将下一节点的地址赋值给pcur。对于创建新的节点以及赋值接口SLTNode* SLTBuyNode(SLDataType x) {SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//因为malloc返回的是申请的空间的地址要使用指针来进行解引用if (newnode NULL) {perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;}在这里SLTNode*是返回的值newnode的类型在这里先通过malloc 来在堆上然后再进行if判断新节点是否为空如果为空则证明申请空间失败通过perror来打印出错误。如果是exit0证明程序正常结束然后返回0给操作系统。如果是非0则程序异常退出告知系统运行错误。然后将传递的参数x赋值给这个新节点然后将next赋值为NULL,最后再返回这个新的指针的地址节点的尾插//在这里进行二级指针的传参有两方面的考虑一方面是为了防止出函数后堆内存销毁所以在这里要进行传地址plist传递的是这个给变量本身的地址然后*plist得到的就是这个节点的地址。//然而在这SLTNode**pphead是为了保证类型匹配 SLTNode* ptail *pphead;在这里*pphead就是SLTNode*类型从而实现类型匹配进行赋值运算void SLTPushBack(SLTNode** pphead, SLDataType x) {assert(pphead);//增加断言不能为空无法解引用空指针SLTNode* newnode SLTBuyNode(x);//申请新的 节点//SLTNode* newnode(SLTNode*)malloc(sizeof(SLTNode));//在这里定义插入新的节点//在这里先找到尾结点再将尾节点和新节点连接在一起//空链表和非空链表if (*pphead NULL) {*pphead newnode;}else{SLTNode* ptail *pphead;while (ptail-next ! NULL) {//在这里的循环判断表达式节点中储存的下一个结点的地址不为空ptail ptail-next;}//patil指向的就是尾节点ptail-next newnode;}}在这里使用二级指针传参一方面考虑的是类型匹配问题另一方面则是为了保证传地址修改。使用断言保证传参地址不为空然后使用SLTBuyNode函数来申请新的节点。接下来进行判断传参地址表示的是空链表还是非空链表如果是空链表就使得新节点作为该链表的头节点如果为非空链表则使用while循环来找到尾节点然后将新节点插入到尾节点之后。头插节点接口void SLTPushFront(SLTNode** pphead, SLDataType x) {assert(pphead);SLTNode* newnode SLTBuyNodex;//newnode *ppheadnewnode-next *pphead;//将新节点与原本的第一个节点相连接*pphead newnode;//在使得该指针指向第一个节点 在这里*pphead相当于一个用来遍历每一个节点的指针在这里插入新的节点后要使得这个指针指向头节点}在这里传参使用二级指针的目的与尾插的目的相同另外直接将新节点插入链表开头即将新节点的成员变量next储存*pphead该节点的地址使得插入节点与原头节点相连。在这里*pphead始终是指向头节点的指针变量所以对其进行重新赋值使其指向新的头节点。删除节点接口void SLTPopBack(SLTNode** pphead) {assert(pphead *pphead);//链表不能为空//链表只有一个节点if ((*pphead)-next NULL)//-的优先级高于*{free(*pphead);*pphead NULL;}else {SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next) {prev ptail;//在这里循环从前往后推移直到patil指向最后一个节点而prev为上一个节点ptail ptail-next;}//在这里prev为删除的那个节点的上一个节点中存储的地址因为最后一个节点被删除所以prev-next应该指向NULL//prev patil//释放free(ptail);ptail NULL;prev-next NULL;//在这里之所以要设置两个指针前后遍历因为在尾删这一块不仅仅是要free尾节点也要使得上一个节点的next为NULL,从而要得到尾节点的上一个节点的地址}}在这里断言链表不能为空且指向头节点的指针不能为空。然后使用if判断分支当链表只有一个节点的情况以及当链表不是只有一个节点的情况。当只有单个节点的时候直接将该节点free掉将堆上内存还回去。然后将指向头节点的指针置为空避免野指针的出现。当不是单个节点的情况下先定义两个SLTNode*类型的指针一个指向尾节点而另一个指向该尾节点的前一个节点具体操作逻辑是使用while循环终止条件是当ptail中的成员变量next为空。然后进行遍历循环从头节点开始。然后同样进行free将堆上内存释放再者将尾节点置为空将前一个节点的成员变量next置为空。头删接口void SLPopFront(SLTNode** pphead) {//既可以处理多节点的情况也可以处理单个节点的情况//链表不能为空assert(pphead *pphead);//在这里next只是一个临时的变量来存储指向第二个节点的地址SLTNode* next (*pphead)-next;//-优先级高于*free(*pphead);//在这里使得next中的地址转移给*pphead来作为头节点*pphead next;//使得*pphead指向第二个节点让第二个节点成为头节点}在这里为避免删除头节点之后而找不到新的链表的头节点的地址先定义一个指针来直线头节点的下一个节点然后将原头节点堆上空间释放。然后将指向头节点的指针指向新的头节点。节点查找接口SLTNode* SLTFind(SLTNode* phead, SLDataType x) {//在链表中查找节点中存储的数据SLTNode* pcur phead;//为了不修改phead这个指针因为在最后pcur最后会为空while (pcur)//等价于pcur!NULL;{if (pcur-data x) {return pcur;}pcur pcur-next;//在这里通过不断把下个节点的地址赋值给指针从而借助while循环实现遍历}//pcurNULL;在这里pcur可能最后为NULL,为此在这使用pcur指针代替指针phead;return 0;}//在这里**pphead是有可能值被改变的而pos是指拿来使用而不会被改变因为最后pcur会为空如果直接在原来指向头节点的指针上修改则会被修改所以在这里设置一个临时变量。使用while循环当节点中的成员变量正好等于数据x的时候就直接返回该节点的地址在循环过程中pcur指针是不断更新指向下一个节点的。当最终没有查找到对应的值的时候就直接结束。在指定的节点前插入新的节点的接口void SLTInsert(SLTNode** pphead,SLTNode *pos, SLDataType x) {assert(pphead *pphead);//在这里因为要找到对应的所要找到的节点的位置不为空assert(pos);SLTNode* newnode SLTBuyNode(x);//若pos*pphead;说明是头插if (pos *pphead) {SLTPushFront(pphead, x);}else{SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}//要让prev -newnode - pos 三者手牵手然后地址相连接newnode-next pos;prev-next newnode;}}同样在这里通过断言保证链表以及头节点指针不为空以及所查找的节点的地址不为空。然后使用if判断如果目标节点是头节点的情况下就直接调用头插函数如果不是头节点的情况下创建一个新的指针变量先储存头节点的地址避免对链表原头节点的地址进行修改。然后进行while循环来找到目标节点的前一个节点然后让该节点的成员变量next等于插入的新的节点的地址然后让该新节点的next保存目标节点的地址然后最后通过next串联起来使得三个节点实现了链接。在目标节点之后插入新的节点//在指定位置之后插入数据void SLTInsertAter(SLTNode* pos, SLDataType x)//为什么没有头节点{assert(pos);SLTNode* newnode SLTBuyNode(x);newnode-nextpos-next;pos-next newnode;}在这里先assert断言避免目标节点的地址为空然后创建一个新的节点使其成员变量next与目标节点的next相等表示为新的节点代替目标节点来指向下一个节点然后再将新的节点与目标节点相连pos-nextnewnode实现原目标节点与新节点的相连与目标节点的下一个节点的相连。删除节点操作接口void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead *pphead);//pos是头节点if (pos *pphead) {SLPopFront(pphead);}else {SLTNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}prev-next pos-next;free(pos);pos NULL;}}在该接口中传参头节点地址然后分支进行判断如果目标节点等于头节点就直接进行头删操作else则将头节点地址赋值给一个新的指针变量避免堆原头节点的地址的修改。然后通过while循环来遍历到目标节点的前一个节点。然后先将目标价节点的下一个节点的地址赋值给目标节点的前一个节点的成员变量next目的是将目标节点删除后依旧可以保证链表的连续性然后再进行空间释放操作以及赋空操作删除目标节点之后的节点的接口void SLTEraseAfter(SLTNode* pos) {assert(pos pos-next);SLTNode* del pos-next;//pos del del-next就相当于pos-next-nextpos-next del-next;free(del);del NULL;}删除目标节点先将目标节点下一个节点的地址赋值给新的指针变量来避免数据的丢失然后再将目标前一个节点的成员变量next被赋值为目标节点的下一个节点的地址实现节点直接的相连。在保证目标节点前后的节点相连后才能对目标节点进行空间释放及赋空。销毁链表操作接口void SListDesTroy(SLTNode** pphead) {assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur) {SLTNode* next pcur-next;free (pcur);pcur next;}//pcur*pphead NULL;//在这里使得头节点为空}在实现链表的销毁的操作过程中是节点逐个销毁的过程将后一个节点的地址赋值给新定义的相同类型的指针变量然后再对pcur这个指向节点的指针进行释放之后再将保留下一个节点的地址的next赋值给pcur来进行循环直到pcur指针为空则标志着销毁完成在进行free销毁后*pphead这个指向头节点的指针赋值为空避免野指针。结言对于单链表的解释和一些说法可能不够清楚犀利个人的见解和认识也是在数据结构的学习的开始时写的如果有错误和解释有误的地方欢迎指出