顺序表的优缺点

顺序表的问题

头部和中部的插入删除效率都不行，

O

(

N

)

O(N)

O(N)空间不够了，扩容有一定消耗（尤其是异地扩容）开新空间，拷贝数据，释放旧空间扩容逻辑，可能还存在空间浪费

多扩，浪费空间少扩，频繁扩容

顺序表的优点 尾插尾删足够快下标的随机访问和修改

链表：按需申请释放

单链表

初始化

<code>typedef int SLTDataType;

struct SListNode

{

SLTDataType data;

struct SListNode* next;

};

typedef struct SListNode SLTNode;

或

typedef int SLTDataType;

typedef struct SListNode

{

SLTDataType data;

struct SListNode* next;

}SLTNode;

SLTNode，节点data，数据域next，指针域，是一个结构体指针，不能是数据类型的指针，否则不能指向下一个节点

打印单链表

void PrintList(SLTNode* phead)

{

SLTNode* cur = phead;

while (cur != NULL)

{

printf("%d->", cur->data);

cur = cur->next;

}

printf("NULL\n");

}

phead存的是第一个节点的地址把第一个节点赋值给cur，cur指向第一个节点当cur不为空，访问curcur->next，取结构体里的值，存的是下一个节点的地址把cur->next赋给cur，cur指向下一个节点以此循环，直到cur指向NULL实际上cur没有动，只是值一直在变化而已

最开始将phead赋给cur

cur不为NULL时，将cur->next，也就是下一个节点的地址赋给cur，cur指向下一个节点

直到cur指向NULL，结束

构建链表

<code>int main()

{

SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));

n1->data = 10;

SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));

n2->data = 20;

SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));

n3->data = 30;

n1->next = n2;

n2->next = n3;

n3->next = NULL;

PrintSList(n1);

return 0;

}

创建节点

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;

}

sizeof里是节点的类型，不是SLTDataType检查新malloc的节点地址是否为空初始化新节点

尾插

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;

}

}

先创建一个节点

如果单链表没有节点，为第一次插入

将newnode赋给*pphead，也就是把newnode的地址给*pphead，*pphead指向newnode。

由于这里要修改的phead是结构体指针，在函数中要修改实参需要通过指针的指针也就是二级指针，再解引用来修改。

<code>*pphead就是phead

当单链表中已经有节点

将*pphead头节点赋给tail，也就是把第一个节点的地址赋给tail，tail指向第一个节点

将tail->next赋给tail，也就是下一个节点的地址赋给tail，tail指向下一个节点

一直循环，直到tail->next指向NULL停止，也就是tail指向NULL的前一个节点

将newnode赋给tail->next，将next指向的NULL，改为指向newnode

尾插完成

改变结构体，要用结构体指针改变结构体指针，要用结构体指针的指针

头插

<code>void SLTPushFront(SLTNode** pphead, SLTDataType x)

{

SLTNode* newnode = BuySListnode(x);

newnode->next = *pphead;

*pphead = newnode;

}

newnode是一个结构体*pphead是结构体指针，用结构体指针可以访问这个结构体的数据，也可以通过next找到下一个节点的地址

将phead赋给newnode->next，新节点的next指向phead

phead存的是第一个节点的地址，等同于

将newnode赋给phead，phead指向newnode，也就是第一个节点

完成头插

尾删

不能直接删去最后一个节点，也得把前一个节点的next指向空，否则会造成野指针

<code>void SLTPopBack(SLTNode** pphead)

{

assert(*pphead);

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;

}

}

如果phead直接是NULL

有可能是调用错误，用assert报错提醒。

当删到最后一个节点时

此时phead指向第一个节点，next指向下一个节点，指向NULL，表示链表只剩最后一个节点

直接free掉phead指针，将phead置为空

链表中还有其他节点时

用tail指针遍历，找最后一个节点

这里如果用一个tail指针，删除掉最后一个节点之后，前一个节点的next指针没有改变，所以需要两个指针跑

再设置一个tailPrev指针，每次tail往下遍历之前，把tail赋给tailPrev，也就是让tailPrev指向当前自己，自己再往后遍历

phead赋给tail，tail指向第一个节点；将tailPrev初始化为NULL

两个指针开始往后遍历，当tail->next指向空结束

free掉tail指针，将tailPrev->next置为空

尾删完成

第二种写法

<code>SLTNode* tail = *pphead;

while (tail->next->next)

{

tail = tail->next;

}

free(tail->next);

tail->next = NULL;

使用一个tail节点，用tail->next->next找到最后一个节点指向的空，这样tail->next指向的就是最后一个节点，free掉最后一个节点也就是tail->next，然后将tail->next，也就是最后一个节点的上一个节点置为空

头删

