数据结构(1)-堆栈,队列的实现
博客专区 > centrald 的博客 > 博客详情
数据结构(1)-堆栈,队列的实现
centrald 发表于3年前
数据结构(1)-堆栈,队列的实现
  • 发表于 3年前
  • 阅读 29
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

栈:

顺序结构实现堆栈:          

(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


标签: 数据结构 队列 C
共有 人打赏支持
粉丝 9
博文 66
码字总数 110060
×
centrald
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: