欢迎光临
我们一直在努力

数据结构(4):循环链表、栈与队列

一、循环链表(环形链表)

循环链表是一种特殊的单链表,尾节点的指针域不指向 NULL,而是指向头节点,形成一个环。

1. 节点结构体

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

2. 创建空循环链表

创建头节点后,头节点的指针域指向自己,形成一个"自环"。

node_t * clinklist_create(void)
{
//创建头节点
node_t *head = malloc(sizeof(node_t));
if (head == NULL)
{
printf("malloc fail\\n");
return NULL;
}
//头节点的指针域指向自己
head->next = head;

return head;

}

3. 插入数据——头插

循环链表的头插需要分三种情况考虑:

  • 空循环链表
  • 只有一个数据节点
  • 多个节点

思路:

  • 1.创建新节点,填充数据
  • 2.链接:
    • p_new->next = phead->next;(新节点指向原来的首节点)
    • 找到头节点的上一个节点(p->next == phead),让其指向新节点
    • p->next = p_new;
  • 特殊情况: 单个节点时,数据节点要指向自己。

    int is_empty(node_t *phead)
    {
    if (phead==NULL)
    {
    return -1;
    }

    return phead->next == phead;

    }
    int clinklist_insert_head(node_t* phead,data_t data)
    {
    if (phead==NULL)
    {
    return -1;
    }
    //创建节点
    node_t *p_new = malloc(sizeof(node_t));
    if (p_new == NULL)
    {
    printf("malloc fail\\n");
    return -1;
    }
    p_new->data = data;
    //空循环链表
    if (is_empty(phead) == 1)
    {
    phead->next = p_new;
    p_new->next = p_new;
    }else
    {
    node_t *tail = phead->next;
    //找到尾节点(头节点上一个节点)
    while (tail->next != phead->next)
    tail=tail->next;
    //链接
    p_new->next = phead->next;
    tail->next = p_new;
    phead->next = p_new;
    }
    return 0;
    }

    多节点时的操作: 遍历找到头节点的前一个节点(p->next == phead),让 p->next = p_new 即可。

    3.5 遍历打印

    循环链表的遍历终止条件与普通链表不同:当指针回到头节点时停止(p != phead),而不是 p != NULL。

    int clinklist_print(node_t *phead)
    {
    if (phead==NULL || is_empty(phead) == 1)
    {
    return -1;
    }

    node_t *p = phead->next;

    while (p->next != phead->next)
    {
    printf("%d ",p->data);
    p = p->next;
    }
    printf("%d \\n",p->data);

    return 0;
    }

    与普通链表的区别: 普通链表遍历条件是 p != NULL,循环链表因为尾节点指向头节点,永远不会有 NULL,所以必须用 p != phead 作为终止条件,否则会死循环。

    4. 查找

    node_t * clinklist_find_key(node_t *phead,data_t key)
    {
    if (phead==NULL || is_empty(phead) == 1)
    {
    return NULL;
    }

    node_t *p = phead->next;

    while (p->next != phead->next)
    {
    if (p->data == key)
    {
    return p;
    }
    p = p->next;
    }

    if (p->data == key)
    {
    return p;
    }

    return NULL;

    5. 删除(头删)

    思路:

    • p:移动的指针,找到要删除节点的前一个节点
    • p_temp:要删除的节点

    int clinklist_delete_head(node_t *phead)
    {
    if (phead==NULL || is_empty(phead) == 1)
    {
    return -1;
    }

    node_t *p_temp = phead->next;
    node_t *tail = phead->next;
    while (tail->next != phead->next)
    tail = tail->next;
    phead->next = p_temp->next;
    tail->next = p_temp->next;
    free(p_temp);

    return 0;
    }

    6. 销毁

    销毁逻辑:

  • 1.p = phead->next->next;(从第二个数据节点开始)
  • 2.循环过程中逐个删除,直到 p == phead->next(只剩一个数据节点)
  • 3.free(p);(释放最后一个数据节点)
  • 4.free(phead); *phead = NULL;(释放头节点,置空指针)
  • int clinklist_destroy(node_t **phead)
    {
    if (*phead==NULL || is_empty(*phead) == 1)
    {
    return -1;
    }
    node_t *p = (*phead)->next;

    while (p->next != (*phead)->next)
    {
    node_t *p_temp = p;
    p = p->next;
    free(p_temp);
    }
    free(p);
    free(*phead);
    *phead = NULL;
    return 0;
    }

    循环链表操作小结

    序号操作说明
    1 创建 头节点指针域指向自己
    2 插入 头插法,注意空链表和单节点的特殊处理
    3 查找 遍历条件为 p != phead
    4 删除 找前驱节点,注意释放内存
    5 销毁 逐个释放所有节点,头节点最后释放
    6 判空 phead->next == phead

    二、栈

    1. 栈的基本概念

    栈是一种线性的数据结构,属于受限的线性表——只能在一端进行数据操作。

    • 栈顶:操作数据的一端(入栈、出栈都在此进行)
    • 栈底:不能进行数据操作的一端
    • 操作顺序:FILO(First In Last Out,先进后出)

    类比:筒装羽毛球,先放进去的在最下面,最后才能拿出来。

    栈的基本操作:

    序号操作说明
    1 创建栈 初始化栈结构
    2 入栈(push) 将数据放入栈顶
    3 出栈(pop) 从栈顶取出数据
    4 获取栈顶元素 返回栈顶元素但不出栈
    5 获取栈的容量 栈能存放的最大元素个数
    6 获取栈的大小 栈中有效数据的个数
    7 销毁 释放栈的内存

    2. 顺序栈(数组实现)

    结构体定义

    typedef int data_t;
    typedef struct seqstack
    {
    data_t *stack; //需要空间 堆上开辟
    int top;
    int max;
    }seqstack_t;

    关键约定
    • 栈空:top == -1
    • 栈满:top == max – 1
    创建栈

    seqstack_t * seqstack_create(int n) //n表示栈容量
    {
    //栈结构创建出来
    seqstack_t *ps = malloc(sizeof(seqstack_t));
    if (ps == NULL)
    {
    return NULL;
    }
    //创建栈的空间
    ps->stack = malloc(sizeof(data_t) * n);
    //栈顶指针 初始化
    //容量初始化一下
    ps->top = -1;
    ps->max = n;

    return ps;
    }

    判空与判满

    int is_empty(seqstack_t *ps)
    {
    if (ps == NULL)
    {
    return -1;
    }

    return ps->top == -1;
    }

    int is_full(seqstack_t *ps)
    {
    if (ps == NULL)
    {
    return -1;
    }

    return ps->top == ps->max-1;
    }

    入栈(push)

    int push(seqstack_t *ps, data_t data)
    {
    if (ps == NULL)
    {
    return -1;
    }

    if (is_full(ps) == 1)
    {
    printf("full stack!\\n");
    return -1;
    }
    ps->top ++;
    ps->stack[ps->top] = data;

    return 0;
    }

    出栈(pop)

    int pop(seqstack_t *ps,data_t *data)
    {
    if (ps == NULL || is_empty(ps) == 1)
    {
    return -1;
    }
    //栈空 is_empty
    // *data = 栈顶数据
    // top–

    *data = ps->stack[ps->top];
    ps->top–;

    return 0;
    }

    获取栈顶元素

    data_t get_top_element(seqstack_t *ps)
    {
    /// 直接返回此时栈指针所指向的元素
    if (ps == NULL)
    {
    return -1;
    }
    if (is_empty(ps) == 1)
    {
    return -1;
    }

    return ps->stack[ps->top];
    }

    获取栈的大小

    int get_stack_size(seqstack_t *ps )
    {
    // 就是top+1
    if (ps == NULL)
    {
    return -1;
    }

    if (is_empty(ps) == 1)
    {
    return 0;
    }

    return ps->top + 1;
    }

    销毁栈

    int seqstack_destroy(seqstack_t **pps)
    {
    if(pps == NULL)
    {
    return -1;
    }
    free((*pps)->stack);
    free(*pps);
    *pps = NULL;
    return 0;
    }


    3. 链式栈(链表实现)

    链式栈本质上还是单向链表的操作,属于受限的线性表。

    • 入栈 push → 对应链表的头插
    • 出栈 pop → 对应链表的头删
    • 栈顶 → 链表的首节点(头节点的下一个)
    • 栈底 → 不动

    链式栈不需要考虑容量限制。

    节点结构体

    typedef struct stack
    {
    data_t data;
    struct stack *next;
    } node_t;

    创建栈(创建空链表)

    node_t *linkstack_create(void)
    {
    node_t *pstack = malloc(sizeof(node_t));
    if (pstack == NULL)
    return NULL;
    pstack->next = NULL;
    return pstack;
    }

    入栈 push(头插)

    int push(node_t *pstack, data_t data)
    {
    node_t *p_new = malloc(sizeof(node_t));
    if (p_new == NULL)
    return -1;

    p_new->data = data;
    p_new->next = pstack->next;
    pstack->next = p_new;
    return 0;
    }

    出栈 pop(头删)

    int pop(node_t *pstack, data_t *data)
    {
    if (pstack == NULL || pstack->next == NULL)
    return -1;

    node_t *p_temp = pstack->next;
    *data = p_temp->data;
    pstack->next = p_temp->next;
    free(p_temp);
    return 0;
    }

    获取栈顶元素

    data_t get_top_element(node_t *pstack)
    {
    // 获取首节点的数据,先判断是否为空栈
    if (pstack == NULL || pstack->next == NULL)
    return (data_t)-1;
    return pstack->next->data;
    }

    获取栈的大小

    int get_stack_size(node_t *pstack)
    {
    int count = 0;
    node_t *p = pstack->next;
    while (p != NULL)
    {
    count++;
    p = p->next;
    }
    return count;
    }

    销毁(逐个销毁链表节点)

    int linkstack_destroy(node_t **ppstack)
    {
    if (ppstack == NULL || *ppstack == NULL)
    return -1;

    // 链表节点挨个销毁
    node_t *p = *ppstack;
    while (p != NULL)
    {
    node_t *temp = p;
    p = p->next;
    free(temp);
    }

    // 悬空指针
    *ppstack = NULL;
    return 0;
    }


    三、队列

    1. 队列的基本概念

    队列是一种受限的线性表,类似于排队。

    • 队头:负责出数据
    • 队尾:负责入数据
    • 操作顺序:FIFO(First In First Out,先进先出)

    队列可以用顺序表(数组) 或 链表 实现。


    2. 顺序队列——循环队列

    用数组实现队列时,为了避免"假溢出"问题,采用循环队列的方式,通过取模运算让下标循环。

    队列结构体

    typedef int data_t;
    typedef struct queue
    {
    data_t *que; // 队列的空间
    int head; // 队头——负责出数据
    int tail; // 队尾——负责入数据
    int tlen; // 容量
    } queue_t;

    关键状态判断
    • 队空:head == tail == 0
    • 队满:(tail + 1) % N == head(牺牲一个存储空间来区分队空和队满)

    取模运算 %N 保证下标在 [0, N-1] 范围内循环。

    创建队列

    queue_t *queue_create(int len)
    {
    queue_t *pq = malloc(sizeof(queue_t));
    if (pq == NULL)
    {
    return NULL;
    }

    pq->que = malloc(sizeof(data_t)*len);
    if (pq->que == NULL)
    {
    free(pq);
    return NULL;
    }

    pq->head = pq->tail = 0;
    pq->len = len;

    return pq;
    }

    判空与判满

    int is_empty(queue_t *pq)
    {
    if (pq == NULL)
    {
    return -1;
    }

    return pq->tail == pq->head;
    }

    int is_full(queue_t *pq)
    {
    if (pq == NULL)
    {
    return -1;
    }

    return ((pq->tail+1) % pq->len) == 0;
    }

    入队 enqueue

    int enqueue(queue_t *pq,data_t data)
    {
    if (pq == NULL)
    {
    return -1;
    }
    if (is_full(pq) == 1)
    {
    return -1;
    }

    pq->que[pq->tail] = data;
    pq->tail++;

    return 0;
    }

    出队 dequeue

    int dequeue(queue_t *pq, data_t *data)
    {
    //判断是否空? — is_empty()
    //队头负责出数据
    //先出值
    //后 移动head
    if (pq == NULL)
    {
    return -1;
    }
    if (is_empty(pq) == 1)
    {
    return -1;
    }
    *data = pq->que[pq->head];
    pq->head++;
    return 0;
    }

    销毁队列

    int queue_destroy(queue_t **ppq)
    {
    if(ppq == NULL ||*ppq==NULL )
    {
    return -1;
    }
    free((*ppq)->que);

    free(*ppq);
    *ppq=NULL;
    return 0;

    }


    3. 链式队列(链表实现)

    用链表实现队列,操作对应到链表的基本操作:

    队列操作对应链表操作说明
    创建队列 创建空链表 初始化
    入队 尾插 队尾入数据
    出队 头删 队头出数据
    销毁队列 销毁链表 释放所有节点

    四、总结回顾

    核心要点

    1. 循环链表

    • 尾节点指针指向头节点,形成环形结构
    • 遍历终止条件为 p != phead(而不是 p != NULL)
    • 头插时注意空链表和单节点的特殊处理

    2. 栈

    • 受限的线性表,只能在栈顶操作
    • FILO(先进后出)
    • 顺序栈用数组实现,注意 top == -1 表示空栈,top == max-1 表示满栈
    • 链式栈本质上是单向链表,入栈即头插,出栈即头删

    3. 队列

    • 受限的线性表,队头出数据,队尾入数据
    • FIFO(先进先出)
    • 循环队列通过取模 %N 实现下标循环,牺牲一个空间区分队空和队满
    • 链式队列入队对应尾插,出队对应头删
    赞(0)
    未经允许不得转载:171主机测评 » 数据结构(4):循环链表、栈与队列
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址