数据结构笔记【2】

链式存储

线性表之单链表

将线性表的个元素分布在存储器的不同存储块，称为结点，通过地址或指针建立元素之间的联系。

结点分为data域和next域，next域是一个指针，指向 $a_i$ 的直接后继 $a_{i+1}$ 的所在结点。next为NULL时表明该元素为链表最后一个元素。

头结点：data不重要，专门用来标记第一个元素的结点地址

结点类型描述:

typedef struct node
{
    data_t data;    //数据域
    struct node *next;  //结点的后继指针域
}listnode, *linklist;   //linklist 是一个指向链表的指针类型，用于操作链表的头指针

所以有

1 2	`listnode A; // 定义一个结点 linklist p = &A; // 定义一个链表头指针，并指向 A 结点`

获取 $a_i$ : p->data;
获取 $a_{i+1}$ : p->next->data;

若指针p的值为NULL，则其不指向任何结点，此时取p->data或p->next是错误的

单链表的遍历

线性存储中，遍历基于表尾标识符last完成，索引 $i$ 从0循环到last视为遍历一次。

链式存储中，节点之间由next进行后继连接，所以遍历应当从头节点开始，由head = head->next方式进行索引（指针）更新

示例：

/*
    * @brief: 遍历链表并打印其中的元素
    * @param: H: 指向链表的指针
    * @return: 遍历成功返回0，失败返回-1
*/
int list_show(linklist H)
{
    linklist p;

    if (H == NULL) // 如果链表为空，直接返回 NULL
    {
        printf("H is NULL\n");
        return -1;
    }

    p = H->next; //p 指向头结点的下一个节点 注意：这里不是线性存储，节点之间通过指针连接，不能写成p=H+1
    while (p != NULL)
    {
        printf("%d ",p->data);
        p = p->next;  //p指向下一个节点
    }

    return 0;
}

单链表获取指定位置的节点地址

头节点只有Next域，没有data域；尾节点只有data域，Next域为NULL。

list_get()函数遍历到指定链表的pos位置，遍历到之后返回最后一个节点的指针。注意遍历可以有两种方式：

从头节点开始，初始化p = head,i = -1，遍历到i < pos时结束，此时的pos是包含头节点在内的位置，比如链表{1,2,6,3}，元素2的位置是2，不是1；
从头节点之后的第一个结点开始，初始化p = head->next; i = 0，遍历到i < pos时结束，此时的pos是不包含头节点在内的位置，比如链表{1,2,6,3}，元素2的位置是1；

/*
    * @brief: 获取链表中指定位置的节点地址
    * @param: H: 指向链表的指针
    * @param: pos: 指定的位置
    * @return: 插入成功返回找到的结点，失败返回NULL
*/
linklist list_get(linklist H, int pos)
{
    linklist p; // 声明一个指向链表节点的指针，用于遍历链表
    int i = -1; // 用于记录遍历位置，初始化为-1以考虑头结点

    if (H == NULL) // 如果链表为空，直接返回 NULL
    {
        printf("H is NULL\n");
        return NULL;
    }

    if (pos == -1) // 如果 pos == -1，返回头结点
    {
        return H;
    }

    p = H; // 从头结点的下一个节点开始遍历
    while (i < pos) // 当 i 小于 pos 时继续循环
    {
        p = p->next; // 移动到下一个节点
        if (p == NULL)  // 如果链表到达了末尾，且还没找到 pos，返回 NULL
        {
            printf("pos is invalid\n");
            return NULL;
        }
        i++; // 记录当前遍历到的节点编号
    }

    return p; // 返回找到的节点
}

单链表的其他操作

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"

/*
    * @brief: 创建一个空的链式线性表
    * @param: 无
    * @return: 返回链表的头指针
*/
linklist list_create()
{
    linklist head = (linklist)malloc(sizeof(listnode));

    if (head == NULL)
    {
        printf("memory allocation failed\n");
        return NULL;
    }
    head->next = NULL;  // 初始化头结点的指针域为空，表示链表为空
    return head;
}

