【编织时空一：探究顺序表与链表的数据之旅】

本章重点

1. 线性表

2. 顺序表

3. 顺序表OJ题

1.线性表

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

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

2.顺序表

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表中的元素在内存中是相邻存储的，每个元素都有一个对应的索引来标识其在顺序表中的位置。顺序表支持随机访问，可以通过索引直接访问任意位置的元素。

        顺序表一般可以分为：

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

 静态顺序表的缺点：

1. 固定大小： 静态顺序表的大小在创建时被固定下来，无法动态地扩展或缩小。这意味着一旦初始化了静态顺序表，其容量就无法改变。如果需要存储的元素数量超过初始分配的容量，可能需要重新分配更大的空间并手动进行数据迁移。

2. 内存浪费： 如果静态顺序表的容量设置过大，但实际存储的元素数量较少，会导致内存浪费。因为未使用的部分空间也会被保留，占用了额外的内存。

3. 不灵活： 由于容量固定，静态顺序表可能无法适应动态变化的数据需求。当需要的容量超过初始设置时，可能需要重新设计或重写代码。

4. 初始化成本： 静态顺序表在初始化时需要分配固定大小的内存空间，而如果无法预估元素的最终数量，就需要进行适当的空间规划，这可能增加设计和开发的成本。

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

3.顺序表接口实现 

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* a;  // 指向动态开辟的数组int size;       // 有效数据个数int capicity;   // 容量空间的大小
}SeqList;// 基本增删查改接口
// 
// 顺序表初始化
void SeqListInit(SeqList * s);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* s);
// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* s);
// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* s);
// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* s);
// 顺序表打印
void SeqListPrint(SeqList* s);

顺序表初始化：void SeqListInit(SeqList * s);

        代码中存在一些问题，主要是关于C语言中函数参数传递方式的错误理解。C语言中的参数传递是值传递，意味着函数接收的是参数的副本，而不是原始的数据。因此，当你在 SeqListInit 函数中修改 s 的值时，实际上只是修改了传递进来的副本，而不会影响原始的 s。为了解决这个问题，需要通过指针传递来修改原始数据。

// 顺序表初始化
void SeqListInit(SeqList* s)
{s->a = NULL;s->size = 0;s->capicity = 0;
}

但是，我们需要在初始的时候就开辟一些空间，这样更方便数据存储，不用一上来就扩容。

// 顺序表初始化
void SeqListInit(SeqList* s)
{s->a = (SeqList*)malloc(sizeof(SLDataType) * 4);if (s->a == NULL){perror("malloc");//return;只是该函数退出，程序依然运行exit(-1);//程序退出为-1}s->size = 0;s->capicity = 4;
}

        malloc函数：malloc函数的返回值是void *，使用malloc函数要在返回的时候转化为我们需要的类型。malloc(sizeof(SLDataType) * 4)这代表的是申请了4个SLDataType类型大小的空间。        

        malloc函数的使用要引头文件#include<stdlib.h>。
        分配成功则返回指向被分配内存的指针，分配失败则返回空指针NULL。

检查空间，如果满了，进行增容：void CheckCapacity(SeqList* s);

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* s)
{//满了需要扩容if (s->size == s->capicity){//realloc,第二个参数是新空间的大小，不是要扩多少SLDataType* temp = (SLDataType*)realloc(s->a, s->capicity * 2 * sizeof(SLDataType));//扩容2倍if (temp == NULL){perror("realloc");exit(-1);}s->a = temp;s->capicity *= 2;}
}

        realloc函数：realloc函数的返回值是void *，使用realloc函数要在返回的时候转化为我们需要的类型。realloc(s->a, s->capicity * 2 * sizeof(SLDataType))这代表的是申请了s->capicity * 2 个SLDataTypet型大小的空间。 我这里是扩充2倍空间。同时realloc函数,第二个参数是新空间的大小，不是要扩多少 。    

        realloc函数的使用要引头文件#include<stdlib.h>。
        分配成功则返回指向被分配内存的指针，分配失败则返回空指针NULL。

顺序表尾插：void SeqListPushBack(SeqList* s, SLDataType x);

// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x)
{CheckCapacity(s);s->a[s->size] = x;//尾插数字s->size++;//尾插后有效数字+1
}

顺序表尾删：void SeqListPopBack(SeqList* s);

// 顺序表尾删
void SeqListPopBack(SeqList* s)
{s->a[s->size - 1] = 0;s->size--;
}

这样写有一个问题，万一要删除的数字就是0，你还把size-1的位置设置为0，就没有意义了，我们发现只用将size--就行，有效数字就会少一个，打印数据自然会少一个，下次再尾插原本的数据就会被覆盖，原数字也自然就被删除了。

// 顺序表尾删
void SeqListPopBack(SeqList* s)
{//s->a[s->size - 1] = 0;s->size--;
}

这样写是不是还有问题，假设删掉的数字比原本数字多怎么办？程序直接崩了，这样会出现越界访问的问题

