本文是「跟著 Arden 學演算法」系列的第一天筆記,主題是一級 ADT(first-class data type)。
我們前一天實作的 ADT 有這樣的特點:它只用來表示一個物件。我們可以像使用 int 一樣使用它——宣告一個整數寫作 int m;類似的,也能宣告一個堆疊 stack sta。可惜 C 語言不支援運算子重載,我們無法為自訂 ADT 賦予 *、-、+ 這類運算,只能用函式來實作。
所謂一級 ADT,就是這樣的東西:它可以有多個實例,我們能用它來宣告變數,並為這些變數賦予實例的值。
複數由實部與虛部兩部分組成,我們用兩個浮點數來表示資料,並提供初始化、存取實部與虛部、乘法等操作。
//file name : complex.h
typedef struct complex
{
float re;
float im;
};
complex init(float, float);
float re(complex);
float im(complex);
complex mult(complex, complex);
//file name : complex.c
#include <stdlib.h>
#include <complex.h>
complex init(float m_re, float m_im)
{
complex c;
c.re = m_re;
c.im = m_im;
return c;
}
float re(complex m_c) { return m_c.re; }
float im(complex m_c) { return m_c.im; }
complex mult(complex fc, complex sc)
{
complex c;
c.re = fc.re * sc.re - fc.im * sc.im;
c.im = fc.re * sc.re + fc.im * sc.im;
return c;
}
試著使用一下,一切都能正常運作。但總覺得還差了點什麼。讓我們回頭想想:辛辛苦苦分成兩個檔案來實作一個複數,目的究竟是什麼?答案是抽象。而抽象的手段就是資料封裝——可我們真的封裝好了嗎?還沒有。
complex.h 中把結構定義整個攤了出來,等於讓所有引用它的使用者都能看見內部欄位。這樣一來,使用者根本不必呼叫 init(),直接寫 c1.re = 2; c1.im = 3; 就能達到目的,前面建立介面的努力就白費了。更重要的是,日後程式結構一旦改變,這些直接操作資料的寫法會讓維護變得棘手,後果嚴重。
最簡便的做法,是在 complex.h 中看不見結構的具體定義,但仍需宣告它。找個替代品——用不完整的型別指標:
//file name : complex.h typedef struct complex *Comp; complex init(float, float); float re(Comp); float im(Comp); complex mult(Comp, Comp);
再把結構定義移到實作檔中:
//file name : complex.c
#include <stdlib.h>
#include <complex.h>
struct complex { float re; float im; };
Comp init(float m_re, float m_im)
{
Comp c = malloc(sizeof *c);
c->re = m_re;
c->im = m_im;
return c;
}
float re(Comp m_c) { return m_c->re; }
float im(Comp m_c) { return m_c->im; }
Comp mult(Comp fc, Comp sc)
{
return init(re(fc) * re(sc) - im(fc) * im(sc),
re(fc) * re(sc) + im(fc) * im(sc));
}
這樣一來,使用者只能透過 init、re、im、mult 這些介面來操作複數,再也無法直接碰觸內部欄位,封裝才算真正到位。今天可說收穫頗豐,其中「隱藏實作、只暴露介面」的理念,值得時刻提醒自己如何設計並發布自己的 ADT。
(附註:這個版本每次呼叫都配置記憶體,卻尚未妥善 free,存在記憶體洩漏的問題,實際使用時仍需補上適當的釋放機制。)