线性表数据结构C代码实现

---

文章目录

线性表数据结构C代码实现前言一、代码分层二、代码1.APP业务层2.公共模块代码3.顺序存储结构驱动模块代码4.单向链表存储结构驱动模块代码5.双向链表存储结构驱动模块代码 总结

---

前言

主要是通过C语言代码实现线性表的顺序存储、单向链表存储和双向链表存储。理论知识不详细叙述

---

一、代码分层

本章需要实现三种线性表存储结构，分别为顺序存储结构、单向链表存储结构和双向链表存储结构。 代码主要分为五大块：分别是app程序（业务代码）、顺序存储结构驱动模块、单向链表存储结构驱动模块、双向链表存储结构模块和共用模块。交互过程如下图所示。

二、代码

1.APP业务层

代码如下：这里主要通过简单的shell交互进行验证代码,通过修改main函数里的存储类型字段可以调用相对应的底层驱动。

/**@file * @note Li Haoqin. All rights reserved * @brief app代码 * *@author lihaoqin *@date 2020/10/08 * *@version * data |version |author |message * :----- |:----- |:----- |:---- * 2020/10/08 |V1.0.0 |lihaoqin |创建代码文档 *@warning */ #include <stdio.h> #include "interface.h" typedef enum { LIST_CLEAR = 0, LIST_INSERT, LIST_DELETE, LIST_GET_DATA, LIST_GET_LENGTH, LIST_SHOW, MAX_LIST_OPT } LIST_OPT; typedef enum { LIST_TYPE_SEQUENTIAL = 0, LIST_TYPE_SGL_LINK, LIST_TYPE_DOUBLE_LINK, MAX_LIST_TYPE } LIST_TYPE; typedef struct { LIST_TYPE list_type; /**< 存储类型 */ LINEAL_TABLE_FUNC func; /**< 操作函数集 */ void *handle; /**< 访问句柄 */ } LINEAR_CTRL; static LINEAR_CTRL lineal_ctrl; int main(void) { int opt = 0; int ret = 0; int idx = 0; ELEMTYPE data; LIST_TYPE list_type = LIST_TYPE_SGL_LINK; /**< 存储类型为顺序结构存储 */ LINEAR_CTRL *ctrl = &lineal_ctrl; if (LIST_TYPE_SEQUENTIAL == list_type) { ret = sequential_list_get_func(&ctrl->func); if (0 != ret) { LOG("%s[%d] sequential_list_get_func failed with ret %d\n", __FUNCTION__, __LINE__, ret); return -1; } } else if (LIST_TYPE_SGL_LINK == list_type) { ret = sgl_link_list_get_func(&ctrl->func); if (0 != ret) { LOG("%s[%d] sgl_link_list_get_func failed with ret %d\n", __FUNCTION__, __LINE__, ret); return -1; } } else if (LIST_TYPE_DOUBLE_LINK == list_type) { //后续实现 } ret = ctrl->func.create_list(&ctrl->handle); if (0 != ret) { LOG("%s[%d] create_list failed with ret %d\n", __FUNCTION__, __LINE__, ret); return -2; } ret = ctrl->func.init_list(ctrl->handle); if (0 != ret) { LOG("%s[%d] init_list failed with ret %d\n", __FUNCTION__, __LINE__, ret); return -3; } while (1) { LOG("\n\n==================================\n"); LOG("========= program start ========\n"); LOG("======== input your opt> ========\n"); LOG("== 0.clear list 1.insert date ==\n"); LOG("== 2.delete date 3.get date ==\n"); LOG("== 4.get length 5.show list ==\n"); scanf("%d", &opt); switch(opt) { case LIST_CLEAR: ret = ctrl->func.clear_list(ctrl->handle); if (0 != ret) { LOG("%s[%d] clear_list failed with ret %d\n", __FUNCTION__, __LINE__, ret); } else { LOG("%s[%d] clear_list success\n", __FUNCTION__, __LINE__); } break; case LIST_INSERT: LOG("intput insert pos idx:"); scanf("%d", &idx); LOG("intput insert data:"); scanf("%d", &data); ret = ctrl->func.insert_elem(ctrl->handle, idx, data); if (0 != ret) { LOG("%s[%d] insert_elem failed with ret %d\n", __FUNCTION__, __LINE__, ret); } else { LOG("%s[%d] insert_elem success, idx %d, data %d\n", __FUNCTION__, __LINE__, idx, data); } break; case LIST_DELETE: LOG("intput delete pos idx:"); scanf("%d", &idx); ret = ctrl->func.delete_elem(ctrl->handle, idx, &data); if (0 != ret) { LOG("%s[%d] delete_elem failed with ret %d\n", __FUNCTION__, __LINE__, ret); } else { LOG("%s[%d] delete_elem success, idx %d, data %d\n", __FUNCTION__, __LINE__, idx, data); } break; case LIST_GET_DATA: LOG("intput get data pos idx:"); scanf("%d", &idx); ret = ctrl->func.get_elem(ctrl->handle, idx, &data); if (0 != ret) { LOG("%s[%d] get_elem failed with ret %d\n", __FUNCTION__, __LINE__, ret); } else { LOG("%s[%d] get_elem success, idx %d, data %d\n", __FUNCTION__, __LINE__, idx, data); } break; case LIST_GET_LENGTH: ret = ctrl->func.get_list_length(ctrl->handle, &data); if (0 != ret) { LOG("%s[%d] get_elem failed with ret %d\n", __FUNCTION__, __LINE__, ret); } else { LOG("%s[%d] get_elem success, length %d\n", __FUNCTION__, __LINE__, data); } break; case LIST_SHOW: ret = ctrl->func.show_list(ctrl->handle); if (0 != ret) { LOG("%s[%d] show_list failed with ret %d\n", __FUNCTION__, __LINE__, ret); } else { LOG("%s[%d] show_list success\n", __FUNCTION__, __LINE__); } break; default: LOG("%s[%d] opt %d error\n", __FUNCTION__, __LINE__, opt); break; } } return 0; }

