首页 > 编程语言 >【数据结构】详细介绍线性表中的顺序表，带你复盘实现细节，附上顺序表编程练习题

【数据结构】详细介绍线性表中的顺序表，带你复盘实现细节，附上顺序表编程练习题

时间：2024-08-14 15:56:51浏览次数：16  
标签：练习题 顺序 线性表 psl int SeqList array size

目录

一. 线性表

二. 顺序表 

1. 静态顺序表与动态顺序表

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

2.1 顺序表初始化 

2.2 判断是否需要扩容  

2.3 顺序表指定位置插入

2.4 顺序表头插

2.5 顺序表尾插

2.6 顺序表指定位置删除

2.7 顺序表头删

2.8 顺序表尾删

2.9 顺序表查找

2.10 顺序表修改 

2.11 顺序表销毁

2.12 顺序表打印

3. 顺序表的缺点

4. 顺序表编程练习题 

4.1 移除元素

4.2 删除有序数组中的重复项

4.3 合并两个有序数组

一. 线性表

1. 线性表(linear list)是n个具有相同特性的数据元素的有限序列。

2. 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

二. 顺序表 

1. 静态顺序表与动态顺序表

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

2. 顺序表一般可以分为：

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

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType array[N]; //定长数组
	size_t size;         //有效数据个数
}SeqList;

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

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* array; //指向动态开辟的数组
	size_t size;       //有效数据个数
	size_t capacity;   //空间容量
}SeqList;

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

1. 静态顺序表只适用于确定知道需要存多少数据的场景。

2. 静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。

3. 所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

2.1 顺序表初始化 

1. 将结构的每个成员进行初始化

void SeqListInit(SeqList* psl, size_t capacity)
{
	assert(psl);

	psl->array = (SLDataType*)malloc(sizeof(SeqList) * capacity);
	if (psl->array == NULL)
	{
		perror("malloc");
		return;
	}
	psl->size = 0;
	psl->capacity = capacity;
}

2.2 判断是否需要扩容  

1. 判断有效个数是否和容量相等。

2. 使用realloc增容。

void CheckCapacity(SeqList* psl)
{
	assert(psl);

	if (psl->size == psl->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror(realloc);
			return;
		}
		psl->array = tmp;
		psl->capacity *= 2;
	}
}

2.3 顺序表指定位置插入

1. 对pos进行范围判断。

1. 判断是否需要扩容。

2. 将pos后面的元素往后挪一位。

3. pos位置插入值。

4. 有效个数加一。

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);

	CheckCapacity(psl);

	size_t cur = psl->size;
	while (cur != pos)
	{
		psl->array[cur] = psl->array[cur - 1];
		cur--;
	}

	psl->array[pos] = x;
	psl->size++;
}

2.4 顺序表头插

1. 判断是否需要扩容。

2. 将所有元素都往后移一位，留出第一个位置插入(如果头插之前没有元素，则直接插入即可)。

3. 有效个数加一。

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	CheckCapacity(psl);

	int tmp = psl->size;
	while (tmp > 0) //当本身为空时，就不走这个循环
	{
		psl->array[tmp] = psl->array[tmp - 1];
		tmp--;
	}

	psl->array[0] = x;
	psl->size++;
}

方法2：复用SeqListInsert

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	SeqListInsert(psl, 0, x);
}

2.5 顺序表尾插

1. 插入前判断是否需要增容。

2. size作为下标正好是最后一个元素的后一位。

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	CheckCapacity(psl);
	psl->array[psl->size++] = x;
}

方法2：复用SeqListInsert

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	SeqListInsert(psl, psl->size, x);
}

2.6 顺序表指定位置删除

1. 判断pos是否合法。

2. 将pos后面的元素往前覆盖一位。

3. 有效个数减一。

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	int cur = pos;
	while (cur < psl->size - 1)
	{
		psl->array[cur] = psl->array[cur + 1];
		cur++;
	}
	
	psl->size--;
}

2.7 顺序表头删

1. 判断有效个数是否为0，为0不用删。

2. 将后面的与元素往前覆盖一位。

3. 有效元素个数减一。

void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size);

	size_t cur = 0;
	while (cur < psl->size - 1)
	{
		psl->array[cur] = psl->array[cur + 1];
		cur++;
	}

	psl->size--;
}

方法2：复用SeqListErase

void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	SeqListErase(psl, 0);
}

2.8 顺序表尾删

1. 判断size，size如果为0就不能删。

2. 删除尾部元素直接将size减减即可。

void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size);

	psl->size--;
}

方法2：复用SeqListErase

void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	SeqListErase(psl, psl->size - 1);
}

2.9 顺序表查找

1. 遍历一遍进行比较。

2. 找到返回下标，否则返回-1。

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (size_t i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x) return i;
	}

	return -1;
}

2.10 顺序表修改 

1. 对pos进行范围判断。

2. 将pos作为下标进行修改。

void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	psl->array[pos] = x;
}

2.11 顺序表销毁

1. 销毁时需要释放空间，指针置空。

2. 有效个数和容量置0。

