【数据结构】第二站:顺序表

这篇具有很好参考价值的文章主要介绍了【数据结构】第二站:顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、线性表

二、顺序表

1.顺序表的概念以及结构

2.顺序表的接口实现

3.顺序表完整代码

三、顺序表的经典题目

1.移除元素

2.删除有序数组中的重复项

3.合并两个有序数组


一、线性表

在了解顺序表前,我们得先了解线性表的概念

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储
 

二、顺序表

1.顺序表的概念以及结构

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

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

静态顺序表

typedef int SLDateType;

#define N 10

typedef struct SeqList
{
	SLDateType a[N];
	int size;
}SL;

如上代码所示,就是静态顺序表的定义。但是静态顺序表很不好用,因为开多了内存浪费,开少了不够用

动态顺序表

//动态顺序表
typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;//指向数据的指针
	int size;
	int capacity; //容量
}SL;

如上代码所示,动态的顺序表就是通过一个指针来指向数据。为了动态管理,所以要添加一个容量的变量

2.顺序表的接口实现

我们使用顺序表的目的就是为了增删查改一些数据。为此接口主要围绕增删查改。

1.顺序表接口声明

//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表的销毁
void SeqListDestroy(SL* ps);
//顺序表的打印
void SeqListPrint(SL ps);
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x);
//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x);
//顺序表的尾删
void SeqListPopBack(SL* ps);
//顺序表的头删
void SeqListPopFront(SL* ps);
//顺序表的查找
int SeqListFind(SL* ps, SLDateType x);
//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x);
//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos);

如上代码所示,对于顺序表,我们主要的目的就是增删查改,因此我们所需要实现的接口就又初始化、销毁、打印、尾插、头插、尾删、头删、查找、在某位置插入、在某位置删除等

2.顺序表的初始化

//顺序表的初始化
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

如上代码所示,我们的函数参数是顺序表的指针,返回类型是void。

首先肯定ps是不可能为空的,因为ps是顺序表的地址。

然后我们让顺序表的数据指针指向的数组初始容量设置为INIT_CAPACITY,这个容量由宏来自定义。然后判断是否开辟内存成功。

如果成功则将size置为0,size代表的是当前顺序表内已经存放的数据个数。

2.顺序表的销毁

//顺序表的销毁
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

我们在来看一下顺序表的销毁,对于顺序表的销毁,也是比较简单的,我们的顺序表中,数据指针所指向的区域是在堆区的,所以我们要对这个堆区进行释放掉。然后将其置空,最后size和capacity都置为0即可

3.顺序表打印

//顺序表的打印
void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}

如上代码所示,由于是打印数据,所以我们传一个形参就已经可以了。当然传顺序表的地址也是没有任何问题的。然后就是使用一个循环来进行打印即可。

4.顺序表的尾插以及扩容函数

//扩容函数
void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

如上代码所示,我们想要对顺序表进行尾插,那么首先我们得确保一下当前的容量是否足够,为了代码的简洁,我们直接将检查容量封装成一个函数,在检查容量的过程中,如果size和capacity相等,那么就意味着函数需要扩容了。我们使用realloc函数进行扩容即可,需要注意的是,进行扩容的时候要使用一个新的指针进行接收这个扩容后的地址,不然一旦扩容失败,后果得不偿失。我们一般采用的是扩容二倍。当然这里我们可以根据自己的想法进行调整。

扩容成功以后,由于是一个数组,那么就很简单的直接将数组的最后一个元素直接赋值即可,然后size++就可以了

5.顺序表的头插

//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}

对于顺序表的头插,我们仍然是先检查容量,这里就体现我们之前将扩容封装成一个一个函数的优势了。然后使用一个循环,将整个数组的值向后移动一个空间。最后将第一个元素给插入x即可

6.顺序表的尾删

//顺序表的尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("无可删除数据\n");
		return;
	}
	ps->size--;
}

对于这个尾删,我们特别需要主要的是当size为0的时候,就没有数据,不需要删除即可,这里可以采用assert暴力截止,也可以使用return温柔的拦截

然后我们直接让size--就可以了

7.顺序表的头删

//顺序表的头删
void SeqListPopFront(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("无可删除数据\n");
		return;
	}
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

对于顺序表的头删,也是需要注意size为0的情况,然后将从下标为1的元素开始,全体元素向前移动的一个空间即可,最后size--

8.顺序表的查找

//顺序表的查找
int SeqListFind(SL* ps, SLDateType x) 
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

对于顺序表的查找,我们就直接采用循环遍历的方式即可,如果找到了,则返回下标,否则返回-1

9.顺序表在pos位置的插入

//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->size++;
}

如上代码所示,在pos位置的插入,那么首先需要注意的是,pos的范围要合理,pos应该大于等于0且小于等于size,pos等于size其实就是尾插

