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

数据结构(C\C++)——顺序表

article 2025/3/25 13:25:14

前言

本文介绍顺序表相关知识点及三道leetcode练习题

顺序表

- 前言
- 正文
- 1. 线性表
- 2. 顺序表
- - 2.1 概念与结构
  - 2.2 分类
  - 2.3 动态顺序表的实现
  - 2.4 顺序表算法题
  - - 2.4.1移除元素：
    - 2.4.2 删除有序数组中的重复项：
    - 2.4.3 合并两个有序数组：
  - 2.5 顺序表问题与思考
- 总结

正文

1. 线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。它是一种在实际中广泛使用的数据结构，常见的线性表有顺序表、链表、栈、队列、字符串等。

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

2. 顺序表

2.1 概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

顺序表的底层结构是数组，是对数组的封装，实现了常用的增删改查等接口。

2.2 分类

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

//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct seqList
{
    SLDataType a[N];//定长数组
    int size; //有效数据个数
}SL;

静态顺序表存在缺陷，空间给少了不够用，给多了造成空间浪费。

动态顺序表：按需申请空间。

//动态顺序表--按需申请
typedef struct SeqList
{
    SLDataType* a;
    int size; //有效数据个数
    int capacity;//空间容量
}SL;

2.3 动态顺序表的实现

本文采用多文件结构，包含初始化、销毁、扩容、插入删除、查找等函数声明。
后续会有一个通讯录代码采用单文件结构示例
SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;      //有效数据个数
	int capacity;  //空间容量
}SL;

//typedef struct SeqList SL;

void SLPrint(SL* ps);
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);

//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);

//指定位置之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 删除POS位置的数据
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//增容
		//realloc第二个参数，单位是字节
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//空间足够的情况下
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	//温柔的处理方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	assert(ps != NULL);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//将顺序表中所有数据向后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	++ps->size;
}

//尾删
void SLPopBack(SL* ps)
{
	//ps：限制参数不能直接给NULL
	//ps->size：顺序表为空
	assert(ps && ps->size);
	--ps->size;
}

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}

//指定位置之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);
	//pos及之后的数据整体向后挪动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
}
// 删除POS位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//pos之后的数据整体向前挪动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//未找到
	return -1;
}
//销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

test.c

#include"SeqList.h"
//根据需求取消注释即可
void test01()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);
	//SLPushBack(&sl, 5);
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);//4 3 2 1
	//SLPushFront(NULL, 1);
	//
	//SLPopBack(&sl);
	//SLPrint(&sl);
	//SLPopBack(&sl);
	//SLPrint(&sl);
	//SLPopBack(&sl);
	//SLPrint(&sl);
	//SLPopBack(&sl);
	//SLPrint(&sl);
	//SLPopBack(&sl);
//
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);
//
	//SLInsert(&sl, 4, 100);
	//SLPrint(&sl);

	//SLErase(&sl, 3);
	//SLPrint(&sl);
	//int find = SLFind(&sl, 22222);
	//printf("%d",find)
	//SLDestroy(&sl);
}

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

2.4 顺序表算法题

前两道题目都运用了双指针法，第三道是一道经典例题，希望可以仔细琢磨
相关题目可在LeetCode上练习：

2.4.1移除元素：

https://leetcode.cn/problems/remove-element/description/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int L1 = m - 1;
    int L2 = n - 1;
    int L3 = m + n - 1;

    while (L1 >= 0 && L2 >= 0)
    {
        if (nums1[L1] >= nums2[L2])
        {
            nums1[L3--] = nums1[L1--];

        }
        else
        {
            nums1[L3--] = nums2[L2--];

        }

    }
    while (L2 >= 0)
    {
        nums1[L3--] = nums2[L2--];
    }
}

2.4.2 删除有序数组中的重复项：

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

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];
            dst++;
        }
        src++;
    }
    return dst;
}

2.4.3 合并两个有序数组：

https://leetcode.cn/problems/merge-sorted-array/description/
在这里插入图片描述

int removeDuplicates(int* nums, int numsSize)

{
	int dst = 0;
	int src = dst + 1;

	while (src < numsSize)
	{
		if (nums[src] != nums[dst] && ++dst != src)
		{
			nums[dst] = nums[src];
		}

		++src;

	}

	return dst + 1;

}