2.公共模块代码

代码如下：主要是业务层通过这里获取驱动层的函数集。

/**@file interface.h * @note Li Haoqin. All rights reserved * @brief 交互头文件 * *@author lihaoqin *@date 2020/10/08 * *@version * data |version |author |message * :----- |:----- |:----- |:---- * 2020/10/08 |V1.0.0 |lihaoqin |创建代码文档 *@warning */ #ifndef __INTERFACE_H_ #define __INTERFACE_H_ #ifdef __cplusplus extern "C" { #endif #define LOG printf typedef int ELEMTYPE; /*！函数操作集函数 */ typedef struct { int (*create_list)(void **handle); int (*init_list)(void *handle); int (*clear_list)(void *handle); int (*insert_elem)(const void *handle, int idx, ELEMTYPE e); int (*delete_elem)(const void *handle, int idx, ELEMTYPE *e); int (*get_elem)(const void * handle, int idx, ELEMTYPE *e); int (*get_list_length)(const void *handle, int *length); int (*show_list)(const void * handle); } LINEAL_TABLE_FUNC; int sequential_list_get_func(LINEAL_TABLE_FUNC *func); /**< 顺序存储结构函数集获取函数 */ int sgl_link_list_get_func(LINEAL_TABLE_FUNC *func); /**< 单向链表存储结构函数集获取函数 */ //TODO双向链表函数集获取函数 #ifdef __cplusplus } #endif #endif

3.顺序存储结构驱动模块代码

代码如下：

