[C語言] 快速排序法(quick sort)

#include<stdio.h>

/** quick_sort [快速排序法]
 * @param {array} array
 * @param {int} low
 * @param {int} high
 */
int quick_sort(int *array,int low,int high) {
    int pivot_point,pivot_item,i,j,temp;
    // 指標交界結束排序
    if(high<=low){return 1;}

    // 紀錄樞紐值
    pivot_item = array[low];
    j=low;
    
    // 尋找比樞紐小的數
    for(i=low+1; i<=high; i++) {
        // 跳過等於或大於的數
        if(array[i]>=pivot_item){continue;}

        j++;
        // 交換 array[i] , array[j]
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 將樞紐位址移到中間
    pivot_point=j;
    // 交換 array[low] , array[pivot_point]
    temp = array[low];
    array[low] = array[pivot_point];
    array[pivot_point] = temp;

    // 遞迴處理左側區段
    quick_sort(array,low,pivot_point-1);
    // 遞迴處理右側區段
    quick_sort(array,pivot_point+1,high);

    return 1;
}


/*主程式*/
int main(){
    int a[]={12,42,54,3,5,32,61,24,31};

    quick_sort(a,0,8);

    int i;
    for(i=0; i<=8; i++) {
        printf("%d\n",a[i]);
    }

    _getch();
    return 0;
}

[C語言] 連結串列(link list)

/* link list (連結串列) */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/* 定義結構型態 */
typedef struct link_node{
    int data;
    struct link_node *link;
} LINK_NODE;



/* 產生新節點 */
LINK_NODE *new_node(int data){
    LINK_NODE *node;
    node=(LINK_NODE *) malloc(sizeof(LINK_NODE));/*<stdlib.h>*/
    
    // 記憶體不足
    if(node == NULL){ return NULL;}
    
    node->data=data;  
    node->link=NULL;     
    return node;
}


/* 加入新的資料於最後 */
LINK_NODE *push_node(LINK_NODE *list, int data){
    /*產生新節點*/
    LINK_NODE *node=new_node(data);  

    // 加入第一個新節點
    if(list==NULL){    
        list=node;
    }else{
        LINK_NODE *p=list;  
        // 取得最後一個節點
        while(p->link!=NULL){p=p->link;}
        p->link=node;
    }   
    return list;
}


/* 排序插入新節點 */
LINK_NODE *sort_insert(LINK_NODE *list,int data){
    // 加入第一筆資料
    
    // 產生新節點
    LINK_NODE *node=new_node(data);    
    if(list==NULL){ list=node; return list; }  

    // 尋找大於資料(data)的位址
    LINK_NODE *r=list,*q=list;    
    while(r!=NULL && r->data<data){ q=r; r=r->link; }

    if(r==list){ // 首節點
        node->link=list; list=node; 
    }else{ // 加入新節點於中間
        node->link=q->link; 
        q->link=node; 
    }    
    return list; 
}


/* 計算串列長度 */
int get_length(LINK_NODE *list){
    LINK_NODE *p=list;
    int count=0;  
    while(p!=NULL){    
        count++;  
        p=p->link;  
    }
    
    return count;
}


/* 搜尋資料(data)的節點位子 */
LINK_NODE *search_node(LINK_NODE *list, int data){
    LINK_NODE *p=list;  
    while(p!=NULL && p->data!=data){ p=p->link; }
    return p ;
}


/* 印出所有串列的所有資料 */
int display(LINK_NODE *list){
    LINK_NODE *p=list;
    while(p!=NULL){ 
        printf("%d\n",p->data);/*<stdio.h>*/
        p=p->link;  
    }
    return 1;
}




/*主程式*/
int main(){
    LINK_NODE *list=NULL;
    
    list=sort_insert(list,4);
    list=sort_insert(list,2);
    list=sort_insert(list,7);
    list=sort_insert(list,9);
    list=sort_insert(list,14);
    display(list);
    
    printf("--------------------------\n");
    
    list=push_node(list,4);
    list=push_node(list,2);
    list=push_node(list,7);
    list=push_node(list,9);
    list=push_node(list,14);
    display(list);
    
    _getch();  
    return 0;
}

[C語言] 字串取代(str_replace)

strlen , strcpy , strstr , strcat , malloc

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

/* str_replace [字串取代]
 * @param {char*} source 原始的文字
 * @param {char*} find 搜尋的文字  
 * @param {char*} rep 替換的文字
 * */
char *str_replace (char *source, char *find,  char *rep){
    // 搜尋文字的長度
    int find_L=strlen(find);
    // 替換文字的長度
    int rep_L=strlen(rep);
    // 結果文字的長度
    int length=strlen(source)+1;
    // 定位偏移量
    int gap=0;
    
    // 建立結果文字，並複製文字
    char *result = (char*)malloc(sizeof(char) * length);
    strcpy(result, source);    
    
    // 尚未被取代的字串
    char *former=source;
    // 搜尋文字出現的起始位址指標
    char *location= strstr(former, find);
    
    // 漸進搜尋欲替換的文字
    while(location!=NULL){
        // 增加定位偏移量
        gap+=(location - former);
        // 將結束符號定在搜尋到的位址上
        result[gap]='\0';
        
        // 計算新的長度
        length+=(rep_L-find_L);
        // 變更記憶體空間
        result = (char*)realloc(result, length * sizeof(char));
        // 替換的文字串接在結果後面
        strcat(result, rep);
        // 更新定位偏移量
        gap+=rep_L;
        
        // 更新尚未被取代的字串的位址
        former=location+find_L;
        // 將尚未被取代的文字串接在結果後面
        strcat(result, former);
        
        // 搜尋文字出現的起始位址指標
        location= strstr(former, find);
    }    
 
    return result;

}


int main(){
    char* str1 = "this is a string of characters";
    char* str2 = str_replace(str1, "is","FFF");
    
    printf( "str1: '%s'\n", str1 );
    printf( "str2: '%s'\n", str2 );

    _getch();    
    return 0;
}

參考來源：
Standard C String and Character [C++ Reference]

[C語言] 取得目錄名稱路徑(dirname)

dirname

#include <libgen.h>

int main(){
    char W_path1[] = "E:\\test" ;
    char W_path2[] = "E:\\Program\\clear\\ape-06\\Debug" ;
    char W_path3[] = "E:\\Program\\clear\\.metadata\\.plugins\\org" ;
    
    dirname(W_path1);
    printf("%s\n",W_path1);
    // E:\
    
    dirname(W_path2);
    printf("%s\n",W_path2);
    // E:\Program\clear\ape-06
    
    dirname(W_path3);
    printf("%s\n",W_path3);
    // E:\Program\clear\.metadata\.plugins
    
    char L_path1[] = "/test" ;
    char L_path2[] = "/Program/clear/ape-06/Debug" ;
    char L_path3[] = "/Program/clear/.metadata/.plugins/org" ;
    
    dirname(L_path1);
    printf("%s\n",L_path1);
    // /
    
    dirname(L_path2);
    printf("%s\n",L_path2);
    // /Program/clear/ape-06
    
    dirname(L_path3);
    printf("%s\n",L_path3);
    // /Program/clear/.metadata/.plugins


    _getch();    
    return 0;
}

參考來源：
<libgen.h>

[C語言] 遞迴掃瞄目錄下所有文件(dir_recursive)

opendir , readdir , closedir

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

#include <sys/types.h>
#include <dirent.h>


/* dir_recursive [遞迴掃瞄目錄下所有文件]
 * 掃瞄 path 下所有的文件，並輸出至 output 的文件中
 * output 必須為可寫入的文件
 * */
int dir_recursive(char *path, FILE *output){
    char glue='\\'; // Windows 的分隔符號
    //char glue='/'; // Linux 的分隔符號
    
    // 嘗試開啟目錄
    DIR * dp = opendir(path);
    
    if (!dp){    
        // 不是目錄，輸出至檔案    
           fprintf(output,"%s\n",path);
           return 1;
    }
    
    struct dirent *filename;    
    while((filename=readdir(dp))){
        // 跳過當前及母目錄
        if(!strcmp(filename->d_name,"..") || !strcmp(filename->d_name,".")){
            continue;
        }
        
        // 計算新的路徑字串所需的長度
        int pathLength=strlen(path)+strlen(filename->d_name)+2;
        // 產生新的陣列空間
        char *pathStr = (char*)malloc(sizeof(char) * pathLength);
        // 複製當前目錄路徑至新的陣列空間
        strcpy(pathStr, path);
        
        // 檢查目錄分隔符號
        int i=strlen(pathStr);
        if(pathStr[i-1]!=glue){
            pathStr[i]=glue;
            pathStr[i+1]='\0';
        }
        
        // 串接次目錄名稱或檔案名稱至新的陣列空間
        strcat(pathStr, filename->d_name);
        
        // 遞迴呼叫目錄掃瞄
        dir_recursive(pathStr,output);
        
    }
    
    // 關閉目錄
    closedir(dp);
    
    return 1;
}



int main(){
    // 建立輸出的文件檔
    FILE *fileOut = fopen("output.txt", "w");
    
    // 掃瞄 E:\test 下所有的文件
    dir_recursive("E:\\test",fileOut); 
    
    return 0;
}

參考來源：
[原创]LINUX下用C语言历遍目录 C语言列出目录_小徐博客 学无止境 minix and linux

[C語言] 字串相加(string_concat)

strlen , strcpy , strcat

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

/* string_concat [字串相加]
 * 將 str1 與 str2 相加，並返回新的字串
 * */
char *string_concat(char *str1, char *str2) {
    // 計算所需的陣列長度
    int length=strlen(str1)+strlen(str2)+1;
    
    // 產生新的陣列空間
    char *result = (char*)malloc(sizeof(char) * length);
    
    // 複製第一個字串至新的陣列空間
    strcpy(result, str1);
    // 串接第二個字串至新的陣列空間
    strcat(result, str2);
    
    return result;
}


int main(){
    char *a="123456";
    char *b="abcde";
    char *c=string_concat(a,b);
    printf("%s\n",c);
    
    _getch();
    return 0;
}

參考來源：
Standard C String and Character [C++ Reference]

[C語言] 檔案讀寫

fclose , feof , fopen , fprintf , fscanf , printf , remove , rename , rewind , scanf , ftell , fseek

#include <stdio.h>

int main(){
    FILE *fileIn;
    FILE *fileOut;

    fileIn = fopen("input.txt", "r");
    if(fileIn == NULL){printf("檔案不存在\n"); return 0;}

    fileOut = fopen("output.txt", "w");
    /* Mod:
    * "r" : 開啟檔案，以純文字方式[讀取]。
    * "w" : 開啟或建立檔案，以純文字方式[寫入]，會複寫原先的資料。
    * "a" : 開啟或建立檔案，以純文字方式[寫入]，並將檔案指標移到最後。
    * "rb" : 同 "r" 但以二進位(binary)方式[讀取]。
    * "wb" : 同 "w" 但以二進位(binary)方式[寫入]。
    * "ab" : 同 "a" 但以二進位(binary)方式[寫入]。
    * "r+" : 同 "r" 但同時具有[讀取/寫入]的權力
    * "w+" : 同 "w" 但同時具有[讀取/寫入]的權力
    * "a+" : 同 "a" 但同時具有[讀取/寫入]的權力
    * "rb+" : 同 "rb" 但同時具有[讀取/寫入]的權力
    * "wb+" : 同 "wb" 但同時具有[讀取/寫入]的權力
    * "ab+" : 同 "ab" 但同時具有[讀取/寫入]的權力。
    */


    int    a1;
    float  a2;
    char   a3;
    char   a4[100];

    while(!feof(fileIn)){// 當讀取結束時會回傳 true
        // 依格式讀取一列文字，所有的變數都要取址，除了字元陣列
        fscanf(fileIn,"%d %f %c %s",&a1,&a2,&a3,a4);

        // 依格式將資料輸出至螢幕上
        printf("%d %f %c %s\n",a1,a2,a3,a4);

        // 依格式寫入一列文字
        fprintf(fileOut,"%d %f %c %s\n",a1,a2,a3,a4);

        /* %c : 一個字元(char)格式
        * %s : 一個字串格式
        *
        * %i : 一個整數(int)格式
        * %d : 一個十進位整數(int)格式
        * %u : 一個十進位無符號整數(unsigned)格式
        *
        * %e, %f, %g : 一個浮點數(float)格式
        * %lf: 一個浮點數(double)格式
        *
        * %o : 八進位(02732)格式
        * %x : 十六進位(0x27fa)格式
        * %% : 跳脫成 %
        * */

    }

    // 輸出當前的檔案指標位址
    printf("offset = %ld\n", ftell(fileIn) );

    // 將檔案指標返回至最上面，失敗則回傳 0
    // 會清除錯誤並將 EOF 標示清除
    // 當需要重新讀取時可利用此函數
    rewind(fileIn);

    // 將移動檔案指標從開始處偏移 5 個字元，成功則回傳 0
    // 會將 EOF 標示清除
    fseek(fileIn,5,SEEK_SET);
    /* int fseek( FILE *stream, long offset, int origin );
    * stream : 檔案指標
    * offset : 偏移量，可為正負數
    * origin : 偏移的依據位址
    *   SEEK_SET　0  檔案起始位址
    *   SEEK_CUR  1  當前位址
    *   SEEK_END  2  檔案結束位址
    * */


    // 關閉檔案指標
    fclose(fileIn);
    fclose(fileOut);

    // 將檔案 "input.txt" 移除
    remove("input.txt");

    // 將 "output.txt" 的檔案名稱變更為 "input.txt"
    rename("output.txt","input.txt");


    // 按任意鍵結束
    _getch();
    return 0;
}

參考來源：
Standard C I/O [C++ Reference]
printf() 與 scanf()

[C語言] 動態記憶體配置(malloc)

malloc , calloc , realloc , free

#include <stdlib.h>

int main(){

/*一維陣列*/
    int size1=1000;
    int *array1;
 
    // 利用 malloc 配置空間 。
    array1 = (int*) malloc(size1 * sizeof(int));
    
    // 利用 calloc 配置空間，會初始為 0 。
    array1 = (int*) calloc(size1 , sizeof(int));
    
    // 利用 realloc 將原本的空間調整成兩倍，並且複製原本的內容，
    // 但不保證是原本的空間位址。 
    array1 = (int*) realloc(array1, 2 * size1 * sizeof(int));
    
    
    // 釋放記憶體空間。
    free(array1);
 
 
/*二維陣列*/
    int i;
    int size_x=100;
    int size_y=100;
    int **array2;
    
    // 利用 malloc 配置二維空間 。
    array2 = (int**) malloc(size_x * sizeof(int*));
    for (i=0; i<size_x; i++){
        array2[i] = (int*) malloc(size_y * sizeof(int));
    }
    
    
    // 釋放記憶體空間
    for (i=0; i<size_x; i++){
        free(array2[i]);
    }
    free(array2);
    
    return 0; 
}

參考來源：
Standard C Memory [C++ Reference]