Follow Fang!: Data structure

顯示具有 Data structure 標籤的文章。顯示所有文章

2013/08/01

Java 中序轉後序中序轉前序演算法

最近別實驗室的學弟要寫一個計算機，但是他沒想到方法
我推薦他用中序轉後序的方式去處理，不過他似乎不太瞭解
所以我就直接幫他分析一下程式碼

這次程式碼是由良葛格的『中序式轉後序式（前序式）』及『後序式的運算』複製過來的XD

分別由『Calculator』及『Infix』所組成的，Infix類別是在做『中序轉前序』或『中序轉後序』
Calculator則是提供輸入四則運算以及運算的類別

觀念部份，改天補上

資料結構刪除單向鍊結串列

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 10
 
struct List
{
    int num;
    int total;
    struct List *Next;
};
typedef struct List Node;
typedef Node *Link;

int Data[2][MAX]={1,3,5,7,9,2,4,6,8,10,
                    141,77,150,200,19,12,1414,176,188,20};
 
 
Link Delete_List(Link Head, int Key)
{
    Link Pointer = Head;
    Link Back;

    while(1){
        if(Pointer->Next == NULL){
            printf("Not found\n");
            break;
        }

        if(Head->num == Key){
            Head = Pointer->Next;
            free(Pointer);
            break;
        }

        Back = Pointer;
        Pointer = Pointer->Next;

        if(Pointer->num == Key){
            Back ->Next = Pointer->Next;
            free(Pointer);
            break;
        }
    }

    return Head;
}


void Print_List(Link Head)
{
    Link Pointer = Head;

    while (Pointer != NULL){
        printf("[%d, %d] ", Pointer->num, Pointer->total);
        Pointer = Pointer->Next;
    }
    printf("\n");
}
 
void Free_List(Link Head)
{
    Link Pointer;
    while(Head != NULL){
        Pointer = Head;
        Head = Head->Next;
        free(Pointer);
    }
}
 
Link Create_List(Link Head)
{
    Link New;
    Link Pointer;
    int i;
 
    Head = (Link)malloc(sizeof(Node));
     
    if(Head == NULL)
        printf("Memory allocate Failure!!\n");
    else{
        Head->num = Data[0][0];
        Head->total = Data[1][0];
        Head->Next = NULL;
 
        Pointer = Head;
         
        for(i=1; i<MAX; i++){
            New = (Link)malloc(sizeof(Node));
            New->num = Data[0][i];
            New->total = Data[1][i];
            New->Next = NULL;
 
            Pointer->Next = New;
            Pointer = New;
        }
    }
     
    return Head;
}
 
void main()
{
    Link Head = Create_List(Head);
    int key;
 
    if(Head != NULL){

        Print_List(Head);

        while(1){
            printf("Input 0 to Exit\n");    
            
            printf("Input data number for Delete:");
            scanf("%d", &key);
            
            if(key == 0)
                break;

            Head = Delete_List(Head, key);
            Print_List(Head);
        }

        Free_List(Head);
    }
}

參考資料：
資料結構黃國瑜/葉乃菁

資料結構單向鍊結串列插入

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 10
 
struct List
{
    int num;
    int total;
    struct List *Next;
};
typedef struct List Node;
typedef Node *Link;
 
int Data[2][MAX]={1,3,5,7,9,2,4,6,8,10,
                    141,77,150,200,19,12,1414,176,188,20};
 
 
Link Insert_List(Link Head, Link New, int key)
{
    Link Pointer = Head;

    while(1){

        if(Pointer == NULL){
            New->Next = Head;
            Head = New;
            break;
        }

        if(Pointer->num == key){
            New->Next = Pointer->Next;
            Pointer->Next = New;
            break;
        }

        Pointer = Pointer->Next;
    }

    return Head;
}


void Print_List(Link Head)
{
    Link Pointer = Head;

    while (Pointer != NULL){
        printf("[%d, %d] ", Pointer->num, Pointer->total);
        Pointer = Pointer->Next;
    }
    printf("\n");
}
 
void Free_List(Link Head)
{
    Link Pointer;
    while(Head != NULL){
        Pointer = Head;
        Head = Head->Next;
        free(Pointer);
    }
}
 
Link Create_List(Link Head)
{
    Link New;
    Link Pointer;
    int i;
 
    Head = (Link)malloc(sizeof(Node));
     
    if(Head == NULL)
        printf("Memory allocate Failure!!\n");
    else{
        Head->num = Data[0][0];
        Head->total = Data[1][0];
        Head->Next = NULL;
 
        Pointer = Head;
         
        for(i=1; i<MAX; i++){
            New = (Link)malloc(sizeof(Node));
            New->num = Data[0][i];
            New->total = Data[1][i];
            New->Next = NULL;
 
            Pointer->Next = New;
            Pointer = New;
        }
    }
     
    return Head;
}
 