// 顺序表尾删
void SeqListPopBack(SeqList* s)
{//方法一：if(s->size == 0)//保证不会被越界{return;}//s->a[s->size - 1] = 0;s->size--;//方法二：assert(s->size > 0);//s->a[s->size - 1] = 0;s->size--;
}

顺序表头插：void SeqListPushFront(SeqList* s, SLDataType x);

// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x)
{CheckCapacity(s);//挪动数据int end = s->size - 1;//最后一个数据while (end >= 0){s->a[end + 1] = s->a[end];end--;}s->a[0] = x;s->size++;
}

顺序表头删：void SeqListPopFront(SeqList* s);

// 顺序表头删
void SeqListPopFront(SeqList* s)
{assert(s->size > 0);//防止越界int begin = 0;while (begin < s->size - 1){s->a[begin] = s->a[begin + 1];begin++;}s->size--;
}

顺序表查找：int SeqListFind(SeqList* s, SLDataType x);

顺序表有顺序存取的功能，因此按位查找元素可以直接通过数组下标定位取得。

// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x)
{for (int i = 0; i < s->size; i++){if (s->a[i] == x)return i;}return -1;
}

顺序表在pos位置插入x：void SeqListInsert(SeqList* s, size_t pos, SLDataType x);

        顺序表的元素插入和插队是一个意思的。想象一下，有一个人要插队，他要插到第3个位置去，那么他前面的两个人不用动，而他后面的人都得动。具体步骤是：最后面的那个人后退一个位置，倒数第二个人后退到原来最后一个人的位置，这样子后面的每个人依次后退，最后就空出来了一个位置，这个人就插队进去了。顺序表也是这么插入的。在插入操作完成后表长+1（多了一个人）。

元素插入有一些要求：

1. 元素下标是否越界（有没有插队到奇怪的位置）
2. 顺序表存储空间是否满了（有没有位置让你插队）

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x)
{//检查pos是否合法assert(pos >= 0 && pos <= s->size);//检查是否需要扩容CheckCapacity(s);int end = s->size - 1;while (end >= pos){s->a[end + 1] = s->a[end];end--;}s->a[pos] = x;s->size++;
}

顺序表删除pos位置的值：void SeqListErase(SeqList* s, size_t pos);

        删除和插入的操作类型，这里借用插队的例子说明。一群人在排队，有一个人有事临时走了，那么这个人的位置就空出来了，后面的人就一个个往前一步，补上这个空位。在删除操作完成后表长-1（少了一个人）。

元素删除有一些要求：

1. 元素下标是否越界（走的人是不是这个排队里面的人）
2. 顺序表存储空间是否为空（有没有人可以走）

// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos)
{//检查pos是否合法assert(pos >= 0 && pos < s->size);int begin = pos;while (begin < s->size - 1){s->a[begin] = s->a[begin + 1];begin++;}s->size--;
}

顺序表销毁：void SeqListDestory(SeqList* s);

        顺序表初始化的时候是用malloc函数向系统申请的空间，malloc函数申请的空间是在内存的堆区，堆区的空间不会被系统自动回收，还需要用free函数释放空间。与malloc一样，要引头文件#include<stdlib.h>。

// 顺序表销毁
void SeqListDestory(SeqList* s)
{free(s->a);//释放开辟的空间s->a = NULL;s->size = 0;s->capicity = 0;
}

顺序表打印：void SeqListPrint(SeqList* s);

// 顺序表打印
void SeqListPrint(SeqList* s)
{for (int i = 0; i < s->size; i++){printf("%d ", s->a[i]);}printf("\n");
}

修改顺序表pos位置的值

// 修改顺序表pos位置的值
void SeqListModify(SeqList* s, size_t pos, SLDataType x)
{assert(pos >= 0 && pos < s->size);//修改pos位置的值s->a[pos] = x;
}

3.顺序表OJ题

1. 原地移除数组中所有的元素val，OJ链接：

https://leetcode.cn/problems/remove-element/

思路一：暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

删除过程如下：

int removeElement(int* nums, int numsSize, int val) 
{int size = numsSize;for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--; // 此时数组的大小-1}}return size;
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

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

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

删除过程如下：

int removeElement(int* nums, int numsSize, int val)
{int fastindex = 0;int slowindex = 0;while (fastindex < numsSize){if (nums[fastindex] != val){nums[slowindex++] = nums[fastindex++];//赋值}else{fastindex++;//发现需要移除的元素，就将指针向后移动一位}}return slowindex;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

2. 删除排序数组中的重复项，OJ链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

3. 合并两个有序数组，OJ链接：https://leetcode.cn/problems/merge-sorted-array/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{int end1 = m;int end2 = n;int end = m + n;while (end1 >= 0 && end2 >= 0){if (nums1[end1] < nums2[end2])nums1[end--] = nums2[end2--];elsenums1[end--] = nums1[end1--];}while (end2 >= 0)nums1[end--] = nums2[end2--];
}

 本节结束啦！