当前位置：首页 > news >正文

《重生到现代之从零开始的数据结构生活》—— 顺序表1

news 2025/8/20 16:15:58

线性表

线性表：是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表有顺序表、链表、栈、队列、字符串等等

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

什么叫做逻辑上是线性结构嘞，就是说他在我们想象中的样子是连续的，就像是一串字符串，我们都会觉得他是连续的，但是，他在物理上不一定连续

顺序表

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

他这个数组的储存很有意思，那为什么不直接说是数组呢？非要画蛇添足的说它顺序表吗

采用数组，就是顺序表的底层逻辑是数组，但是顺序表会在他的基础上添加一些东西

顺序表的实现

首先和顺序表不可分割的就是：结构体，指针，动态内存管理

静态顺序表

typedef int  seqlista//（因为不知道什么类型的就自己定义一个类型，改的话好改）
struct seqlist{seqlista = arr[N];//定长数组int size;//有效数据的个数
}

而由于是静态的，就会出现空间的一系列问题，比如空间的大了怎么办等等

所以我们还有动态顺序表

动态顺序表

动态顺序表和静态顺序表有点不一样

typedef int  seqlista
struct seqlist
{seqlista *a;//指针int size;//有效的数据个数int capacity;//空间容量（按照份数来）
}

动态顺序表的实现

说了这么多，让我们粗略的实现一下动态顺序表吧

头文件的函数的定义

#include<stdio.h>
#include<stdlib.h>typedef int ever;struct seqlist {ever* arr;//数组int size;//有效数组个数int cap;//容量单位
};//动态顺序表void yttandb(struct seqlist* b);//初始化void pushback(struct seqlist* b, ever x);//尾插

函数的实现

#include"seqlist.h"void yttandb (struct seqlist* a) {a->arr = NULL;a->size = a->cap = 0;
}//初始化void pushback(struct seqlist* a, ever b) {if (a->size == a->cap)//空间不够{int newcap = a->cap == 0 ? a->cap = 4 : a->cap * 2;ever* tmp = (ever*)realloc(a->arr, newcap * sizeof(ever));a->arr = tmp;a->cap = newcap;}a->arr[a->size++] = b;
}

函数的调用

#include"seqlist.h"
void SLTest()
{struct seqlist sl;yttandb(&sl);pushback(&sl, 1);pushback(&sl, 2);pushback(&sl, 3);pushback(&sl, 4);
}int main()
{SLTest();return 0;
}