/*
    * @brief: 插入元素到链表中
    * @param: head: 指向链表头结点的指针
    * @param: value: 要插入的值
    * @param: pos：插入位置，新的节点会放置在该位置之后
    * @return: 插入成功返回0，失败返回-1
*/
int list_insert(linklist head, data_t value, int pos)
{
    if (head == NULL) return -1;  // 检查链表是否存在

    // 如果要在第 0 位插入节点（头结点之后）
    if (pos == 0)
    {
        linklist new_node = (linklist)malloc(sizeof(listnode));   //为新节点申请内存 
        if (new_node == NULL)
        {
            printf("memory allocation failed\n");
            return -1;
        }

        new_node->data = value;   // 新节点的数据域赋值
        new_node->next = head->next;  // 新节点指向头结点后的第一个节点
        head->next = new_node;  // 头结点的next指向新插入的节点
        return 0;
    }

    // 否则查找 pos-1 位置的前驱节点
    linklist prev_node = list_get(head, pos-1);
    if (prev_node == NULL)
    {
        printf("Invalid position\n");
        return -1;
    }

    // 为新节点申请内存
    linklist new_node = (linklist)malloc(sizeof(listnode));   
    if (new_node == NULL)
    {
        printf("memory allocation failed\n");
        return -1;
    }

    new_node->data = value;  // 设置新节点的数据
    new_node->next = prev_node->next;  // 新节点指向原链表在插入位置后的节点
    prev_node->next = new_node;  // 前驱节点替换为新插入的节点

    return 0;
}


/*
    * @brief: 获取链表中指定位置的节点地址
    * @param: H: 指向链表的指针
    * @param: pos: 指定的位置
    * @return: 插入成功返回找到的结点，失败返回NULL
*/
linklist list_get(linklist H, int pos)
{
    linklist p; // 声明一个指向链表节点的指针，用于遍历链表
    int i = -1; // 用于记录遍历位置，初始化为-1以考虑头结点

    if (H == NULL) // 如果链表为空，直接返回 NULL
    {
        printf("H is NULL\n");
        return NULL;
    }

    if (pos == -1) // 如果 pos == -1，返回头结点
    {
        return H;
    }

    p = H; // 从头结点开始遍历
    while (i < pos) // 当 i 小于 pos 时继续循环
    {
        p = p->next; // 移动到下一个节点
        if (p == NULL)  // 如果链表到达了末尾，且还没找到 pos，返回 NULL
        {
            printf("pos is invalid\n");
            return NULL;
        }
        i++; // 记录当前遍历到的节点编号
    }

    return p; // 返回找到的节点
}

/*
    * @brief: 遍历链表并打印其中的元素
    * @param: H: 指向链表的指针
    * @return: 遍历成功返回0，失败返回-1
*/
int list_show(linklist H)
{
    linklist p;

    if (H == NULL) // 如果链表为空，直接返回 NULL
    {
        printf("H is NULL\n");
        return -1;
    }

    p = H->next; //p 指向头结点的下一个节点 注意：这里不是线性存储，节点之间通过指针连接，不能写成p=H+1
    while (p != NULL)
    {
        printf("%d ",p->data);
        p = p->next;  //p指向下一个节点
    }

    return 0;
}

/*
    * @brief: 遍历链表并查找指定的值
    * @param: H: 指向链表的指针
    * @return: 查找成功返回0，失败返回-1
*/
int list_search(linklist H, data_t value)
{
    if (H == NULL) // 如果链表为空，直接返回 NULL
    {
        printf("H is NULL\n");
        return -1;
    }

    linklist p = H->next;
    int i = 0; //初始化节点索引为-1

    while (p != NULL)
    {
        if (p->data == value)
        {
            printf("search ok, pos is %d\n",i);
        }
        i++;
        p = p->next;   //更新指针，指向下一个节点
    }

    return 0;
}

