数据结构：顺序表的概念、实现与操作

数据结构：顺序表的概念、实现与操作 | 极客日志

#define N 100 // 静态顺序表
struct SeqList {
    int arr[N];
    int size; // 有效数据个数
};

// 动态顺序表
typedef int SLDataType; // 方便后续类型的统一替换
typedef struct SeqList {
    SLDataType* arr;
    int size;      // 有效数据个数
    int capacity;  // 空间大小
} SL;

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 顺序表初始化
void SLInit(SL* ps);

void SLInit(SL* ps) // 传值调用会报错
{
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
    // 也可以初始化就给一块空间
    // ps->arr = malloc();
    // ps->size = ps->capacity = 10;
}

void SLTest01() {
    SL sl;
    SLInit(sl); // 错误：sl 没有初始化
}

void SLTest01() {
    SL sl;
    SLInit(&sl);
}

// 顺序表的销毁
void SLDestory(SL* ps);

// 顺序表的销毁
void SLDestory(SL* ps) {
    if (ps->arr) // 有空间就销毁
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

// 尾插
void SLPushBack(SL* ps, SLDataType x);
// 头插
void SLPushFront(SL* ps, SLDataType x);

// 尾插 - 未封装函数前
void SLPushBack(SL* ps, SLDataType x) {
    ps->arr[ps->size] = x;
    ++ps->size; // 可以合并为 ps->arr[ps->size++] = x;
}

// 插入数据之前判断空间够不够
if (ps->capacity == ps->size) {
    // 申请空间
    // 需要先判断 capactity 空间容量是否为 0
    int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    // ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
    // 这样直接写的话会有申请失败的问题，所以还要检查一下申请是否失败的判断
    // 先放在一个临时指针 SLDataType* tmp=(SLDataType*)realloc(ps->arr, newCapacity *sizeof(SLDataType));
    if (tmp == NULL) {
        perror("realloc fail!");
        exit(1);
    }
    // 空间申请成功
    ps->arr = tmp;
    ps->capacity = newCapacity;
}

void SLCheckCapacity(SL* ps) {
    // 插入数据之前判断空间够不够
    if (ps->capacity == ps->size) {
        // 申请空间
        // 需要先判断 capactity 空间容量是否为 0
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        // ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        // 这样直接写的话会有申请失败的问题，所以还要检查一下申请是否失败的判断
        // 先放在一个临时指针 SLDataType* tmp =(SLDataType*)realloc(ps->arr, newCapacity *sizeof(SLDataType));
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1); // 不在 main 函数里面使用 exit(1)，直接退出，不再继续执行
        }
        // 空间申请成功
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

SLPushBack(NULL, 5); // 指针为空，不能解引用，因此要对这种情况进行判断

void SLPushBack(SL* ps, SLDataType x) {
    // 避免用户输入 NULL 判断 ps 是否为空
    assert(ps);
    SLCheckCapacity(ps); // 判断空间够不够
    ps->arr[ps->size++] = x;
}

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps); // 判断空间够不够
    // 先让顺序表的整体后移
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

// 顺序表打印
void SLPrint(SL s);

void SLPrint(SL s) {
    for (int i = 0; i < s.size; i++) {
        printf("%d ", s.arr[i]);
    }
    printf("\n");
}

void SLTest01() {
    SL s1;
    // 初始化
    SLInit(&s1);
    // 增删查改
    // 尾插
    SLPushBack(&s1, 1);
    SLPushBack(&s1, 2);
    SLPushBack(&s1, 3);
    SLPushBack(&s1, 4);
    // 打印
    SLPrint(s1);
    // 头插
    SLPushFront(&s1, 5);
    SLPushFront(&s1, 6);
    // 打印
    SLPrint(s1);
}

int main() {
    SLTest01();
    return 0;
}

// 尾删
void SLPopBack(SL* ps);
// 头删
void SLPopFront(SL* ps);

void SLPopBack(SL* ps) {
    // 不能为空，为空不能执行删除操作
    assert(ps);
    assert(ps->size); // 顺序表不为空
    // ps->arr[ps->size - 1] = -1; // 表示把这个位置的值删去，可以不要这段代码
    // 因为 size--完后不会访问后面的数据，如果想尾插的话会覆盖原来的值
    --ps->size;
}

void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    // 数据整体向前移动
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1]; // arr[size - 2] = arr[size - 1]
    }
    ps->size--;
}

