数据结构-顺序表

news/2024/7/16 7:30:56 标签: c语言, 算法, vscode, ide

数据结构-顺序表

  • 线性表
  • 顺序表的概念和结构
    • 静态顺序表和动态顺序表
  • 接口的实现
    • 顺序表的初始化
    • 顺序表的打印
    • 顺序表的销毁
    • 顺序表的增容
    • 顺序表的尾插
    • 顺序表的尾删
    • 顺序表的头插
    • 顺序表的头删
    • 顺序表的任意位置插入
    • 顺序表的任意位置删除
    • 顺序表中元素的查找
  • 完整代码

线性表

线性表是n个具有相同特性的数据元素的有限序列。它是一种数据结构。常见的线性表有：顺序表，链表，栈，队列，字符串等。线性表在逻辑上是线性结构，也就是说，从逻辑的角度来看，它是连续的一条直线。但是在物理结构上不一定是连续的，通常以数组和链式结构的形式存储。这里我们主要了解顺序表。

顺序表的概念和结构

顺序表是用一段物理地址连续的存储单元依次存储元素的线性结构。一般情况下采用数组的形式进行存储。在数组上完成数组的增删查改。
在这里插入图片描述

顺序表一般可以分为静态顺序表和动态顺序表。

静态顺序表和动态顺序表

静态顺序表的数组长度是固定的。如下：

#define N 10000
typedef int SLDataType;
struct SeqList
{
	SLDataType a[N];
	int size;
};

这里#define 对数组的长度10000用N来替换；typedef对int数据类型重新定义为一个新的名字SLDataType；SeqList就是我们的顺序表，它包括数组和当前的数据表的长度size。

由于静态顺序表的数组大小是固定的，当数组大小不大时，数据增加，可能存放不下；当数组大小大的时候，又会造成空间的浪费。因此，静态顺序表不常用。常用动态顺序表，如下：

//动态
typedef int SLDataType;
#define INIT_CAPACITY 4


typedef struct SeqList
{
	SLDataType* a;
	int size;//当前数据的个数
	int capacity;//容量
}SL;

这里typedef对int数据类型重新定义为一个新的名字SLDataType；SeqList就是我们的顺序表，它包括SLDataType* a指针和当前的数据的个数size，顺序表的容量capacity；对顺序表struct SeqList数据类型重新定义为一个新的名字SL。

接口的实现

顺序表的初始化

初始化：malloc函数申请空间为数组所占用的空间，size置零，给定初始容量为4
这里我们采用指针进行函数传参。

#define INIT_CAPACITY 4

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

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

顺序表的打印

顺序表的打印就是打印出数组中的元素

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

顺序表的销毁

动态空间释放，指针置NULL；变量归0

void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

顺序表的增容

当元素个数size大于等于顺序表中的capacity时，就需要增容。
我们使用realloc函数对其增容，增容后，指针需要重新赋值，capacity变量值需要改变。

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

		ps->a = temp;
		ps->capacity *= 2;
	}
}

顺序表的尾插

尾插比较简单，只需要size++后，给数组赋值即可。

void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->capacity==ps->size)
	{
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType*) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = temp;
		ps->capacity *= 2;
	}//这里也可以直接调用SLCheckCapacity函数
	ps->a[ps->size++] = x;
}

顺序表的尾删

这里只需要size–动作，不需要去计较最后一个元素是否已从内存中清空；但是需要检查size，即顺序表中要存在数据。

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

顺序表的头插

在顺序表的头部插入数据，就是意为着所有的元素都要后移1位。如果从前面的元素开始移动数据，则会覆盖掉后面的元素。因此，我们从最后一个元素向后移动数据，一直到指针end指向0。动画如下：
在这里插入图片描述

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	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);
}

顺序表的头删

在顺序表的头部删除数据，只需要将后面的元素逐步覆盖掉前一个元素，指针从1开始，到size-1结束。动画如下：
在这里插入图片描述

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);
}

顺序表的任意位置插入

和头插的思想一样，在被插入的位置和以后的位置的元素都要后移1位，仍然是从最后一个元素后移，指针由size-1变化到pos。动画如下：
在这里插入图片描述

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos>=0&&pos<=ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

因为是任意位置的插入，因此，对于头插和尾插都可以用SLInsert函数实现，如下：

SLInsert(ps,ps->size,x);//尾插
SLInsert(ps, 0, x);//头插

顺序表的任意位置删除

与头删的思想一样，只需要将被删除位置后面的元素依次覆盖掉前面的元素。动画如下：
在这里插入图片描述

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

因为是任意位置的删除，所以头删和尾删也可以用SLErase函数表示，如下：

SLErase(ps,ps->size-1);//尾删
SLErase(ps, 0);//头删

顺序表中元素的查找

这里采用遍历的方法来查找元素，如下：

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

	return -1;
}

完整代码

主程序：

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void TestSeList1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 4);
	SLPushBack(&s, 6);
	SLPushBack(&s, 8);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);

	SLPushFront(&s, -1);
	SLPushFront(&s, -2);
	SLPushFront(&s, -3);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);

	SLInsert(&s, 1, 11);
	SLInsert(&s, 2, 12);
	SLErase(&s, 2);
	SLErase(&s, 1);

	SLPushBack(&s, 100);
	SLPushFront(&s, -100);
	SLPopBack(&s);
	SLPopFront(&s);

	int ret=SLFind(&s,1);
	printf("%d\n",ret);


	SLPrint(&s);
	SLDestroy(&s);

}
int main()
{
	TestSeList1();

	return 0;
}

