数据结构学习——4
一、栈
1.相关概念
栈定义：栈也是线性结构的一种，第一个进入栈的叫栈底（某些情况也是栈顶），特点是先进后出 LIFO
顺序栈：顺序表实现栈
链式栈：单链表实现栈
递增栈：栈底为低地址，栈顶为高地址（地址递增）
递减栈：栈底为高地址，栈顶为低地址（地址递减）
栈顶指针 top：指向栈顶的指针
空（top）递增/递减：top所指为栈顶元素的更顶上一个空的位置，入栈时先入再更改top。
满（top）递增/递减：top所指为栈顶元素，入栈时先更改top再将元素入栈。
顺序栈结构：
typedef int data_t;
typedef struct{
data_t data[20];
int top;
}stack_t;
2.代码实现
stack.h
/*===============================================
* 文件名称：stack.h
* 创 建 者：
* 创建日期：2025年07月30日
* 描 述：
================================================*/
#ifndef __STACK_H__
#define __STACK_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 20
typedef int data_t;
typedef struct
{
data_t data[LEN];
int top;
}stack_t;
//create
stack_t *stack_create();
//empty
int is_empty(stack_t *s);
//full
int is_full(stack_t *s);
//length
int get_length(stack_t *s);
//push
int stack_push(stack_t *s,data_t data);
//pop
data_t stack_pop(stack_t *s);
//show
void stack_show(stack_t *s);
//get_top
data_t get_top(stack_t *s);
//clear
void stack_clear(stack_t *s);
#endif
stack.c
/*===============================================
* 文件名称：stack.c
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：满递增栈
================================================*/
#include "stack.h"
//create
stack_t *stack_create()
{
stack_t *s = (stack_t *)malloc(sizeof(stack_t));
if(s == NULL)
return NULL;
s->top = -1;
return s;
}
//empty
int is_empty(stack_t *s)
{
if(s == NULL)
return 0;
return s->top == -1;
}
//full
int is_full(stack_t *s)
{
if(s == NULL)
return 0;
return s->top + 1 == LEN;
}
//length
int get_length(stack_t *s)
{
if(s == NULL)
return 0;
return s->top + 1;
}
//push
int stack_push(stack_t *s,data_t data)
{
if(s == NULL)
return 0;
if(is_full(s))
return 0;
s->top += 1;
s->data[s->top] = data;
}
//pop
data_t stack_pop(stack_t *s)
{
if(s == NULL)
return 0;
if(is_empty(s))
return 0;
s->top -= 1;
return s->data[s->top + 1];
}
//show
void stack_show(stack_t *s)
{
if(s == NULL)
return;
if(is_empty(s))
{
printf("栈为空!\n");
return;
}
for(int i = 0 ; i <= s->top ; i++)
printf("%4d ",s->data[i]);
printf("\n");
}
//get top
int get_top(stack_t *s)
{
if(s == NULL)
return -1;
if(is_empty(s))
return -1;
return s->top;
}
//clear
void stack_clear(stack_t *s)
{
if(s == NULL)
return;
s->top = -1;
}
main.c
int main(int argc, char *argv[])
{
stack_t *s = stack_create();
if(s == NULL)
return 0;
for(int i = 1 ; i <= 10 ; i++)
stack_push(s,i);
stack_show(s);
printf("出栈: %4d \n",stack_pop(s));
printf("出栈: %4d \n",stack_pop(s));
printf("出栈: %4d \n",stack_pop(s));
printf("出栈: %4d \n",stack_pop(s));
stack_show(s);
//栈顶元素获取
int top = get_top(s);
if(top >= 0)
printf("栈顶：%4d \n",s->data[top]);
stack_clear(s);
stack_show(s);
return 0;
}
二、链式栈（单链表）
使用单链表的形式，用head来表示top，所有Push都在top位置
stack.h
/*===============================================
* 文件名称：stack.h
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：栈 by 链表
================================================*/
#ifndef __STACK_H__
#define __STACK_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct Node
{
data_t data;
struct Node *next;
}stack_t;
//create
stack_t *stack_create();
//empty
int is_empty(stack_t *s);
//length
int stack_length(stack_t *s);
//push
int stack_push(stack_t *s,data_t data);
//pop
data_t stack_pop(stack_t *s);
//show
void stack_show(stack_t *s);
#endif
stack.c
/*===============================================
* 文件名称：stack.c
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：栈 by 链表
================================================*/
#include "stack.h"
//create
stack_t *stack_create()
{
stack_t *top = (stack_t *)malloc(sizeof(stack_t));
if(top == NULL)
return NULL;
top->next = NULL;
return top;
}
//empty
int is_empty(stack_t *top)
{
return top->next == NULL;
}
//length
int stack_length(stack_t *top)
{
int count = 0;
if(is_empty(top))
return count;
stack_t *p = top->next;
while(p != NULL)
{
count++;
p = p->next;
}
return count;
}
//push
int stack_push(stack_t *top,data_t data)
{
stack_t *new = (stack_t *)malloc(sizeof(stack_t));
if(new == NULL)
return 0;
new->data = data;
new->next = top->next;
top->next = new;
return 1;
}
//pop
data_t stack_pop(stack_t *top)
{
if(is_empty(top))
return -1;
stack_t *p = top->next;
top->next = p->next;
data_t data = p->data;
free(p);
return data;
}
//show
void stack_show(stack_t *top)
{
if(is_empty(top))
{
printf("栈为空!");
return;
}
stack_t *p = top->next;
while(p != NULL)
{
printf("%4d ",p->data);
p = p->next;
}
printf("\n");
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：栈 by 链表
================================================*/
#include "stack.h"
int main(int argc, char *argv[])
{
stack_t *top = stack_create();
if(top == NULL)
return 0;
for(int i = 1 ; i <= 10 ; i++)
stack_push(top,i);
stack_show(top);
printf("pop : %4d\n",stack_pop(top));
printf("pop : %4d\n",stack_pop(top));
printf("pop : %4d\n",stack_pop(top));
printf("pop : %4d\n",stack_pop(top));
stack_show(top);
return 0;
}
三、循环队列
1.相关概念
定义：也是线性表，先进队的先出去，后进的后出
顺序队列：顺序表构成的队列
链式队列：链表构成的队列
队头指针：指向队头元素
队尾指针：指向队尾元素
注意：循环队列一定要有一个空间作为缓冲区（不使用）
2.代码实现
queue.h
/*===============================================
* 文件名称：queue.h
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：循环队列 by 数组
================================================*/
#ifndef __QUEUE_H__
#define __QUEUE_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct
{
data_t *data;
int front,rear;
int len;
}queue_t;
//create
queue_t *queue_create(int size);
//empty
int is_empty(queue_t *q);
//full
int is_full(queue_t *q);
//length
int queue_length(queue_t *q);
//en
int queue_en(queue_t *q,data_t data);
//de
data_t queue_de(queue_t *q);
//show
void queue_show(queue_t *q);
#endif
queue.c
/*===============================================
* 文件名称：queue.c
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：循环队列 by 数组
================================================*/
#include "queue.h"
//create
queue_t *queue_create(int size)
{
queue_t *q = (queue_t *)malloc(sizeof(queue_t));
if(q == NULL)
return NULL;
q->data = (data_t *)malloc(sizeof(data_t) * size);
if(q->data == NULL)
return NULL;
q->front = q->rear = size - 1;
q->len = size;
return q;
}
//empty
int is_empty(queue_t *q)
{
return q->front == q->rear;
}
//full
int is_full(queue_t *q)
{
return (q->rear + 1) % q->len == q->front;
}
//length
int queue_length(queue_t *q)
{
return (q->rear - q->front + q->len) % q->len;
}
//en
int queue_en(queue_t *q,data_t data)
{
if(is_full(q))
return 0;
q->rear = (q->rear + 1) % q->len;
q->data[q->rear] = data;
return 1;
}
//de
data_t queue_de(queue_t *q)
{
if(is_empty(q))
{
return 0;
}
q->front = (q->front + 1) % q->len;
return q->data[q->front];
}
//show
void queue_show(queue_t *q)
{
if(is_empty(q))
{
printf("队已空！\n");
return;
}
int i;
for(i = (q->front+1)%q->len ;
i != (q->rear+1)%q->len ;
i = (i + 1) % q->len)
{
printf("%4d ",q->data[i]);
}
printf("\n");
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：青木莲华
* 创建日期：2025年07月30日
* 描 述：循环队列 by 数组
================================================*/
#include "queue.h"
int main(int argc, char *argv[])
{
int len = 10;
queue_t *q = queue_create(len);
int i = 1;
while(i < 15)
{
if(is_full(q))
break;
queue_en(q,i);
i++;
}
queue_show(q);
printf("out : %d\n",queue_de(q));
printf("out : %d\n",queue_de(q));
printf("out : %d\n",queue_de(q));
printf("out : %d\n",queue_de(q));
printf("out : %d\n",queue_de(q));
queue_show(q);
queue_en(q,11);
queue_en(q,22);
queue_en(q,33);
queue_show(q);
return 0;
}
运行截图
四、作业
用非循环 单链表实现排序操作
选择排序函数(单链表详细代码参考之前笔记)
/*===============================================
* 文件名称：link.c
* 创 建 者：青木莲华
* 创建日期：2025年07月28日
* 描 述：非循环单链表 选择排序
================================================*/
//排序 sort 用选择排序实现
void link_sort(link_t *head)
{
link_t *p = head; //每次比较确定的最小值节点所在位置，下一趟最小值前驱
link_t *q = head->next; //遍历用指针
link_t *mp = p; //最小节点前驱
link_t *min = head->next; //最小节点
int len = link_length(head); //链表节点个数，循环趟数为 len - 1次
for(int i = 1 ; i < len ; i++)
{
while(q->next != NULL) //min 与 q->next 比较 所以循环条件为q->next != NULL
{
if(min->data > q->next->data) //min节点大于q节点则 mp = q , min = q->next;
{
mp = q;
min = q->next;
}
q = q->next;
}
mp->next = min->next; //改变最小节点的前驱后继的指向，保证链表不断
//将min插入到p->next位置（更改本次循环最小节点位置）
min->next = p->next;
p->next = min;
p = p->next; //重置p位置到当前最小节点位置
mp = p; //重置最小节点前驱
min = p->next;
q = p->next;
}
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：青木莲华
* 创建日期：2025年07月28日
* 描 述：非循环单链表 选择排序
================================================*/
#include "link.h"
int main(int argc, char *argv[])
{
link_t *head = link_create();
if(head == NULL)
printf("create failed\n");
link_insert(head,7,0);
link_insert(head,13,0);
link_insert(head,55,0);
link_insert(head,11,0);
link_insert(head,8,0);
link_show(head);
//排序
link_sort(head);
link_show(head);
return 0;
}
运行截图
京公网安备 11010502036488号