/*
    * @brief: 合并两个链表，然后存储到新链表中
    * @param: H1: 指向链表1的指针
    * @param: H2: 指向链表2的指针
    * @return: 返回表3
*/
linklist list_merge(linklist H1, linklist H2)
{
    if (H1 == NULL || H2 == NULL) 
    {
        printf("H1 or H2 is null\n");
        return NULL;
    }
    
    linklist H3 = list_create();    //创建新表

    //拷贝H1至H3
    linklist TempPtr1 = H1->next;   //声明TempPtr指向H1的下一个节点，跳过头节点
    int count1 = 0;
    while (TempPtr1 != NULL)
    {
        list_insert(H3, TempPtr1->data, count1);    //向H3插入H1的data
        TempPtr1 = TempPtr1->next;  //更新指针
        count1++;   //更新计数器
    } 

    linklist TempPtr2 = H2->next;
    int count2 = 0;
    while (TempPtr2 != NULL)
    {
        list_insert(H3, TempPtr2->data, count1 + count2);
        TempPtr2 = TempPtr2->next;
        count2++;
    }

    return H3;
}

/*
    * @brief: 删除两个链表中的重复部分，将剩余元素存在新表中
    * @param: H1: 指向链表1的指针
    * @param: H2: 指向链表2的指针
    * @return: 返回表3
    * @note: 仅适用于小链表，大链表可以用哈希表
*/
linklist list_purge(linklist H1, linklist H2)
{
    if (H1 == NULL || H2 == NULL) 
    {
        printf("H1 or H2 is null\n");
        return NULL;
    }

    linklist H3 = list_create();

    int is_common = 0;  //初始化标记，09为不重复，1为重复

    linklist TempPtr1 = H1->next;   //初始化Ptr1指向H1的第一个有效节点
    while (TempPtr1 != NULL)
    {
        linklist TempPtr2 = H2->next;   // 每次遍历TempPtr1时，重置TempPtr2，否则TempPtr2一旦遍历到NULL后不会返回
        while (TempPtr2 != NULL)
        {
            if (TempPtr1->data == TempPtr2->data)
            {
                printf("common elements:%d\n",TempPtr2->data);
                
                is_common = 1;
                list_insert(H3, TempPtr2->data, 0);
            }
            TempPtr2 = TempPtr2->next;  //更新TempPtr2
        }

        if (is_common == 0)  // 如果不是重复元素，插入到H3中
        {
            list_insert(H3, TempPtr1->data, 0);
        }
        TempPtr1 = TempPtr1->next;  //更新TempPtr1
    }

    return H3;
}

/*
    * @brief: 删除指定位置的节点
    * @param: H: 指向链表的指针
    * @param: pos：待删除结点的位置
    * @return: 成功返回0，失败返回-1
*/
int list_delete(linklist H, int pos)
{
    if (H == NULL) 
    {
        printf("no such linklist\n");
        return -1;
    }

    // 如果删除的位置是第一个节点
    if (pos == 1)
    {
        linklist TempPtr = H->next; // 保存下一个节点
        free(H); // 释放头节点
        H = TempPtr; // 更新头指针
        return 0;
    }

    // 获取待删除节点的前一个节点
    linklist Prev_Node = list_get(H, pos - 1);
    if (Prev_Node == NULL || Prev_Node->next == NULL)
    {
        printf("invalid position\n");
        return -1;
    }

    // 获取待删除的节点
    linklist TempPtr = Prev_Node->next;
    Prev_Node->next = TempPtr->next; // 连接前后节点
    free(TempPtr); // 释放被删除的节点

    return 0;
}

/*
    * @brief: 删除整个链表并释放内存
    * @param: H: 指向链表的指针
    * @return: 成功返回0，失败返回-1
*/
int list_free(linklist H)
{
    if (H == NULL)
    {
        printf("no such linklist\n");
        return -1;
    }

    linklist TempPtr = H;

    while (H != NULL)
    {
        TempPtr = H;    // 保存当前节点
        H = H->next;    // 更新链表头指针为下一个节点
        free(TempPtr);  // 释放当前节点
    }

    return 0;
}

