链表主要操作集的实现

作者: 小能猫吃牙膏 | 来源:发表于2019-04-30 16:55 被阅读0次

相关宏定义及数据类型的别名定义

#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;
}

链表主要操作集的实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读