文档章节

数据结构(1)-堆栈,队列的实现

centrald
 centrald
发布于 2015/03/02 21:02
字数 1749
阅读 30
收藏 0
点赞 0
评论 0

栈:

顺序结构实现堆栈:          

(1)sa.h

#ifndef _SA_H
#define _SA_H //防止重复include
//各种声明都定义在头文件里
//各种实现都定义在.c文件里(变量赋值/函数代码)
#include<sys/types.h>
typedef struct Stack{
        int* addr; //数组的首地址,需要分配内存
        size_t cap;//容量,size_t是非负整数类型
        size_t top;//当前下标,也是栈顶
} STACK;
void stack_init(STACK* stack,size_t cap);//栈的初始化
void stack_deinit(STACK* stack);//销毁堆栈
int stack_full(STACK* stack);//判断栈是否满
int stack_empty(STACK* stack);//判断堆栈是否空
void stack_push(STACK* stack,int data);//入栈
int stack_pop(STACK* stack);//出栈
int stack_top(STACK* stack);//看栈而不出栈
size_t stack_size(STACK* stack);//栈的元素数量
#endif

(2)sa.c

#include<stdlib.h>
#include "sa.h"
void stack_init(STACK* stack,size_t cap){//栈的初始化
        stack->arr = malloc(cap*4);//分配内存空间,结构指针的成员用->
        stack->cap = cap; //容量
        stack->top = 0; //栈定 为0
}
void stack_deinit(STACK* stack){//销毁堆栈
        free(stack->arr);//释放内存
        stack->arr = NULL;//地址不能是无效地址
        stack->cap = 0;//消除隐患
        stack->top = 0;
}
int stack_full(STACK* stack){//判断栈是否满
        return stack->top>=stack->cap;//或者==
}
int stack_empty(STACK* stack){;//判断堆栈是否空
        return !stack->top; //==0,取反的效率高
}
void stack_push(STACK* stack,int data){//入栈
        stack->arr[stack->top]=data;
        stack->top++;
}
int stack_pop(STACK* stack){//出栈
        stack->top--;
        return stack->arr[stack->top];
}
int stack_top(STACK* stack){//看栈而不出栈
        return stack->arr[stack->top - 1];
}
size_t stack_size(STACK* stack){//栈的元素数量
        return stack->top;
}

栈的基本数据结构实现完毕,下来进行测试

(3)test.c

#include<stdio.h>
#include "sa.h"

int main()
{
        STACK stack;
        stack_init(&stack,10);
        int i=0;
        while (!stack_full(&stack)){
                stack_push(&stack,i++);
        }
        while(!stack_empty(&stack)){
                printf("%d\n",stack_pop(&stack));
        }
return 0;
}

编译执行;

#gcc test.c sa.c 

# ./a.out
9
8
7
6
5
4
3
2
1
0
基于链式表的堆栈

(1)sl.h

#ifndef _SL_H
#define _SL_H
#include<sys/types.h>

typedef struct StackNode{
        int data; //数据
        struct StackNode* next;//下一个节点的地址
} STACK_NODE;
typedef struct Stack{
        STACK_NODE* top;//栈顶节点
} STACK;
void stack_init(STACK* stack);//初始化为NULL堆栈
void stack_deinit(STACK* stack);//释放所有节点并置空
int stack_empty(STACK* stack);//判断是否为空
void stack_push(STACK* stack,int data);//入栈
int stack_pop(STACK* stack);//出栈
int stack_top(STACK* stack);//查看栈顶而不出栈
size_t stack_size(STACK* stack);//栈中的元素
#endif

(2)sl.c

#include<stdlib.h>
#include "sl.h"
static STACK_NODE* create_node(int data,STACK_NODE* next){
//新建节点并返回,static表示只有在本文件使用,外部不能使用
        STACK_NODE* node = malloc(sizeof(STACK_NODE));
        node->data=data;
        node->next=next;
        return node;
}
static STACK_NODE* destroy_node(STACK_NODE* node){
//删除一个节点并返回下一个节点地址
        STACK_NODE* next=node->next;
        free(node);
        return next;
}
void stack_init(STACK* stack){//初始化为NULL堆栈
        stack->top=NULL;
}
void stack_deinit(STACK* stack){//释放所有节点并置空
        while(stack->top)
                stack->top=destroy_node(stack->top);
}
int stack_empty(STACK* stack){//判断是否为空
        return !stack->top;
}
void stack_push(STACK* stack,int data){//入栈
        //先执行函数,再执行赋值
        stack->top = create_node(data,stack->top);
}
int stack_pop(STACK* stack){//出栈
        int data = stack->top->data;//栈顶节点的data
        stack->top = destroy_node(stack->top);
        return data;
}
int stack_top(STACK* stack){//查看栈顶而不出栈
        return stack->top->data;
}
size_t stack_size(STACK* stack){//栈中的元素数量
        size_t size=0;
        STACK_NODE* node = NULL;//top不能变
        for(node=stack->top;node;node=node->next)
                ++size;
        return size;
}

