【数据结构】-------顺序表

一、概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。（顺序表就是数组，但是在数组的基础上，它还要求数据从头开始存并且是连续存储的，不能跳跃间隔。）

二、顺序表一般可以分为： 静态顺序表、动态顺序表。

1. 静态顺序表：使用定长数组存储。

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

三、代码实现---动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多 了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下 面我们实现动态顺序表。

SeqList.h

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

typedef int SeqDatatype;//如果类型改变，方便修改
//动态顺序表
typedef struct SeqList {
    SeqDatatype* a;
    int size;        //表示数组中存储了多少个数据
    int capacity;    //数组实际能存数据的空间容量是多大
}SL;

//接口函数

void SeqListInit(SL* ps);
void SeqListPrint(SL*ps);

//检查是否增容
void SeqListCheckCapacity(SL* ps);
//在尾部插入
void SeqListPushBack(SL* ps, SeqDatatype* x);

//在尾部删除
void SeqListPopBack(SL* ps);

//在头部插入
void SeqListPushFront(SL* ps, SeqDatatype* x);

//在头部删除
void SeqListPopFront(SL* ps);

//找到了返回x位置下标，没有找到返回-1
int SeqListFind(SL* ps, SeqDatatype* x);

//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SeqDatatype* x);

//删除指定位置的数据（pos）
void SeqListErase(SL* ps, int pos);
void SeqListDestroy(SL* ps);

SeqList.c

#include"SeqList.h"
void SeqListInit(SL* ps)
{
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}
void SeqListDestroy(SL* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void SeqListPrint(SL* ps)
{
    for (int i = 0; i < ps->size; ++i)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}
void SeqListCheckCapacity(SL* ps)
{
    //如果没有空间或者空间不足，就扩容
    if (ps->size == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SeqDatatype* tmp = (SeqDatatype*)realloc(ps->a, newcapacity * sizeof(SeqDatatype));
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}
void SeqListPushBack(SL* ps, SeqDatatype* x)
{
    SeqListCheckCapacity(ps);
    ps->a[ps->size] = x;
    ps->size++;
    /*SeqListInsert(ps, ps->size, x);*/

}
void SeqListPopBack(SL* ps)
{
    assert(ps->size>0);
    ps->size--;
    /*SeqListErase(ps, ps->size-1);*/

}
void SeqListPushFront(SL* ps, SeqDatatype* 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, ps->size, x);*/
}
void SeqListPopFront(SL* ps)
{
    assert(ps->size > 0);
    
    //挪动数据
    int begin = 1;
    while (begin < ps->size)
    {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;

    }
    ps->size--;
    /*SeqListErase(ps, 0);*/
}
int SeqListFind(SL* ps, SeqDatatype* x)
{
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
            return i;
        
    }
    return -1;
}
void SeqListInsert(SL* ps, int pos, SeqDatatype* x)
{
    assert(pos >=0 && 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 >= 0 && pos < ps->size);
    int begin = pos+1;
    while (begin < ps->size)
    {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;

    }
    ps->size--;
}

四、顺序表的缺陷：

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

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

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

4.顺序表要求数据从开始位置连续存储，在头部或者中间位置插入删除数据就需要挪动数据，效率不高。

五、数组相关面试题

1、移除元素

移除元素https://leetcode.cn/problems/remove-element/

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

思路：双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组

慢指针：指向更新 新数组下标的位置

//时间复杂度 O(n)
int removeElement(int* nums, int numsSize, int val){

    // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < numsSize; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
}

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

删除有序数组中的重复项https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

思路：找到重复区间[i,j]，将重复区间的第一个值赋给dst,dst往后挪一个位置。注意：当循环结束的时候，还剩下最后一个位置的值没有挪动，需要在循环后将最后一个值赋给dst。最后返回的dst就是去重后数组的长度。

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

3、合并两个有序数组。

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

思路：归并思想，将两个数组从后往前进行比较，把较大的那个数放入第一个数组的最后（依此往前放），如果比较到最后第二个数组还剩下数据，则全部依此挪到第一个数组中。第一个数组就是合并好的数组。

//时间复杂度 O(m+n)
void merge(int* nums1, int m, int* nums2, int n){
    int end1=m-1;
    int end2=n-1;
    int end=m+n-1;
    while(end1>=0&&end2>=0)
     {
         if(nums1[end1]>nums2[end2])
         {
             nums1[end]=nums1[end1];
             --end1;
             --end;
         }
         else
         {
             nums1[end]=nums2[end2];
             --end2;
             --end;
         }
         
    }
    while(end2>=0)
    {
         nums1[end]=nums2[end2];
             --end2;
             --end;
    }
}