数据结构——线性表

目录

1.线性表的定义

2.顺序表

2.1顺序表的定义

 2.2 顺序表的应用

2.2.1 顺序表的管理

（1） 顺序表的初始化

（2） 销毁顺序表

（3） 打印顺序表的值

（4）检查顺序表的容量

（5）尾插法

（6） 尾删法

（7） 头插法

（8） 头删法

（9） 测试

2.2.2 顺序表指定位置的插入和删除

（1）在pos位置插入x

（2） 删除pos位置的值

2.2.3 OJ练习题  

（1）27. 移除元素 - 力扣（LeetCode）

（2）88. 合并两个有序数组 - 力扣（LeetCode）

1.线性表的定义

        线性表（linear list）是n个具有相同特性的数据元素的有限序列。

         线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串。线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1顺序表的定义

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

顺序表一般可以分为：

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

顺序表采用数组储存，那我们定义的时候就需要定义一个数组，我们采用结构体储存这个结构。静态顺序表的大小是确定的，我们用一个常量N表示。下面给出代码：

 //静态顺序表
#define N 1000
typedef int SLDataType;

struct SeqList
{
	SLDataType a[N];
	int size;//有效数据的个数
};

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

动态顺序表我们使用一个指针，指针指向数组，在使用的时候使用动态内存函数，动态开辟内存空间。下面给出代码：

// 动态顺序表
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;   //指针指向空间
	int size;        // 存储有效数据个数
	int capacity;    // 空间大小
}SL;
 2.2 顺序表的应用

        实际应用中，由于静态顺序表的大小很难确定，小了不够用，大了浪费空间，所以我们大多时候采用动态顺序表，那么接下来我们就基于动态顺序表进行定义。

2.2.1 顺序表的管理

        我们给出一些顺序表的基本操作，增加数据，删除数据，改变数据，查看数据。

// 管理数据 -- 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);
（1） 顺序表的初始化

        我们在使用顺序表时候，首先要对顺序表进行初始化。此时我们传入的参数是结构体指针而不是结构体，是为了改变实参。我们为数组a动态开辟了4个SLDataType大小的空间，动态内存开辟不要忘记对开辟的空间进行检查。然后我们初始化此时的空间大小为4，数据使用的空间为0。代码如下：

//初始化顺序表 注意要传指针才能改变实参
void SLInit(SL* ps)
{
	//动态开辟内存
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc failed");
		exit(-1);//程序报错 直接退出
		//return;区分于return返回值
	}

	ps->size = 0;
	ps->capacity = 4;
}
（2） 销毁顺序表

        我们是动态开辟的空间，使用完了之后要对顺序表进行销毁。先释放空间，后别忘了对指针置空，防止野指针！代码如下：

//销毁顺序表
void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
（3） 打印顺序表的值

        我们需要一个函数打印出此时顺序表里面的值，size是数组里的有效数据大小，所以我们只需要打印到size。代码如下：

//打印顺序表的值
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
（4）检查顺序表的容量

        我们初始化内存大小是4，如果我们此时要存8个数据，就会发生越界。所以我们定义一个函数检查此时顺序表的容量。我们分配的大小为现在大小的两倍，记得检查空间是否成功开辟，此时顺序表的容量就变为原来的两倍。在这里有个细节：我们用的是realloc，它生成的空间有两种不同的方法，忘记的大家可以看一下之前C语言进阶部分内存函数的知识。所以我们一开始把生成的空间用临时变量储存，最后在把临时变量赋给a。防止开辟失败导致内存泄漏。代码如下：

//检查顺序表的容量
void SLCheckCapacity(SL* ps)
{
	// 满了要扩容
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}
}
（5）尾插法

        我们先来了解什么是尾插法，尾插法就是把数据每次都插入顺序表最末尾的位置。那我们在插入前要先检查空间是否够用，然后只需要将数据放入有效数据末尾，增加有效数据长度即可。

// 尾插法
void SLPushBack(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}
（6） 尾删法

        尾删法，从尾部一个一个删除数据，但这里我们需要检查有效数据的大小，如果它此时为0，那我们直接执行删除，下一次使用就会导致数组越界。所以我们需要进行一个断言。