(3)测试代码

test.c

#include<stdio.h>
#include "sl.h"

int main()
{
        STACK stack;
        stack_init(&stack);
        int i=0;
        while (i<10){
                stack_push(&stack,i++);
        }
        while(!stack_empty(&stack)){
                printf("%d\n",stack_pop(&stack));
        }
return 0;
}

# cc testsl.c sl.c

# ./a.out

9
8
7
6
5
4
3
2
1
0
demo:

使用链式堆栈实现,10进制数转化为任意进制数

#include<stdio.h>
#include "sl.h"

int main(){

        int number,base;
        printf("请输入整数和进制数\n");
        scanf("%d%d",&number,&base);
        STACK stack;
        stack_init(&stack);
        do{
                stack_push(&stack,number%base);
        }while(number=number/base);
        printf("转换的结果:\n");
        while(!stack_empty(&stack))
        {
                int digit = stack_pop(&stack);
                if(digit<10) printf("%d",digit);
                else printf("%c",digit-10+'A');
        }
        printf("\n");
        stack_deinit(&stack);
return 0;
}

# cc example.c sl.c
# ./a.out
请输入整数和进制数
23 2
转换的结果:
10111

队列:

顺序结构实现队列

(1)qa.h

#ifndef _QA_H
#define _QA_H
#include<sys/types.h>
typedef struct Queue{
        int* arr; //数组的首地址
        size_t cap; //数组的长度
        size_t front; //队首下标
        size_t rear; //队尾下标
        size_t size; //元素数量
} QUEUE;
void queue_init(QUEUE* queue,size_t cap); //初始化队列
void queue_deinit(QUEUE* queue);  //回收队列资源
int queue_full(QUEUE* queue); //判断队列的满
int queue_empty(QUEUE* queue);//判断队列的空
void queue_push(QUEUE* queue,int data); //入队
int queue_pop(QUEUE* queue); //出队函数
int queue_front(QUEUE* queue); //查看队首函数
size_t queue_size(QUEUE* queue); //查看队列大小
#endif

(2)qa.c

#include<stdlib.h>
#include "qa.h"

void queue_init(QUEUE* queue,size_t cap){ //初始化队列
        queue->arr = malloc(cap * sizeof(int));
        queue->cap = cap;
        queue->front = 0;
        queue->rear = 0;
        queue->size = 0;
}
void queue_deinit(QUEUE* queue){  //回收队列资源
        free(queue->arr);
        queue->arr = NULL; //保证指针的有效性
        queue->cap = 0;
        queue->front = 0;
        queue->rear = 0;
        queue->size = 0;

}
int queue_full(QUEUE* queue){ //判断队列的满
        return queue->size >= queue->cap;
}
int queue_empty(QUEUE* queue){//判断队列的空
        return !queue->size;
}
void queue_push(QUEUE* queue,int data){ //入队
        if(queue->rear>=queue->cap)//下标越界
                queue->rear = 0;
        queue->arr[queue->rear] = data;//数据放队尾
        queue->rear++;//队尾后移
        queue->size++;//元素数量增加
}
int queue_pop(QUEUE* queue){ //出队函数
        if(queue->front >= queue->cap)
                queue->front = 0;
        queue->size--; //元素数量减少
        return queue->arr[queue->front++];
        //int temp = queue->arr[queue->front];
        //queue->front++;
        //return temp;

}
int queue_front(QUEUE* queue){ //查看队首函数
        if(queue->front >= queue->cap)
                queue->front=0;
        return queue->arr[queue->front];

}
size_t queue_size(QUEUE* queue){ //查看队列大小
        return queue->size;
}

进行测试

(3)testqa.c

#include<stdio.h>
#include "qa.h"

int main(){
        QUEUE queue;//创建队列
        queue_init(&queue,5);
        int i;
        for(i=0;i<5;i++){
                if(!queue_full(&queue))//如果队列不满可以加
                queue_push(&queue,i);
        }
        printf("size:=%d\n",queue_size(&queue));
        while(!queue_empty(&queue)){
                printf("%d\n",queue_pop(&queue));
        }
        queue_deinit(&queue);
return 0;
}

# cc testqa.c qa.c

# ./a.out

size:=5
0
1
2
3
4
链式结构实现队列:

(1)ql.h

