-
相關(guān)宏定義及數(shù)據(jù)類型的別名定義
#define LIST_INIT_SIZE 10 // 初始化順序表的空間分配量 #define LIST_INCREMENT 10 // 順序表空間用完后的分配增量 #define OK 1 // 函數(shù)正常返回 #define ERROR -1 // 函數(shù)異常返回 #define EMPTY 0 // 表空 #define NOT_EMPTY 1 // 表不空 typedef int ElemType; // 元素類型 typedef int Status; // 狀態(tài)(用作返回值類型) typedef int Length; // 長(zhǎng)度 typedef int Position; // 位序 -
結(jié)構(gòu)定義
typedef struct { ElemType *elem; // 存儲(chǔ)空間基址(首地址) int length; // 已存儲(chǔ)的元素個(gè)數(shù) int list_size; // 當(dāng)前分配的存儲(chǔ)量(目前可存儲(chǔ)元素的個(gè)數(shù)) } SqList; -
InitList()：構(gòu)造一個(gè)空表
Status InitList_Sq(SqList *L) { // 動(dòng)態(tài)分配存儲(chǔ)空間猛蔽，返回已分配空間的首地址 L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); // 如果分配后返回地址為空 說(shuō)明分配失敗 if (!L->elem) exit(ERROR); L->length = 0; // 空表長(zhǎng)度為0 L->list_size = LIST_INIT_SIZE; // 當(dāng)前分配量即為初始分配量 return OK; } -
DestroyList(): 銷毀線性表
Status DestroyList_Sq(SqList *L) { // 如果傳入的線性表空間首地址為空 說(shuō)明初始化時(shí)空間分配異常 // 則直接異常終止進(jìn)程 之后的代碼將不被執(zhí)行 if (!L->elem) exit(EXIT_FAILURE); // 釋放 L->elem 指向的內(nèi)存 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(): 檢測(cè)該表是否為空
Status ListEmpty_Sq(SqList *L) { return (L->length > 0) ? NOT_EMPTY : EMPTY; } -
GetLength(): 獲取順序表中元素的個(gè)數(shù)
Length GetLength_Sq(SqList *L) { return L->length; } -
GetElem(): 用 e 返回 L 中下標(biāo)為 i 的元素的值
Status GetElem_Sq(SqList *L, int i, ElemType *e) { // 若空間分配異常或表中無(wú)元素 異常返回 if (!L->elem || L->length < 1) return ERROR; *e = L->elem[i]; return OK; } LocateElem(): 返回表中第一個(gè)與 e 值滿足關(guān)系 compare() 的元素的位序（非下標(biāo)）
Position LocateElem_Sq(SqList *L, ElemType e, Status((*compare)(ElemType e1, ElemType e2))) {
// 若順序表為空 返回錯(cuò)誤狀態(tài)
if (ListEmpty_Sq(L) == EMPTY)
return ERROR;
for (int i = 0; i < L->length; ++i) {
// 將第 i 個(gè)元素與 e 值作為參數(shù)傳入 compare()仁堪，根據(jù)返回值判斷是否滿足該關(guān)系陨囊，若是墨微，則返回位序坞靶，否則繼續(xù)往下遍歷
if ((*compare)(e, L->elem[i]) == OK)
return i + 1;
else
continue;
}
return 0;
}
-
compare(): 這里使用相等關(guān)系表示 compare() 函數(shù)
Status Equal(ElemType e1, ElemType e2) { return (e1 == e2) ? OK : ERROR; }- 調(diào)用舉例
int main() { ... // 返回表中第一個(gè)值為 8 的元素的位序 int pos = LocateElem_Sq(&L, 8, Equal); // 例如對(duì)于順序表：{3, 8, 6, 0, 9, 7, 4, 11}辽剧，此時(shí) pos 的值應(yīng)為 2 printf("%d", pos); ... } -
GetKth(): 獲取第 k(位序排截，非下標(biāo)) 個(gè)元素
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 的前驅(qū)
ElemType PriorElem_Sq(SqList *L, ElemType curElem, ElemType *pre_e) { // 先找到當(dāng)前元素的位序 int locateRes = LocateElem_Sq(L, curElem, Equal); // ERROR:表空; 1: 位序?yàn)?，第1個(gè)元素?zé)o前驅(qū); 0: 表中未找到當(dāng)前元素 if (locateRes == ERROR || locateRes == 1 || locateRes == 0) { if (locateRes == 1) { printf("\nERROR: 第一個(gè)元素?zé)o前驅(qū)挠蛉！"); } else if (locateRes == 0) { printf("\nERROR: 目標(biāo)元素: %d 不存在祭示！", curElem); } return ERROR; } // 成功找到存在前驅(qū)的 curElem else { // 將位序?yàn)?locateRes - 1 的元素（即curElem的前驅(qū)）值寫入 pre_e if (GetKth(L, locateRes - 1, pre_e) != ERROR) { return OK; } else { printf("\nERROR: 未找到指定元素: %d 的前驅(qū)！", curElem); return ERROR; } } } -
NextElem(): 獲取 curElem 的后繼
ElemType NextElem_Sq(SqList *L, ElemType curElem, ElemType *next_e) { int locateRes = LocateElem_Sq(L, curElem, Equal); // ERROR:表空; 1: 位序?yàn)閘ength谴古，最后1個(gè)元素?zé)o后繼; 0: 表中未找到當(dāng)前元素 if (locateRes == ERROR || locateRes == L->length || locateRes == 0) { if (locateRes == L->length) { printf("\nERROR: 最后一個(gè)元素?zé)o后繼质涛！"); } else if (locateRes == 0) { printf("\nERROR: 目標(biāo)元素: %d 不存在！", curElem); } return ERROR; } else { // 將位序?yàn)?locateRes + 1 的元素(即curElem的后繼)值寫入 next_e if (GetKth(L, locateRes + 1, next_e) != ERROR) { return OK; } else { printf("\nERROR: 未找到指定元素: %d 的前驅(qū)掰担！", curElem); return ERROR; } } } -
調(diào)用舉例：查看表中所有元素的前驅(qū)與后繼
int main () { ... for (int i = 0; i < L.length; i++) { // cur_e 為當(dāng)前遍歷的元素 ElemType cur_e = L.elem[i]; // pre_e, next_e 分別表示指向前驅(qū)和后繼元素所占內(nèi)存空間的地址汇陆，均為臨時(shí)量，用完需要釋放 ElemType *pre_e = (ElemType *)malloc(sizeof(ElemType)); ElemType *next_e = (ElemType *)malloc(sizeof(ElemType)); // 將 cur_e 的前驅(qū)元素的值寫入 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); // 釋放動(dòng)態(tài)空間 free(pre_e); free(next_e); } ... } -
ListInsert(): 在表中第 i 個(gè)元素之前插入元素 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; } // 從被插入的元素位置起教寂，至表尾元素止，整體移動(dòng) ElemType *q = &L->elem[i]; ElemType *p = &L->elem[L->length - 1]; // 從后向前逐個(gè)進(jìn)行值的遷移 為新值的插入騰出一個(gè)元素所需的空間 while (p >= q) { *(p + 1) = *p; --p; } *q = e; // 給目標(biāo)插入位置賦值 ++L->length; return OK; } -
ListDelete(): 刪除指定下標(biāo)的元素执庐，并返回它的值
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]; // 目標(biāo)刪除元素的值 ElemType *q = &L->elem[i + 1]; // 目標(biāo)刪除位置的后一個(gè) ElemType *p = &L->elem[L->length - 1]; // 表尾位置 // 從前往后進(jìn)行元素的逐個(gè)遷移 while (q <= p) { *(q - 1) = *q; q++; } --L->length; return *e; } -
ListTraverse(): 對(duì)表中每個(gè)元素進(jìn)行遍歷
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(): 這里使用打印輸出元素的值表示對(duì)單個(gè)元素的訪問(wèn)
Status PrintElem(ElemType *curElem) { if (!curElem) return ERROR; printf("%d ", *curElem); return OK; }- 調(diào)用舉例
int main() { ... // 以 PrintElem 作為 Visit 方法遍歷順序表 L酪耕，程序?qū)⒋蛴≥敵?L 中每個(gè)元素的值 ListTraverse_Sq(&L, PrintElem); ... } -
AssignElem(): 自定義表長(zhǎng)并為各元素賦值
Status AssignElem_Sq(SqList *L, int *assign_size) { // 傳入的表還未分配內(nèi)存空間，錯(cuò)誤 if (!L->elem) exit(EXIT_FAILURE); printf("Input the assignment size: "); // 欲賦值的個(gè)數(shù)轨淌，即表長(zhǎng) scanf_s("%d", assign_size, 1); // 欲賦值的個(gè)數(shù)大于當(dāng)前已有的空間迂烁，錯(cuò)誤 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; }
