居然花了一個禮拜寫merge sort

服替代役有很多無聊的時間，所以我就在公家電腦灌了cygwin練習用gnu提供的工具(e.g. g++, make等) 來寫程式。一開始挑戰的是我大一的時候寫不出來的merge sort，讀入random.txt並且排列出來，最多排列1024個數字。

merge_sort.cpp

#include "function.h"

int main()

{
        fstream fstr; 
        int i=0; 
        int rand[1024]; 
        int temp[1024]; 
        int randn; 
        
        cout<<"unsorted:"; 
        fstr.open("random.txt", ios::in); 
                while(fstr>>rand[i]){

                cout<<rand[i]<<setw(2); 
                i++; 
        }

        cout<<" # of rands:"<<i<<endl; 
        randn=i; 

        merge_sort(rand, randn, temp); 

        cout<<"sorted list: "; 
        for(i=0; i<randn; i++) 
                cout<<rand[i]<<" "; 

        fstr.close(); 

        return 0; 

}

function.cpp

#include "function.h"

void merge_sort(int* unsorted, int size, int* sorted)

//sort the unsorted array
{
        int mid; 
        int *left, *right; 
        int i; 
        
        if(size<2) return; 

        mid=(size+1)/2; 
        left=unsorted;

        right=unsorted+mid; 

        //printf("[%d, %d]\n", *left, *right); 
        
        merge_sort(left, mid, sorted); 
        merge_sort(right, size-mid, sorted); 
        
        for(i=0; i<size; i++)   printf("%d,", unsorted[i]); 
        printf(" | "); 
        merge(left, mid, right, size-mid, sorted); 
        for(i=0; i<size; i++)   printf("%d,", unsorted[i]); 
        printf("\n"); 


}

void merge(int* left, int sizel, int* right, int sizer, int* sorted)