void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size); //=ps->size 时相当于尾插
    // 插入数据空间够不够
    SLCheckCapacity(ps);
    // 让 pos 后面的数据往后挪，从后往前挪
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->arr[i] == x) {
            // 找到了
            return i;
        }
    }
    // 没有找到
    return -1;
}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 定义顺序表结构
// #define N 100
// // 静态顺序表
// struct SeqList
// {
//     int arr[N];
//     int size; // 有效数据个数
// };

// 动态顺序表
typedef int SLDataType; // 方便后续类型的统一替换
typedef struct SeqList {
    SLDataType* arr;
    int size;
    int capacity;
} SL;

// 顺序表初始化
void SLInit(SL* ps);
// 顺序表的销毁
void SLDestory(SL* ps);
// 顺序表打印
void SLPrint(SL s); // 不需要改可以传值
// 头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
// 指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
// 查找
int SLFind(SL* ps, SLDataType x);

#include "SeqList.h"

// 1. 初始化
void SLInit(SL* ps) // 传值调用会报错
{
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
    // 也可以初始化就给一块空间
    // ps->arr = malloc();
    // ps->size = ps->capacity = 10;
}

// 5. 由于头插和尾插都需要判断空间够不够，于是干脆设一个函数判断
void SLCheckCapacity(SL* ps) {
    // 插入数据之前判断空间够不够
    if (ps->capacity == ps->size) {
        // 申请空间
        // 需要先判断 capactity 空间容量是否为 0
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        // ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        // 这样直接写的话会有申请失败的问题，所以还要检查一下申请是否失败的判断
        // 先放在一个临时指针 SLDataType* tmp =(SLDataType*)realloc(ps->arr, newCapacity *sizeof(SLDataType));
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1); // 不在 main 函数里面使用 exit(1)，直接退出，不再继续执行
        }
        // 空间申请成功
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

// 3. 尾插 - 封装函数后
void SLPushBack(SL* ps, SLDataType x) {
    // 避免用户输入 NULL 判断 ps 是否为空
    assert(ps);
    SLCheckCapacity(ps); // 判断空间够不够
    ps->arr[ps->size++] = x;
}

// 4. 头插
void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps); // 判断空间够不够
    // 先让顺序表的整体后移
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

// 7. 尾删
void SLPopBack(SL* ps) {
    // 不能为空，为空不能执行删除操作
    assert(ps);
    assert(ps->size); // 顺序表不为空
    // ps->arr[ps->size - 1] = -1; // 表示把这个位置的值删去，可以不要这段代码
    // 因为 size--完后不会访问后面的数据，如果想尾插的话会覆盖原来的值
    --ps->size;
}

// 8. 头删
void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    // 数据整体向前移动
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1]; // arr[size - 2] = arr[size - 1]
    }
    ps->size--;
}

// 9. 指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size); //=ps->size 时相当于尾插
    // 插入数据空间够不够
    SLCheckCapacity(ps);
    // 让 pos 后面的数据往后挪，从后往前挪
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1]; // arr[pos+1]=arr[pos]
    }
    ps->arr[pos] = x;
    ps->size++;
}

// 10. 删除指定位置的数据
void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1]; // arr[size-2]=arr[size-1]
    }
    ps->size--;
}

// 11. 查找
int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->arr[i] == x) {
            // 找到了
            return i;
        }
    }
    // 没有找到
    return -1;
}

// 2. 顺序表的销毁
void SLDestory(SL* ps) {
    if (ps->arr) // 有空间就销毁
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

// 6. 打印
void SLPrint(SL s) {
    for (int i = 0; i < s.size; i++) {
        printf("%d ", s.arr[i]);
    }
    printf("\n");
}

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

// 传值
void SLTest01() {
    SL s1;
    // 初始化
    SLInit(&s1);
    // 增删查改
    // 尾插
    SLPushBack(&s1, 1);
    SLPushBack(&s1, 2);
    SLPushBack(&s1, 3);
    SLPushBack(&s1, 4);
    // 打印
    SLPrint(s1);
    // 头插
    SLPushFront(&s1, 5);
    SLPushFront(&s1, 6);
    // 打印
    SLPrint(s1);
    // 尾删
    SLPopBack(&s1);
    SLPrint(s1);
    // 头删
    SLPopFront(&s1);
    SLPrint(s1);
    // 指定位置之前插入
    SLInsert(&s1, 0, 99);
    SLPrint(s1);
    SLInsert(&s1, s1.size, 88);
    SLPrint(s1);
    // 指定位置删去
    SLErase(&s1, 0);
    SLPrint(s1);
    SLErase(&s1, s1.size - 1);
    SLPrint(s1);
    // 查找
    int find = SLFind(&s1, 3);
    if (find < 0) {
        printf("没有找到\n");
    } else {
        printf("找到了，下标为%d\n", find);
    }
    // 销毁
    SLDestory(&s1);
}

int main() {
    SLTest01();
    return 0;
}

int removeElement(int* nums, int numsSize, int val) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == val) {
            for (int j = i + 1; j < numsSize; j++) {
                nums[j - 1] = nums[j];
            }
            i--; // 因为下标 i 以后的数值都向前移动了一位，所以 i 也向前移动一位
            numsSize--;
        }
    }
    return numsSize;
}

