顺序表详解（SeqList）

本文使用C语言进行顺序表的代码实现。

博主将使用代码和相关知识相结合的方式进行讲解，简单易懂，懵懂的大学生一听就会~

顺序表是一种线性表的存储结构，它将数据元素存储在一段连续的存储空间中，每个元素占据一个存储单元，并按照逻辑顺序依次存放。顺序表可以采用数组来实现，通过数组的下标来表示元素在顺序表中的位置，从而实现对元素的快速访问和操作。

一、顺序表的定义

线性表是一种基本的数据结构，它是由一组相同类型的数据元素组成的有序序列。线性表的特点是元素之间的关系是线性的，即每个元素都有一个唯一的索引（也称为位置），并且可以通过索引访问元素。

线性表有两种常见的实现方式：顺序表和链表。顺序表是使用一组连续的内存空间来存储元素，而链表则是使用一组离散的内存空间来存储元素，并通过指针将它们连接起来。

本文讲解顺序表的代码实现。

二、顺序表的实现

我们使用多文件的方法来进行顺序表的实现。

  • SeqList.h用存放需要使用的头文件及声明函数
  • SeqList.c用来实现对于顺序表的操作函数
  • test用来进行顺序表的功能测试和使用

1.顺序表的初始化

//结构体创建
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;
	int size;     // 有效数据的个数
	int capacity; // 容量
}SL;


//顺序表初始化
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

首先创建一个结构体用来存放一个指针a，数据个数和顺序表的容量。

2.设置修改检查函数

//作为每次增添时的检查函数，如果顺序表的存储满了就进行扩容
void SeqListCheckCapacity(SL* ps)
{
	// 满了就要扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

 该函数用于检查顺序表（a）是否大小足够进行添加数据，如果大小为0那么将空间设置为4，如果不够用即用realloc扩容到原大小的二倍。，之后再对相关数值进行修改。

3.从头部插入数据

void SeqListPushFront(SL* ps, SQDataType 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++;

}

头插的方法相当于是将整个顺序表向后挪动一位，最后将第一个位置空下然后插入数据。但是挪动的顺序是从后往前挪动，如果是从前往后的话就会将数据覆盖，从而无法正常插入。

4.从尾部插入数据

void SeqListPushBack(SL* ps, SQDataType x)
{
	SeqListCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;

}

尾插就是直接向顺序表最后添加数据。

5.指定位置插入数据

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos <= ps->size);
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	//将pos位置及之后全部向后移动一位，然后再pos位置上插入x
	ps->a[pos] = x;
	ps->size++;
}

关于assert断言相关知识如果想深入学习可以点击这段话跳转至博主的另一篇博客~

首先使用assert断言进行一个条件判断，确保插入的位置合法。之后的移动数据位置的操作和头插的方法类似，将pos位置和之后的数据全部向后移动一个位置，然后再在pos这个下标的位置上添加数据。

6.从头部删除数据

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);

	
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

代码实现的操作就是将第一个位置上的位置进行覆盖，用第一个之后的数据逐一将前面一个的数据进行覆盖，从而达到删除第一个数据的效果。最后将size进行修改。

7.从尾部删除数据

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);

	ps->size--;
}

直接将顺序表的size进行-1就可以实现删除最后一个数据的操作。

8.指定位置删除数据

void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

操作与头删类似，先设置start的数值为要删除的那个下标，然后将start之后的数据依次向前挪动覆盖数据实现在该指定位置的数据删除。

9.指定位置修改数据

void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);
	ps->a[pos] = x;
}

修改数据的操作十分简单，找到该位置的下标然后进行修改即可完成操作。

10.查找数据