/**@file sequential.c * @note Li Haoqin. All rights reserved * @brief 顺序存储驱动模块源文件 * *@author lihaoqin *@date 2020/10/08 * *@version * data |version |author |message * :----- |:----- |:----- |:---- * 2020/10/08 |V1.0.0 |lihaoqin |创建代码文档 *@warning */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "interface.h" /*! 线性表顺序存储结构驱动接口 */ #define MAX_SIZE (20u) typedef struct { int is_init; /**< 是否初始化 */ int cur_length; /**< 当前数据个数 */ ELEMTYPE data[MAX_SIZE]; /**< 数据元素 */ } SQ_LIST, LIST; /** 创建列表 * param: handle 获取创建的列表句柄 * return：0：成功，其他：失败 */ static int create_list(void **handle) { LIST *list = NULL; if (NULL == handle) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } list = (LIST *)malloc(sizeof(LIST)); if (NULL == list) { LOG("%s[%d] malloc failed\n", __FUNCTION__, __LINE__); return -2; } *(LIST **)handle = list; return 0; } /** 初始化列表 * param: handle 列表句柄 * return：0：成功，其他：失败 */ static int init_list(void *handle) { LIST *list = (LIST *)handle; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } memset(list, 0, sizeof(LIST)); list->is_init = 1; return 0; } /** 清理列表 * param: handle 列表句柄 * return：0：成功，其他：失败 */ static int clear_list(void *handle) { LIST *list = (LIST *)handle; int i = 0; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } for (i = 0; i < list->cur_length; i++) { list->data[i] = 0; } list->cur_length = 0; return 0; } /** 获取元素 * param: handle 列表句柄 * param: idx 元素索引 * param: e 返回的元素 * return：0：成功，其他：失败 */ static int get_elem(const void *handle, int idx, ELEMTYPE *e) { LIST *list = (LIST *)handle; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } if (idx >= list->cur_length) { LOG("%s[%d] idx limit cur length, idx %d, cur_length %d\n", __FUNCTION__, __LINE__, idx, list->cur_length); return -3; } *e = list->data[idx]; return 0; } /** 插入元素 * param: handle 列表句柄 * param: idx 元素索引 * param: e 插入的元素 * return：0：成功，其他：失败 */ static int insert_elem(const void *handle, int idx, ELEMTYPE e) { LIST *list = (LIST *)handle; int i = 0; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } if (MAX_SIZE == list->cur_length) { LOG("%s[%d] list full, max_length %d, cur_length %d\n", __FUNCTION__, __LINE__, MAX_SIZE, list->cur_length); return -3; } if (idx > list->cur_length) /**< idx为0表示插在最前面，idx如果为cur_length表示插在尾部 */ { LOG("%s[%d] idx limit cur length, idx %d, cur_length %d\n", __FUNCTION__, __LINE__, idx, list->cur_length); return -4; } for (i = list->cur_length; i > idx; i--) { list->data[i] = list->data[i-1]; } list->data[idx] = e; list->cur_length++; return 0; } /** 删除元素 * param: handle 列表句柄 * param: idx 元素索引 * param: e 删除的元素值 * return：0：成功，其他：失败 */ static int delete_elem(const void *handle, int idx, ELEMTYPE *e) { LIST *list = (LIST *)handle; int i = 0; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } if (0 == list->cur_length) { printf("%s[%d] list empty\n", __FUNCTION__, __LINE__); return -3; } if (idx >= list->cur_length) { LOG("%s[%d] idx limit cur length, idx %d, cur_length %d\n", __FUNCTION__, __LINE__, idx, list->cur_length); return -4; } *e = list->data[idx]; for (i = idx; i < (list->cur_length - 1); i++) { list->data[i] = list->data[i+1]; } list->cur_length--; return 0; } /** 获取长度 * param: handle 列表句柄 * param: length 返回的数据长度 * return：0：成功，其他：失败 */ static int get_list_length(const void *handle, int *length) { LIST *list = (LIST *)handle; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } *length = list->cur_length; return 0; } /** 打印列表信息 * param: handle 列表句柄 * return：0：成功，其他：失败 */ static int show_list(const void *handle) { LIST *list = (LIST *)handle; int i = 0; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } for (i= 0; i < list->cur_length; i++) { LOG("idx:%d -> data:%d\n", i, list->data[i]); } LOG("length:%d\n", list->cur_length); return 0; } int sequential_list_get_func(LINEAL_TABLE_FUNC *func) { if (NULL == func) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } func->create_list = create_list; func->init_list = init_list; func->clear_list = clear_list; func->insert_elem = insert_elem; func->delete_elem = delete_elem; func->get_elem = get_elem; func->get_list_length = get_list_length; func->show_list = show_list; return 0; }

4.单向链表存储结构驱动模块代码

