目录

1.0：单链表

1.1：概念

1.2：理解

2.0：一个简单的单链表举例

3.0:单链表结构

3.1：定义一个元素链

3.2：打印链表

3.3：创建空间

3.4：尾插

3.5：头插

3.6：尾删

3.7：头删

3.8：查找相关值

3.9：在pos位置之前插入x

3.10：在pos位置之后插入x

3.11：删除pos位置

3.12：删除pos的后一个位置

3.13：销毁

1.0：单链表

1.1：概念

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

1.2：理解

        类似于这种用一个起始地址来记录首元素地址，之后每个元素内存有指向下一个元素地址的指针的链表，我们叫做单链表。

2.0：一个简单的单链表举例

2.1：创建

typedef int SLTDataType;
typedef struct SListNode {SLTDataType date;struct SListNode* next;
}SLTNode;

        我们首先定义一个简单的结构体类型，里面存放一个数据和结构体指针

        指针用来指向下一个结构体的地址，这样，我们就可以通过前一个里面的指针来找到下一个结构体元素了。

2.2：手动链接

int main() {SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));n1->date = 1;SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n2->date = 2;SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));n3->date = 3;n1->next = n2;n2->next = n3;n3->next = NULL;PrintSList(n1);return 0;
}

        我们向内存申请空间，（需要检查，这里默认申请成功）我们给每块空间date变量赋值，之后再将前一块空间内的指针指向下一块空间，从而将他们连接起来。

2.3：打印测试

void PrintSList(SLTNode* phead) {SLTNode* sur = phead;while (sur != NULL) {printf("%d->",cur->date);sur = cur->next;}printf("NULL\n");
}

        我们创建sur指针，将他指向第一块空间地址，并且打印每块空间的date值

2.4：大致思路

对于sur=sur->next的思路图如下：

 通过此语句，我们可以遍历每个空间。

接下来，整体逻辑思路如下所示：

3.0:单链表结构

3.1：定义一个元素块

typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;
int main() {//定义一个起始指针；SLTNode* plist = NULL;//进行指令//销毁SLTDestroy(&plist);return 0;
}

        定义一个元素，里面存有数值和指针。

3.2：打印链表

//打印
void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur != NULL) {printf("%d->",cur->data);cur = cur->next;}printf("NULL\n");
}

       我们设定一个指针去遍历这个单链表，从而达到打印的效果

3.3：创建空间

//创建空间
SLTNode* BuySListNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc faill");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

        我们在进行插入的时候都需要单独创建空间，我们使得每次创建的空间值为插入的值，指针指向空

3.4：尾插

//尾插
void SLTPushBack(SLTNode**pphead,SLTDataType x) {assert(pphead);SLTNode* newnode = BuySListNode(x);if (*pphead == NULL) {//改变的是结构体指针，要用二级指针*pphead = newnode;}else {SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}//改变结构体，用结构体指针即可tail->next = newnode;}
}

        我们首先创建一块空间，当单链表一个元素都没有，就需要特殊处理，需要改起始指针的值，让起始指针指向新开辟的空间，如果有元素，拿一个指针遍历一遍找到最后一个元素，再将最后一个元素的指针指向新空间即可。

3.5：头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}

        头插这里首先创建空间，将起始指针指向新空间地址，再将新空间内的指针指向原来第一个空间即可，由于这里需要改起始指针的指向，所以需要二级指针。

3.6：尾删

//尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead);//空assert(*pphead);//一个节点//两个或两个以上if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}else {//方法一SLTNode* tailprev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL) {tailprev = tail;tail = tail->next;}free(tail);tailprev->next = NULL;//方法二/*SLTNode* tail = *pphead;while (tail->next->next!=NULL) {tail = tail->next;}free(tail);tail->next = NULL;*/}
}

        尾删我们一般需要找到最后一个元素，如果链表有多个元素，只需要双指针找到最后一个和倒数第二个元素，将倒数第二个元素所指向的指针指向空即可，然后释放最后一块空间。

        但如果只有一个元素时，我们就需要将起始指针指向空，所以这里需要二级指针，使其指向空即可。

3.7：头删

//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead);//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

       头删我们只需要将起始指针指向第二个元素地址即可，也可以将起始指针指向第一个元素内指针指向的地址（也是第二个元素的地址），最后释放掉第一个元素内存即可。

3.8：查找相关值

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur != NULL) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}

        查找相关值需要利用指针去遍历单链表的同时，去比较对应的元素值和比较值，如果找到了，那就需要返回对应的指针，找不到就返回空指针。

3.9：在pos位置之前插入x

//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//插入的时候，必须保证有元素才能插入//头插if (pos == *pphead) {SLTPushBack(pphead, x);}else {//中间插入SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

       在pos位置之前插入分为两种情况，一种在第一个位置后插入元素，这里我们创建好空间之后，改变起始指针指向的地址，改为新空间的地址，再将新空间元素内指针指向原本第一个空间的地址即可，使他们链接。一种是在第二个元素或第二个元素之后插入，我们只需要利用双指针找到要插入的空间和前一个空间，使得前一个空间元素的指针指向新空间地址，再将新空间元素指针指向下一个空间地址即可。

3.10：在pos位置之后插入x

//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

       我们只需要找到pos位置，创建好新空间，将pos位置的指针指向新空间地址，再将新空间内的指针指向下一个空间地址即可。

3.11：删除pos位置

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(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;}
}

        删除pos位置如果我们要删除的是首元素，那么就是一个头删。如果删除的不是首元素，我们只需要利用指针找到pos位置前一块空间，然后让前一块指针指向pos位置元素内指针指向的地址（也就是下一块元素地址）使他们链接即可。

3.12：删除pos的后一个位置

//删除pos的后一个位置
void SLTEraseAft(SLTNode* pos) {assert(pos);//检查pos是否是未节点//方法一/*if (pos->next == NULL) {return;}*///方法二assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

        删除pos后一个空间的思路就是找到位置，然后创建空间，使得pos元素指针指向pos下一个空间的地址即可。

3.13：销毁

//销毁
void SLTDestroy(SLTNode** pphead) {assert(pphead);SLTNode* cur = *pphead;while (cur != NULL) {SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

        销毁时需要在遍历的同时，用指针去保存下一块空间地址，然后释放当前空间即可。

        最后，以上内容为个人理解，如有不足，还请各位指教！！！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！