Pages

2011年6月14日 星期二

[研究] 一個文件壓縮軟體Beta

      這是我寫的一個作業。
      我寫了一個可以壓縮文件的軟體,只支援 Ascii 碼文件。目前測試沒有Bug(只要文件內容都是嚴謹的ASCII碼的話)。
本程式功能:將ASCII文件壓縮為一個壓縮檔,檔案夠大時,文件大小可以壓縮約為原檔案的60%。
本程式執行環境為unix-liked系統。

本程式在freebsd下跑完全正常,但在windows系統下,解壓縮回來偶爾會有幾個字有顯示的問題。
使用方法:
輸入 compress [fileName]:可以將當前資料夾內的 [fileName] 檔案壓縮名為output.ufp的檔案,並存放在當前目錄下。

輸入 decompress可以將當前目錄下名為output.ufp檔解壓回原文件,並命名為decompress.txt,並存放在當前目錄下。
輸入 /help:可以查看指令。
之前的下載位置的檔案有問題,現在更新了:
免費檔案下載位置:http://www.sendspace.com/file/m9oqrc

2011年6月9日 星期四

[C++] 動態陣列擴充時,容易犯錯的指標傳遞

        在動態擴充陣列大小時,如果透過很多函式來傳遞,要注意指標的問題。
        舉例來說,寫一個函式Expand用來擴充陣列,需傳給此函式一個指標代表陣列,然而如果宣告參數時只寫一個星號,則Expand內部會自動產生一個新的指標(假設叫做A)並將傳遞進來的指標(假設叫做B)內所存的位址複製一份在新的指標變數A內。
        在這種情況下要注意,如果在Expand內將A指標指向一個新的位址,那麼就指標B並沒有指向新的位址,這是容易讓程式當掉的地方。
        因此Expand可以在宣告參數時,給予參數兩個星號,如此傳遞進來的,就是B指標的位址,因此只要更改此位址指向的那個位置,就可以把原來傳遞進來的陣列更改。
用言語表達此觀念似乎不太清楚,用實例來表達如下:
以下是我打的一個範例程式碼:
//////////////////////////////////////////////////////
#include<iostream>
using namespace std;
void Expand1(int **arrReceive,int &size,int key)
{
    int *old = *arrReceive;
    *arrReceive = new int [size+1];
    for(int i=0;i<size;i++)
    {
        (*arrReceive)[i] = old[i];
    }
    (*arrReceive)[size] = key;
    size++;
    delete []old;
}
int *Expand2(int *arrReceive,int &size,int key)
{
    int *newArr = new int [size+1];
    for(int i=0;i<size;i++)
    {
        newArr[i] = arrReceive[i];
    }
    newArr[size] = key;
    delete []arrReceive;
    size++;
    return newArr;
}
void changeArr(int **arrReceive,int &size)
{
    Expand1(&(*arrReceive),size,123);
    (*arrReceive) = Expand2(*arrReceive,size,456);
}
int main()
{
    int size = 3;
    int *a = new int [size];  //不能寫int a[] = {1,2,3}; 會有問題。
    cout << "original array:" << endl;
    for(int i=0;i<size;i++)
    {
        a[i] = i;
        cout << " " << a[i];
    }
    cout << endl;
    changeArr(&a,size);
    cout << "after change:" << endl;
    for(int i=0;i<size;i++)
    {
        cout << " " << a[i];
    }
    cout << endl;
}
//////////////////////////////////////////////////////////
執行結果>>
original array:
0 1 2
after change:
0 1 2 123 456


Expand1跟Expand2的都可以安全的擴充陣列。
1.   Expand1是:將指向原陣列第一個元素的指標,這個指標有一個位址,把這個位址丟給Expand1來接,Expand1會產生一個新的指標並把這個位址指向的位址做更改。因此元陣列整個都被更改了。
2.   Expand2是直接在Expand2函式內產生一個新的陣列指標,並把舊的陣列指標指向的地方delete,回傳新的指標給原指標接收,也可以擴充陣列。

2011年6月6日 星期一

[演算法] heap sort

以下的心得,以Max-heap為例:
1.   max heap的特性:
      一個node的parent的索引值是這個node的索引值除以2之後取floor。一個node的左邊child是這個node索引值乘以2,右邊的child的索引值是當前node索引值乘以2之後再加上1。
     因此可以定義macro:
     #define Parent(i) i/2
     #define Left(i) 2*i
     #define Right(i) (2*i)+1
2.   以下方法,可以很快地寫出一個heap sort:
      首先迅速建立heap,要維持一個heap,只須有2個部分:
      第一部份,要有一個函式可以調整任意一個node往下樹的下方移動,使整個樹維持max heap的特性。做到這一點只要比較這個node跟其兩個child三者之中誰最大,將要調整的node與其child中最大的數值調換。如此將node往下調整移動後,再將剛剛調換過的child那個位置,傳入自己這個函式,遞迴呼叫自己,繼續從那個位置往下調整。
      第二部分,要建立一個heap,需要定義這個heap的大小,整個heap中有幾個node一定要知道。將整個陣列視為heap時:
heap
   
