【数据结构】顺序表的实现

一、线性表

线性表是n个具有相同特性的数据元素的有限序列。

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

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

二、顺序表的简介

1、顺序表的概念

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

2、顺序表的优点

1、随机访问时间复杂度O(1)

2、不用像链表那样，需要额外开辟空间存放指针

3、顺序表的缺点

1、空间不够，需要扩容，扩容可能需要重新申请一块新的空间，拷贝原始数据，释放旧空间。

2、一般是2倍扩容，一次扩容太多造成空间浪费，扩容太少可能导致空间不足，扩容频繁。2倍比较合适。但是仍存在空间浪费。

3、中间/头部插入删除需要挪动数据，时间复杂度O(N)

三、传值和传址的理解

1、顺序表中传入的实参是结构体变量，形参是实参的临时拷贝，在拷贝中更改不会影响传入的实参。顺序表中打印函数不会改变实参中的内容，可传值也可传址，但是传值存在拷贝过程，有较大的消耗，所以这个函数也建议传址。

2、链表中传入的实参是结构体头指针，当使用头插头删等接口时，需要改变头指针，所以要传入二级指针。但是修改头指针指向的next指针或者date值时，传值也行。

四、SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
    SLDateType* arr;//动态开辟的数组
    int size;//当前存放的数据个数
    int capacity;//有效容量
}SL;

void SLInit(SL* psl);//初始化
void SLDestory(SL* psl);//销毁
void SLPrint(SL* psl);//打印
void SLExpend(SL* psl);//判断扩容
void SLPushBack(SL* psl, SLDateType x);//尾插
void SLPopBack(SL* psl);//尾删
void SLPushFront(SL* psl, SLDateType x);//头插
void SLPopFront(SL* psl);//头删
int SLFind(SL* psl,SLDateType x);//查找
void SLInsert(SL* psl, size_t pos, SLDateType x);//在pos位置插入x
void SLErase(SL* psl, size_t pos);//在pos位置删除x
void SLModify(SL* psl, size_t pos, SLDateType x);//修改

五、SeqList.c

1、顺序表的初始化

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

初始化中，这里arr数组初始化为NULL。（也可以根据个人喜好为arr数组在堆区动态开辟几个空间）

2、顺序表的销毁

void SLDestory(SL* psl)//销毁
{
    assert(psl);
    free(psl->arr);
    psl->arr = NULL;
    psl->capacity = psl->size = 0;
}

把动态开辟的arr数组free并置空，size和capacity置为0

3、顺序表的打印

void SLPrint(SL* psl)//打印
{
    assert(psl);
    for (int i = 0; i < psl->size; i++)
    {
        printf("%d ", psl->arr[i]);
    }
}

4、判断是否需要扩容

void SLExpend(SL* psl)//判断扩容
{
    //检查容量capacity，判断是否需要扩容
    if (psl->size == psl->capacity)
    {
        int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        //psl->capacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        //使用newCapacity而不是直接用capacity作用是防止后续空间扩容失败
        //当然后续失败了也直接exit结束程序了
        SLDateType* tmp = (SLDateType*)realloc(psl->arr, sizeof(SLDateType) * newCapacity);
        if (tmp == NULL)
        {
            perror("realloc fail!\n");
            exit(-1);
        }
        psl->arr = tmp;
        psl->capacity = newCapacity;
    }
}

因为初始化时arr没有给空间，这里检查扩容时给初始空间。

注意用newCapacity和tmp先接收新容量和新空间，防止后续空间动态开辟失败（那么就会有人问了，后面realloc失败不是直接exit了吗，为什么还要用newCapacity暂时存放新的容量，而不是直接用psl->capacity = psl->capacity == 0 ? 4 : psl->capacity * 2?是因为如果有人后边是用温柔的检查，直接return，那么这样写会导致capacity不准确）

5、顺序表的尾插、尾删

void SLPushBack(SL* psl,SLDateType x)//尾插
{
    assert(psl);
    SLExpend(psl);//检查扩容
    psl->arr[psl->size] = x;
    psl->size++;
}
void SLPopBack(SL* psl)//尾删
{
    assert(psl);
    assert(psl->size > 0);
    psl->size--;
}