函数的定义

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void SLInit(SL* ps)
{
	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)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

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

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

		ps->a = temp;
		ps->capacity *= 2;
	}
}


void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->capacity==ps->size)
	{
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType*) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = temp;
		ps->capacity *= 2;
	}
	ps->a[ps->size++] = x;


	//SLInsert(ps,ps->size,x);
}

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


	//SLErase(ps,ps->size-1);
}


void SLPushFront(SL* ps, SLDataType x)
{
	//assert(ps);
	//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&&pos<=ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

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

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

	return -1;
}

函数的声明

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//静态
//#define N 10000
//typedef int SLDataType;
//struct SeqList
//{
//	SLDataType a[N];
//	int size;
//};

//动态
typedef int SLDataType;
#define INIT_CAPACITY 4


typedef struct SeqList
{
	SLDataType* a;
	int size;//当前数据的个数
	int capacity;//容量
}SL;

void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);


void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPopBack(SL* ps);//尾删
void SLPushFront(SL* ps,SLDataType x);//头插
void SLPopFront(SL* ps);//头删
void SLInsert(SL* ps,int pos,SLDataType x);//任意位置的插入
void SLErase(SL* ps,int pos);//任意位置的删除
int SLFind(SL* ps, SLDataType x);//查找元素

http://www.niftyadmin.cn/n/366297.html

相关文章

引用 随笔

引用 随笔

本质 引用的本质其实就是指针常量 *const p 引用的底层机制实际上是和指针一样的。不要相信有别名&#xff0c;不要认为引用可以节省一个指针的空间&#xff0c;因为这一切不会发生&#xff0c;编译器还是会把引用解释为指针。 引用和指针本质上没有区别。 举例&#xff1a…
阅读更多...
【硬件】嵌入式电子设计基础之数字电路

【硬件】嵌入式电子设计基础之数字电路

数字电路与模拟电路的设计思想和应用方法有许多不同之处。 计算器是一个典型的由数字电路实现的电子设备&#xff0c;用户通过数字或符号摁键输入运算式&#xff0c;计算器经过运算之后把结果显示在屏幕上。现代数学电子学始于1946年&#xff0c;其标志是一台以电子管为核心器件…
阅读更多...
集成学习以及随机森林介绍

集成学习以及随机森林介绍

一、集成学习简介 1.什么是集成学习&#xff1f; 集成学习&#xff08;Ensemble Learning&#xff09;是一种机器学习方法&#xff0c;通过将多个弱学习器&#xff08;weak learner&#xff09;组合在一起来构建一个更强大的学习器&#xff08;strong learner&#xff09;。 …
阅读更多...
聚类算法学习笔记（一）

聚类算法学习笔记（一）

聚类算法学习笔记&#xff08;一&#xff09; 方法Euclidean Cluster [ 1 ] ^{[1]} [1]SuperVoxel [ 1 ] ^{[1]} [1]Depth Cluster [ 1 ] ^{[1]} [1]SLR: Scan-line Run [ 1 ] ^{[1]} [1]Range Image-based [ 2 ] ^{[2]} [2] 实验对比其他概念PQCluster ToleranceKD-Tree Refer…
阅读更多...
recurdyn一般接触特征参数含义

recurdyn一般接触特征参数含义

一般接触特征设置 Static Threshold Velocity静态门槛速度&#xff1a;判断静态摩擦和动态摩擦的标准&#xff0c;若相对速度小于此值&#xff0c;摩擦为静摩擦&#xff1b;若相对速度大于此值&#xff0c;摩擦为动摩擦。静态摩擦区域内摩擦系数计算函数为 Dynamic Threshold V…
阅读更多...
SpringBoot 上传图片-指定目录按照日期存储

SpringBoot 上传图片-指定目录按照日期存储

SpringBoot 上传图片-指定目录按照日期存储 1. 在配置文件中指定文件保存根目录 我用的yaml,用properties也行 file-save-path: D:/upload/2. 文件上传接口 package com.admin.controller.wechat;import cn.hutool.core.lang.UUID; import com.redic.base.Result; import com…
阅读更多...
COLMAP中将旋转矩阵转为四元数的实现

COLMAP中将旋转矩阵转为四元数的实现

instant-ngp中执行scripts/colmap2nerf.py时&#xff0c;在colmap_text目录下会生成cameras.txt、images.txt、points3D.txt三个文件: 1.cameras.txt&#xff1a; (1).该文件包含数据集中所有重构相机(all reconstructed cameras)的内在参数(intrinsic parameters)&#xff0c;…
阅读更多...
Qt, Text Edit 和 Plain Text Edit关于调整字体样式的问题

Qt, Text Edit 和 Plain Text Edit关于调整字体样式的问题

问题: 在编写小案例的过程中需要使用一个文本容器用于显示文本效果, 因为涉及文本字体的 加粗, 倾斜, 下划线, 以及颜色效果, 这里使用了 Text Edit 组件, 但是使用后发现容器中的文本无法实现同时设置 加粗 倾斜 下划线的情况, 且单独设置时只有 下划线 有效果, 加粗 倾斜 均无…
阅读更多...
最新文章

Copyright @ 2022~2023