【数据结构初阶】顺序表SeqList

描述

顺序表我们可以把它想象成在一个表格里面填数据，并对数据做调整；

那我们的第一个问题是：怎么样在创建出足够的空间呢？

我们可以去堆上申请，用一个指针指向一块空间，如果申请的空间不够，我们可以再realloc申请出来。

我们的第二个问题是：怎么样标记我们用了多少空间呢？

这时我们就需要一个变量来记录我们当前的用到第几个“格子”（即用了多少空间），我们这里用size来表示：

我们的第三个问题是：怎么样知道我们有空间呢？

这时我们就需要一个变量来记录我们“格子”总数（即拥有多少空间），我们这里用capacity来表示：

所以（在.h文件中）我们线性表的结构体描述为：

typedef int SLDataType;

typedef struct SeList
{
	SLDataType* a;
	int size;
	int capacity;
}SL;

组织

  1. 初始化
  2. 释放
  3. 尾插
  4. 尾删
  5. 头插
  6. 头删
  7. 指定位置删除
  8. 指定位置插入
  9. 查找指定元素

1.初始化

把我们描述出来的顺序表结构体里的变量初始化

在.h文件中：

因为要对创建出来的结构体里的内容进行修改，所以函数要进行传址调用；

在.c文件中:

我们用malloc来开辟空间,同时注意检查malloc；

因为我们刚刚开辟空间，并没有往顺序表里增删查改 所以此时size为0；

而我们的capacity就是在malloc开辟的空间大小。

void SLInit(SL* ps)
{
	assert(ps->a);

	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

2.释放

将描述出来的顺序表结构体里的变量逐个进行释放；

在.h 文件中：

在.c文件中：

首先是指针a，需要使用free函数将其释放，还需要注意的是free后，需要将a置空，避免出现野指针；

因为size和capacity是临时变量储存在栈上，函数调用结束后会自动释放，我们这里把它改为0就可以了。

void SLDestroy(SL* ps)
{
	assert(ps->a);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

3.尾插

向顺序表的尾部插入数据；

在.h 文件中：

在.c文件中：

尾插数据时，首先，需要判断capacity（空间）是否足够，如果不够需要扩容，这里我们写个扩容函数：

扩容我们用realloc函数，最后要返回ps至尾插函数判断是否为空；

接着，才能将数据尾插；

最后别忘了调整size的位置；

SL* SLExpand(SL* ps)
{
	assert(ps->a);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)* ps->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return NULL;
		}
		ps->capacity *=2;
		ps->a = tmp;
	}
	return ps;
}

void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps->a);
	//扩容
	if (ps->size == ps->capacity)
	{
		SL* ret = SLExpand(ps);
		if (ret == NULL)
		{
			return;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;

}

4.尾删

将顺序表的尾部删除；

在.h 文件中：

在.c 文件中：

因为顺序表是从开始连续存储size个数据，不能单独释放那一块区域，所以我们直接将size--就可以了，如果往后插入的话，就直接把数据覆盖；

assert（）如果当capacity为空的时候还尾删时会报错,并且终止程序；

void SLPopBack(SL* ps)
{
	assert(ps->a);
	ps->size--;
}

5.头插

向顺序表的头部插入数据；

在.h 文件中：

在.c 文件中：

首先，我们得先判断空间是否足够，如果不够就扩容；

第二步：把数据往后移一位，数据从最后一位开始向后移动；

第三步：进行数据头插，别忘了把size的大小改改；

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps->a);

	//扩容
	if (ps->size == ps->capacity)
	{
		SL* ret = SLExpand(ps);
		if (ret == NULL)
		{
			return;
		}
	}

	//移动数据
	for (int i = ps->size; i >0 ; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	//头插
	ps->a[0] = x;
	ps->size++;

}

6.头删

将顺序表的头部数据删除；

在.h 文件中：

在.c 文件中：

我们只需要将从第二位数据开始往前移动，把前一位的数据覆盖就可以达到头删的效果；

