数据结构-链表

🗡CSDN主页：d1ff1cult.🗡

🗡代码云仓库：d1ff1cult.🗡

🗡文章栏目：数据结构专栏🗡

目录

目录

代码总览：

接口slist.h：

slist.c:

1.什么是链表

1.1链表的概念

 1.2链表的分类

2.链表与顺序表

顺序表的优点与缺陷

3链表

3.1链表实现

总结

---

---

代码总览：

slist.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);SLTNode* BuySListNode(SLTDataType x);
//开辟新的节点void SLTPushBack(SLTNode** pphead, SLTDataType x);
//尾插
void SLTPushFront(SLTNode* phead, SLTDataType x);
//头插
void SLTPopBack(SLTNode** pphead);
//尾删
void SLTPopFront(SLTNode**  pphead);
//头删
void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x);
//在pos之前插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTErase(SLTNode** pphead, SLTNode*pos);
//删除pos位置
void SLTEraseAfter(SLTNode* pos);
//删除pos后一个位置
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//查找 

slist.c:

#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) 
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}//头插
void SLTPopBack(SLTNode** pphead, SLTDataType x)
{//1.空assert(*pphead);//2.一个节点//3.一个以上节点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){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);//空//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data== x){return cur;}cur = cur->next;}return NULL;
}
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}
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);}
}
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

---

1.什么是链表

1.1链表的概念

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

 

 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

 1.2链表的分类

1.带头或不带头

2.循环或不循环

3.双向或单向

2.链表与顺序表

顺序表的优点与缺陷

顺序表的数据在物理空间上是连续存放的，使得我们用数组下标访问变的十分简单，尾插尾删的效率比较高，但同时想要在中间删除数据时，需要将数据一个个挪动，效率比较低，但同时他的数据在物理空间上连续存放也有了以下的问题

1中间/头部的插入删除，时间复杂度为O(N)
2.增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3.增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

详细了解请移步：

3链表

链表是一块一块独立的空间，通过结构体指针来连接，删除/插入数据比较方便，空间使用malloc函数开辟，浪费的空间比较少，而且在物理上不是连续存放的，不会出现异地扩容之类的行为，对空间懂得利用较高，空间都是按需申请的

3.1链表实现

1.定义一个结构体

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

同时为了方便改变数据的类型，我们定义typedef int SLTDataType;结构体中的内容有存储的数据还有指向下一块内容的结构体指针 next

2.链表的遍历

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

 这其中有一句非常关键的代码：cur=cur->next;这个时候又得拿出这张图了：

将头指针phead赋值给cur，让cur不断向后遍历，直到遇到NULL指针停下来

那么cur=cur->next;首先cur=phead，此时cur指向了第一个结构体，打印data

然后再将结构体中next指向的地址赋值给cur，此时cur就指向了下一个结构体，

如此遍历直到cur遇到了NULL；

3.创建新节点

定义一个结构体指针newnode用来创建新的节点，使用malloc手动开辟所需的空间，需要注意的是newnode是结构体指针，类型是SLTNode而不是SLTDataType，如果定义成了SLTDataType类型，后续的free操作就会报错

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;
}

 4.尾插

引入了新的结构体指针tail，不断遍历链表，直到tail->next==NULL的时候说明已经找到了链表的尾部，此时再将创建好的newnode赋值给tail->next将新节点和链表链接起来实现了链表的尾插。  注意，while中tail->next==NULL，不能写成tail==NULL，tail=newnode。

因为phead newnode tail都是形参出了作用域后就会销毁，这样写不仅实现不了尾插，还会导致内存的泄露。

下面这个图就是错误原因

这一段尾插没有考虑链表为空的情况。

void SLTPushBack(SLTNode* phead, SLTDataType x) 
{SLTNode* newnode = BuySListNode(x);SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}//尾插

 下面为正确的尾插，参数需要传二级指针

1.改变结构体需要用结构体指针（参数）

2.改变结构体指针需要用结构体指针的指针（tail->next = newnode）

void SLTPushBack(SLTNode** pphead, SLTDataType x) 
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

 5.头插

分为三种情况

1.空

2.一个节点

3.一个以上的节点（两种写法）

当找到尾部tail后不能直接将tail   free释放掉然后置空，因为上一个结构体还指向tail，然而tail又是局部变量，出了作用域就会被销毁，所以上一个结构体的next指向了野指针，所以我们就想到了使用tail的前一个 tailPrev，避免了野指针的出现；

链表的头插，，简单而且效率高

void SLTPopBack(SLTNode** pphead, SLTDataType x)
{//1.空assert(*pphead);//2.一个节点//3.一个以上节点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){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

 6.头删

同样考虑是否为空，较为简单，头删简单效率高。

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

7.查

这里的查也同时可以起到修改的作用，查找到数据后，将其内容修改。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data== x){return cur;}cur = cur->next;}return NULL;
}//修改：
//SLTNode* pos = SLTFind(plist, 1);//if (pos)//{//	pos->data *= 10;//}

8.在pos位置前插入

（其实相当于在pos位置插入）在pos位置前插入，需要链表遍历到pos，但是此时不知道pos前一个位置的地址，无法做到在pos位置前插入，所以我们又引进了一个结构体指针prev，指向了pos的前一个位置.

单链表的前插还是具有一定的局限性，前插用双向链表来实现更为便捷。

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}}

 9.在pos位置后插入

注意

newnode->next = pos->next;
pos->next = newnode;

这两句代码的顺序不能改变，不然就会出现环链表，，从而导致死循环

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

 10.删除pos位置

首先判断一下pos是不是头指针，如果是就复用之前写的头删，如果不是，就选择引入prev指针指向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);}
}

11.删除pos位置后一个

较为简单不再赘述

void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

 12.销毁

void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

---

总结

以上便是不带哨兵 单链表的实现。