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

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 2023年5月13日
000
C语言树状数组的实例详解

首先需要了解什么是树状数组。树状数组（Binary Indexed Tree，BIT），也叫做 Fenwick 树（树状数组的发明者是Peter M. Fenwick），是一个查询和修改复杂度都为 log(n) 的数据结构，与线段树类似，但使用起来比线段树更加方便以及简洁。在该攻略中，我们将通过两条树状数组的实例，详细讲解树状数组，让读者更好地理解树状数组…

数据结构 2023年5月17日
000
Python实现KNN邻近算法

Python实现KNN邻近算法的完整攻略 KNN算法是一种常用的机器学习算法，用于分类和回归问题。本文将详细讲解Python实现KNN算法的整个攻略，包括算法原理实现过和示例。算法原理 KNN算法的基本思想是通过计算待分类样本与训练集中所有样本距离选取距近的k样本，根据这k个样本的类别进行投票，将待分类样归票数多的类别。在回归中，KNN算法的基本思想是通过…

python 2023年5月14日
000
python 排序算法总结及实例详解

Python排序算法总结及实例详解排序算法是计算机科学中的基本问题之一，它的目的是将一组数据按照一定的顺序排列。在Python中，我们可以使用多种排序算法来对数据进行排序。本文将介绍常见的排序算法及其Python实现，并提供两个示例说明。常见的排序算法冒泡排序冒泡排序是一种简单的排序算法，它的基本思想是通过不断交换相邻的元素，将较大的元素逐渐“冒泡”…

python 2023年5月13日
000
Java实现链表数据结构的方法

Java实现链表数据结构的方法可以分为以下步骤：定义链表节点类Node 首先，在Java中实现链表数据结构，需要定义一个链表节点类，称为Node。Node类中包含两个重要属性：数据域data，用于存储每个节点的数据信息。指针域next，用于存储下一个节点的引用。代码示例： public class Node { public int data; //…

数据结构 2023年5月17日
000
C语言数据结构与算法之链表(一)

欢迎阅读本篇文章，本文将为大家详细讲解C语言中数据结构与算法之链表。接下来，将从以下几个方面为大家讲述：链表的定义链表的特点链表的分类单向链表的实现及应用双向链表的实现及应用示例说明 1. 链表的定义链表是由一系列节点组合而成的数据结构，每个节点都包含了一个数据域和一个指向下一个节点的指针域。其中，链表的头结点为第一个节点，而尾节点为最后一个节…

数据结构 2023年5月17日
000
java数据结构与算法数组模拟队列示例详解

下面是“java数据结构与算法数组模拟队列示例详解”的完整攻略。标题 Java数据结构与算法：数组模拟队列示例详解简介本文将以Java语言为例，详细讲解如何使用数组模拟队列。对于初学者来说，队列是一个非常基础的数据结构，掌握其实现方法可以帮助进一步理解其他的数据结构和算法。队列的定义队列（Queue）是一种先进先出（First In First O…

数据结构 2023年5月17日
000
Java数据结构之单链表的实现与面试题汇总

Java数据结构之单链表的实现与面试题汇总一、前言单链表是数据结构中最基础的数据结构之一，也是在面试时经常会考察的一个知识点。本文将详细介绍单链表的实现过程，并对常见的单链表面试题进行总结，帮助大家深入了解单链表的原理和应用。二、单链表的实现单链表是由一些列节点构成的，每个节点包括一个数据和一个指向下一个节点的指针。下面我们将实现一个简单的单链表，并…

数据结构 2023年5月17日
000

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

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

前言

顺序表SeqList

顺序表定义

初始化

判断是否为空

查询元素长度

打印元素

插入元素

删除元素

查询元素位置

查询位置上的元素值

链表LinkList

链表定义

空元素初始化

数组初始化

查询元素长度

打印元素

插入元素

删除元素

查询位置上的元素值

双链表DLinkList

双链表定义

初始化

打印元素

插入元素

删除元素

顺序栈SeqStack

顺序栈定义

初始化

判断是否为空

进栈

出栈

读取栈顶元素

循环顺序队列CircleQueue

循环顺序队列定义

初始化

判断队列是否为空

判断队列是否已满

获取队列长度

进队

出队

链队列LinkQueue

链队列定义

初始化

判断队列是否为空

获取队列长度

进队

出队

相关文章