首页 > 其他分享 >数据结构（顺序表）

数据结构（顺序表）

时间：2024-09-29 13:47:32浏览次数：12  
标签：ps arr 顺序 capacity int SLDataType 数据结构 size

无论你期望或者不期望，清晨依旧来临。 -- 谏山创 《进击的巨人》

线性表的概念

1.线性表是n个具有相同特性的数据元素的有限序列。

2.线性表在逻辑上是线性结构，但是在物理结构上并不⼀定是连续的。

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

顺序表的概念

1. 顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构.

2. ⼀般情况下采⽤数组存储，即顺序表是对数组的封装,实现了常⽤的增删改查等接口。

3. 顺序表的底层是数组，但是在数组基础上，添加了很多其他的功能。

  形象的理解，把数组比作成一辆黄包车，那么顺序表就是一辆专车，除了把你运输到目的地之外，还能提供其他黄包车没有的服务，让你更加舒服。

顺序表的分类

静态顺序表

1. 使⽤定⻓数组存储元素。

2. 空间给少了不够⽤，给多了造成空间浪费。

3. 一般不用静态顺序表。

#define N 7 //方便后期修改成其他数字大小,一键替换
typedef int SLDataType; //方便后期修改成其他类型,一键替换
typedef struct SeqList
{
	SLDataType a[N];//定长数组
	int size;//有效的数据个数
}SL;//把struct SeqList结构体重命名为SL

动态顺序表

1. 结构体成员变量声明时不能初始化。（但可以宏定义）

typedef int SLDataType;//方便后期修改成其他类型,一键替换
typedef struct SeqList
{
	SLDataType* arr;//一个指针，所以不需要考虑数组大小
    int capacity;//顺序表的容量
	int size;//有效数据大小
}SL;//把struct SeqList结构体重命名为SL

动态顺序表的初始化

传数值初始化
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;
void Init_SQL((SL s)
{
	s.arr = NULL;
	s.size = s.capacity = 0;
	return 0;
}
int main()
{
	SL s;
	Init_SQL(s);//由于传值，所以函数调用完后，形参空间释放，实参无影响，故还是没有初始化
	return 0;
}
传地址初始化
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;
void Init_SQL(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	return 0;
}
int main()
{
	SL s;
	Init_SQL(&s);
	return 0;
}
//ps->相当于*(p.s)

1. 如果直接传值，那么结构体变量s将无法初始化，因为形参初始化完后，就直接释放了内存空间。 

2. 如果传地址的话，那么形参和实参共用一块地址，所以结构体变量s就能实现初始化。

动态顺序表的销毁

void Kill_SQL(SL* ps)
{
	if (ps->arr != NULL)//如果arr不是空指针，则进入去释放arr的空间
	{
		free(ps->arr);//释放空间
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	return 0;
}

1. 顺序表的销毁与初始化很像，多了一个操作：如果结构体变量s1占用了内存，那么先释放内存，再将结构体变量s1赋值为0。

动态顺序表的增容 

1. 增容一般成倍数增容，一般2倍或者3倍。

void LargerSQL(SL* ps, SLDataType x)
{
	assert(ps);//防止传入空指针
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;//更新指针
		ps->capacity = NEWcapacity;//更新成员内容
	}
	ps->arr[ps->size++] = x;//尾部插入
	return 0;
}

动态顺序表尾插数据

void End_Add(SL* ps, SLDataType x)
{
	assert(ps);//防止传入空指针
	if (ps->size== ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)relloc(ps->arr, NEWcapacity  * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;//更新指针
		ps->capacity = NEWcapacity;//更新成员内容
	}
	ps->arr[ps->size] = x;//尾部插入
    ps->size++;
	return 0;
}

动态顺序表头插数据

void Head_Add(SL* ps, SLDataType x)
{
	assert(ps);//防止传入空指针
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size;i>0; i--)//把后size个数据整体向后移动一位
	{
		ps->arr[i] = ps->arr[i - 1];
	}
    ps->arr[0]=x;//在最前面插入新成员
    ps->size++;
	return 0;
}

动态顺序表尾删数据

void End_Less(SL* ps)
{
	assert(ps);//防止传入空指针，没有初始化
	assert(ps->size);//防止没有有效数据
	ps->size--;//有效成员个数减一
	return 0;
}

动态顺序表头删数据

void Head_Less(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 1; i < ps->size-1; i++)//除了第一个数组成员，其余的都往前移一位
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;//有效成员个数减一
	return 0;
}

 动态顺序表任意位置增加数据

1. 在第pos个成员之后增加一个数据。

void Free_Add(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos > 0 && pos < ps->size);
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
	return 0;
}

动态顺序表任意位置删除数据

2. 在第pos个成员之后删除一个数据。 

void Free_Less(SL* ps, int pos)
{
	assert(ps);
	assert(pos > 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
	return 0;
}

动态顺序表的成员查找

int Find_Group(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("找到了\n");
			printf("下标是%d\n",x);
			return x;
		}
	}
	printf("没有找到\n");
	return -1;//如果没有找到则返回一个无效的下标
}

 动态顺序表的打印

void Print_SQL(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}

