【数据结构】知识点一：线性表之顺序表

内容导航

  • 一、什么是线性表？
  • 二、什么是顺序表？
    • 1、顺序表的概念
    • 2、顺序表的结构
      • a. 静态顺序表：使用定长数组存储元素。
      • b. 动态顺序表：使用动态开辟的数组存储。
  • 三、顺序表的接口实现精讲
    • 1.接口一：打印数据
    • 2.接口二：表初始化
    • 3.接口三：数据销毁
    • 4.接口四：尾插数据
    • 5.接口五：尾删数据
    • 6.接口六：头插数据
    • 7.接口七：头删数据
    • 8.接口八：容量检查
    • 9.接口九：任意位置的插入
    • 9.接口九：任意位置的删除
    • 10.接口十：任意数据的查找
  • 四、源代码分享
    • 1.SeqList.h
    • 2.SeqList.c
    • 3.test.c

一、什么是线性表？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

二、什么是顺序表？

1、顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

2、顺序表的结构

a. 静态顺序表：使用定长数组存储元素。

b. 动态顺序表：使用动态开辟的数组存储。

三、顺序表的接口实现精讲

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

1.接口一：打印数据

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLPrint(SL* ps1)								//打印数据
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)
	{
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}

2.接口二：表初始化

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLInit(SL* ps1)							//初始化顺序表，全部为0
{
	assert(ps1);
	ps1->a = NULL;
	ps1->size = 0;
	ps1->capacity = 0;
}

3.接口三：数据销毁

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLDestroy(SL* ps1)							//销毁顺序表
{
	assert(ps1);
	if (ps1->a != NULL)							
	{
		free(ps1->a);
		ps1->a = NULL;
		ps1->size = 0;
		ps1->capacity = 0;
	}
}

4.接口四：尾插数据

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLPushBack(SL* ps1, SLDataType x)			//尾插入
{
	assert(ps1);
	SLCheckCapacity(ps1);						//检查容量
	ps1->a[ps1->size] = x;
	ps1->size++;
}

5.接口五：尾删数据

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLPopBack(SL* ps1)							//尾删除
{
	assert(ps1);
	assert(ps1->size > 0);						//有效数据为0则不需要删
	ps1->size--;
}

6.接口六：头插数据

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLPushFront(SL* ps1, SLDataType x)		//头插入
{
	assert(ps1);
	SLCheckCapacity(ps1);						//检查容量
	//往后挪动数据
	int end = ps1->size - 1;
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[0] = x;
	ps1->size++;
}

7.接口七：头删数据

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLPopFront(SL* ps1)						//头删除
{
	assert(ps1);
	assert(ps1->size > 0);						//有效数据为0则不需要删
	//往前挪动数据
	int begin = 1;
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];
		begin++;
	}
	ps1->size--;
}

8.接口八：容量检查

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLCheckCapacity(SL* ps1)					//检查空间是否充足，若否，使空间充足，头插尾插都要用到
{
	assert(ps1);
	if (ps1->size == ps1->capacity)
	{
		int NewCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps1->a = tmp;
		ps1->capacity = NewCapacity;
	}
}

9.接口九：任意位置的插入

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLInsert(SL* ps1, int pos, SLDataType x)	//任意位置的插入
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性
	SLCheckCapacity(ps1);						//检查容量

	//往后挪动数据
	int end = ps1->size - 1;
	while (end > pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}

9.接口九：任意位置的删除

<font color=black size=4 font face=黑体" >代码之函数的定义：

void SLErase(SL* ps1, int pos)					//任意位置的删除
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性
	//往前挪动数据
	int begin = pos+1;
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];
		begin++;
	}
	ps1->size--;
}

10.接口十：任意数据的查找

<font color=black size=4 font face=黑体" >代码之函数的定义：

int SLFind(SL* ps1, SLDataType x)				//查找某个数据，找到返回下标，未找到返回-1
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)			//直接遍历查找
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

四、源代码分享

1.SeqList.h

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;							//开辟的数组地址
	int size;								//有效数据个数
	int capacity;							//容量空间的大小
}SL;

void SLPrint(SL* ps1);						//打印数据
void SLInit(SL* ps1);						//初始化顺序表，全部为0
void SLDestroy(SL* ps1);					//销毁顺序表


void SLPushBack(SL* ps1, SLDataType x);		//尾插入
void SLPushFront(SL* ps1, SLDataType x);	//头插入
void SLPopBack(SL* ps1);					//尾删除
void SLPopFront(SL* ps1);					//头删除

