考研数据结构模板：顺序表、链表、栈、队列

前言

1. 代码风格偏向于考研风格而非算法竞赛风格。
2. 代码实现参考《2024数据结构王道复习指导》。
3. 注释详细、保证看懂。
4. 下面是已实现的数据结构模板：
   1. 顺序表SeqList
   2. 链表LinkList
   3. 双链表DLinkList
   4. 顺序栈SeqStack
   5. 循环顺序队列CircleQueue
   6. 链队列LinkQueue

顺序表SeqList

顺序表定义

// 定义顺序表
struct SeqList {
    int *data; // 数据动态分配
    int length, maxLength; // 当前长度、最大长度
};
// 最大容量
#define SEQ_LIST_MAX_SIZE 100
// 初始容量
#define SQL_LIST_INIT_SIZE 10

初始化

void SeqListInitial(SeqList &list) {
    list.maxLength = SQL_LIST_INIT_SIZE;
    list.data = new int[list.maxLength];
    list.length = 0;
}

判断是否为空

bool SeqListIsEmpty(SeqList &list) {
    return list.length == 0;
}

查询元素长度

int SeqListLength(SeqList &list) {
    return list.length;
}

打印元素

void SeqListPrint(SeqList &list) {
    for (int i = 0; i < list.length; i++) {
        printf("%d ", list.data[i]);
    }
}

插入元素

bool SeqListInsert(SeqList &list, int index, int data) {
    if (index < 1 || index > list.length + 1) { // index范围必须在[1, list.SeqListLength + 1]
        return false; // 下标溢出
    }
    if (list.length == list.maxLength) { // 空间不足，申请空间
        if (list.length == SEQ_LIST_MAX_SIZE) {
            return false; // 空间溢出
        } else {
            int maxLength; // 下一次申请空间的长度
            if (list.length * 2 < SEQ_LIST_MAX_SIZE) {
                maxLength = list.length * 2; // 容量每次扩大两倍
            } else {
                maxLength = SEQ_LIST_MAX_SIZE;
            }
            int *memory = new int[maxLength]; // 创建一块存储空间
            for (int i = 0; i < list.length; i++) { // 复制数组
                memory[i] = list.data[i];
            }
            delete list.data; // 释放原来的空间
            list.data = memory;
            list.maxLength = maxLength;
        }
    }
    for (int i = list.length; i >= index; i--) { // 移动数组
        list.data[i] = list.data[i - 1];
    }
    list.length++;
    list.data[index - 1] = data; // 插入元素
    return true;
}

删除元素

bool SeqListRemove(SeqList &list, int index, int &data) {
    if (index < 1 || index > list.length) { // index取值范围为[1, list.SeqListLength]
        return false; // 溢出
    }
    data = list.data[index - 1]; // 保存删除的数据
    for (int i = index; i < list.length; i++) { // 移动元素
        list.data[i - 1] = list.data[i];
    }
    list.length--;
    return true;
}

查询元素位置

int SeqListFindIndex(SeqList &list, int data) {
    for (int i = 0; i < list.length; i++) { // 遍历数组
        if (list.data[i] == data) {
            return i + 1;
        }
    }
    return -1; // 找不到则返回-1
}

查询位置上的元素值

bool SeqListGet(SeqList &list, int index, int &data) {
    if (index < 1 || index > list.length) { // 下标范围在[1, list.length]之间
        return false;
    }
    data = list.data[index - 1]; // 保存元素
    return true;
}

链表LinkList

链表定义

// 单链表节点
struct LinkListNode {
    int data;
    LinkListNode *next;
};

// 单链表
struct LinkList {
    LinkListNode *head; // 头指针
    LinkListNode *tail; // 尾指针
};

空元素初始化

void LinkListInitial(LinkList &list) {
    LinkListNode *node = new LinkListNode(); // 初始化头节点
    list.head = node;
    list.tail = node;
}

数组初始化

void LinkListInitial(LinkList &list, int data[], int length) {
    LinkListNode *node = new LinkListNode();
    list.head = node;
    list.tail = node;
    for (int i = 0; i < length; i++) { // 尾插法插入所有元素
        LinkListNode *next = new LinkListNode();
        next->data = data[i];
        list.tail->next = next;
        list.tail = list.tail->next;
    }
}