<code>void SLTPopFront(SLTNode** pphead)

{

assert(*pphead);

SLTNode* newhead = (*pphead)->next;

free(*pphead);

*pphead = newhead;

}

头删不需要找尾，找到下一个即可

一个节点和多个节点不需要分开讨论，都是将第一个节点删去，链接下一个，无非是一个节点的情况下一个节点是空而已，逻辑是一样的

先断言，phead如果是空，就报错，暴力检查

将phead->next，也就是第二个节点的地址赋给newhead，newhead指向第二个节点

释放掉phead

将newhead赋给phead，phead指向第二个节点

查找

查找只需要遍历链表即可，并不会修改头指针，因此不需要传二级指针

<code>SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

{

SLTNode* cur = phead;

while (cur)

{

if (cur->data == x)

{

return cur;

}

cur = cur->next;

}

return NULL;

}

创建一个cur指针遍历链表

将phead赋给cur，cur指向第一个节点

将cur->next赋给cur，cur指向下一个节点，一直循环直到cur指向NULL；如果找到x。就直接返回cur如果没有找到x，cur指向空遍历完毕后，就返回NULL

查找还可以用作修改，用查找函数查找到目标data，然后用pos将返回值接收，再修改pos

如果返回空的话，链表不会有变化

pos之前插入x

在pos位置之前插入一个值，pos可以是任意位置

pos有可能是头插，需要修改头节点，用二级指针

其余情况需要找到pos位置的前一个，来修改next，单链表中只能从头节点开始遍历整个链表

<code>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;

}

}

当pos就是头节点，就相当于头插，直接复用之前的函数

当pos为后续节点

创建一个prev指针，遍历链表来找pos的前一个节点，假如pos是3

创建一个newnode节点，将newnode赋给prev->next，也就是prev->next存newnode的地址，指向newnode

将pos赋值给newnode->next，newnode->next指向pos

pos之后插入x

不可能是头插，pos是第一个节点，就是往第一个节点后面插入

<code>void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{

assert(pos);

SLTNode* newnode = BuySListNode(x);

newnode->next = pos->next;

pos->next = newnode;

}

如果pos是NULL，则有可能是传错了，直接报错

复用之前的函数，创建一个节点

将pos->next赋给newnode->next，newnode->next指向pos的下一个节点

将newnode赋给pos->next，pos->next指向newnode，pos的下一个节点变为newnode

删除pos位置

需要找pos前一个节点来断开连接

头删需要处理，因为没有前一个节点

不需要特别处理尾删

<code>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);

}

}

假如pos是2，通过prev找到pos的上一个节点

将pos->next赋给prev->next，prev->next指向pos的下一个节点

最后不需要将pos指针置空，因为函数返回以后，pos就是野指针

删除pos后一个位置

pos可以是任意节点

不能删除头节点

当pos是最后一个节点，没有意义

<code>void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)

{

assert(pos);

assert(pos->next);

SLTNode* posNext = pos->next;

pos->next = posNext->next;

free(posNext);

posNext = NULL;

}

通过断言检查上述两种情况

通过posNext节点存pos的下一个节点

将posNext->next赋给pos->next，pos->next指向posNext的下一个节点，将posNext断开连接

直接free掉posNext节点，可以置空

声明定义分离实现

<code>#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 SLTPushBack(SLTNode** pphead, SLTDataType x);

void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);

void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos之后插入x

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos的后一个位置

void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);

#include"SList.h"

void SLTPrint(SLTNode* phead)

{

SLTNode* cur = phead;

while (cur)

{

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;

return 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;

}

}

void SLTPushFront(SLTNode** pphead, SLTDataType x)

{

SLTNode* newnode = BuySListnode(x);

newnode->next = *pphead;

*pphead = newnode;

}

void SLTPopBack(SLTNode** pphead)

{

assert(*pphead);

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;

}

}

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** pphead, SLTNode* pos, SLTDataType x)

{

assert(pos);

SLTNode* newnode = BuySListNode(x);

newnode->next = pos->next;

pos->next = newnode;

}

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);

}

}

void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)

{

assert(pos);

assert(pos->next);

SLTNode* posNext = pos->next;

pos->next = posNext->next;

free(posNext);

posNext = NULL;

}

#include"SList.h"

void TestSList1()

{

int n;

printf("请输入链表的长度：");

scanf("%d", &n);

printf("\n请依次输入每个节点的值");

SLTNode* plist = NULL;

for (size_t i = 0; i < n; i++)

{

int val;

scanf("%d", &val);

SLTNode* newnode = BuySListNode(val);

//头插

newnode->next = plist;

plist = newnode;

if (plist == NULL)

{

plist = newnode;

}

else

{

plist->next;

}

}

SLTPrint(plist);

}