数据结构 | 第一章 | 线性表 | 静态和动态顺序表

静态顺序表和动态顺序表

一、基础知识

• 概念：线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

  用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串

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

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

  • 顺序表一般可以分为：
  • 静态顺序表：使用定长数组存储。
  • 动态顺序表：使用动态开辟的数组存储。

realloc函数：

• realloc 是 C 语言标准库中的一个函数，用于调整之前使用 malloc、calloc 或 realloc 函数分配的内存块的大小。realloc 允许你增大或减小内存块的大小，并返回一个指向新内存块的指针。如果内存重新分配成功，原来的数据（在调整大小后仍然有效的部分）会被复制到新的内存块中。

void *realloc(void *ptr, size_t size);

• ptr 是指向之前分配的内存块的指针。如果 ptr 是 NULL，realloc 的行为等同于 malloc(size)，即分配一个新的内存块。
• size 是新的内存块的大小（以字节为单位）。

返回值：

• 如果重新分配成功，realloc 返回一个指向新内存块的指针。
• 如果重新分配失败，返回 NULL，并且原来的内存块保持不变。

注意事项：

1. 如果 realloc 成功，它会释放原来的内存块并返回一个新的内存块。即使新的内存块大小小于原来的大小，原来的内存块仍然会被释放。
2. 如果 realloc 失败，它会返回 NULL 并且原来的内存块保持不变，因此在使用 realloc 后应该检查返回值是否为 NULL。
3. 使用 realloc 后，原来的指针（ptr）可能不再有效，应该使用 realloc 返回的新指针来访问内存。

exit(-1):

退出状态码是一个整数，它通常用于表示程序的结束状态。按照惯例：

• 返回 0 通常表示程序成功完成。
• 返回非零值通常表示程序遇到了某种错误或异常情况。

二、静态和动态顺序表

提示：静态顺序表在动态顺序表上使用malloc函数进行分配即可。

头文件：SeqList.h

// Created by zjc on 2024/10/15 13:59#ifndef C_CODE2_SEQLIST_H
#define C_CODE2_SEQLIST_H#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>// 1.静态顺序表无法灵活的分配空间
//  1.1 给少了不够用，给多了用不完
//#define MAX_SIZE 10typedef int SQDataType;typedef struct SeqList{// 改成动态的
//    SQDataType a[MAX_SIZE];SQDataType* a;int size;       // 有效数据个数int capacity; // 容量
}SL;// 增删查改接口函数 声明
void SeqListInit(SL* ps);// 1.增加尾插接口函数 声明
void SeqListPushBack(SL* ps,SQDataType x);
// 2.增加头插接口函数 声明
void SeqListPushFront(SL* ps,SQDataType x);
// 3.尾删
void SeqListPopBack(SL* ps);
// 4.头删
void SeqListPopFront(SL* ps);
// 5.随机插入
void SeqListInsert(SL* ps,int pos,SQDataType x);
// 6.随机删除
void SeqListErase(SL* ps,int pos);
// 7.销毁空间
void SeqListDestroy(SL* ps);
// 8.查找数据
//  返回值为int
int SeqListFind(SL* ps,SQDataType x);
// 9. 修改数据
void SeqListModify(SL* ps,int pos,SQDataType x);// 菜单
//void menu();// 打印
void SeqListPrint(SL* ps);#endif //C_CODE2_SEQLIST_H

文件：SeqList.c