void SLInsert(SL* ps1, int pos, SLDataType x);	//任意位置的插入
void SLErase(SL* ps1, int pos);					//任意位置的删除

int SLFind(SL* psl, SLDataType x);				//查找某个数据，找到返回下标，未找到返回-1

2.SeqList.c

#include"SeqList.h"

void SLPrint(SL* ps1)								//打印数据
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)
	{
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}

void SLInit(SL* ps1)							//初始化顺序表，全部为0
{
	assert(ps1);
	ps1->a = NULL;
	ps1->size = 0;
	ps1->capacity = 0;
}

void SLDestroy(SL* ps1)							//销毁顺序表
{
	assert(ps1);
	if (ps1->a != NULL)							
	{
		free(ps1->a);
		ps1->a = NULL;
		ps1->size = 0;
		ps1->capacity = 0;
	}
}

void SLCheckCapacity(SL* ps1)					//检查空间是否充足，若否，使空间充足，头插尾插都要用到
{
	assert(ps1);
	if (ps1->size == ps1->capacity)
	{
		int NewCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps1->a = tmp;
		ps1->capacity = NewCapacity;
	}
}
void SLPushBack(SL* ps1, SLDataType x)			//尾插入
{
	assert(ps1);
	SLCheckCapacity(ps1);						//检查容量
	ps1->a[ps1->size] = x;
	ps1->size++;
}

void SLPushFront(SL* ps1, SLDataType x)		//头插入
{
	assert(ps1);
	SLCheckCapacity(ps1);						//检查容量
	//往后挪动数据
	int end = ps1->size - 1;
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[0] = x;
	ps1->size++;
}

void SLPopBack(SL* ps1)							//尾删除
{
	assert(ps1);
	assert(ps1->size > 0);						//有效数据为0则不需要删
	ps1->size--;
}

void SLPopFront(SL* ps1)						//头删除
{
	assert(ps1);
	assert(ps1->size > 0);						//有效数据为0则不需要删
	//往前挪动数据
	int begin = 1;
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];
		begin++;
	}
	ps1->size--;
}

void SLInsert(SL* ps1, int pos, SLDataType x)	//任意位置的插入
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性
	SLCheckCapacity(ps1);						//检查容量

	//往后挪动数据
	int end = ps1->size - 1;
	while (end > pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}

void SLErase(SL* ps1, int pos)					//任意位置的删除
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性
	//往前挪动数据
	int begin = pos+1;
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];
		begin++;
	}
	ps1->size--;
}

int SLFind(SL* ps1, SLDataType x)				//查找某个数据，找到返回下标，未找到返回-1
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)			//直接遍历查找
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

3.test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void menu()
{
	printf("********************************\n");
	printf("****1、尾插数据  2、尾删数据****\n");
	printf("****3、头插数据  4、头删数据****\n");
	printf("****5、打印数据  0、退出    ****\n");
	printf("********************************\n");
}

int main()
{
	SL s;
	SLInit(&s);

	int option = 0;
	do
	{
		menu();
		printf("请输入你的选择:>");
		scanf("%d", &option);
		if (option == 1)
		{
			printf("请依次输入你的要尾插数据个数和数据:>");
			int n = 0;
			scanf("%d", &n);
			for (int i = 0; i < n; i++)
			{
				int x = 0;
				scanf("%d", &x);
				SLPushBack(&s, x);
			}
		}
		else if (option == 2)
		{
			printf("请依次输入你的要尾删数据的个数:>");
			int n = 0;
			scanf("%d", &n);
			for (int i = 0; i < n; i++)
			{
				SLPopBack(&s);
			}
		}
		else if (option == 3)
		{
			printf("请依次输入你的要头插数据个数和数据:>");
			int n = 0;
			scanf("%d", &n);
			for (int i = 0; i < n; i++)
			{
				int x = 0;
				scanf("%d", &x);
				SLPushFront(&s, x);
			}
		}
		else if (option == 4)
		{
			printf("请依次输入你的要头删数据的个数:>");
			int n = 0;
			scanf("%d", &n);
			for (int i = 0; i < n; i++)
			{
				SLPopFront(&s);
			}
		}
		else if (option == 5)
		{
			SLPrint(&s);
		}
		else if (option == 0)
		{
			break;
		}
		else
		{
			printf("无此选项，请重新输入\n");
		}
	} while (option != 0);
	SLDestroy(&s);
	return 0;
}

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

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

相关文章

肿瘤相关巨噬细胞TAM综述及研究学习②

