关键词:
目录
2.1优点:我们可以根据实际情况,对内存进行自由分配,从而不造成内存分配浪费!
1.线性表
2.顺序存储结构(顺序表)
顺序存储结构(顺序表)的定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素
2.1顺序表一般可以分为:
1. 静态顺序表:使用定长数组存储元素
1.1静态顺序表:顺序表的大小是确定的,容量是固定的.
#define N 10000//运用宏定义,可以方便修改容量的大小
typedef int SLDataType;//运用宏定义,可以根据情况改变存储类型
// 静态顺序表
typedef struct SeqList
SLDataType a[N];
int size; // 表示数组中存储了多少个数据
SL;
结论:静态顺序表不是很常量,了解就行.
2. 动态顺序表:使用动态开辟的数组存储。(重要)
2.1优点:我们可以根据实际情况,对内存进行自由分配,从而不造成内存分配浪费!
2.2顺序表的定义
typedef int sldatatype;//根据实际情况,可以改变存储的类型
typedef struct
sldatatype* a;//开辟数组a
int size;//多少个数据
int capacity;//容量是多大
sl;
2.3顺序表的初始化
//顺序表初始化
void SeqListInit(SL* ps)
ps->a = NULL;
ps->size = ps->capacity = 0;//赋值0
//指针设为空指针,ps指向的容量和数据都赋值0
2.4顺序表增容:
请记住:两种情况都要扩容:
内存还未开辟
内存满了开辟
代码如下
void SeqListCheckCapacity(SL* ps)//顺序表扩容
// 如果没有空间或者空间不足,那么我们就扩容
if (ps->size == ps->capacity)
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
if (tmp == NULL)
printf("realloc fail\\n");
exit(-1);//扩容都要这种判断是否成功
ps->a = tmp;
ps->capacity = newcapacity;
2.5顺序表的删除
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos)
assert(pos >= 0 && pos < ps->size);//防止越界
int begin = pos + 1;//遍历从0开始,要加1//取出要删掉的数字
while (begin < ps->size)
ps->a[begin - 1] = ps->a[begin];//删掉的元素的位置后面每个元素都要往前挪.
++begin;
ps->size--;
思路 :
1.取出要删掉的数字;
2.删掉的元素的位置后面每个元素都要往前挪.
2.6顺序表的查找:
//输入你要查找的数据,找到这个数据就返回数据的下标,找不到就返回-1.
int SeqListFind(SL* ps, SLDataType x)
for (int i = 0; i < ps->size; i++)
if (ps->a[i] == x)
return i;//查找对应那个数据的下标
return -1;
思路:
1.查找你要找的数据
2.找得到,就返回该数据的下标
3.找不到就返回-1
2.7顺序表的打印
void SeqListPrint(SL* ps)
for (int i = 0; i < ps->size; ++i)
printf("%d ", ps->a[i]);
printf("\\n");
2.8顺序表的释放
顺序表释放://扩容就要释放//但只能有一个
void SeqListDestory(SL* ps)
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;//释放都要这样
2.9顺序表的插入
//顺序表插入
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
// 温柔的处理方式
/*if (pos > ps->size || pos < 0)
printf("pos invalid\\n");
return;
*///防止越界
// 粗暴的方式
assert(pos >= 0 && pos <= ps->size);
//两种方式都可以,但推荐粗暴的方式
SeqListCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= pos)
ps->a[end + 1] = ps->a[end];//增加位置,把前面的都推到后面去
--end;
ps->a[pos] = x;
ps->size++;
2.10顺序表的头插头删
顺序表头插
void SeqListPushFront(SL* ps, SLDataType x)
SeqListCheckCapacity(ps);//扩容
//挪动数据
int end = ps->size - 1;
while (end >= 0)
ps->a[end + 1] = ps->a[end];
--end;
ps->a[0] = x;
ps->size++;
//SeqListInsert(ps, 0, x);其实用插入就足够了
顺序表头删
void SeqListPopFront(SL* ps)
assert(ps->size > 0);
//挪动数据
int begin = 0;
while (begin < ps->size-1)
ps->a[begin] = ps->a[begin+1];
++ begin;
int begin = 1;
while (begin < ps->size)
ps->a[begin-1] = ps->a[begin];
++begin;
ps->size--;
//SeqListErase(ps, 0);用这个删除就足够了
2.11顺序表的尾插尾删
//顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x)
/*SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;*/
SeqListInsert(ps, ps->size, x);//用插入就可以代替
//顺序表尾删
void SeqListPopBack(SL* ps)
// 温柔处理方式
//if (ps->size > 0)
//
// //ps->a[ps->size - 1] = 0;
// ps->size--;
//
// 暴力处理方式
/*assert(ps->size > 0);
ps->size--;*/
SeqListErase(ps, ps->size-1);//用删除就可以删除
数据结构学习总结线性表之顺序表(代码片段)
...dquo;一对一”逻辑关系的数据,最佳的存储方式是使用线性表。那么,什么是线性表呢?线性表,全名为线性存储结构。使用线性表存储数据的方式可以这样理解,即“把所有数据用一根线儿串起来,再存储到物理空间中&r... 查看详情
数据结构之线性表之顺序存储java实现(代码片段)
文章目录线性表的定义线性表的基本运算线性表的存储之顺序存储定义线性表添加元素查找元素删除元素打印线性表实现的完整代码测试一下线性表的定义线性表的逻辑特征:①有且仅有一个称为开始元素的a1,她没有前... 查看详情
数据结构之顺序表(代码片段)
...找元素操作顺序表之任意位置插入顺序表之任意位置擦除线性表之查看有多少元素线性表之修改任意位置线性表之销毁空间综合SeqList.h文件内容SeqList.c文件内容前言讲完算法效率,就正式开始我们的数据结构 查看详情
线性表之栈(代码片段)
栈的定义: 一种只能在一端进行插入或删除操作的线性表被称为栈,其中允许删除或插入的一端为栈顶,另一端为栈底,栈底固定不变; 栈的特点:先进后出,例如弹夹,先装的子弹最后才能出; 按照存储结构可以... 查看详情
数据结构——线性表之顺序表篇(代码片段)
...码顺序表小结前言在介绍顺序表之前我们先简单了解一下线性表:线性表是n个具有相同特性的数据元素的有限序列,在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表... 查看详情
线性表之顺序表(代码片段)
线性表的结构体定义:#defineMaxSize100typedefstructintdata[MaxSize];intlength;Sqlist; 顺序表在内存中以数组形式保存,是一组连续的内存空间。顺序表基本算法:构造一个空的线性表://初始化线性表STATUSInitList(Sqlist&L)//置表长为0L.len... 查看详情
线性链表之顺序表
顺序表中数据元素的存储地址是其序号的线性函数,只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间是相等的,具有这一特点的存储结构称为[随机存储]。使用的基本数据结构:数组特点:顺序... 查看详情
线性表之顺序存储-顺序表(代码片段)
顺序表的操作[x]向有序顺序表插入一个元素[x]顺序表的冒泡排序[x]顺序表的删除操作[x]顺序表中元素的查找[x]顺序表的逆置[x]删除顺序表中的相同元素[x]向顺序表的指定位置插入元素[x]打印顺序表顺序表的存储结构#definemaxsize100/... 查看详情
02线性表之顺序表(代码片段)
肚子饿了就要吃 ~ 嗝 ———路飞 目录1.本章重点2.线性表3.顺序表实现3.1顺序表的概念及结构4.静态顺序表5.动态顺序表 5.1“增”尾插:头插:5.2“删”尾删头删5.3随机“插入”5.4随机“删除”5.5内存销毁5.6“改”5... 查看详情
线性表之顺序存储结构实现(上)
一,线性表的概念以及数学定义1.线性表的概念 零个或多个数据元素的有限序列。首先说明这是一个序列,也就是说数据元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都... 查看详情
数据结构学习总结线性表之单链表(代码片段)
一,回忆链表 链表,别名链式存储结构或单链表,用于存储逻辑关系为"一对一"的数据。与顺序表不同,链表不限制数据的物理存储状态,换句话说,使用链表存储的数据元素,其物理存储位置是随机的。&nbs... 查看详情
数据结构——线性表之顺序表
定义:顺序表是由一段连续的储存单元存储数据的一种简单的数据结构形式,其优点在于快速的查找存储单元的值,缺点在于时间复杂度:查找:O(1),插入和删除:O(n);对于清华大学《数据结构》——做出自己的理解;(用实例... 查看详情
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实... 查看详情
数据结构线性表之实现单链表(代码片段)
数据结构线性表之实现单链表数据结构线性表之实现单链表相关文章单链表定义单链表相关操作数据结构线性表之实现单链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实现顺序表(三)数... 查看详情
day1线性表之顺序存储
...驱和后继。存储结构用一组地址连续的存储单元以此存放线性表中的数据元素。LOC(ai)=LOC(ai-1)+sizeofLOC(ai)=LOC(a1)+(i-1)×sizeof*sizeof是每个数据元素所占存储空间大小*线性表中元素位序从一开始,数组从0开始表示方法静态1 查看详情
线性表-顺序存储结构(代码片段)
线性表-顺序存储结构顺序存储结构线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素三个属性存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置线性表的最大存储容量:... 查看详情
数据结构与算法-线性表之静态链表(代码片段)
前言:前面介绍的线性表的顺序存储结构和链式存储结构中,都有对对象地引用或指向,也就是编程语言中有引用或者指针,那么在没有引用或指针的语言中,该怎么实现这个的数据结构呢?一、简介 定义:用数组代替指针... 查看详情
数据结构与算法-线性表之循环链表(代码片段)
前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到了尾部标识就停止了向后链的操作。也就是说... 查看详情