栈与队列的三个例子
2010年10月05日 04:07 | Comments(31) | Category:C语言 | Tags:栈 队列 应用
1.小括号匹配
#define FORMATSTR "%c "
typedef char ElemType;
#define BufSize 128
#include "Stack.h"
int CheckBracket(char *str, int len)
{
int i = 0;
SQSTACK S;
char ch;
InitSqstack(&S, len);
while(str[i])
{
ch = str[i];
if(ch == '(')
PushS(&S, ch);
else if(ch == ')')
if(!PopS(&S, &ch))
{
DestroySqstack(&S);
return 0;
}
++i;
}
if(IsSqstackEmpty(S))
;
else
i = 0;
DestroySqstack(&S);
return i;
}
int main(void)
{
//栈示例 - 括号匹配
char string[BufSize];
gets(string);
if(CheckBracket(string, strlen(string)))
puts("Match!");
else
puts("Mismatch!");
return 0;
}
2.迷宫求解
#define FORMATSTR
typedef struct
{
int x, y, v; //坐标与方向
}ElemType;
#include "Stack.h"
int Map[10][10] =
{
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,0,1,
1,0,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,
};
int tox[5] = {0, 0,1,0,-1}; //偏正方向
int toy[5] = {0,-1,0,1, 0}; //偏正方向
int main(void)
{
//链式栈示例 - 迷宫求解，给定的迷宫，输出所有解。
LINKSTACK S;
ElemType e;
int x, y, v; //当前坐标
int ox, oy; //修正坐标
int i, j, k = 0;
e.x = 1; e.y = 1; //出发点
e.v = 0; //方向
InitLinkstack(&S);
PushL(S, e);
Map[1][1] = 8;
while(!IsLinkstackEmpty(S))
{
PopL(S, &e);
x = e.x; y = e.y; v = e.v + 1;
//back from here
if(e.v > 0)
Map[y+toy[e.v]][x+tox[e.v]] = 0;
while(v <= 4)
{
ox = x + tox[v];
oy = y + toy[v];
if(ox == 8 && oy == 9) //终点
{
printf("Answer %d:\n", ++k);
for(i = 0; i < 10; ++i)
{
for(j = 0; j < 10; ++j)
printf("%d ", Map[i][j]);
putchar(10);
}
++v;
}
else if(ox > 0 && oy > 0 && !Map[oy][ox])
{
e.x = x; e.y = y; e.v = v;
PushL(S, e);
x = ox, y = oy; v = 1;
Map[y][x] = 8;
}
else
++v;
}
}
DestroyLinkstack(&S);
return 0;
}
3.最短路径
#define FORMATSTR
typedef struct
{
int x, y, pre; //坐标与方向
}ElemType;
#include "Queue.h"
int Map[10][10] =
{
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,0,1,
1,0,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,
};
int tox[5] = {0, 0,1,0,-1}; //偏正方向
int toy[5] = {0,-1,0,1, 0}; //偏正方向
int main(void)
{
//队列示例 - 迷宫的最短路径
SQQUEUE Q;
ElemType e;
int x, y, v; //当前坐标
int ox, oy; //修正坐标
int i, j, k = 0, step = 2; //从02开始
e.x = 1; e.y = 1; //出发点
e.pre = 2; //前驱
InitSqqueue(&Q, 10*10);
EnSqqueue(&Q, e);
Map[1][1] = step;
while(!IsSqqueueEmpty(Q)) //BFS
{
DeSqqueue(&Q, &e);
x = e.x; y = e.y; v = e.pre += 1;
for(i = 1; i <= 4; ++i)
{
e.x = x + tox[i]; e.y = y + toy[i];
if(Map[e.y][e.x] == 0)
{
EnSqqueue(&Q, e);
Map[e.y][e.x] = e.pre;
if(e.x == 8 && e.y == 8) //终点
{
printf("The Shortest Path is:\n");
for(i = 0; i < 10; ++i)
{
for(j = 0; j < 10; ++j)
printf("%02d ", Map[i][j]);
putchar(10);
}
DestroySqqueue(&Q);
return 0; //找到就停
}
}
}
}
DestroySqqueue(&Q);
return 0;
}
栈的头文件
2010年10月05日 04:00 | Comments(2) | Category:C语言 | Tags:数据结构 栈 链式栈
/* 数据结构 栈的实现 Stack.h
* author : star
*/
//防止重复定义
#ifndef STACK_H
#define STACK_H
#include "defs.h"
//初始化大小为n的栈
int InitSqstack(SQSTACK *S, int n)
{
S->data = (ElemType *)malloc(n * sizeof(ElemType));
if(S->data == NULL)
return 0;
S->size = n;
S->top = -1;
return 1;
}
//销毁栈
void DestroySqstack(SQSTACK *S)
{
free(S->data);
S->data = NULL;
S->top = -1;
S->size = 0;
}
//判断栈空、栈满
int IsSqstackEmpty(SQSTACK S)
{
return S.top == -1;
}
int IsSqstackFull(SQSTACK S)
{
return S.top == S.size-1;
}
//入栈
int PushS(SQSTACK *S, ElemType e)
{
if(IsSqstackFull(*S))
return 0;
++S->top;
S->data[S->top] = e;
return 1;
}
//出栈
int PopS(SQSTACK *S, ElemType *e)
{
if(IsSqstackEmpty(*S))
return 0;
*e = S->data[S->top];
--S->top;
return 1;
}
//初始化链式栈
int InitLinkstack(LINKSTACK *S)
{
*S = (LINKSTACK)malloc(sizeof(LSNODE));
if(*S == NULL)
return 0;
(*S)->next = NULL;
return 1;
}
//销毁链式栈
int DestroyLinkstack(LINKSTACK *S)
{
LSNODEPTR q, p;
p = *S;
while(p)
{
q = p;
p = p->next;
free(q);
}
*S = NULL;
}
//判断链栈空、满
IsLinkstackEmpty(LINKSTACK S)
{
return S->next == NULL;
}
IsLinkstackFull(LINKSTACK S)
{
return S->next != NULL;
}
//入链栈
int PushL(LINKSTACK S, ElemType e)
{
LSNODEPTR p;
p = (LSNODEPTR)malloc(sizeof(LSNODE));
if(p == NULL)
return 0;
p->data = e;
p->next = S->next;
S->next = p;
return 1;
}
//出链栈
int PopL(LINKSTACK S, ElemType *e)
{
LSNODEPTR p;
p = S->next;
if(p == NULL)
return 0;
S->next = p->next;
*e = p->data;
free(p);
return 1;
}
#endif
数据结构头文件Ver2.0
2010年10月05日 03:57 | Comments(1) | Category:C语言 | Tags:数据结构 链表 栈 队列
/* 数据结构 全部结构定义文件 defs.h
* author : star
*/
//引入所有需要的头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//防止重复定义
#ifndef DEF_H
#define DEF_H
//定义执行状态返回结果
#define TRUE 1 //成功
#define FALSE 0 //失败
#ifndef FORMATSTR
#define FORMATSTR "%d " //输出格式
typedef int ElemType; //基本数据类型
#endif
//线性表
typedef struct
{
ElemType *data; //数据
int size; //容量
int len; //长度
}SQLIST;
//单链表
typedef struct link_node
{
ElemType data; //数据
struct link_node *next; //结点
}NODE, *NODEPTR, *LINKLIST;
//双向链表
typedef struct dlink_node
{
ElemType data; //数据
struct dlink_node *next, *prior; //前后结点
}DBNODE, *DBNODEPTR, *DBLINKLIST;
//循环单向链表 原理同单链表
//循环双向链表 原理同双向链表
//静态链表
#define SLEN 512 //静态链表长度
typedef struct slink_node
{
ElemType data; //数据
int next; //指针
}SNODE, *SLINKLIST;
/*静态链表是给没有指针的语言写的，C语言有指针，*
*而且静态链表不实用，定义多而杂，因此不写了 */
//广义表
enum{ATOM,LIST};
typedef struct glist_node
{
int tag; //ATOM或LIST
union
{
ElemType data; //ATOM
struct glist_node *head; //LIST
}item;
struct glist_node *next; //结点
}GLNODE, *GLIST;
//顺序栈
typedef struct
{
ElemType *data; //数据
int top; //栈顶
int size; //容量
}SQSTACK;
//链式栈
typedef struct stack_node
{
ElemType data; //数据
struct stack_node *next; //结点
}LSNODE, *LSNODEPTR, *LINKSTACK;
//顺序循环队列
typedef struct
{
ElemType *data; //数据
int front, rear; //队首与队尾
int size; //容量
}SQQUEUE;
//链式队列
typedef struct queue_node //结点
{
ElemType data;
struct queue_node *next;
}LQNODE, *LQNODEPTR;
typedef struct
{
LQNODEPTR front, rear; //队首与队尾
}LKQUEUE;
#endif