当前位置： 首页 > article >正文

【数据结构2】线性表——顺序表

article 2024/12/26 1:12:20

醒醒啊该读书了

文章目录

  • 前言
  • 一、线性表的概念
  • 二、顺序表的实现
    • 2.1.顺序表的概念及结构
    • 2.2.动态顺序表的接口实现
    • 2.3.动态顺序表的全部代码展示
  • 三、顺序表相关OJ题练习
  • 总结

前言

【本节目标】
1.了解线性表概念；
2.实现顺序表的增删查改等功能；
3.练习顺序表相关OJ题。

一、线性表的概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储，分别对应着顺序表和链表，今天我们先来学习顺序表。
线性表

二、顺序表的实现

2.1.顺序表的概念及结构

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

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储
  2. 动态顺序表：使用动态开辟的数组存储
//顺序表的静态存储

//增强程序的可维护性，MAX_SIZE和SQDataType方便可改
#define MAX_SIZE 100
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType a[MAX_SIZE];	//定长数组
	int size;	//有效数据的个数
}SL;

//顺序表的动态存储
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;	//指向动态开辟的数组
	int size;		//有效数据的个数
	int capacity;	//容量空间的大小
}SL;

2.2.动态顺序表的接口实现

静态顺序表的缺点：定长数组导致空间开多了浪费，开少了不够用，不能灵活控制。静态顺序表只适用于确定知道需要存多少数据的场景。
所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表的基本增删查改等函数接口。

//顺序表初始化
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//顺序表的销毁
//malloc的空间不销毁就会存在内存泄漏
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//函数封装：检查顺序表容量是否为满，满了则扩容
void SeqListCheckCapacity(SL* ps)
{
	//容量满了就要扩容扩两倍
	if (ps->size == ps->capacity)
	{
		/*realloc(原空间，扩容大小) :
		后面有足够的空间就原地扩，没有的话开辟一个新空间拷贝数据，释放旧空间。
		原空间如果为空，则申请一个新空间，相当于malloc。*/
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//扩两倍
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

//顺序表的任意位置数据的插入
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos <= ps->size);	
	SeqListCheckCapacity(ps);
	
	//将要插入的位置之后的数据都往后挪一位
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

//顺序表的尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	SeqListCheckCapacity(ps);	//检查顺序表容量是否为满，满了则扩容
	
	ps->a[ps->size] = x;
	ps->size++;
}

//顺序表的尾插，或者直接复用SeqListInsert
void SeqListPushBack(SL* ps, SQDataType x)
{
	SeqListInsert(ps, ps->size, x);	
}

//顺序表的头插
void SeqListPushFront(SL* ps, SQDataType x)
{
	SeqListCheckCapacity(ps);

	//先将数据都往后挪一位，再将要插入的数据插在头
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

//顺序表的头插，或者直接复用SeqListInsert
void SeqListPushFront(SL* ps, SQDataType x)
{
	SeqListInsert(ps, 0, x);
}

//顺序表的任意位置数据的删除
void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);	
	//将要删除的位置之后的数据都往前挪一位
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

//顺序表的尾删
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);	//断言，相当于粗暴的if，用来检查数组是否为空
	//断言函数void assert(int expression)：expression结果为0则直接终止程序，否则不作操作
	ps->size--;		//尾删直接把有效数据个数减一就可以了
}

//顺序表的尾删，或者直接复用SeqListErase
void SeqListPopBack(SL* ps)
{
	SeqListErase(ps, ps->size - 1);
}

//顺序表的头删
void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);
	//从第二个数开始，后面的数全部往前挪一位
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

//顺序表的头删，或者直接复用SeqListErase
void SeqListPopFront(SL* ps)
{
	SeqListErase(ps, 0);	//直接复用SeqListErase
}

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

//顺序表的修改
void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);	
	ps->a[pos] = x;
}

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

2.3.动态顺序表的全部代码展示

  • SeqList.h
#pragma once

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

typedef int SQDataType;
typedef struct SeqList
{
	SQDataType* a;
	int size;		//有效数据的个数
	int capacity;	//容量空间的大小
}SL;

//增删查改等接口函数的函数声明
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestory(SL* ps);
void SeqListPushBack(SL* ps, SQDataType x);
void SeqListPushFront(SL* ps, SQDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);
void SeqListInsert(SL* ps, int pos, SQDataType x);
void SeqListErase(SL* ps, int pos);
int SeqListFind(SL* ps, SQDataType x);
void SeqListModity(SL* ps, int pos, SQDataType x);

#endif
  • SeqList.c
#define  _CRT_SECUER_NO_WARNINGS
#include "SeqList.h"