int SeqListFind(SL* ps, SQDataType x)
{
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

遍历顺序表，逐个进行对比，与要查找的数据相同时返回该数据位置的下标，未找到返回-1.

三、整体程序代码展现

因为指定位置插入数据的函数和指定位置删除数据的函数可以完成头插尾插，头删尾删的操作，所以在程序中直接使用这两个插入方法进行头尾的操作减少了代码量。

在test.c中通过简单的菜单和分支操作可以对顺序表进行简单的操作。

SeqList.h

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include <assert.h>


// 增强程序可维护性
typedef int SQDataType;
// 动态的
typedef struct SeqList
{
	SQDataType* a;
	int size;     // 有效数据的个数
	int capacity; // 容量
}SL;

//typedef struct SeqList SL;

// 增删查改等接口函数
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestory(SL* ps);

// 头插 尾插 头删 尾删
void SeqListPushBack(SL* ps, SQDataType x);
void SeqListPushFront(SL* ps, SQDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);
void SeqListInsert(SL* ps, int pos, SQDataType x);
void SeqListErase(SL* ps, int pos);

int SeqListFind(SL* ps, SQDataType x);
void SeqListModity(SL* ps, int pos, SQDataType x);

SeqList.c

#include "SeqList.h"

// 增删查改等接口函数

//初始化数组
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//清除内存
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//作为每次增添时的检查函数，如果顺序表的存储满了就进行扩容
void SeqListCheckCapacity(SL* ps)
{
	// 满了就要扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

// 头插 尾插 头删 尾删
void SeqListPushBack(SL* ps, SQDataType x)
{
	/*SeqListCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;*/

	SeqListInsert(ps, ps->size, x);
}

void SeqListPushFront(SL* ps, SQDataType x)
{
	//SeqListCheckCapacity(ps);

	 1、初始条件
	 2、结束条件
	 3、迭代过程
	//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 SeqListPopBack(SL* ps)
{
	//assert(ps->size > 0);

	ps->a[ps->size - 1] = 0;
	//ps->size--;
	SeqListErase(ps, ps->size - 1);
}

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);

	/*
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;*/
	SeqListErase(ps, 0);
}

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos <= ps->size);
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	//将pos位置及之后全部向后移动一位，然后再pos位置上插入x
	ps->a[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

int SeqListFind(SL* ps, SQDataType x)
{
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

//修改pos位置上的值为x
void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);
	ps->a[pos] = x;
}

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

test.c

#include "SeqList.h"

void TestSeqList1()
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushBack(&sl, 5);
	SeqListPushBack(&sl, 6);
	SeqListPushBack(&sl, 7);
	SeqListPushBack(&sl, 8);
	SeqListPushBack(&sl, 9);
	SeqListPushBack(&sl, 10);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPushBack(&sl, 11);
	SeqListPrint(&sl);

	SeqListDestory(&sl);
}

void TestSeqList2()
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushFront(&sl, 1);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);
	SeqListPushFront(&sl, 5);
	SeqListPushFront(&sl, 6);
	SeqListPrint(&sl);

	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPrint(&sl);

	SeqListPopFront(&sl);
	SeqListPrint(&sl);

	SeqListDestory(&sl);
}

void TestSeqList3()
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushFront(&sl, 1);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);
	SeqListPushFront(&sl, 5);
	SeqListPushFront(&sl, 6);
	SeqListPrint(&sl);
	SeqListInsert(&sl, 1, 20);
	SeqListPrint(&sl);

	SeqListErase(&sl, 1);
	SeqListPrint(&sl);

	SeqListDestory(&sl);
}

void menu()
{
	printf("**********************************************\n");
	printf("1.尾插数据， 2.头插数据\n");
	printf("3.尾删数据， 4.头删数据\n");
	printf("5.打印数据，-1.退出\n");
	printf("**********************************************\n");
	printf("请输入你操作选项:");
}

int main()
{
	SL s;
	SeqListInit(&s);
	int option = 0;
	int x = 0;
	while (option != -1)
	{
		menu();
		scanf("%d", &option);
		switch (option)
		{
		case 1:
			printf("请输入你要插入的数据，以-1结束\n");
			do {
				scanf("%d", &x);
				if (x != -1)
				{
					SeqListPushBack(&s, x);
				}
			} while (x != -1);
			break;
		case 2:
			break;
		case 3:
			break;
		case 4:
			break;
		case 5:
			SeqListPrint(&s);
			break;
		default:
			break;
		}
	}

	SeqListDestory(&s);

	return 0;
}

那么本篇博客到此就结束了，如果可以帮助到你是博主的荣幸！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/399557.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

VSCODE中使用Django处理后端data和data models

VSCODE中使用Django处理后端data和data models

链接&#xff1a; Python and Django tutorial in Visual Studio Code MVC的理解 在实际的程序中采用MVC的方式进行任务拆分。 Model&#xff08;模型&#xff09;负责封装应用程序的数据和业务逻辑部分。Model包含数据结构&#xff0c;数据处理逻辑以及相关的操作方法&#…
阅读更多...
Camunda和SpringBoot的兼容版本

