目录
一、概念
二、分类
1. 单向或者双向
编辑
2. 带头或者不带头
3. 循环或者非循环
三、接口实现
1.定义结构
2、申请节点
3、尾插
4、头插
5、尾删
6、头删
7.查找，也可以充当修改
8、在pos之前插入x
9、在pos之后插入x
编辑 10、删除pos位置
11、删除pos之后位置
四、完整代码
一、概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
二、分类
实际中链表的结构非常多样，以下情况组合起来就有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;
}