顺序表回顾—引入链表
缺陷： 1.空间不够了，增容。（增容会带来缺陷，增容会付出一定的性能消耗，其次可能存在一定的空间浪费） 例如：当我有一百个空间，满了之后，增容扩大两倍，但是我插入之后，只插入了10个数据，所以浪费了90个空间。 2.头部或者中部左右的插入删除的效率低。->O(N) 如何解决： 1.空间上，按需给空间。 2.不要求物理空间连续，头部和中部的插入，就不需要挪动数据。 解决方案：链表
一、链表是什么？
1.链表的分类
1.单向链表：单向链表的特点是链表的链接方向是单向的，对链表的访问需要通过顺序读取从头部开始。 2.双向链表：双向链表也叫双链表，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。 3.循环链表：循环链表的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。 4.线性链表：线性链表是一种简单的链表结构，每个结点只包含一个指向下一个结点的指针。 5.树链表：树链表是一种层次化的链表结构，它的每个结点可以有多个子结点，通过指针连接。 6.网链表：网链表是一种复杂一点的链表结构，它的每个结点可以有多个指向前驱和后继的指针。 等等… 本次内容讲的是单向链表。
2.单向链表
注意：最后一个指针应该指向空指针。 链表的概念及结构 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 从逻辑结构看：链表是线性的，是想象出来的。 从物理结构看：
第二个空间存的是第二个节点的地址。 节点的地址是malloc来的，也可以认为是随机的，malloc是操作系统随机找的一个空闲的空间。 最后一个节点存的是空指针。 顺序表和链表的区别就是： 物理上是连续的存储的，链表的物理空间是不连续的。
链表的定义：
代码语言：javascript复制typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//结构体中不能有结构体嵌套，但是可以是结构体指针，
//指针就是一个地址，表示4个字节，指针指向的下一个节点是结构体
}SLT;注意：结构内部是不能用typedef的结构体类型。
二、链表的应用
1.链表的打印
注意：这里的SLT类型是上文定义的结构体类型
代码语言：javascript复制void SListPrint(SLT* plist)
{
SLT* cur=plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}2.建立新的节点
代码语言：javascript复制SLT* BuySListNode(SLTDataType x)
{
SLT* newnode = (SLT*)malloc(sizeof(SLT));
newnode->data = x;
newnode->next = NULL;
return newnode;
}3.尾插和首插
代码语言：javascript复制//尾插
void SListPushBack(SLT** pplist, SLTDataType x)
{
SLT* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;//形参是实参的零时拷贝，出了定义域会销毁
}
else
{
SLT* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
//尾节点，链接新节点
tail->next = newnode;
}
}
//头插
void SListPushFront(SLT** pplist, SLTDataType x)
{
SLT* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}4.尾删和头删
代码语言：javascript复制//尾删
void SListPopBack(SLT** pplist)
{
if (*pplist == NULL)
{
return;
}
else if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
return;
}
SLT* tail = *pplist;
SLT* prev = NULL;//保存上一个节点的指针变量
while (tail->next != NULL)
{
prev = tail;//将上一个节点存起来
tail = tail->next;//找下一个节点
}
free(tail);//free掉下一个空间
prev->next = NULL;//找到倒数第二个节点指向的下一个节点，并置为空指针。防止变为野指针
tail = NULL;//置位空指针
}
//头删
void SListPopFront(SLT** pplist)
{
SLT* tail = (*pplist)->next;//将下一个节点的位置给存起来
free(*pplist);//将这个节点给free掉
*pplist = NULL;//置空
*pplist = tail;//找到下一个节点，并将其赋值为头结点
}5.查找链表中的数据
代码语言：javascript复制//查找链表数据
SLT* SListFind(SLT* plist, SLTDataType x)
{
SLT* cur = plist;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}6.在指定pos位置之前插入数据或者删除pos位置数据
代码语言：javascript复制//在pos位置前插入x
void SListInsert(SLT** pplist, SLT* pos, SLTDataType x)
{
if (*pplist == pos)
{
SListPushFront(pplist, x);
}
else
{
SLT* newnode = BuySListNode(x);
SLT* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
//删除pos位置的数
void SListErase(SLT** pplist, SLT* pos)
{
if (pos == *pplist)
{
SListPopFront(pplist);
}
else
{
SLT* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SLT* tail = pos->next;
free(pos);
prev->next = tail;
}
}三、如何使用链表应用中的函数及函数封装
1.在pos前插入指定x
代码语言：javascript复制void TestSlist3()
{
SLT* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SLT* pos = SListFind(plist, 4);
if (pos)
{
SListInsert(&plist, pos, 30);
}
printf("n");
SListPrint(plist);
}
int main()
{
TestSlist3();
return 0;
}注意：删除pos位置的数也与上述代码雷同
2.封装为3个文件
1. Slist.h
代码语言：javascript复制#pragma once//防止重复包含
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//结构体中不能有结构体嵌套，但是可以是结构体指针，
//指针就是一个地址，表示4个字节，指针指向的下一个节点是结构体
}SLT;
void SListPrint(SLT* plist);
void SListPushBack(SLT** plist, SLTDataType x);
void SListPushFront(SLT** pplist, SLTDataType x);
void SListPopBack(SLT** pplist);
void SListPopFront(SLT** pplist);
//查找位置
SLT* SListFind(SLT* plist, SLTDataType x);
//在pos前面插入一个数
void SListInsert(SLT** pplist,SLT*pos,SLTDataType x);
//删除pos位置的值
void SListErase(SLT** pplist,SLT*pos);2. test.c文件
代码语言：javascript复制#include "Slist.h"
void TestSlist1()
{
SLT *plist=NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);
SListPrint(plist);
}
void TestSlist2()
{
SLT* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SListPopFront(&plist);
SListPopBack(&plist);
printf("n");
SListPrint(plist);
}
void TestSlist3()
{
SLT* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SLT* pos = SListFind(plist, 4);
if (pos)
{
SListInsert(&plist, pos, 30);
}
printf("n");
SListPrint(plist);
}
void TestSlist4()
{
SLT* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SLT* pos = SListFind(plist, 3);
if (pos)
{
SListErase(&plist, pos);
}
printf("n");
SListPrint(plist);
}
int main()
{
TestSlist4();
return 0;
}注意：Slist.c文件就是上面函数，这里不过多重复阐述
四、总结
链表相较于顺序表来说难度有所上升，但是掌握链表基本概念，练习一些算法题还是很好掌握的。