//尾删法
void SLPopBack(SL* ps)
{
	assert(ps->size > 0);

	//ps->a[ps->size - 1] = 0;
	ps->size--;
}
（7） 头插法

        头插法就是从数组的前面插入值，我们先来看一下实现方法：

   

 

        我们用这种方法把值往后移动一位，要从后往前覆盖，不能从前往后，防止丢失值。空出开头位给插入数据，大家看懂的话可以尝试自己写一下代码，想一想循环的终止条件。

//头插法：从后往前覆盖值
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++;
}
（8） 头删法

        头删法的思想和头插法类似，我们定义一个begin指针，只需要将后面的值往前覆盖，覆盖到最前面的值就好，还是注意循环的终止条件。

//头删法：从后往前覆盖
void SLPopFront(SL* ps)
{
	//注意检查size大小
	assert(ps->size > 0);

	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}
（9） 测试
#include<stdio.h>

#include"SeqList.h"


void TestSeqList1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 0);
	SLPushBack(&sl, 0);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	/*SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);*/
	SLPrint(&sl);

	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPrint(&sl);

	SLDestroy(&sl);
}

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

大家可以根据自己理解想一想测试函数输出的值是多少？看是否充分了解尾插数据插入位置。

void TestSeqList2()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLPushFront(&sl, 10);
	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPrint(&sl);
}

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

大家可以根据自己理解想一想测试函数输出的值是多少？看是否充分了解头插数据插入位置。 

2.2.2 顺序表指定位置的插入和删除
（1）在pos位置插入x

        在pos位置处插入值x的思路有一些像头插，不过头插是第一个位置，那pos位置插入改变一下循环条件就可以解决，问题是要对pos位置进行限制，pos不能小于0，pos也不能大于size。

// 在pos位置插入x
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++;
}
（2） 删除pos位置的值

        删除pos位置的值，通过一个begin指针，实现从pos位置后面的值对前面的值进行覆盖。相当于头删的时候，pos值为0。代码实现原理如下：

// 删除pos位置的值
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--;
}
2.2.3 OJ练习题  
（1）27. 移除元素 - 力扣（LeetCode）

考虑到空间复杂度，这道题我们的思路是用两个指针对数组进行判断。一个src指针，一个dst指针，我们对src指向的值进行判断，若src指向的值不等于val，那我们就把值赋给dst，再把src++和dst++，最后返回数组的长度就是dst。我们来看一下演示步骤：

int removeElement(int* nums, int numsSize, int val) {
    int dst=0;
    int src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[dst++]=nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst;
}
（2）88. 合并两个有序数组 - 力扣（LeetCode）

我们先来了解什么是非递减序列：1 2 2 5 6这种序列就是非递减序列，递增序列：1 2 3 5 6，这种就是递增序列。接下来我们思考一下这道题目：要求两个非递减序列合并到大的序列后依旧为非递减序列。我们对两个数组定义两个指针，倒着比较将大的数插入。每个数组最后面的都是最大的数，放在最后就可以保证生成的数组还是非递减数组。代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1=m-1,end2=n-1,end=m+n-1;
    while(end1>=0&&end2>=0)
    {
        if(nums1[end1]>nums2[end2])
        {
            nums1[end--]=nums1[end1--];
        }
        else
        {
            nums1[end--]=nums2[end2--];
        }
    }
    while(end2>=0)
    {
        nums1[end--]=nums2[end2--];
    }
}

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

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

相关文章

C#文件操作File类vsFileInfo类和Directory类vsDirectoryInfo类

C#文件操作File类vsFileInfo类和Directory类vsDirectoryInfo类

目录 一、File类vsFileInfo类 1.File类 &#xff08;1&#xff09;示例源码 &#xff08;2&#xff09;生成效果 2.FileInfo类 &#xff08;1&#xff09;示例源码 &#xff08;2&#xff09;生成效果 二、 Directory类vsDirectoryInfo类 1.Directory类 &#xff08;…
阅读更多...
C语言基础介绍

C语言基础介绍

1. C语言基础知识 C语言是一种计算机编程语言&#xff0c;是一门用于编写系统软件和应用软件的高级语言。C语言的基础知识包括&#xff1a; 数据类型&#xff1a;C语言中的数据类型包括整型、浮点型、字符型等。 变量&#xff1a;C语言中使用变量来存储数据&#xff0c;变量必…
阅读更多...
量化交易：因子风险暴露