因为size是顺序表能访问的数据个数，尾删直接size--就行。不用担心那个删除的元素的值还放在那里，因为size--后，顺序表根本访问不到那个数据了。

6、顺序表的头插、头删

void SLPushFront(SL* psl, SLDateType x)//头插
{
    assert(psl);
    SLExpend(psl);//判断扩容
    //int end = psl->size==0?0:psl->size-1;//当时怕size等于0，导致end等于-1，其实end等于-1不会进循环
    int end = psl->size-1;//end是数组最后一个元素的下标
    while (end>=0)
    {
        psl->arr[end + 1] = psl->arr[end];
        end--;
    }
    psl->arr[0] = x;
    psl->size++;
}
void SLPopFront(SL* psl)//头删
{
    assert(psl);
    assert(psl->size > 0);
    for (int i = 0; i < psl->size-1; i++)
    {
        psl->arr[i] = psl->arr[i + 1];
    }
    psl->size--;
}

头插复杂一点，需要从最后一个元素开始往后边挪动数据。

头删迭代覆盖即可。

7、顺序表的查找

int SLFind(SL* psl, SLDateType x)//查找
{
    assert(psl);
    for (int i = 0; i < psl->size; i++)
    {
        if (psl->arr[i] == x)
        {
            return i;
            break;
        }
    }
    return -1;
}

返回下标

8、在下标pos位置插入删除

//注意，这里的形参用的size_t
void SLInsert(SL* psl, size_t pos, SLDateType x)//在pos位置插入x
{
    assert(psl);
    assert(pos <= psl->size);//pos是size_t类型>=0
    SLExpend(psl);//判断扩容
    size_t end = psl->size;//end要等于psl->size
    for (int i = 0; i < psl->size - pos; i++)
    {
        psl->arr[end] = psl->arr[end - 1];
        end--;
    }
    psl->arr[pos] = x;
    psl->size++;
}
void SLErase(SL* psl, size_t pos)//在pos位置删除x
{
    assert(psl);
    assert(pos < psl->size);//这个断言顺便检查了size<=0的情况（删空了还在删）
    size_t begin = pos;
    while (begin < psl->size-1)//这里一定要size-1，不要做越界覆盖
    {
        psl->arr[begin] = psl->arr[begin + 1];
        ++begin;
    }
    --psl->size;
}

9、顺序表的修改

void SLModify(SL* psl, size_t pos, SLDateType x)//修改
{
    assert(psl);
    assert(pos < psl->size);
    psl->arr[pos] = x;
}

六、力扣oj

1、移除元素

int removeElement(int* nums, int numsSize, int val){
    int fast=0;
    int slow=0;
    while(fast<numsSize)
    {
        if(nums[fast]!=val)//当“快指针”指向的值不等于val时，
        {
            nums[slow++]=nums[fast++];//把“快指针”指向的值给“慢指针”
        }
        else
        {
            fast++;
        }
    }
    return slow;
}

思路：当“快指针”指向的值不等于val时，把“快指针”指向的值给“慢指针”，反之，快++，慢不动

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

int removeDuplicates(int* nums, int numsSize){
    int fast=0;
    int slow=0;
    while(fast<numsSize)
    {
        if(nums[fast]==nums[slow])//如果快指针指向的数值和slow指向的相等，fast++
        {
            fast++;
        }
        else//反之，slow先++，再拷贝fast指向的值到slow
        {
            slow++;
            nums[slow]=nums[fast];
            fast++;
        }
    }
    return slow+1;
}

3、合并两个有序数组

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int end1=m-1;
    int end2=n-1;
    int i=m+n-1;
    //从数组nums1的末尾开始覆盖
    while(end1>=0&&end2>=0)
    {
        if(nums2[end2]>=nums1[end1])
        {
            nums1[i]=nums2[end2];
            --end2;
            --i;
        }
        else
        {
            nums1[i]=nums1[end1];
            --end1;
            --i;
        }
    }
    while(end2>=0)//处理一下end2没放完的情况
    {
        nums1[i]=nums2[end2];
        --end2;
        --i;
    }
}

从num1的末尾开始覆盖，最后处理一下nums2没放完的情况