第 2 章 线性表 （ 双链循环线性表(链式存储结构）实现）
1. 背景说明
2. 示例代码
1) status.h
/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H#define CHECK_NULL(pointer) if (!(pointer)) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_NULL_PTR); \return NULL; \
}#define CHECK_RET(ret) if (ret != RET_OK) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret); \return ret; \
}#define CHECK_VALUE(value, ERR_CODE) if (value) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_CODE); \return ERR_CODE; \
}#define CHECK_FALSE(value, ERR_CODE) if (!(value)) { \printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_CODE); \return FALSE; \
} /* 函数结果状态码 */
#define TRUE 1 /* 返回值为真 */
#define FALSE 0 /* 返回值为假 */
#define RET_OK 0 /* 返回值正确 */
#define INFEASIABLE 2 /* 返回值未知 */
#define ERR_MEMORY 3 /* 访问内存错 */
#define ERR_NULL_PTR 4 /* 空指针错误 */
#define ERR_MEMORY_ALLOCATE 5 /* 内存分配错 */
#define ERR_NULL_STACK 6 /* 栈元素为空 */
#define ERR_PARA 7 /* 函数参数错 */
#define ERR_OPEN_FILE 8 /* 打开文件错 */
#define ERR_NULL_QUEUE 9 /* 队列为空错 */
#define ERR_FULL_QUEUE 10 /* 队列为满错 */
#define ERR_NOT_FOUND 11 /* 表项不存在 */
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如 RET_OK 等 */
typedef int Bollean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */#endif // !STATUS_H2) cycleDoubleLinkList.h
/* 双链循环线性表(链式存储结构）头文件实现 */#ifndef CYCLEDOUBLELINKLIST_H
#define CYCLEDOUBLELINKLIST_H#include "status.h"typedef int ElemType;typedef struct DuLNode {ElemType data;struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;/* 产生空的双向循环链表 L */
Status InitList(DuLinkList *L);/* 操作结果：销毁双向循环链表 L */
Status DestroyList(DuLinkList *L);/* 初始条件：L 已存在操作结果：将 L 重置为空表 */
Status ClearList(DuLinkList L);/* 初始条件：线性表 L 已存在操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Bollean ListEmpty(DuLinkList L);/* 初始条件：L 已存在操作结果：返回 L 中数据元素个数 */
int ListLength(DuLinkList L);/* 当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR */
Status GetElem(DuLinkList L, int i, ElemType *e);/* 初始条件：L 已存在，compare() 是数据元素判定函数操作结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序若这样的数据元素不存在，则返回值为 0 */
int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType));/* 操作结果：若 curr_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱否则操作失败，pre_e 无定义 */
Status PriorElem(DuLinkList L, ElemType curr_e, ElemType *pre_e);/* 操作结果：若 curr_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继否则操作失败，next_e 无定义 */
Status NextElem(DuLinkList L, ElemType curr_e, ElemType *next_e);/* 在双向链表 L 中返回第 i 个元素的位置指针 */
DuLinkList GetElemP(DuLinkList L, int i);/* 算法 2.18，在带头结点的双链循环线性表 L 中第 i 个位置之前插入元素 e，i 的合法值为 1≤ i ≤ 表长 + 1 */
Status ListInsert(DuLinkList L, int i, ElemType e);/* 算法 2.19，删除带头结点的双链循环线性表 L 的第 i 个元素,i 的合法值为 1 ≤ i ≤ 表长 */
Status ListDelete(DuLinkList L, int i, ElemType *e);/* 由双链循环线性表 L 的头结点出发,正序对每个数据元素调用函数 visit() */
void ListTraverse(DuLinkList L, void(*visit)(ElemType));/* 由双链循环线性表 L 的头结点出发,逆序对每个数据元素调用函数 visit() */
void ListTraverseBack(DuLinkList L, void(*visit)(ElemType));#endif // !CYCLEDOUBLELINKLIST_H
3) cycleDoubleLinkList.c
/* 双链循环线性表(链式存储结构）源文件实现 */#include "cycleDoubleLinkList.h"
#include <stdlib.h>
#include <stdio.h>static DuLinkList MakeNewDuLNode(ElemType e)
{DuLinkList newDuLNode = (DuLinkList)malloc(sizeof(DuLNode));CHECK_NULL(newDuLNode)newDuLNode->data = e;newDuLNode->prior = NULL;newDuLNode->next = NULL;return newDuLNode;
}/* 产生空的双向循环链表 L */
Status InitList(DuLinkList *L)
{*L = (DuLinkList)malloc(sizeof(DuLNode));CHECK_VALUE(!(*L), ERR_MEMORY_ALLOCATE)(*L)->next = (*L)->prior = *L;return RET_OK;
}/* 操作结果：销毁双向循环链表 L */
Status DestroyList(DuLinkList *L)
{DuLinkList p = (*L)->next;DuLinkList q;while (p != *L) {q = p->next;free(p);p = q;}free(*L);*L = NULL;return RET_OK;
}/* 初始条件：L 已存在操作结果：将 L 重置为空表 */
Status ClearList(DuLinkList L)
{DuLinkList p = L->next;DuLinkList q;while (p != L) {q = p->next;free(p);p = q;}L->next = L->prior = L;return RET_OK;
}/* 初始条件：线性表 L 已存在操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Bollean ListEmpty(DuLinkList L)
{return ((L->next == L) && (L->prior == L)) ? TRUE : FALSE;
}/* 初始条件：L 已存在操作结果：返回 L 中数据元素个数 */
int ListLength(DuLinkList L)
{DuLinkList p = L->next;int length = 0;while (p != L) {++length;p = p->next;}return length;
}/* 当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR */
Status GetElem(DuLinkList L, int i, ElemType *e)
{DuLinkList p = L->next;int count = 0;while ((p != L) && (count < i - 1)) {++count;p = p->next;}CHECK_VALUE((p == L) || count > i - 1, ERR_PARA)*e = p->data;return RET_OK;
}/* 初始条件：L 已存在，compare() 是数据元素判定函数操作结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序若这样的数据元素不存在，则返回值为 0 */
int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{DuLinkList p = L->next;int count = 0;while (p != L) {++count;if (compare(p->data, e)) {return count;}p = p->next;}return 0;
}/* 操作结果：若 curr_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱否则操作失败，pre_e 无定义 */
Status PriorElem(DuLinkList L, ElemType curr_e, ElemType *pre_e)
{DuLinkList p = L->next->next;while (p != L) {if (p->data == curr_e) {*pre_e = p->prior->data;return TRUE;}p = p->next;}return FALSE;
}/* 操作结果：若 curr_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继否则操作失败，next_e 无定义 */
Status NextElem(DuLinkList L, ElemType curr_e, ElemType *next_e)
{DuLinkList p = L->next->next;while (p != L) {if (p->prior->data == curr_e) {*next_e = p->data;return TRUE;}p = p->next;}return FALSE;
}/* 在双向链表 L 中返回第 i 个元素的位置指针 */
DuLinkList GetElemP(DuLinkList L, int i)
{DuLinkList p = L;for (int j = 0; j < i; ++j) {p = p->next;}return p;
}/* 在带头结点的双链循环线性表 L 中第 i 个位置之前插入元素 e，i 的合法值为 1≤ i ≤ 表长 + 1 */
Status ListInsert(DuLinkList L, int i, ElemType e)
{CHECK_VALUE((i < 1 || i > ListLength(L) + 1), ERR_PARA)DuLinkList p = GetElemP(L, i - 1);CHECK_VALUE(!p, ERR_NOT_FOUND)DuLinkList newDuLNode = MakeNewDuLNode(e);CHECK_VALUE(!newDuLNode, ERR_MEMORY_ALLOCATE)newDuLNode->prior = p;newDuLNode->next = p->next;p->next->prior = newDuLNode;p->next = newDuLNode;return RET_OK;
}/* 删除带头结点的双链循环线性表 L 的第 i 个元素,i 的合法值为 1 ≤ i ≤ 表长 */
Status ListDelete(DuLinkList L, int i, ElemType *e)
{CHECK_VALUE((i < 1 || i > ListLength(L)), ERR_PARA)DuLinkList p = GetElemP(L, i);CHECK_VALUE(!p, ERR_NOT_FOUND)*e = p->data;p->prior->next = p->next;p->next->prior = p->prior;free(p);return RET_OK;
}/* 由双链循环线性表 L 的头结点出发,正序对每个数据元素调用函数 visit() */
void ListTraverse(DuLinkList L, void(*visit)(ElemType))
{DuLinkList p = L->next;while (p != L) {visit(p->data);p = p->next;}
}/* 由双链循环线性表 L 的头结点出发,逆序对每个数据元素调用函数 visit() */
void ListTraverseBack(DuLinkList L, void(*visit)(ElemType))
{DuLinkList p = L->prior;while (p != L) {visit(p->data);p = p->prior;}
}4) main.c
/* 入口程序源文件 */#include "cycleDoubleLinkList.h"
#include <stdio.h>Status Compare(ElemType e1, ElemType e2);void Visit(ElemType e);int main(void)
{DuLinkList L;InitList(&L);for (int i = 0; i < 5; ++i) {ListInsert(L, i + 1, i + 1);}printf("Output Link List for sequence: ");ListTraverse(L, Visit);putchar('\n');printf("Output Link List for adverse: ");ListTraverseBack(L, Visit);putchar('\n');ElemType e;ListDelete(L, 2, &e);printf("After delete %d, Link List is: ", e);ListTraverse(L, Visit);putchar('\n');printf("The num of L is %d\n", ListLength(L));printf("List is %s\n", (ListEmpty(L) == TRUE) ? "empty" : "not empty");ClearList(L);printf("After clear L, List is %s\n", (ListEmpty(L) == TRUE) ? "empty" : "not empty");for (int i = 0; i < 5; ++i) {ListInsert(L, i + 1, i + 1);}ListTraverse(L, Visit);putchar('\n');Status ret = GetElem(L, 3, &e);if (ret == RET_OK) {printf("The %dth element of L is %d\n", 3, e);} else {printf("%dth element is not exist.\n", 3);}ret = LocateElem(L, 4, Compare);if (ret) {printf("The element of %d is %dth\n", 4, ret);} else {printf("Element %d is not exist in L\n", 4);}ret = PriorElem(L, 4, &e);if (ret == TRUE) {printf("The prior element of %d is %d\n", 4, e);} else {printf("Element %d do not have prior element\n", 4);}ret = NextElem(L, 4, &e);if (ret == TRUE) {printf("The next element of %d is %d\n", 4, e);} else {printf("Element %d do not have next element\n", 4);}DestroyList(&L);return 0;
}Status Compare(ElemType e1, ElemType e2)
{return (e1 == e2) ? TRUE : FALSE;
}void Visit(ElemType e)
{printf("%d ", e);
}3. 输出示例
