【数据结构】顺序表

逃离我推掉我的手 2024-04-01 13:02 13阅读 0赞

#### 文章目录 ####

*   *  顺序表
     *   *  概念及结构
         *  接口实现
         *  数组相关的面试题
         *   *  原地移除数组中的所有元素val
             *  删除排序数组中的重复项
             *  合并两个有序数组
             *  顺序表的问题和思考

### 顺序表 ###

#### 概念及结构 ####

> 顺序表是用一段**物理地址连续**的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
> 
> 顺序表一般可以分为：
> 
> 1.  **静态顺序表：使用定长数组存储单元**
>     
>     ![image-20221031200436218][]
> 2.  **动态顺序表：使用动态开辟的数组存储**
> 
> ![image-20221031200758371][]

#### 接口实现 ####

> 静态顺序表只适用于确定知道需要存多少个数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以实现中基本都是使用动态顺序表，根据需要动态的分配空间的大小，所以我们就用动态顺序表。
> 
>     typedef int SLDataType;
>     
>     //顺序表的动态存储
>     
>     typedef struct SeqList {
>         SLDataType* a;  //指向动态开辟的数组
>         int size;        //有效数据的个数
>         int capacity;    //容量空间的大小
>     }SeqList;

>     //顺序表初始化
>     void SeqListInit(SeqList* ps)
>     {
>         pa->a = NULL;
>         ps->size = 0;
>         ps->capacity = 0;
>     }
> 
>     //检查空间，如果满了，进行增容
>     void CheckCapacity(SeqList* ps)
>     {
>         if(ps->size == ps->capacity)
>         {
>             int newCapacity = ps->capacity = 0 ? 4 : ps->capacity * 2;
>             DataType* tmp = (DataType*)realloc(ps->a, newCapacity * sizeof(DataType));
>             if(tmp == NULL)
>             {
>                 perror("realloc fail");
>                 exit(-1);
>             }
>             ps->a = tmp;
>             ps->capacity = newCapacity;
>         }
>     }
> 
>     //顺序表尾插
>     void SeqListPushBack(SeqList* ps, DataType x)
>     {
>         //先判断是否需要增容
>         CheckCapacity(ps);
>         ps->[ps->size] = x;
>         ps->size++;
>     }
> 
>     //顺序表尾删
>     void SeqListPopBack(SeqList* ps)
>     {
>         if(ps->size == 0) //如果size是0了就结束，否则会变成-1，造成数组越界
>         {
>             return;
>         }
>         ps->size --;
>     }
> 
>     //顺序表头插
>     void SeqListPushFront(SeqList* ps, DataType x)
>     {
>         //先判断是否需要增容
>         CheckCapacity(ps);
>         //需要将如图所示的数字往后移动一位
>         int end = ps->size - 1;
>         while(end >= 0)
>         {
>             ps->a[end + 1] = ps->a[end];
>             end --;
>         }
>         ps->a[0] = x;
>         ps->size ++;
>     }
> 
> ![image-20221031205226594][]
> 
>     //顺序表头删
>     void SeqListPopFront(SeqList* ps)
>     {
>         if(ps->size < 0)
>         {
>             return;
>         }
>         //直接让1包含之后的数字都往前移动一位
>         int begin = 1;
>         while(begin < ps->size)
>         {
>             ps->a[begin - 1] = ps->a[begin];
>             begin ++;
>         }
>         ps->size --;
>     }
> 
> ![image-20221031205919230][]
> 
>     //顺序表查找
>     int SeqListFind(SeqList* ps, DataType x)
>     {
>         for(int i = 0; i < ps->size; i ++)
>         {
>             if(ps->a[i] == x)
>             {
>                 return i;
>             }
>         }
>         return -1;
>     }
> 
>     //顺序表在pos位置插入x
>     void SeqListInsert(SeqList* ps, int pos, DataType x)
>     {
>         //判断是否需要扩容
>         CheckCapacity(ps);
>         //pos代表的是下标， 需要将pos位置的值都往后移动一位
>         //从后往前移动
>         int end = ps->size - 1;
>         while(end >= pos)
>         {
>             ps->a[end + 1] = ps->a[end];
>             end --;
>         }
>         ps->a[pos] = x;
>         ps->size ++;
>     }
> 
>     // 顺序表删除pos位置的值
>     void SeqListErase(SeqList* ps, int pos)
>     {
>         //判断是否越界
>         if(ps->size < 0)
>         {
>             return;
>         }
>         //直接让pos之后的数字都往前移动一位
>         int begin = pos;
>         while(begin < ps->size)
>         {
>             ps->a[begin] = ps[begin + 1];
>             begin ++;
>         }
>         ps->size --;
>     }
> 
>     //顺序表的销毁
>     void SeqListDestory(SeqList* ps)
>     {
>         if(ps->a)
>         {
>             ps->a = NULL;
>             ps->size = ps-> capacity = 0;
>         }
>     }
> 
>     //顺序表的打印
>     void SeqListPrint(SeqList* ps)
>     {
>         for(int i = 0; i < ps->size; i ++)
>         {
>             printf("%d ", ps->a[i]);
>         }
>     }

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