{
        //printf("left=%d, right=%d, sizel=%d, sizer=%d ", *left, *right, sizel, sizer); 
        int i=0, j=0, k=0; 
        while(i<sizel && j<sizer)

        {
                if(*(left+i)<*(right+j)) {

                        sorted[k]=*(left+i); 
                        i++; 
                }

                else{
                        sorted[k]=*(right+j);

                        j++; 
                }
                k++; 

        }

        if(i==sizel) 
                memcpy(sorted+k, right+j, sizeof(int)*(sizer-j)); 
        if(j==sizer)

                memcpy(sorted+k, left+i, sizeof(int)*(sizel-i)); 

        memcpy(left, sorted, sizeof(int)*(sizel+sizer)); 
        
        //for(i=0; i<sizel+sizer; i++)  printf("%d,", sorted[i]); 

        //printf("\n"); 
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H

#include <iostream>
#include <iomanip>

#include <fstream> 
using namespace std; 
#include <string.h>


void merge_sort(int* unsorted, int size, int* sorted); 

void merge(int* left, int sizel, int* right, int sizer, int* sorted); 


#endif

一個簡易可用的Makefile

以下，我常用的makefile 設定，算蠻夠用了，感謝大學室友pky教導。

<-- makefile sample 1 -->

all: main.o tools.o utility.o
gcc -o a.out main.o tools.o utility.o
main.o: main.c
gcc -o main.o -c main.c
tools.o: tools.c
gcc -o tools.o -c tools.c
utility.o: utility.c
gcc -o utility.o -c utility.c
clean:
rm -f *.o a.out

<-- makefile sample 2 -->

# erase old setting in suffixes
.SUFFIXES:
# add new setting into suffixes
.SUFFIXES: .c .cpp .o

EXE = a.out
CC = gcc
all: main.o tools.o utility.o
$(CC) -o $(EXE) $^
.c.o:
$(CC) -o $@ -c $<
clean:
rm -f *.o $(EXE)

<-- makefile sample 3-->

.SUFFIXES:
.SUFFIXES: .c .cpp .o

EXE = round
CC = g++
OBJS = round.o

all: $(OBJS)
     $(CC) -o $(EXE) $(OBJS)
     ./$(EXE)
.c.o:
     $(CC) -c -o $@ $<
.cpp.o:
     $(CC) -c -o $@ $<
clean:
     rm -f *.o $(EXE)

Linux 新增硬碟的方法

昨天終於可以把1T的硬碟接上去了，紀錄一下方法:

1. 接上硬碟，SATA線和電源線也一併接上

2. 用fdisk 查出新硬碟的代號為何

# fdisk -l

Disk /dev/sdc: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0xe3f21533

Device Boot Start End Blocks Id System

/dev/sdc1 1 121601 976760001 83 Linux

(這是切割好的結果，還沒切割前的System欄位應會是空的，可以看到新硬碟的代號是/dev/sdc)

3. 利用fdisk 切割新硬碟的partition

# fdisk /dev/sdc

(期間會問要切external or primary partition，選primary，據說external是swap區用的 @@? )

4. 將新硬碟格式化為ext3格式

# mke2fs -j /dev/sdc1

(如果step 3選成externel，這個步驟將沒用，mke2fs會跑出錯誤訊息)

5. 建立一個資料夾來作mount，我建在 /home/public/Drama

# mkdir /home/public/Drama

6. 修改/etc/fstab, 這台主機mount的方式已經改為使用UUID來作mount，這樣就不會因為bios認硬碟的順序改變而影響磁碟代號，進而影響到mount的資料夾。

@/etc/fstab

...

#/dev/sdc1 /home/public/Drama ext3 defaults 0 0

UUID=89348fd1-8ec1-4365-98e4-78c06861bac9 /home/public/Drama ext3 defaults 0 0

...

7. 重新mount一次即可，如此新硬碟就被mount在 /home/public/Drama

#mount -a

避免多重定義的技巧

有個header file裡面定義了一個class，而此header file同時被另外兩個cpp 檔include，而此三個檔案編譯之後預計產生一個object code。此時就會有重複宣告的問題。

@common.h
class base_class{...};

@util.h
#include "common.h"
...

@main.h
#include "common.h"
#include "util.h"
int main(){
...
}

在header file內加上 #ifndef, #define與#endif可以解決這個問題，語法如下：

#ifndef
#define
... // header file內的所有source code
#endif

一般Label的規定為前後加上底線，字母全部大寫，並且把dot也變成底線，例如stdio.h:
#ifndef _STDIO_H_
#define _STDIO_H_
...
#endif

如此一來，preprocessor在展開source code的時候就不會有重複宣告的問題，因為util.cpp並不會include到common.h。建議是無論header file會不會被兩個以上的cpp include都加上macro，如此就可安心地include自己想要的header。

const member in class

假設有個class 裡面有個成員具備const屬性，則此const成員必須在initialization list內做初始化。

class A{
public:
A(){};
private:
const int constant1;
const int constant2;
};

A::A(): constant1(123), constant2(456)
{
...
}

C語言- 原來在function裡面回傳一個string只有兩種辦法

今天寫程式的時候發現一個問題: 要怎麼樣在C程式的function回傳一串文字? C程式回傳的東西只能是一個位址(char*), 程式像下面這樣寫的話

char* str_test(){
char a[20]="abcd";
return a;
}

會是嚴重的錯誤, 因為a是local var, 在離開str_test的時候就已經被free掉, 回傳的位址指向的東西將是一串無意義的東西。

所以只有兩種辦法可以做:

第一, 把a指向即使離開str_test也不會被free掉的地方, 就是heap區域, 注意: 但這需要用到heap區域的空間, 如果heap區域滿了, new指令也沒有用, 可能需要做new指令是否成功的檢查。

char* str_test(){
char* a= new char[20];
sprintf(a, "abcd");
return a;
}

第二, 直接把a指向的區域變成即使離開str_test也不會被release, 使用static指令, 但是這還是有點暴力。

char* str_test(){
static char a[20]= "abcd";
return a;
}

思考了一下, 最好的方式應該是把一個char*傳進去, 直接在function裡面更改指標指向的區域, function回傳void就好。

void str_test(char* result){
sprintf(result, "abcd");
//change result
}

雖然是很小的觀念, 但是影響很大, 指標的使用真的要很小心, 千萬不能讓指標指向的東西突然變成沒意義的東西。

ps. 雖說如此, c++的string卻可以做以下的事情:
#include

string str_test(){
string a="abcd";
return a;
}
改天要去找一下c++ STL的原始碼看看string是怎麼做的, 應該是多了不少個instruction作處理。