本章重点

（1）线性表（2）顺序表

一线性表

线性表（ linear list ）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

二顺序表

顺序表的英文是sequence list

2.1 概念和结构

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

顺序表一般可以分为：（1）静态顺序表：使用定长数组存储元素。

1. //静态
2. #define N 100
3. //顺序表要求存储的数据从0开始，连续依次存储
4. struct SeqList
5. {
6.  int a[N];
7.  int size;//记录了存储多少个数据
8. };//当前结构体，是一个静态的顺序表，不是特别的实用
9. //出现的问题：会出现浪费空间或者空间不够用的情况

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

1. //动态的顺序表，更加的实用
2. typedef int SLDateType;
3. 
4. struct SeqList
5. {
6.  SLDateType* a;
7.  int size;//存储的个数
8.  int capacity;//存储空间大小
9. };

2.2 接口实现

实现动态顺序表

SeqList.h

1. #pragma once
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <assert.h>
5. 
6. 
7. //静态
8. //#define N 100
9. //顺序表要求存储的数据从0开始，连续依次存储
10. //struct SeqList
11. //{
12. //  int a[N];
13. //  int size;//记录了存储多少个数据
14. //};//当前结构体，是一个静态的顺序表，不是特别的实用
15. //出现的问题：会出现浪费空间或者空间不够用的情况
16. 
17. 
18. //动态的顺序表，更加的实用
19. typedef int SLDateType;
20. 
21. typedef struct SeqList
22. {
23.   SLDateType* a;
24.   int size;//存储的个数
25.   int capacity;//存储空间大小
26. }SeqList;
27. 
28. 
29. void SeqListCheckCapacity(SeqList* psl);//检查是否需要扩容
30. 
31. 
32. 
33. void SeqListPrint(SeqList* psl);//打印
34. 
35. void SeqListInit(SeqList* psl);//初始化
36. void SeqListDestroy(SeqList* psl);//销毁
37. 
38. void SeqListPushBack(SeqList* psl, SLDateType x);//尾插 不要命名为中文拼音
39. void SeqListPopBack(SeqList* psl);//尾删
40. void SeqListPushFront(SeqList* psl, SLDateType x);//头插
41. void SeqListPopFront(SeqList* psl);//头删
42. void SeqListInsert(SeqList* psl, size_t pos, SLDateType x);//下标为pos的位置插入
43. void SeqListErase(SeqList* psl, size_t pos); //下标为pos的位置删除
44. int SeqListFind(SeqList* psl, SLDateType x);//查找

