Archive for 四月, 2011

maze – 回溯法解决迷宫

LINUX C & ARM & C51 | Posted by 老沙
4月 22 2011

#include <stdio.h>

struct point {
    int row;
    int col;
};

/* define point stack */
struct point stack[512];

/* define stack pointer */
int top = 0;

/* define push() */
void push(struct point node)
{
    stack[top++] = node;
    return;
}

/* define pop() */
struct point pop(void)
{
    return stack[–top];
}

/* define isempty() */
int isempty(void)
{
    return (top == 0);
}

int maze[5][5] =
{
    { 0, 0, 0, 0, 0 },
    { 1, 1, 1, 1, 0 },
    { 0, 0, 0, 1, 0 },
    { 0, 0, 0, 1, 0 },
    { 0, 0, 0, 1, 0 }
};

struct point father[5][5] =
{
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
};

void print_stack(void)
{
    int i;

    for (i = top-1; i >= 0; i–)
        printf("(%d, %d) n", stack[i].row, stack[i].col);

    printf("————————n");

    return;
}

void print_maze(void)
{
    int i, j;

    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 5; j++)
        {
            printf("%d ", maze[i][j]);
        }
        printf("n");
    }

    printf("————————n");
    return;
}

void print_father(void)
{
    int i, j;
    struct point node;

    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 5; j++)
        {
            node = father[i][j];
            printf("(%2d,%2d) ", node.row, node.col);
        }
        printf("n");
    }

    printf("————————n");
    return;
}

struct point entry = {0, 0};
struct point out = {4, 4};

void backtrack(struct point p)
{
    /* define tmp node = curr point */
    struct point node = p;
    struct point null = {-1, -1};
    struct point top, topfather;
    int row, col;

#ifdef DEBUG
    printf("backtrack is begin n");
    print_stack();
    getchar();
#endif

    /* peak stack top */
    top = pop();
    push(top);

    /* get top father */
    topfather = father[top.row][top.col];

    while(1)
    {
        /* get curr node's row & col */
        row = node.row;
        col = node.col;

        /* clear maze[][] = 0 */
        maze[row][col] = 0;

        /* get current node's father */
        node = father[row][col];

        /* clear father[][] = (-1,-1) */
        father[row][col] = null;
#ifdef DEBUG
        print_maze();
        print_father();
        getchar();
#endif

        /* end condition */
        /* peak stack top point -> topfather */
        /* if node == topfather, break */
        if (node.row == topfather.row && node.col == topfather.col)
            break;
    }

//    printf("backtrack is over n");
}

void print_solution(void)
{
    /* define tmp node = exit point */
    struct point node = out;
    int row, col;
    static int counter = 0;

    while(1)
    {
        /* print curr node */
        printf("(%d, %d) <- ", node.row, node.col);
        row = node.row;
        col = node.col;

        /* get current node's father */
        node = father[row][col];

        /* if current node is (-1,-1), then break */
        if (node.row == -1)
            break;
    }

    printf("n");   
    printf("%d solution is over n", ++counter);   

    return;
}

int main(void)
{
    //struct point entry = {2, 2};
    struct point curr;
    struct point node;
    int flag = 0;

    printf("hello, mazer!n");

    /* init stack, push entry point */
    push(entry);

#ifdef DEBUG
    print_stack();
    print_maze();   
    print_father();   
#endif

    while (!isempty())
    {
        /* get the stack top */
        curr = pop();
       
        /* flag curr point */
        maze[curr.row][curr.col] = 2;

        /* check it */
    //    print_stack();
    //    print_maze();

        /* judgement if curr is exit point */
        if (curr.row == out.row && curr.col == out.col)
        {
            printf("one solution found! n");
            print_solution();

            /* begin to backtrack */
            backtrack(curr);
        //    break;
            continue;
        }

        /* expand from curr */
        flag = 0;

        /* look left */
        if (curr.col-1 >= 0 && maze[curr.row][curr.col-1] == 0)
        {
            /* push left point */
            node.row = curr.row;
            node.col = curr.col – 1;
            /* node 's father is null */
            if (father[node.row][node.col].row == -1)
            {   
                push(node);
                /* remember father */
                father[node.row][node.col] = curr;
                flag++;
            }
        }

        /* look up */
        if (curr.row-1 >= 0 && maze[curr.row-1][curr.col] == 0)
        {
            /* push up point */
            node.row = curr.row – 1;
            node.col = curr.col;
            if (father[node.row][node.col].row == -1)
            {   
                push(node);
                /* remember father */
                father[node.row][node.col] = curr;
                flag++;
            }
        }

        /* look right */
        if (curr.col+1 < 5 && maze[curr.row][curr.col+1] == 0)
        {
            /* push right point */
            node.row = curr.row;
            node.col = curr.col + 1;
            if (father[node.row][node.col].row == -1)
            {   
                push(node);
                /* remember father */
                father[node.row][node.col] = curr;
                flag++;
            }
        }

        /* look down */
        if (curr.row+1 < 5 && maze[curr.row+1][curr.col] == 0)
        {
            /* push down point */
            node.row = curr.row + 1;
            node.col = curr.col;
            if (father[node.row][node.col].row == -1)
            {   
                push(node);
                /* remember father */
                father[node.row][node.col] = curr;
                flag++;
            }
        }
#ifdef DEBUG
        print_stack();
        print_father();
        getchar();
#endif

        /* if no way out (curr node has no expand node) */
        if (flag == 0)
            backtrack(curr);
    }

    printf("maze is over n");
//    print_stack();
   
    return 0;
}
 

bubble – 冒泡排序

