循环单链表

循环链表的存储示意图

定义

代码实现

// DataElement.h
#ifndef INC_01_DATAELEMENT_H
#define INC_01_DATAELEMENT_H
#define MAX_SIZE 255
// 定义数据元素
typedef struct {
    int id;
    char * name;
} ElementType;
// 定义顺序表结构
typedef struct {
    ElementType datas[MAX_SIZE];  // 顺序表中的数据集合
    int length;  // 当前顺序表中的元素个数
} SeqList;
#endif

// CircularLinkList.h
#ifndef INC_01_CIRCULARLINKLIST_H
#define INC_01_CIRCULARLINKLIST_H
#include <stdio.h>
#include <stdlib.h>
#include "DataElement.h"
/** 循环链表的结点 **/
typedef struct CircularNode {
    ElementType data;  // 数据域
    struct CircularNode * next;  // 指向下一个结点的指针域
} CircularNode;
/** 循环链表结构 **/
typedef struct CircularLinkList{
    CircularNode * next;  // 指向第一个结点的指针，头指针
    int length;  // 长度
} CircularLinkList;
/** 在循环链表中插入元素 **/
void InsertCircularLinkList(CircularLinkList * clList, int pos, ElementType element);
/** 打印循环链表的所有元素 **/
void PrintCircularLinkList(CircularLinkList * clList);
/** 打印循环链表的所有元素 **/
void InitCircularLinkList(CircularLinkList * clList, ElementType * dataArray, int length);
/** 删除并返回所删除的元素 **/
ElementType DeleteCircularLinkList(CircularLinkList * clList, int pos);
#endif

// CircularLinkList.c
#include "CircularLinkList.h"
/** 在循环链表中插入元素 **/
void InsertCircularLinkList(CircularLinkList * clList, int pos, ElementType element) {
    CircularNode * node = (CircularNode * )malloc(sizeof(CircularNode));
    node -> data = element;
    node -> next = NULL;
    // 插入的是第一个结点
    if (pos == 1) {
        node -> next = clList -> next;
        if (!node -> next) {  // 如果插入的链表长度为 0
            node -> next = node;
        } else {  // 如果长度不为 0
            CircularNode * lastNode = clList -> next;
            for (int i = 1; i < clList -> length ; ++i) {
                lastNode = lastNode -> next;
            }
            lastNode -> next = node;
        }
        clList -> next = node;
        clList -> length++;
        return;
    }
    // 插入的不是第一个结点
    CircularNode * currNode = clList -> next;
    for (int j = 1; currNode && j < pos - 1; ++j) {
        currNode = currNode -> next;
    }
    if (currNode) {
        node -> next = currNode -> next;
        currNode -> next = node;
        clList -> length++;
        if (pos == clList -> length) {
            node -> next = clList -> next;
        }
    }
};
/** 打印循环链表的所有元素 **/
void PrintCircularLinkList(CircularLinkList * clList){
    if (clList -> length == 0 || !clList -> next) {
        printf("链表长度为空，没有内容可以打印！");
        clList -> length = 0;
        return;
    }
    CircularNode * node = clList -> next;
    for (int i = 0; i < clList -> length; ++i) {
        printf("%d\t%s\n", node -> data.id, node -> data.name);
        node = node -> next;
    }
};
/** 打印循环链表的所有元素 **/
void InitCircularLinkList(CircularLinkList * clList, ElementType * dataArray, int length) {
    for (int i = 0; i < length; ++i) {
        InsertCircularLinkList(clList, i + 1, dataArray[i]);
    }
};
/** 删除并返回所删除的元素 **/
ElementType DeleteCircularLinkList(CircularLinkList * clList, int pos) {
    ElementType element;
    element.id = -999;
    if (pos == 1) {
        CircularNode * node = clList -> next;
        if (node) {
            element = node -> data;
            CircularNode * lastNode = clList -> next;
            for (int i = 1; i < clList -> length; ++i) {
                lastNode = lastNode -> next;
            }
            clList -> next = node -> next;
            lastNode -> next = clList -> next;
            free(node);
            clList -> length--;
        }
        return element;
    }
    CircularNode * preNode;
    CircularNode * node = clList -> next;
    for (int i = 1; node && i < pos; ++i) {
        preNode = node;
        node = node -> next;
    }
    if (node) {
        element = node -> data;
        preNode -> next = node -> next;
        free(node);
        clList -> length--;
    }
    return element;
};

// main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DataElement.h"
#include "CircularLinkList.h"
ElementType dataArray[] = {
        {1, "奇异博士"},
        {2, "美国队长"},
        {3, "太上老君"},
        {4, "齐天大圣"},
};
void TestCircularLinkList();
int main() {
    TestCircularLinkList();
    return 0;
}
void TestCircularLinkList() {
    CircularLinkList * clList = (CircularLinkList *)malloc(sizeof(CircularLinkList));
    clList -> length = 0;
    clList -> next = NULL;
    InitCircularLinkList(clList, dataArray, 4);
    PrintCircularLinkList(clList);
    ElementType element = DeleteCircularLinkList(clList, 2);
    printf("删除的元素:%s\n", element.name);
    printf("删除后的链表！\n");
    PrintCircularLinkList(clList);
};

循环双链表

当循环双链表为空表时，其头节点的prior域和next域都为等于L