顺序表知识点

深碍√TFBOYSˉ_ 2023-10-12 10:23 59阅读 0赞

**目录**

本章重点

一 线性表

二 顺序表

2.1 概念和结构

2.2 接口实现

2.3 数组相关面试题

2.4 顺序表的问题

--------------------

行动是打败焦虑最好的方法

--------------------

## 本章重点 ##

（1）线性表（2）顺序表

--------------------

## 一 线性表 ##

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

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

## 二 顺序表 ##

顺序表的英文是sequence list

### 2.1 概念和结构 ###

顺序表是用一段 **物理地址连续** 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。（顺序表就是数组，只是增加了一些要求）

顺序表一般可以分为：（1）**静态顺序表：使用定长数组存储元素** 。

//静态
    #define N 100
    //顺序表要求存储的数据从0开始，连续依次存储
    struct SeqList
    {
    	int a[N];
    	int size;//记录了存储多少个数据
    };//当前结构体，是一个静态的顺序表，不是特别的实用
    //出现的问题：会出现浪费空间或者空间不够用的情况

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

//动态的顺序表，更加的实用
    typedef int SLDateType;
    
    struct SeqList
    {
    	SLDateType* a;
    	int size;//存储的个数
    	int capacity;//存储空间大小
    };

### 2.2 接口实现 ###

实现动态顺序表

**SeqList.h**

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    
    //静态
    //#define N 100
    //顺序表要求存储的数据从0开始，连续依次存储
    //struct SeqList
    //{
    //	int a[N];
    //	int size;//记录了存储多少个数据
    //};//当前结构体，是一个静态的顺序表，不是特别的实用
    //出现的问题：会出现浪费空间或者空间不够用的情况
    
    
    //动态的顺序表，更加的实用
    typedef int SLDateType;
    
    typedef struct SeqList
    {
    	SLDateType* a;
    	int size;//存储的个数
    	int capacity;//存储空间大小
    }SeqList;
    
    
    void SeqListCheckCapacity(SeqList* psl);//检查是否需要扩容
    
    
    
    void SeqListPrint(SeqList* psl);//打印
    
    void SeqListInit(SeqList* psl);//初始化
    void SeqListDestroy(SeqList* psl);//销毁
    
    void SeqListPushBack(SeqList* psl, SLDateType x);//尾插 不要命名为中文拼音
    void SeqListPopBack(SeqList* psl);//尾删
    void SeqListPushFront(SeqList* psl, SLDateType x);//头插
    void SeqListPopFront(SeqList* psl);//头删
    void SeqListInsert(SeqList* psl, size_t pos, SLDateType x);//下标为pos的位置插入
    void SeqListErase(SeqList* psl, size_t pos); //下标为pos的位置删除
    int SeqListFind(SeqList* psl, SLDateType x);//查找

**SeqList.c**