量化交易：因子风险暴露

本文介绍了如何计算因子风险暴露的内容。 判断风险暴露的建模是否合理 通常&#xff0c;此分析是基于历史数据&#xff0c;而对历史风险暴露的估计可能会影响未来的风险暴露。 因此&#xff0c;计算因子风险暴露是不够的。 必须对风险暴露保持信心&#xff0c;并明白对风险暴…
阅读更多...
Vue框架学习笔记——键盘事件

Vue框架学习笔记——键盘事件

文章目录 前文提要键盘事件&#xff08;并不是所有按键都能绑定键盘事件&#xff09;常用的按键不同的tab和四个按键keyCode绑定键盘事件&#xff08;不推荐&#xff09;Vue.config.keyCode.自定义键名 键码 神奇的猜想div标签和click.enterbutton标签和click.enter 前文提要 …
阅读更多...
定长子网划分和变长子网划分问题_二叉树解法_通俗易懂_配考研真题

定长子网划分和变长子网划分问题_二叉树解法_通俗易懂_配考研真题

引入:定长子网划分和变长子网划分的基本概念 定长子网划分和变长子网划分的基本概念 目前常用的子网划分&#xff0c;是基于CIDR的子网划分&#xff0c;也就是将给定的CIDR地址块划分为若干个较小的CIDR地址块。 定长子网划分: 使用同一个子网掩码来划分子网&#xff0c;因…
阅读更多...
【版本管理 | Git】Git rebase 命令最佳实践！确定不来看看？

【版本管理 | Git】Git rebase 命令最佳实践！确定不来看看？

&#x1f935;‍♂️ 个人主页: AI_magician &#x1f4e1;主页地址&#xff1a; 作者简介&#xff1a;CSDN内容合伙人&#xff0c;全栈领域优质创作者。 &#x1f468;‍&#x1f4bb;景愿&#xff1a;旨在于能和更多的热爱计算机的伙伴一起成长&#xff01;&#xff01;&…
阅读更多...
智能优化算法应用：基于斑点鬣狗算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于斑点鬣狗算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于斑点鬣狗算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于斑点鬣狗算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.斑点鬣狗算法4.实验参数设定5.算法结果6.参考…
阅读更多...
VM虚拟机中Ubuntu14.04安装VM tools后仍不能全屏显示

VM虚拟机中Ubuntu14.04安装VM tools后仍不能全屏显示

1、查看Ubuntu所支持的分辨率大小。 在终端处输入&#xff1a; xrandr&#xff0c;回车 2、输入你想设置的分辨率参数。 我设置的为1360x768&#xff0c;大家可以根据自己的具体设备设置。 在终端输入&#xff1a;xrandr -s 1360x768 注意&#xff1a;这里1360后边是字母 x 且…
阅读更多...
＜JavaEE＞ Thread线程类 和 Thread的常用方法

＜JavaEE＞ Thread线程类 和 Thread的常用方法

目录 一、Thread概述 二、构造方法 三、常用方法 1.1 getId()、getName()、getState()、getPririty() 1.2 start() 1.3 isDaemon()、setDaemon() 1.4 isAlive() 1.5 currentThread() 1.6 Interrupt()、interrupted()、isInterrupted() 1.6.1 方法一&#xff1a;添加共…
阅读更多...
S25FL系列FLASH读写的FPGA实现

S25FL系列FLASH读写的FPGA实现

文章目录 实现思路具体实现子模块实现top模块 测试Something 实现思路 建议读者先对 S25FL-S 系列 FLASH 进行了解&#xff0c;我之前的博文中有详细介绍。 笔者的芯片具体型号为 S25FL256SAGNFI00&#xff0c;存储容量 256Mb&#xff0c;增强高性能 EHPLC&#xff0c;4KB 与 6…
阅读更多...
Java中static、final、static final的区别

Java中static、final、static final的区别

文章目录 finalstaticstatic final final final可以修饰&#xff1a;属性&#xff0c;方法&#xff0c;类&#xff0c;局部变量&#xff08;方法中的变量&#xff09; final修饰的属性的初始化可以在编译期&#xff0c;也可以在运行期&#xff0c;初始化后不能被改变。 final修…
阅读更多...
nginx配置文件的简单结构