SeqList.c

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "SeqList.h"
3. 
4. //代码重复的内容
5. //扩容
6. void SeqListCheckCapacity(SeqList* psl)
7. {
8.  assert(psl);
9.  if (psl->size == psl->capacity)
10.   {
11.     size_t newCapacity = psl->capacity == 0 ? 4 : (psl->capacity) * 2;//因为，我们初始化结构体的时候，容量初始化的值为0，当我们想要扩容的时候，同时容量也要增加
12.     SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//当容量的数值增加后，用realloc进行扩容
13.     if (tmp == NULL)
14.     {
15.       printf("realloc fail\n");
16.       exit(-1);
17.     }
18.     else
19.     {
20.       psl->a = tmp;
21.       psl->capacity = newCapacity;
22.     }
23.   }
24. }
25. 
26. 
27. 
28. //主代码
29. //打印数组
30. void SeqListPrint(SeqList* psl)
31. {
32.   assert(psl);
33.   for (int i = 0; i < psl->size; ++i)
34.   {
35.     printf("%d ", psl->a[i]);
36.   }
37.   printf("\n");
38. }
39. //初始化
40. void SeqListInit(SeqList* psl)
41. {
42.   assert(psl);
43.   psl->a = NULL;
44.   psl->size = 0;
45.   psl->capacity = 0;
46. }
47. //销毁
48. void SeqListDestroy(SeqList* psl)
49. {
50.   assert(psl);
51.   free(psl->a);
52.   psl->a = NULL;
53.   psl->size = 0;
54.   psl->capacity = 0;
55. }
56. //尾插，如果空间足够，直接添加
57. void SeqListPushBack(SeqList* psl, SLDateType x)
58. {
59.   //本来尾插的代码(1)
60.   //assert(psl);
61.   //SeqListCheckCapacity(psl);
62.   //psl->a[psl->size] = x;//把x这个数据放进去
63.   //psl->size++;
64.   //因为插入函数写过，就可以直接用插入函数(2)
65.   SeqListInsert(psl, psl->size, x);
66. }
67. //尾删
68. void SeqListPopBack(SeqList* psl)
69. {
70.   assert(psl);
71.   if (psl->size > 0)
72.   {
73.     psl->size--;
74.   }
75. }
76. //头插
77. void SeqListPushFront(SeqList* psl, SLDateType x)
78. {
79.   assert(psl);
80.   //注意，从前面插入，又要求连续，需要将整体向后平移一下。（正确的思路应该是从后向前，依次向后移一位）
81.   //如果，从前向后的话进行移位，会导致数据被覆盖
82.   SeqListCheckCapacity(psl);//扩容
83.   //开始插入数据
84.   int end = psl->size - 1;//这里不能写size_t,因为写成size_t，当size为0的时候，会导致end是一个非常大的数字，
85.   while (end >= 0)
86.   {
87.     psl->a[end + 1] = psl->a[end];
88.     --end;
89.   }
90.   psl->a[0] = x;
91.   psl->size++;
92. }
93. //头删
94. void SeqListPopFront(SeqList* psl)
95. {
96.   assert(psl);
97.   //要考虑size=0的情况，是不可以再次进行头删
98.   if (psl->size > 0)
99.   {
100.    int begin = 0;
101.    while (begin <= psl->size - 1)
102.    {
103.      psl->a[begin] = psl->a[begin + 1];
104.      ++begin;
105.    }
106.    --psl->size;
107.  }
108. }
109. // 下标为pos的位置插入
110. void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
111. {
112.  assert(psl);//暴力
113.  //下标为size这个位置也是可以的，相当于尾插//size_t不会小于0的
114.  if (pos > psl->size)
115.  {
116.    printf("pose越界:%d\n", pos);
117.    return;
118.  }
119.  SeqListCheckCapacity(psl);
120.  //这个是错误的代码，
121.  //size_t end = psl->size - 1;// end是size_t类型的，size为0的时候，在进行减一操作后，会变成一个很大的数字，所以就错了，
122.  // 改成int类型的话在while进行比较的时候，会发生整形提升，有符号的和无符号进行比较，会被提升为无符号的，所以还是while循环还是可以进去，达不到我们想要的效果，我们想要的效果是，进不去这个循环
123.  //while (end >= pos)
124.  //{
125.  //  psl->a[end + 1] = psl->a[end];
126.  //  end--;
127.  //}
128.  //psl->a[pos] = x;
129.  //++psl->size;
130.  //正确的代码，不让end涉及-1,
131.  size_t end = psl->size;
132.  while (end > pos)
133.  {
134.    psl->a[end] = psl->a[end - 1];
135.    end--;
136.  }
137.  psl->a[pos] = x;
138.  ++psl->size;
139. }
140. //下标为pos的位置删除
141. void SeqListErase(SeqList* psl, size_t pos)
142. {
143.  assert(psl);
144.  assert(pos < psl->size);
145.  size_t begin = pos + 1;
146.  while (begin < psl->size )
147.  {
148.    psl->a[begin - 1] = psl->a[begin];
149.    begin++;
150.  }
151.  psl->size--;
152. }
153. 
154. //查找
155. int SeqListFind(SeqList* psl, SLDateType x)
156. {
157.  assert(psl);
158.  for (int i = 0; i < psl->size; ++i)
159.  {
160.    if (psl->a[i] == x)
161.    {
162.      return i;
163.    }
164.  }
165.  return -1;
166. }

易错点：

1. void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
2. {
3.  assert(psl);//暴力
4.  //下标为size这个位置也是可以的，相当于尾插//size_t不会小于0的
5.  if (pos > psl->size)
6.  {
7.    printf("pose越界:%d\n", pos);
8.    return;
9.  }
10.   SeqListCheckCapacity(psl);
11.   //这个是错误的代码，
12.   //size_t end = psl->size - 1;// end是size_t类型的，size为0的时候，在进行减一操作后，会变成一个很大的数字，所以就错了，
13.   // 改成int类型的话在while进行比较的时候，会发生整形提升，有符号的和无符号进行比较，会被提升为无符号的，所以还是while循环还是可以进去，达不到我们想要的效果，我们想要的效果是，进不去这个循环
14.   //while (end >= pos)
15.   //{
16.   //  psl->a[end + 1] = psl->a[end];
17.   //  end--;
18.   //}
19.   //psl->a[pos] = x;
20.   //++psl->size;
21.   //正确的代码（1），不让end涉及-1,
22.   size_t end = psl->size;//如果，end是int类型的，那么在while进行比较的时候，会发生整形提升，有符号的和无符号
23.   while (end > pos)
24.   {
25.     psl->a[end] = psl->a[end - 1];
26.     end--;
27.   }
28.   psl->a[pos] = x;
29.   ++psl->size;
30. }

