苏州建设建设信息网站,棋牌类网站开发,亚马逊海外网站,专门做ppt会员网站前言 数据结构的学习来到栈与队列。 数据结构就概念而言并不复杂#xff0c;重点在于准确地实现相应的功能。老样子#xff0c;代码为主。
概述 1.基础 2.栈的功能的代码实现 3.链栈功能的代码实现 4.队列的功能的代码实现 1.基础
1. 基本概念#xff1a;
栈与队列#…前言 数据结构的学习来到栈与队列。 数据结构就概念而言并不复杂重点在于准确地实现相应的功能。老样子代码为主。
概述 1.基础 2.栈的功能的代码实现 3.链栈功能的代码实现 4.队列的功能的代码实现 1.基础
1. 基本概念
栈与队列运算受限的线性表。 2. 数据结构分类表1 关系类型 数据结构 一对一 线性表如数组、链表 一对多 树形结构如二叉树 多对多 图形结构如图 3. 栈Stack
定义
typedef struct stack {int data[MAX]; // 存储数据的数组int top; // 栈顶指针} stack, *stack_p;
特性
栈顶为 top初始值为 -1。先进后出FILO仅允许在栈顶插入push和删除pop。 4. 队列Queue
定义
typedef struct Queue {int data[MAX]; // 存储数据的数组int front; // 队头指针int rear; // 队尾指针} queue, *queue_p;
特性
先进先出FIFO front指向队列头部第一个元素。rear指向队列尾部最后一个元素。 操作规则 入队enqueue从 rear 插入。出队dequeue从 front 删除。 5. 对比总结 结构 操作规则 核心指针 特点 栈 FILO后进先出 top 仅栈顶操作 队列 FIFO先进先出 front、rear 队头删队尾插 6. 补充说明
动态内存链表通过 malloc 动态申请内存栈/队列通常使用静态数组也可动态实现。应用场景 栈函数调用、表达式求值。队列任务调度、缓冲区管理。
手写笔记 2.栈的功能的代码实现
2.1 makefile
EXE01_stack
Objs$(patsubst %.c,%.o,$(wildcard *.c))
CCgcc
CFlags-c -oall:$(EXE)
$(EXE):$(Objs)$(CC) $^ -o $
%.o:%.c$(CC) $^ $(CFlags) $#伪目标
.PHONY:clean
clean:rm $(EXE) $(Objs)
2.2 stack.h
#ifndef _HEAD_H_
#define _HEAD_H_#include stdio.h
#include string.h
#include stdlib.h#define MAX 7typedef struct
{int data[MAX]; //存储栈中的数据int top; //记录栈顶元素的位置(初始值为-1)
}stack,*stack_p;//fun
stack_p create_stack();
int empty_stack(stack_p S);
int full_stack(stack_p S);
void push_stack(stack_p S,int value);
int pop_stack(stack_p S);
int pop_stack1(stack_p S,int value);
void show_stack(stack_p S);
void destory(stack_p* S);#endif
2.3 fun.c
#include stack.h
//1、创建顺序栈
stack_p create_stack(){stack_p H (stack_p)malloc(sizeof(stack));if(H NULL){printf(failed);return NULL;}memset(H,0,sizeof(stack));H-top -1;return H;
}
//2、判空
int empty_stack(stack_p S){if(SNULL)return -1;return S-top-1;
}
//3、判满
int full_stack(stack_p S){if(SNULL)return -1;return S-topMAX-1?1:0;
}
//4、入栈
void push_stack(stack_p S,int value){if(SNULL)return;S-data[S-top1] value;S-top;return;
}
//5、出栈
int pop_stack(stack_p S){if(SNULL)return 9999;return S-data[S-top--];
}
//5.1、出栈不推荐栈结构不允许
int pop_stack1(stack_p S,int value){if(SNULL)return 9999;int i 0;for(i 0; iS-top; i){if(S-data[i] value){break;}}for(int j i; jS-top; j){S-data[j] S-data[j1];}S-top--;return value;
}
//6、输出栈中元素
void show_stack(stack_p S){if(SNULL)return;for(int i S-top; i0; --i){printf(%d ,S-data[i]);}printf(\n);
}
//7、销毁栈
void destory(stack_p *S){if(SNULL||*SNULL){printf(error);return;}free(*S);*SNULL;
}
2.4 main.c
#include stack.h
int main(int argc, const char *argv[])
{stack_p S create_stack();push_stack(S,1);push_stack(S,2);push_stack(S,3);push_stack(S,4);push_stack(S,5);show_stack(S);printf(出栈 %d\n,pop_stack(S));printf(出栈后);show_stack(S);printf(弹出3 %d\n,pop_stack1(S,3));printf(弹出后);show_stack(S);return 0;
} 2.5 run
ubuntuubuntu:~/data_structre/class4/stack$ ./01_stack
5 4 3 2 1
出栈 5
出栈后4 3 2 1
弹出3 3
弹出后4 2 1
ubuntuubuntu:~/data_structre/class4/stack$
3.链栈功能的代码实现
3.1 makefile
EXE01_linked_stack
Objs$(patsubst %.c,%.o,$(wildcard *.c))
CCgcc
CFlags-c -oall:$(EXE)
$(EXE):$(Objs)$(CC) $^ -o $
%.o:%.c$(CC) $^ $(CFlags) $#伪目标
.PHONY:clean
clean:rm $(EXE) $(Objs)
3.2 stack.h
#ifndef _HEAD_H_
#define _HEAD_H_#include stdio.h
#include string.h
#include stdlib.h#define MAX 7typedef struct node
{int data;struct node *next;
}node,*node_p;//fun
node_p create_node(int value);
int empty_stack(node_p S);
void push_stack(node_p* S,int value);
int pop_stack(node_p* S);int count_stack(node_p S);
void output(node_p S);#endif
3.3 fun.c
#include linked_stack.h
//1、新建
node_p create_node(int value){node_p S (node_p)malloc(sizeof(node));if(S NULL)return NULL;S-data value;S-next NULL;return S;
}
//2、判空
int empty_stack(node_p S){return S NULL;
}
//3、入栈
void push_stack(node_p* S,int value){if(S NULL)return;node_p new create_node(value);new-next *S;*S new;
}
//4、出栈
int pop_stack(node_p* S){if(*S NULL)return -1;if(empty_stack(*S))return -2;int data_pop (*S)-data;node_p p_delete *S;*S (*S)-next;free(p_delete);return data_pop;
}
//count
int count_stack(node_p S){node_p p S;int count 0;while(p ! NULL){p p-next;count;}return count;
}
//output
void output(node_p S){if(S NULL)return;node_p p S;//int count count_stack(S);while(p ! NULL){printf(%d ,p-data);p p-next;}printf(\n);return;
}
3.4 main.c
#include linked_stack.h
int main(int argc, const char *argv[])
{node_p S NULL;push_stack(S,1);push_stack(S,2);push_stack(S,3);push_stack(S,4);push_stack(S,5);output(S);printf(计数 %d\n,count_stack(S));printf(出栈 %d\n,pop_stack(S));printf(出栈后);output(S);return 0;
} 3.5 run
ubuntuubuntu:~/data_structre/class4/linked_stack$ ./01_linked_stack
5 4 3 2 1
计数 5
出栈 5
出栈后4 3 2 1
ubuntuubuntu:~/data_structre/class4/linked_stack$
4.队列的功能的代码实现
4.1 makefile
EXE01_queue
Objs$(patsubst %.c,%.o,$(wildcard *.c))
CCgcc
CFlags-c -oall:$(EXE)
$(EXE):$(Objs)$(CC) $^ -o $
%.o:%.c$(CC) $^ $(CFlags) $#伪目标
.PHONY:clean
clean:rm $(EXE) $(Objs)
4.2 queue.h
#ifndef _HEAD_H_
#define _HEAD_H_#include stdio.h
#include string.h
#include stdlib.h#define MAX 7typedef struct queue
{int data[MAX];int front;int rear;
}queue, *queue_p;//fun
void output(queue_p Q);
queue_p create_que();
int empty_que(queue_p Q);
int full_que(queue_p Q);
void push_que(queue_p Q,int value);
int pop_que(queue_p Q);
void destroy(queue_p *Q);
int count_que(queue_p Q);#endif
4.3 fun.c
#include queue.h
//
void output(queue_p Q){for(int iQ-front; iQ-rear-1; i){printf(%d ,Q-data[i]);}printf(\n);
}
//1、创建循环队列
queue_p create_que()
{queue_p S (queue_p)malloc(sizeof(queue));if(SNULL)return NULL;memset(S,0,sizeof(queue));return S;
}
//2、判空
int empty_que(queue_p Q){if(QNULL)return -1;return Q-front Q-rear;
}
//3、判满
int full_que(queue_p Q){return (Q-rear1)%MAX Q-front;
}
//4、入队
void push_que(queue_p Q,int value){if(QNULL)return;if(full_que(Q))return;Q-data[Q-rear] value;Q-rear (Q-rear1)%MAX;
}
//5、出队
int pop_que(queue_p Q){if(QNULL)return -1;if(empty_que(Q))return -2;int out_queue Q-data[Q-front];Q-front (Q-front1)%MAX;return out_queue;
}
//6、销毁队列
void destroy(queue_p *Q){if(QNULL || *QNULL)return;free(*Q);printf(released\n);return;
}
//7、返回队列中元素的个数
int count_que(queue_p Q){if(Q NULL)return -1;return (Q-rear - Q-front MAX)%MAX;
}4.4 main.c
#include queue.h
int main(int argc, const char *argv[])
{queue_p Q create_que();push_que(Q, 1);push_que(Q, 2);push_que(Q, 3);push_que(Q, 4);push_que(Q, 5);output(Q);printf(计数 %d\n,count_que(Q));printf(出队 %d\n,pop_que(Q));printf(出队后);output(Q);destroy(Q);return 0;
}
4.5 run
ubuntuubuntu:~/data_structre/class4/queue$ ./01_queue
1 2 3 4 5
计数 5
出队 1
出队后2 3 4 5
released
ubuntuubuntu:~/data_structre/class4/queue$
结语 一对一的结构线性结构的学习到此告一段落下一篇是对线性结构的总结。
