【数据结构】顺序表

作者：日出等日落

专栏：数据结构

只有毅力才会使我们成功，而毅力的来源又在于毫不动摇，坚决采取为达到成功所需要的手段。                                                                                                       ——车尔尼雪夫斯基

目录

前言：

参数部分：

 函数功能：

初始化Seqlist:

销毁Seqlist：

打印Seqlist：

扩容Seqlist：

尾插：

尾删：

头插：

头删：

在任意位置上插入：

删除任意位置：

查找任意位置：

完整代码： 

Seqlist.h:

Seqlist.c:

Text.c:

前言：

顺序表：

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

顺序表一般可以分为：

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

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

注：本章讲解动态顺序表

参数部分：

  • 首先是连续存放的数据，我们会想到数组，但是我们的个数不能改变，所以我们需要一个指针a指向malloc开辟一段连续的空间。
  • 然后当我们需要改变这个空间的大小，我们还需要一个变量来表示已有空间容量的大小capacity。
  • 我们如何判断什么时候需要扩容呢？需要一个计算多少个有效数据的个数变量size来判断等于已有空间的大小来决定是否扩容。 

定义结构体 ：

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;   //动态数组
	int size;       // 记录存储多少个有效数据
	int capacity;   // 空间容量大小 
}SL;

在这里我分为了三个部分来实现：

  • SeqList.h文件中进行函数声明。
  • SeqList.c函数进行各个函数的实现。
  • Test.c函数进行函数的测试。 

 函数功能：

初始化Seqlist:

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

销毁Seqlist：

//销毁
void SLDestory(SL* ps)
{
	assert(ps);
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

打印Seqlist：


//打印
void SLPrint(SL* ps)
{
	assert(ps);

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

扩容Seqlist：

SLCheckCapacity(SL* ps)
{
	//扩容
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail :");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

尾插：

//尾插
void SLPushBack(SL* ps,SLDataType x)
{
//扩容
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
	//SLInsert(ps, ps->size,x);
}

尾删：

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
	//SLErase(ps, ps->size - 1);
}

头插：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
	//SLInsert(ps, 0, x);
}

头删：

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 1;
	while (begin<ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
	//SLErase(ps, 0);
}

在任意位置上插入：

//从中间位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (pos <= end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}


删除任意位置：

// 删除pos位置数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	int begin = pos;
	int end = ps->size - 1;
	while (begin <= end)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

查找任意位置：

// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin)
{
	assert(ps);
	for (int i=0 ; i < ps->size; i++)
	{
		if (x == ps->a[i])
		{
			printf("%d\n", i);
			return i;
		}
	}
	return -1;
}

完整代码： 

Seqlist.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


//动态顺序表
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int size;       // 记录存储多少个有效数据
	int capacity;   // 空间容量大小 
}SL;

//初始化
void SLInit(SL* ps);

//尾插尾删
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);

//销毁
void SLDestory(SL* ps);

//初始化
void SLPrint(SL* ps);


//头插头删
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

// 中间插入删除
// 在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 删除pos位置数据
void SLErase(SL* ps, int pos);

//int SLFind(SL* ps, SLDataType x);

// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin);

Seqlist.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"

SLCheckCapacity(SL* ps)
{
	//扩容
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail :");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps,SLDataType x)
{/*
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;*/
	SLInsert(ps, ps->size,x);
}

//打印
void SLPrint(SL* ps)
{
	assert(ps);

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

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

//销毁
void SLDestory(SL* ps)
{
	assert(ps);
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

//尾删
void SLPopBack(SL* ps)
{
	/*assert(ps);
	assert(ps->size > 0);
	ps->size--;*/
	SLErase(ps, ps->size - 1);
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	//SLCheckCapacity(ps);
	挪动数据
	//int end = ps->size - 1;
	//while (end>=0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	end--;
	//}
	//ps->a[0] = x;
	//ps->size++;
	SLInsert(ps, 0, x);
}

void SLPopFront(SL* ps)
{
	//assert(ps);
	//assert(ps->size > 0);
	//int begin = 1;
	//while (begin<ps->size)
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	begin++;
	//}
	//ps->size--;
	SLErase(ps, 0);
}

//从中间位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (pos <= end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

// 删除pos位置数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	int begin = pos;
	int end = ps->size - 1;
	while (begin <= end)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin)
{
	assert(ps);
	for (int i=0 ; i < ps->size; i++)
	{
		if (x == ps->a[i])
		{
			printf("%d\n", i);
			return i;
		}
	}
	return -1;
}

Text.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"

TextSeqList1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);


	SLDestory(&sl);
}