#include "SeqList.h"void SeqListInit(SL *ps) {// 使用malloc申请；可以先设置为NULL，待会在尝试ps->a = NULL;ps->size = 0;ps->capacity = 0;}// 检查容量是否够用
void SeqListCheckCapacity(SL *ps) {if (ps->size == ps->capacity) {//1. 满了就要扩容，一般是两倍//2. 判断capacity 是否等于0;int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SQDataType *tmp = (SQDataType *) realloc(ps->a, newcapacity * sizeof(SQDataType));// 判断是否分配成功if (tmp == NULL) {printf("realloc fail\n");exit(-1);} else {// 1.如果开辟成功，就把新开的空间赋值给指针ps->a = tmp;// 2.数据个数不变，容量增加一倍ps->capacity = newcapacity;}}}// 打印输出
void SeqListPrint(SL *ps) {int i = 0;for (i = 0; i < ps->size; i++) {printf(" %d", ps->a[i]);}printf("\n");
}
/*1. 静态数据表初始化
void SeqListInit(SL* ps)
{memset(ps->a,0,sizeof(SQDataType)*MAX_SIZE);ps->size = 0;}2.尾插
void SeqListPushBack(SL* ps,SQDataType x)
{// 判断顺序表是否满了，满了就不插入了if (ps->size >= MAX_SIZE){printf("Seqlist is full !");return;}ps->a[ps->size] = x;ps->size++;
}*/

文件：test.c

// Created by zjc on 2024/10/15 13:59#include "SeqList.h"void TestSeqList1() {SL s1;// 1.初始化SeqListInit(&s1);/*// 尾插入数据SeqListPushBack(&s1,1);SeqListPushBack(&s1,2);SeqListPushBack(&s1,3);SeqListPushBack(&s1,4);SeqListPushBack(&s1,5);SeqListPushBack(&s1,6);SeqListPushBack(&s1,7);SeqListPushBack(&s1,8);SeqListPushBack(&s1,9);SeqListPushBack(&s1,10);SeqListPushBack(&s1,11);
*/// 2.头插入数据SeqListPushFront(&s1, 1);SeqListPushFront(&s1, 2);SeqListPushFront(&s1, 3);SeqListPushFront(&s1, 4);SeqListPushFront(&s1, 5);SeqListPushFront(&s1, 6);// 打印SeqListPrint(&s1);// 3，尾删SeqListPopBack(&s1);// 4. 头删SeqListPopFront(&s1);// 5. 随机插入SeqListInsert(&s1, 1, 20);// 打印SeqListPrint(&s1);// 6.随机删除SeqListErase(&s1, 1);// 打印SeqListPrint(&s1);// 7.释放空间SeqListDestroy(&s1);
}void menu(){printf("**************************************\n");printf("1.尾插数据  2.头插数据\n");printf("3.尾删数据  4.头删数据\n");printf("5.打印数据  -1.退出\n");printf("**************************************\n");printf("请输入你的操作选项：\n");}int main() {SL s;// 初始化SeqListInit(&s);//  option为选项int option = 0;// x为插入的数据int x = 0;while(option != -1){menu();// 选择哪一项scanf("%d",&option);// 判断对应选项的内容switch(option){case 1:printf("请输入你插入的数据，以-1结束\n");do{//  输入插入的数据scanf("%d",&x);// 可以反复插入数据，以输入-1结束if(x != -1){SeqListPushBack(&s,x);}}while(x != -1);break;case 2:break;case 3:break;case 4:break;case 5:SeqListPrint(&s);break;default:break;}}//    TestSeqList1();SeqListDestroy(&s);return 0;
}

三、接口设置

assert函数：

在C语言中，assert 是一个宏，而不是一个函数，它用于在调试期间验证程序中的假设。这个宏定义在 <assert.h> 头文件中。assert 宏接受一个表达式作为参数，并在运行时检查这个表达式的值。

如果表达式的值为真（非零），则 assert 宏不执行任何操作，程序继续执行。如果表达式的值为假（零），则 assert 宏会打印一条错误消息（通常包含失败的表达式、文件名和行号），并调用 abort 函数来终止程序。

// 1.尾插
void SeqListPushBack(SL *ps, SQDataType x) {// 调用函数检查容量SeqListCheckCapacity(ps);// 1.将数据放进去// 2.然后将下标++ps->a[ps->size] = x;ps->size++;
}

// 2.头插
void SeqListPushFront(SL *ps, SQDataType x) {// 调用函数检查容量SeqListCheckCapacity(ps);int end = ps->size - 1;// 从后往前挪，最后一个值size-1// 1.初始条件：// 2.结束条件：直到第一个元素下标为0，移动完毕// 3.迭代过程while (end >= 0) {// 将数据从后依次移动到下一个位置ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

// 3.尾删
void SeqListPopBack(SL* ps){// 如果存在的元素大于0，还可以删除，等于0就没有元素可以删除了assert(ps->size > 0);
//    ps->a[ps->size - 1] = 0; 没必要，要是本身就是0呢
//    直接--就可以了ps->size--;
}

// 4.头删
void SeqListPopFront(SL* ps){assert(ps->size > 0);int start = 1;// 如果start大于等于说明元素已经全部移除完成while(start < ps->size){// 依次将元素往前放// 相当于将a[1]赋值给a[0]ps->a[start - 1] = ps->a[start];start++;}// 将size--ps->size--;
}

// 5.随机插入
void SeqListInsert(SL* ps,int pos,SQDataType x){// 位置肯定要小于表的长度assert(pos < ps->size);// 检查容量是否足够SeqListCheckCapacity(ps);int end = ps->size - 1;// 循环判断最后一个元素是否与当前while(end >= pos){ps->a[end+1]= ps->a[end];--end;}// 将需要放入的数据放进去ps->a[pos] = x;// size ++ps->size++;
}

• 数据删除后数据空间依然是存在的

// 6.随机删除
void SeqListErase(SL* ps,int pos){// 位置肯定要小于数据个数的，[0,size)assert(pos < ps->size);// start位置定义在pos后面int start = pos + 1;// start等于size就已经将元素遍历完成while(start < ps->size){ps->a[start - 1]= ps->a[start];start++;}// 将size--ps->size--;
}

// 7.销毁空间
void SeqListDestroy(SL *ps) {// malloc的空间不销毁就会存在内存泄漏free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}

// 9. 修改数据
void SeqListModify(SL* ps,int pos,SQDataType x){assert(pos > ps->size);ps->a[pos] = x;
}

四、题目练习

1、题目一

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k = removeElement(nums, val); // 调用你的实现assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）

思路：双指针同步

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

2. src位置不是val就放在dst位置，然后src++，dst++

3. scr位置是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++];// src++;// dst++;}else{src++;}}return dst;
}

2、题目二

88. 合并两个有序数组

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

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

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

示例 1：

输入：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 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

解答思路：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 = m-1;int end2 = n-1;int end = m + n -1;// 两个都没有到尾才进行比较while(end1 >= 0 && end2 >= 0){if(nums1[end1] >  nums2[end2]){nums1[end] = nums1[end1];--end;// end1大就将end1----end1;}else{nums1[end] = nums2[end2];--end;// end1大就将end1----end2;}}// 如果是end1结束，不需要处理，因为就在nums1里面while(end2 >= 0){// 剩余nums2，就是最小的了，将nums2所有数据移动到nums1nums1[end] = nums2[end2];--end;--end2;}
}