然后检查容量,使用循环将原来pos以及之后的位置统一向后移动一个空间,然后将pos位置的值赋值即可,最后size++

10.顺序表在pos位置的删除

//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

对于在pos位置的删除,那么思路与前面也是极其相似的,首先需要注意的是pos的范围,这里要小心了,pos是不可以等于size的

然后就是通过循环,将pos后面的数据,统一向前覆盖即可

3.顺序表完整代码

SeqList.h

#pragma once
//静态顺序表
//typedef int SLDateType;
//
//#define N 10
//
//typedef struct SeqList
//{
//	SLDateType a[N];
//	int size;
//}SL;
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define INIT_CAPACITY 4
//动态顺序表
typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;//指向数据的指针
	int size;
	int capacity; //容量
}SL;

//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表的销毁
void SeqListDestroy(SL* ps);
//顺序表的打印
void SeqListPrint(SL ps);
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x);
//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x);
//顺序表的尾删
void SeqListPopBack(SL* ps);
//顺序表的头删
void SeqListPopFront(SL* ps);
//顺序表的查找
int SeqListFind(SL* ps, SLDateType x);
//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x);
//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

//顺序表的初始化
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}
//顺序表的销毁
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//顺序表的打印
void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}
//扩容函数
void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}
//顺序表的尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("无可删除数据\n");
		return;
	}
	ps->size--;
}
//顺序表的头删
void SeqListPopFront(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("无可删除数据\n");
		return;
	}
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//顺序表的查找
int SeqListFind(SL* ps, SLDateType x) 
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->size++;
}
//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void TestSeqList1()
{
	SL s;
	SeqListInit(&s);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrint(s);

	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 3);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 1);

	SeqListPrint(s);

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);

	SeqListPrint(s);
	
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrint(s);

	SeqListPopFront(&s);
	SeqListPrint(s);

	SeqListPopFront(&s);
	SeqListPrint(s);

	SeqListPopFront(&s);
	SeqListPrint(s);

	SeqListPopFront(&s);
	SeqListPrint(s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);

}
void TestSeqList2()
{
	SL s;
	SeqListInit(&s);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrint(s);

	int pos = SeqListFind(&s, 3);
	
	SeqListInsert(&s, pos, 5);
	SeqListInsert(&s, pos, 6);
	SeqListInsert(&s, pos, 7);
	SeqListPrint(s);

	SeqListErase(&s, pos);
	SeqListErase(&s, pos);
	SeqListErase(&s, pos);
	SeqListPrint(s);

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

三、顺序表的经典题目

1.移除元素

题目链接:力扣

解一:暴力循环法

即利用顺序表在某个位置的删除,只要某个位置满足删除的条件,就将后面的数据全部移动到前面来。但是效率太低,时间复杂度达到了O(N²)

解二:使用新数组

开辟一个新的数组,如果原数组中的这个元素不是需要移除的元素,则直接拷贝到新数组中,如果是需要移除的元素,则不拷贝,最后将新数组拷贝到原来的数组中即可,如果新数组开辟在了堆区,那么要记得释放空间,这种方法的时间复杂度和空间复杂度均为O(N),显然不满足题目要求

解三:使用双指针

思路与解二基本类似,但是不同的是,我们可以利用两个下标来实现我们的思路,我们设置两个下标src和dst,我们让src去遍历整个数组,如果在src处的值不是val,则将src处的值拷贝到dst中,然后src和dst均++

如果是val,则src++。其余不动,代码如下

int removeElement(int* nums, int numsSize, int val) {
    int src = 0;
    int dst = 0;
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            nums[dst] = nums[src];
            dst++;
            src++;
        }
        else
        {
            src++;
        }
    }
    return dst;
}

2.删除有序数组中的重复项

题目描述:力扣

对于这道题,我们的思路和第一道题是基本一致的,采用双指针的方法

【数据结构】第二站:顺序表

 如上图所示,我们使用src和dst两个下标,src初始值设置为1,dst设置为0,那么当src和dst的值相等的时候,src++。如果不相等,则先让dst++,然后将src处的值赋值给dst,最后src++。代码如下

int removeDuplicates(int* nums, int numsSize) {
    int src = 1;
    int dst = 0;
    for (src = 1; src < numsSize;)
    {
        if (nums[src] == nums[dst])
        {
            src++;
        }
        else
        {
            dst++;
            nums[dst] = nums[src];
            src++;
        }
    }
    return dst + 1;
}

3.合并两个有序数组

题目描述:力扣

解一:直接合并,然后排序

最简单的方式就是直接暴力合并,然后采用排序算法就可以了。但是这是一个俗手。时间复杂度较高

解二:归并

对于这道题而言,我们可以采用归并的思路

【数据结构】第二站:顺序表

首先是设置三个下标end1,end2,end。

然后我们循环比较end1和end2所指向的较大值,将较大值赋给end所指向的位置。然后赋值的end和被赋值的end均--。