//顺序表的初始化
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//顺序表的销毁，malloc的空间不销毁就会存在内存泄漏
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//函数封装：检查顺序表的容量是否为满
void SeqListCheckCapacity(SL* ps)
{
	//满了就要扩容 扩两倍
	if (ps->size == ps->capacity)
	{
		/*realloc(原空间，扩容大小) :
		后面有足够的空间就原地扩，没有的话开辟一个新空间拷贝数据，释放旧空间
		原空间如果为空，则申请一个新空间，相当于malloc*/
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

//顺序表的尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	/*SeqListCheckCapacity(ps);	//检查顺序表容量是否为满，满了则扩容
	ps->a[ps->size] = x;
	ps->size++;*/

	SeqListInsert(ps, ps->size, x);	//直接复用SeqListInsert
}

//顺序表的头插
void SeqListPushFront(SL* ps, SQDataType x)
{
	/*SeqListCheckCapacity(ps);
	先将数据都往后挪一位，再将要插入的数据插在头
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;*/

	SeqListInsert(ps, 0, x);
}

//顺序表的尾删
void SeqListPopBack(SL* ps)
{
	//assert(ps->size > 0);		//相当于粗暴的if，用来检查
	//断言函数void assert(int expression)：expression结果为0则直接终止程序，否则不作操作
	//ps->size--;

	SeqListErase(ps, ps->size - 1);	//直接复用SeqListErase
}


//顺序表的头删
void SeqListPopFront(SL* ps)
{
	//assert(ps->size > 0);	
	//从第二个数开始，后面的数全部往前挪一位	
	//int start = 1;
	//while (start < ps->size)
	//{
	//	ps->a[start - 1] = ps->a[start];
	//	++start;
	//}
	//ps->size--;

	SeqListErase(ps, 0);
}

//顺序表的任意位置数据的插入
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos <= ps->size);	
	SeqListCheckCapacity(ps);

	//将要插入的位置之后的数据都往后挪一位
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

//顺序表的任意位置数据的删除
void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);	

	//将要删除的位置之后的数据都往前挪一位
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

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

//顺序表的修改
void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);		
	ps->a[pos] = x;
}

//顺序表的打印
void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
  • Test.c（测试写一个测一个，方便改错，这里写完后我将顺序表做成了一个菜单）
#define  _CRT_SECUER_NO_WARNINGS
#include "SeqList.h"

//void TestSeqList1()
//{
//	SL sl;
//	SeqListInit(&sl);
//	SeqListPushBack(&sl, 6);
// 	SeqListPushBack(&sl, 7);
//	SeqListPushBack(&sl, 8);
//	SeqListPushBack(&sl, 9);
//	SeqListPushBack(&sl, 10);
//	SeqListPrint(&sl);
//
//	SeqListPushFront(&sl, 5);
//	SeqListPushFront(&sl, 4);
//	SeqListPushFront(&sl, 3);
//	SeqListPushFront(&sl, 2);
//	SeqListPushFront(&sl, 1);
//	SeqListPrint(&sl);
//
//	SeqListPopBack(&sl);
//	SeqListPopBack(&sl);
//	SeqListPrint(&sl);
//
//	SeqListPopFront(&sl);
//	SeqListPopFront(&sl);
//	SeqListPrint(&sl);
//
//	SeqListInsert(&sl, 3, 250);
//	SeqListPrint(&sl);
//
//	SeqListErase(&sl, 3);
//	SeqListPrint(&sl);
//
//	SeqListDestory(&sl);
//}

//菜单 (不要一上来就写，先写上面的测试)
void menu()
{
	printf("\n--------------------------------------\n");
	printf("1.尾插数据  2.头插数据\n");
	printf("3.尾删数据  4.头删数据\n");
	printf("5.选择某一位置插入数据\n");
	printf("6.选择某一位置删除数据\n");
	printf("7.查找数据  8.修改数据\n");
	printf("9.清空     -1.退出\n");
	printf("--------------------------------------\n");
	printf("请输入你的操作选项：\n");
}

int main()
{
	SL s;
	SeqListInit(&s);
	int option = 0;
	int x = 0, y = 0;
	while (option != -1)
	{
		menu();
		scanf_s("%d", &option);
		switch (option)
		{
		case 1:
			printf("请输入你要插入的数据，以-1结束\n");
			do
			{
				scanf_s("%d", &x);
				if (x != -1)
				{
					SeqListPushBack(&s, x);
				}
			} while (x != -1);
			SeqListPrint(&s);
			break;
		case 2:
			printf("请输入你要插入的数据，以-1结束\n");
			do
			{
				scanf_s("%d", &x);
				if (x != -1)
				{
					SeqListPushFront(&s, x);
				}
			} while (x != -1);
			SeqListPrint(&s);
			break;
		case 3:
			SeqListPopBack(&s);
			SeqListPrint(&s);
			break;
		case 4:
			SeqListPopFront(&s);
			SeqListPrint(&s);
			break;
		case 5:
			printf("请输入你要插入的位置和数据：\n");
			scanf_s("%d %d", &x, &y);
			SeqListInsert(&s, x, y);
			SeqListPrint(&s);
			break;
		case 6:
			printf("请输入你要删除的数据的位置：\n");
			scanf_s("%d", &y);
			SeqListErase(&s, y);
			SeqListPrint(&s);
			break;
		case 7:
			printf("请输入你要查找的数据：\n");
			scanf_s("%d", &x);
			y = SeqListFind(&s, x);
			if (y == -1)
				printf("未找到！\n");
			else
				printf("它在第%d个位置\n", y);
			break;
		case 8:
			printf("请输入你要修改的位置和数据：\n");
			scanf_s("%d %d", &x, &y);
			SeqListModity(&s, x, y);
			SeqListPrint(&s);
			break;
		case 9:
			SeqListInit(&s);
			break;
		case -1:
		default:
			break;
		}
	}
	SeqListDestory(&s);

	return 0;
}

