BrainFuck解释器
2011年2月01日 08:57 | Comments(19) | Category:C语言 | Tags:c BrainFuck 解释器
无注释版本:
#include <stdio.h> #include <stdlib.h> #define SIZE 5000 char data[SIZE], code[SIZE]; int ptr, flag; void interpreter(char *ip) { char* re; while (*ip) { switch(*ip++) { case '<': --ptr; break; case '>': ++ptr; break; case '+': ++data[ptr]; break; case '-': --data[ptr]; break; case '.': putchar(data[ptr]); fflush(stdout); break; case ',': data[ptr] = getchar(); fflush(stdout); break; case '[': for (flag=1,re=ip; flag && *ip; ++ip) flag += *ip=='[', flag -= *ip==']'; if(!flag) { ip[-1] = 0; while (data[ptr]) interpreter(re); ip[-1] = ']'; break; } case ']': puts("Unbalancded brackets!"), exit(-3); default : ;//SKIP } if (ptr < 0 || ptr > 100) puts("Out of Range"), exit(-4); } } int main(int argc, char *argv[]) { FILE *fin; int codelength; if (argc != 2) return puts("BrainFuck Interpreter v 0.1\nStar\nUsage:BFI filename"), 0; if ((fin = fopen(argv[1], "r")) == NULL) return puts("Cannot open file!"), -1; fseek(fin, 0, SEEK_END); if ((codelength = ftell(fin)) > SIZE) return puts("The program is too large."), -2; fseek(fin, 0, SEEK_SET); fread(code, codelength, 1, fin); code[codelength] = '\0'; interpreter(code); return 0; }
栈与队列的三个例子
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:02 | Comments(1) | Category:C语言 | Tags:数据结构 循环队列 链式队列
/* 数据结构 队列的实现 Queue.h * author : star */ //防止重复定义 #ifndef QUEUE_H #define QUEUE_H #include "defs.h" //初始化大小为n的队列 int InitSqqueue(SQQUEUE *Q, int n) { Q->data = (ElemType *)malloc((n+1) * sizeof(ElemType)); if(Q->data == NULL) return 0; Q->front = Q->rear = 0; Q->size = n + 1; return 1; } //销毁队列 void DestroySqqueue(SQQUEUE *Q) { free(Q->data); Q->data = NULL; Q->front = Q->rear = Q->size = 0; } //判断队空还是满 int IsSqqueueEmpty(SQQUEUE Q) { return Q.front == Q.rear; } int IsSqqueueFull(SQQUEUE Q) { return Q.front == (Q.rear+1) % Q.size; } //入队 int EnSqqueue(SQQUEUE *Q, ElemType e) { if(IsSqqueueFull(*Q)) return 0; Q->data[Q->rear] = e; Q->rear = (Q->rear+1) % Q->size;\ return 1; } //出队 int DeSqqueue(SQQUEUE *Q, ElemType *e) { if(IsSqqueueFull(*Q)) return 0; *e = Q->data[Q->front]; Q->front = (Q->front+1) % Q->size; return 1; } //队列长度 int SqqueueLen(SQQUEUE Q) { return (Q.size + Q.rear + Q.front) % Q.size; } //初始化空链式队 void InitLkqueue(LKQUEUE *Q) { Q->front = Q->rear = NULL; } //销毁链式队列 void DestroyLkqueue(LKQUEUE *Q) { LQNODEPTR p; while(Q->front != NULL) { p = Q->front; Q->front = p->next; free(p); } Q->rear = NULL; } //入链队 int EnLkqueue(LKQUEUE *Q, ElemType e) { LQNODEPTR p; p = (LQNODEPTR)malloc(sizeof(LQNODE)); if(p == NULL) return 0; p->data = e; p->next = NULL; if(Q->front == NULL) Q->front = Q->rear = p; else Q->rear->next = Q->rear = p; return 1; } //出链队 int DeLkqueue(LKQUEUE *Q, ElemType *e) { LQNODEPTR p; if(Q->front == NULL) return 0; p = Q->front; Q->front = p->next; if(Q->front == NULL) Q->rear = NULL; *e = p->data; free(p); return 1; } #endif
栈的头文件
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