/*
    * @brief: 倒置链表
    * @param: H: 指向链表的指针
    * @return: 成功返回0，失败返回-1
    * @note: 将节点拿出放到
*/
int list_reverse(linklist H)
{
    if (H == NULL)
    {
        printf("no such linklist\n");
        return -1;
    }

    if (H->next == NULL)
    {
        printf("linklist is empty\n");
        return -1;
    }

    //链表一分为二
    linklist p = H->next->next;
    H->next->next = NULL;

    
    while (p != NULL)
    {
        linklist q = p; // 暂存当前节点
        p = p->next;    // 移动到下一个节点
        q->next = H->next; // 将当前节点插入到链表头部（头插法）
        H->next = q; // 更新头节点为新插入的节点
    }

    return 0;
}

/*
    * @brief: 求链表相邻两节点data值之和为最大的第一结点的指针
    * @param: H: 指向链表的指针
    * @return: 成功返回指针，失败返回NULL
*/
int list_getmax(linklist H)
{
    if (H == NULL)
    {
        printf("no such linklist\n");
        return -1;
    }

    if (H->next == NULL)
    {
        printf("linklist is empty\n");
        return -1;
    }

    int sum_new, max = 0;
    linklist p = H->next;
    linklist max_p = H->next;
    int sum = p->data + p->next->data;

    while (p != NULL && p->next != NULL)
    {
        sum_new = p->data + p->next->data;
        
        if (sum_new >= max)
        {
            max = sum_new;
            max_p = p;
        }

        p = p->next;
    }
    //printf("max sum is %d",max);
    return max;
}

栈(Stack)

和微机原理中栈的原理相同

注意：

先进后出
注意栈顶指针的更新

栈主要用于以下场景：

函数调用：使用栈来保存当前函数的局部变量、返回地址等信息。当函数调用另一个函数时，新的函数信息被压入栈中，函数执行完毕后会从栈中弹出，返回上一个函数。
撤销操作
递归
二叉树遍历

#include <stdio.h>
#include <stdlib.h>
#include "linear_stack.h"
#include <string.h>

/*
    @brief: 创建新的栈
    @param: len: 栈的长度
    @return: 指向栈的指针
*/
sqstack *stack_create(int len)
{
    if (len < 0)
    {
        printf("len is illegal\n");
        return NULL;
    }

    sqstack *ss;

    //申请用于放置结构体的内存
    ss = (sqstack *)malloc(sizeof(sqstack));   
    if (ss == NULL) {
        printf("Failed to allocate memory for stack.\n");
        return NULL;
    }

    //申请用于放置栈内数据的内存
    ss->data = (data_t *)malloc(sizeof(data_t) * len);
    if (ss->data == NULL) {
        printf("Failed to allocate memory for stack data.\n");
        free(ss);  
        return NULL;
    }

    memset(ss->data, 0, len*sizeof(data_t));
    ss->top = -1;
    ss->maxlen = len;

    return ss;
}

/*
    @brief: 入栈
    @param: s：对应栈指针 value：待入栈值
    @return: 成功返回0，失败返回-1
*/
int stack_push(sqstack *s, data_t value)
{
    if (s == NULL)
    {
        printf("no such stack\n");
        return -1;
    }
    if (s->top == s->maxlen - 1)
    {
        printf("stack is full\n");
        return -1;
    }

    s->top++;
    s->data[s->top] = value;

    printf("stack push ok\n");
    return 0;
}

/*
    @brief: 判断栈是否为空
    @param: s：对应栈指针
    @return: 栈为空返回-1，非空返回0，函数非法返回-2
*/
int stack_empty(sqstack *s)
{
    if (s == NULL)
    {
        printf("no such stack\n");
        return -2;
    }

    if (s->top == -1)
    {
        printf("stack is empty\n");
        return -1;
    }
    else
    {
        return 0;
    }
}

/*
    @brief: 判断栈是否为满
    @param: s：对应栈指针
    @return: 栈为满返回-1，非满返回0，函数非法返回-2
*/
int stack_full(sqstack *s)
{
    if (s == NULL)
    {
        printf("no such stack\n");
        return -2;
    }

    if (s->top == s->maxlen - 1)
    {
        printf("stack is full\n");
        return -1;
    }
    else
    {
        return 0;
    }
}

