C语言——顺序表

文章目录

  • 一、线性表
  • 二、顺序表
    • 顺序表和数组的区别
    • 顺序表的分类
    • 1.静态顺序表
    • 2.动态顺序表
  • 三、动态顺序表的实现
    • 1.动态顺序表头文件
    • 2.动态顺序表源文件
    • 3.测试源文件

一、线性表


线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使
⽤的数据结构,常⻅的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的
线性表在物理上存储时,通常以数组和链式结构的形式存储

二、顺序表

顺序表和数组的区别

顺序表的底层结构是数组,对数组的封装,实现了常⽤的增删改查等接口

顺序表的分类

1.静态顺序表

概念:使⽤ 定⻓数组 存储元素

在这里插入图片描述

在这里插入图片描述

静态顺序表缺陷:空间给少了不够⽤,给多了造成空间浪费

2.动态顺序表

动态顺序表就是动态分配内存,可以根据需求调节数组大小

在这里插入图片描述
在这里插入图片描述

三、动态顺序表的实现

实现的主要思想:
1.初始化顺序表:先初始化arr为NULL,size为0,capacity为0
2.销毁顺序表:顺序表使用完成之后,把arr动态分配的内存释放掉
3.扩容顺序表:在每次插入数据之前必须先检查是否空间充足,不足则开辟更大的空间
4.增删查改顺序表:围绕数组去做即可,比较简单。增:头插,尾插,指定位置插入;删:包括头删,尾删,指定位置删除;查找数据。

1.动态顺序表头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 动态顺序表
//  按需申请
typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

void SLInit(SL* ps);//顺序表的初始化
void SLDestroy(SL* ps);//顺序表的销毁
void SLPrint(SL* ps);//顺序表的打印

void SLCheckCapacity(SL* ps);//扩容

//头部插入删除 / 尾部插入删除
void SLPushFront(SL* ps, SLDateType x);
void SLPushBack(SL* ps, SLDateType x);

void SLPopFront(SL* ps);
void SLPopBack(SL* ps);


//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDateType x);
void SLErase(SL* ps, int pos);

//查找数据
int SLFind(SL* ps, SLDateType x);

2.动态顺序表源文件

#include "Seqlist.h"
//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps-> size = 0;
	ps->capacity = 0;
}
//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

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

//扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//申请空间
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDateType* tmp = (SLDateType*)realloc(ps->arr, NewCapacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序
		}
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
}

//头部插入
void SLPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size-1;i >= 0;i--)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[0] = x;
	ps->size++;
}

