C++數據結構學(xué)習在鏈表中鏈入對象

Hugo801122

似乎你也注意到了，不管怎么定義，好像一個(gè)鏈表中的對象都是同一類(lèi)型的。而實(shí)際上，這也是必須的，否則，返回節點(diǎn)中的數據這樣的函數的返回值的類(lèi)型是什么呢？但是，人的要求是無(wú)止境的……（省略本人感慨若干百字）。把不同的對象鏈在一個(gè)鏈表中的目的是為了方便使用，現在一定記住這個(gè)原則，后面的討論都是基于這個(gè)原則的，否則，我們就是技術(shù)狂人了——偏偏實(shí)現一些看起來(lái)不可能的事情。


　　達到這個(gè)目標的原理其實(shí)很簡(jiǎn)單，只要把不同類(lèi)型的對象變成同樣的類(lèi)型就可以了�？聪旅娴慕Y構定義：
　　struct Mobject
　　{
　　void *p;
　　int ObjectType;
　　};
　　將一個(gè)對象鏈入鏈表時(shí)，將指向這個(gè)對象的指針賦給p，同時(shí)記錄對象類(lèi)型。當取得這個(gè)節點(diǎn)的時(shí)候，根據ObjectType的值來(lái)確定p指的對象類(lèi)型，從而還原指針類(lèi)型，也就得到了原來(lái)的對象。

　　后面講到的廣義表實(shí)際上采用的就是這種方法。顯而易見(jiàn)的，這樣的Mobject支持的對象是預先確定的，你將自己維護ObjectType列表，每添加一種類(lèi)型的支持，你需要在ObjectType列表中給出它的替代值，然后在相應的switch(ObjectType)給出這種類(lèi)型的case語(yǔ)句。很煩人是吧，下面給出另一種方法，其實(shí)還是這個(gè)原理，不同的是，把這個(gè)煩人的工作交給編譯器了。

　　還記得前邊強調的原則嗎，為什么我們將不同類(lèi)型的對象放在一個(gè)鏈表中呢？很顯然，我們想達到這樣的一個(gè)效果：比如說(shuō)，我們在一個(gè)鏈表中儲存了三角形，直線(xiàn)，圓等圖形的參數，我們希望對某個(gè)節點(diǎn)使用Draw()方法，就重繪這個(gè)圖形；使用Get()則得到這個(gè)圖形的各個(gè)參數；使用Put()則修改圖形的參數�？梢钥闯�，這些不同的對象實(shí)際上有同樣的行為，只是實(shí)現的方法不同。

C++的多態(tài)性正好可以實(shí)現我們的構想。關(guān)于這方面，請參閱相關(guān)的C++書(shū)籍（我看的是《C++編程思想》）。請看如下的例子：

　　#ifndef Shape_H
　　#define Shape_H

　　class Shape
　　{
　　public:
　　virtual void Input() = 0;
　　virtual void Print() = 0;
　　Shape(){};
　　virtual ~Shape(){};

　　};

　　#endif


　　【說(shuō)明】定義一個(gè)抽象基類(lèi)，有兩個(gè)行為，Input()為輸入圖形參數，Print()為打印圖形參數。圖省事，只是簡(jiǎn)單的說(shuō)明問(wèn)題而已。

　　#ifndef Point_H
　　#define Point_H

　　class Point
　　{
　　public:
　　void Put()
　　{
　　cout << "x坐標為：";
　　cin >> x;
　　cout << "y坐標為：";
　　cin >> y;
　　}

　　void Get()
　　{
　　cout << endl << "x坐標為：" << x;
　　cout << endl << "y坐標為：" << y;
　　}

　　virtual ~Point(){};

　　private:
　　int x;
　　int y;
　　};

　　#endif

　　【說(shuō)明】點(diǎn)的類(lèi)定義與實(shí)現。

　　#ifndef Circle_H
　　#define Circle_H

