关键词：

文章目录

• 顺序表
• • 1. 线性表
  • 2. 顺序表
  • 3. 顺序表基本概念
  • 4. 顺序表实现
  • • 顺序表初始化
    • 顺序表的扩容
    • 顺序表的插入
    • 顺序表的删除
    • 顺序表的查找
    • 顺序表的修改
    • 顺序表的销毁
  • 5. 顺序表总结

---

顺序表

1. 线性表

线性表：线性表是由n个具有相同特性的数据元素组成的序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串。

数据结构中包括逻辑结构和物理结构两个层次

• 逻辑结构

  数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立与计算机的。所以，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

  数据的逻辑结构有两个要素：一是数据元素，二是关系。数据元素的含义如前所述，关系是指数据元素之间的逻辑关系。它根据元素之间关系的不同特性，通常有4类基本结构。

• 集合结构

  数据元素之间除了属于同一个集合的关系外，没有其它关系。

• 线性结构

  数据元素之间存在这一对一的关系，比如将一些学生的信息按照它的学号按照先后顺序排序，组成一个线性结构

• 树结构

  数据元素之间存在着一对多的关系，比如在班级管理体系中，班长管理多个组长，每个组长管理多名组员

• 图结构

  数据元素之间存在着多对多的关系，比如多位同学之间的朋友关系，任何两个同学都可以是朋友，从何构成图结构。

• 物理结构

  数据对象在计算机中的存储表示称为存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求既要存储数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个节点来表示。

  物理结构又可以分为顺序存储和链式存储。顺序表和链表就是典型代表。

2. 顺序表

3. 顺序表基本概念

顺序表使用一段连续物理地址的存储单元依次存储数据元素的一种线性结构，简单来说就是一个数组，一个可以动态增长的数组，并且要求里面存储的数据必须是从左往右是连续的。然后在这个数组上完成增删改查。顺序表的特点是逻辑上相邻的数据元素，物理上也是相邻的

顺序表的缺陷

1. 动态扩容有性能消耗
2. 如果在头部插入数据，需要挪动元素

顺序表的存储结构

typedef int SeqDataType;
typedef struct SeqList 

	SeqDataType* arr;//指向动态开辟数组首元素
	size_t size;//存放元素个数
	size_t capacity;//容量
SeqList;

4. 顺序表实现

静态的顺序表只适合用于知道需要存储多少数据的场景，如果静态的顺序表定义的数组太大就会出现浪费，而定义的太小就会不够用。所以使用动态的顺序表会更加合理，通过动态分配空间来实现顺序表。

typedef int SeqDataType;
typedef struct SeqList 

	SeqDataType* arr;
	size_t size;//存放元素个数
	size_t capacity;//容量
SeqList;

//初始化顺序表
void SeqListInit(SeqList* pq);
//销毁顺序表
void SeqListDestory(SeqList* pq);
//打印顺序表元素
void SeqListPrint(SeqList* pq);
//判断顺序表是否为空
int SeqListEmpty(SeqList* pq);
//获取顺序表元素个数
size_t SeqListSize(SeqList* pq);
//判断扩容顺序表
int CheckCapacity(SeqList* pq);
//尾插
void SeqListPushBack(SeqList* pq, SeqDataType data);
//头插
void SeqListPushFront(SeqList* pq, SeqDataType data);
//删除末尾元素
void SeqListPopBack(SeqList* pq);
//删除头部元素
void SeqListPopFront(SeqList* pq);
//在顺序表中查找元素
SeqDataType SeqListFind(SeqList* pq, SeqDataType data);
//获取指定位置的数据元素
SeqDataType SeqListGet(SeqList* pq, size_t pos);
//在顺序表pos位置插入数据
void SeqListInsert(SeqList* pq, size_t pos, SeqDataType data);
//删除顺序表中pos位置的元素
void SeqListErase(SeqList* pq, size_t pos);
//修该顺序表pos位置的元素
void SeqListModify(SeqList* pq, size_t pos, SeqDataType target);

