数据结构修炼第二篇：顺序表和链表

文章列表

数据结构修炼第二篇：顺序表和链表

系列文章目录

第一章时间复杂度和空间复杂度

第二章顺序表，列表

第三章栈和队列

第四章二叉树

第五章排序

作者：🎈乐言🎈

简介：🎈大一学生，目前在致力于c/c++/python，高数的学习，有问题尽管问我，关注后私聊！

持续更新专栏：《c进阶》，《数据结构修炼》🚀（优质好文持续更新中）🎈

文章目录

系列文章目录

文章目录

前言

线性表

各个接口的实现

1.初始化顺序表

2.销毁顺序表

3.检查顺序表容量是否满了

4.顺序表尾插

5.顺序表尾删

6.顺序表头插

7.顺序表头删

8.在顺序表中查找定值

9.在顺序表指定位置插入数据

链表

无头单向循环链表的实现

单链表定义：

动态申请一个节点

销毁（释放）所有节点

打印单链表

单链表头插

单链表尾删

单链表头部删除

单链表在pos位置之后插入

单链表中删除位置为pos的节点

单链表删除指定pos位置之后的节点

求单链表的长度：

判断但俩表是否为空

总结

前言

在顺序表和链表的学习过程中，相信大家会有一些困惑，因为这里用到了大量结构体和数组的知识，乐言在这里将会对顺序表和单链表进行深刻的讲解，有代码问题，可以后台私信作者！！！！！！！！如果文章有错误，欢迎指正！！！！！！

🚀线性表

线性表（linear list）是n个具有相同特性的数据元素的 有限序列 。线性表是一种在实际中广泛使

用的数据结构，常见的线性表： 顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在 物理结构上并不一定是连续的 ，

线性表在物理上存储时，通常以 数组和 链式结构 的形式存储

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存

储。在数组上完成数据的增删查改。

顺序表有静态的和动态的两种，首先我们来看 静态的顺序表的代码：

#define N 10000
typedef int sldataline;
struct Seqline
{sldataline a[N];int size;
};

我们在这里可以发现，静态的顺序表开辟的内存是固定的，给多了浪费空间，给少了又不够，还得重新调整代码，所以静态的顺序表十分不好用，在实际的生活场景中用的也不多。

所以我们通常使用动态的顺序表：

typedef int SLDataType;
typedef struct Seqlist
{SLDataTpye *a;size_t size;size_t capacity
}SeqList;

我们要加上容量空间，同时size为存储的有效数据的个数

如果空间不够就可以扩容

🚀各个接口的实现

1.初始化顺序表

要防止传进来的指针为空，所以一定要提前加上断言

void SeqListInit(SeqList*psl)
{assert(psl!=NULL);psl->size=0;psl->capacity=0;
}

2.销毁顺序表

依然要记得加上断言，防止传进来的指针是空指针

void SeqListDestory(SeqList*psl)
{assert(psl!=NULL);free(psl->a);psl->size=0;psl->capacity=0;
}

首先释放开辟的空间，然后将指针置为空，将数据和空间容量大小都重置为0

3.检查顺序表容量是否满了

如果我们一个个加入数据，这样重复操作对我们来说太过麻烦，所以我们可以一次性扩容两倍，这样能应付大多数情况，两倍是一个折中的方式

void CheckCapacity(SeqList*psl)
{assert(psl!=NULL);if(psl->size == psl->capacity){size_t newcapacity;if(psl->capacity == 0)newcapacity = psl->capacity = 4;elsenewcapacity = 2 * psl->capacity;}SLDataTpye*p=(SLDataType*)realloc(psl->a,newcapacity*sizeof(SLDataType));//扩容if(p == NULL){perror("realloc");exit(-1);}psl->p;psl->capacity = newcapacity;
}

4.顺序表尾插

void SeqListPushBack(Seqlist*psl,SLDataType x)
{assert(psl !=NULL);CheckCapacity(psl);psl->a[psl->size] =x;psl->size++;
}

5.顺序表尾删

void SeqListPopBack(SeqList*psl)
{assert(psl->NULL);assert(psl->size >0);psl->size --;
}

