系列文章目录
第一章 时间复杂度和空间复杂度
第二章 顺序表,列表
第三章 栈和队列
第四章 二叉树
第五章 排序
作者:🎈乐言🎈
简介:🎈大一学生,目前在致力于c/c++/python,高数的学习,有问题尽管问我,关注后私聊!
持续更新专栏:《c进阶》,《数据结构修炼》🚀(优质好文持续更新中)🎈
文章目录
目录
系列文章目录
文章目录
前言
线性表
各个接口的实现
1.初始化顺序表
2.销毁顺序表
3.检查顺序表容量是否满了
4.顺序表尾插
5.顺序表尾删
6.顺序表头插
7.顺序表头删
8.在顺序表中查找定值
9.在顺序表指定位置插入数据
链表
无头单向循环链表的实现
单链表定义:
动态申请一个节点
销毁(释放)所有节点
打印单链表
单链表头插
单链表尾删
单链表头部删除
单链表在pos位置之后插入
单链表中删除位置为pos的节点
单链表删除指定pos位置之后的节点
求单链表的长度:
判断但俩表是否为空
总结
前言
在顺序表和链表的学习过程中,相信大家会有一些困惑,因为这里用到了大量结构体和数组的知识,乐言在这里将会对顺序表和单链表进行深刻的讲解,有代码问题,可以后台私信作者!!!!!!!!如果文章有错误,欢迎指正!!!!!!
🚀线性表
#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;
else
newcapacity = 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);
}
求单链表的长度:
遍历寻找是否为空即可文章来源:https://www.toymoban.com/news/detail-432322.html
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;
}
🚀总结
本文具体写了顺序表和单链表增删查改的一系列操作,希望各位同志们也要动手操作一下,这样才能融会贯通,熟稔于心文章来源地址https://www.toymoban.com/news/detail-432322.html
到了这里,关于数据结构修炼第二篇:顺序表和链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!