这里我只实现比价关键的接口

顺序表初始化

顺序表初始化比较简单，只需要通过malloc开辟一块合适的空间就好.

1. 判断结构体是否为空
2. 初始化容量为10
3. 使用malloc函数开辟空间

//初始化顺序表
void SeqListInit(SeqList* pq)

	assert(pq);
	pq->capacity = 10;
	pq->arr = (SeqDataType*)malloc(sizeof(int) * pq->capacity);
	if (pq->arr == NULL)
	
		printf("初始化失败\\n");
		exit(1);
	
	memset(pq->arr, 0, sizeof(int) * pq->capacity);//给顺序表初始化
	pq->size = 0;

顺序表的扩容

如果在插入数据元素的时候发现满了就要进行扩容，通过realloc来对数组进行扩容，需要进行扩容的数组进行判空。

1. 如果当前元素个数等于数组容量就进行扩容
2. 使用realloc对数组进行二倍扩容
3. 如果扩容失败，则什么都不做
4. 扩容成功就把结构体数组指向扩容空间的首地址

//判断扩容顺序表
int CheckCapacity(SeqList* pq)

	if (pq->size == pq->capacity)
	
		//二倍扩容
		pq->capacity = pq->capacity * 2;
		SeqDataType* ptr = (SeqDataType*)(realloc(pq->arr, sizeof(int) * pq->capacity));
		if (ptr == NULL)
		
			printf("扩容失败\\n");
			pq->capacity = pq->capacity / 2;
			return 1;
		
		pq->arr = ptr;
		printf("扩容成功\\n");
	

	return 0;

顺序表的插入

顺序表元素插入分为3种，从头部插入、从末尾插入、从指定位置插入。其实只要实现了从指定位置插入，头插和尾插都可以调用指定位置插入的接口。指定位置插入思路。

1. 首先得判NULL和是否越界
2. 判断是否需要扩容
3. 从最后一个元素位置开始，将元素从前往后移动

//在顺序表pos位置插入数据
void SeqListInsert(SeqList* pq, size_t pos, SeqDataType data)

	assert(pq);
	assert(pos <= pq->size);//越界判断
	CheckCapacity(pq);
	size_t index = pq->size;
	while (index > pos)
	
		pq->arr[index] = pq->arr[index - 1];
		index--;
	
	pq->arr[pos] = data;
	pq->size++;

比如要在下标为2的位置插入元素

实现了指定位置插入之后，头插和尾插就比较简单了

头插

//头插
void SeqListPushFront(SeqList* pq, SeqDataType data)

	assert(pq);
	
	SeqListInsert(pq, 0, data);

尾插

//尾插
void SeqListPushBack(SeqList* pq, SeqDataType data)

	assert(pq);

	SeqListInsert(pq, pq->size, data);

顺序表插入元素的时间复杂度是$O(N)$

顺序表的删除

顺序表的删除分为头删、尾删和指定位置删除，和插入类似，只需要从后往前挪动元素将要删除的元素覆盖即可。

1. 判NULL和是否越界
2. 将pos位置的元素全部往前挪动
3. 元素个数减1

//删除顺序表中pos位置的元素
void SeqListErase(SeqList* pq, size_t pos)

	assert(pq);
	assert(pos < pq->size);
	size_t index = pos;
	while (index < pq->size - 1)
	
		pq->arr[index] = pq->arr[index + 1];
		index++;
	
	pq->size--;

完成了指定位置删除就可以，调用它完成头删和尾删了

头删

//删除头部元素
void SeqListPopFront(SeqList* pq)

	assert(pq);

	SeqListErase(pq, 0);

尾删

//删除末尾元素
void SeqListPopBack(SeqList* pq)

	assert(pq);
	assert(pq->size != 0);
	
	SeqListErase(pq, pq->size-1);

顺序表删除的时间复杂为$O(N)$

顺序表的查找