因为我们无法得知SLDataType是什么类型，他随时都可以改，因此我们不能单纯直接将随意赋值为0（psl->a[psl->size-1]=0)

6.顺序表头插

因为顺序表是连续存储的，所以我们在顺序表头部插入的时候，我们要依次挪动数据

void SeqListPushFront(SeqList*psl,SLDType x)
{assert(psl);CheckCapacity(psl);int i = 0;for(i=psl->size-1;i>=0;i--){psl->a[i+1] = psl->a[i];}psl->a[0] = x;psl->size++;
}

7.顺序表头删

因为顺序表是连续存储的，所以要依次挪动数据

void SeqListPopFront(SeqList* psl)
{assert(psl);assert(psl->size >0);int i =0;for(i=1;i<psl->size;i++){psl->a[i-1]=psl->a[i];}psl->size--;
}

依次覆盖即可，然后再把有效数据-1；

8.在顺序表中查找定值

int SeqListFind(const SeqList*psl,SLDataType x)
{assert(psl);int i = 0;for(i=0;i<psl->size;i++){if(psl->[i]==x){return i;}}return -1;
}

9.在顺序表指定位置插入数据

void SeqListInsert(SeqList*psl,size_t pos,SLDataType x)
{assert（psl）；assert（pos>=0 && pos <=psl->size);CheckCapacity(psl);size_t i =0;for(i=psl->size;i>pos;i--){psl->a[i]=psl->a[i-1];}psl->a[pos]=x;psl->size++;
}

🚀链表

顺序表我们在使用时，虽然下标可以随时访问，但是会出现一系列问题会引起我们的思考

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看

🚀无头单向循环链表的实现

第一步我们依然是先新建一个工程：

SList.h（单链表的类型定义，函数接口声明，引用头文件）
SList.c（单链表各个接口函数的实现）
test.c（主函数，测试函数的各个接口功能）

单链表定义：

单链表类似如图结构

一部分储存结构体的数据，另一部分储存下一块结构体空间的地址

代码如下：

typedef int SLDatatype;//定义单链表数据类型typedef struct SListNode//定义单链表节点
{SLDataType data;//数据空间struct SListNode*next；//指针空间
}SListNode;

动态申请一个节点

代码如下：

SListNode* BuySListNode(SLTDataType x)
{SListNode* node=(SListNode*)malloc(sizeof(SListNode));if(node == NULL){perror("malloc");return;}
}

销毁（释放）所有节点

我们在这里有一个遍历链表的操作

{SListNode* node = (SListNode*)malloc(sizeof(SListNode));if (node == NULL){perror("malloc");return;}node->data = x;node->next = NULL;
}
void SListDestory(SListNode** pphead)
{assert(pphead);SListNode* cur = *pphead;while (cur != NULL){SListNode* next = cur->next;free(cur);}*pphead = NULL;
}

最后不能忘了置空指针

打印单链表

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

单链表尾插

下面是一个明显的错误

代码看似逻辑清晰，其实问题暴露无遗。此处的指针传参，相当于把plist指针变量的值拷贝给phead给phead赋值newhead，phead的值改变是不会影响plist

这种写法会导致一个问题：

当链表为空时，我们需要改变plist的指向，让他指向第一个节点，然而初始值plist和phead都指向NULL，调用函数后，phead指向了新的节点，但是plist还是指向NULL

问题出现，我们又该如何解决？

plist指向的是第一个节点的指针，想要在函数中改变plist的值（指向），必须把plist指针进行指针传参，因为plist原本就是一级指针，我们要想改变他，我们只能取他的地址进行传参

在函数中，我们想要改变int的值，就要传递int*,当我们想要传递int*的时候，我们就要传递int**......

正确写法是通过二级指针传参，改变plist的指向

单链表为空的时候，plist直接指向新节点

单链表不为空，会找到尾部节点，然后将尾部节点的next指向新节点！！！

//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{assert(pphead);SListNode* newnode = BuyListNode(x);if (*pphead == NULL)*pphead = newnode;else if (**pphead != NULL){SListNode* tail = *phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

单链表头插

头插具体实现算法如图：

新数据的next指向plist指向的节点

代码实现：

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

单链表尾删

