-
相關(guān)宏定義及數(shù)據(jù)類(lèi)型的別名定義
#define OK 1 #define ERROR -1 #define EMPTY 0 #define NOT_EMPTY 1 typedef int ElemDataType; typedef int Status; typedef int Length; typedef int Position;
-
結(jié)構(gòu)定義
// 鏈表數(shù)據(jù)元素結(jié)點(diǎn):存儲(chǔ)元素值及下一結(jié)點(diǎn)的地址 typedef struct LNode { ElemDataType data; struct LNode *next; } ElemType, *Link; // 存儲(chǔ)鏈表基本信息的結(jié)構(gòu):包括鏈表頭隙赁、尾結(jié)點(diǎn)的地址及鏈表長(zhǎng)度信息 typedef struct { Link head, tail; int length; } LinkList;
-
InitList():構(gòu)造一個(gè)帶頭結(jié)點(diǎn)的空表
// 初始化鏈表結(jié)構(gòu)别凹,該鏈表為帶頭結(jié)點(diǎn)(內(nèi)容為空)的單鏈表 Status InitList_L(LinkList *L) { ElemType *emptyNode; emptyNode = (ElemType *)malloc(sizeof(ElemType)); // 若分配失敗 則返回異常 if (!emptyNode) return ERROR; // 指針域置空 emptyNode->next = NULL; // 空表,頭尾結(jié)點(diǎn)均指向數(shù)據(jù)域畦徘、指針域都為空的頭結(jié)點(diǎn) (*L).head = (*L).tail = emptyNode; // 鏈表長(zhǎng)度為 0 (*L).length = 0; return OK; }
有了頭結(jié)點(diǎn)后,對(duì)在第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)关带,和刪除第一個(gè)結(jié)點(diǎn)治专,其操作與對(duì)其他結(jié)點(diǎn)的操作可統(tǒng)一起來(lái)
-
CreateList(): 建立鏈表
- 正向建立鏈表(表頭至表尾)
// 正向建立鏈表 Status CreateList_L_ProperOrder(LinkList *L, int size) { InitList_L(L); ElemType *newNode, *p = (*L).head; // size: 欲創(chuàng)建的結(jié)點(diǎn)個(gè)數(shù) printf("Input %d nodes: ", size); for (int i = 0; i < size; ++i) { newNode = (ElemType *)malloc(sizeof(ElemType)); if (!newNode) return ERROR; // 獲取用戶輸入,將其賦給新結(jié)點(diǎn)的數(shù)據(jù)域 scanf_s("%d", &newNode->data, 1); p->next = newNode; // 將新結(jié)點(diǎn)接入尾結(jié)點(diǎn)之后 p = p->next; // 使 p 指向新的尾結(jié)點(diǎn) p->next = NULL; // 表尾結(jié)點(diǎn)指針域置空 (*L).tail = p; // 更新鏈表中的尾指針域,使其指向最新的尾結(jié)點(diǎn) (*L).length++; // 表長(zhǎng)度+1 } return OK; }
- 逆向建立鏈表(表尾至表頭)
// 逆向建立鏈表 Status CreateList_L_ReverseOrder(LinkList *L, int size) { InitList_L(L); Link newNode; printf("Input %d nodes: ", size); for (int i = 0; i < size; ++i) { newNode = (ElemType *)malloc(sizeof(ElemType)); if (!newNode) return ERROR; scanf_s("%d", &newNode->data, 1); newNode->next = (*L).head->next; // 將新結(jié)點(diǎn)插入到第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn)后的結(jié)點(diǎn))之前 (*L).head->next = newNode; // 新結(jié)點(diǎn)成為新的第一個(gè)結(jié)點(diǎn) (*L).length++; // 長(zhǎng)度+1 // 倒序建立鏈表,第一次連入鏈表的結(jié)點(diǎn)即為尾結(jié)點(diǎn) if (i == 0) { (*L).tail = newNode; // 鏈表尾指針指向第一個(gè)連入的結(jié)點(diǎn)赚哗,從此再不變化 } } return OK; }
-
DestroyList(): 銷(xiāo)毀線性表
Status DestroyList_Sq(SqList *L) { // 若鏈表不存在頭結(jié)點(diǎn)埠对,則表明尚未初始化奈虾,無(wú)需銷(xiāo)毀 if (!(*L).head) exit(EXIT_FAILURE); // 先將鏈表置空露久,釋放所有含有效數(shù)據(jù)的結(jié)點(diǎn) ClearList_L(L); // 釋放頭結(jié)點(diǎn) FreeNode(&((*L).head)); (*L).head = (*L).tail = NULL; return OK; }
-
ClearList():重置為空表
// 將鏈表置空笼沥,并釋放原鏈表的節(jié)點(diǎn)空間铣揉,即清除所有含有效數(shù)據(jù)的結(jié)點(diǎn) Status ClearList_L(LinkList *L) { if ((*L).head == (*L).tail) return ERROR; Link p = (*L).head->next; // p 初始指向第一個(gè)結(jié)點(diǎn) Link DelNode = NULL; (*L).head->next = NULL; // 將頭結(jié)點(diǎn)與第一個(gè)結(jié)點(diǎn)的連接切斷 // 依次釋放各結(jié)點(diǎn)的空間 while (p != NULL) { DelNode = p; *p = *p->next; FreeNode(&DelNode); } (*L).tail = (*L).head; (*L).length = 0; return OK; }
-
ListEmpty(): 檢測(cè)該表是否為空
Status ListEmpty_L(LinkList *L) { return L->length == 0 ? EMPTY : NOT_EMPTY; }
-
GetLength(): 獲取順序表中元素的個(gè)數(shù)
Length GetLength_L(LinkList *L) { return (*L).length; }
-
GetHeadNodeVal(): 返回第一個(gè)非空節(jié)點(diǎn)的值
ElemDataType GetHeadNodeVal(LinkList *L) { return (*L).head->next->data; }
-
GetTailNodeVal(): 獲取尾結(jié)點(diǎn)的值
ElemDataType GetTailNodeVal(LinkList *L) { return (*L).tail->data; }
-
GetLength_L(): 獲取鏈表長(zhǎng)度
Length GetLength_L(LinkList *L) { return (*L).length; }
-
GetElem(): 用 e 返回 L 中第 i 個(gè)結(jié)點(diǎn)的值
Status GetElem_L(LinkList *L, int i, ElemDataType *e) { if (L->head->next == NULL) { printf("ERROR: 該鏈表為空哪审!"); return ERROR; } if (i < 1 || i > L->length) { printf("ERROR: 目標(biāo)位置: %d 錯(cuò)誤蛾魄!", i); return ERROR; } Link p = L->head->next; int j = 1; while (p && j < i) { p = p->next; j++; } if (j == i) { *e = p->data; } // 未找到鏈表中第 i 個(gè)位置的結(jié)點(diǎn) else { e = NULL; printf("ERROR: 未找到目標(biāo)結(jié)點(diǎn)!"); return ERROR; } return OK; }
-
LocateElem(): 返回表中第一個(gè)與 e 值滿足關(guān)系 compare() 的元素的位置
Position LocateElem_L(LinkList *L, ElemType e, Status((*compare)(ElemDataType e1, ElemDataType e2))) { if (ListEmpty_L(L) == EMPTY) { printf("ERROR: 表不能為空湿滓!\n"); return ERROR; } int i = 1; Link p = L->head->next; while (p) { if ((*compare)(e.data, p->data) == OK) { return i; } else { i++; p = p->next; } } return 0; }
-
compare(): 這里使用相等關(guān)系表示 compare() 函數(shù)
Status Equal(ElemDataType e1, ElemDataType 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 個(gè)元素
Status GetKth(LinkList *L, int k, ElemType *e) { Link p = L->head->next; int i = 1; while (p && i < k) { p = p->next; i++; } if (i == k) { *e = *p; return OK; } else { return ERROR; } }
-
PriorElem(): 獲取 curElem 的前驅(qū),用 pre_e 返回
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ū))值寫(xiě)入 pre_e if (GetKth(L, locateRes - 1, pre_e) != ERROR) { return OK; } else { printf("\nERROR: 未找到指定元素: %d 的前驅(qū)而线!", curElem.data); return ERROR; } } }
-
NextElem(): 獲取 curElem 的后繼铭污,用 next_e 返回
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的后繼)值寫(xiě)入 next_e if (GetKth(L, locateRes + 1, next_e) != ERROR) { return OK; } else { printf("\nERROR: 未找到指定元素: %d 的前驅(qū)!", curElem.data); return ERROR; } } }
-
調(diào)用舉例:查看表中所有元素的前驅(qū)與后繼
int main () { ... Link p = L1.head->next; while (p) { ElemType cur_e = *p; ElemType *pre_e = (ElemType *)malloc(sizeof(ElemType)); ElemType *next_e = (ElemType *)malloc(sizeof(ElemType)); if (PriorElem_L(&L1, cur_e, pre_e) == ERROR) { pre_e->data = -1; } if (NextElem_L(&L1, cur_e, next_e) == ERROR) { next_e->data = -1; } printf("\npreElem: %d\ncurElem: %d\nnextElem: %d\n", pre_e->data, cur_e.data, next_e->data); FreeNode(&pre_e); FreeNode(&next_e); p = p->next; } ... }
-
Append(): 將一鏈表添加至指定鏈表的最后
// 將 S 所指的一串結(jié)點(diǎn)鏈接在 L 的最后一個(gè)結(jié)點(diǎn) Status Append(LinkList *L, LinkList S) { if (ListEmpty_L(&S) == EMPTY) { return ERROR; } (*L).tail->next = S.head->next; // 將 S 的第一個(gè)非空節(jié)點(diǎn)接入 L 的尾結(jié)點(diǎn) (*L).tail = S.tail; // 更新 L 尾結(jié)點(diǎn)的指向 (*L).length += S.length; // 更新 L 的表長(zhǎng) S.head->next = NULL; // 斷開(kāi)頭結(jié)點(diǎn)與 S 第一個(gè)非空節(jié)點(diǎn)的連接 S.tail = NULL; // 尾結(jié)點(diǎn)置空 S.length = 0; // 表長(zhǎng)清零 FreeNode(&(S.head)); // 釋放 S 的頭結(jié)點(diǎn)空間 return OK; }
-
LinkListInsBefore(): 在表中第 i 個(gè)結(jié)點(diǎn)之前插入數(shù)據(jù)域?yàn)?e 的新結(jié)點(diǎn)
Status LinkListInsBefore(LinkList *L, int i, ElemDataType e) { // i = length + 1 時(shí)誓竿,等同于在表尾添加結(jié)點(diǎn) if (i <= 0 || i > (*L).length + 1) { printf("\nERROR: 插入位置: %d 不合法磅网!", i); return ERROR; } ElemType *p = (*L).head, *newNode; int j = 0; // j 從 0 至 i - 2,循環(huán)共進(jìn)行 i - 1 次筷屡,p 從頭結(jié)點(diǎn)向后移動(dòng) i - 1 次涧偷,循環(huán)結(jié)束后,p 指向的為第 i - 1 個(gè)結(jié)點(diǎn)毙死,即被插入的結(jié)點(diǎn)的前驅(qū) while (j < i - 1) { p = p->next; ++j; } newNode = (ElemType *)malloc(sizeof(ElemType)); newNode->next = p->next; // 使新結(jié)點(diǎn)指向第 i 個(gè)結(jié)點(diǎn) p->next = newNode; // 使第 i 個(gè)結(jié)點(diǎn)的前驅(qū)指向新結(jié)點(diǎn) newNode->data = e; // 為新結(jié)點(diǎn)的數(shù)據(jù)域賦值 (*L).length++; // 表長(zhǎng)+1 // 在表尾添加結(jié)點(diǎn)燎潮,鏈表結(jié)構(gòu)中尾指針需更新 if (p == (*L).tail) { (*L).tail = newNode; } return OK; }
-
LinkListInsAfter(): 在第 i 個(gè)結(jié)點(diǎn)之后插入數(shù)據(jù)域?yàn)?e 的新結(jié)點(diǎn)
Status LinkListInsAfter(LinkList *L, Position i, ElemDataType e) { LinkListInsBefore(L, i+1, e); return OK; }
-
ListDelete(): 刪除第 i 個(gè)元素 并返回它的值
// 刪除第 i 個(gè)元素 Status ListDelete_L(LinkList *L, int i, ElemDataType *e) { if (i < 1 || i >(*L).length) exit(ERROR); if ((*L).length < 1) exit(ERROR); Link p = (*L).head; for (int j = 0; j < i - 1; ++j) { p = p->next; // p 指向的是被刪除元素的前驅(qū),即:被刪除的元素指針是 p->next } *e = p->next->data; p->next = p->next->next; (*L).length--; // 長(zhǎng)度 - 1 free(p->next); // 釋放被刪除的節(jié)點(diǎn)空間 // 經(jīng)刪除操作后扼倘,若p 的指針域?yàn)榭杖贩猓f(shuō)明刪除的是表尾元素,尾指針需更新 if (!(p->next)) (*L).tail = p; return OK; }
-
ListTraverse(): 對(duì)表中每個(gè)元素進(jìn)行遍歷
Status ListTraverse_L(LinkList *L, Status((*visit)(ElemType *curElem))) { if (ListEmpty_L(L) == EMPTY) return ERROR; Link p = L->head->next; while (p) { if ((*visit)(p) == ERROR) { exit(EXIT_FAILURE); } p = p->next; } printf("\n"); return OK; }
-
visit(): 這里使用打印輸出元素的值表示對(duì)單個(gè)元素的訪問(wèn)
Status PrintElem(ElemType *curElem) { if (!curElem) return ERROR; printf("%d ", curElem->data); return OK; }
- 調(diào)用舉例
int main() { ... // 以 PrintElem 作為 Visit 方法遍歷順序表 L再菊,程序?qū)⒋蛴≥敵?L 中每個(gè)元素的值 ListTraverse_Sq(&L, PrintElem); ... }
-
MergeList(): 將兩個(gè)有序鏈表(升序)合并為一個(gè)新鏈表
Status MergeList_L(LinkList *L1, LinkList *L2, LinkList *L3) { if ((*L1).length < 1 || (*L2).length < 1) exit(EXIT_FAILURE); Link pa, pb, pc; pa = (*L1).head->next; pb = (*L2).head->next; // L3 無(wú)需新分配空間爪喘,不妨以 L1 的頭指針作為起點(diǎn),通過(guò)改變當(dāng)前結(jié)點(diǎn)的指針域來(lái)達(dá)到按序合并的效果 *L3 = *L1; // pc 一開(kāi)始指向的是 L1 的頭結(jié)點(diǎn)(數(shù)據(jù)域?yàn)榭眨? pc = (*L3).head; while (pa && pb ) { if (pa->data <= pb->data) { pc->next = pa; pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa ? pa : pb; (*L3).length = (*L1).length + (*L2).length; (*L3).tail = pa ? (*L1).tail : (*L2).tail; return OK; }