Chinaunix首页 | 论坛 | 博客
  • 博客访问: 34116
  • 博文数量: 8
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 14
  • 用 户 组: 普通用户
  • 注册时间: 2013-09-23 11:25
文章分类
文章存档

2015年(2)

2014年(4)

2013年(2)

我的朋友

分类: C/C++

2014-10-21 21:28:40

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;

}

阅读(1257) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~