void SLPopFront(SL* ps)
{
	assert(ps->a);
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

7.指定位置删除

将顺序表的指定位置数据删除；

在.h 文件中：

在.c 文件中：

首先，要先用assert检查一下空间和size的值是否合理；

如果删除的数据是最后一个就直接尾删；

如果如果删除的数据不是最后一个就需要移动数据覆盖，类似于头删；

void SLErase(SL* ps, int pos)
{
	assert(ps->a);
	assert(pos >= 0&&pos<ps->size);

	//如果pos是最后一个数据，尾删
	if (pos == ps->size - 1)
	{
		SLPopBack(ps);
	}

	else
	{
		for (int i = pos; i < ps->size; i++)
		{
			ps->a[i] = ps->a[i + 1];
		}
		ps->size--;
	}

	
}

8.指定位置插入

将顺序表的指定位置数据插入；

在.h 文件中：

在.c 文件中：

首先，要先用assert检查一下空间和size的值是否合理；

如果删除的数据是最后一个就直接尾插；

如果如果删除的数据不是最后一个就需要移动数据，再插入数据，类似于头插；

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps->a);
	assert(pos >= 0 && pos <= ps->size);

	//判断容量
	if (ps->size == ps->capacity)
	{
		SL* ret = SLExpand(ps);
		if (ret == NULL)
		{
			return;
		}
	}

	//尾插
	if (pos == ps->size - 1)
	{
		SLPushBack(ps,x);
	}
	else
	{
		for (int i = ps->size; i > pos; i--)
		{
			ps->a[i] = ps->a[i - 1];
		}
		ps->size++;
		ps->a[pos] = x;
	}
}

9.查找指定元素

在顺序表中查找指定数据，并输出其下表，和在该表中的个数；

在.h 文件中：

在.c 文件中：

for循环遍历一下顺序表，如果遍历过程中找到了直接打印其下标，并用一个变量记录它出现的此数。

出循环后打印其和在该表中出现的个数。

void SLFindPoint(SL* ps, SLDataType x)
{
	assert(ps->a);
	
	int cnt = 0;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			cnt++;
			printf("找到了第%d个，下标为:%d\n",cnt, i);
		}
	}
	if (cnt == 0)
	{
		printf("抱歉，无该数据\n");
	}
	else
	{
		printf("共找到%d个数据\n", cnt);
	}
}

整个程序

.h文件：

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

typedef int SLDataType;
#define INIT_CAPACITY 4

typedef struct SeList
{
	SLDataType* a;
	int size;
	int capacity;
}SL;

void SLPrint(SL* ps);

void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLErase(SL* ps,int pos);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLFindPoint(SL* ps, SLDataType x);

.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"


void SLPrint(SL* ps)
{
	assert(ps->a);

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


void SLInit(SL* ps)
{
	assert(ps->a);

	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

void SLDestroy(SL* ps)
{
	assert(ps->a);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

SL* SLExpand(SL* ps)
{
	assert(ps->a);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)* ps->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return NULL;
		}
		ps->capacity *=2;
		ps->a = tmp;
	}
	return ps;
}

void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps->a);
	//扩容
	if (ps->size == ps->capacity)
	{
		SL* ret = SLExpand(ps);
		if (ret == NULL)
		{
			return;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;

}

void SLPopBack(SL* ps)
{
	assert(ps->a);
	ps->size--;
}

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps->a);

	//扩容
	if (ps->size == ps->capacity)
	{
		SL* ret = SLExpand(ps);
		if (ret == NULL)
		{
			return;
		}
	}

	//移动数据
	for (int i = ps->size; i >0 ; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	//头插
	ps->a[0] = x;
	ps->size++;

}

void SLPopFront(SL* ps)
{
	assert(ps->a);
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

void SLErase(SL* ps, int pos)
{
	assert(ps->a);
	assert(pos >= 0&&pos<ps->size);

	//如果pos是最后一个数据，尾删
	if (pos == ps->size - 1)
	{
		SLPopBack(ps);
	}

	else
	{
		for (int i = pos; i < ps->size; i++)
		{
			ps->a[i] = ps->a[i + 1];
		}
		ps->size--;
	}

	
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps->a);
	assert(pos >= 0 && pos <= ps->size);

	//判断容量
	if (ps->size == ps->capacity)
	{
		SL* ret = SLExpand(ps);
		if (ret == NULL)
		{
			return;
		}
	}

	//尾插
	if (pos == ps->size - 1)
	{
		SLPushBack(ps,x);
	}
	else
	{
		for (int i = ps->size; i > pos; i--)
		{
			ps->a[i] = ps->a[i - 1];
		}
		ps->size++;
		ps->a[pos] = x;
	}
}

void SLFindPoint(SL* ps, SLDataType x)
{
	assert(ps->a);
	
	int cnt = 0;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			cnt++;
			printf("找到了第%d个，下标为:%d\n",cnt, i);
		}
	}
	if (cnt == 0)
	{
		printf("抱歉，无该数据\n");
	}
	else
	{
		printf("共找到%d个数据\n", cnt);
	}
}

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

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

