【C/C++】C语言实现顺序表

简单描述

• 用codeblocks编译通过
• 源码参考连接

https://gitee.com/IUuaena/data-structures-c.git

代码

• common.h

#ifndef COMMON_H_INCLUDED
#define COMMON_H_INCLUDED

#define LIST_INIT_CAPACITY  100 //!< 线性表初始化长度
#define LIST_INCREMENT      10  //!< 线性表增量
#define ELEM_TYPE           int //!< 线性表元素类型

/*! @brief 函数返回值枚举 */
typedef enum {
    OK = 0,             //!< 正确
    NON_ALLOCATED = 1,  //!< 内存分配失败
    NON_EXISTENT = 2,   //!< 不存在
    OVERFLOW = 3,       //!< 溢出
    ERROR = 4           //!< 其他类型错误
} status_t;

#endif // COMMON_H_INCLUDED

• seq_list.h

#ifndef SEQ_LIST_H_INCLUDED
#define SEQ_LIST_H_INCLUDED

#include "common.h"


/*!
 * @brief **线性表**
 * @note
 */
typedef struct {
    ELEM_TYPE* elements;    //!< 元素数组
    int length;             //!< 长度
    int capacity;           //!< 容量
} seq_list_t;


// 顺序表初始化
status_t SeqListInit(seq_list_t* seq_list);

// 顺序表插入
status_t SeqListInsert(seq_list_t* seq_list, int pos, ELEM_TYPE elem);

// 顺序表删除元素
status_t SeqListDelete(seq_list_t* seq_list, int pos, ELEM_TYPE* elem);

// 顺序表查找
int SeqListLocate(seq_list_t* seq_list, ELEM_TYPE elem, int (*compare)(ELEM_TYPE, ELEM_TYPE));

// 顺序表的合并
status_t SeqListMerge(seq_list_t* list_a, seq_list_t* list_b, seq_list_t* merged_list);

// 顺序表打印
void SeqListPrint(seq_list_t* seq_list);


#endif // SEQ_LIST_H_INCLUDED

/*!
 * @file seq_list.c
 * @author CyberDash计算机考研, [e-mail](抖音id:cyberdash_yuan)
 * @brief 顺序表源文件
 * @version 1.0.0
 * @date 2022-07-10
 * @copyright Copyright (c) 2021
 *  CyberDash计算机考研
 */

#include <stdlib.h>
#include <stdio.h>
#include "seq_list.h"


/*!
 * @brief **顺序表初始化**
 * @param seq_list **顺序表**(指针)
 * @return **是否成功**
 * @note
 * 顺序表初始化
 * ----------
 * ----------
 * - 分配elements数组内存 \n
 * &emsp; **if** 内存分配失败 : \n
 * &emsp;&emsp; 返回NON_ALLOCATED \n
 */
status_t SeqListInit(seq_list_t* seq_list)
{

    // 分配elements数组内存
    seq_list->elements = (ELEM_TYPE*)malloc(LIST_INIT_CAPACITY * sizeof(ELEM_TYPE));
    if (!seq_list->elements)
    {
        return NON_ALLOCATED;
    }

    // 设置length和capacity
    seq_list->length = 0;                       // 空表长度为0
    seq_list->capacity = LIST_INIT_CAPACITY;    // 初始存储容量

    return OK;
}


/*!
 * @brief **顺序表插入**
 * @param seq_list **顺序表**(指针)
 * @param pos **插入位置(插入到该位置结点的前一位置)**
 * @param elem **待插入元素**
 * @return **执行结果**
 * @note
 * 顺序表插入
 * ------------
 * ------------
 * **注**: 本顺序表实现, 索引从1开始, 区别于数组的从0开始\n
 * - 插入位置合法性判断 \n
 * &emsp; **if** 插入位置 < 1 或者 插入位置 > 长度 + 1 : \n
 * &emsp;&emsp; 返回OVERFLOW \n
 * - 满容量处理 \n
 * &emsp; **if** 线性表的容量已满(不扩容无法插入) : \n
 * &emsp;&emsp; 使用增量LIST_INCREMENT计算新的容量, 并分配新的elements数组内存 \n
 * &emsp;&emsp; **if** 内存分配失败 : \n
 * &emsp;&emsp;&emsp; 返回NON_ALLOCATED \n
 * &emsp;&emsp; 顺序表elements指针指向新数组 \n
 * &emsp;&emsp; 顺序表capacity增加容量数值 \n
 * - 插入位置(包含)后面的所有结点向后移动一位 \n
 * - 插入元素 \n
 * &emsp; 插入位置赋值 \n
 * &emsp; 表长+1 \n
 */
