作大數運算時,動態記憶體如何配置??

https://docs.google.com/document/d/1GipxWZXETrLAcb...

這邊是我寫好的Code

基本上沒問題了

但是太大的數字還是跑不出來

還是需要用到動態記憶體配置

那我該如何做

應該用個function就能達到吧

能請大大幫我看一下嗎??

或著大概給我一個 function

我自己再去實作

因為我用到七八個字元陣列

Update:

謝謝妳喔

其實寫成五個是規定的

我們其實第二次作業就是要寫

operator overloading了

所以第一次不會用 assignment operator 來測試

但是這次要實作 = 了

那個,可以說明一下 BigNum & add(BigNum const &);

這行嗎 為什麼使用 reference 以及 const

還有為什麼我們交的時候

copy constructor 是這樣寫 BigNum ( const BigNum &)

const 是在前面

BigNum & add(BigNum const &); 這行 const 我也可以放到前面嗎??

Update 2:

我還是大一新手啦 ><

以前完全沒碰過

我很多習慣還是沒很好,努力改進中

Update 3:

我試著在 add()

裡面再 temp1 = new char[..]

for(){ temp[]='\0' }

怎麼crash了...

Update 4:

ok了

我某些地方重複delete了 = =

Update 5:

像 digitnum 那邊

我是 return digitnum

那我該在什麼地方 delete 它 ??

Update 6:

請問

copy constructor

overload assignment operator =

為了避免的,是相同的問題嗎??

Update 7:

作 overload assignment operator的時候

為什麼都要先check

然後delete在new?

Update 8:

意見七

是在說明我必須先delete在new的原因嗎??

Update 9:

這樣

BigNum & BigNum::operator=(const BigNum & b)

要先 if(&b!=this)

delete[]

new

copy

return *this

2 Answers

