【数据结构】链表

目录

数据结构之链表：：

                                SList.h

                                1.链表的概念及结构

                                2.链表的分类 

                                SList.c

                                3.动态申请一个结点                              

                                4.单链表打印

                                5.单链表销毁

                                6.单链表头插

                                7.单链表头删

                                8.单链表尾插

                                9.单链表尾删

                              10.单链表查找

                              11.单链表在pos之前插入

                              12.单链表在pos之后插入

                              13.删除pos位置

                              14.删除pos后面位置                              

---

数据结构之链表：：

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;
SListNode* next为C++中的语法 将其封装成了类
void SListPrint(SLTNode* phead);
void Destory(SLTNode** pphead);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
删除pos后面位置
void SListEraseAfter(SLTNode* pos);

1.链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的.

注意：

1.从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续.

2.现实中的结点一般都是从堆上申请出来的.

3.从堆上申请的空间,是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续.

2.链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构.

1.单向或者双向 

 

2.带头或者不带头

 3.循环或者非循环 

 虽然有这么多的链表结构，但是我们实际中最常用还是两种结构. 

无头单向非循环链表：
结构简单，一般不会用来单独存数据，实际上更多是作为其他数据结构的子结构，如哈希桶,图的邻接表等.
带头双向循环链表：
结构最复杂，一般用来单独存储数据,实际中使用到的链表数据结构，都是带头双向循环链表，这个结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了.

SList.c

3.动态申请一个结点

SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

4.单链表打印

void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

5.单链表销毁

void Destory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur != NULL){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

6.单链表头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

7.单链表头删

void SListPopFront(SLTNode** pphead)
{assert(pphead);温柔的检查if (*pphead == NULL){return;}暴力的检查//assert(*pphead != NULL);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}

8.单链表尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{1.链表是空2.链表非空链表为空 插入第一个结点 要改变的是SListNode* 用的是结构体指针的指针链表不为空 尾插要改变的是结构体SListNode的成员 用的是结构体指针assert(pphead);SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

9.单链表尾删

void SListPopBack(SLTNode** pphead)
{assert(pphead);温柔的检查——为空不删if (*pphead == NULL){return;}暴力的检查//assert(*pphead != NULL);1.一个结点 2.多个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{找尾SLTNode* prev = NULL;/*SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}prev->next == NULL;free(tail);tail = NULL;*/SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}prev->next = NULL;free(tail->next);tail->next = NULL;}
}

10.单链表查找

链表中的查找函数可以替代其修改函数
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

11.单链表在pos之前插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SListPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;pos不在链表中 pos不在链表中 prev为空还没有找到pos 说明pos传错了assert(prev);}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}

12.单链表在pos之后插入

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

13.删除pos位置

void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SListPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;检查pos不是链表中结点 参数传错的情况assert(prev);}prev->next = pos->next;free(pos);//pos = NULL;此代码并不会改变pos 使用人在main函数将其置空}
}

14.删除pos后面位置

void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* next = pos->next;pos->next = next->next;free(next);}
}
单链表:只适合头插头删——O(1)
任意位置高效插入删除——双向链表
进阶:删除pos位置 要求是O(1) 替换法删除
缺陷:pos不能是尾结点 解决方法:将链表改成循环链表
进阶:在pos位置之前插入 要求是O(1)
方法:在pos位置后创造结点+替换法
newnode = BuySListNode(pos->val); 
pos->val = x;