/*
    @brief: 数据出栈
    @param: s：对应栈指针
    @return: 返回出栈值，如果栈为空或出错则返回-999
*/
data_t stack_pop(sqstack *s)
{
    if (s == NULL)
    {
        printf("Stack not initialized\n");
        return -999;  
    }

    if (s->top == -1)
    {
        printf("Stack is empty\n");
        return -999;  
    }
     
    data_t temp = s->data[s->top];
    s->top--;
    return temp;
}

/*
    @brief: 清除栈内所有元素
    @param: s：对应栈指针
    @return: 成功返回0，失败返回-1
*/
int stack_clear(sqstack *s)
{
    if (s == NULL)
    {
        printf("Stack not initialized\n");
        return -1;  
    }

    if (s->top == -1)
    {
        return 0;  
    }

    //一般的栈清空操作只会重置 top，但不释放内存
    s->top = -1;
    //free(s->data);
    //s->data = NULL;

    return 0;
}

/*
    @brief: 释放整个栈的空间
    @param: s：对应栈指针
    @return: 成功返回0，失败返回-1
*/
int stack_free(sqstack *s)
{
    if (s == NULL)
    {
        printf("Stack not initialized\n");
        return -1;  
    }

    free(s->data);
    s->data = NULL;
    free(s);

    return 0;
}

队列(Queue)

基于数组的队列

等同于现实生活中的“排队”，元素从列尾存入，列首取出

双端队列：列首和列尾都可以进行存入和取出；或解释为：同一个队列共享列首和列尾

队列多被用于：

任务调度
消息队列
IO请求管理（确保系统资源的有序访问）

队列结构体一般为

typedef int data_t;
#define N 64
typedef struct 
{
    data_t data[N];
    int front, rear;    //rear为队尾后一个元素的下标
}sequeue_t;

其中rear一般指示队尾元素的下一个位置，也就是下一个要入队的元素位置。用于处理队列为空或只有一个元素时的情况。头尾位置重合时，队列即为空。
初始front, rear = 0;

出队列：x = sq[front++]
入队列：sq[rear++] = x;

当队列中前几个元素出队时，会造成这些位置为空，从而浪费队列中的可存储空间。此时可以使用循环队列。
为区别空队和满队，满队元素个数比数组元素个数少一个。

/*
    @brief: 创建空队列
    @param: 无
    @return: 指向队列的指针
*/
sequeue queue_create()
{
    sequeue qq = (struct queue*)malloc(sizeof(struct queue));

    if (qq == NULL)
    {
        printf("malloc failed\n");
        return NULL;
    }

    qq->front = 0;
    qq->rear = 0;

    memset(qq->data, 0, sizeof(qq->data));

    return qq;
}

/*
    @brief: 遍历并打印队列
    @param: q：队列指针
    @return: 成功返回0，失败返回-1
*/
int queue_print(sequeue q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if (q->front == q->rear)
    {
        printf("queue is empty");
        return -1;
    }

    for (int i = q->front; i < q->rear; i++)
    {
        printf("%d ", q->data[i]);
    }

    return 0;
}

/*
    @brief: 元素入队
    @param: q：队列指针 data：待入队元素
    @return: 成功返回0，失败返回-1
*/
int enqueue(sequeue q, data_t data)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if ((q->rear + 1) % N == q->front)
    {
        printf("queue is full\n");
        return -1;
    }

    q->data[q->rear] = data;
    q->rear = (q->rear + 1) % N;    // rear 指针移动到队列边界时，通过取余使其返回到数组开头，实现循环

    return 0;
}

/*
    @brief: 元素出队
    @param: q：队列指针
    @return: 成功返回出队元素，失败返回-1
    @note: 出队元素为队首的第一个元素
*/
int dequeue(sequeue q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if (q->front == q->rear)
    {
        printf("queue is empty");
        return -1;
    }

    int temp = q->data[q->front];
    q->front = (q->front + 1) % N;

    return temp;
}

/*
    @brief: 清空队列内元素，但不释放内存
    @param: q：队列指针
    @return: 成功返回0，失败返回-1
    @note: 
*/
int queue_clear(sequeue q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    q->front = 0;
    q->rear = 0;

    return 0;
}

基于链式存储的队列

插入操作在队尾进行，删除操作在队首进行，由队首指针和队尾指针控制队列操作