status_t SeqListInsert(seq_list_t* seq_list, int pos, ELEM_TYPE elem)
{

    // 插入位置合法性判断
    if (pos < 1 || pos > seq_list->length + 1)
    {
        return OVERFLOW;
    }

    // 满容量处理
    if (seq_list->length >= seq_list->capacity)
    {
        // 使用增量LIST_INCREMENT计算新的容量, 并分配新的elements数组内存
        unsigned int new_capacity = (seq_list->capacity + LIST_INCREMENT) * sizeof(ELEM_TYPE);
        ELEM_TYPE* new_elements = (ELEM_TYPE*)realloc(seq_list->elements, new_capacity);
        if (!new_elements)
        {
            return NON_ALLOCATED;
        }

        seq_list->elements = new_elements;      // 顺序表elements指针指向新数组
        seq_list->capacity += LIST_INCREMENT;   // 顺序表capacity增加容量数值
    }

    // 插入位置(包含)后面的所有结点向后移动一位
    ELEM_TYPE* insert_pos_elem = seq_list->elements + pos - 1;
    for (ELEM_TYPE* cur = seq_list->elements + seq_list->length - 1; cur >= insert_pos_elem; cur--)
    {
        *(cur + 1) = *cur;
    }

    *insert_pos_elem = elem;  // 插入elem
    seq_list->length++;       // 表长增1

    return OK;
}


/*!
 * @brief **顺序表删除元素**
 * @param seq_list **顺序表**(指针)
 * @param pos **被删除结点所在位置**
 * @param elem **被删除结点的保存变量**
 * @return **执行结果**
 * @note
 * 顺序表删除元素
 * ------------
 * ------------
 * - 删除节点位置正确性检查 \n
 * &emsp;**if** pos < 1 或者 pos > 线性表长度 : \n
 * &emsp;&emsp; 返回OVERFLOW \n
 * - 被删除结点的值赋给保存变量 \n
 * - 被删除结点后面的所有结点向前移动补位 \n
 * &emsp; **for loop** 被删除节点后侧所有所有结点 : \n
 * &emsp;&emsp; 当前结点值赋给前一节点 \n
 * - 表长减1 \n
 */
status_t SeqListDelete(seq_list_t* seq_list, int pos, ELEM_TYPE* elem)
{
    if (pos < 1 || pos > seq_list->length)
    {
        return OVERFLOW;
    }

    // 待删除节点值赋给保存变量
    ELEM_TYPE* delete_pos_elem = &(seq_list->elements[pos - 1]);
    *elem = *delete_pos_elem;

    ELEM_TYPE* last_elem = seq_list->elements + seq_list->length - 1;   // 表尾元素指针
    for (ELEM_TYPE* cur = delete_pos_elem + 1; cur <= last_elem; cur++)
    {
        // 当前结点值赋给前一结点
        *(cur - 1) = *cur;
    }

    // 表长减1
    seq_list->length--;

    return OK;
}


/*!
 * @brief **顺序表查找**
 * @param seq_list **顺序表**(指针)
 * @param elem **元素值**
 * @param compare **比较函数**
 * @return **元素位置**
 * @note
 * 顺序表查找
 * ------------
 * ------------
 * 如果没有该元素, 则返回0, 否则返回所在位置(首元素从1开始) \n
 * - 初始化pos和遍历指针cur \n
 * &emsp; pos初始化为1(首结点位置) \n
 * &emsp; cur指向elements数组首元素 \n
 * - 遍历线性表查找
 * &emsp; **while** 未遍历完线性表and未找到对应结点 : \n
 * &emsp;&emsp; pos加1 \n
 * &emsp;&emsp; cur指向后一元素 \n
 * - 返回位置 \n
 * &emsp; 如果找到位置, 返回位置 \n
 * &emsp; 如果没有找到位置, 返回0 \n
 */