void main()
{
    Link Head = Create_List(Head);
    Link New;
    int key;
 
    if(Head != NULL){
        Print_List(Head);

        while(1){
            printf("Input 0 to Exit\n");
            
            New = (Link) malloc(sizeof(Node));
            
            printf("Input data number:");
            scanf("%d", &New->num);
            
            if(New->num == 0)
                break;

            printf("Input data total:");
            scanf("%d", &New->total);

            printf("Input the data number for Insert:");
            scanf("%d", &key);

            Head = Insert_List(Head, New, key);

            Print_List(Head);
        }

        Free_List(Head);
    }
}

參考資料：
資料結構黃國瑜/葉乃菁

資料結構單向鍊結串列搜尋

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct List
{
    int num;
    int total;
    struct List *Next;
};
typedef struct List Node;
typedef Node *Link;

int SearchTime = 0;
int Data[2][MAX]={91,35,75,75,99,2,400,6,85,100,
                    141,77,150,200,19,12,1414,176,188,20};


int Search_List(int key, Link Head)
{
    Link Pointer;
    Pointer = Head;

    while( Pointer != NULL){
        SearchTime++;
        if( Pointer->num == key ){
            printf("Data number: %d\n", Pointer->num);
            printf("Data total: %d\n", Pointer->total);
            return 1;
        }
        Pointer = Pointer->Next;
    }

    return 0;
}


void Free_List(Link Head)
{
    Link Pointer;
    while(Head != NULL){
        Pointer = Head;
        Head = Head->Next;
        free(Pointer);
    }
}

Link Create_List(Link Head)
{
    Link New;
    Link Pointer;
    int i;

    Head = (Link)malloc(sizeof(Node));
    
    if(Head == NULL)
        printf("Memory allocate Failure!!\n");
    else{
        Head->num = Data[0][0];
        Head->total = Data[1][0];
        Head->Next = NULL;

        Pointer = Head;
        
        for(i=1; i<MAX; i++){
            New = (Link)malloc(sizeof(Node));
            New->num = Data[0][i];
            New->total = Data[1][i];
            New->Next = NULL;

            Pointer->Next = New;
            Pointer = New;
        }
    }
    
    return Head;
}

void main()
{
    Link Head = Create_List(Head);
    int number;

    if(Head != NULL){
        printf("Input Data number:");
        scanf("%d", &number);

        if( Search_List(number,Head)){
            printf("Search time = %d\n", SearchTime);
        }else{
            printf("NO found!!\n");
        }

        Free_List(Head);
    }
}

參考資料：
資料結構黃國瑜/葉乃菁

資料結構 Greatest common divisor(最大公因數)

GCD是耳熟能詳的一種遞迴方法，中文意思是『求最大公因數』
求最大公因數再小學的時候就有交過，有一種方法就是透過輾轉相除法
透過輾轉相除法不斷的對除，最後解即為最大公因數

程式碼如下：

#include <stdio.h>

int count = 0;

int GCD(int a, int b){
        count++;

        if(a % b == 0)  return b;
        else return GCD(b, a % b);
}

int main()
{
        printf("Number:%d\n", GCD(120, 45));
        printf("Count:%d\n", count);

        return 0;
}

資料結構 Ackermain's function(阿克曼函數)

感覺是很複雜的函數，有興趣可以探討『阿克曼函数--一个计算方法』

#include <stdio.h>

int count = 0;

int Ackerman(int m, int n){
        count++;

        if(m == 0) return n + 1;
        else if(n == 0) return Ackerman(m - 1, 1);
        else return Ackerman(m - 1, Ackerman(m, n - 1));
}


int main()
{
        printf("Number:%d\n", Ackerman(2,2));
        printf("Count:%d\n", count);

        return 0;
}

參考資料：
http://zh.wikipedia.org/wiki/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B8
http://blog.sina.com.cn/s/blog_4765a1560100bpqn.html

資料結構 Binomial coefficient(二項式係數)

有興趣可以參考一下Binomial coefficient

#include <stdio.h>
int count = 0;

int Binomial(int n, int m){
         count++;

         if( n == m || m == 0 )
                return 1;
         else
                return (Binomial( n - 1, m) + Binomial( n - 1 , m - 1 ));
}

int main()
{
         printf("Number:%d\n",Binomial(5,3));
         printf("Count%d\n",count);

        return 0;
}

參考資料：
http://en.wikipedia.org/wiki/Binomial_coefficient

Follow Fang!

2013/08/01

Java 中序轉後序中序轉前序演算法

2013/07/27

資料結構刪除單向鍊結串列

資料結構單向鍊結串列插入

資料結構單向鍊結串列搜尋

資料結構 Greatest common divisor(最大公因數)

資料結構 Ackermain's function(阿克曼函數)

資料結構 Binomial coefficient(二項式係數)

2012/11/30

資料結構反轉鍊結串列

資料結構將兩個鍊結串列相連

2012/11/28

資料結構河內之塔(Tower of Hanoi)

2012/11/27

資料結構刪除鍊結串列

2012/11/24

資料結構單向鍊結串列應用

資料結構下三角陣列轉一維陣列

資料結構上三角陣列轉一維陣列

資料結構稀疏矩陣

資料結構二維陣列轉成一維陣列

資料結構費氏數列

資料結構矩陣相乘