结构体需要定义两个：节点结构体和队列结构体

typedef int data_t;

typedef struct node
{
    data_t data;
    struct node* next;
}*linklist;

typedef struct queue
{
    linklist front;
    linklist rear;
};

初始化：创建空队列，front和rear指针都为空
入队：在队尾新增一个节点，并更新当前队尾节点的next指针
出队：更新front指针到待出队节点的下一个节点，然后删除原有队首节点

与线性表不同的是，链式队列中rear指针一般指向最后队列的一个节点，而非最后一个节点的下一个节点。

判断链式队列是否为空的条件只有一个：front == NULL, rear == NULL，不能使用front==rear判断，因为这里front和rear都是指针，并且rear指向的是最后一个节点，而非线性队列中的指向最后一个位置的下一个位置（待插入位置）。假设队伍中只有一个元素，这时候front和rear二者相同，但队列不为空。

创建新的链式队列

/*
    @ brief：创建并初始化新的链式队列
    @param：无
    @return：成功指向新队列的指针，失败返回NULL
*/
struct queue* queue_create()
{
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));

    if (q == NULL)
    {
        printf("malloc failed\n");
        return NULL;
    }

    q->front = NULL;
    q->rear = NULL;

    return q;
}

为队列申请内存，暂时先不申请节点的，因为这是一个空队列，目前还没有元素
因为队列中没有节点，front和rear指针都为NULL

遍历队列

/*
    @ brief：遍历链式队列并打印所有元素
    @param：q：队列指针
    @return：成功返回0，失败返回-1
*/
int queue_print(struct queue* q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if (q->front == NULL)
    {
        printf("queue is empty\n");
        return -1;
    }

    struct node* temp = q->front;

    while (temp != NULL)
    {
        printf("%d", temp->data);
        temp = temp->next;
    }

    printf("\n");

    return 0;
}

在遍历时要用临时指针temp来代替front，如果直接用front指针的话，遍历一次之后front就回不去了，整个队列会被破坏
尽量不要在遍历前用temp存储front指针，用front指针遍历完之后再front = temp这种形式返回回去的这种方法，在多线程的时候可能会有问题
遍历结束的条件是当temp指针走到NULL之后，表明从队首节点到队尾节点全都扫描到了，而不是temp(front)=rear或者temp(front)=rear->next，因为链式队列中rear指针指向的是最后一个（队尾）节点

其他

/*
    @ brief：创建并初始化新的链式队列
    @param：无
    @return：成功指向新队列的指针，失败返回NULL
*/
struct queue* queue_create()
{
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));

    if (q == NULL)
    {
        printf("malloc failed\n");
        return NULL;
    }

    q->front = NULL;
    q->rear = NULL;

    return q;
}

/*
    @ brief：遍历链式队列并打印所有元素
    @param：q：队列指针
    @return：成功返回0，失败返回-1
*/
int queue_print(struct queue* q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if (q->front == NULL)
    {
        printf("queue is empty\n");
        return -1;
    }

    struct node* temp = q->front;

    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    printf("\n");

    return 0;
}


/*
    @ brief：元素入队
    @param：q：队列指针 val：待入队元素值
    @return：成功返回0，失败返回-1
*/
int enqueue(struct queue* q, data_t val)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }
    struct node* newnode = (struct node*)malloc(sizeof(struct node));

    newnode->data = val;
    newnode->next = NULL;

    //判断原队列是否为空
    if (q->rear == NULL)
    {
        q->front = newnode;
        q->rear = newnode;
    }
    else
    {  
        q->rear->next = newnode;
        q->rear = newnode;
    }

    return 0;
}

/*
    @ brief：元素出队
    @param：q：队列指针
    @return：成功返回0，失败返回-1
*/
int dequeue(struct queue* q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if (q->front == NULL)
    {
        printf("queue is empty\n");
        return -1;
    }

    struct node* temp_node = q->front;
    int temp = temp_node->data;
    q->front = q->front->next;

    // 如果队列为空，则需要更新 rear 为 NULL
    if (q->front == NULL)
    {
        q->rear = NULL;
    }

    free(temp_node);

    return temp;
}