int SeqListLocate(seq_list_t* seq_list, ELEM_TYPE elem, int (*compare)(ELEM_TYPE, ELEM_TYPE))
{

    // 初始化pos和遍历指针cur
    int pos = 1;                            // pos为第1个元素的位置
    ELEM_TYPE* cur = seq_list->elements;    // cur指向第1个元素的存储位置

    // 遍历线性表查找
    while (pos <= seq_list->length && (*compare)(*cur, elem) != 0)
    {
        pos++;
        cur++;
    }

    // 返回位置
    if (pos <= seq_list->length)
    {
        return pos;
    }

    return 0;
}


/*!
 * @brief **顺序表的合并**
 * @param list_a **顺序表a**
 * @param list_b **顺序表b**
 * @param merged_list **合并后的顺序表**
 * @return **执行结果**
 * @note
 *
 * 顺序表的合并
 * ----------
 * ----------
 * - 初始化两个顺序表的表头指针/表尾指针 \n
 * &emsp; list_a_cur指向表a的表头, list_b_cur指向表b的表头 \n
 * &emsp; list_a_last指向表a的表尾, list_b_last指向表b的表尾 \n
 * - 合并后的表设置属性分配内存 \n
 * &emsp; 设置长度/容量 \n
 * &emsp; 分配内存 \n
 * &emsp; **if** 内存分配失败 : \n
 * &emsp;&emsp; 返回NON_ALLOCATED \n
 * - 执行合并 \n
 * &emsp; **while** 任意一个表未合并完 : \n
 * &emsp;&emsp; **if** 表a当前元素 <= 表b当前元素 : \n
 * &emsp;&emsp;&emsp; 表a当前元素(*list_a_cur)插入合并表表尾 \n
 * &emsp;&emsp;&emsp; list_a_cur指向后面1位 \n
 * &emsp;&emsp; **else** (表a当前元素 > 表b当前元素) : \n
 * &emsp;&emsp;&emsp; 表b当前元素(*list_b_cur)插入合并表表尾 \n
 * &emsp;&emsp;&emsp; list_b_cur指向后面1位 \n
 * &emsp;&emsp; merged_list_cur指向后面1位(合并表当前元素向后移动) \n
 * - 未合并完的表补表尾 \n
 * &emsp; 表a剩余元素加到合并表尾部(如果表a有剩余) \n
 * &emsp; 表b剩余元素加到合并表尾部(如果表b有剩余) \n
 */
status_t SeqListMerge(seq_list_t* list_a, seq_list_t* list_b, seq_list_t* merged_list)
{
    ELEM_TYPE* list_a_cur = list_a->elements;   // list_a_cur指针 -> 顺序表a的elements数组首地址
    ELEM_TYPE* list_b_cur = list_b->elements;   // list_b_cur指针 -> 顺序表b的elements数组首地址
    ELEM_TYPE* list_a_last = list_a->elements + list_a->length - 1; // last_a_last指针 -> 顺序表a的elements数组尾地址
    ELEM_TYPE* list_b_last = list_b->elements + list_b->length - 1; // last_b_last指针 -> 顺序表b的elements数组尾地址

    // 合并后的表设置属性分配内存
    merged_list->length = list_a->length + list_b->length;  // 长度
    merged_list->capacity = list_a->capacity + list_b->capacity;        // 容量
    merged_list->elements = (ELEM_TYPE*)malloc(merged_list->capacity * sizeof(ELEM_TYPE));  // elements数组分配内存
    if (!merged_list->elements)
    {
        return NON_ALLOCATED;   // 分配失败
    }

    // 执行合并
    ELEM_TYPE* merged_list_cur = merged_list->elements; // merged_list_cur指针 -> 合并后的顺序表的elements数组首地址

    while (list_a_cur <= list_a_last && list_b_cur <=list_b_last)
    {
        // list_a_cur和list_b_cur指向的两个元素, 选择较小的进入merged_list, 对应的cur指针向后移一位, merged_list_cur向后移一位
        if (*list_a_cur <= *list_b_cur)
        {
            *merged_list_cur = *list_a_cur;
            list_a_cur++;
        }
        else
        {
            *merged_list_cur = *list_b_cur;
            list_b_cur++;
        }
        merged_list_cur++;
    }

    // list_a剩余元素加到merged_list尾部(如果list_a有剩余)
    while (list_a_cur <= list_a_last)
    {
        *merged_list_cur = *list_a_cur;
        merged_list_cur++;
        list_a_cur++;
    }

    // list_b剩余元素加到merged_list尾部(如果list_b有剩余)
    while (list_b_cur <= list_b_last)
    {
        *merged_list_cur = *list_b_cur;
        merged_list_cur++;
        list_b_cur++;
    }

    return OK;
}