Camunda和SpringBoot的兼容版本

官网 https://docs.camunda.org/manual/7.15/user-guide/spring-boot-integration/version-compatibility/ Camunda和SpringBoot的兼容版本
阅读更多...
安达发|APS生产排程的多机台产线详解

安达发|APS生产排程的多机台产线详解

在生产管理中&#xff0c;APS&#xff08;高级计划与排程&#xff09;系统它可以帮助企业实现生产过程的优化和效率提升。特别是在多机台产线的生产环境中&#xff0c;APS系统的作用更加明显。本文将详细解析APS生产排程的多机台产线&#xff0c;包括允许使用的最大设备数&…
阅读更多...
ai数字仿真辩论主持人提升用户体验

ai数字仿真辩论主持人提升用户体验

Ai虚拟主持人是元宇宙和AI人工智能技术在播音主持行业的重要应用&#xff0c;AI虚拟主持人能极大提升新闻资讯内容的精准度&#xff0c;改变单一的播报形式。 首先&#xff0c;AI虚拟主持人极大地提升了节目的制作效率和灵活性。传统主持人需要花费大量时间进行彩排和录制&…
阅读更多...
【JGit】分支管理实践

【JGit】分支管理实践

本文紧接【JGit】简述及学习资料整理。 以下梳理了使用 JGit 进行 Git 操作的实践 JGit实践 主函数 public static void main(String[] args) throws Exception {String localDir "D:\\tmp\\git-test\\";String gitUrl "http://192.168.181.1:3000/root/g…
阅读更多...
PFA容量瓶在半导体晶圆化学机械抛光中的用处是什么？

PFA容量瓶在半导体晶圆化学机械抛光中的用处是什么？

PFA容量瓶又称可溶性聚四氟乙烯容量瓶、特氟龙容量瓶容量瓶&#xff0c;有螺纹和插口两种可供选择&#xff0c;常用有10ml、25ml、50ml、100ml、250ml、500ml、1000ml规格 Teflon系列PFA容量瓶是一个透明的长颈瓶&#xff0c;瓶体为梨形&#xff0c;便于摇荡液体和刷洗。每一个…
阅读更多...
Linux进程（一）信号-----信号产生

Linux进程（一）信号-----信号产生

前言 在 Linux 中&#xff0c;进程具有独立性&#xff0c;进程在运行后可能 “放飞自我”&#xff0c;这是不利于管理的&#xff0c;于是需要一种约定俗成的方式来控制进程的运行&#xff0c;这就是 进程信号&#xff0c;本文将会从什么是进程信号开篇&#xff0c;讲述各种进程…
阅读更多...
harmony 鸿蒙系统学习 安装ohpm报错 ohpm install failed

harmony 鸿蒙系统学习 安装ohpm报错 ohpm install failed

一. 安装配置 DevEco Studio 安装包时报错 execute ohpm install failed. Install task failed: ArkTS 3.2.12.5. Install ArkTS dependencies failed. 解决办法 找原因&#xff0c;首先&#xff0c;我的电脑中之前安装过node&#xff0c;也许是因为这个。&#xff08;其实…
阅读更多...
Redis之缓存雪崩问题解决方案

Redis之缓存雪崩问题解决方案

文章目录 一、书接上文二、介绍三、解决方案1. 锁2. 不同的过期时间3. 缓存预热和定时任务 一、书接上文 Redis之缓存穿透问题解决方案实践SpringBoot3Docker 二、介绍 缓存雪崩&#xff0c;指大量的缓存失效&#xff0c;大量的请求又同时落在数据库。主要的一种诱因是key设…
阅读更多...
先进电机技术——步进电机与伺服电机

先进电机技术——步进电机与伺服电机

一、步进电机 步进电机是一种特殊类型的电动机&#xff0c;它的工作方式是将输入的电脉冲信号转换成精确的机械运动——通常是转子的角位移或直线移动。每接收到一个电脉冲信号&#xff0c;步进电机内部的定子绕组按顺序通电&#xff0c;产生磁场变化&#xff0c;使得与之相互…
阅读更多...
企业级人脸美颜和美妆解决方案

企业级人脸美颜和美妆解决方案

视觉营销日益重要&#xff0c;而人脸美颜和美妆作为视觉营销的关键环节&#xff0c;更是受到了众多企业的关注。美摄科技&#xff0c;作为国内领先的人脸美颜和美妆解决方案提供商&#xff0c;以其先进的技术和卓越的产品&#xff0c;助力企业打造完美视觉体验&#xff0c;提升…
阅读更多...
STM32引脚重定义问题

STM32引脚重定义问题

最近在搞资源管理&#xff0c;发现有些引脚不能用 比如这个PE引脚。我想用他输出PWM&#xff0c;但是不能用&#xff0c;我也重定义了&#xff0c;还是不能用。回去翻看了技术手册。 RCC_APB2PeriphClockCmd(RCC_APB2Periph_AFIO, ENABLE); //重映射引脚功能&#xff0c;需…
阅读更多...
Flutter自定义tabbar任意样式

Flutter自定义tabbar任意样式

场景描述 最近在使用遇到几组需要自定义的tabbar或者类似组件&#xff0c;在百度查询资料中通常&#xff0c;需要自定义 TabIndicator extends Decoration 比如上图中的带圆角的指示器这样实现 就很麻烦&#xff0c; 搜出来的相关也是在此之处上自己画&#xff0c;主要再遇…
阅读更多...
2.20号qt

2.20号qt

1.Qt中的信息调试类 &#xff08;输出类&#xff09; QDebug //1.类似与printf qDebug("%s","hello kittiy"); //2. 类似与cout 默认有换行 比较常用的方式 qDebug() << "你好" ; //1.类似与printf qDebug("%s",&q…
阅读更多...
dubbo源码中设计模式——注册中心中工厂模式的应用

dubbo源码中设计模式——注册中心中工厂模式的应用

工厂模式的介绍 工厂模式提供了一种创建对象的方式&#xff0c;而无需指定要创建的具体类。 工厂模式属于创建型模式&#xff0c;它在创建对象时提供了一种封装机制&#xff0c;将实际创建对象的代码与使用代码分离。 应用场景&#xff1a;定义一个创建对象的接口&#xff0…
阅读更多...
Kotlin基本语法 4 类

Kotlin基本语法 4 类

1.定义类 package classStudyclass Player {var name:String "jack"get() field.capitalize()set(value) {field value.trim()} }fun main() {val player Player()println(player.name)player.name " asdas "println(player.name)} 2.计算属性与防范…
阅读更多...
【Python】 剪辑法欠采样 CNN压缩近邻法欠采样

【Python】 剪辑法欠采样 CNN压缩近邻法欠采样

借鉴&#xff1a;关于K近邻&#xff08;KNN&#xff09;&#xff0c;看这一篇就够了&#xff01;算法原理&#xff0c;kd树&#xff0c;球树&#xff0c;KNN解决样本不平衡&#xff0c;剪辑法&#xff0c;压缩近邻法 - 知乎 但是不要看他里面的代码&#xff0c;因为作者把代码…
阅读更多...
QEMU源码全解析 —— virtio（20）

QEMU源码全解析 —— virtio（20）

接前一篇文章&#xff1a; 上回书重点解析了virtio_pci_modern_probe函数。再来回顾一下其中相关的数据结构&#xff1a; struct virtio_pci_device struct virtio_pci_device的定义在Linux内核源码/drivers/virtio/virtio_pci_common.h中&#xff0c;如下&#xff1a; /* O…
阅读更多...
话说激励广告

话说激励广告

一、导言 如果一个入场口令是请问效率秘诀是&#xff1a; _ _ _&#xff0c;_ _ _ _。&#xff0c;然后她会告诉你通过小程序&#xff1a; 点“试彩蛋”&#xff0c;看完视频广告之后可以得到答案&#xff0c;这种形式是不是有点意思。这就是激励广告的一种应用场景。 激励…
阅读更多...
[ai笔记8] 聊聊openAI最新文生视频产品-Sora

[ai笔记8] 聊聊openAI最新文生视频产品-Sora

欢迎来到文思源想的ai空间&#xff0c;这是技术老兵重学ai以及成长思考的第8篇分享&#xff01; 近期sora在科技届引发不小的轰动&#xff0c;虽然这是openai并未对外发布的相关产品&#xff0c;目前如同小米汽车的技术发布会&#xff0c;但是确实引发了不小的震撼&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023