1.填图游戏：
在一个m*n的方框中，输入任意的坐标点，则包含这个坐标点的图框被自动填充“颜色”。代码：
#include
#include
#define M 20
#define N 20
static int graph[M][N]={
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{1,1,1,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,0,1},
{1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1},
{1,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,0,0,1},
{1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1},
{1,1,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,0,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
void showgraph(int graph[][N])
{
int i,j;
for(i=0;i {
for(j=0;j {
if(graph[i][j]==1 || graph[i][j] == 2)
printf("*");
else
printf(" ");
}
printf("\n");
}
}
int NotFilling(int m, int n)
{
if(graph[m][n] == 0)
return 0;
else
return -1;
}
int PointOnEdge(int m, int n)
{
if(graph[m][n] == 1)
return 0;
else
return -1;
}
void pre_draw(int m,int n)
{
if((n-1 > 0) && (PointOnEdge(m,n-1)==-1) && (NotFilling(m,n-1) == 0))
{
// printf("m=%d,n-1=%d\n",m,n-1);
graph[m][n-1]=2;
pre_draw(m,n-1);
}
if((m+1)<19 && (PointOnEdge(m+1,n) == -1) && (NotFilling(m+1,n) == 0))
{
// printf("m+1=%d,n=%d\n",m+1,n);
graph[m+1][n] =2;
pre_draw(m+1,n);
}
if((n+1)< 19 && (PointOnEdge(m,n+1) == -1) && (NotFilling(m,n+1) == 0))
{
// printf("m=%d,n+1=%d\n",m,n+1);
graph[m][n+1] =2;
pre_draw(m,n+1);
}
if((m-1) > 0 && (PointOnEdge(m-1,n) == -1) && (NotFilling(m-1,n) == 0))
{
// printf("m-1=%d,n=%d\n",m-1,n);
graph[m-1][n] =2;
pre_draw(m-1,n);
}
}
void main(void)
{
showgraph(graph);
int m,n;
do{
printf("\nPlease input m=[0~19],n=[0~19]:");
scanf("%d %d", &m, &n);
if(PointOnEdge(m,n) == 0)
printf("The point is on the edge, please try again!\n");
else
break;
}while(1);
graph[m][n]=1;
pre_draw(m,n);
showgraph(graph);
}
2.球钟算法：
有四个容器，其中一个容器最初放有27个球，剩下的三个分别可以放入4，11，11个球，分别代表1min, 5min 和 1 hour,问多长时间以后管里的球依旧是1～27的顺序。
::::::::::::::
queue.h
::::::::::::::
#include
#define QUEUE_TYPE int
void create_queue(size_t size);
void destroy_queue(void );
void insert(QUEUE_TYPE value);
void delete(void);
QUEUE_TYPE first(void);
int is_empty(void);
int is_full(void);
void show_queue(void);
void show_myqueue(void);
void record_queue(int [], int);
::::::::::::::
g_stack.h
::::::::::::::
#include
#define GENERIC_STACK( STACK_TYPE, SUFFIX, STACK_SIZE) \
static STACK_TYPE stack##SUFFIX[STACK_SIZE];\
static int top_element##SUFFIX = -1;\
\
int \
is_empty##SUFFIX(void) \
{ \
return top_element##SUFFIX == -1; \
} \
\
int \
is_full##SUFFIX(void) \
{ \
return top_element##SUFFIX == STACK_SIZE -1; \
} \
\
void \
push##SUFFIX(STACK_TYPE value) \
{ \
assert(!is_full##SUFFIX()); \
top_element##SUFFIX += 1; \
stack##SUFFIX[top_element##SUFFIX] = value; \
} \
\
void \
pop##SUFFIX(void) \
{ \
assert(!is_empty##SUFFIX()); \
top_element##SUFFIX -= 1; \
} \
\
STACK_TYPE top##SUFFIX(void) \
{ \
assert(!is_empty##SUFFIX()); \
return stack##SUFFIX[top_element##SUFFIX]; \
}
::::::::::::::
main.c
::::::::::::::
#include "g_stack.h"
#include "queue.h"
#include
GENERIC_STACK(int,_int_a,4)
GENERIC_STACK(int,_int_b,11)
GENERIC_STACK(int,_int_c,11)
#define QUEUE_SIZE 27
void one_cycle(void)
{
int queue_pop;
int queue_push;
int i;
queue_pop = first();
delete();
if(!is_full_int_a())
{
push_int_a(queue_pop);
}
else
{
for(i=0;i<4;i++)
{
insert(top_int_a());
pop_int_a();
}
if(!is_full_int_b())
push_int_b(queue_pop);
else
{
for(i=0;i<11;i++)
{
insert(top_int_b());
pop_int_b();
}
if(!is_full_int_c())
push_int_c(queue_pop);
else
{
for(i=0;i<11;i++)
{
insert(top_int_c());
pop_int_c();
}
insert(queue_pop);
}
}
}
}
void list_array(int queue[])
{
int i = 0;
while(queue[i]!=-1 && i < QUEUE_SIZE)
{
printf("%d ",queue[i]);
i++;
}
printf("\n");
}
int compare_queue(int a[], int b[])
{
int i;
for(i=0;i {
if(a[i] != b[i])
return 0;
}
return 1;
}
void time_counting(int *min, int *hour, int *day)
{
if( *min != 59) // min
{
*min += 1;
}
else //hour
{
*min = 0;
if( *hour != 23 )
*hour += 1;
else //day
{
*hour = 0;
*day += 1;
}
}
}
main(void)
{
int count = 0;
int start_queue[QUEUE_SIZE];
int queue[QUEUE_SIZE];
int i;
int min = 0 ;
int hour = 0;
int day = 0;
create_queue(QUEUE_SIZE);
for(i=0;i insert(i+1);
record_queue(start_queue, QUEUE_SIZE);
record_queue(queue, QUEUE_SIZE);
list_array(queue);
printf("Compare result : %d\n",compare_queue(start_queue,queue));
while(1)
{
i = 0;
one_cycle();
record_queue(queue, QUEUE_SIZE);
count++;
time_counting(&min, &hour, &day);
/*
if(count > 33110)
{
printf("Count = %d\n",count);
list_array(queue);
}
*/
if(compare_queue(start_queue,queue)==1)
break;
//printf("Compare result : %d\n",compare_queue(start_queue,queue));
//getchar();
}
printf("Count = %d mintinues\n",count);
printf("%d days:%d hours:%d mins\n", day, hour, min);
}
::::::::::::::
queue.c
::::::::::::::
#include "queue.h"
#include
struct node_st{
int id;
int value;
struct node_st *next;
};
static struct node_st *root = NULL;
void show_myqueue(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
printf("%d ",current->value);
current = current->next;
if(current->id == start)
break;
}
printf("\n");
}
void record_queue(int queue[],int queue_size)
{
int i=0;
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
queue[i] = current->value;
i++;
current = current->next;
if(current->id == start)
break;
}
if(i queue[i]=-1;
}
void show_queue(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
printf("queue id:%d value:%d\n",current->id,current->value);
current = current->next;
if(current->id == start)
break;
}
}
void create_queue(size_t size)
{
int i;
struct node_st *current= NULL;
struct node_st *new;
for(i=0;i {
new = malloc(sizeof(struct node_st));
new->id = i;
new->value = -1;
new->next = NULL;
if(root == NULL)
current = root = new;
else
{
current->next = new;
current = current->next;
new = NULL;
}
}
if(current->next == NULL)
current->next = root;
}
void insert(QUEUE_TYPE value)
{
struct node_st *current = root;
int ret=0;
while(current->value != -1)
{
if((ret=is_full()) == 1)
break;
current = current->next;
}
if(ret == 0)
current->value = value;
}
/* check if the queue is empty:
if return 0, it shows that the queue is not empty;
if return 1, it shows that the queue is empty
*/
int is_empty(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value == -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}
/* check if the queue is full:
if return 0, it shows that the queue is not full;
else if return 1, it shows that the queue is full
*/
int is_full(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}
void delete(void)
{
if(!is_empty())
{
root->value = -1;
root= root->next;
}
}
QUEUE_TYPE first(void)
{
return root->value;
}
void destroy_queue(void)
{
int start, end;
struct node_st *current = root;
struct node_st *previous = root;
start = current->id;
do{
end =current->id;
current = current->next;
}while(current->id != start);
while(current->id != end)
{
previous = current;
current = current->next;
free(previous);
previous = NULL;
}
free(current);
current = NULL;
}
3.Dijkstra算法：
::::::::::::::
dijkstra.c
::::::::::::::
#include
#include
#define SIZE 7
typedef struct NODE_ST{
int dv;
int pv;
int known;
}node_data;
void sort_route(int temp[],node_data V[])
{
int i=0;
int j,k;
int tmp;
while(temp[i] != -1)
{
// printf("temp[%d]=%d\n",i,temp[i]);
i++;
}
for(j=0;j {
for(k=0;k {
if(V[temp[j]].dv < V[temp[k]].dv)
{
tmp = temp[j];
temp[j]=temp[k];
temp[k] = tmp;
}
}
}
}
void display_route(node_data V[], int n)
{
int i;
printf("v Known dv pv\n");
for(i=1;i<=n;i++)
printf("V%d: %d %d V%d\n", i, V[i].known, V[i].dv, V[i].pv);
}
void clear_route(int route[])
{
route[0]=-1;
}
void update_route(int node[][SIZE], node_data V[], int volume, int route[])
{
int i,j;
i = 0;
while(route[i] != -1)
i++;
// printf("\tstart updating on V%d:\n",volume);
V[volume].known = 1;
for(j=1;j<8;j++)
{
if(node[volume-1][j-1]>0)
{
if(V[j].known == 1)
continue;
if((V[j].dv != 0) && (V[j].dv < (V[volume].dv + node[volume-1][j-1])))
continue;
// update the shorter route
V[j].pv = volume;
V[j].dv = V[volume].dv + node[volume-1][j-1];
route[i]=j;
// printf("\tUpdate V%d in route \n",j);
i++;
}
}
route[i]=-1;
// display_route(V, 7);
}
int check_known(node_data V[], int size)
{
int i;
for(i=1;i<=size;i++)
{
if(V[i].known == 0)
return 0;
}
return 1;
}
void dijkcheck(int node[][SIZE],node_data V[], int volume)
{
int i;
int route[SIZE];
int new_route[SIZE];
route[0]=-1;
new_route[0]=-1;
// printf("Enter V%d node:\n",volume);
update_route(node, V, volume, route);
while(check_known(V, SIZE) == 0)
{
//getchar();
sort_route(route,V);
for(i=0;route[i] != -1;i++)
update_route(node, V, route[i], new_route);
for(i=0;new_route[i] != -1;i++)
route[i]=new_route[i];
route[i]=-1;
new_route[0]=-1;
}
}
::::::::::::::
main.c
::::::::::::::
#include "dijkstra.c"
int main(void)
{
int i,j;
int start = 3;
int node[SIZE][SIZE]={ // V1 V2 V3 V4 V5 V6 V7
/*V1*/ { 0, 2, -1, 1,-1, -1, -1},
/*V2*/ {-1, 0, -1, 3,10, -1, -1},
/*V3*/ { 4,-1, 0,-1,-1, 5, -1},
/*V4*/ {-1,-1, 2, 0, 2, 8, 4},
/*V5*/ {-1,-1, -1,-1, 0, -1, 6},
/*V6*/ {-1,-1, -1,-1,-1, 0, -1},
/*V7*/ {-1,-1, -1,-1,-1, 1, 0}};
node_data V[8];
for(i=1;i<8;i++)
{
V[i].dv=0;
V[i].pv=999;
V[i].known=0;
}
dijkcheck(node, V, start);
printf("Final route starting from V%d:\n",start);
display_route(V,7);
}
4.拓扑排序：
::::::::::::::
topologic.h
::::::::::::::
#ifndef _TOPOLOG_HS_
#define _TOPOLOG_HS_
int check_nohead(linkqueue *L[], int volume, int n);
#endif
::::::::::::::
topologic.c
::::::::::::::
#include "linkqueue.h"
#include "topologic.h"
#include
#include
static int count = 1;
int check_nohead(linkqueue *L[], int volume, int n)
{
int i;
lkqnode *current = NULL;
for(i=0;i {
current = L[i]->rear->next;
if(linkqueue_is_empty(L[i]))
continue;
while(current != NULL)
{
if(current->data == volume)
return -1;
current = current->next;
}
}
return 0;
}
void sort(linkqueue *L[], int arr[], int n)
{
int i;
int loop = 1;
for(i=0;i {
if(L[i]->id != -1)
continue;
if(check_nohead(L,i,n)==0)
{
empty_linkqueue(L[i]);
L[i]->id = count;
arr[count-1] = i;
count++;
loop = 0;
break;
}
}
if(count <= n && loop == 0 )
sort(L,arr,n);
}
::::::::::::::
linkqueue.c
::::::::::::::
#include
#include
#include "linkqueue.h"
linkqueue * linkqueue_create()
{
linkqueue *L;
lkqnode *new;
L=malloc(sizeof(*L));
if(L == NULL)
return NULL;
L->id = -1;
L->front = L->rear = malloc(sizeof(struct linkqueue));;
L->rear->next = NULL;
return L;
}
int linkqueue_enqueue(linkqueue *L,datatype x)
{
lkqnode *new;
lkqnode *current ;
new = malloc(sizeof(*new));
if(new == NULL)
return -1;
new->data = x;
new->next = NULL;
L->front = new;
if(L->rear->next == NULL)
{
L->rear->next = new;
return 0;
}
current = L->rear->next;
while(current->next != NULL)
current = current->next;
current->next = new;
// printf("%d \n",L->rear->data);
}
int linkqueue_dequeue(linkqueue *L,datatype *x)
{
if(L->front == NULL)
return -1;
lkqnode *p = L->rear;
lkqnode *q = p->next;
*x = q->data;
p->next = q->next;
free(q);
return 0;
}
int linkqueue_is_empty(linkqueue *L)
{
return L->rear->next == NULL;
}
void linkqueue_display(linkqueue *L)
{
// printf("display\n");
lkqnode *current = L->rear->next;
while(current != NULL)
{
printf("%d ",current->data);
current = current->next;
}
}
void empty_linkqueue(linkqueue *L)
{
if(linkqueue_is_empty(L))
return;
lkqnode *q = L->rear->next;
lkqnode *p;
while(q != NULL)
{
p = q;
q = q->next;
free(p);
}
L->rear->next = NULL;
}
::::::::::::::
linkqueue.h
::::::::::::::
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
typedef int datatype;
typedef struct linkqueue
{
datatype data;
struct linkqueue *next;
}lkqnode;
typedef struct
{
int id;
lkqnode *front;
lkqnode *rear;
}linkqueue;
linkqueue * linkqueue_create();
int linkqueue_enqueue(linkqueue *,datatype);
int linkqueue_dequeue(linkqueue *,datatype *);
int linkqueue_is_empty(linkqueue *);
void linkqueue_display(linkqueue *);
void empty_linkqueue(linkqueue *);
#endif
::::::::::::::
main.c
::::::::::::::
#include "linkqueue.h"
#include "topologic.h"
#include
#define C1 0
#define C2 1
#define C3 2
#define C4 3
#define C5 4
#define C6 5
#define C7 6
#define C8 7
#define C9 8
#define C10 9
#define C11 10
#define C12 11
#define C13 12
main(void)
{
int i;
int arr[12]={0};
linkqueue *L[12];
L[C1]=linkqueue_create();
linkqueue_enqueue(L[C1],C2);
linkqueue_enqueue(L[C1],C3);
linkqueue_enqueue(L[C1],C4);
linkqueue_enqueue(L[C1],C12);
L[C2]=linkqueue_create();
linkqueue_enqueue(L[C2],C3);
L[C3]=linkqueue_create();
linkqueue_enqueue(L[C3],C5);
linkqueue_enqueue(L[C3],C7);
linkqueue_enqueue(L[C3],C8);
L[C4]=linkqueue_create();
linkqueue_enqueue(L[C4],C5);
L[C5]=linkqueue_create();
linkqueue_enqueue(L[C5],C7);
L[C6]=linkqueue_create();
linkqueue_enqueue(L[C6],C8);
L[C7]=linkqueue_create();
L[C8]=linkqueue_create();
L[C9]=linkqueue_create();
linkqueue_enqueue(L[C9],C10);
linkqueue_enqueue(L[C9],C11);
linkqueue_enqueue(L[C9],C12);
L[C10]=linkqueue_create();
linkqueue_enqueue(L[C10],C12);
L[C11]=linkqueue_create();
linkqueue_enqueue(L[C11],C6);
L[C12]=linkqueue_create();
sort(L,arr,12);
for(i=0;i<12;i++)
printf("C%d ", arr[i]+1 );
printf("\n");
}
5.计算器
方法一：建立两个栈（符号栈和数字栈），通过压栈和出栈进行计算。
主程序：
::::::::::::::
main.c
::::::::::::::
#include
#include
#include "g_stack.h"
GENERIC_STACK(int,_int,30)
GENERIC_STACK(char,_char,30)
#define MAXSIZE 100
void getstring(char *str)
{
int i;
fgets(str, MAXSIZE, stdin);
}
int converse(char *str)
{
int i;
int count=0;
int num=0;
int mul=1;
while(str[count]!='\0')
count++;
for(i=count-1;i>=0;i--)
{
num += mul*(str[i]-'0');
mul *= 10;
}
return num;
}
int compare_op(char a,char b)
{
int flag_a;
int flag_b;
if(a == '+' || a == '-')
flag_a = 1;
else if(a == '*' || a == '/')
flag_a = 2;
else if(a == '^')
flag_a =3;
else if(a == '#' || a =='(')
flag_a = 0;
if(b == '+' || b == '-')
flag_b = 1;
else if(b == '*' || b == '/')
flag_b = 2;
else if(b == '^')
flag_b =3;
else if(b == '#' || b =='(')
flag_b = 0;
return flag_a - flag_b;
}
int power(int a, int n)
{
int i;
int value = 1;
for(i=0;i value *= a;
return value;
}
int result(int a, int b, char op)
{
switch(op){
case '+':
return a+b;
break;
case '-':
return a-b;
break;
case '*':
return a*b;
break;
case '/':
return a/b;
break;
case '^':
return power(a,b);
break;
default:
break;
}
}
int native_oper(void)
{
int a,b,c;
char current_op;
while(top_char() != '#' && top_char() != '(')
{
current_op = top_char();
pop_char();
b = top_int();
pop_int();
a = top_int();
pop_int();
c = result(a,b,current_op);
push_int(c);
}
if(top_char() == '(')
pop_char();
return 0;
}
/*
void parentheses_oper(void)
{
int a,b,c;
char current_op;
while(top_char() != '(')
{
current_op = top_char();
pop_char();
b = top_int();
pop_int();
a = top_int();
pop_int();
c = result(a,b,current_op);
push_int(c);
}
}
*/
int operation(char *str)
{
int i;
char buffer[MAXSIZE];
int b_count;
int num=0;
char top_op;
char current_op;
int a;
int b;
int c;
push_char('#');
for(i=0; str[i] != '\n'; i++)
{
if(str[i]=='(')
{
push_char(str[i]);
continue;
}
if(isdigit(str[i]))
{
b_count=0;
while(isdigit(str[i]))
{
buffer[b_count]=str[i];
b_count++;
i++;
}
buffer[b_count] = '\0';
num = converse(buffer);
push_int(num);
// printf("%d ",num);
i--;
continue;
}
if(str[i]==')')
{
if(native_oper()==0)
continue;
else
return -1;
}
top_op = top_char();
current_op = str[i];
if(compare_op(current_op,top_op) > 0)
{
push_char(current_op);
}
else if((compare_op(current_op, top_op) < 0)||(compare_op(current_op, top_op) == 0))
{
i--;
pop_char();
b = top_int();
pop_int();
a = top_int();
pop_int();
c = result(a,b,top_op);
push_int(c);
}
// printf("%c ",top_char());
}
if(native_oper()==0)
return top_int();
else
return -1;
}
int main(void)
{
char str[MAXSIZE];
int i;
int result;
getstring(str);
result = operation(str);
if(result != -1)
printf("Th final result is %d\n",result);
// printf("%d\n",converse("1234"));
}
队列头文件和函数：
::::::::::::::
queue.c
::::::::::::::
#include "queue.h"
#include
struct node_st{
int id;
int value;
struct node_st *next;
};
static struct node_st *root = NULL;
void show_queue(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
printf("queue id:%d value:%d\n",current->id,current->value);
current = current->next;
if(current->id == start)
break;
}
}
void create_queue(size_t size)
{
int i;
struct node_st *current= NULL;
struct node_st *new;
for(i=0;i {
new = malloc(sizeof(struct node_st));
new->id = i;
new->value = -1;
new->next = NULL;
if(root == NULL)
current = root = new;
else
{
current->next = new;
current = current->next;
new = NULL;
}
}
if(current->next == NULL)
current->next = root;
}
void insert(QUEUE_TYPE value)
{
struct node_st *current = root;
int ret=0;
while(current->value != -1)
{
if((ret=is_full()) == 1)
break;
current = current->next;
}
if(ret == 0)
current->value = value;
}
/* check if the queue is empty:
if return 0, it shows that the queue is not empty;
if return 1, it shows that the queue is empty
*/
int is_empty(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value == -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}
/* check if the queue is full:
if return 0, it shows that the queue is not full;
else if return 1, it shows that the queue is full
*/
int is_full(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}
void delete(void)
{
if(!is_empty())
{
root->value = -1;
root= root->next;
}
}
QUEUE_TYPE first(void)
{
return root->value;
}
void destroy_queue(void)
{
int start, end;
struct node_st *current = root;
struct node_st *previous = root;
start = current->id;
do{
end =current->id;
current = current->next;
}while(current->id != start);
while(current->id != end)
{
previous = current;
current = current->next;
free(previous);
previous = NULL;
}
free(current);
current = NULL;
}
::::::::::::::
queue.h
::::::::::::::
#include
#define QUEUE_TYPE int
void create_queue(size_t size);
void destroy_queue(void );
void insert(QUEUE_TYPE value);
void delete(void);
QUEUE_TYPE first(void);
int is_empty(void);
int is_full(void);
void show_queue(void);
栈定义：
::::::::::::::
g_stack.h
::::::::::::::
#include
#define GENERIC_STACK( STACK_TYPE, SUFFIX, STACK_SIZE) \
static STACK_TYPE stack##SUFFIX[STACK_SIZE];\
static int top_element##SUFFIX = -1;\
\
int \
is_empty##SUFFIX(void) \
{ \
return top_element##SUFFIX == -1; \
} \
\
int \
is_full##SUFFIX(void) \
{ \
return top_element##SUFFIX == STACK_SIZE -1; \
} \
\
void \
push##SUFFIX(STACK_TYPE value) \
{ \
assert(!is_full##SUFFIX()); \
top_element##SUFFIX += 1; \
stack##SUFFIX[top_element##SUFFIX] = value; \
} \
\
void \
pop##SUFFIX(void) \
{ \
assert(!is_empty##SUFFIX()); \
top_element##SUFFIX -= 1; \
} \
\
STACK_TYPE top##SUFFIX(void) \
{ \
assert(!is_empty##SUFFIX()); \
return stack##SUFFIX[top_element##SUFFIX]; \
}
方法二：利用二叉树建立一个逆波兰序的表达式（需要先吧中序表达式转成逆波兰序表达式）
主程序：
::::::::::::::
main.c
::::::::::::::
#include
#include
#include "tree.h"
#include "g_stack.h"
#include "point_stack.h"
#define MAXSIZE 50
#define MAXOPSIZE 100000
GENERIC_STACK(char,_char,30)
GENERIC_STACK(char,_char_2,30)
void getstring(char *str)
{
int i;
fgets(str, MAXSIZE, stdin);
}
int converse(char *str)
{
int i;
int count=0;
int num=0;
int mul=1;
while(str[count]!='\0' && str[count]!='\n')
count++;
for(i=count-1;i>=0;i--)
{
num += mul*(str[i]-'0');
mul *= 10;
}
return num;
}
int compare_op(char a,char b)
{
int flag_a;
int flag_b;
if(a == '+' || a == '-')
flag_a = 1;
else if(a == '*' || a == '/')
flag_a = 2;
else if(a == '^')
flag_a =3;
else if(a == '#' || a == '(')
flag_a = 0;
if(b == '+' || b == '-')
flag_b = 1;
else if(b == '*' || b == '/')
flag_b = 2;
else if(b == '^')
flag_b =3;
else if(b == '#' || b == '(')
flag_b = 0;
return flag_a - flag_b;
}
void print_op(char end_op)
{
while(top_char() != end_op)
{
push_char_2(top_char());
pop_char();
}
}
void reverse_char(char *des, char *src)
{
int i;
int j;
for(i=0;src[i] != '\0';i++);
for(j=0;j des[j]=src[i-j-1];
des[j]='\0';
}
void MiddleToEnd(char *buffer)
{
int i;
char des[MAXSIZE];
char current_op;
push_char('#');
push_char_2('#');
for(i=0;buffer[i]!='\n';i++)
{
if(buffer[i] == ')')
{
print_op('(');
pop_char();
continue;
}
else if(buffer[i] == '(')
{
push_char(buffer[i]);
continue;
}
if(isalnum(buffer[i]))
push_char_2(buffer[i]);
else
{
if(isalnum(buffer[i-1]))
push_char_2(' ');
current_op = buffer[i];
if(buf
fer[i]=='(' || compare_op(top_char(),current_op)<0)
push_char(buffer[i]);
else
{
while((compare_op(top_char(),current_op) > 0) || (compare_op(top_char(),current_op)== 0 ))
{
push_char_2(top_char());
pop_char();
}
push_char(buffer[i]);
}
}
}
print_op('#');
for(i=0;!is_empty_char_2();i++)
{
des[i]=top_char_2();
pop_char_2();
}
des[--i]='\0';
reverse_char(buffer,des);
}
SearchTree CreateExprTree(char *buffer)
{
int i;
int num;
char digit_str[20];
int str_count;
SearchTree p_l;
SearchTree p_r;
SearchTree op;
SearchTree T[100]={NULL};
int t_count = 0;
Stack S = NULL;
S = CreateStack();
for(i=0; buffer[i] != '\0'; i++)
{
// printf("buffer[i]=%c\n",buffer[i]);
if(isdigit(buffer[i]))
{
str_count = 0;
while(isdigit(buffer[i]))
{
digit_str[str_count] = buffer[i];
i++;
str_count++;
}
if(!isspace(buffer[i]))
i--;
digit_str[str_count] = '\0';
num = converse(digit_str);
p_l = Insert(num, T[t_count]);
// p_l = Find(num, T[t_count]);
// printf("Push p_l for %d\n",num);
Push(p_l, S);
t_count++;
}
else
{
p_r = top(S);
Pop(S);
p_l = top(S);
Pop(S);
op = Insert(buffer[i]-MAXOPSIZE, T[t_count]);
op->Left = p_l;
op->Right = p_r;
Push(op, S);
t_count++;
}
}
return op;
}
int result(int a, int b, char op)
{
int i;
int mul_sum=1;
switch(op){
case '+':
return a+b;
break;
case '-':
return a-b;
break;
case '*':
return a*b;
break;
case '/':
return a/b;
break;
case '^':
for(i=b;i>0;i--)
mul_sum *= a;
return mul_sum;
break;
default:
break;
}
}
SearchTree CutTree(SearchTree T)
{
ElementType sum;
char op;
SearchTree t_l;
SearchTree t_r;
while(1)
{
if(T->Left->Element > 128 - MAXOPSIZE && T->Right->Element > 128 - MAXOPSIZE)
{
t_l = T->Left;
t_r = T->Right;
op = (char)(T->Element+MAXOPSIZE);
printf("\n%c ",op);
T->Element = result(T->Left->Element, T->Right->Element, op);
T->Left = T->Right = NULL;
printf("result is %d\n",T->Element);
free(t_l);
free(t_r);
return T;
}
else
{
if(T->Left->Element < 128 - MAXOPSIZE)
{
T->Left = CutTree(T->Left);
}
if(T->Right->Element < 128 - MAXOPSIZE)
{
T->Right = CutTree(T->Right);
}
}
}
return T;
}
int main(void)
{
char buffer[MAXSIZE];
int num;
int i;
char current_op;
char top_op;
SearchTree root = NULL;
Position res = NULL;
getstring(buffer);
MiddleToEnd(buffer);
printf("%s\n",buffer);
root = CreateExprTree(buffer);
// ListTree(root, printf_s);
res = CutTree(root);
printf("The final result is %d\n",res->Element);
#ifdef DEBUG
push_char('#');
for(i=0;buffer[i]!='\n';i++)
{
if(buffer[i] == ')')
{
print_op('(');
pop_char();
continue;
}
if(isalnum(buffer[i]))
printf("%c",buffer[i]);
else
{
if(isalnum(buffer[i-1]))
printf(" ");
current_op = buffer[i];
// if(buffer[i]=='(');
// printf("%c\n",buffer[i]);
if(buffer[i]=='(' || compare_op(top_char(),current_op)<0)
push_char(buffer[i]);
else
{
while((compare_op(top_char(),current_op) > 0) || (compare_op(top_char(),current_op)==
0 ))
{
printf("%c",top_char());
pop_char();
}
push_char(buffer[i]);
}
}
}
print_op('#');
// num = converse(buffer);
// printf("%d\n",num);
#endif
}
指针栈的代码：
::::::::::::::
point_stack.c
::::::::::::::
#include "point_stack.h"
#include
#include
#include
Stack CreateStack(void)
{
Stack S = NULL;
S = malloc(sizeof(struct Node *));
if(S == NULL)
{
printf("Fail to malloc\n");
return NULL;
}
S->Next = NULL;
return S;
}
void Push(ElementStackType X, Stack S)
{
Stack new;
new = malloc(sizeof(struct Node *));
if(new == NULL)
{
printf("Fail to malloc\n");
exit(1);
}
new->Element = X;
new->Next = S->Next;
S->Next = new;
}
ElementStackType top(Stack S)
{
if(!IsEmpty(S))
return S->Next->Element;
else
{
perror("Empty Stack!!!\n");
exit(1);
}
}
void Pop(Stack S)
{
Stack FirstCell = NULL;
if(IsEmpty(S))
{
perror("Empty Stack!!!\n");
exit(1);
}
else
{
FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);
}
}
int IsEmpty(Stack S)
{
return S->Next == NULL;
}
void MakeStackEmpty(Stack S)
{
Stack FirstCell = NULL;
if(S == NULL)
perror("Must use CreateStack first!\n");
else
while(S->Next != NULL)
{
FirstCell = S->Next;
Pop(S);
free(FirstCell);
}
}
::::::::::::::
point_stack.h
::::::::::::::
#ifndef __POINT_STACK_H_
#define __POINT_STACK_H_
#define ElementStackType void*
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void Push(ElementStackType X, Stack S);
ElementStackType top(Stack S);
void Pop(Stack S);
#endif
struct Node
{
ElementStackType Element;
PtrToNode Next;
};
二叉树代码：
::::::::::::::
tree.h
::::::::::::::
#ifndef __TREE_SH_
#define __TREE_SH_
#define ElementType int
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
SearchTree MakeEmpty(SearchTree T);
SearchTree CreateTree(void); //Don need it
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);
void ListTree(Position P, void (*callback)(ElementType X));
void printf_s(ElementType X);
int Count_Node(SearchTree T);
#endif
struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
};
::::::::::::::
tree.c
::::::::::::::
#include "tree.h"
#include
#include
#define MAXOP 100000
static int count = 0;
SearchTree CreateTree(void)
{
SearchTree new;
new = malloc(sizeof(SearchTree));
new->Left = new->Right = NULL;
return new;
}
SearchTree MakeEmpty(SearchTree T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
ElementType Retrieve(Position P)
{
return P->Element;
}
void printf_s(ElementType X)
{
if(X < -1)
printf("%c\n",X+MAXOP);
else
printf("%d\n",X);
}
void ListTree(Position P, void (*callback)(ElementType X))
{
if(P != NULL)
{
(*callback)(P->Element);
ListTree(P->Left,callback);
ListTree(P->Right,callback);
}
}
int Count_Node(SearchTree T)
{
if( T != NULL)
{
count++;
Count_Node(T->Left);
Count_Node(T->Right);
}
return count;
}
SearchTree Delete(ElementType X, SearchTree T)
{
Position P = T;
Position SmallRC = NULL;
if(P == NULL)
return NULL;
else if(X < P->Element)
P->Left = Delete(X, P->Left);
else if(X > P->Element)
P->Right = Delete(X, P->Right);
else if(X == P->Element)
{
if((P->Left != NULL) && (P->Right != NULL))
{
SmallRC = FindMin(P->Right);
P->Element = SmallRC->Element;
P->Right = Delete(P->Element,P->Right);
}
else if((P->Left == NULL)||(P->Right == NULL))
{
SmallRC = P;
if(P->Left == NULL)
P = P->Right;
else if(P->Right == NULL)
P = P->Left;
free(SmallRC);
}
}
return P;
}
int My_Delete(ElementType X, SearchTree T)
{
}
SearchTree Insert(ElementType X, SearchTree T)
{
if(T == NULL)
{
// printf("insert %d\n",X);
T = malloc(sizeof(struct TreeNode *));
if(T == NULL)
{
perror("Fail to malloc memory for a new tree!!!\n");
return NULL;
}
T->Element = X;
T->Left = T->Right = NULL;
return T;
}
else
{
if(X < T->Element)
T->Left = Insert(X,T->Left);
else
T->Right = Insert(X,T->Right);
}
return T;
}
Position Find(ElementType X, SearchTree T)
{
Position P = T;
if(T == NULL)
return NULL;
while(P != NULL)
{
if(X < P->Element)
P = P->Left;
else if(X > P->Element)
P = P->Right;
else
return P;
}
return NULL;
}
Position FindMin(SearchTree T)
{
Position P = T;
while(P->Left !=NULL)
P = P->Left;
return P;
}
Position FindMax(SearchTree T)
{
Position P = T;
while(P->Right != NULL)
P = P->Right;
return P;
}
阅读(1524) | 评论(0) | 转发(0) |