/*!
 * @brief **顺序表打印**
 * @param seq_list 顺序表(指针)
 * @note
 * 顺序表打印
 * ---------
 * ---------
 * 循环打印顺序表各元素
 */
void SeqListPrint(seq_list_t* seq_list)
{
    for (int i = 0; i < seq_list->length; i++)
    {
        printf("%d ", seq_list->elements[i]);
    }
}

• main.c

#include <stdio.h>
#include <stdlib.h>
#include "seq_list.h"



/*!
 * @brief **比较函数**
 * @param item1 **元素1**
 * @param item2 **元素2**
 * @return **结果**
 * @note
 * 比较函数
 * -------
 * -------
 * **if** 元素1 > 元素2 : \n
 * &emsp; 返回1 \n
 * **else if** 元素1 = 元素2 : \n
 * &emsp; 返回0 \n
 * **else if** 元素1 < 元素2 : \n
 * &emsp; 返回-1 \n
 */
int compare(ELEM_TYPE item1, ELEM_TYPE item2)
{
    if (item1 > item2)
    {
        return 1;
    }
    else if (item1 == item2)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}


/*!
 * @brief **测试线性表插入**
 * @note
 * 测试线性表插入
 * ------------
 * ------------
 *
 */
void TestSeqListInsert()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                       测试顺序表的插入                       |\n");

    seq_list_t* seq_list = (seq_list_t*)malloc(sizeof(seq_list_t));
    SeqListInit(seq_list);

    printf("初始化顺序表sqList完成\n\n");

    ELEM_TYPE elem1 = 1;
    ELEM_TYPE elem2 = 2;
    ELEM_TYPE elem3 = 3;

    printf("在位置1前边插入elem1: %d\n", elem1);
    SeqListInsert(seq_list, 1, elem1);
    printf("在位置2前边插入elem2: %d\n", elem2);
    SeqListInsert(seq_list, 2, elem2);
    printf("在位置3前边插入elem3: %d\n", elem3);
    SeqListInsert(seq_list, 3, elem3);

    printf("\n打印顺序表sqList:\n");
    SeqListPrint(seq_list);

    printf("\n-------------------------------------------------------------\n\n");
}


/*!
 * @brief **测试线性表删除**
 * @note
 * 测试线性表删除
 * ------------
 * ------------
 */
void TestSeqListDelete()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                       测试顺序表的删除                       |\n");

    seq_list_t* seq_list = (seq_list_t*)malloc(sizeof(seq_list_t));
    SeqListInit(seq_list);

    printf("初始化顺序表sqList完成\n\n");

    ELEM_TYPE elem1 = 1;
    ELEM_TYPE elem2 = 3;
    ELEM_TYPE elem3 = 5;

    printf("在位置1前边插入elem1: %d\n", elem1);
    SeqListInsert(seq_list, 1, elem1);
    printf("在位置2前边插入elem2: %d\n", elem2);
    SeqListInsert(seq_list, 2, elem2);
    printf("在位置3前边插入elem3: %d\n", elem3);
    SeqListInsert(seq_list, 3, elem3);

    printf("\n删除位置2的元素\n");
    ELEM_TYPE delete_item;
    SeqListDelete(seq_list, 2, &delete_item);
    printf("被删除的元素值: %d\n", delete_item);

    printf("\n打印顺序表sqList:\n");
    SeqListPrint(seq_list);

    printf("\n-------------------------------------------------------------\n\n");
}


/*!
 * @brief **测试线性表查找**
 * @note
 * 测试线性表查找
 * ------------
 * ------------
 */