查询元素长度

int LinkListLength(LinkList &list) {
    int length = 0;
    LinkListNode *p = list.head->next;
    while (p != NULL) { // 遍历链表直到为空
        length++;
        p = p->next;
    }
    return length;
}

打印元素

void LinkListPrint(LinkList &list) {
    if (list.head == list.tail) {
        return;
    }
    LinkListNode *p = list.head->next;
    while (p != NULL) { // 遍历所有元素，直到为空
        printf("%d ", p->data);
        p = p->next;
    }
}

插入元素

bool LinkListInsert(LinkList &list, int index, int data) {
    if (index < 1) { // 下标范围必须大于等于1
        return false;
    }
    LinkListNode *p = list.head; // 用于保存插入位置的前驱
    for (int i = 1; i < index; i++) { // 找到插入位置的前驱
        p = p->next;
        if (p == NULL) {
            return false; // 不存在此下标
        }
    }
    LinkListNode *node = new LinkListNode(); // 插入元素
    node->data = data;
    node->next = p->next;
    p->next = node;
    return true;
}

删除元素

bool LinkListRemove(LinkList &list, int index, int &data) {
    if (index < 1) { // 下标范围必须大于等于1
        return false;
    }
    LinkListNode *p = list.head; // 用于保存插入位置的前驱
    for (int i = 1; i < index; i++) { // 查找删除位置的前驱
        p = p->next;
        if (p == NULL) {
            return false; // 不存在此下标
        }
    }
    LinkListNode *node = p->next; // 执行删除操作
    data = node->data; // 保存删除节点的值
    p->next = node->next;
    delete node; // 释放空间
    return true;
}

查询位置上的元素值

bool LinkListGet(LinkList &list, int index, int &data) {
    if (index < 1) { // 下标范围必须大于等于1
        return false;
    }
    LinkListNode *p = list.head;
    for (int i = 1; i <= index; i++) { // 遍历链表
        p = p->next;
        if (p == NULL) {
            return false; // 不存在此下标
        }
    }
    data = p->data;
    return true;
}

双链表DLinkList

双链表定义

// 双链表节点
struct DLinkListNode {
    int data;
    DLinkListNode *prev, *next; // 前驱与后继节点
};

// 双链表
struct DLinkList {
    DLinkListNode *head; // 头节点
};

初始化

void DLinkListInitial(DLinkList &list) {
    DLinkListNode *head = new DLinkListNode(); // 创建头节点
    list.head = head;
}

打印元素

void DLinkListPrint(DLinkList &list) {
    DLinkListNode *p = list.head;
    while (p->next != NULL) {
        p = p->next;
        printf("%d ", p->data);
    }
}

插入元素

bool DLinkListNodeInsert(DLinkList &list, int index, int data) {
    if (index < 1) { // 下标范围必须大于等于1
        return false;
    }
    DLinkListNode *p = list.head;
    for (int i = 1; i < index; i++) { // 找到插入位置的前驱
        p = p->next;
        if (p == NULL) {
            return false; // 不存在此下标
        }
    }
    DLinkListNode *node = new DLinkListNode(); // 插入元素
    node->data = data;
    node->next = p->next;
    if (p->next != NULL) {
        p->next->prev = node;
    }
    node->prev = p;
    p->next = node;
    return true;
}

删除元素

bool DLinkListRemove(DLinkList &list, int index) {
    if (index < 1) { // 下标范围必须大于等于1
        return false;
    }
    DLinkListNode *p = list.head; // 找到删除位置的前驱
    for (int i = 1; i < index; i++) {
        p = p->next;
        if (p == NULL) {
            return false; // 不存在此下标
        }
    }
    DLinkListNode *q = p->next; // 被删除的元素
    if (q == NULL) { // 当q为链表末尾时，则被删除的元素不存在
        return false;
    }
    p->next = q->next;
    if (q->next != NULL) {
        q->next->prev = p;
    }
    delete q; // 释放空间
    return true;
}

顺序栈SeqStack

顺序栈定义