当end2的值先变成了负数的时候,那么自然是最好的状态,此时肯定有序。

但是当end1的值先变成了负数的时候,那么end2的数据并未完全存放到nums1中,此时我们需要将end2的剩余元素给插入到nums1中

具体代码如下:


void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1 = m - 1;
    int end2 = n - 1;
    int end = m + n - 1;

    while (end1 >= 0 && end2 >= 0)
    {
        if (nums1[end1] > nums2[end2])
        {
            nums1[end] = nums1[end1];
            end--;
            end1--;
        }
        else
        {
            nums1[end] = nums2[end2];
            end--;
            end2--;
        }
    }
    if (end1 < 0)
    {
        while (end2 >= 0)
        {
            nums1[end] = nums2[end2];
            end2--;
            end--;
        }
    }
}

好了,本期内容就到这里

如果对你有帮助的话,不要忘记点赞加收藏哦!!!文章来源地址https://www.toymoban.com/news/detail-408942.html

到了这里,关于【数据结构】第二站:顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-线性表-顺序表

    线性表的定义:由n(n=0)个数据特性相同的元素构成的有限序列,称为线性表。当n=0时称之为空表。 因为构件线性表时元素数组已经使用静态分配,所以在此只需要对线性表的长度执行初始化即可。 获取数据需要参数: sqList:需要给定一个线性表从而获取数据,因为只是拿值

    2024年02月08日
    浏览(48)
  • 数据结构 · 线性表 | 顺序表

    啊我摔倒了..有没有人扶我起来学习.... 👱 个人主页: 《 C G o d 的 个 人 主 页 》 color{Darkorange}{《CGod的个人主页》} 《 C G o d 的 个 人 主 页 》 交个朋友叭~ 💒 个人社区: 《 编 程 成 神 技 术 交 流 社 区 》 color{Darkorange}{《编程成神技术交流社区》} 《 编 程 成 神 技 术

    2024年02月02日
    浏览(49)
  • 数据结构——线性表①(顺序表)

    线性表是一种数据结构,它是由n个具有 相同数据类型 的数据元素a1,a2,…,an组成的 有限序列 。 其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。 线性表可以用 顺序存储结构 或 链式存储结构

    2024年02月06日
    浏览(53)
  • 数据结构:线性表之-顺序表

    目录 1.线性表概念 1.1 什么是顺序列表 1.2 线性表 2.顺序表实现 将有以下功能: 详细过程 顺序表的动态存储 顺序表初始化 尾插 扩容 头插 更改后的尾插 尾删 头删 打印 释放内存 优化顺序表 (任意位置插入删除) 优化后的头插尾插 优化后的头删尾删 查找和删除 进行装饰(菜单

    2024年02月10日
    浏览(51)
  • 数据结构---顺序表示的线性表

             数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简言之,数据

    2024年02月16日
    浏览(53)
  • 数据结构: 线性表(顺序表实现)

    线性表(linear list)是 n 个具有相同特性的数据元素的有序序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表: 顺序表,链表,栈,队列,字符串… 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删

    2024年02月14日
    浏览(49)
  • C/C++数据结构---顺序表---线性存储结构

    个人主页: 仍有未知等待探索_小项目,洛谷刷题,数据结构-CSDN博客 专题分栏---数据结构: 数据结构_仍有未知等待探索的博客-CSDN博客 目录 一、知识储备 二、引例  三、顺序表 第一步,先创建一个顺序表类型 第二步,定义和初始化顺序表    第三步,顺序表的基本操作

    2024年02月08日
    浏览(41)
  • 数据结构(二)----线性表(顺序表,链表)

    目录 1.线性表的概念 2.线性表的基本操作 3.存储线性表的方式 (1)顺序表 •顺序表的概念 •顺序表的实现 静态分配: 动态分配: 顺序表的插入: 顺序表的删除: 顺序表的按位查找: 顺序表的按值查找: 顺序表的特点: (2)单链表 •单链表的实现 不带头结点的单链表

    2024年04月16日
    浏览(56)
  • 【数据结构】线性表和顺序表

    Yan-英杰的主页 悟已往之不谏 知来者之可追 目录 1.线性表 2.顺序表         2.1 静态顺序表         2.2 动态顺序表         2.3移除元素         线性表( linear list )是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线

    2023年04月08日
    浏览(84)
  • 数据结构——线性表之顺序表

    目录 一.线性表 二.顺序表实现  2.1 概念及结构  2.2 动态顺序表 2.2.1 初始化与销毁函数 2.2.2 打印函数 2.2.3 尾插函数 2.2.4 尾删函数 2.2.5 扩容函数 2.2.6 头插函数 2.2.7 头删函数 2.2.8 任意位置插入函数 2.2.9 查找函数 2.2.10 任意位置删除函数  2.2.11 修改函数 三.完整代码 四.力扣

    2024年02月07日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包