目录
一、不带头单链表
? ? ? ?初始准备
? ? ? ?链表节点创建与销毁
? ? ? ?尾插尾删
? ? ? ?头插头删
? ? ? ?随机位置插入与删除
? ? ? ?缺陷
? ? ? ?全部代码
二、链表带环问题
三、带头双链表
? ? ? ?初始准备
? ? ? ?链表节点创建与销毁
? ? ? ?尾插尾删
? ? ? ?头插头删
? ? ? ?随机位置插入与删除
? ? ? ?全部代码
四、对比顺序表与链表
一、不带头单链表
初始准备
不带头单链表，首先创建了一个结构体，而该结构体有2个成员，一个用来存储数据(data)，另一个用来存储下一个数据的地址(next*)，从而使得两个结构体变量连接起来，如下图
为了书写简洁，用typedef将其结构体类型名修改
?
又为了能方便存储不同类型的数据，不至于把程序写的太呆板，采用typedef将其类型名修改，要存储其他类型的数据时，只要修改即可。如下图，存储浮点型数据时，只要int改为float或double
打印链表
每打印一个数据，指针就向后移动一步
?注意：打印因为没有改变链表，所以只需传一级指针即可
? ? ? ? ? ?上图也可以不用创建cur,直接用phead
指针传参
无头单链表中，只有打印和查找数据时，不用传二级指针，其余时候都要传二级，因为要改变链表
上述两种都是传递地址，在C语言中要改变实参时，必须传地址才行?
链表节点创建与销毁
先用malloc开辟一块空间，大小是结构体的大小，然后再做判断，最后再对成员进行初始化即可
链表销毁时，要采用两个指针，一个在前，一个在后，要不然释放空间后，就成了野指针，找不到后面的数据了，把最后一个数据销毁后，再将其置空即可
?
尾插尾删
首先判断链表是否为空(没有数据)，没有就直接添加数据即可，有就找尾，最后一个数据的next指针为空，就表示找到了，直接连接数据紧接其后即可
要分两种情况，一种是只有一个节点时，另一种是多个节点时
多个节点时，尾删也需要两个指针，否则在删除最后一个数据后，要把前一个数据的next*置空，否则next*就是野指针了，下一次删除就找不到尾了
一个节点时，直接释放，置空即可
?
头插头删
头插时不需要判断链表是否为空，只要创建新节点，让它指向头节点，再把新节点的地址赋值给头节点的指针，作为新的头节点指针
?头删时要判断链表是否为空，毕竟空链表不能删除
先用一个指针变量存储头节点的下一个节点的地址，再将头节点销毁，再将其前面创建的指针的值赋给头节点的指针?
随机位置插入与删除
查找随机数，返回其地址，找不到就返回空指针，同样不需要传二级指针
在随机数的后面插入数据，找不到数据时，pos为空，所以断言判断一下。如下图，如果不多创建一个指针变量时，就需要先连线2，再连线1，因为先练线1时，就找不到cur2,指向的那个节点了；多创建一个变量保存节点地址，1、2那个先连都可以
?
在随机数的前面插入数据时，要分两种情况
第一种，随机数就是头节点的数据时，直接头插即可
第二种，找到pos的前一个节点，再创建节点，3个节点连接即可
在前面和后面插入两种方法对比，在后面插入明显更简单，效率也更高，因为不需要找前一个节点，这也是单链表的缺陷，双链表可以弥补这一缺陷
删除随机数后面的一节点的数据时，要作2次断言，第一个是随机数存不存在，第二个是随机数的下一个节点存不存在
?
删除随机数时，首先判断是不是随机数存不存在，同样有两种情况
第一种，随机数是头节点的数据时，直接头删即可
第二种，找到随机数的前一个节点，再连接，释放随机数的节点即可
缺陷：
每存一个数据，都要存一个指针去链接后面数据节点
不支持随机访问(用下标去访问第i个)
全部代码
//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct SList
{
DataType data;
struct SList* next;
}SLT;
//创建节点
SLT* SListNode(DataType x);
//打印链表
void SListPrint(SLT* phead);
//销毁链表
void SListDestroy(SLT** pphead);
//尾插
void SListPushBack(SLT** pphead, DataType x);
//尾删
void SListPopBack(SLT** pphead);
//头插
void SListPushFront(SLT** pphead, DataType x);
//头删
void SListPopFront(SLT** pphead);
//查找随机数
SLT* SListFind(SLT* pphead, DataType pos);
//随机位置向后插入
void SListInsert(SLT* pos, DataType x);
//随机位置的数的删除
void SListDeleteAfter(SLT* pos);
//随机位置向前插入
void SListInsertPrev(SLT** pphead, SLT* pos, DataType x);
//随机位置数据的删除
void SListDelete(SLT** pphead, SLT* pos);
//定义文件
#include"SList.h"
SLT* SListNode(DataType x)
{
SLT* newnode = (SLT*)malloc(sizeof(SLT));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLT** pphead, DataType x)
{
if (*pphead == NULL)
{
*pphead = SListNode(x);
}
else
{
SLT* cur = *pphead;
while (cur->next)
{
cur = cur->next;
}
cur->next = SListNode(x);
}
}
void SListPrint(SLT* phead)
{
SLT* cur = phead;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void SListDestroy(SLT** pphead)
{
assert(pphead);
SLT* cur = *pphead;
SLT* prev = *pphead;
while (cur)
{
prev = cur;
cur = cur->next;
free(prev);
}
*pphead = NULL;
}
void SListPopBack(SLT** pphead)
{
assert(*pphead);
SLT* cur = *pphead;
SLT* prev = NULL;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (cur->next)
{
prev = cur;
cur = cur->next;
}
free(cur);
cur = NULL;
prev->next = NULL;
}
}
void SListPushFront(SLT** pphead, DataType x)
{
SLT* cur = *pphead;
SLT* newnode = SListNode(x);
newnode->next = cur;
*pphead = newnode;
}
void SListPopFront(SLT** pphead)
{
assert(*pphead);
SLT* cur = (*pphead)->next;
free(*pphead);
*pphead = cur;
}
SLT* SListFind(SLT* phead, DataType pos)
{
assert(phead);
SLT* cur = phead;
while (cur)
{
if (cur->data == pos)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
void SListInsert(SLT* pos, DataType x)
{
assert(pos);
SLT* cur2 = pos->next;
SLT* newnode = SListNode(x);
newnode->next = cur2;
pos->next = newnode;
}
void SListDelete(SLT** pphead, SLT* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLT* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SListDeleteAfter(SLT* pos)
{
assert(pos);
assert(pos->next);
pos->next = pos->next->next;
free(pos->next);
pos->next = NULL;
}
void SListInsertPrev(SLT** pphead, SLT* pos, DataType x)
{
SLT* newnode = SListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
SLT* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
//测试文件
#include"SList.h"
void test1()
{
SLT* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPrint(plist);
}
void test2()
{
SLT* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPopFront(&plist);
SListPrint(plist);
}
void test3()
{
SLT* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SLT* pos = SListFind(plist, 3);
SListInsert(pos, 8);
/*SListDeleteAfter(pos);
SListPrint(plist);*/
SListInsertPrev(&plist, pos, 15);
SListPrint(plist);
SListDelete(&plist, pos);
SListPrint(plist);
SListDestroy(&plist);
}
int main()
{
//test1();
//test2();
test3();
return 0;
}二、链表带环问题
结论一：
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表 带环则一定会在环中相遇
证明如下图：
?至于fast走4步，slow走1步的情况下，读者可依照上图依葫芦画瓢分析
结论二：
fast与slow一定会在环的入口处相遇
三、带头双链表
初始准备
首先创建一个结构体，有3个成员，第一个是存储数据，2个指针，一个指向前节点，另一个指向后节点，用typedef将其结构体类型名修改，使其简洁，方便使用
用typedef将其数据类型名修改，便于存储其它数据时，不用大幅度改动
链表节点创建与销毁
首先创建一个头节点，用malloc开辟空间，不存储数据，前后指针均指向本身
?
然后用malloc创建其它节点，添加节点时，只需调用函数即可，前后指针均置为NULL
销毁双链表时，从头节点后的节点开始销毁，最后再销毁头节点
?
打印双链表
?
尾插尾删
?
尾删不能把头节点给删了，所以需断言
?
头插头删
?
?
头删不能把头节点给删了，所以需断言
??
随机位置插入与删除
查找
找不到返回NULL，找得到返回其地址
?
?
?
?
全部代码
//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct List
{
DataType data;
struct List* prev;
struct List* next;
}LT;
//初始化双链表
LT* LTInit();
//创建节点
LT* LTNode(DataType x);
//打印双链表
void LTPrint(LT* phead);
//尾插
void LTPushBack(LT* phead, DataType x);
//尾删
void LTPopBack(LT* phead);
//头插
void LTPushFront(LT* phead, DataType x);
//头删
void LTPopFront(LT* phead);
//查找
LT* LTFind(LT* phead, DataType pos);
//随机位置插入数据
void LTInsert(LT* pos, DataType x);
//随机位置的数据删除
void LTDelete(LT* pos);
//销毁双链表
void LTDestroy(LT* phead);
//定义文件
#include"List.h"
LT* LTInit()
{
LT* head = (LT*)malloc(sizeof(LT));
if (head == NULL)
{
printf("malloc fail\n");
exit(-1);
}
head->next = head;
head->prev = head;
return head;
}
LT* LTNode(DataType x)
{
LT* newnode = (LT*)malloc(sizeof(LT));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
void LTPrint(LT* phead)
{
assert(phead);
LT* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LT* phead, DataType x)
{
assert(phead);
LT* newnode = LTNode(x);
LT* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void LTPopBack(LT* phead)
{
assert(phead);
assert(phead->next != phead);
LT* tail = phead->prev;
LT* prevtail = phead->prev->prev;
phead->prev = prevtail;
prevtail->next = phead;
free(tail);
tail = NULL;
}
void LTPushFront(LT* phead, DataType x)
{
assert(phead);
LT* newnode = LTNode(x);
LT* begintail = phead->next;
phead->next = newnode;
newnode->prev = phead;
begintail->prev = newnode;
newnode->next = begintail;
}
void LTPopFront(LT* phead)
{
assert(phead);
assert(phead->next != phead);
LT* begin = phead->next;
LT* cur = begin->next;
phead->next = cur;
cur->prev = phead;
free(begin);
begin = NULL;
}
LT* LTFind(LT* phead, DataType pos)
{
assert(phead);
LT* cur = phead->next;
while (cur != phead)
{
if (cur->data == pos)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
void LTInsert(LT* pos, DataType x)
{
assert(pos);
LT* newnode = LTNode(x);
LT* prevpos = pos->prev;
prevpos->next = newnode;
newnode->prev = prevpos;
pos->prev = newnode;
newnode->next = pos;
}
void LTDelete(LT* pos)
{
assert(pos);
LT* prevpos = pos->prev;
LT* tailpos = pos->next;
prevpos->next = tailpos;
tailpos->prev = prevpos;
free(pos);
pos = NULL;
}
void LTDestroy(LT* phead)
{
assert(phead);
LT* cur = phead->next;
while (cur != phead)
{
LT* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
//测试文件
#include"List.h"
void test1()
{
LT* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPopBack(plist);
//LTPopBack(plist);
//LTPopBack(plist);
//LTPopBack(plist);
//LTPopBack(plist);
LTPrint(plist);
}
void test2()
{
LT* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPushFront(plist, 5);
LTPushFront(plist, 6);
LTPushFront(plist, 7);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPopFront(plist);
//LTPopFront(plist);
//LTPopFront(plist);
//LTPopFront(plist);
LTPrint(plist);
}
void test3()
{
LT* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LT* pos = LTFind(plist, 3);
LTInsert(pos, 8);
LTInsert(pos, 16);
LTDelete(pos);
LTPrint(plist);
LTDestroy(plist);
}
int main()
{
test1();
//test2();
//test3();
return 0;
}四、对比顺序表与链表
顺序表
优点：
支持随机访问。需要随机访问结构支持算法可以很好的适用
缺点：
头部中部插入删除时间效率低? O(n)
连续的物理空间，空间不够了以后需要增容：
增容有一定程度消耗
为了避免频繁增容，一般我们都按倍数去增容，用不完可能存在一定的空间浪费
链表(双向带头循环)
优点：
任意位置插入删除效率高? O(1)
按需申请释放空间
缺点：
不支持随机访问(用下标访问)。意味着：一些排序、二分查找等在这种结构上不适用
链表每存储一个值，同时要存储一个指针，也有一定的消耗