顺序表的介绍与简单运用

1：解释与结构

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

顺序表一般可分为一下几类

1.1 静态顺序表

概念：使用定长数组存储元素。注意：这种是连续存储数据，不能跳跃。

可以参考上面的图片。

1.2动态顺序表

概念：使用动态开辟的数组存储。可以进行增容.

2:接口实现

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

可以参考并写下相关代码来进一步了解接口的实现。

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

3：实际例题

3.1：

给你一个数组?nums?和一个值?val，你需要?原地?移除所有数值等于?val?的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用?O(1)?额外空间并?原地?修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。这是相关的例题链接。力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

int removeElement(int* nums, int numsSize, int val) {
   int size=0;
   for(int i=0;i<numsSize;i++)
   {
       if(nums[i]!=val)
       {
           nums[size]=nums[i];     这里相当于一个是快的i和一个慢的size,可以直接将不是val的数赋值 
                                       给size数组中，是val的数组直接跳过不传给size数组。
           size++;                                                  
       }
   }
    return size;
}

3.2：

给你一个?非严格递增排列?的数组?nums?，请你?原地?删除重复出现的元素，使每个元素?只出现一次?，返回删除后数组的新长度。元素的?相对顺序?应该保持?一致?。然后返回?nums?中唯一元素的个数。力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这一题与上一题同样是相同的思路。设置一个快数组和一个慢数组。
int removeDuplicates(int* nums, int numsSize) {
   if(numsSize==0)
   {
       return 0;               这里是防止数组元素为零。
   }
   int slow=1;
   int fast=1;
   for(fast=1;fast<numsSize;fast++)
   {
       if(nums[fast]!=nums[fast-1])
       {
           nums[slow]=nums[fast];
           slow++;
           
       }
   }
   return slow;
}

3.3：

给你两个按?非递减顺序?排列的整数数组?nums1?和?nums2，另有两个整数?m?和?n?，分别表示?nums1?和?nums2?中的元素数目。

请你?合并?nums2?到?nums1?中，使合并后的数组同样按?非递减顺序?排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组?nums1?中。为了应对这种情况，nums1?的初始长度为?m + n，其中前?m?个元素表示应合并的元素，后?n?个元素为?0?，应忽略。nums2?的长度为?n?。力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

int cmp(int*a,int*b)
{
   return *a-*b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
     for(int i=0;i<n;i++)
     {
         nums1[m+i]=nums2[i];

     }
     qsort(nums1,n+m,sizeof(int),cmp);
}
这里如果自己写函数是比较麻烦的，所以我们可以用C语言的库函数很简单的就解决了。