制作菜单没有什么技巧，耐得住性子就好，做出来还是成就感满满的，大家都可以去试试~

菜单

三、顺序表相关OJ题练习

3.1. 原地移除元素：https://leetcode-cn.com/problems/remove-element/

移除元素
移除元素

//法一：快慢指针，时间复杂度O(N)，空间复杂度O(1)。
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int p1 = 0,p2 = 0;	//p1是快指针，p2是慢指针
        while(p1 < n)
        {
            if(nums[p1] != val)
                nums[p2++] = nums[p1];
            p1 ++;
        }
        return p2;
    }
};

//法二：空间换时间，创建一个新数组，时间复杂度O(N)，空间复杂度O(N)。
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        vector<int> b;	//创建一新数组b
        int cnt=0;
        for(int i=0;i<n;++i)
        {
            if(nums[i] != val) 
            {
                b.push_back(nums[i]);
                cnt ++;
            }
        }
        for(int i=0;i<cnt;++i)
            nums[i] = b[i];
        return cnt;
    }
};

3.2. 合并两个有序数组：https://leetcode-cn.com/problems/merge-sorted-array/

合并数组

//法一：双指针，从后往前插
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1=m-1,p2=n-1,cnt=m+n-1;
        while(p1>=0 && p2>=0)
        {
            if(nums1[p1] > nums2[p2])
                nums1[cnt--] = nums1[p1--];
            else
                nums1[cnt--] = nums2[p2--];
        }
        while(p2>=0) nums1[cnt--] = nums2[p2--];
        //如果p1>=0,不需要处理,因为本来就在nums1里面
    }
};

//法二：空间换时间，创建新数组
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> a(m+n);
        int x=0,y=0,cnt=0;
        while(x<m && y<n)
        {
            if(nums1[x] <= nums2[y])
                a[cnt++] = nums1[x++];
            else
                a[cnt++] = nums2[y++];
        }
        while(y<n) 
            a[cnt++] = nums2[y++];
        while(x<m)
            a[cnt++] = nums1[x++];
        for(int i=0;i<m+n;++i)
        {
            nums1[i] = a[i];
        }
    }
};

总结

数据结构的线性表——顺序表就到这里了，代码有点多所以文章比较长，顺序表相对较简单，耐着性子把接口函数记住并熟悉，一定要自己把代码敲一遍噢，培养代码能力，对后续学习数据结构也很有帮助，加油！
好好学习卡


http://www.kler.cn/a/451466.html

相关文章：

  • information_schema是什么？
  • 安装openGauss数据库一主一备
  • 四种电子杂志制作软件
  • 解决 Docker 中 DataLoader 多进程错误：共享内存不足
  • 分享某大佬微信hook 最新版本 dll （懂得都懂）
  • 蓝桥杯嵌入式备赛教程(1、led，2、lcd，3、key)
  • 动态规划：石子合并 图文+举例超详细说明
  • OpenCV相机标定与3D重建(26)计算两个二维点集之间的部分仿射变换矩阵（2x3）函数 estimateAffinePartial2D()的使用
  • AWTK 在树莓派 pico 上的移植笔记
  • HTMLCSSJavaScriptDOM 之间的关系？
  • 组态页面渲染器通过npm包方式使用页面没有渲染成功的问题
  • gesp(三级)（14）洛谷：B4039：[GESP202409 三级] 回文拼接
  • 贪心算法求解加油站问题
  • 《ROS2 机器人开发 从入门道实践》 鱼香ROS2——第4章内容
  • WebAuthn 项目常见问题解决方案
  • C++抽象类与类继承相关注意事项 [学习笔记]
  • select 1 from table的作用 详解
  • 【ue5学习笔记2】在场景放入一个物体的蓝图输入事件无效？
  • sentinel学习笔记8-系统自适应与黑白名单限流
  • LabVIEW实现GSM/GPRS通信
  • LeetCode 3138.同位字符串连接的最小长度：计数（一个数最多128个因数）
  • Python中定位元素包含文本信息的详细解析与代码示例
  • QWebChannel实现与JS的交互
  • 使用React构建一个掷骰子的小游戏
  • skywalking 搭建
  • 【漫话机器学习系列】016.误差中的偏差(BIAS)