-
相关宏定义及数据类型的别名定义
#define LIST_INIT_SIZE 10 // 初始化顺序表的空间分配量 #define LIST_INCREMENT 10 // 顺序表空间用完后的分配增量 #define OK 1 // 函数正常返回 #define ERROR -1 // 函数异常返回 #define EMPTY 0 // 表空 #define NOT_EMPTY 1 // 表不空 typedef int ElemType; // 元素类型 typedef int Status; // 状态(用作返回值类型) typedef int Length; // 长度 typedef int Position; // 位序 -
结构定义
typedef struct { ElemType *elem; // 存储空间基址(首地址) int length; // 已存储的元素个数 int list_size; // 当前分配的存储量(目前可存储元素的个数) } SqList; -
InitList()：构造一个空表
Status InitList_Sq(SqList *L) { // 动态分配存储空间，返回已分配空间的首地址 L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); // 如果分配后返回地址为空 说明分配失败 if (!L->elem) exit(ERROR); L->length = 0; // 空表长度为0 L->list_size = LIST_INIT_SIZE; // 当前分配量即为初始分配量 return OK; } -
DestroyList(): 销毁线性表
Status DestroyList_Sq(SqList *L) { // 如果传入的线性表空间首地址为空 说明初始化时空间分配异常 // 则直接异常终止进程 之后的代码将不被执行 if (!L->elem) exit(EXIT_FAILURE); // 释放 L->elem 指向的内存 free(L->elem); L->elem = NULL; L->length = 0; L->list_size = 0; return OK; } -
ClearList()：重置为空表
Status ClearList_Sq(SqList *L) { if (!L->elem) return ERROR; L->length = 0; return OK; } -
ListEmpty(): 检测该表是否为空
Status ListEmpty_Sq(SqList *L) { return (L->length > 0) ? NOT_EMPTY : EMPTY; } -
GetLength(): 获取顺序表中元素的个数
Length GetLength_Sq(SqList *L) { return L->length; } -
GetElem(): 用 e 返回 L 中下标为 i 的元素的值
Status GetElem_Sq(SqList *L, int i, ElemType *e) { // 若空间分配异常或表中无元素 异常返回 if (!L->elem || L->length < 1) return ERROR; *e = L->elem[i]; return OK; } LocateElem(): 返回表中第一个与 e 值满足关系 compare() 的元素的位序（非下标）
Position LocateElem_Sq(SqList *L, ElemType e, Status((*compare)(ElemType e1, ElemType e2))) {
// 若顺序表为空 返回错误状态
if (ListEmpty_Sq(L) == EMPTY)
return ERROR;
for (int i = 0; i < L->length; ++i) {
// 将第 i 个元素与 e 值作为参数传入 compare()，根据返回值判断是否满足该关系，若是，则返回位序，否则继续往下遍历
if ((*compare)(e, L->elem[i]) == OK)
return i + 1;
else
continue;
}
return 0;
}
-
compare(): 这里使用相等关系表示 compare() 函数
Status Equal(ElemType e1, ElemType e2) { return (e1 == e2) ? OK : ERROR; }- 调用举例
int main() { ... // 返回表中第一个值为 8 的元素的位序 int pos = LocateElem_Sq(&L, 8, Equal); // 例如对于顺序表：{3, 8, 6, 0, 9, 7, 4, 11}，此时 pos 的值应为 2 printf("%d", pos); ... } -
GetKth(): 获取第 k(位序，非下标) 个元素
Status GetKth(SqList *L, int k, ElemType *e) { // 1<=k<=length if (k < 1 || k > L->length) { return ERROR; } else { *e = L->elem[k - 1]; return OK; } } -
PriorElem(): 获取 curElem 的前驱
ElemType PriorElem_Sq(SqList *L, ElemType curElem, ElemType *pre_e) { // 先找到当前元素的位序 int locateRes = LocateElem_Sq(L, curElem, Equal); // ERROR:表空; 1: 位序为1，第1个元素无前驱; 0: 表中未找到当前元素 if (locateRes == ERROR || locateRes == 1 || locateRes == 0) { if (locateRes == 1) { printf("\nERROR: 第一个元素无前驱！"); } else if (locateRes == 0) { printf("\nERROR: 目标元素: %d 不存在！", curElem); } return ERROR; } // 成功找到存在前驱的 curElem else { // 将位序为 locateRes - 1 的元素（即curElem的前驱）值写入 pre_e if (GetKth(L, locateRes - 1, pre_e) != ERROR) { return OK; } else { printf("\nERROR: 未找到指定元素: %d 的前驱！", curElem); return ERROR; } } } -
NextElem(): 获取 curElem 的后继
ElemType NextElem_Sq(SqList *L, ElemType curElem, ElemType *next_e) { int locateRes = LocateElem_Sq(L, curElem, Equal); // ERROR:表空; 1: 位序为length，最后1个元素无后继; 0: 表中未找到当前元素 if (locateRes == ERROR || locateRes == L->length || locateRes == 0) { if (locateRes == L->length) { printf("\nERROR: 最后一个元素无后继！"); } else if (locateRes == 0) { printf("\nERROR: 目标元素: %d 不存在！", curElem); } return ERROR; } else { // 将位序为 locateRes + 1 的元素(即curElem的后继)值写入 next_e if (GetKth(L, locateRes + 1, next_e) != ERROR) { return OK; } else { printf("\nERROR: 未找到指定元素: %d 的前驱！", curElem); return ERROR; } } } -
调用举例：查看表中所有元素的前驱与后继
int main () { ... for (int i = 0; i < L.length; i++) { // cur_e 为当前遍历的元素 ElemType cur_e = L.elem[i]; // pre_e, next_e 分别表示指向前驱和后继元素所占内存空间的地址，均为临时量，用完需要释放 ElemType *pre_e = (ElemType *)malloc(sizeof(ElemType)); ElemType *next_e = (ElemType *)malloc(sizeof(ElemType)); // 将 cur_e 的前驱元素的值写入 pre_e if (PriorElem_Sq(&L, cur_e, pre_e) == ERROR) { *pre_e = -1; } // 将 cur_e 的后继元素的值写入 next_e if (NextElem_Sq(&L, cur_e, next_e) == ERROR) { *next_e = -1; } // 输出 cur_e, pre_e, next_e printf("\npreElem: %d\ncurElem: %d\nnextElem: %d\n", *pre_e, cur_e, *next_e); // 释放动态空间 free(pre_e); free(next_e); } ... } -
ListInsert(): 在表中第 i 个元素之前插入元素 e
Status ListInsert_Sq(SqList *L, int i, ElemType e) { // i = 0: 在表头插入元素， i = length: 在表尾插入元素，均合法，除此之外的都不合法 if (i < 0 || i > L->length) { return ERROR; } // 若空间不足，需增大空间分配量 if (L->length >= L->list_size) { ElemType *newbase; newbase = (ElemType*)realloc(L->elem, (LIST_INIT_SIZE + LIST_INCREMENT) * sizeof(ElemType)); if (!newbase) exit(EXIT_FAILURE); L->elem = newbase; L->list_size += LIST_INCREMENT; } // 从被插入的元素位置起，至表尾元素止，整体移动 ElemType *q = &L->elem[i]; ElemType *p = &L->elem[L->length - 1]; // 从后向前逐个进行值的迁移 为新值的插入腾出一个元素所需的空间 while (p >= q) { *(p + 1) = *p; --p; } *q = e; // 给目标插入位置赋值 ++L->length; return OK; } -
ListDelete(): 删除指定下标的元素，并返回它的值
Status ListDelete_Sq(SqList *L, int i, ElemType *e) { if (ListEmpty_Sq(L) == EMPTY) return ERROR; if (i < 0 || i > L->length - 1) return ERROR; *e = L->elem[i]; // 目标删除元素的值 ElemType *q = &L->elem[i + 1]; // 目标删除位置的后一个 ElemType *p = &L->elem[L->length - 1]; // 表尾位置 // 从前往后进行元素的逐个迁移 while (q <= p) { *(q - 1) = *q; q++; } --L->length; return *e; } -
ListTraverse(): 对表中每个元素进行遍历
Status ListTraverse_Sq(SqList *L, Status((*visit)(ElemType *curElem))) { if (ListEmpty_Sq(L) == EMPTY) return ERROR; for (int i = 0; i < L->length; ++i) { if ((*visit)(&L->elem[i]) == ERROR) { exit(EXIT_FAILURE); } } printf("\n"); return OK; } -
visit(): 这里使用打印输出元素的值表示对单个元素的访问
Status PrintElem(ElemType *curElem) { if (!curElem) return ERROR; printf("%d ", *curElem); return OK; }- 调用举例
int main() { ... // 以 PrintElem 作为 Visit 方法遍历顺序表 L，程序将打印输出 L 中每个元素的值 ListTraverse_Sq(&L, PrintElem); ... } -
AssignElem(): 自定义表长并为各元素赋值
Status AssignElem_Sq(SqList *L, int *assign_size) { // 传入的表还未分配内存空间，错误 if (!L->elem) exit(EXIT_FAILURE); printf("Input the assignment size: "); // 欲赋值的个数，即表长 scanf_s("%d", assign_size, 1); // 欲赋值的个数大于当前已有的空间，错误 if (*assign_size > L->list_size) exit(EXIT_FAILURE); // 依次为各元素赋值 for (int i = 0; i < *assign_size; ++i) { scanf_s("%d", &L->elem[i], 1); L->length++; } return OK; }