/*
    @ brief：清空队列并删除对应节点
    @param：q：队列指针
    @return：成功返回0，失败返回-1
*/
int queue_clear(struct queue* q)
{
    if (q == NULL)
    {
        printf("no such queue\n");
        return -1;
    }

    if (q->front == NULL)
    {
        return 0;
    }

    //临时节点，用于储存待删除的节点而不影响后续节点的遍历
    struct node* temp;  
    
    while (q->front != NULL)
    {
        temp = q->front;
        q->front = q->front->next;
        free(temp);
    }

    q->rear = NULL;

    return 0;
}

球钟问题（队列和栈的应用）

球钟问题（Ball Clock Problem）是一种经典的算法和数据结构题目，主要用于考察队列和栈的结合运用。问题的基本情景是：
假设有一个球钟系统，它通过小球来计时。系统中有 3 个轨道，每个轨道容量不同：

分钟轨道（Min Track）：最多可容纳 4 个小球。
五分钟轨道（Five-Min Track）：最多可容纳 11 个小球。
小时轨道（Hour Track）：最多可容纳 11 个小球。

运作机制：

初始状态下有一组编号为 1 到 n 的小球，n 是球的总数，这些小球依次通过队列进行处理。
每分钟，第一个小球从队列中取出，放到分钟轨道上。
当分钟轨道满（即放入第5个小球时），轨道中的 4 个小球被依次放回队列，保持原来的顺序，而第 5 个小球则进入五分钟轨道。
当五分钟轨道满（即放入第12个小球时），轨道中的 11 个小球被依次放回队列，第 12 个小球进入小时轨道。
当小时轨道满（即放入第12个小球时），轨道中的 11 个小球被依次放回队列，第 12 个小球也回到队列的末尾。

问题的一个常见考点是计算在给定的初始状态下，经过多少分钟后，小球队列的顺序会恢复到最初的状态。

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
#include "linear_stack.h"

#define N 27

int main()
{
    struct queue* main_queue = queue_create();
    struct stack* minute = stack_create(4);
    struct stack* five_minute = stack_create(11);
    struct stack* hour = stack_create(11);

    int time = 0;

    //初始化主队列中的27个小球
    for (int i = 1; i <= N; i++)
    {
        enqueue(main_queue, i);
    }

    while (!stack_full(hour))   //如果小时轨道未满，继续
    {
        while (!stack_full(five_minute))    //如果五分钟轨道未满，继续
        {
            while (!stack_full(minute))     //如果分钟轨道未满，继续
            {
                int ball = dequeue(main_queue);     //从主队列中获取小球
                stack_push(minute, ball);           // 放入分钟栈中
                time++;

                if (stack_full(minute))             //如果分钟栈满了
                {
                    int count_min = 0;
                    while (count_min < 4)    
                    {
                        int min_top_ball = stack_pop(minute);   //从分钟栈中弹出一个小球
                        enqueue(main_queue, min_top_ball);      //该小球送入主队列
                        count_min++;
                    }

                    stack_push(five_minute, ball);          //将一个小球推入五分钟栈
                }
            }
            if (stack_full(five_minute))    //如果五分钟栈满了
            {
                int count_five_min = 0;
                while (count_five_min < 11)  
                {
                    int five_min_top_ball = stack_pop(five_minute);     //从五分钟栈中弹出一个小球
                    enqueue(main_queue, five_min_top_ball);     //送回主队列
                    count_five_min++;
                }

                stack_push(hour, dequeue(main_queue));
            }
        }

        if (stack_full(hour))
        {
            int count_hour = 0;
            while (count_hour < 11)
            {
                int hour_top_ball = stack_pop(hour);
                enqueue(main_queue, hour_top_ball);
                count_hour++;
            }
        }
    }

    printf("钟表恢复到初始状态所需时间: %d 分钟\n", time);

    return 0;
}

数据结构

数据结构笔记【2】

http://akichen891.github.io/2024/10/11/数据结构笔记【2】/

作者

Aki Chen

发布于

2024年10月11日

更新于

2024年10月17日

许可协议

【矩阵论】矩阵分解上一篇

数据结构笔记【1】下一篇