#ifndef _QL_H
#define _QL_H
#include<sys/types.h>
typedef struct QueueNode{//链式表节点
        int data; //数据
        struct QueueNode* next;//下一个元素的地址
} QUEUE_NODE;
typedef struct Queue{
                QUEUE_NODE* front;//队首节点地址,负责出队
                QUEUE_NODE* rear;//队尾节点,负责入队
} QUEUE;
void queue_init(QUEUE* queue);//初始化为NULL
void queue_deinit(QUEUE* queue);//释放节点后删除
int queue_empty(QUEUE* queue);//判断是否为空
void queue_push(QUEUE* queue,int data);//入队
int queue_pop(QUEUE* queue);//出队
int queue_front(QUEUE* queue);//查看队首
size_t queue_size(QUEUE* queue);//取元素数量
#endif

(2)ql.c

#include<stdlib.h>
#include "ql.h"
static QUEUE_NODE* create_node(int data){//创建节点
        QUEUE_NODE* node= malloc(sizeof(QUEUE_NODE));
        node->data = data;
        node->next = NULL;
        return node;
}
static QUEUE_NODE* destroy_node(QUEUE_NODE* node){//删除节点
        QUEUE_NODE* next= node->next;
        free(node);
        return next;
}
void queue_init(QUEUE* queue){//初始化为NULL
        queue->front = NULL;
        queue->rear = NULL;
}
void queue_deinit(QUEUE* queue){//释放节点后删除
        while(queue->front)
                queue->front = destroy_node(queue->front);
        queue->rear = NULL;
}
int queue_empty(QUEUE* queue){//判断是否为空
        return !queue->front && !queue->rear;
}
void queue_push(QUEUE* queue,int data){//入队
        QUEUE_NODE* node = create_node(data);
        if(queue->rear)//不是第一个
                queue->rear->next = node;
        else //是第一个
                queue->front = node;
        queue->rear = node;
}
int queue_pop(QUEUE* queue){//出队
        int data = queue->front->data;
        queue->front = destroy_node(queue->front);
        if(!queue->front) queue->rear = NULL;//如果最后出队为空,rear也为空
        return data;
}
int queue_front(QUEUE* queue){//查看队首
        return queue->front->data;
}
size_t queue_size(QUEUE* queue){//取元素数量
        size_t size= 0;
        QUEUE_NODE* node;
        for(node = queue->front;node;node=node->next)
                size++;
        return size;

}

(3)测试代码

testql.c

#include<stdio.h>
#include "ql.h"

int main(){
        QUEUE queue;//创建队列
        queue_init(&queue);
        int i;
        for(i=0;i<5;i++){
                queue_push(&queue,i);
        }
        printf("size:=%d\n",queue_size(&queue));
        while(!queue_empty(&queue)){
                printf("%d\n",queue_pop(&queue));
        }
        queue_deinit(&queue);
return 0;
}

# gcc testql.c ql.c

# ./a.out

size:=5
0
1
2
3
4


© 著作权归作者所有

共有 人打赏支持
centrald
粉丝 11
博文 70
码字总数 117691
作品 0
杭州
程序员
zephyr笔记 2.5.3 栈

1 前言 堆栈是实现传统的后进先出 (LIFO) 队列的内核对象,允许线程和ISR添加和移除有限数量的32位数据值。 我正在学习 Zephyr,一个很可能会用到很多物联网设备上的操作系统,如果你也感兴趣...

iotisan ⋅ 05/03 ⋅ 0

《编程之美》-取队列中的最大值(读书分享)

题目:设计一种数据结构和算法,让取队列最大值的操作的事件复杂度降到最低。对队列操作后依然能够简便取出最大值。 对于栈来讲,Push和Pop均是在栈顶完成的,所以很容维护最大值,而且他的时...

吟啸_徐行 ⋅ 2013/03/15 ⋅ 4

堆和栈(Java数据结构)

堆 常见使用场景: (英语:heap)亦被称为: 优先队列 (英语:priority queue),是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反...

晓阳 ⋅ 2015/10/14 ⋅ 0

洪柏利/PHP_SPL

SPL SPL的常用数据结构以及常用迭代器等,主要是参考慕课网的《站在巨人的肩膀上写代码-SPL》教程 1-1 概述 1. 什么是SPL SPL是Standard PHP Library的缩写 官方定义:The Standard PHP Libr...

洪柏利 ⋅ 01/11 ⋅ 0

JAVA基础(16)--ArrayList集合存储自定义对象、ArrayList取出重复元素、LinkedList、LinkedList实现队列结构

ArrayList集合存储自定义对象 ArrayList取出重复元素方式1 ArrayList取出重复元素方式2 ArrayList取出重复的自定义元素 从下面代码中我们可以看出:contains方法中把equals方法分装了 Linked...

