营口网站seo_河北保定疫情最新情况_首页优化排名_cms网站

1 概念与结构

1.1 结点

1.2 链表的性质

2 实现单链表

2.1打印SLPrint

2.2申请一个结点SLBuyNode

2.3尾插SLPushBack

2.4头插SLPushfront

2.5尾删SLPopBack

2.6头删SLPopfront

2.7查找结点位置SLFindNode

2.8在pos位置插入SLInsert

2.9在pos节点之后插入SLInsertAfter

2.10删除pos位置的结点SLErase

2.11删除pos位置之后后的结点SLEraseAfter

2.12销毁链表SLDestory

3.整体代码

1 概念与结构

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.1 结点

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点” 结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。图中指针变量head保存的是第⼀个结点的地址，我们称head此时“指向”第⼀个结点，如果我们希望 head“指向”第⼆个结点时，只需要修改head保存的内容为0x0012。链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

1.2 链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

结点对应的结构体代码：

struct SListNode
{int data; //结点数据struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。

2 实现单链表

这里也是先建三个文件，SList.h,SList.c,test.c,分别为头文件，实现函数的文件，测试文件

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;typedef struct SLNode
{SLDataType data;struct SLNode* next;
}SLNode;void SLPrint(SLNode* phead);
SLNode* SLBuyNode(SLDataType x);void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushfront(SLNode** pphead, SLDataType x);
void SLPopBack(SLNode** pphead);
void SLPopfront(SLNode** pphead);SLNode* SLFindNode(SLNode* phead, SLDataType x);
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
void SLInsertAfter( SLNode* pos,SLDataType x);
void SLErase(SLNode** pphead, SLNode* pos);
void SLEraseAfter(SLNode* pos);
void SLDestory(SLNode** pphead);

包括了结构体SLNode表示结点，这里有一个结构体自引用，用来找到下一个结点位置，以及实现的各种函数这里typedef的SLDataType，便于后续修改数据类型，这里以int类型为例。

2.1打印SLPrint

void SLPrint(SLNode* phead)
{SLNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

这里定义一个指向头结点的指针，当pcur不为NULL时，就打印pcur->data,pcur等于指向pcur的下一个节点，相当于循环里面的++,这是单链表遍历的方式,直到pcur为NULL停止。

2.2申请一个结点SLBuyNode

SLNode* SLBuyNode(SLDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

这里申请一个结点，所以返回类型是这个结构体指针，利用malloc函数申请，注意判断是否申请成功，再将值赋给newnode->data,newnode的下一个节点为NULL。

2.3尾插SLPushBack

void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* newnode = SLBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else {SLNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}

尾插即从链表尾部插入，注意这里传参需要传二级指针，因为这里可能会引起头结点的改变，要使实参的改变，就要传它的指针，本身它就是一级指针，所以这里传二级，首先断言pphead不能指为空，申请一个结点，如果链表为空，则直接将申请的结点直接赋给头结点，如果链表不为空，因为链表只能从上一个结点找到下一个，所以尾插之前，就要找到尾结点，就需要遍历整个链表，再将尾结点的下一个结点，指向newnode，即可。

2.4头插SLPushfront

void SLPushfront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* newnode = SLBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

从头部插入，还是断言，然后申请一个节点，头插较为简单，直接将申请节点的next指向头结点，再将newnode赋给头结点。

2.5尾删SLPopBack

void SLPopBack(SLNode** pphead)
{assert(pphead && *pphead);SLNode* prev = *pphead;SLNode* ptail = *pphead;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}

从尾部删除元素，和尾插一样，如果链表只有一个结点直接free，置空就可以，如果链表不止一个结点，需要遍历，定义尾结点的前一个结点为prev，向后遍历两个依次向后移动直到ptail->next为空就停止，找到尾结点的前一个结点，再将prev的next置为空，然后free掉ptail就可以了。

2.6头删SLPopfront

void SLPopfront(SLNode** pphead)
{assert(pphead && *pphead);SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

从头部删除，先定义头结点的next结点，free掉头结点，再将next结点赋给next，成为新的头结点。

2.7查找结点位置SLFindNode

SLNode* SLFindNode(SLNode* phead, SLDataType x)
{assert(phead);SLNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;

查找，不会影响头结点的改变，所以这里可以传一级指针，这里就和尾插一样遍历，加一个判断pcur->data是否相等x，返回其结点就行，如果未找到就返回NULL。

2.8在pos位置插入SLInsert

void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){SLPushfront(pphead, x);}else{SLNode* prev = *pphead;SLNode* newnode = SLBuyNode(x);while (prev->next != pos){prev = prev->next;}newnode->next=pos;prev->next = newnode;}
}

在pos位置插入一个结点，先申请一个节点，如果在头结点位置插入，直接调用头插函数，如果不是头结点的位置，然后像尾差一样向后遍历找到pos的前一个节点，再将newnode的下一个结点指向pos，pos的前一个结点的next指向newnode即完成插入。

2.9在pos节点之后插入SLInsertAfter

void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

在pos之后，插入不需要遍历，直接在pos后插入，申请完节点后，直接将newnode->next结点指向pos的next，再将pos的next指向newnode。

2.10删除pos位置的结点SLErase

void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead && *pphead);assert(pos);SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

这里删除结点，要断言，链表不为空，pos位置存在，和尾删一样遍历找到pos位置之前的prev，直接将prev的next指向pos的next，释放掉pos的空间，即删除结点。

2.11删除pos位置之后后的结点SLEraseAfter

void SLEraseAfter(SLNode* pos)
{assert(pos&&pos->next!=NULL);SLNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

删除pos位置的节点，将pos的next定义为del，再将pos->next指向del->next,再释放掉del，置为NULL。

2.12销毁链表SLDestory

void SLDestory(SLNode** pphead)
{SLNode* pcur=*pphead;while (pcur){SLNode*next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

循环链表，依次删除，直到pcur为空，最后再将头结点释放掉，置为空。

3.整体代码

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;typedef struct SLNode
{SLDataType data;struct SLNode* next;
}SLNode;void SLPrint(SLNode* phead);
SLNode* SLBuyNode(SLDataType x);void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushfront(SLNode** pphead, SLDataType x);
void SLPopBack(SLNode** pphead);
void SLPopfront(SLNode** pphead);SLNode* SLFindNode(SLNode* phead, SLDataType x);
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
void SLInsertAfter( SLNode* pos,SLDataType x);
void SLErase(SLNode** pphead, SLNode* pos);
void SLEraseAfter(SLNode* pos);
void SLDestory(SLNode** pphead);

SList.c

#include"SList.h"void SLPrint(SLNode* phead)
{SLNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLNode* SLBuyNode(SLDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* newnode = SLBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else {SLNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}void SLPushfront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* newnode = SLBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLPopBack(SLNode** pphead)
{assert(pphead && *pphead);SLNode* prev = *pphead;SLNode* ptail = *pphead;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}void SLPopfront(SLNode** pphead)
{assert(pphead && *pphead);SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}SLNode* SLFindNode(SLNode* phead, SLDataType x)
{assert(phead);SLNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){SLPushfront(pphead, x);}else{SLNode* prev = *pphead;SLNode* newnode = SLBuyNode(x);while (prev->next != pos){prev = prev->next;}newnode->next=pos;prev->next = newnode;}
}void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead && *pphead);assert(pos);SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}void SLEraseAfter(SLNode* pos)
{assert(pos&&pos->next!=NULL);SLNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}void SLDestory(SLNode** pphead)
{SLNode* pcur=*pphead;while (pcur){SLNode*next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}