TextSeqList2()
{
	SL sl;
	SLInit(&sl);
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
	SLPushFront(&sl, 5);
	SLPushFront(&sl, 6);
	SLPushFront(&sl, 7);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLDestory(&sl);

}

TextSeqList3()
{
	SL sl;
	SLInit(&sl);
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
	SLPushFront(&sl, 5);
	SLPrint(&sl);
	SLInsert(&sl, 3, 100);
	SLPrint(&sl);
	

	
	 SLFind(&sl, 100, 0);
	/*if (pos != -1)
	{
		SLErase(&sl, pos);
	}*/
	 SLErase(&sl,2);
	 SLPrint(&sl);
	SLDestory(&sl);

}
int main()
{
	TextSeqList3();
	return 0;
}

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

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

相关文章

Ceph部署

Ceph部署

1. 简介 Ceph是一个高性能、可扩容的分布式存储系统&#xff0c;它提供三大功能&#xff1a; 对象存储&#xff1a;提供RESTful接口&#xff0c;也提供多种编程语言绑定。兼容S3、Swift块存储&#xff1a;由RBD提供&#xff0c;可以直接作为磁盘挂载&#xff0c;内置了容灾机…
阅读更多...
代码规范（以后会补充）

代码规范（以后会补充）

目录 为什么要规范代码 不规范的代码有什么特点 ​编辑 不规范的坏处 规范代码是什么样的 如何规范代码 1.代码中不要出现莫名其妙的数字 2.深度嵌套 3.注释 4.避免创建大函数 5.重复代码 6.变量命名 7.函数命名 8.命名时注意动词的使用 9. 常量值所有都大写 10. 避免变…
阅读更多...
PMP备考资料：如何掌握PMP应考中的计算题？

PMP备考资料：如何掌握PMP应考中的计算题？

计算题总体来说考得非常简单&#xff0c;题量也少&#xff0c;有时候只考3道、4道简单计算。所以这部分内容大家要细心严谨&#xff0c;不要因为粗心而丢掉分数。 01三点估算 通过考虑估算中的不确定性和风险&#xff0c;可以提高活动持续时间估算的准确性。这个概念源自计划…
阅读更多...
映射的概念以及用法

映射的概念以及用法

映射的概念以及用法前言映射的定义映射的应用前言 在数学里&#xff0c;映射是个术语&#xff0c;指两个元素的集之间元素相互 “对应”的关系&#xff0c;为名词。映射&#xff0c;或者射影&#xff0c;在数学及相关的领域经常等同于函数&#xff0c;函数是从非空数集到非空数…
阅读更多...
PyCharm解决Git冲突

PyCharm解决Git冲突

技术背景 在前面的一篇博客中&#xff0c;我们介绍了Fork到自己名下的本地仓库如何与远程原始仓库创建链接的方法。在这篇文章中&#xff0c;我们将要讲解如何应对在这种异步开发的过程中经常有可能会遇到的Git冲突问题&#xff0c;在Pycharm这个专业的Python开发工具中集成了一…
阅读更多...
网络基础概念

网络基础概念

本文目标&#xff1a; ①了解网络发展背景, 对局域网/广域网的概念有基本认识; ②了解网络协议的意义, 重点理解TCP/IP五层结构模型; ③学习网络传输的基本流程, 理解封装和分用; 1.计算机网络背景 OS与网络 在整个计算机体系中&#xff0c;是先由操作系统&#xff0c;再有网…
阅读更多...
Windows下使用SSH密钥实现免密登陆Linux服务器

Windows下使用SSH密钥实现免密登陆Linux服务器

工具&#xff1a; win10、WinSCP 生成ssh密钥&#xff1a; 打开终端&#xff0c;使账号密码登录&#xff0c;输入命令 ssh-keygen -t rsa 会提示密钥存放路径&#xff0c;一般存放在默认路径&#xff0c;直接回车即可&#xff0c;中间会提示输入密码&#xff0c;这里需要注…
阅读更多...
CC攻击原理以及如何防御策略

CC攻击原理以及如何防御策略

CC攻击原理以及如何防御策略 CC 攻击是一种 DDoS&#xff08;分布式拒绝服务&#xff09;&#xff0c;它似乎比其他 DDoS 攻击更具技术性。在这种攻击中&#xff0c;看不到假IP&#xff0c;看不到特别大的异常流量&#xff0c;但会导致服务器无法正常连接。 很多创业公司辛辛苦…
阅读更多...
你是真的“C”——C语言测评总结

你是真的“C”——C语言测评总结

你是真的“C”——C语言测评总结&#x1f60e;前言&#x1f64c;BC146 添加逗号总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右铭&#xff1a;全神贯注的上吧&#xff01;&#xff01;&#xff01; &#x1f60a;作者简介&#xf…
阅读更多...
TreEnhance: A Tree Search Method For Low-Light Image Enhancement 论文阅读笔记