/**@file sgl_link.c * @note Li Haoqin. All rights reserved * @brief 单向链表存储驱动模块源文件 * *@author lihaoqin *@date 2020/10/08 * *@version * data |version |author |message * :----- |:----- |:----- |:---- * 2020/10/09 |V1.0.0 |lihaoqin |创建代码文档 *@warning */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "interface.h" typedef struct NODE { ELEMTYPE data; /**< 数据元素 */ struct NODE *next; /**< 下一个元素 */ } NODE; typedef struct { int is_init; /**< 是否初始化 */ int cur_length; /**< 当前数据个数 */ struct NODE *list_head; } LINK_LIST, LIST; /** 创建列表 * param: handle 获取创建的列表句柄 * return：0：成功，其他：失败 */ static int create_list(void **handle) { LIST *list = NULL; if (NULL == handle) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } list = (LIST *)malloc(sizeof(LIST)); if (NULL == list) { LOG("%s[%d] malloc failed\n", __FUNCTION__, __LINE__); return -2; } *(LIST **)handle = list; return 0; } /** 初始化列表 * param: handle 列表句柄 * return：0：成功，其他：失败 */ static int init_list(void *handle) { LIST *list = (LIST *)handle; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } memset(list, 0, sizeof(LIST)); list->is_init = 1; return 0; } /** 获取元素 * param: handle 列表句柄 * param: idx 元素索引 * param: e 返回的元素 * return：0：成功，其他：失败 */ static int get_elem(const void *handle, int idx, ELEMTYPE *e) { LIST *list = (LIST *)handle; int i = 0; NODE *node = NULL; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } if (idx >= list->cur_length) { LOG("%s[%d] idx limit cur length, idx %d, cur_length %d\n", __FUNCTION__, __LINE__, idx, list->cur_length); return -3; } node = list->list_head; for (i = 0; i < list->cur_length; i++) { node = node->next; } if (NULL == node) { LOG("%s[%d] node is null\n", __FUNCTION__, __LINE__); } *e = node->data; return 0; } /** 插入元素 * param: handle 列表句柄 * param: idx 元素索引 * param: e 插入的元素 * return：0：成功，其他：失败 */ static int insert_elem(const void *handle, int idx, ELEMTYPE e) { LIST *list = (LIST *)handle; int i = 0; NODE *node = NULL; NODE *p_cur = list->list_head; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } if (idx > list->cur_length) /**< idx为0表示插在最前面，idx如果为cur_length表示插在尾部 */ { LOG("%s[%d] idx limit cur length, idx %d, cur_length %d\n", __FUNCTION__, __LINE__, idx, list->cur_length); return -3; } node = (NODE *)malloc(sizeof(NODE)); if (NULL == node) { LOG("%s[%d] malloc node failed\n", __FUNCTION__, __LINE__); return -4; } if (0 == idx) { node->data = e; node->next = p_cur; list->list_head = node; } else { while((NULL != p_cur) && (i < (idx - 1))) { p_cur = p_cur->next; i++; } if (NULL == p_cur) { LOG("%s[%d] list error\n", __FUNCTION__, __LINE__); return -5; } node->data = e; node->next = p_cur->next; p_cur->next = node; } list->cur_length++; return 0; } /** 删除元素 * param: handle 列表句柄 * param: idx 元素索引 * param: e 删除的元素值 * return：0：成功，其他：失败 */ static int delete_elem(const void *handle, int idx, ELEMTYPE *e) { LIST *list = (LIST *)handle; int i = 0; NODE *node = NULL; NODE *p_cur = list->list_head; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } if (0 == list->cur_length) { printf("%s[%d] list empty\n", __FUNCTION__, __LINE__); return -3; } if (idx >= list->cur_length) { LOG("%s[%d] idx limit cur length, idx %d, cur_length %d\n", __FUNCTION__, __LINE__, idx, list->cur_length); return -4; } if (0 == idx) { node = p_cur; *e = node->data; list->list_head = list->list_head->next; free(node); list->cur_length--; } else { while ((NULL != p_cur) && (i < (idx - 1))) { p_cur = p_cur->next; i++; } if (NULL == p_cur->next) { LOG("%s[%d] list error\n", __FUNCTION__, __LINE__); return -5; } node = p_cur->next; *e = node->data; p_cur->next = node->next; free(node); list->cur_length--; } return 0; } /** 清理列表 * param: handle 列表句柄 * return：0：成功，其他：失败 */ static int clear_list(void *handle) { LIST *list = (LIST *)handle; ELEMTYPE tmp; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } while (list->cur_length) { delete_elem(handle, 0, &tmp); } return 0; } /** 获取长度 * param: handle 列表句柄 * param: length 返回的数据长度 * return：0：成功，其他：失败 */ static int get_list_length(const void *handle, int *length) { LIST *list = (LIST *)handle; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } *length = list->cur_length; return 0; } /** 打印列表信息 * param: handle 列表句柄 * return：0：成功，其他：失败 */ static int show_list(const void *handle) { LIST *list = (LIST *)handle; int i = 0; NODE *node = list->list_head; if (NULL == list) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } if (0 == list->is_init) { LOG("%s[%d] list is not init\n", __FUNCTION__, __LINE__); return -2; } for (i= 0; i < list->cur_length; i++) { LOG("idx:%d -> data:%d\n", i, node->data); node = node->next; } LOG("length:%d\n", list->cur_length); return 0; } int sgl_link_list_get_func(LINEAL_TABLE_FUNC *func) { if (NULL == func) { LOG("%s[%d] param is null\n", __FUNCTION__, __LINE__); return -1; } func->create_list = create_list; func->init_list = init_list; func->clear_list = clear_list; func->insert_elem = insert_elem; func->delete_elem = delete_elem; func->get_elem = get_elem; func->get_list_length = get_list_length; func->show_list = show_list; return 0; }

5.双向链表存储结构驱动模块代码

//TODO

---

总结

提示：这里对文章进行总结： 本文主要是以代码实现线性表存储结构，因为线性表相对简单。通过多模块驱动的分层思想进行代码编写，这种方式可以方便后续添加驱动，业务代码不怎么需要修改。