nginx配置文件的简单结构

nginx的配置文件&#xff08;nginx.conf&#xff09;整体上可分为三个部分&#xff1a;全局块、events块、http块 区域职责全局块配置和nginx运行相关的全局配置events块配置和网络连接相关的配置http块配置代理、缓存、日志记录、虚拟主机等配置在http块中&#xff0c;可以包含…
阅读更多...
python：傅里叶分析，傅里叶变换 FFT

python：傅里叶分析，傅里叶变换 FFT

使用python进行傅里叶分析&#xff0c;傅里叶变换 FFT 的一些关键概念的引入&#xff1a; 1.1.离散傅里叶变换&#xff08;DFT&#xff09; 离散傅里叶变换(discrete Fourier transform) 傅里叶分析方法是信号分析的最基本方法&#xff0c;傅里叶变换是傅里叶分析的核心&…
阅读更多...
摆脱无用代码的负担：TreeShaking 的魔力

摆脱无用代码的负担：TreeShaking 的魔力

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
【教学类-06-12】20231126 （一）如何让加减乘除题目从小到大排序（以1-20之间加法为例，做正序排列用）

【教学类-06-12】20231126 （一）如何让加减乘除题目从小到大排序（以1-20之间加法为例，做正序排列用）

结果展示 优化后 优化前 背景需求&#xff1a; 生成列表 单独抽取显示题目排序方法 存在问题: 我希望 00 01 02……这样排序&#xff0c;但是实际上&#xff0c;除了第一个加数会从小到大排序&#xff0c;第二个被加数的第十位数和个位数都会从小到大排序&#xff0c;也就是…
阅读更多...
NeoPreference延伸：为SharedPreferences配置项生成配置页面

NeoPreference延伸：为SharedPreferences配置项生成配置页面

代码地址&#xff1a;https://github.com/Nagi1225/NeoPreference.git 最初在开发NeoPreference这个SharedPreferences工具的时候&#xff0c;就期望完成三个目标&#xff1a; 代码简洁&#xff0c;新增配置项的时候一行代码&#xff08;最多两行&#xff09;&#xff1b;读写…
阅读更多...
线程的常用方法-wait和notify以及线程的结束方式

线程的常用方法-wait和notify以及线程的结束方式

再复习一下Java中的线程的状态图 wait和sleep的区别是&#xff1a;wait需要先持有锁&#xff08;wait需要再synchronized代码块中执行&#xff09;&#xff0c;执行后会让出锁。而sleep不需要先持有锁&#xff0c;执行后也不会释放锁&#xff08;有锁的话抱着锁睡觉&#xff09…
阅读更多...
SpringBoot 环境使用 Redis + AOP + 自定义注解实现接口幂等性

SpringBoot 环境使用 Redis + AOP + 自定义注解实现接口幂等性

目录 一、前言二、主流实现方案介绍2.1、前端按钮做加载状态限制&#xff08;必备&#xff09;2.2、客户端使用唯一标识符2.3、服务端通过检测请求参数进行幂等校验&#xff08;本文使用&#xff09; 三、代码实现3.1、POM3.2、application.yml3.3、Redis配置类3.4、自定义注解…
阅读更多...
基于Haclon的标签旋转项目案例

基于Haclon的标签旋转项目案例

项目要求&#xff1a; 图为HALCON附图“25interleaved_exposure_04”&#xff0c;里面为旋转的二维码标签&#xff0c;请将其旋转到水平位置。 项目知识&#xff1a; 在HALCON中进行图像平移和旋转通常有以下步骤&#xff1a; &#xff08;1&#xff09;通过hom_mat2d_ident…
阅读更多...
jQuery_03 dom对象和jQuery对象的互相转换

jQuery_03 dom对象和jQuery对象的互相转换

dom对象和jQuery对象 dom对象 jQuery对象 在一个文件中同时存在两种对象 dom对象: 通过js中的document对象获取的对象 或者创建的对象 jQuery对象: 通过jQuery中的函数获取的对象。 为什么使用dom或jQuery对象呢&#xff1f; 目的是 要使用dom对象的函数或者属性 以及呢 要…
阅读更多...
最新文章

Copyright @ 2022~2023