TreEnhance: A Tree Search Method For Low-Light Image Enhancement 论文阅读笔记

这是2023年PR这个期刊的论文主要思想是&#xff0c;利用一系列预定义好的操作序列来进行增强&#xff0c;然后利用强化学习来学习增强序列的预测。所以训练阶段有两个交替进行的阶段&#xff0c;一个是蒙特卡洛树搜索阶段&#xff0c;第二个是训练深度强化学习的阶段。而测试的…
阅读更多...
中级软件设计师备考---计算机组成与体系结构3

中级软件设计师备考---计算机组成与体系结构3

目录①磁盘工作原理②计算机总线③系统可靠性分析④校验码CRC循环校验码海明校验码①磁盘工作原理 计算题 ②计算机总线 概念题 ③系统可靠性分析 计算可靠度 ④校验码 码距&#xff1a;是指两个码字之间的不同位数。例如&#xff0c;1010和1111之间的码距是2&#xff0c…
阅读更多...
160. 相交链表 ——【Leetcode每日一题】

160. 相交链表 ——【Leetcode每日一题】

160. 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c…
阅读更多...
生成式人工智能所面临的问题有哪些？

生成式人工智能所面临的问题有哪些？

在生成式人工智能中工作需要混合技术、创造性和协作技能。通过发展这些技能&#xff0c;您将能够在这个令人兴奋且快速发展的领域应对具有挑战性的问题。 生成式人工智能是指一类机器学习技术&#xff0c;旨在生成与训练数据相似但不完全相同的新数据。 换句话说&#xff0c;…
阅读更多...
【二分—STL】lower_bound()函数upper_bound()函数的使用总结

【二分—STL】lower_bound()函数upper_bound()函数的使用总结

目录一、基本用法&#xff1a;二、具体到题目中如何应用1、数的范围2、递增三元组3、数组元素的目标和一、基本用法&#xff1a; lower_bound() 用于二分查找区间内第一个 大于等于某值(> x) 的迭代器位置 upper_bound() 用于二分查找区间内第一个 大于某值(> x) 的迭代器…
阅读更多...
IP协议以及相关技术

IP协议以及相关技术

这里写目录标题前言正文IP基本认识IP的作用IP和MAC的关系IP地址的基础知识IP地址定义IP地址分类(IPv4)无分类IP地址CIDR子网掩码IPv6基础知识相关技术DNS域名解析ARPDHCPNATICMPIGMP总结参考连接前言 大家好&#xff0c;我是练习两年半的Java练习生&#xff0c;今天我们来讲一…
阅读更多...
Meta AI Segment Anything Model (SAM)初体验

Meta AI Segment Anything Model (SAM)初体验

最近Meta AI发布了Segment Anything模型&#xff0c;可以直接分割任何图片。我趁热乎体验了一下。 文章目录进入官网 & 上传图片Hover & Click——截取物体Box——框选物体Everything——提取所有物体Cut-Outs——提取结果进入官网 & 上传图片 打开Segment Anythi…
阅读更多...
JMP指令寻址方式总结，JMP BX指令寻址方式是什么

JMP指令寻址方式总结，JMP BX指令寻址方式是什么

jmp 指令的几种寻址方式 jmp short 标号 段间跳转 -128-127 jmp far ptr 标号 超段转移 跳转包含目标地址jmp reg 16位寄存器 jmp word ptr 内存单元地址 段内转移 jmp dword ptr 内存单元地址 ( 段间转移) 高字地址存放cs 低字节存放ip jmp指令用法总结 1.直接用法(只能在Deb…
阅读更多...
hadoop3.2.4 集群环境搭建

hadoop3.2.4 集群环境搭建

本文介绍hadoop3.2.4集群环境搭建看本文之前最好先看看伪分布式的 搭建文章链接如下&#xff0c;因为有些问题是伪分布式的时候遇到的&#xff0c;这里就不重复展示解决办法了。 链接&#xff1a;伪分布式搭建 文章目录前言一、准备机器二、linux环境准备工作2.1 修改主机名2.2…
阅读更多...
超详细从入门到精通，pytest自动化测试框架实战-钩子函数（五）

超详细从入门到精通，pytest自动化测试框架实战-钩子函数（五）

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 pytest这个框架提供…
阅读更多...
政务云建设与应用解决方案

政务云建设与应用解决方案

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用&#xff0c;如有侵权请联系删除 政府信息化趋势-四大四新-政务云需求 大平台共享-新设施&#xff1a;打造形成“覆盖全市、统筹利用、统一投入”的大平台&#xff0c;有力促进政务信息系统整合&#xff1b; 大…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站