肿瘤相关巨噬细胞TAM综述及研究学习②

​​​​​​​肿瘤浸润性巨噬细胞的复杂作用&#xff08;综述浏览&#xff09;-CSDN博客 TAM 支持癌细胞的生长和转移&#xff0c;并对 TME 的适应性免疫细胞产生免疫抑制作用。&#xff08;上一篇学习文献&#xff09; 目录 综述① TAM在肿瘤中的作用 M1与 M2 TAM作用 …
阅读更多...
图论 - 最小生成树（Prime、Kruskal）

图论 - 最小生成树（Prime、Kruskal）

文章目录 前言Part 1&#xff1a;Prim算法求最小生成树1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 Part 2&#xff1a;Kruskal算法求最小生成树1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 前言 本篇博客介绍两种求最小生成树的方法&#xff…
阅读更多...
Linux笔记--Vim编辑器

Linux笔记--Vim编辑器

一、vi和vim vi编辑器是所有Unix及Linux系统下标准的编辑器&#xff0c;类似于Windows系统下的记事本。很多软件默认使用vi作为他们编辑的接口。vim是进阶版的vi,vim可以视为一种程序编辑器。 复制/etc/passwd文件到自己的目录下(不要直接修改letc/passwd)&#xff0c;后面使用…
阅读更多...
k8s资源管理之声明式管理方式

k8s资源管理之声明式管理方式

1 声明式管理方式 1.1 声明式管理方式支持的格式 JSON 格式&#xff1a;主要用于 api 接口之间消息的传递 YAML 格式&#xff1a;用于配置和管理&#xff0c;YAML 是一种简洁的非标记性语言&#xff0c;内容格式人性化&#xff0c;较易读 1.2 YAML 语法格式&#xff1a; ●…
阅读更多...
k8s 集群调度，标签，亲和性和反亲和性，污点和容忍，pod启动状态 排错详解

k8s 集群调度，标签，亲和性和反亲和性，污点和容忍，pod启动状态 排错详解

目录 pod启动创建过程 kubelet持续监听的原因 调度概念 调度约束 调度过程 优点 原理 优先级选项 示例 指定调度节点 标签基本操作 获取标签帮助 添加标签&#xff08;Add Labels&#xff09;&#xff1a; 更新标签&#xff08;Update Labels&#xff09; 删除标…
阅读更多...
基于springboot+vue的中国陕西民俗网

基于springboot+vue的中国陕西民俗网

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…
阅读更多...
家政按摩上门服务小程序搭建

家政按摩上门服务小程序搭建

家政按摩上门服务小程序支持技师入驻申请&#xff0c;用户可以通过在线下单预约家政服务&#xff0c;并根据距离、价格、销量好评度等条件进行筛选和选择。用户可以选择技师进行预约&#xff0c;并填写自己的服务地点和时间&#xff0c;享受上门服务。同时&#xff0c;技师也可…
阅读更多...
C++_数据类型_整形

C++_数据类型_整形

数据类型 C规定在创建一个变量或常量时&#xff0c;必须要指定出相应得数据类型&#xff0c;否则无法给变量分配内存 整形 作用 整形变量表示的是整数型的数据 方式 越界
阅读更多...
攻防世界-get_post

攻防世界-get_post

题目信息 相关知识 -G&#xff1a;表示GET请求&#xff0c;缺省POST -d参数用于发送 POST 请求的数据体 使用-d参数以后&#xff0c;HTTP 请求会自动加上标头Content-Type : application/x-www-form-urlencoded。并且会自动将请求转为 POST 方法&#xff0c;因此可以省略-X PO…
阅读更多...
跨站脚本攻击xss-labs(1-20)靶机练手

跨站脚本攻击xss-labs(1-20)靶机练手

目录 一、跨站脚本攻击&#xff08;XSS&#xff09; 1.1 漏洞简介 1.2:类型 1.3 XSS危害 1.4XSS防御规则 二、环境搭建 三、xsst通关记录 Level 1&#xff1a;文本解析为 HTML Level 2&#xff1a;htmlspecialchars;input 标签 value 注入 定义和用法 字符过滤绕过 …
阅读更多...
pytorch基础2-数据集与归一化

pytorch基础2-数据集与归一化

专题链接&#xff1a;https://blog.csdn.net/qq_33345365/category_12591348.html 本教程翻译自微软教程&#xff1a;https://learn.microsoft.com/en-us/training/paths/pytorch-fundamentals/ 初次编辑&#xff1a;2024/3/2&#xff1b;最后编辑&#xff1a;2024/3/2 本教程…
阅读更多...
2024-03-01（金融AI行业与大数据生态圈）