void SeqListDestory(SeqList* psl)
{
	assert(psl);

	free(psl->array);
	psl->array = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

2.12 顺序表打印

1. 遍历数组打印

void SeqListPrint(SeqList* psl)
{
    assert(psl);

	for (int i = 0; i < psl->size; i++) printf("%d ", psl->array[i]);
    printf("\n");
}

完整代码 

SeqList/SeqList · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

3. 顺序表的缺点

1. 中间/头部的插入删除，时间复杂度为O(N)。

2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

4. 顺序表编程练习题 

4.1 移除元素

链接：. - 力扣（LeetCode）

思路： 

1. src遍历判断，等于val就什么也不做，不等于val就把当前值给dst。

2. 等待src给我值，然后加加。

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

    return dst;        
}

4.2 删除有序数组中的重复项

链接：. - 力扣（LeetCode）

思路：利用双指针进行比较。

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

    return dst+1;
}

4.3 合并两个有序数组

链接：. - 力扣（LeetCode）

思路：

1. 从后面开始比较，谁大谁放在后面。

2. 注意结束条件，这里以tail为标准。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int src1 = m-1;
    int src2 = n-1;
    int tail = nums1Size-1;
    while(tail>=0)
    {
        if(src2<0) break;
        if(src1<0) nums1[tail] = nums2[src2--];
        else if(nums2[src2] >= nums1[src1]) nums1[tail] = nums2[src2--];
        else if(nums2[src2] < nums1[src1]) nums1[tail] = nums1[src1--];
        tail--;
    }
}

标签：练习题,顺序,线性表,psl,int,SeqList,array,size
From： https://blog.csdn.net/m0_71164215/article/details/140938115

相关文章

  • 顺序结构
    定义与特点定义顺序结构就是程序运行时自上而下的依次执行我们所写的代码，直到执行完所有语句。在C语言、Java等编程语言中，顺序结构都是程序设计的基础。特点线性执行：程序中的语句按照它们在代码中的顺序，从上到下依次执行。无跳转：在顺序结构中，不存在跳转到其他语句或模块执......
  • 线程执行顺序 join()
    importlombok.SneakyThrows;importjava.util.concurrent.TimeUnit;publicclassT{@SneakyThrowspublicstaticvoidmain(String[]args){Objecto=newObject();Threadthread1=newThread(()->{try{......
  • VJ练习题
    1E-OpeningCeremonyhttps://vjudge.net/contest/647025#problem/E当时想的太复杂没想到消掉最下面一层最优，因为相对层数不变。#include<stdio.h>#include<algorithm>usingnamespacestd;inta[100005];intmain(){intn;while(scanf("%d",&n)!=EOF)......
  • C语言-有n个整数，使前面各数顺序向后移m个位置，最后m个数变成最前面m个数，见 图8.43。写
    1.题目要求:有n个整数，使前面各数顺序向后移m个位置，最后m个数变成最前面m个数，见图8.43。写一函数实现以上功能，在主函数中输入n个整数和输出调整后的n个数。2.解题思路：可采用指针法，可将数组中最后一位元素的值赋给中间变量暂存，然后将剩余数组中的元素通过指针依次后移一位......
  • 图论练习题
    [NOIP2003]神经网络1.题意看懂以后就是计算一下每一个入度0的点最终的状态，并且如果这个状态>0就输出出来，对于阈值，我们可以在一开始就对这些入度的0的点直接减去阈值。2.然后就是一个拓扑排序的模型，因为我们要计算一个点的状态是需要这个点前面相连的所有点的状态而来，因此很容易......
  • 6-61 顺序表基本运算算法的实现
    线性表实验一实现顺序表各种基本运算的算法目的:领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。内容:编写程序，实现顺序表的各种基本运算算法(假设顺序表的元素类型ElemType为char)，并在此基础上设计一个主程序，完成如下功能:(1)初始化顺序表L。(2)依次插入a、b......
  • 数据结构 顺序队列（计数器版）
    在实现循环队列时，为了区分队列为空和队列满的情况，我们通常会浪费一个位置。也就是说，如果队列的总容量是100，那么实际上只能存储99个元素。这是因为我们需要保留一个位置来判断队列是满的还是空的。如果我们不这样做，那么在队列满和队列空时，front和rear指针都会指向同一个位置，......
  • DP练习题（二）
    [NOIP2008普及组]传球游戏上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：......
  • 实验8-1-8 报数：有n个人围成一圈，顺序排号。从第1个人开始报数(从1到3报数)，凡报到3的人
    一、题目要求：报数：有n个人围成一圈，顺序排号。从第1个人开始报数(从1到3报数)，凡报到3的人退出圈子，问最后留下的是原来第几号的那位。二、解题思想：解法：1.定义一个很大整形数组，以及一个当前要喊的数字变量(变化范围是1~3)2.给数组中非3位置进行赋值--赋值要喊的数字3.......
  • springboot 中控制bean 创建的先后顺序
    publicclassConfigTest{@PostConstructpublicvoidtestgfhd(){System.out.println("-111");}}publicclassVd{@PostConstructpublicvoidtestdgg(){System.out.println("22");}}@Configurationpublic......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99