　　#include "Shape.h"
　　#include "Point.h"
class Circle : public Shape
　　{
　　public:
　　void Input()
　　{
　　cout << endl << "輸入圓的參數";
　　cout << endl << "輸入圓心點(diǎn)的坐標：" << endl;
　　center.Put();
　　cout << endl << "輸入半徑：";
　　cin >> radius;
　　}

　　void Print()
　　{
　　cout << endl << "圓的參數為";
　　cout << endl << "圓心點(diǎn)的坐標：" << endl;
　　center.Get();
　　cout << endl << "半徑：" << radius;
　　}
　　virtual ~Circle(){};

　　private:
　　int radius;
　　Point center;
　　};

　　#endif

　　【說(shuō)明】圓的類(lèi)定義與實(shí)現。繼承Shape類(lèi)的行為。

　　#ifndef Line_H
　　#define Line_H

　　#include "Shape.h"
　　#include "Point.h"

　　class Line : public Shape
　　{
　　public:
　　void Input()
　　{
　　cout << endl << "輸入直線(xiàn)的參數";
　　cout << endl << "輸入端點(diǎn)1的坐標：" << endl;
　　point1.Put();
　　cout << endl << "輸入端點(diǎn)2的坐標：" << endl;
　　point2.Put();
　　}

　　void Print()
　　{
　　cout << endl << "直線(xiàn)的參數為";
　　cout << endl << "端點(diǎn)1的坐標：";
　　point1.Get();
　　cout << endl << "端點(diǎn)2的坐標：";
　　point2.Get();
　　}

　　virtual ~Line(){};

　　private:
　　Point point1;
　　Point point2;
　　};

　　#endif

　　【說(shuō)明】直線(xiàn)類(lèi)的定義與實(shí)現。繼承Shape的行為。

　　#ifndef ListTest_H
　　#define ListTest_H

　　#include
　　#include "List.h"
　　#include "Circle.h"
　　#include "Line.h"
　　void ListTest_MObject()
　　{
　　List a;
　　Shape *p1 = new Circle;
　　Shape *p2 = new Line;
　　p1->Input();
　　p2->Input();
　　a.Insert(p1);
　　a.Insert(p2);
　　Shape *p = *a.Next();
　　p->Print();
　　delete p;
　　a.Put(NULL);
　　p = *a.Next();
　　p->Print();
　　delete p;
　　a.Put(NULL);
　　}
　　#endif

【說(shuō)明】這是測試函數，使用方法是在含有main()的cpp文件頭部加入#include “ListTest.h”，然后調用ListTest_Mobject()。這是一個(gè)簡(jiǎn)單的例子，可以看出，刪除這樣的鏈表節點(diǎn)需要兩個(gè)步驟，先delete鏈表節點(diǎn)data域里指針所指的對象，然后才能刪除鏈表節點(diǎn)。同樣，析構這樣鏈表的時(shí)候，也需要注意這個(gè)問(wèn)題。不然的話(huà)，你的程序運行一次內存就少一點(diǎn)（可能不是這樣，據說(shuō)操作系統在程序中止時(shí)可以回收動(dòng)態(tài)內存，但后面的結論是對的），如果是個(gè)頻繁調用的函數，當運行一段時(shí)間后，你的系統就癱瘓了。所以，使用這樣的鏈表最好是派生一個(gè)新的鏈表類(lèi)，實(shí)現相應的操作。例如這樣：

　　class ShapeList : public List
　　{
　　public:
　　BOOL SL_Remove()
　　{
　　Shape *p = *Get();
　　delete p;
　　return Remove();
　　}
　　};
　　【閑話(huà)】不知你是不是對這樣的語(yǔ)句Shape *p = *a.Next();p->Print();不甚理解，還覺(jué)得有點(diǎn)羅嗦。那你試試這樣的語(yǔ)句*a.Next()->Print();能不能編譯通過(guò)。

ArthurXie