C/C++ -顺序表-模块化实现

前言

链表-贯穿数据结构的基础，顺序表是其中之一。当使用c/c++实现这些数据结构的时候，我们使用指针相关内容，良好的指针基础是学好数据结构的关键。*在大多数的教科书中在初始化表时直接固定好了表长，本篇文章介绍的方法是动态开辟内存，这样做的好处是节省了内存开销。*那么我们在进行顺序表的编码前，首先进行c的几个库函数的学习：

①malloc函数：申请一块连续的指定大小的的内存空间，默认值随机。
原型：void *malloc(unsigned int num_bytes);

②calloc函数：申请一块连续的指定大小的内存空间，并将所有值默认为0，等价于malloc,效率比malloc低。
原型：void *calloc(size_t n, size_t size);

③realloc函数：对已经申请的空间进行扩容。
原型：void realloc(void *ptr, size_t size);

这里只是对三种函数进行简单的介绍，在本篇文章中不会详细介绍，需要详细使用方法可以自行百度。

需求

初始化表 -> 将数据分别添加到表a, 表b -> 合并表a 和表b ->输出结果;

顺序表原理

顺序表结构：

在这里插入图片描述

解释：定义结构体，包含顺序表指针 *elements，表中元素个数 count，表中空间长度 size(以一个数据类型为单位)。

// list.c

struct list {
    int *elements;  //元素数组
    int count;      //元素个数（长度）
    int size;       //空间长度
};

顺序表操作：

1.表初始化

struct list *list_init() // 初始化表
{
    // 表指空
    struct list *list = NULL;
    // 给list分配空间(初始化)
    list = (struct list *)malloc(sizeof(struct list));
    if(list == NULL) {
        return NULL;
    }
    // 为表的elements分配空间(初始化)
    list->elements = (int *)calloc(LIST_INIT_SIZE, sizeof(int));
    if(list->elements == NULL) {
        free(list);
        return NULL;
    }
    list->count = 0;
    list->size = 0;

    return list;
}

2.释放表

void list_free(struct list *list)
{
    free(list->elements);
    free(list);
    return;
}

3.清空表

void list_clear(struct list *list)
{
    list->count = 0;
    return;
}

4.判空

int list_isempty(struct list *list)
{
    return list->count == 0;
}

5.获取表长度

int list_count(struct list *list)
{
    return list->count;
}

6.获取元素

int list_get(struct list *list, int index)
{
    return list->elements[index];
}

7.设置元素

void list_set(struct list *list, int index, int element)
{
    list->elements[index] = element;
    return;
}

8.删除元素

int list_remove(struct list *list, int index)
{
    // 存储移除元素，最后返回
    int rm_element = list->elements[index];
    // 从index 开始，元素从后往前移动，elements长度减一
    for(int i = index; i < list->count - 1; i++) {
        list->elements[index] = list->elements[index + 1];
    }

    list->count--;
    return rm_element;
}

9.添加元素

void list_add(struct list *list, int index, int element)
{
    // 表满 ? 扩容 : 退出;
    if(list->count == list->size) {
        int *tmp = NULL;
        tmp = (int *)realloc(list->elements, sizeof(int)*(list->size + LIST_INIT_SIZE));
        if(tmp == NULL) {
            exit(EXIT_FAILURE);
        }

        list->elements = tmp;
        list->size += LIST_INIT_SIZE;
    }
	// 将index之后的元素后移
    for(int i = list->count - 1; i >= index; i--) {
        list->elements[i + 1] = list->elements[i];
    }

    list->elements[index] = element;
    list->count++;

    return;
}

自定义头文件 list.h

// list.h

struct list;
// 初始化表
struct list *list_init();
// 释放表
void list_free(struct list *list);
// 清空表
void list_clear(struct list *list);
// 判空
int list_isempty(struct list *list);
// 获取表长度,返回长度
int list_count(struct list *list);
// 获取元素，返回元素值
int list_get(struct list *list, int index);
// 设置元素
void list_set(struct list *list, int index, int element);
// 删除元素，返回删除元素
int list_remove(struct list *list, int index);
// 添加元素
void list_add(struct list *list, int index, int element);

mian.c

// main.c
    
int main()
{
    // 1.定义 list_a 和 list_b
    struct list *list_a = NULL;
    struct list *list_b = NULL;
    int flag;
    // 2.list_init()方法初始化 list_a 和 list_b, list_add()方法, 插入数据
    list_a = list_init();
    list_add(list_a, 0, 3);
    list_add(list_a, 0, 6);
    list_add(list_a, 0, 9);
    list_add(list_a, 0, 12);
    list_add(list_a, 0, 43);

    list_b = list_init();
    list_add(list_b, 0, 7);
    list_add(list_b, 0, 12);
    list_add(list_b, 0, 1);
    list_add(list_b, 0, 3);
    list_add(list_b, 0, 8);

    // 3.合并 list_a 和 list_b, 去重
    for(int i = 0; i < list_count(list_b); i++) {
        flag = 0;
        for(int j = 0; j < list_count(list_a); j++) {
            if(list_get(list_a, j) == list_get(list_b, i)) {
                flag = 1;
                break;
            }
        }
        if(flag == 0) {
            list_add(list_a, list_count(list_a), list_get(list_b, i));
        }
    }
	cout << "这是结果" << endl;
    // 4.输出结果，释放指针
    for(int i = 0; i < list_count(list_a); i++) {
        cout << list_get(list_a, i) << " ";
    }
    cout << endl;
    list_free(list_a);
    list_free(list_b);

    system("PAUSE");
    return 0;
}