上述错误代码中的解决办法除了上面的代码还有（2）int end = ps->size - 1;while (end > (int)pose);这样写，就不会发生整形提升.

知识点：（1）结构体传参，形参是实参的临时拷贝，形参的改变，并不影响实参。同时结构体传参，如果传递的是形参，实参就无法改变。同时形参是实参的一份临时拷贝，所以，会浪费大量内存，所以结构体传参，应该传递的是结构体的地址。

（2）越界不一定能查出来，越界是抽查，有时候能检查出来，有时候检查不出来

（3）realloc（）两种扩容方式，一种原地扩容（效率高），一种异地扩容。

建议:(1) 写项目的时候，建议菜单最后写，方便测试。

（2）代码进行检查的时候，做到边写边测，进行边测，进行测试的时候，要多考虑特殊情况，数据初始的时候，数据的两级考虑。

2.3 数组相关面试题

1.移除数组（力扣）

原地移除数组中所有的元素 val ，要求时间复杂度为 O(N) ，空间复杂度为 O(1) 。

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

思路一：遍历整个数组，查找到每一个val，碰到val就把他覆盖掉（数组后面的元素向前挪动数据）【时间复杂度为O(N*N)，空间复杂度为O(1)】

思路二：把不是val的值拷贝到新的数组里（双指针（数组））【时间复杂度O(N),空间复杂度O(N)】【不符合题意】

思路三：双指针，但是不开辟新的数组

思路三代码：

1. int removeElement(int* nums, int numsSize, int val){
2. int src = 0;
3. int dst = 0;
4. while (src < numsSize)
5.     {
6. if (nums[src] != val)
7.         {
8.             nums[dst] = nums[src];
9.             src++;
10.             dst++;
11.         }
12. else
13.         {
14.             src++;
15.         }
16.     }
17. return dst;
18. }

2. 删除排序数组中的重复项。

给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

思路： (双指针)src从1开始，每次与前一个下表的内容进行比较，如果相同，dst不加一，src加一，如果不相同， src-1的值赋值给dst，并且src和dst分别加一（注意，src要与前一个下表的内容进行比较，所以src从1开始），最后的时候，把最后一个下标的值也赋值给dst。

1. int removeDuplicates(int* nums, int numsSize){
2. int src = 1;
3. int dst = 0;
4. while (src < numsSize)
5.     {
6. if (nums[src - 1] == nums[src])
7.         {
8.             src++;
9.         }
10. else
11.         {
12.             nums[dst] = nums[src - 1];
13.             src++;
14.             dst++;
15.         }
16.     }
17.     nums[dst] = nums[numsSize - 1];
18. return dst + 1;
19. }

3. 合并两个有序数组

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

代码展示：

1. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
2. int i = m - 1;
3. int j = n - 1;
4. int dst = m + n -1;
5. while (i >= 0 && j >= 0)
6.     {
7. if (nums1[i] > nums2[j])
8.         {
9.             nums1[dst--] = nums1[i--];
10.         }
11. else
12.         {
13.             nums1[dst--] = nums2[j--];
14.         }
15.     }
16. while (j >= 0)
17.     {
18.         nums1[dst--] = nums2[j--];
19.     }
20. }

思路一：（这个需要开额外数组）（归并）两个有序【无序的就把它变成有序的】数组，依次比较，每次把小的放到归并数组里，当有一个数组遍历完之后，就把另一个数组里剩下的元素放到归并数组里（使得归并数组里的元素也是有序的）【注意：非递减序列就说明数组是有序的】【不符合题意，因为用了一个新的数组】

思路二：【双指针】，因为num1是包括所有空间的，所以，可以倒着放【大的先放】，【这两个数组也倒序着进行比较】【这样就和思路一差不多一致】【符合题意】

2.4 顺序表的问题

优点：连续的空间，方便下标随机访问。

问题：

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

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

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

基于顺序表的缺点，就出现了链表。

顺序表知识点

本章重点

一线性表

二顺序表

2.1 概念和结构

2.2 接口实现

2.3 数组相关面试题

2.4 顺序表的问题

热门文章

最新文章

相关电子书

顺序表知识点

本章重点

一 线性表

二 顺序表

2.1 概念和结构

2.2 接口实现

2.3 数组相关面试题

2.4 顺序表的问题

热门文章

最新文章

相关电子书

一线性表

二顺序表