2024-03-01（金融AI行业与大数据生态圈）

1.金融这一块的算法&#xff0c;不像推荐系统&#xff0c;图像等领域&#xff0c;金融领域的算法都比较成熟了。现在来说门槛低&#xff0c;属于初期阶段&#xff0c;上升期。 2.反欺诈的数据标签比较少&#xff0c;有一种“标签染色”的方法来做反欺诈模型的标签。 3.常用反…
阅读更多...
什么是Vue指令？请列举一些常见的Vue指令以及它们的用法

什么是Vue指令？请列举一些常见的Vue指令以及它们的用法

Vue.js 是一款流行的前端框架&#xff0c;它的指令&#xff08;Directives&#xff09;是 Vue.js 提供的一种特殊属性&#xff0c;用于在模板中对 DOM 元素进行直接操作。指令通常是以 v- 开头的特殊属性&#xff0c;用于响应式地将数据绑定到 DOM 元素上。 在 Vue 中&#xf…
阅读更多...
【NTN 卫星通信】卫星和无人机配合的应用场景

【NTN 卫星通信】卫星和无人机配合的应用场景

1 场景概述 卫星接入网是一种有潜力的技术&#xff0c;可以为地面覆盖差地区的用户提供无处不在的网络服务。然而&#xff0c;卫星覆盖范围对于位于考古或采矿地点内部/被茂密森林覆盖的村庄/山谷/靠近山丘或大型建筑物的用户可能很稀疏。因此&#xff0c;涉及卫星接入和无人驾…
阅读更多...
131. 分割回文串（力扣LeetCode）

131. 分割回文串（力扣LeetCode）

文章目录 131. 分割回文串题目描述回溯代码 131. 分割回文串 题目描述 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1&#xff1a; 输入&#xf…
阅读更多...
C#，基于密度的噪声应用空间聚类算法（DBSCAN Algorithm）源代码

C#，基于密度的噪声应用空间聚类算法（DBSCAN Algorithm）源代码

1 聚类算法 聚类分析或简单聚类基本上是一种无监督的学习方法&#xff0c;它将数据点划分为若干特定的批次或组&#xff0c;使得相同组中的数据点具有相似的属性&#xff0c;而不同组中的数据点在某种意义上具有不同的属性。它包括许多基于差分进化的不同方法。 E、 g.K-均值…
阅读更多...
kafka文件存储机制和消费者

kafka文件存储机制和消费者

1.broker文件存储机制 去查看真正的存储文件&#xff1a; 在/opt/module/kafka/datas/ 路径下 kafka-run-class.sh kafka.tools.DumpLogSegments --files ./00000000000000000000.index 如果是6415那么这个会存储在563的log文件之中&#xff0c;因为介于6410和10090之间。 2.…
阅读更多...
STM32使用FlyMcu串口下载程序与STLink Utility下载程序

STM32使用FlyMcu串口下载程序与STLink Utility下载程序

文章目录 前言软件链接一、FlyMcu串口下载程序原理优化手动修改跳线帽选项字节其他功能 二、STLink Utility下载程序下载程序选项字节固件更新 前言 本文主要讲解使用FlyMcu配合USART串口为STM32下载程序、使用STLink Utility配合STLink为STM32下载程序&#xff0c;以及这两个…
阅读更多...
Stable Diffusion 模型分享：AAM XL (Anime Mix)（动漫截屏风格 XL）

Stable Diffusion 模型分享：AAM XL (Anime Mix)（动漫截屏风格 XL）

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八 下载地址 模型介绍 AAM XL (Anime Mix) 是一个动漫截屏风格的模型&#xff0c;是 AAM - AnyLoRA Anime Mix 模…
阅读更多...
【办公类-25-01】20240302 UIBOT上传 ”班级主页-育儿知识（家园小报）“

【办公类-25-01】20240302 UIBOT上传 ”班级主页-育儿知识（家园小报）“

作品展示&#xff1a; 一、背景需求&#xff1a; 本学期制作了 “育儿知识&#xff08;家园小报&#xff09;”合并A4内容 【办公类-22-08】周计划系列&#xff08;4&#xff09;“育儿知识&#xff08;家园小报&#xff09;“ &#xff08;2024年调整版本&#xff09;-CSDN博…
阅读更多...
最新文章

Copyright @ 2022~2023