//尾部插入
void SLPushBack(SL* ps, SLDateType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

//头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0;i < ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size-1;i >= pos;i--)
	{
		ps->arr[i+1] = ps->arr[i];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//指定位置之前删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos;i < ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//查找数据
int SLFind(SL* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

3.测试源文件

最后可以在创建一个测试源文件去测试顺序表的正确性

#include "Seqlist.h"

void test()
{
	SL s1;
	//测试初始化
	SLInit(&s1);
	//测试尾部插入
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushBack(&s1, 5);
	//测试打印
	SLPrint(&s1);

	//测试头部插入
	/*SLPushFront(&s1, 9);
	SLPushFront(&s1, 8);
	SLPushFront(&s1, 7);
	SLPushFront(&s1, 6);
	SLPushFront(&s1, 66);*/

	//测试头删
	/*SLPopFront(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);*/

	//测试尾删
	/*SLPopBack(&s1);
	SLPrint(&s1);
	SLPopBack(&s1);
	SLPrint(&s1);
	SLPopBack(&s1);
	SLPrint(&s1);
	SLPopBack(&s1);
	SLPrint(&s1);
	SLPopBack(&s1);
	SLPrint(&s1);
	SLPopBack(&s1);
	SLPrint(&s1);*/

	//测试在指定位置之前插入数据
	/*SLInsert(&s1, 3, 8);
	SLPrint(&s1);*/

	//测试在指定位置之前删除数据
	/*SLErase(&s1, 1);
	SLPrint(&s1);*/

	//测试查找
	int find = SLFind(&s1, 3);
	if (find != -1)
	{
		printf("找到了!下标为%d\n", find);
	}
	else
	{
		printf("没有找到\n");
	}

	//测试销毁
	SLDestroy(&s1);
}


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

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

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

相关文章

LeetCode-33. 搜索旋转排序数组【数组 二分查找】

LeetCode-33. 搜索旋转排序数组【数组 二分查找】 题目描述&#xff1a;解题思路一&#xff1a;二分查找。1.找哨兵节点&#xff08;nums[0]或nums[-1]&#xff09;可以确定nums[mid]位于前一段或后一段有序数组中。2. 就是边界left和right的变换&#xff0c;具体看代码。解题思…

阿里面试总结

ThreadLocal 线程变量存放在当前线程变量中&#xff0c;线程上下文中&#xff0c;set将变量添加到threadLocals变量中 Thread类中定义了两个ThreadLocalMap类型变量threadLocals、inheritableThreadLocals用来存储当前操作的ThreadLocal的引用及变量对象&#xff0c;把当前线程…

MySQL数据库版本为5.5.62,时间戳超出2038年1月19日的解决方案

MySQL数据库版本是 5.5.62&#xff0c;已设置字段的类型为BIGINT&#xff0c;使用FROM_UNIXTIME()函数来转换时间戳&#xff0c;返回NULL。 SELECT FROM_UNIXTIME(1617970800)SELECT FROM_UNIXTIME(2185743121)MySQL数据库版本为5.5.62&#xff0c;已设置字段的类型为BIGINT&a…

golang web 开发 —— gin 框架 (gorm 链接 mysql)

目录 1. 介绍 2. 环境 3. gin 3.1 gin提供的常见路由 3.2 gin的分组 main.go router.go 代码结构 3.3 gin 提供的Json方法 main.go route.go common.go user.go order.go 3.4 gin框架下如何获取传递来的参数 第一种是GET请求后面直接 /拼上传递的参数 第二种是…

Rust语言入门第一篇-环境搭建

Rust语言入门第一篇 Rust官网 一&#xff0c;环境搭建 1、C开发环境配置 Rust 语言的底层是依赖于 C/C 编译器的。在安装 Rust 编译器时&#xff0c;通常会自动安装所需的 C/C 编译环境&#xff0c;以便 Rust 能够生成可执行文件或库。因此&#xff0c;在安装 Rust 之前&…

用Vue全家桶手工搓了一个类似抖音短视频的软件,全开源

用Vue全家桶手工搓了一个类似抖音短视频的软件&#xff0c;全开源 软件简介 用Vue全家桶手工搓了一个高仿抖音&#xff0c;全开源 PC浏览器请用手机模式访问。先按F12调出控制台&#xff0c;再按CtrlShiftM切换到手机模式&#xff0c;手机请用Via浏览器或者Chrome浏览器预览。…

Vue的学习之旅-part4

Vue的学习之旅-part1 vue的自带指令v-if v-else-if v-else虚拟DOM的复用v-show 与 v-if 的不同之处&#xff1a;v-if v-show各自合适的使用位置&#xff1a; v-for 循环v-for 循环遍历 :key"item" 绑定key&#xff0c;区分循环的内容循环的应用&#xff1a; 前几篇博…

目标检测——色素性皮肤病数据集

一、重要性及意义 首先&#xff0c;色素性皮肤病变是一类常见的皮肤疾病&#xff0c;其发病率有逐年增高的趋势。这些病变可能由遗传或环境因素导致黑素细胞生成异常&#xff0c;如黑色素瘤等。黑色素瘤具有极高的恶性率和致死率&#xff0c;而且恶化可能性大&#xff0c;容易…

汇编——SSE打包整数

SSE也可以进行整数向量的加法&#xff0c;示例如下&#xff1a; ;sse_integer.asm extern printfsection .datadummy db 13 align 16pdivector1 dd 1dd 2dd 3dd 4pdivector2 dd 5dd 6dd 7dd 8fmt1 db "Packed Integer Vector 1: %d, %d, %d, %d",…

鸿蒙ArkTS开始实例:【canvas实现签名板功能】

使用ArkTS中的canvas实现签名板的功能&#xff0c;canvas画布大家都很熟悉&#xff0c;我们会用它经常实现一些画板或者图表、表格之类的功能。canvas签名板是我在开发APP过程中实现的一个功能&#xff0c;开发过程中也是遇到比较多的问题。我会按照以下几点来讲解开发整个过程…

面试算法-153-旋转图像

题目 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,…

计算机网络实验——学习记录四(TCP协议)

1. 打开TCP服务&#xff1a; nc -e /bin/sh -lv 4499 注释&#xff1a; &#xff08;1&#xff09;nc是Linux下启动通讯服务的命令&#xff1b; &#xff08;2&#xff09;-e表示在nc命令后再执行bin文件夹下的shell命令&#xff0c;启动shell命令会导致所有从TCP连接传递到…

JavaEE初阶——多线程(一)

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享多线程的第一部分:引入线程以及创建多线程的几种方式 此文章是建立在前一篇文章进程的基础上的 如果有不足的或者错误的请您指出! 1.认识线程 我们知道现代的cpu大多都是多核心…

【蓝桥杯嵌入式】第十三届省赛(第二场)

目录 0 前言 1 展示 1.1 源码 1.2 演示视频 1.3 题目展示 2 CubeMX配置(第十三届省赛第二场真题) 2.1 设置下载线 2.2 HSE时钟设置 2.3 时钟树配置 2.4 生成代码设置 2.5 USART1 2.5.1 基本配置 2.5.2 NVIC 2.5.3 DMA 2.6 TIM 2.6.1 TIM2 2.6.2 TIM4 2.6.3 …

ICP配准算法

配准算法 问题定义ICP(point to point)算法思想步骤分解point to point和point to plane的区别ICP配准算法的标准流程NDT 本篇将介绍配准算法&#xff0c;将介绍ICP(point to point)、ICP(point to plane)和NDT算法。其中ICP有两种&#xff0c;point to point表示通过构建点与点…

达梦备份与恢复

达梦备份与恢复 基础环境 操作系统&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本&#xff1a;DM Database Server 64 V8 架构&#xff1a;单实例1 设置bak_path路径 --创建备份文件存放目录 su - dmdba mkdir -p /dm8/backup--修改dm.ini 文件…

NzN的数据结构--二叉树part1

你叉叉&#xff0c;让你学数据结构你不学&#xff1b;你叉叉&#xff0c;让你看二叉树你不看。 今天我们来一起学习二叉树部分&#xff0c;先赞后看是好习惯。 一、树的概念及结构 1. 树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有…

阿里云服务器可以干什么?阿里云服务器主要用途是干嘛的?

阿里云服务器可以干嘛&#xff1f;能干啥你还不知道么&#xff01;简单来讲可用来搭建网站、个人博客、企业官网、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云百科aliyunbaike.com整理阿里云服务器的用途&#xff1a; 阿里云服务器活动 aliyunbaike.com…

SpringCloud Alibaba Sentinel 规则持久化

一、前言 接下来是开展一系列的 SpringCloud 的学习之旅&#xff0c;从传统的模块之间调用&#xff0c;一步步的升级为 SpringCloud 模块之间的调用&#xff0c;此篇文章为第十七篇&#xff0c;即使用 Sentinel 实现规则持久化。 二、概述 从前面我们做的实验可知&#xff0c;…

4/7 QT_day1

#include "mainwindow.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent) {//窗口设置this->setWindowTitle("小黑子(little black son)");this->setWindowIcon(QIcon("D:\\qq文件\\Pitrue\\pictrue\\black.jpg"));this-&g…