文章目录
栈队列
栈
定义:
一种可以实现“先进后出”的存储结构。 分类:
静态栈动态栈 算法:
出栈压栈
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
int data
;
struct Node
* pNext
;
}NODE
, * PNODE
;
typedef struct Stack
{
PNODE pTop
;
PNODE pBottom
;
}STACK
, * PSTACK
;
void init(PSTACK
);
void push(PSTACK
,int);
void traverse(PSTACK
);
bool
pop(PSTACK
,int *);
int main(void){
STACK S
;
int val
;
init(&S
);
push(&S
,1);
push(&S
,2);
traverse(&S
);
pop(&S
,&val
);
clear(&S
);
return 0;
}
void init(PSTACK pS
){
pS
->pTop
= (PNODE
)malloc(sizeof(NODE
));
if(NULL == pS
->pTop
){
printf("动态内存分配失败!\n");
ext(-1);
}else{
pS
->pBottom
= pS
->pTop
;
pS
->pTop
->pNext
= NULL;
}
}
void push(PSTACK pS
,int val
){
PNODE pNew
= (PNODE
)malloc(sizeof(NODE
));
pNew
->data
= val
;
pNew
->pNext
= pS
->pTop
;
pS
->pTop
= pNew
;
return;
}
void traverse(PSTACK pS
){
PNODE p
= pS
->pTop
;
while(p
!= pS
->pBottom
){
printf("%d",p
->data
);
p
= p
-pNext
;
}
printf("\n");
return;
}
bool
empty(PSTACK pS
){
if(pS
->pTop
== pS
->pBottom
){
return true
;
}else{
reurn false
;
}
}
bool
pop(PSTACK pS
,int * pVal
){
if(empt(pS
)){
return false
;
}else{
PNODE r
= pS
->pTop
;
*pVal
= r
->data
;
pS
->pTop
= r
->pNext
;
free(r
);
r
= NULL;
return true
;
}
}
void clear(PSTACK pS
){
if(empty(pS
)){
return;
}else{
PNODE p
= pS
->pTop
;
PNODE q
= NULL;
while(p
!= pS
->pBottom
){
q
= p
->pNext
;
free(p
);
p
= q
;
}
pS
->pTop
= pS
->pBottom
;
}
}
应用
函数调用中断表达式求值(计算器算法)内存分配缓冲处理迷宫
队列
定义:
一种可以实现“先进先出”的存储结构。 分类:
链式队列 ——用链表实现静态队列——用数组实现
静态队列通常都必须是循环队列。 应用:
所有和时间有关的操作都有队列的影子。 循环队列
静态队列为什么必须是循环队列
循环队列需要几个参数确定
两个参数(front、rear)
循环队列各个参数的含义
- 各个参数在不同场合有不同的含义
- 队列初始化:
- front和rear的值都是0。
- 队列非空:
- front代表队列的第一个元素,rear代表队列最后一个有效元素的下一个元素。
- 队列空
- front和rear的值相等,但不一定是0。
循环队列入队伪算法
循环队列出队伪算法(取余的操作着实很秀,我想不到) 妙啊
如何判断循环队列是否为空
front和rear的值相等。
如何判断循环队列是否已满(更妙了)
队列算法:
#include <stdio.h>
#include <malloc.h>
typedef struct Queue
{
int * pBase
;
int front
;
int rear
;
}QUEUE
;
void init(QUEUE
*);
bool
en_queue(QUEUE
*,int);
void traverse_queue(QUEUE
*);
bool
full_queue(QUEUE
*);
bool
out_queue(QUEUE
*,int *);
bool
emput_queue(QUEUE
*);
int main(void){
QUEUE Q
;
init(&Q
);
en_queue(&Q
,1);
traverse_queue(&Q
);
return 0;
}
void init(QUEUE
*pQ
){
pQ
->pBase
= (int *)malloc(sizeof(int) * 6);
pQ
->front
= 0;
pQ
->rear
= 0;
}
bool
full_queue(QUEUE
*pQ
){
if((pQ
->rear
+1)%6 == pQ
->front
)
return true
;
else
return false
;
}
bool
en_queue(QUEUE
*pQ
,int val
){
if(full_queue(pQ
)){
printf("入队失败!\n");
return false
;
}else{
pQ
->pBase
[pQ
->rear
] = val
;
pQ
->rear
= (pQ
->rear
+1)%6;
return true
;
}
}
void traverse_queue(QUEUE
* pQ
){
int i
= pQ
->front
;
while(i
!= pQ
->rear
){
printf("%d",pQ
->pBase
[i
]);
i
= (i
+1)%6;
}
printf("\n");
return;
}
bool
emput_queue(QUEUE
* pQ
){
if(pQ
->front
== pQ
->rear
)
return true
;
else
return false
;
}
bool
out_queue(QUEUE
* pQ
,int * pVal
){
if(emput_queue(pQ
)){
return false
;
}else{
*pVal
= pQ
->pBase
[pQ
->front
];
pQ
->front
= (pQ
->front
+1)%6;
return true
;
}
}