数据结构---单链表
目录
一、概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
二、分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
这里我们只介绍无头单向非循环链表：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
三、接口实现
1.定义结构
//定义一下结构
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;这里为了方便我们测试代码的正确性，我们顺手实现一个Print，以方便我们检查。
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//cur向后走
}
printf("NULL\n");
}2、申请节点
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}3、尾插
下面这样写对吗？
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
SLTNode* tail = phead;
while (tail != NULL)
{
tail = tail->next;
}
tail = newnode;
}
改正：
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
SLTNode* tail = phead;
while (tail->next!= NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
那么这样写就写完了吗？那如果我的链表是个空的呢？
//这样写对吗???
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (phead = NULL)
{
phead = newnode;
}
else
{
SLTNode* tail = phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
} 
从结果来看好像并没有插进去啊，这是怎么回事呢？
我们要改变plist就要传plist的地址过去，所以代码应该这么写：
//正确代码
//尾插
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;
}
}
4、头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
5、尾删
下面这样写对吗？
void SLTPopBack(SLTNode** pphead)
{
//1、空
assert(*pphead);
//2、一个节点
//3、一个以上节点
if ((*pphead)->next = NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
free(tail);
tail = NULL;
}
}
正确代码：
//尾删
void SLTPopBack(SLTNode** pphead)
{
//1、空
assert(*pphead);
//2、一个节点
//3、一个以上节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//方法一：
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
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;
}
8、在pos之前插入x
//在pos之前插入x
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之后插入x
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}注意：
10、删除pos位置
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
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之后位置
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//检查pos是不是尾节点
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
fress(posNext);
posNext = NULL;
}
四、完整代码
//SList.h
#pragma once
#include <stdio.h>
#include <stdlib.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 SLTPushFront(SLTNode** phead, SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLTPopFront(SLTNode** pphead);
//尾删
void SLTPopBack(SLTNode** pphead);
//查找,也可以充当修改
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//cur向后走
}
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;
return newnode;
}
//尾插
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;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1、空
assert(*pphead);
//2、一个节点
//3、一个以上节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
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);
//空
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;
}
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
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;
}
}
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除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的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//检查pos是不是尾节点
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}原文地址：https://blog.csdn.net/m0_73299878/article/details/144304598
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！