静态顺序表和动态顺序表
一、基础知识
-
概念：线性表（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，并且原来的内存块保持不变。注意事项：
- 如果
realloc成功，它会释放原来的内存块并返回一个新的内存块。即使新的内存块大小小于原来的大小，原来的内存块仍然会被释放。- 如果
realloc失败，它会返回NULL并且原来的内存块保持不变，因此在使用realloc后应该检查返回值是否为NULL。- 使用
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 10
typedef 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;
}
四、题目练习
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 个元素之外留下了什么并不重要（因此它们并不计入评测）
思路：双指针同步
-
时间复杂度O(N)，空间复杂度O(1)
-
src位置不是val就放在dst位置，然后src++，dst++
-
scr位置是val,src++
开始：
最后：
