顺序表实现

1、顺序表概念及结构

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

顺序表一般可以分为

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

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

静态顺序表

动态顺序表

2、接口实现

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

数据结构是完成对顺序表的增删查改等接口函数的实现。

3、练习：移除元素 

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

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

2）元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例

输入：nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2

输出：5, nums = [0, 1, 4, 0, 3]

解释：函数应该返回新的长度5, 并且nums中的前五个元素为0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

思路：

1）src位置不是val，就放到dst位置。然后src++，dst++

2）src位置是val，src++

//函数实现

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++];

              }

              else

              {

                     ++src;

              }

       }

       return dst;

}

int main()

{

       int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };

       int val = 2;

       int size = 0;

       int i = 0;

       //时间复杂度O(N)，空间复杂度O(1)

       size = removeElement(nums, (sizeof(nums) / sizeof(nums[0])), val);

       for (i = 0; i < size; i++)

       {

              printf("%d ", nums[i]);

       }

       return 0;

}

4、练习：合并两个有序数组

练习：合并两个有序数组，给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。

示例

输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3

输出：[1, 2, 2, 3, 5, 6]

解释：需要合并[1, 2, 3] 和[2, 5, 6] 。

合并结果是[1, 2, 2, 3, 5, 6] ，其中斜体加粗标注的为nums1中的元素

思路：nums1和nums2都从后往前走，取大的从后往前放

void merge(int* nums1, int m, int* nums2, int n)

{

       int end1 = m - 1;//数组10个元素，下标是0-9，所以指向最后一个元素的下标是size-1

       int end2 = n - 1;//数组10个元素，下标是0-9，所以指向最后一个元素的下标是size-1

       int end = m + n - 1;//数组10个元素，下标是0-9，所以指向最后一个元素的下标是size-1

       while (end1 >= 0 && end2 >= 0)//有一个结束，就暂时结束了。用逻辑与

       {

              if (nums1[end1] > nums2[end2])

              {

                     nums1[end] = nums1[end1];

                     --end;

                     --end1;

              }

              else

              {

                     nums1[end] = nums2[end2];

                     --end;

                     --end2;

              }

       }

       //如果是end1没完，不需要处理。因为就是在nums1里面

       while (end2 >= 0)

       {

              nums1[end] = nums2[end2];

              --end;

              --end2;

       }

}

int main()

{

       int nums1[] = { 1, 2, 3, 0, 0, 0 };

       int nums2[] = { 2, 5, 6 };

       int i = 0;

       //时间复杂度O(M+N)，空间复杂度O(1)

       merge(nums1, 3, nums2, 3);

       for (i = 0; i < (sizeof(nums1) / sizeof(nums1[0])); i++)

       {

              printf("%d ", nums1[i]);

       }

       return 0;

}