Rating
  • 其威
    Lv 7
    9 years ago
    Favorite Answer

    1. 你的加減乘除 (add(), minus(), mul(), divide()) 都有五種版本, 這樣很囉唆...

    你應該是寫五個版本的 constructor 給 BigNum class, 這麼一來編譯器發現可以自動使用 c-tor 把 T 轉成 BigNum 的時候就會自動轉換, 即使沒有, 你也只要手動指定.

    這麼一來你加減乘除每種都只要維護一份實做即可.

    class BigNum {

    public:

    BigNum(char *);

    BigNum(char *, int);

    BigNum(int = 0);

    BigNum(int, int);

    BigNum & add(BigNum const &);

    BigNum & minus(BigNum const &);

    BigNum & mul(BigNum const &);

    BigNum & divide(BigNum const &);

    };

    那麼你就可以寫

    BigNum a;

    a.add(123); // 用 BigNum::BigNum(int)

    a.add("123"); // 用 BigNum::BigNum(char *)

    a.add(BigNum(123, 4)); // 用 BigNum::BigNum(int, int)

    a.add(BigNum("123", 4)); // 用 BigNum::BigNum(char *, int)

    然後, 基本的加減乘除動作, 你應該要多載基本的 + - * / (最好再多做 += -= *= /=) 運算子, 那你就可以寫

    BigNum a;

    a = a + 123;

    a = a + "123";

    a = a + BigNum(123, 4);

    a = a + BigNum("123", 4);

    2. 有動態記憶體配置的 class 必須提供 assignment operator (operator =) 與 copy constructor (BigNum(BigNum const &)).

    否則在你寫

    BigNum a, b;

    a = b;

    的時候, 噢噢~ a 裡面配置的記憶體都洩漏了, 而且改 a 跟 b 變成參照相同位置的記憶體 = =

    更糟糕的是, 當你跳出 a 與 b 的 scope 的時候, 要 ~BigNum() 會 delete [] 一堆東西. 可是由於此時 a 與 b 裡面的指標都是相同位置, 會導致 double free.

    3. 暫存用的變數 (temp1, temp2, retemp, result, input, former, formeruse, digitnum) 應該在用到的時候才配置空間, 而不是跟隨著 class 每個 instance 就配置一份.

    試想, 你只有在執行 BigNum::add() 的時候會用到 temp1, 不考慮平行處理的話就等於同時只會需要一份 temp1. 可是你把他當成 data member, 變成每產生一個 BigNum 就要配置一份這個空間. 如果你宣告一個 BigNum 陣列 (例如 BigNum arr[100000]), 就多浪費了 99999 個 temp1, 更別說那唯一一個真正有用的 temp1 還不是隨時隨地都要用到...

    我們說「程式設計」「程式設計」,寫「程式」以前要先「設計」. 這個紙上談兵的階段是絕對不能省略的.

    你也許該說說看你的程式是怎麼設計的? 有畫流程圖嗎? 有預先設計過資料結構嗎?

    還是說你就是:

    -「喔, 這裡需要一個變數」:宣告一個 temp1 或 temp2

    -「喔, 這裡暫存變數用過了」:弄個迴圈把他清空

    -「喔, 這裡順序反了」:呼叫 reorder() 來調整

    -「嗯, 這個不夠長」:把 current[300] 改成 current]500]...

    - ...

    寫到最後自己都搞不清楚自己寫了什麼.

    如果你有設計過, 應該會發現:

    - 加法: 要預留多一位數的空間. 例如二位數 + 二位數 = 三位數, 三位數 + 四位數 = 五位數... 依此類推.

    - 乘法: 要預留 m + n 位數的空間 (m 位數 * n 位數 = m + n 位數), 例如二位數 * 二位數 = 四位數, 三位數 + 五位數 = 八位數... 依此類推.

    - 減法跟除法總是會越來越小, 所以預留比較長的數字的空間即可.

    2011-04-17 05:20:03 補充:

    補充不下了, 只好寫在意見.

    你在根據加數、被加數、乘數、被乘數的位數來決定和與積的位數的時候, 可以參考以下程式碼 (假設 strlen() 可以用來算位數)

    char * ret = new char[std::max(strlen(a), strlen(b)) + 1]; // 加法用這行

    char * ret = new char[strlen(a) + strlen(b)]; // 乘法用這行

    // 在這裡把運算結果寫入 ret

    // 釋放原本的 current, 然後將結果設定給 current.

    delete [] current;

    current = ret;

    2011-04-17 05:21:36 補充:

    std::max() 請

    #include [algorithm]

    (啞虎騎嬤姿勢佳會把 < 跟 > 符號吃掉, 所以請自己把 [ ] 換成 < >)...

    2011-04-17 13:46:26 補充:

    const 可以寫在型態的前面或後面, 表達的是同樣的意思, 沒有差別.

    只是我習慣把 const 寫在右邊.

    const int a;

    int const a;

    這兩個表達的是完全相同的意思.

    這裡用 reference 是因為, 你的 BigNum class 是個很大的物件 (裡面有一大堆 new 出來的 char[500]).

    每次傳資料都複製一次是一筆不必要的支出 (時間+空間成本).

    所以用 reference 傳, 那麼他實際傳入的是原本的物件, 沒有複製動作.

    可是為了避免你在 add() 裡面不小心改到他, 所以加上 const.

    2011-04-17 13:53:22 補充:

    事實上你的 BigNum::digits() 應該回傳一個 size_t (unsigned int) 而不是 char *.

    size_t BigNum::digits()

    {

    return strlen(current);

    }

    那麼整個 digitnum 就可以從 class 中移除.

    不過這裡沒有看到你的 client code, 所以你要自己做對應的修改.

    2011-04-17 13:56:08 補充:

    發現一個筆誤:

    (x) 三位數 + 五位數 = 八位數

    (o) 三位數 * 五位數 = 八位數

    2011-04-17 14:46:36 補充:

    是.

    預設的 trivial (編譯器幫你產生) 的 copy c-tor 與 assignment operator 是 "bitwize copy".

    例如你有個 class:

    class MyClass {

    int b;

    int c;

    int d;

    };

    當你寫

    MyClass a, b;

    a = b;

    的時候, 編譯器會幫你作:

    a.b = b.b;

    a.c = b.c;

    a.d = b.d;

    2011-04-17 14:49:28 補充:

    可是你的 class 裡面有動態記憶體配置, 所以當他複製 a.current = b.current (與其他變數) 的時候, 會導致指標被覆寫.

    於是

    1. 原本 a 配置的記憶體就丟失了 (再也沒辦法得知原本的記憶體位置)

    2. 現在 a.current 與 b.current 都指到同一塊記憶體 (b.current), 在 a 解構時會 delete [] a.current, 可是 b 解構時又重複 delete [] b.current. 導致 double free error.

    2011-04-17 14:51:59 補充:

    請問你所謂 "先 check, 然後 delete, 再 new" 是什麼意思?

    要先 delete 的原因是, 本來這塊記憶體是要等到 BigNum 解構的時候才會 delete, 可是你現在要把別的位置 assign 給這個 pointer, 那麼將來 delete 的就是你新 new 出來的記憶體了.

    所以必須先 delete 原本配置來的記憶體.

    2011-04-17 14:56:30 補充:

    奧, 這是為了避免你寫出

    BigNum a;

    a = a;

    這種程式碼.

    當自己 assign 給自己的時候, 複製一整排變數是沒有意義的... (浪費時間而已...)

    2011-04-19 02:21:19 補充:

    指標的 const, 請在 * 畫一條直線,

    如果 const 出現在左邊, 表示指標指到的東西是 const.

    如果 const 出現在右邊, 表示指標本身是 const.

    const A * const p;

    在 * 畫一條直線:

    左邊的 const 表示 *p 是 const

    右邊的 const 表示 p 是 const

    寫成 A const * const p; 會是完全相同的意思.

  • 9 years ago

    "bitwize copy"?

    比較有印象這叫 "Shallow Copy"

    2011-04-18 21:49:23 補充:

    BigNum & add(BigNum const &b);

    BigNum & add(const BigNum &b);

    "此時不會有差別!!"

    但在某些狀況下const的意義上是不一樣的喔!

    舉例來說:

    class A

    {

    public:

    void Test1(){cout<<"Success"<

    2011-04-18 21:52:57 補充:

    BigNum & add(BigNum const &);

    BigNum & add(const BigNum &);

    在此時沒有差別!!

    但const的位置在某些情況下意義是不一樣的喔!

    2011-04-18 21:54:45 補充:

    舉例來說:

    class A

    {

    public:

    void Test1() { cout < < "Success" < < endl ; }

    void Test0() const { cout < < "Success" < < end l; }

    };

    2011-04-18 21:55:09 補充:

    void f(const A* &b)

    {

    b->Test0();

    //b->Test1(); //不能呼叫非const的function

    b = new A();

    }

    void f1(A* const &b)

    {

    b->Test0();

    b->Test1();

    //b = new A(); //不能改變b值

    }

    int main(int argc, char *argv[])

    {

    A *b;

    A *c;

    }

    2011-04-18 21:58:20 補充:

    此時

    void f1(A* const &b)是保護reference b指標的指向不受更改

    void f(const A* &b)是保護reference b指標的指向的物件不受更改

    此情況便該寫成

    void f(const A* const &b)

    是保護reference b指標的指向的物件不受更改

    且保護reference b指標的指向的物件不受更改

Still have questions? Get your answers by asking now.