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

2023年4月17日下午1:58 • 算法与数据结构

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

前言

代码风格偏向于考研风格而非算法竞赛风格。
代码实现参考《2024数据结构王道复习指导》。
注释详细、保证看懂。
下面是已实现的数据结构模板：
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 SEQ_LIST_INIT_SIZE 10

初始化

void SeqListInitial(SeqList &list) {
    list.maxLength = SEQ_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;
}

原文链接：https://www.cnblogs.com/kkelin/p/17324548.html

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：考研数据结构模板：顺序表、链表、栈、队列 - Python技术站

数据结构珂霖算法

0 0 打赏

微信扫一扫

支付宝扫一扫

手动实现数据结构-栈结构

上一篇 2023年4月17日

数据结构之哈夫曼树与哈夫曼编码

下一篇 2023年4月17日

详解Python牛顿插值法

以下是关于“Python牛顿插值法”的完整攻略：简介牛顿插值法是一种用于插值的数值分析方法，它可以通过已知的数据点来构造一个多项式函数，从而在数据点之间进行插值。在本教程中，我们将介绍如何使用Python实现牛顿插值法，并提供两个示例说明。实现牛顿插值法以下是使用Python实现牛顿插值法的代码： def newton_interpolation(x…

python 2023年5月14日
000
手动实现数据结构-栈结构

1.栈结构是一种受限的线性结构。特点：先进后出 2.使用TS实现 1 //封装一个栈使用泛型类 2 class ArrayStack<T=any>{//给一个默认值为any类型 3 //定义一个数组，用于存储元素 4 private data:T[]=[] 5 //push:将元素压入栈中 6 push(e:T):void{ 7 this.…

算法与数据结构 2023年4月17日
000
Python实现的朴素贝叶斯分类器示例

以下是关于“Python实现的朴素贝叶斯分类器示例”的完整攻略：简介朴素贝叶斯分类器是一种常用的机器学习算法，用于分类和预测。在本教程中，我们将介绍如何使用Python实现一个朴素贝叶斯分类器，包括数据预处理、特征提取、模型训练和预测等步骤。原理朴素贝叶斯分类器是一种基于贝叶斯定理的分类器，它假设特征之间相互独立，从而简化了计算。在本教程中，我们将使…

python 2023年5月14日
000
Python机器学习之逻辑回归

Python机器学习之逻辑回归逻辑回归（Logistic Regression）是一种常用的分类算法，它可以用于二分类和多分类问题。在这篇文章中，我们将介绍如何使用Python实现逻辑回归算法，并详细讲解实现原理。实现原理逻辑回归是一种基于概率的分类算法，它的目标是根据输入特征预测样本属于哪个类别。逻辑回归的实现原理如下：首先定义一个逻辑回归模型，包…

python 2023年5月14日
000
一些常见的字符串匹配算法

作者：京东零售李文涛一、简介 1.1 Background 字符串匹配在文本处理的广泛领域中是一个非常重要的主题。字符串匹配包括在文本中找到一个，或者更一般地说，所有字符串(通常来讲称其为模式)的出现。该模式表示为p=p[0..m-1];它的长度等于m。文本表示为t=t[0..n-1],它的长度等于n。两个字符串都建立在一个有限的字符集上。一个比较常见…

算法与数据结构 2023年4月25日
000
C语言中数据结构之链式基数排序

C语言中数据结构之链式基数排序概述链式基数排序是基数排序的一种实现方式。基数排序是一种桶排序算法，它通过将需要排序的数据分成多个桶，并且按照一定的顺序将数据从桶中取出来，以达到排序的目的。链式基数排序则使用了链表结构来实现桶的功能。实现步骤链式基数排序的实现步骤如下：申请链表节点数组，并初始化链表头结点数组。链表的数量等于指定的基数，例如10进制的…

数据结构 2023年5月17日
000
Python实现遗传算法(二进制编码)求函数最优值方式

下面是详细讲解“Python实现遗传算法(二进制编码)求函数最优值方式”的完整攻略，包括算法原理、Python实现和两个示例。算法原理遗传算法是一种基于自然选择和遗传机制的优化算法，其主要思想是通过模拟生物进化过程，寻找最优解。在二进制编码的遗传算法中，每个个体用一个二进制串表示，通过不断交叉、变异和选择操作，寻找最优解。二进制编码的遗传算法的实现过程…

python 2023年5月14日
000
Java数据结构之队列(动力节点Java学院整理)

Java数据结构之队列(动力节点Java学院整理) 队列是一种有序列表，在其中所有插入操作必须在后端进行，而所有的删除操作必须在前端进行的数据结构。这种结构有时被称为先进先出（FIFO）。队列的分类普通队列：队列和栈一样，都是只能在一端进行插入操作，在另一端进行删除操作的特殊线性表。队列的特点是：先进先出。适用于数据必须按照插入顺序处理的必要场合。双端…

数据结构 2023年5月17日
000

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

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

前言

顺序表SeqList

顺序表定义

初始化

判断是否为空

查询元素长度

打印元素

插入元素

删除元素

查询元素位置

查询位置上的元素值

链表LinkList

链表定义

空元素初始化

数组初始化

查询元素长度

打印元素

插入元素

删除元素

查询位置上的元素值

双链表DLinkList

双链表定义

初始化

打印元素

插入元素

删除元素

顺序栈SeqStack

顺序栈定义

初始化

判断是否为空

进栈

出栈

读取栈顶元素

循环顺序队列CircleQueue

循环顺序队列定义

初始化

判断队列是否为空

判断队列是否已满

获取队列长度

进队

出队

链队列LinkQueue

链队列定义

初始化

判断队列是否为空

获取队列长度

进队

出队

相关文章