顺序表的查找分两种，一种是查找指定数据元素返回下标，另外一种是直接获取某个下标的元素

查找元素

//在顺序表中查找元素
SeqDataType SeqListFind(SeqList* pq, SeqDataType data)

	assert(pq);
	size_t i = 0;
	for (i = 0; i < pq->size; i++)
	
		if (pq->arr[i] == data)
		
			//返回第一个找到的元素的下标
			return i;
		
	

	return -1;

获取指定位置的元素

//获取指定位置的数据元素
SeqDataType SeqListGet(SeqList* pq, size_t pos)

	assert(pq);
	assert(pos < pq->size);

	return pq->arr[pos];

顺序表查找的时间复杂度为$O(N)$，但如果是给定下标获取元素则是$O(1)$

顺序表的修改

顺序表的修改指定下标的元素，也是非常简单的

//修该顺序表pos位置的元素
void SeqListModify(SeqList* pq, size_t pos, SeqDataType target)

	assert(pq);
	assert(pos < pq->size);

	pq->arr[pos] = target;

顺序表的修改时间复杂度为$O(N)$

顺序表的销毁

顺序表的销毁只需要

1. 把元素个数容量赋值成0

2. 将开辟的内存空间释放掉

3. 再将数组指向NULL

//销毁顺序表
void SeqListDestory(SeqList* pq)

	assert(pq);
	pq->size = 0;
	pq->capacity = 0;
	free(pq->arr);
	pq->arr = NULL;

5. 顺序表总结

1. 顺序表的插入和删除时间复杂度为$O(N)$
2. 顺序表的扩容使用的是realloc，如果后面的空间不够就会重新开辟新的空间，再把数据拷贝到新的空间，这样就会有一定的额性能消耗
3. 顺序表存在着一定的资源浪费，比如当前顺序表的容量为200，当放满之后再插入10个元素，就会进行2倍扩容到400，此时就浪费了190个数据空间。

我们发现顺序表存在着一定缺陷，如果想不那么浪费空间就想着扩容扩少一点，但扩容小了如果有大量数据插入又会存着不断扩容的情况，那么又会有着性能的消耗。

针对以上问题，就可以引入链表。
下一篇链表博客马上发布。

---

c语言带头双向循环链表增删改查的实现(代码片段)

...，一般用在单独存储数据，但实际中使用的链表数据结构大多数都是带头双向循环链表。带头双向循环链表虽然结构复杂，但是实际上实现起来比单链表和顺序表都要更加简单，这篇博客的内容就是带头双向循环... 查看详情

c语言顺序表的动态存储：增删改查的实现(代码片段)

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。使用定长数组存储的是静态顺序表，使用动态开辟的数组存储的是动态顺序表。以下是... 查看详情

数据结构单链表singlelinkedlist，java实现单链表增删改查(代码片段)

文章目录链表介绍应用示例链表介绍链表是有序的列表，但是它在内存中是存储是不连续的，如下：链表是以节点的方式来存储，是链式存储：①每个节点包含data域存储数据，next域指向下一个节点②链表... 查看详情

python2和python3操作mysql数据库实现创建表删除表增删改查操作(代码片段)

1、MySQL数据库和表的编码格式（1）创建数据库并指定字符集mysql>createdatabasetestpythondbcharactersetutf8;QueryOK,1rowaffected,1warning(0.60sec)（2）查看数据库的编码格式mysql>showvariableslike'charact 查看详情

r操作mysql数据库创建表删除表增删改查（crud）(代码片段)

R操作MySQL数据库创建表、删除表、增删改查（CRUD） 关系数据中的数据是按照一定范式去存储的。当我们需要非常高级和复杂的Sql查询就可以使用关系数据库的数据资产。不光java和python可以容易地连接到数据库，R也可以很容... 查看详情

c/c++数据结构-完整代码队列queue（顺序存储，链式存储）增删改查(代码片段)

