顺序表

秃头王

基础数据结构

发布于：2022年1月14日

次浏览

数据结构 = 结构定义 + 结构操作

cppreference

https://zh.cppreference.com/w/%E9%A6%96%E9%A1%B5

顺序表 - 线性结构：一对一

1.什么是顺序表？是一个更高级的数组

结构定义：

一片连续存储空间

可以存储任意类型值 (类型需要一致，int、char、结构体…) (data_type)

顺序表大小 (size)

顺序表以存储个数 (length)

结构操作：

插入元素 (insert)

如果第一个满足只执行1不满足可以直接执行 2 可以通过整理直接用2来实现

如果代插入数据i 等于i == length 那么直接在后面添加length++

在待插入位置i 把i + 1 后数据全部向后移动一位,并且legth++

删除元素 (clear)

待删位置 i 把i + 1之后位置的数据向前移动一位覆盖掉 length--

新知识

#include <stdlib.h> // malloc 需要头文件
#include <stdio.h>
#demine MAX_N 20

/* 函数中 // int arr[n + 1]; // 栈区 在Linux系统中只有 8M 很小
 * malloc 动态开辟空间 如果不用需要主动释放 返回值是一块连续的地址(逻辑上) void*
 * calloc 参数size为申请地址的单元元素长度，nmemb为元素个数，即在内存中申请nmemb *size字节大小的连续地址空间， 并赋值0-相当于自带初始化；
 * realloc 给一个已经分配了地址的指针重新分配空间，参数ptr为原有的空间地址，size为重新申请的地址长度；
 * free 释放
 **/

int main() {
    // 函数 malloc
    int *v = (int *) malloc(sizeof(int) * MAX_N);
    free(v);
    v = NULL;
    // 函数 calloc
    int *v1 = (int *) calloc(20, MAX_N * sizeof(int));
    free(v);
    v = NULL;
    // 函数 realloc  在 malloc 基础上
    // 数字数量大于当前 malloc 大小 重新分配
    int *v = (int *) malloc(sizeof(int) * MAX_N);
    v = (int *) realloc (v, 5 * sizeof(int) * MAX_N);
    free(v);
    v = NULL;
    return 0;
}

代码演示-顺序表

/*************************************************************************
        > File Name: 顺序表.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月14日 星期五 12时03分03秒
 ************************************************************************/

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

#define COLOR(a, b) "\033[" #b "m" a"\033[0m"

#define GREEN(a) COLOR(a, 32)
#define RED(a) COLOR(a, 31)

typedef int Type;

typedef struct Vector {
    Type *data;
    int size, length;
} Vec;


Vec *init(int n) {
    // int arr[n + 1]; // 栈区 在Linux系统中只有 8M 很小
    Vec *v = (Vec *)malloc(sizeof(Vec));
    v->data = (Type *)malloc(sizeof(Type) * n);
    v->size = n;
    v->length = 0;
    return v;
}

void clear(Vec *v) {
    if(v == NULL) return ; // 如果内存申请失败
    free(v->data); // 申请了2个空间
    free(v);
    return ;
}

// 扩容
int expand(Vec *v) {
    int extr_size = v->size;
    Type *p;
    while(extr_size) {
        p = (Type *)realloc(v->data, sizeof(Type) * (v->size + extr_size));
        if(p != NULL) break;
        extr_size >>= 1;
    }
    if(p == NULL) {
        printf(RED("扩容失败\n"));
        return 0;
    }
    v->size += extr_size;
    v->data = p;
    printf(GREEN("当前容量 : %d -- 扩容到 : %d\n"), v->size - extr_size, v->size);
    return 1;
}

int insert(Vec *v, int ind, Type val) {
    // ind 需要插入的位置
    if(v == NULL) return 0;
    if(ind < 0 || ind > v->length) return 0;
    if(v->length == v->size) {
        if(!expand(v)) return 0;
    }
    for(int i = v->length; i > ind; i--) {
        v->data[i] = v->data[i - 1];
    }
    v->data[ind] = val;
    v->length +=1;
    return 1;
}

int erase(Vec *v, int ind) {
    if(v == NULL) return 0;
    if(ind < 0 || ind >= v->length) return 0;
    for(int i = ind + 1; i < v->length; i++) {
        v->data[i - 1] = v->data[i];
    }
    v->length--;
    return 1;
}

void output(Vec *v) {
    if(v == NULL) return ;
    printf("Vector(%d) :[", v->length);
    for(int i = 0; i < v->length; i++) {
        i && printf(",");
        printf("%d", v->data[i]);
    }
    printf("]\n");
    return ;
}

int main() {
    #define MAX_N 20
    Vec *v = init(1);
    srand(time(0));
    for(int i = 0; i < MAX_N; i++) {
        int op = rand() % 2;
        int ind = rand() % (v->length + 3) - 1;
        int val = rand() % 100;
        switch(op) {
            case 0: printf("insert %d at %d to Vector = %d \n", val, ind, insert(v, ind, val)); break;
            case 1: printf("erase a iterm at %d from Vector = %d\n", ind, erase(v, ind)); break;
        }
        output(v), printf("\n");
    }
    clear(v);
    #undef MAX_N
    return 0;
}