#define _CRT_SECURE_NO_WARNINGS 1
    #include "SeqList.h"
    
    //代码重复的内容
    //扩容
    void SeqListCheckCapacity(SeqList* psl)
    {
    	assert(psl);
    	if (psl->size == psl->capacity)
    	{
    		size_t newCapacity = psl->capacity == 0 ? 4 : (psl->capacity) * 2;//因为，我们初始化结构体的时候，容量初始化的值为0，当我们想要扩容的时候，同时容量也要增加
    		SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//当容量的数值增加后，用realloc进行扩容
    		if (tmp == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    		else
    		{
    			psl->a = tmp;
    			psl->capacity = newCapacity;
    		}
    	}
    }
    
    
    
    //主代码
    //打印数组
    void SeqListPrint(SeqList* psl)
    {
    	assert(psl);
    	for (int i = 0; i < psl->size; ++i)
    	{
    		printf("%d ", psl->a[i]);
    	}
    	printf("\n");
    }
    //初始化
    void SeqListInit(SeqList* psl)
    {
    	assert(psl);
    	psl->a = NULL;
    	psl->size = 0;
    	psl->capacity = 0;
    }
    //销毁
    void SeqListDestroy(SeqList* psl)
    {
    	assert(psl);
    	free(psl->a);
    	psl->a = NULL;
    	psl->size = 0;
    	psl->capacity = 0;
    }
    //尾插，如果空间足够，直接添加
    void SeqListPushBack(SeqList* psl, SLDateType x)
    {
    	//本来尾插的代码(1)
    	//assert(psl);
    	//SeqListCheckCapacity(psl);
    	//psl->a[psl->size] = x;//把x这个数据放进去
    	//psl->size++;
    	//因为插入函数写过，就可以直接用插入函数(2)
    	SeqListInsert(psl, psl->size, x);
    }
    //尾删
    void SeqListPopBack(SeqList* psl)
    {
    	assert(psl);
    	if (psl->size > 0)
    	{
    		psl->size--;
    	}
    }
    //头插
    void SeqListPushFront(SeqList* psl, SLDateType x)
    {
    	assert(psl);
    	//注意，从前面插入，又要求连续，需要将整体向后平移一下。（正确的思路应该是从后向前，依次向后移一位）
    	//如果，从前向后的话进行移位，会导致数据被覆盖
    	SeqListCheckCapacity(psl);//扩容
    	//开始插入数据
    	int end = psl->size - 1;//这里不能写size_t,因为写成size_t，当size为0的时候，会导致end是一个非常大的数字，
    	while (end >= 0)
    	{
    		psl->a[end + 1] = psl->a[end];
    		--end;
    	}
    	psl->a[0] = x;
    	psl->size++;
    }
    //头删
    void SeqListPopFront(SeqList* psl)
    {
    	assert(psl);
    	//要考虑size=0的情况，是不可以再次进行头删
    	if (psl->size > 0)
    	{
    		int begin = 0;
    		while (begin <= psl->size - 1)
    		{
    			psl->a[begin] = psl->a[begin + 1];
    			++begin;
    		}
    		--psl->size;
    	}
    }
    // 下标为pos的位置插入
    void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
    {
    	assert(psl);//暴力
    	//下标为size这个位置也是可以的，相当于尾插//size_t不会小于0的
    	if (pos > psl->size)
    	{
    		printf("pose越界:%d\n", pos);
    		return;
    	}
    	SeqListCheckCapacity(psl);
    	//这个是错误的代码，
    	//size_t end = psl->size - 1;// end是size_t类型的，size为0的时候，在进行减一操作后，会变成一个很大的数字，所以就错了，
    	// 改成int类型的话在while进行比较的时候，会发生整形提升，有符号的和无符号进行比较，会被提升为无符号的，所以还是while循环还是可以进去，达不到我们想要的效果，我们想要的效果是，进不去这个循环
    	//while (end >= pos)
    	//{
    	//	psl->a[end + 1] = psl->a[end];
    	//	end--;
    	//}
    	//psl->a[pos] = x;
    	//++psl->size;
    	//正确的代码，不让end涉及-1,
    	size_t end = psl->size;
    	while (end > pos)
    	{
    		psl->a[end] = psl->a[end - 1];
    		end--;
    	}
    	psl->a[pos] = x;
    	++psl->size;
    }
    //下标为pos的位置删除
    void SeqListErase(SeqList* psl, size_t pos)
    {
    	assert(psl);
    	assert(pos < psl->size);
    	size_t begin = pos + 1;
    	while (begin < psl->size )
    	{
    		psl->a[begin - 1] = psl->a[begin];
    		begin++;
    	}
    	psl->size--;
    }
    
    //查找
    int SeqListFind(SeqList* psl, SLDateType x)
    {
    	assert(psl);
    	for (int i = 0; i < psl->size; ++i)
    	{
    		if (psl->a[i] == x)
    		{
    			return i;
    		}
    	}
    	return -1;
    }

**易错点：**

void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
    {
    	assert(psl);//暴力
    	//下标为size这个位置也是可以的，相当于尾插//size_t不会小于0的
    	if (pos > psl->size)
    	{
    		printf("pose越界:%d\n", pos);
    		return;
    	}
    	SeqListCheckCapacity(psl);
    	//这个是错误的代码，
    	//size_t end = psl->size - 1;// end是size_t类型的，size为0的时候，在进行减一操作后，会变成一个很大的数字，所以就错了，
    	// 改成int类型的话在while进行比较的时候，会发生整形提升，有符号的和无符号进行比较，会被提升为无符号的，所以还是while循环还是可以进去，达不到我们想要的效果，我们想要的效果是，进不去这个循环
    	//while (end >= pos)
    	//{
    	//	psl->a[end + 1] = psl->a[end];
    	//	end--;
    	//}
    	//psl->a[pos] = x;
    	//++psl->size;
    	//正确的代码（1），不让end涉及-1,
    	size_t end = psl->size;//如果，end是int类型的，那么在while进行比较的时候，会发生整形提升，有符号的和无符号
    	while (end > pos)
    	{
    		psl->a[end] = psl->a[end - 1];
    		end--;
    	}
    	psl->a[pos] = x;
    	++psl->size;
    }

上述错误代码中的解决办法除了上面的代码还有（2）int end = ps->size - 1;while (end > (int)pose);这样写，就不会发生整形提升.

> 知识点：（1）结构体传参，形参是实参的临时拷贝，形参的改变，并不影响实参。同时结构体传参，如果传递的是形参，实参就无法改变。同时形参是实参的一份临时拷贝，所以，会浪费大量内存，所以结构体传参，应该传递的是结构体的地址。
> 
> （2）越界不一定能查出来，越界是抽查，有时候能检查出来，有时候检查不出来
> 
> （3）realloc（）两种扩容方式，一种原地扩容（效率高），一种异地扩容。

> 建议:(1) 写项目的时候，建议菜单最后写，方便测试。
> 
> （2）代码进行检查的时候，做到边写边测，进行边测，进行测试的时候，要多考虑特殊情况，数据初始的时候 ，数据的两级考虑。

### 2.3 数组相关面试题 ###

**1.移除数组（力扣）**

原地移除数组中所有的元素 val ，要求时间复杂度为 O(N) ，空间复杂度为 O(1) 。

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

**思路一**： 遍历整个数组，查找到每一个val，碰到val就把他覆盖掉（数组后面的元素向前挪动数据）【时间复杂度为O(N\*N)，空间复杂度为O(1)】

**思路二**：把不是val的值拷贝到新的数组里（双指针（数组））【时间复杂度O(N),空间复杂度O(N)】【不符合题意】

**思路三**：双指针，但是不开辟新的数组

思路三代码：

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

**2. 删除排序数组中的重复项。**

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

**思路**： (双指针)src从1开始，每次与前一个下表的内容进行比较，如果相同，dst不加一，src加一，如果不相同， **src-1的值赋值给dst**，并且src和dst分别加一（注意，src要与前一个下表的内容进行比较，所以src从1开始），最后的时候，把 **最后一个下标**的值也赋值给dst。

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

**3. 合并两个有序数组**

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。**注意**：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

**代码展示：**

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

> 思路一：（这个需要开额外数组）（归并）两个有序【无序的就把它变成有序的】数组，依次比较，每次把小的放到归并数组里，当有一个数组遍历完之后，就把另一个数组里剩下的元素放到归并数组里（使得归并数组里的元素也是有序的）【注意：非递减序列就说明数组是有序的】【不符合题意，因为用了一个新的数组】
> 
> 思路二：【双指针】，因为num1是包括所有空间的，所以，可以倒着放【大的先放】，【这两个数组也倒序着进行比较】【这样就和思路一差不多一致】【符合题意】

### 2.4 顺序表的问题 ###

优点：连续的空间，方便下标随机访问。

问题：

1.  中间 / 头部的插入删除，时间复杂度为 O(N)，效率比较低

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

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

基于顺序表的缺点，就出现了链表。