// 最大空间
#define SEQ_STACK_MAX_SIZE 100

// 顺序栈
struct SeqStack {
    int data[SEQ_STACK_MAX_SIZE];
    int top; // 栈顶指针
};

初始化

void SeqStackInitStack(SeqStack &stack) {
    stack.top = -1; // 使用-1标识为空栈
}

判断是否为空

bool SeqStackIsEmpty(SeqStack &stack) {
    return stack.top == -1;
}

进栈

bool SeqStackPush(SeqStack &stack, int data) {
    if (stack.top == SEQ_STACK_MAX_SIZE - 1) {
        return false; // 空间不够
    }
    stack.data[++stack.top] = data; // 指针后移并添加元素
    return true;
}

出栈

bool SeqStackPop(SeqStack &stack, int &data) {
    if (stack.top == -1) {
        return false; // 没有元素
    }
    data = stack.data[stack.top--]; // 删除元素并将指针前移
    return true;
}

读取栈顶元素

bool SeqStackGetTop(SeqStack &stack, int &data) {
    if (stack.top == -1) {
        return false; // 没有元素
    }
    data = stack.data[stack.top];
    return true;
}

循环顺序队列CircleQueue

循环顺序队列定义

// 最大空间
#define CIRCLE_QUEUE_MAX_SIZE 10

// 循环顺序队列
struct CircleQueue {
    int data[CIRCLE_QUEUE_MAX_SIZE];
    int front, rear; // 头指针和尾指针
};

初始化

void CircleQueueInit(CircleQueue &queue) {
    queue.front = queue.rear = 0;
}

判断队列是否为空

bool CircleQueueIsEmpty(CircleQueue &queue) {
    return queue.front == queue.rear;
}

判断队列是否已满

bool CircleQueueIsFull(CircleQueue &queue) {
    return (queue.rear + 1) % CIRCLE_QUEUE_MAX_SIZE == queue.front; // 队尾的下一个位置是队头，则说明队满
}

获取队列长度

int CircleQueueLength(CircleQueue &queue) {
    return (queue.rear - queue.front + CIRCLE_QUEUE_MAX_SIZE) % CIRCLE_QUEUE_MAX_SIZE;
}

进队

bool CircleQueuePush(CircleQueue &queue, int data) {
    if (CircleQueueIsFull(queue)) { // 如果队列已满，则无法进队
        return false;
    }
    queue.data[(queue.rear++) % CIRCLE_QUEUE_MAX_SIZE] = data; // 取模实现循环
    return true;
}

出队

bool CircleQueuePop(CircleQueue &queue, int &data) {
    if (CircleQueueIsEmpty(queue)) { // 如果队列为空，则无法出队
        return false;
    }
    data = queue.data[(queue.front++) % CIRCLE_QUEUE_MAX_SIZE];
    return true;
}

链队列LinkQueue

链队列定义

// 链队列节点
struct LinkQueueNode {
    int data;
    LinkQueueNode *next;
};

// 链队列
struct LinkQueue {
    LinkQueueNode *front, *rear; // 头指针和尾指针
};

初始化

void LinkQueueInit(LinkQueue &queue) {
    LinkQueueNode *head = new LinkQueueNode(); // 头节点
    queue.front = queue.rear = head;
}

判断队列是否为空

bool LinkQueueIsEmpty(LinkQueue &queue) {
    return queue.front == queue.rear;
}

获取队列长度

int LinkQueueLength(LinkQueue &queue) {
    int length = 0;
    // 遍历链表直到为空
    LinkQueueNode *p = queue.front->next;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

进队

void LinkQueuePush(LinkQueue &queue, int data) {
    LinkQueueNode *node = new LinkQueueNode(); // 头节点
    node->data = data;
    queue.rear->next = node;
    queue.rear = queue.rear->next;
}

出队

bool LinkQueuePop(LinkQueue &queue, int &data) {
    if (LinkQueueIsEmpty(queue)) {
        return false; // 队列为空
    }
    LinkQueueNode *head = queue.front; // 头节点
    LinkQueueNode *node = head->next;
    data = node->data;
    queue.front = node; // 新的头节点
    delete head; // 释放空间
    return true;
}