-
相关宏定义及数据类型的别名定义
#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; -
结构定义
// 链表数据元素结点：存储元素值及下一结点的地址 typedef struct LNode { ElemDataType data; struct LNode *next; } ElemType, *Link; // 存储链表基本信息的结构：包括链表头、尾结点的地址及链表长度信息 typedef struct { Link head, tail; int length; } LinkList; -
InitList()：构造一个带头结点的空表
// 初始化链表结构，该链表为带头结点(内容为空)的单链表 Status InitList_L(LinkList *L) { ElemType *emptyNode; emptyNode = (ElemType *)malloc(sizeof(ElemType)); // 若分配失败 则返回异常 if (!emptyNode) return ERROR; // 指针域置空 emptyNode->next = NULL; // 空表，头尾结点均指向数据域、指针域都为空的头结点 (*L).head = (*L).tail = emptyNode; // 链表长度为 0 (*L).length = 0; return OK; }有了头结点后，对在第一个结点前插入新结点，和删除第一个结点，其操作与对其他结点的操作可统一起来
-
CreateList(): 建立链表
- 正向建立链表(表头至表尾)
// 正向建立链表 Status CreateList_L_ProperOrder(LinkList *L, int size) { InitList_L(L); ElemType *newNode, *p = (*L).head; // size: 欲创建的结点个数 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); p->next = newNode; // 将新结点接入尾结点之后 p = p->next; // 使 p 指向新的尾结点 p->next = NULL; // 表尾结点指针域置空 (*L).tail = p; // 更新链表中的尾指针域，使其指向最新的尾结点 (*L).length++; // 表长度+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; // 将新结点插入到第一个结点(头结点后的结点)之前 (*L).head->next = newNode; // 新结点成为新的第一个结点 (*L).length++; // 长度+1 // 倒序建立链表，第一次连入链表的结点即为尾结点 if (i == 0) { (*L).tail = newNode; // 链表尾指针指向第一个连入的结点，从此再不变化 } } return OK; }
-
DestroyList(): 销毁线性表
Status DestroyList_Sq(SqList *L) { // 若链表不存在头结点，则表明尚未初始化，无需销毁 if (!(*L).head) exit(EXIT_FAILURE); // 先将链表置空，释放所有含有效数据的结点 ClearList_L(L); // 释放头结点 FreeNode(&((*L).head)); (*L).head = (*L).tail = NULL; return OK; } -
ClearList()：重置为空表
// 将链表置空，并释放原链表的节点空间，即清除所有含有效数据的结点 Status ClearList_L(LinkList *L) { if ((*L).head == (*L).tail) return ERROR; Link p = (*L).head->next; // p 初始指向第一个结点 Link DelNode = NULL; (*L).head->next = NULL; // 将头结点与第一个结点的连接切断 // 依次释放各结点的空间 while (p != NULL) { DelNode = p; *p = *p->next; FreeNode(&DelNode); } (*L).tail = (*L).head; (*L).length = 0; return OK; } -
ListEmpty(): 检测该表是否为空
Status ListEmpty_L(LinkList *L) { return L->length == 0 ? EMPTY : NOT_EMPTY; } -
GetLength(): 获取顺序表中元素的个数
Length GetLength_L(LinkList *L) { return (*L).length; } -
GetHeadNodeVal(): 返回第一个非空节点的值
ElemDataType GetHeadNodeVal(LinkList *L) { return (*L).head->next->data; } -
GetTailNodeVal(): 获取尾结点的值
ElemDataType GetTailNodeVal(LinkList *L) { return (*L).tail->data; } -
GetLength_L(): 获取链表长度
Length GetLength_L(LinkList *L) { return (*L).length; } -
GetElem(): 用 e 返回 L 中第 i 个结点的值
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: 目标位置: %d 错误！", 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 个位置的结点 else { e = NULL; printf("ERROR: 未找到目标结点！"); return ERROR; } return OK; } -
LocateElem(): 返回表中第一个与 e 值满足关系 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(): 这里使用相等关系表示 compare() 函数
Status Equal(ElemDataType e1, ElemDataType 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(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 的前驱，用 pre_e 返回
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.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: 位序为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.data); return ERROR; } } } -
调用举例：查看表中所有元素的前驱与后继
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 所指的一串结点链接在 L 的最后一个结点 Status Append(LinkList *L, LinkList S) { if (ListEmpty_L(&S) == EMPTY) { return ERROR; } (*L).tail->next = S.head->next; // 将 S 的第一个非空节点接入 L 的尾结点 (*L).tail = S.tail; // 更新 L 尾结点的指向 (*L).length += S.length; // 更新 L 的表长 S.head->next = NULL; // 断开头结点与 S 第一个非空节点的连接 S.tail = NULL; // 尾结点置空 S.length = 0; // 表长清零 FreeNode(&(S.head)); // 释放 S 的头结点空间 return OK; } -
LinkListInsBefore(): 在表中第 i 个结点之前插入数据域为 e 的新结点
Status LinkListInsBefore(LinkList *L, int i, ElemDataType e) { // i = length + 1 时，等同于在表尾添加结点 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，循环共进行 i - 1 次，p 从头结点向后移动 i - 1 次，循环结束后，p 指向的为第 i - 1 个结点，即被插入的结点的前驱 while (j < i - 1) { p = p->next; ++j; } newNode = (ElemType *)malloc(sizeof(ElemType)); newNode->next = p->next; // 使新结点指向第 i 个结点 p->next = newNode; // 使第 i 个结点的前驱指向新结点 newNode->data = e; // 为新结点的数据域赋值 (*L).length++; // 表长+1 // 在表尾添加结点，链表结构中尾指针需更新 if (p == (*L).tail) { (*L).tail = newNode; } return OK; } -
LinkListInsAfter(): 在第 i 个结点之后插入数据域为 e 的新结点
Status LinkListInsAfter(LinkList *L, Position i, ElemDataType e) { LinkListInsBefore(L, i+1, e); return OK; } -
ListDelete(): 删除第 i 个元素 并返回它的值
// 删除第 i 个元素 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 指向的是被删除元素的前驱，即：被删除的元素指针是 p->next } *e = p->next->data; p->next = p->next->next; (*L).length--; // 长度 - 1 free(p->next); // 释放被删除的节点空间 // 经删除操作后，若p 的指针域为空，说明删除的是表尾元素，尾指针需更新 if (!(p->next)) (*L).tail = p; return OK; } -
ListTraverse(): 对表中每个元素进行遍历
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(): 这里使用打印输出元素的值表示对单个元素的访问
Status PrintElem(ElemType *curElem) { if (!curElem) return ERROR; printf("%d ", curElem->data); return OK; }- 调用举例
int main() { ... // 以 PrintElem 作为 Visit 方法遍历顺序表 L，程序将打印输出 L 中每个元素的值 ListTraverse_Sq(&L, PrintElem); ... } -
MergeList(): 将两个有序链表(升序)合并为一个新链表
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 无需新分配空间，不妨以 L1 的头指针作为起点，通过改变当前结点的指针域来达到按序合并的效果 *L3 = *L1; // pc 一开始指向的是 L1 的头结点（数据域为空） 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; }