Chason-洪 ⋅ 04/28 ⋅ 0

Java 复习 —— 集合

1、类的基本结构 Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set |-HashSet |-TreeSet Map ├Hashtable ├HashMap └WeakHashMap 2、基本概念 0)Collection ......

learn_more ⋅ 2015/08/05 ⋅ 0

Java LinkedList

基本概念 LinkedList可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行列表操作。 LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。 实际上...

有苦向瓜诉说 ⋅ 2017/11/22 ⋅ 0

python基础知识3(列表和元组)

# 列表(可变数据类型) ## 列表的定义 列表是打了激素的数组,数组只能存储同种类型的数据,而列表像一个仓库,存储不同类型的数据. l = [] l = [1] l = [1,(1,2),"hello",[1,2]] ## 列表的特性...

lulu2017 ⋅ 2017/09/01 ⋅ 0

PHP实现二叉树的深度优先遍历(前序、中序、后序)和广度优先遍历(层次)

http://blog.csdn.net/baidu_30000217/article/details/52953127 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深...

szxy1234 ⋅ 2017/08/24 ⋅ 0

Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论](http://en.wik...

宅男潇涧 ⋅ 2014/07/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

对于程序员的招聘问题,作为软件人的一些吐槽和建议

作为软件人,找工作有时候似乎挺苦逼的。 说真的,让我去掉前面这句中“似乎”二字吧。就是苦逼!很多人都曾抱怨处在招聘的一方很糟糕——我们没有任何可靠的方式来甄别会写代码并且写得好的...

老道士 ⋅ 34分钟前 ⋅ 0

HDFS原理学习

一、概述 1、 Hadoop整合了众多的文件系统,首先提供了一个高层的文件系统抽象org.apache.hadoop.fs.FileSystem。然后有各个文件系统的实现类。 2、Hadoop是JAVA编写的,不同文件系统之间的交...

cjxcloud ⋅ 38分钟前 ⋅ 0

Linux下MySQL表名不区分大小写的设置方法(抄袭别人的)

Linux下MySQL表名不区分大小写的设置方法 MySQL表名不区分大小写的设置方法 在用centox安装mysql后,把项目的数据库移植了过去,发现一些表的数据查不到,排查了一下问题,最后发现是表名的大...

随风而浮沉 ⋅ 43分钟前 ⋅ 0

ubuntu下安装宋体simsun

sudo cp simsun.ttc /usr/share/fonts cd /usr/share/fonts sudo chmod 644 simsun.ttc 更新字体缓存: 代码: sudo mkfontscale 代码: sudo mkfontdir 代码: sudo fc-cache -fsv 安装chrome扩......

wangxuwei ⋅ 44分钟前 ⋅ 0

利用 ssh 传输文件

Linux 下一般可以用 scp 命令通过 ssh 传送文件: #把服务器上的 /home/user/a.txt 发送到本机的 /var/www/local_dir 目录下scp username@servername:/home/user/a.txt /var/www/local_dir...

大灰狼时间 ⋅ 55分钟前 ⋅ 0

web3j教程:android和java程序员如何使用web3j开发区块链以太坊

如何使用web3j为Java应用或Android App增加以太坊区块链支持,本教程内容即涉及以太坊中的核心概念,例如账户管理包括账户的创建、钱包创建、交易转账,交易与状态、智能合约开发与交互、过滤...

智能合约 ⋅ 今天 ⋅ 0

web3j开发java或android以太坊智能合约快速入门

web3j简介 web3j是一个轻量级、高度模块化、响应式、类型安全的Java和Android类库提供丰富API,用于处理以太坊智能合约及与以太坊网络上的客户端(节点)进行集成。 可以通过它进行以太坊区块链...

笔阁 ⋅ 今天 ⋅ 0

一起读书《深入浅出nodejs》-异步I/O

异步I/O “异步”这个名词其实很早就诞生了,但它大规模流行却是在Web 2.0浪潮中,它伴随着AJAX的第一个A(Asynchronous)席卷了Web。 为什么要异步I/O 关于异步I/O为何在Node里如此重要,这与...

小草先森 ⋅ 今天 ⋅ 0

JVM各种问题

1、如果启动什么都不设,会怎样? 先来看一个命令 [root@localhost bin]# java -XX:+PrintCommandLineFlags -version -XX:InitialHeapSize=29899008 -XX:MaxHeapSize=478384128 -XX:+PrintCo......

算法之名 ⋅ 今天 ⋅ 0

SAS笔记-宏2

宏是一种文本,一般来说其编译是在程序执行之前。 宏变量的创建 %let语句 %let macro_variables = text; %let是常见的宏变量建立方式,其编译就在执行前。如下例中,想要宏变量test等于数据集...

tonorth123 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部