##### [原地移除数组中的所有元素val][val] #####

> ![image-20221031214120650][]
> 
> 思路：
> 
> 设置两个指针，如果src不等于val则直接赋值给dest所在位置的下标，然后两个指针都加加，如果相等就只让src加加就可以
> 
> 代码：
> 
>     int removeElement(int* nums, int numsSize, int val){
>          
>         int src = 0;
>         int dest = 0;
>         while(src < numsSize)
>         {
>          
>             if(nums[src] == val)
>             {
>          
>                 src ++;
>             }
>             else 
>             {
>          
>                 nums[dest] = nums[src];
>                 dest ++;
>                 src ++;
>             }
>         }
>         return dest;
>     }

##### [删除排序数组中的重复项][Link 1] #####

> 代码：
> 
>     int removeDuplicates(int* nums, int numsSize){
>          
>         int src = 1;
>         int dest = 0;
>         while(src < numsSize) 
>         {
>          
>             if(nums[src] == nums[dest])
>             {
>          
>                 src ++;
>             }
>             else
>             {
>          
>                 dest ++;
>                 nums[dest] = nums[src];
>                 src ++;
>             }
>         }
>         return dest + 1;
>     }
> 
> ![image-20221101162051549][]

##### [合并两个有序数组][Link 2] #####

> ![image-20221103122930266][]
> 
> 思路：
> 
> 从后面往前面开始一个个比较，如果大的就放到最后一个。
> 
> 代码：
> 
>     void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
>          
>        int i1 = m - 1;
>        int i2 = n - 1;
>        int j = m + n - 1;
>        while(i1 >= 0 && i2 >= 0)
>        {
>          
>            if(nums1[i1] > nums2[i2])
>            {
>          
>                nums1[j --] = nums1[i1 --];
>            }
>            else 
>            {
>          
>                nums1[j --] = nums2[i2 --];
>            }
>        }
>        while(i2 >= 0)
>        {
>          
>            nums1[j --] = nums2[i2 --];
>        }
>     }

##### 顺序表的问题和思考 #####

> 问题：
> 
> 1.  中间/头部的插入删除，时间复杂度为O(N)
> 2.  增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
> 3.  增容一般是呈2倍的增长，势必会有一定的空间浪费，例如当前容量为100，满了以后增容到200，我们继续插入了5个数据，后面没有数据插入了，那么就浪费了95个空间。
> 
> 思考：
> 
> 如何解决以上问题？下面我们看看链表的结构

[image-20221031200436218]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/78011045cd54467bbff1aefc24b8879d.png
[image-20221031200758371]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b46b0a23fedb448ba9b3f02a6b99dd0b.png
[image-20221031205226594]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1f5ffde6021b4c7b9b73f0ca3fe3810f.png
[image-20221031205919230]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a517060072d049639533dc2d8f1b388b.png
[val]: https://leetcode.cn/problems/remove-element/
[image-20221031214120650]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b35dbd067638463c96ea04a783991c05.png
[Link 1]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[image-20221101162051549]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/722ef76d30bf4a75a8cb7c3f72dceea4.png
[Link 2]: https://leetcode.cn/problems/merge-sorted-array/
[image-20221103122930266]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5908a4386ed1424ba1c34056292d2926.png