2193 字
11 分钟
数据结构C(1) 线性表的实现
已完成std::vector的基本功能, 包括空间倍增, 插入删除, 查找, 查前驱, 查后继等等.
// by ykindred, 2025.9.15#ifndef DATA_STRUCTURE_LIST_H#define DATA_STRUCTURE_LIST_H
#include <malloc.h>#include <stdbool.h>#define OK 0#define ERROR (-1)#define OVERFLOW (-2)typedef int status;typedef u_int64_t size_t;typedef int elem_t;typedef struct{ elem_t *arr; size_t size; size_t space;} ContList;void myAssert(bool check, const char *prompt, status s);void *myMalloc(size_t size);void *myRealloc(void *p, size_t size);ContList *InitList();void ListExpand(ContList *list, size_t need);ContList *InitListSize(size_t size);ContList *InitListSizeWith(size_t size, elem_t e);void CheckListExist(ContList *L);ContList *DestroyList(ContList *L);ContList *ClearList(ContList *L);bool ListEmpty(ContList *L);size_t ListLength(ContList *L);void CheckOverflow(size_t idx, size_t lowBound, size_t uppBound);elem_t GetItem(ContList *L, size_t i);elem_t *LocateElem(ContList *L, elem_t e);elem_t *PriorElem(ContList *L, elem_t cur_e);elem_t *NextElem(ContList *L, elem_t cur_e);ContList *ListAppend(ContList *L, elem_t e);ContList *ListInsert(ContList *L, size_t m, elem_t e);ContList *ListDelete(ContList *L, size_t m);
#endif //DATA_STRUCTURE_LIST_H// by ykindred, 2025.9.15#include <malloc.h>#include <stdbool.h>#include <string.h>#include <stdlib.h>#include <assert.h>#include "list.h"#define INITIAL_LIST_SPACE 4#define MAX_SIZE (size_t)1e9#define EXPAND_TIMES 2
void myAssert(bool check, const char *prompt, status s) { if (!check) { fprintf(stderr, "%s\n", prompt); // 错误信息直接输出到stderr exit(s); }} // 封装一个好用的, 逻辑类似python的assert
void *myMalloc(size_t size) { void *p = malloc(size); myAssert(p != NULL, "ERROR: list malloc failed!", ERROR); // 每次malloc都检查, 不如封装起来 return p;}void *myRealloc(void *p, size_t size) { void *newArr = realloc(p, size); myAssert(newArr != NULL, "ERROR: realloc failed!", ERROR); return newArr;} // 既然每次malloc和realloc都要检查, 不如封装起来
ContList *InitList() { // 初始化一个有序线性表并返回, 线性表的空间默认为4 // 用法: ContList *L = InitList(); // 创建空的有序线性表L ContList *list = NULL; list = myMalloc(sizeof(ContList)); list->arr = NULL; list->arr = myMalloc(INITIAL_LIST_SPACE * sizeof(elem_t)); list->space = INITIAL_LIST_SPACE; list->size = 0; return list;} // 初始化列表
void ListExpand(ContList *list, size_t need) { myAssert(list != NULL, "ERROR: invalid list in ListExpand()!", ERROR); myAssert(need <= MAX_SIZE, "OVERFLOW: memory needed is too large!", OVERFLOW); assert(list != NULL); // 纯粹为了消除warning, release版本中会自动失效 size_t sp = list->space; while (sp < need) { sp *= EXPAND_TIMES; } // 保证扩容均摊O(1) list->arr = myRealloc(list->arr, sp * sizeof(elem_t)); list->space = sp;}
ContList *InitListSize(size_t size) { // 初始化一个指定大小的有序线性表, 用0填充, 并返回 // 用法: ContList *A = InitListSize(20); // 指定L的大小为20 return InitListSizeWith(size, 0);} // 初始化指定大小列表
ContList *InitListSizeWith(size_t size, elem_t e) { // 初始化一个指定大小的有序线性表, 用e填充, 并返回 // 用法: ContList *L = InitListSizeWith(20, 6); // 指定L的大小为20, 并将全部元素填充为6 ContList *list = InitList(); ListExpand(list, size); list->size = size; for (int i = 0; i < list->size; i++) { list->arr[i] = e; } return list;} // 初始化指定大小列表并填充
void CheckListExist(ContList *L) { // 查看列表是否存在, 不存在则报错. myAssert(L != NULL, "ERROR: list does not exist!", ERROR);}
ContList *DestroyList(ContList *L) { // 若线性表L存在, 销毁线性表L // 用法: ContList *L = InitList(); L = DestroyList(L); // 此时L指向NULL CheckListExist(L); free(L->arr); free(L); return NULL;} // 销毁列表
ContList *ClearList(ContList *L) { // 若线性表L存在, 将L置空 // 用法: ContList* L = InitList(); L = ClearList(L); // 此时L为空表 CheckListExist(L); L->size = 0; // 这里为什么不free(L->arr)节省空间, 我认为既然L->arr的大小达到过size, 那么即便它被置空了, 也有达到size的潜力, 不置空可以省下O(n)的时间复杂度. // 正常的项目里应该不会出现一个先储存1e8量级数据, 置空后只储存十几个数据的线性表, 即使有也应该先destroy后再创建. return L;} // 清空列表
ContList *ClearListWithFree(ContList *L) { // 保留free(L->arr)的选项 CheckListExist(L); free(L->arr); L->size = 0; L->arr = myMalloc(INITIAL_LIST_SPACE * sizeof(elem_t)); L->space = INITIAL_LIST_SPACE; return L;}
bool ListEmpty(ContList *L) { // 若线性表存在, 其为空返回true, 不为空返回false // 用法: ContList* L = InitList(); if (ListEmpty(L)) print("true"); // true CheckListExist(L); return L->size == 0;} // 列表是否为空
size_t ListLength(ContList *L) { // 若线性表存在, 返回其大小 // 用法: ContList* L = InitListSize(20); printf("%d", ListLength(L)); // 20 CheckListExist(L); return L->size;} // 列表大小
void CheckOverflow(size_t idx, size_t lowBound, size_t uppBound) { // 检测索引是否超限 myAssert(idx <= uppBound && idx >= lowBound, "OVERFLOW: index overflow!", OVERFLOW); // ULL比较, 应该不会出现问题.}
elem_t GetItem(ContList *L, size_t i) { // 若线性表存在, 获取其第i个元素(索引从1开始), 若i越界则报错. // 用法: elem_t val = GetItem(L, 4); // 获取L的第4个元素 CheckListExist(L); CheckOverflow(i, 1, L->size); return (L->arr)[i - 1];} // 获取元素
elem_t *LocateElem(ContList *L, elem_t e) { // 若线性表存在, 返回指向L中第一个与e相同的数组元素的指针, 若不存在这样的元素返回NULL. CheckListExist(L); for (size_t i = 0; i < L->size; i++) { // 遍历, uint作为循环条件时一定要注意符号(因为-1U = UMAX) if (L->arr[i] == e) { return &L->arr[i]; } } return NULL;} // 定位元素
elem_t *PriorElem(ContList *L, elem_t cur_e) { // 若线性表存在, 查找元素cur_e并返回指向前一个元素的指针, 若cur_e不存在或其后继不存在则返回NULL. // 用法: 同上 CheckListExist(L); for (size_t i = 1; i < L->size; i++) { // uint作为循环条件时一定要注意符号(因为-1U = UMAX) if (L->arr[i] == cur_e) { return &L->arr[i - 1]; } } return NULL;} // 查元素前驱
elem_t *NextElem(ContList *L, elem_t cur_e) { // 若线性表存在, 查找元素cur_e并返回指向后一个元素的指针, 若cur_e不存在或其后继不存在则返回NULL. // 用法: 略 CheckListExist(L); if (ListEmpty(L)) { // 这里注意不能删掉, L->size类型是uint, 若0-1后, 反而会变成UMAX, 会出大问题. return NULL; } for (size_t i = 0; i < L->size - 1; i++) { // i遍历到size-2即可, 因为最后一个元素的后继必然不存在 if (L->arr[i] == cur_e) { return &L->arr[i + 1]; } } return NULL;} // 查元素后继
ContList *ListAppend(ContList *L, elem_t e) { // 若线性表存在, 在其后端补充元素e. // 用法: L = ListAppend(L, e); CheckListExist(L); myAssert(L->space >= L->size, "ERROR: unexpected list size and list space!", ERROR); if (L->space == L->size) { // 需要扩容1 ListExpand(L, L->size + 1); } L->arr[L->size] = e; L->size++; return L;}
ContList *ListInsert(ContList *L, size_t m, elem_t e) { // 若线性表存在, 在L中第i个位置(索引从1开始)前插入数据e, L的长度倍增. // 以下实现逻辑: 1. append任意一个元素; 2. 从最后一位逆序到m+1, arr[i] = arr[i - 1]; 3. arr[m] = e // 考虑特殊情况: 1. 空表; 2. m本身是最后一位 // 用法: L = ListInsert(L, m, e); CheckListExist(L); CheckOverflow(m, 1, L->size + 1); if (ListEmpty(L)) { // 空表 L = ListAppend(L, e); return L; } m -= 1; // 变成索引, 方便使用 L = ListAppend(L, 0); // 注意这里size++了 for (size_t i = L->size - 1; i > m; i--) { // 注意最后一位是size - 1 L->arr[i] = L->arr[i - 1]; } // m本身是最后一位的情况会自动处理 L->arr[m] = e; return L;}
ContList *ListDelete(ContList *L, size_t m) { // 若线性表存在, 删除L中第i个位置(索引从1开始)的元素. // 用法: L = ListDelete(L, m); // 以下实现逻辑: 从位置m到末尾, arr[i] = arr[i + 1]., 记得size-- CheckListExist(L); CheckOverflow(m, 1, L->size); m -= 1; for (size_t i = m; i < L->size - 1; i++) { L->arr[i] = L->arr[i + 1]; } L->size--; return L;}
// 以下函数不需要, 有需求的时候可以手动用for循环遍历/*void TraverseList(ContList *L, void (*func)(void *, ...)) { // 遍历函数, 函数指针func作为参数传入 for (int i = 0; i < L->size; i++) { ... }}*/// 以下为GPT5-mini提供的测试程序
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <sys/wait.h>#include <unistd.h>#include "list.h"
#define TEST_ASSERT(cond, msg) \ if (!(cond)) { printf("FAILED: %s\n", msg); return 1; } else { printf("PASSED: %s\n", msg); }
#define TEST_SAFE(func, desc) do { \ pid_t pid = fork(); \ if (pid == 0) { \ /* 子进程执行测试 */ \ func; \ exit(0); \ } else { \ int status; \ waitpid(pid, &status, 0); \ if (WIFEXITED(status) && WEXITSTATUS(status) == 0) { \ printf("PASSED (safe): %s\n", desc); \ } else { \ printf("FAILED (safe): %s\n", desc); \ } \ } \} while(0)
void test_overflow_access() { ContList *L = InitList(); ListAppend(L, 1); GetItem(L, 2); // 越界访问，应触发myAssert}
void test_prior_next_null() { ContList *L = InitList(); ListAppend(L, 10); PriorElem(L, 10); // 前驱不存在，应返回NULL NextElem(L, 10); // 后继不存在，应返回NULL DestroyList(L);}
int main() { printf("=== 完全自动化安全测试开始 ===\n");
// 基础功能测试 ContList *L = InitList(); TEST_ASSERT(L != NULL, "初始化列表"); TEST_ASSERT(ListEmpty(L), "列表为空");
for (int i = 1; i <= 5; i++) ListAppend(L, i*10); TEST_ASSERT(ListLength(L) == 5, "添加元素长度为5"); TEST_ASSERT(GetItem(L,1)==10, "获取第1个元素为10"); TEST_ASSERT(GetItem(L,5)==50, "获取第5个元素为50");
L = ListInsert(L,3,99); TEST_ASSERT(GetItem(L,3)==99, "插入99到第3位"); L = ListDelete(L,2); TEST_ASSERT(GetItem(L,2)==99, "删除第2位后第2位为99");
elem_t *p = LocateElem(L,99); TEST_ASSERT(p && *p==99, "LocateElem找到99"); p = LocateElem(L,1000); TEST_ASSERT(p==NULL, "LocateElem找不到1000");
elem_t *prev = PriorElem(L,99); elem_t *next = NextElem(L,99); TEST_ASSERT(prev && *prev==10, "99前驱为10"); TEST_ASSERT(next && *next==30, "99后继为30");
// 安全性边界测试 TEST_SAFE(test_overflow_access, "越界访问GetItem触发myAssert"); TEST_SAFE(test_prior_next_null, "前驱/后继不存在返回NULL安全测试");
// 清空和销毁 L = ClearList(L); TEST_ASSERT(ListEmpty(L), "清空列表"); L = DestroyList(L); TEST_ASSERT(L==NULL, "销毁列表");
printf("=== 完全自动化安全测试结束 ===\n"); return 0;} 数据结构C(1) 线性表的实现
https://fuwari.vercel.app/posts/数据结构c1-线性表的实现/