相关文章

第十六届山东省职业院校技能大赛高职组“软件测试”赛项规程

第十六届山东省职业院校技能大赛高职组“软件测试”赛项规程

第十六届山东省职业院校技能大赛 高职组“软件测试”赛项规程 一、赛项名称 赛项名称&#xff1a;软件测试 赛项组别&#xff1a;高职组 赛项专业大类&#xff1a;电子与信息大类 二、竞赛目的 软件是新一代信息技术的灵魂&#xff0c;是数字经济发展的基础&#xff0c;是…
阅读更多...
汽车ECU的虚拟化技术初探(一)

汽车ECU的虚拟化技术初探(一)

目录 1.为什么要提汽车ECU的虚拟化&#xff1f; 2.虚拟化技术分类 2.1 硬件虚拟化 2.2 操作系统虚拟化 问题引入&#xff1a; Hypervisor是如何来管理和隔离硬件资源&#xff0c;保证各个不同功能的应用程序的资源使用安全和资源调度&#xff1f;没有MMU就做不了虚拟化&am…
阅读更多...
Clickhouse学习笔记（11）—— 数据一致性

Clickhouse学习笔记（11）—— 数据一致性

使用合并树引擎时&#xff0c;无论是ReplacingMergeTree还是SummingMergeTree&#xff0c;都只能保证数据的最终一致性&#xff0c;因为数据的去重、聚合等操作会在数据合并的期间进行&#xff0c;而合并会在后台以一个不确定的时间进行&#xff0c;因此无法预先计划&#xff1…
阅读更多...
基于SSM的停车场管理系统设计与实现

基于SSM的停车场管理系统设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。你想解决的问题&#xff0c;今天给大家介绍…
阅读更多...
Spring基础学习——web

Spring基础学习——web

Spring基础学习——web 一、Spring整合Web环境1.1 JavaWeb三大组件作用及其特点1.2 Spring整合Web环境的思路及实现1.3 Spring开发Web环境组件spring-web1.4 web层MVC框架思想与设计思路 一、Spring整合Web环境 1.1 JavaWeb三大组件作用及其特点 在Java语言当中&#xff0c;w…
阅读更多...
creo6.0教程之旋转，扫描

creo6.0教程之旋转，扫描

目录 一、旋转&#xff1a;二、扫描&#xff1a; 一、旋转&#xff1a; 案例1&#xff1a;旋转一个球&#xff1a; 任意一个平面绘制草图&#xff1a; 确定草图后&#xff0c;然后退出草图&#xff0c;点击旋转&#xff1a; 案例2&#xff1a;旋转一个杯子雏形&#xff1a; …
阅读更多...
在以TAB为首地址的字存储区中存放有N个无符号数，试统计低3位全为1的数的个数（个数设为≤9），并显示。

在以TAB为首地址的字存储区中存放有N个无符号数，试统计低3位全为1的数的个数（个数设为≤9），并显示。

;默认认采用ML6.11汇编程序 DATAS SEGMENT;此处输入数据段代码TAB DW -7,7,15,20,21N($-TAB)/2;G DW 0 DATAS ENDS STACKS SEGMENT;此处处输入堆栈段代码; DB 200 DUP(0) STACKS ENDS CODES SEGMENTASSUME CS:CODES,DS: DATAS, SS:STACKS START:MOV AX, DATASMOV DS,AX;此处输入…
阅读更多...
swift和OC混编报错问题

swift和OC混编报错问题

1.‘objc’ instance method in extension of subclass of ‘xxx’ requires iOS 13.0.0 需要把实现从扩展移到主类实现。iOS13一下扩展不支持objc 2.using bridging headers with framework targets is unsupported 报错 这个错误通常指的是在一个框架目标中使用桥接头是不…
阅读更多...
01:2440----点灯大师

01:2440----点灯大师

目录 一:点亮一个LED 1:原理图 2:寄存器 3:2440的框架和启动过程 A:框架 B:启动过程 4:代码 5:ARM知识补充 6:c语言和汇编的应用 A:代码 B:分析汇编语言 C:内存空间 7:内部机制 二:点亮2个灯 三:流水灯 四:按键控制LED 1:原理图 2:寄存器配置 3:代码 一:点…
阅读更多...
postgresql|数据库|提升查询性能的物化视图解析

postgresql|数据库|提升查询性能的物化视图解析