综合示例的代码 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//一个指针，所以不需要考虑数组大小
	int capacity;//顺序表的容量
	int size;//有效数据大小
}SL;//把struct SeqList结构体重命名为SL
void Init_SQL(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	return;
}
void End_Add(SL* ps, SLDataType x)
{
	assert(ps);//防止传入空指针
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;//更新指针
		ps->capacity = NEWcapacity;//更新成员内容
	}
	ps->arr[ps->size++] = x;//尾部插入
	return;
}
void Print_SQL(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	return;
}
void Head_Add(SL* ps, SLDataType x)
{
	assert(ps);//防止传入空指针
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > 0; i--)//把后size个数据整体向后移动一位
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//在最前面插入新成员
	ps->size++;
	return;
}
void End_Less(SL* ps)
{
	assert(ps);//防止传入空指针，没有初始化
	assert(ps->size);//防止没有有效数据
	ps->size--;//有效成员个数减一
	return;
}
void Head_Less(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 1; i < ps->size ; i++)//除了第一个数组成员，其余的都往前移一位
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;//有效成员个数减一
	return;
}
void Free_Add(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos > 0 && pos < ps->size);
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
	return 0;
}
void Free_Less(SL* ps, int pos)
{
	assert(ps);
	assert(pos > 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
	return 0;
}
int Find_Group(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("找到了\n");
			printf("下标是%d\n",x);
			return x;
		}
	}
	printf("没有找到\n");
	return -1;//如果没有找到则返回一个无效的下标
}
void Kill_SQL(SL* ps)
{
	if (ps->arr != NULL)//如果arr不是空指针，则进入去释放arr的空间
	{
		free(ps->arr);//释放空间
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	return 0;
}
int main()
{
	SL s;
	//Init_SQL(&s);
	//Print_SQL(&s);

	//End_Add(&s,3);
	//Head_Add(&s, 4);
	//Print_SQL(&s);
	//Head_Add(&s, 5);
	//Print_SQL(&s);
	//End_Less(&s);
	//Print_SQL(&s);
	//Head_Less(&s);
	//Print_SQL(&s);
	//Free_Add(&s,1,0);
	//Print_SQL(&s);
	//Free_Less(&s, 1);
	//Print_SQL(&s);
	//int num=Find_Group(&s,4);
	//printf("%d", num);

	//Kill_SQL(&s);
	//Print_SQL(&s);
	return 0;
}

1. 这是一个包含了顺序表的各种功能函数的综合示例。

2. 当我们需要看看是否符合我们预期时候，可以直接用打印方式进行查看。

致谢

  感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！

标签：ps,arr,顺序,capacity,int,SLDataType,数据结构,size
From： https://blog.csdn.net/hsy1603914691/article/details/142280812

相关文章

  • C++ 静态顺序表和动态顺序表
    对比静态顺序表与动态顺序表特性静态顺序表动态顺序表大小固定动态内存管理简单复杂随机访问快速快速插入/删除效率较低较低（需移动元素）扩展能力不可扩展可扩展C++静态顺序表概述定义：静态顺序表是一种线性表的实现方式，采用一段连续的内存空间存储数据元素，具有固定的大小。在......
  • 算法实战：剖析 Redis 常用的数据类型对应的数据结构
    算法实战：剖析Redis常用的数据类型对应的数据结构Redis是一个非常流行的内存数据库，它提供了多种数据类型，每种数据类型都有其特定的数据结构支持。了解这些数据结构对于深入理解Redis的工作原理和优化使用非常重要。本文将剖析Redis常用的数据类型对应的数据结构，并通......
  • 18年408数据结构
    第一题：解析：这道题很简单，按部就班的做就可以了。画出S1，S2两个栈的情况：S1:      S2:                    2        +        3        -        8        *......
  • 第5周 5.1 顺序与选择结构
    5.1顺序与选择结构5.1.1顺序结构顺序结构是程序中最简单、最基本的流程控制结构，它按照程序中语句出现的先后顺序依次执行，直到程序的结束。顺序结构示例：publicclassHelloWorld{publicstaticvoidmain(String[]args){System.out.println("Hel......
  • 数据结构设计
    数据结构设计设计有setAll功能的哈希表加时间戳#include<vector>#include<iostream>#include<algorithm>#include<unordered_map>usingnamespacestd;//<key,<val,time>>unordered_map<int,pair<int,int>>map;intsetA......
  • 关于RocketMQ的顺序消息
     在RocketMQ中，实现顺序消息的确需要一些特定的配置和注意事项。1.**OrderProducerBean**:使用OrderProducerBean可以保证消息的顺序发送。它会将消息发送到同一个队列中，从而保证顺序。然而，确保顺序的前提是所有相关的消息都应该使用相同的键（key）进行发送，以确保它们被路......
  • 嵌入式学习--数据结构+算法
    嵌入式学习--数据结构+算法数据结构1.1数据1.2逻辑结构1.3存储结构1）顺序存储结构2）链式存储结构1.4操作（数据的运算）算法2.1算法与程序2.2算法与数据结构2.3算法的特性2.4如何评价一个算法的好坏？2.5时间复杂度2.6空间复杂度数据结构数据的逻辑结构、存储结构、......
  • 【数据结构】堆（Heap）详解
     在深入了解堆这一重要的数据结构之前，不妨先回顾一下我之前的作品——“二叉树详解”。上篇文章......
  • 数据结构：速通并查集
    并查集用来干什么：处理不相交的集合的合并以及查询相交集合的个数等情况例题（自行搜索）：36024年第一批笔试算法题传染病防控 并查集具有三个操作initfindunioninit初始化集合，将当前所有节点的父节点设置为自己intfa[]=newint[10000];intsize[]=newint[10000];//这里是......
  • 类中静态代码块、静态属性加载顺序
     1、如果静态属性在静态代码块前面classFoo{publicFoo(){System.out.println("我是Example的静态属性foo");System.out.println("未修改的静态属性值为====>"+Example.staticVariable);Example.staticVariable=2;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99