LINUX C & ARM & C51 | Posted by 老沙
4月 22 2011

#include <stdio.h>

int bubble(int *a,int len)
{
    int i,j;

    for(i=0;i<len-1;i++){
        for(j=0;j<len-i-1;j++){
            if(a[j]>a[j+1]){
                a[j]^=a[j+1];
                a[j+1]^=a[j];
                a[j]^=a[j+1];
            }
        }
    }
    return 0;
}

int main(void)
{
    int a[]={6,5,4,3,2,1},i;

    bubble(a,6);
    for(i=0;i<6;i++){
        printf("%d ",a[i]);

    }
    printf("n");
   
    return 0;
}

 

mergesort – 归并排序

LINUX C & ARM & C51 | Posted by 老沙
4月 22 2011

#include <stdio.h>
#define LEN 8
int a[LEN]={5,2,4,7,1,3,2,6};
void merge(int start,int mid,int end)
{
    int n1=mid-start+1;
    int n2=end-mid;
    int left[n1],right[n2];
    int i,j,k;

    for(i=0;i<n1;i++)
        left[i]=a[start+i];
    for(j=0;j<n2;j++)
        right[j]=a[mid+j+1];

    i=j=0;

    for(k=start;i < n1 && j <n2;k++){
        if(left[i]<right[j]){
            a[k]=left[i];
            i++;
        }
        else{
            a[k]=right[j];
            j++;
        }

    }

    if(i<n1){
        for(;i<n1;i++){
            a[k]=left[i];
            k++;
        }
    }
    if(j<n2){
        for(;j<n2;j++){
            a[k]=right[j];
            k++;
        }
    }

}
void sort(int start,int end)
{
    int mid;
    if(start<end){
        mid=(start+end)/2;
        sort(start,mid);
        sort(mid+1,end);
        merge(start,mid,end);

    }

}

int main(void)
{
    int i;
    sort(0,LEN-1);
    for(i=0;i<LEN;i++){
        printf("%d ",a[i]);
    }
    printf("n");

    return 0;
}

 

insertion – 插入排序

LINUX C & ARM & C51 | Posted by 老沙
4月 22 2011

void insertion_sort(int *a,int len)
{
    int i,j,key;

    for(i=1;i<len;i++){
        key=a[i];
        j=i-1;
        while(j>=0 && a[j]>key){
            a[j+1]=a[j];
            j–;
        }
        a[j+1]=key;
    }
}

int main(void)
{
    int a[]={12,5,9,3,4,7,4,6,2},i;

    for(i=0;i<9;i++)
        printf("%d ",a[i]);
    printf("n");
    insertion_sort(a,9);
    for(i=0;i<9;i++)
        printf("%d ",a[i]);
    printf("n");
    return 0;
}

 

halfind – 折半查找

LINUX C & ARM & C51 | Posted by 老沙
4月 22 2011

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LEN 8

int halfind(int *a,int key)
{
    int start =0,end=LEN-1,mid;
    while(start <= end){
        mid=(start+end)/2;
        if(a[mid] > key){
            end=mid -1;
        }
        else if(a[mid] < key){
            start=mid+1;
        }
        else
            return mid;   

    }

    return -1;
}

int main(int argc,char **argv)
{
    int a[]={1,2,3,4,5,6,7,8};
    printf("%dn",halfind(a,atoi(argv[1])));
   
    return 0;
}

 

==============递归方式===============

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LEN 8
int a[]={1,2,3,4,5,6,7,8};

int halfind(int start,int end,int key)
{
    int mid;
    if(start <= end){

        mid=(start+end)/2;
        if(a[mid] > key){
            halfind(start,mid -1,key);
           
        }
        else if(a[mid] < key){
            halfind(mid+1,end,key);
        }
        else{
            printf("%dn",mid);
            return mid;   
        }

    }

    return -1;
}

int main(int argc,char **argv)
{
    printf("%dn",halfind(0,LEN-1,atoi(argv[1])));
   
    return 0;
}
 

变参 – Variadic 应用

LINUX C & ARM & C51 | Posted by 老沙
4月 17 2011

好久没更新博客了,太忙了^-^

这是我写的一个仿scanf函数,比较粗糙,只是练习一下变参

#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <stdlib.h>
void dget(int *b, char k)
{
    char n[20],*a;
    a=n;
    do{
    *a=getchar();
    a++;
    }while(!(*(a-1) == 'n' || *(a-1) == k));
    *(a-1)='';
    *b=atoi(n);
}

void sget(char *a,char k)
{
    do{
    *a=getchar();
    a++;
    }while(!(*(a-1) == 'n' || *(a-1) == k));
    *(a-1)='';
}

void cget(char *a)
{
    *a=getchar();
    getchar();
}

int myscanf(char *list, …)
{
    va_list ap;
    char *p;
    int *num;
   

    va_start(ap,list);
    for(;*list!='';list++){
       
        if(*list=='%'){
            switch(*(list+1)){
                case 'c':
                    p=(char *)va_arg(ap,int);
                    cget(p);
                    list++;
                    continue;
                case 's':
                    p=(char *)va_arg(ap,int);
                    sget(p,*(list+2));
                    list++;
                    continue;
                case 'd':
                    num=(int *)va_arg(ap,int);
                    dget(num,*(list+2));
                    list++;
                    continue;
                default:
                    //list++;
                    break;
            }
        }
    }

    return 0;
}

int main(void)
{
    int a,c;
    char b[30];
    myscanf("%s,%d,%c",b,&c,&a);
    printf("%s,%c,%d",b,a,c);
    return 0;
}