前言&#xff1a; 我们一般认为数字的世界是一个虚拟的世界&#xff0c;OK&#xff0c;但我们其实有些需求是和现实世界一模一样的&#xff0c;比如&#xff0c;数据库尤其是关系型数据库&#xff0c;希望在使用的数据库能够更快&#xff08;查询速度&#xff09;&#xff0c;…
阅读更多...
亚马逊云AI应用科技创新下的Amazon SageMaker使用教程

亚马逊云AI应用科技创新下的Amazon SageMaker使用教程

目录 Amazon SageMaker简介 Amazon SageMaker在控制台的使用 模型的各项参数 pytorch训练绘图部分代码 Amazon SageMaker简介 亚马逊SageMaker是一种完全托管的机器学习服务。借助 SageMaker&#xff0c;数据科学家和开发人员可以快速、轻松地构建和训练机器学习模型&#…
阅读更多...
765. 情侣牵手

765. 情侣牵手

765. 情侣牵手&#xff08;leetcode,数学思维题&#xff09;-------------------Java实现 题目表述 n 对情侣坐在连续排列的 2n 个座位上&#xff0c;想要牵到对方的手。 人和座位由一个整数数组 row 表示&#xff0c;其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺…
阅读更多...
头歌答案--爬虫实战

头歌答案--爬虫实战

目录 urllib 爬虫 第1关&#xff1a;urllib基础 任务描述 第2关&#xff1a;urllib进阶 任务描述 requests 爬虫 第1关&#xff1a;requests 基础 任务描述 第2关&#xff1a;requests 进阶 任务描述 网页数据解析 第1关&#xff1a;XPath解析网页 任务描述 第…
阅读更多...
汉明距离(Java)

汉明距离(Java)

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y&#xff0c;计算并返回它们之间的汉明距离。 方法1:使用内置函数 class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);} }方法2:移位实…
阅读更多...
技能培训知识付费服务预约小程序的效果如何

技能培训知识付费服务预约小程序的效果如何

技能、证书往往是很多人生活的基本&#xff0c;行业岗位竞争激烈&#xff0c;每个人都希望有多种技能或工作所需&#xff0c;而需求持续增加下&#xff0c;相关技能培训机构也很多&#xff0c;比如常见的考证、钢琴培训、针灸培训、花艺培训等。 很多行业都需要学习或考证&…
阅读更多...
mac homebrew.mxcl.php@5.6.plist

mac homebrew.mxcl.php@5.6.plist

今天启动php5.6时 遇到了一个问题 servers % brew services start php5.6 Bootstrap failed: 5: Input/output error Try re-running the command as root for richer errors. Error: Failure while executing; /bin/launchctl bootstrap gui/501 /Users/ssh/Library/LaunchAge…
阅读更多...
Spring源码系列-Spring事务

Spring源码系列-Spring事务

目录 声明式事务 事务传播行为 源码解析 开启事务 调用顺序 EnableTransactionManagement注解的两个作用 引入AutoProxyRegistrar后置处理器 引入ProxyTransactionManagerConfiguration配置类 加载切面 事务的Advisor的注册 事务Advice 事务PointCut 创建动态代理…
阅读更多...
编程知识\_C与汇编深入分析

编程知识\_C与汇编深入分析

1. 汇编怎么调用C函数 1.1 直接调用 bl main 1.2 想传参数怎么办&#xff1f; 在arm中有个ATPCS规则(ARM-THUMB procedure call standard&#xff08;ARM-Thumb过程调用标准&#xff09;。 约定r0-r15寄存器的用途&#xff1a; r0-r3 调用者和被调用者之间传参数 r4-r11 函…
阅读更多...
理解王自如，希望成为王自如

理解王自如，希望成为王自如

我是卢松松&#xff0c;点点上面的头像&#xff0c;欢迎关注我哦&#xff01; 昨天看了王自如的采访视频&#xff0c;这两天刷了很多屏。 王自如说&#xff1a;我没看过格力给的工资条。在顶级的企业家身边工作&#xff0c;哪怕每天只是听她讲什么做什么&#xff0c;我都觉得是…
阅读更多...
“富婆”通讯录——让你少奋斗50年

“富婆”通讯录——让你少奋斗50年

文章目录 一、项目需求分析二、通讯录各功能实现思路及代码准备工作2.1、打印一个菜单&#xff0c;提供用户选择功能2.2、添加联系人信息2.3、删除联系人信息2.4、查询联系人信息2.5、修改联系人信息2.6、显示所有联系人信息2.7、对所有联系人信息进行排序整理2.8、删除所有联系…
阅读更多...
最新文章

Copyright @ 2022~2023