C/C++数据结构-完整代码（一）数据结构的理论，线性表（动态数组，链表）（完整的算法代码-增删改查-代码解析+运行结果解析）C/C++数据结构-完整代码（二）栈（栈的顺... 查看详情

海上生明月，天涯共此时，mysql表增删改查的中秋大礼包来啦！！！(代码片段)

这里写目录标题MySQL表的增删改查数据库约束notnulluniquedefaultprimarykeyforeignkey新增查询聚合查询groupbyhaving联合查询（多表查询）外连接自连接子查询合并查询MySQL表的增删改查数据库约束notnull指定某列不能存null值createtable[... 查看详情

mybatis实现单表增删改查操作

mybatis是对持久层进行了封装、mybatis文档地址：https://mybatis.org/mybatis-3/zh/index.html下面实现单表的增删改查操作。1.新建maven项目命名为mybatis、并在pom.xml中引入相关依赖<?xmlversion="1.0"encoding="UTF-8"?><projectxmlns="http://maven.ap 查看详情

djangoorm单表增删改查(代码片段)

一简单增删改查1.增User.objects.create(name=‘Alan‘,age=10,birthday=‘2018-08-08‘)user=User(name=‘Alan‘,age=10,birthday=‘2018-08-08‘)user.save()2.查询#操作的结果拥有是一个listusers=User.objects.filter(name=‘Owen‘)#只能操作有且只有一条数据记录user=Us... 查看详情

初级web---完成一个基础的学生表增删改查(代码片段)

在之前的基础上[简易的网站登录注册,注销退出操作]添加了登录失效拦截,(在session中存入登录用户的信息,若存储信息的当前session被销毁,则拦截请求,强制跳转到登录页面)会话销毁有三种情况:(1)服务器关闭时,session对象销毁;(2)在... 查看详情

mybatis实现部门表增删改查以及排序

废话不说,直接开门见山!需要在WebContent下的lib下导入两个包mybatis-3.2.5.jarojdbc6.jar 1packagecom.xdl.entity;23importjava.io.Serializable;45publicclassDeptimplementsSerializable{6privateIntegerdeptno;//类型和名称与表保持一致7pri 查看详情

c/c++数据结构-完整代码队列queue（顺序存储，链式存储）增删改查(代码片段)

队列1、队列的基本概念队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行... 查看详情

数据结构-顺序表详解(c语言版)(代码片段)

目录顺序表概念及结构概念：顺序表的动态存储顺序表的实现（C语言版本）顺序表功能：各功能的实现：零：头文件部分一、初始化顺序表二、打印顺序表三、顺序表的销毁四、检查顺序表五、插入数据... 查看详情

mybatis实现对数据库的增删改查(代码片段)

...构如图：本次主要是对tb_brand表实现增删改查。创建先后顺序创建的先后顺序我在前一篇博客已经说清楚了，就不再赘述了，如果不知道如何创建的话，说明对mybatis还是不了解，建立仔细看一看上一篇博客，这是链接：一篇博客... 查看详情

orm多表增删改查(代码片段)

一 创建多表在models.py里创建4张表：Author（作者）、AuthorDetail（作者详细信息）、Publish（出版社）、Book（书）四张表关系为： （1）首先创建一对一关系。OneToOneField（）创建Author表classAuthor(models.Model):name=models.CharField(max_... 查看详情

数据结构--顺序表的实现(c语言实现)(代码片段)

最近终于开始学数据结构了，开个坑记录一下首先，顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为：1.静态... 查看详情

动态链表增删改查及排序功能

主要功能的实现：#include"SeqList.h"voidInitSeqList(SeqList*pSeq)//初始化{ assert(pSeq); pSeq->array=(DataType*)malloc(sizeof(DataType)*DEFAULT_CAPICITY); pSeq->size=0; pSeq->capicity=DEFAULT_CAPICITY;}v 查看详情

orm的单表增删改查

一、与数据库的映射关系         类名<－－－－－－－>表名        属性<－－－－－－－>字段属性的约束<－－－－－－－>字段的类型  实例对象... 查看详情