int removeElement(int* nums, int numsSize, int val) {
    // 创建临时数组
    int* temp = (int*)malloc(numsSize * sizeof(int));
    int k = 0;
    // 遍历原数组，将非 val 的元素放入临时数组
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != val) {
            temp[k] = nums[i];
            k++;
        }
    }
    // 将临时数组的内容复制回原数组
    for (int i = 0; i < k; i++) {
        nums[i] = temp[i];
    }
    free(temp);
    return k;
}

int removeElement(int* nums, int numsSize, int val) {
    // 先创建两个变量
    int src, dst; src = dst = 0;
    while (src < numsSize) {
        if (nums[src] == val) {
            src++;
        } else {
            // 赋值，两指针++
            nums[dst++] = nums[src++];
        }
    }
    // 此时 dst 的值刚好就是新数组的有效长度
    return dst;
}

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    for (int fast = 0; fast < numsSize; fast++) {
        // 若快指针位置的元素不等于要删除的元素
        if (nums[fast] != val) {
            // 将其挪到慢指针指向的位置，慢指针 +1
            nums[slow++] = nums[fast];
        }
    }
    // 最后慢指针的大小就是新的数组的大小
    return slow;
}

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int slow = 1;
    for (int fast = 1; fast < numsSize; fast++) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
    }
    return slow;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1 = m - 1;
    int l2 = n - 1;
    int l3 = m + n - 1;
    while (l1 >= 0 && l2 >= 0) {
        if (nums1[l1] < nums2[l2]) {
            nums1[l3--] = nums2[l2--];
        } else {
            nums1[l3--] = nums1[l1--];
        }
    }
    // 出了循环有两种情况：l1 < 0 || l2 < 0
    // 是否存在 l1,l2 同时小于 0 的情况 -- 不存在
    // 只需要处理 l1 < 0 情况（说明 l2 中数据还没完全放入 num1 中）
    while (l2 >= 0) {
        nums1[l3--] = nums2[l2--];
    }
}

数据结构：顺序表的概念、实现与操作

数据结构：顺序表

前言

1. 线性表

2. 顺序表

2.1 概念及其结构

2.2 定义顺序表结构

2.3 顺序表的初始化

2.4 顺序表的销毁

2.5 顺序表的插入

2.5.1 尾插

2.5.2 头插

2.6 打印

2.7 顺序表的删除

2.7.1 尾删

2.7.2 头删

2.8 指定位置之前插入/指定位置删除数据

2.8.1 指定位置之前插入

2.8.2 指定位置删除

2.9 查找

2.10 所有代码

3. 练习

3.1 移除元素

3.2 删除有序数组的重复项

3.3 合并两个有序数组

4. 顺序表的优点与局限性

结语

更多推荐文章

相关免费在线工具

数据结构：顺序表的概念、实现与操作

数据结构：顺序表

前言

1. 线性表

2. 顺序表

2.1 概念及其结构

2.2 定义顺序表结构

2.3 顺序表的初始化

2.4 顺序表的销毁

2.5 顺序表的插入

2.5.1 尾插

2.5.2 头插

2.6 打印

2.7 顺序表的删除

2.7.1 尾删

2.7.2 头删

2.8 指定位置之前插入/指定位置删除数据

2.8.1 指定位置之前插入

2.8.2 指定位置删除

2.9 查找

2.10 所有代码

3. 练习

3.1 移除元素

3.2 删除有序数组的重复项

3.3 合并两个有序数组

4. 顺序表的优点与局限性

结语

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具