手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

【全球报资讯】考研数据结构模板：顺序表、链表、栈、队列

2023-04-17 06:07:20 来源：博客园

【资料图】

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

前言

代码风格偏向于考研风格而非算法竞赛风格。
代码实现参考《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 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;}

关键词：