這樣子的排法, heap圖內的索引值,注意是從1開始算,在這種情況下,最大的索引值就是整個陣列的size。在建立heap時,要從索引值為 (size/2) 的那個node,開始往索引值小的node去將每個node檢查並往下調整,使整個tree有max-heap之特性。索引值大於size/2的那些node,通通都是樹葉(leaf),樹葉不用調整。
由以上的觀念可以迅速建立heap。
3.   用heap來排序,就是heap sort。非常容易,只是將root取出,然後把最後一個node(最後一片樹葉),摘下來貼到root的位置,然後從root往下調整,使整個heap維持max-heap的特性。注意此時要更新size的大小,將整個heap的size減1。

[C++] token

將string類別切成token的方式我學到的有兩種:
1.    while( getline(inputFile,line))
       {
           istringstream token(line);
           string word;
           while(token >> word)
           {
               //……
           }
       }
       //此為使用istringstream。
2.   使用stringstream:
      string str = "0 1 2 3 4 5";
      stringstream ss(str);
      string token;
      while(1)
      {
          getline(ss, token, ' ');   //指定用空白隔開,亦可指定其他分隔字元
          if (ss.fail())
          break;

          istringstream convert(token);
                 //用istringstream可以將字串轉成整數或其他型態數字
                 //用stringstream也可用同樣方法將string轉成int。
          int tmp = 0;
          convert >> tmp;
          cout << tmp << endl;
      }
      執行結果:
      0
      1
      2
      3
      4
      5

[演算法] MergeSort跟QuickSort的程式架構

1.   Merge Sort的精神就是把陣列切割。所以演算法如下:
      以下的start、mid、end都是陣列的索引值。
      void merge(int *data, int start, int mid, int end)
      {
            這個函式做合併的動作。
      }
      void mergeSort(int *data, int start, int end)
      {
            如果start == end,就return;
            //這個函式做切割的動作。
            (i)   先切成:mid = (start+end)/2,這代表一個陣列切成start到mid跟mid到end。
            (ii)  把start到mid的部分遞迴給自己切。mid+1到end遞迴給自己切。
            (iii) 把start到end部分陣列送給merge合併。
       }
2.   Quick Sort:
      QS
把以上這個圖所做的動作寫在一個函式裡(假設此函式叫做A),在這個函式的最後回傳個索引值:i+1。
這樣就可以在QuickSort函式內利用遞迴,以下是QuickSort函式類內容架構:
   Quick Sort終止條件:if( indexLeft >= indexRight) return;
   int cut = A(data, indexLeft, indexRight);
   QuickSort(data, indexLeft, cut-1);
   QuickSort(data, cut+1, indexRight);

[C++] 讀取文字檔

不同文字檔案格式有不同的讀檔寫法。在此我整理我常用的讀檔方式,遇到不同的文字檔案格式,可以快速地使用以下不同的方法取得文字檔內的資料。
    (1) include<fstream>
         include<sstream>
         以上這兩個標頭檔先include起來。
    (2) 以下是我常用的標準讀取文字檔案的寫法:
          readData()
          {
               ifstream inputFile;
               inputFile.open(“input.txt”,ifstream::in);  //允許input operation。
               string line;
               int lineNumber = 0;
                                                            // 從inputFile,get一段文字到line。
                                                            // 將string命名為line有好處,讓使用
                                                            // getline時不會用錯。
               while(getline(inputFile,line)
               {
                     lineNumber++;
                     cout << lineNumber << “ “;
                     istringstream token(line);
                     string word;
                     while(token >> word)
                     {
                           cout << word << " ";
                     }
                     cout << endl;
               }
          }
         
          這個函式可以切token,並在每一行之前加上行號。
    (3)  getline(cin,line); //會讀入一整行,包括空白,遇到 '\n' 停止讀取。
           cin >> line;        //停止讀取於空白鍵。
           getline(cin,line,’?');   //代表讀到 '?' 就停止讀取。
           getline不會讀到 '\n'。
    (4)   string str = “12345”;
           int len = str.length();     //回傳幾個字。len = 5;
           string tmp = str.substr(0,2);  //從第0個位置取兩個字符。即 "12"。
    (5)  檔案開啟:
           ifstream inputFile;
           inputFile.open(“input.txt”);   //如此檔案內容不會被洗掉
           int oneNumber,anotherNumber;
           inputFile >> oneNumber >> anotherNumber;
           //從檔案讀兩個數設給oneNumber跟anotherNumber。
    (6)  ofstream開檔,如果沒有設ios::app,則檔案內容會被洗掉。

2011年6月1日 星期三

[Matlab] 匿名函數筆記

1.   匿名函數最簡單的使用方法,就是像數學表示函數一樣,將函數的因變數跟自變數表示出來:
   f = @(x,y) 2*x+6*y ;
   f([2 4], [3 6])
   執行結果:
   ans =
          22     44
2.   f = {@(x) x+3, @(y) y+1}
      %如此可以將f視為一個函數陣列。
      f{1}(2)   %第一個column的x代2,所以ans為5。
      f{2}(10) %第二個column的y代10,得到ans為11。
3.  以下是我寫的一個算函數下方面積的例子:
     clc,clear all
     f = @(x) 2*x;
    x = [0:0.01:2];
    fplot(f,[0 2]);

    ts = (2/(length(x)-1));
    tmp = 0;
    for i=1:length(x)-1,
           tmp = tmp + (f(x(i)))*ts;
    end;
    tmp

    執行結果>>tmp = 3.9800
    (執行環境:Octave)