void TestSeqListLocate()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                       测试顺序表的查找                      |\n");

    seq_list_t* seq_list = (seq_list_t*)malloc(sizeof(seq_list_t));
    SeqListInit(seq_list);

    printf("初始化顺序表sqList完成\n\n");

    ELEM_TYPE elem1 = 1;
    ELEM_TYPE elem2 = 3;
    ELEM_TYPE elem3 = 5;

    printf("在位置1前边插入elem1: %d\n", elem1);
    SeqListInsert(seq_list, 1, elem1);
    printf("在位置2前边插入elem2: %d\n", elem2);
    SeqListInsert(seq_list, 2, elem2);
    printf("在位置3前边插入elem3: %d\n", elem3);
    SeqListInsert(seq_list, 3, elem3);

    ELEM_TYPE elem0 = 4;
    int pos0 = SeqListLocate(seq_list, elem0, compare); // 查找elem0的位置
    int pos1 = SeqListLocate(seq_list, elem1, compare); // 查找elem1的位置

    printf("\n");

    printf("elem0:%d在顺序表中的位置:%d\n", elem0, pos0);   // 位置0表示没有该元素
    printf("elem1:%d在顺序表中的位置:%d\n", elem1, pos1);

    printf("\n-------------------------------------------------------------\n\n");
}


/*!
 * @brief **测试线性表合并**
 * @note
 * 测试线性表合并
 * ------------
 * ------------
 */
void TestSeqListMerge()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                       测试顺序表的合并                       |\n");

    ELEM_TYPE elements[6] = { 1, 2, 3, 4, 5, 6 };

    seq_list_t* seq_list_a = (seq_list_t*)malloc(sizeof(seq_list_t));
    SeqListInit(seq_list_a);
    seq_list_t* seq_list_b = (seq_list_t*)malloc(sizeof(seq_list_t));
    SeqListInit(seq_list_b);

    // 顺序表a插入3个元素
    SeqListInsert(seq_list_a, 1, elements[0]);
    SeqListInsert(seq_list_a, 2, elements[2]);
    SeqListInsert(seq_list_a, 3, elements[4]);
    // 顺序表b插入3个元素
    SeqListInsert(seq_list_b, 1, elements[1]);
    SeqListInsert(seq_list_b, 2, elements[3]);
    SeqListInsert(seq_list_b, 3, elements[5]);

    printf("顺序表a: ");
    SeqListPrint(seq_list_a);
    printf("\n");
    printf("顺序表b: ");
    SeqListPrint(seq_list_a);
    printf("\n");

    seq_list_t* merged_list = (seq_list_t*)malloc(sizeof(seq_list_t));
    SeqListInit(merged_list);

    SeqListMerge(seq_list_a, seq_list_b, merged_list);

    printf("合并后的顺序表merged: list: \n");
    SeqListPrint(merged_list);

    printf("\n-------------------------------------------------------------\n\n");
}



int main()
{
    printf("你好!顺序表\n");
    TestSeqListInsert();

    TestSeqListDelete();

    TestSeqListLocate();

    TestSeqListMerge();
    return 0;
}

运行结果

你好!顺序表

|------------------------ CyberDash ------------------------|
|                       测试顺序表的插入                       |
初始化顺序表sqList完成

在位置1前边插入elem1: 1
在位置2前边插入elem2: 2
在位置3前边插入elem3: 3

打印顺序表sqList:
1 2 3
-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                       测试顺序表的删除                       |
初始化顺序表sqList完成

在位置1前边插入elem1: 1
在位置2前边插入elem2: 3
在位置3前边插入elem3: 5

删除位置2的元素
被删除的元素值: 3

打印顺序表sqList:
1 5
-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                       测试顺序表的查找                      |
初始化顺序表sqList完成

在位置1前边插入elem1: 1
在位置2前边插入elem2: 3
在位置3前边插入elem3: 5

elem0:4在顺序表中的位置:0
elem1:1在顺序表中的位置:1

-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                       测试顺序表的合并                       |
顺序表a: 1 3 5
顺序表b: 1 3 5
合并后的顺序表merged: list:
1 2 3 4 5 6
-------------------------------------------------------------


Process returned 0 (0x0)   execution time : 0.099 s
Press any key to continue.