思想：

1：找到链表尾节点的上一个节点。

2：双指针，分别找到链表尾节点和它上一个节点

如图所示：

当单链表只有一个节点时，删除节点，plist指向NULL

而当单链表有多个节点时，先找到单链表尾节点的前一个节点，删除，然后将该节点的next指向NULL

可能会改变plist的指向，所以我们要用二级指针接受

代码如下：

void SListPopBack(SListNode** pphead)
{assert(pphead);assert(*pphead);SListNode* tail = *pphead;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

如果pphead为空，那么直接释放＋置空

如果pphead不为空，那么直接判断下一个节点是否为空为空则置空，不为空则继续判断

思路2代码实现：

void SListPopBack(SListNode** phead)
{assert(pphead);assert(*pphead);SListNode* tail = *pphead;SListNode* prev = *pphead;while (tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;
}

单链表头部删除

void SListPopFront(SListNode** pphead)
{assert(pphead);assert(**pphead);SListNode* cur = *pphead;*pphead = cur->next;free(cur);cur = NULL;
}

将*pphead移向第二个节点即可。

在单链表中查找指定点的节点

SListNode* SListFind(SListNode** pphead, SLDataType x)
{SListNode* cur = *pphead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

单链表在pos位置之后插入

我们只需在pos位置的next指向一个新开辟的地址，新地址的next指向原来的下一个地址

代码实现：

void SListInsertAfter(SListNode* pos, SLDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

单链表中删除位置为pos的节点

考虑到pos位置可能为第一个节点，所以我们有必要选择进行语句

代码如下：

void SListDel(SListNode** pphead,SListNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead){SListPopFront(pphead);}else{SListNode* prev = *pphead;while (prev->next != pos)prev = prev->next;}prev->next = pos->prev;free(pos);pos = NULL;
}

单链表删除指定pos位置之后的节点

图示：

代码实现：

此处我们要定义一个新的指针，来存放pos的下一个节点的地址

void SListDelAfter(SListNode* pos)
{assert(pos);assert(pos->next);SListNode* posnext = pos->next;pos->next = pos->next->next;free(posnext);
}

求单链表的长度：

遍历寻找是否为空即可

int SListSize(SListNode* phead)
{int size = 0;SListNode* cur = phead;while (cur != NULL){size++;cur = cur->next;}return size;
}

判断但俩表是否为空

bool SListEmpty(SListNode* phead)
{return phead == NULL;
}

🚀总结

本文具体写了顺序表和单链表增删查改的一系列操作，希望各位同志们也要动手操作一下，这样才能融会贯通，熟稔于心

数据结构修炼第二篇：顺序表和链表

系列文章目录

文章目录

前言

🚀线性表

🚀各个接口的实现

1.初始化顺序表

2.销毁顺序表

3.检查顺序表容量是否满了

4.顺序表尾插

5.顺序表尾删

6.顺序表头插

7.顺序表头删

8.在顺序表中查找定值

9.在顺序表指定位置插入数据

🚀链表

🚀无头单向循环链表的实现

单链表定义：

动态申请一个节点

销毁（释放）所有节点

打印单链表

单链表头插

单链表尾删

单链表头部删除

单链表在pos位置之后插入

单链表中删除位置为pos的节点

单链表删除指定pos位置之后的节点

求单链表的长度：

判断但俩表是否为空

🚀总结

公告

标签

数据结构修炼第二篇：顺序表和链表

系列文章目录

文章目录

前言

🚀线性表

🚀各个接口的实现

1.初始化顺序表

2.销毁顺序表

3.检查顺序表容量是否满了

4.顺序表尾插

5.顺序表尾删

6.顺序表头插

7.顺序表头删

8.在顺序表中查找定值

9.在顺序表指定位置插入数据

🚀链表

🚀无头单向循环链表的实现

单链表定义：

动态申请一个节点

销毁（释放）所有节点

打印单链表

单链表头插

单链表尾删

单链表头部删除

单链表在pos位置之后插入

单链表中删除位置为pos的节点

单链表删除指定pos位置之后的节点

求单链表的长度：

判断但俩表是否为空

🚀总结

相关问题

公告

标签