C++數據結構學習：在鏈表中鏈入對象

　　似乎你也注重到了，不管怎麼定義，似乎一個鏈表中的對象都是同一類型的。而實際上，這也是必須的，否則，返回節點中的數據這樣的函數的返回值的類型是什麼呢？但是，人的要求是無止境的……（省略本人感慨若干百字）。 <!-- frame contents --> <!-- /frame contents --> 把不同的對象鏈在一個鏈表中的目的是為了方便使用，現在一定記住這個原則，後面的討論都是基於這個原則的，否則，我們就是技術狂人了——偏偏實現一些看起來不可能的事情。
　　
　　 　　達到這個目標的原理其實很簡單，只要把不同類型的對象變成同樣的類型就可以了。看下面的結構定義：
　　 　　strUCt Mobject
　　 　　{
　　 　　void *p;
　　 　　int ObjectType;
　　 　　};
　　 　　將一個對象鏈入鏈表時，將指向這個對象的指針賦給p，同時記錄對象類型。當取得這個節點的時候，根據ObjectType的值來確定p指的對象類型，從而還原指針類型，也就得到了原來的對象。
　　
　　 　　後面講到的廣義表實際上采用的就是這種方法。顯而易見的，這樣的Mobject支持的對象是預先確定的，你將自己維護ObjectType列表，每添加一種類型的支持，你需要在ObjectType列表中給出它的替代值，然後在相應的switch(ObjectType)給出這種類型的case語句。很煩人是吧，下面給出另一種方法，其實還是這個原理，不同的是，把這個煩人的工作交給編譯器了。
　　
　　 　　還記得前邊強調的原則嗎，為什麼我們將不同類型的對象放在一個鏈表中呢？很顯然，我們想達到這樣的一個效果：比如說，我們在一個鏈表中儲存了三角形，直線，圓等圖形的參數，我們希望對某個節點使用Draw()方法，就重繪這個圖形；使用Get()則得到這個圖形的各個參數；使用Put()則修改圖形的參數。可以看出，這些不同的對象實際上有同樣的行為，只是實現的方法不同。
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　C++的多態性正好可以實現我們的構想。關於這方面，請參閱相關的C++書籍（我看的是《C++編程思想》）。請看如下的例子：
　　
　　 　　#ifndef Shape_H
　　 　　#define Shape_H
　　 　　
　　 　　class Shape
　　 　　{
　　 　　public:
　　 　　virtual void Input() = 0;
　　 <!-- frame contents --> <!-- /frame contents --> 　　virtual void Print() = 0;
　　 　　Shape(){};
　　 　　virtual ~Shape(){};
　　 　　
　　 　　};
　　 　　
　　 　　#endif
　　
　　
　　 　　【說明】定義一個抽象基類，有兩個行為，Input()為輸入圖形參數，Print()為打印圖形參數。圖省事，只是簡單的說明問題而已。
　　
　　 　　#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
　　
　　 　　【說明】點的類定義與實現。
　　
　　 　　#ifndef Circle_H
　　 　　#define Circle_H
　　
　　 　　
　　 　　#include "Shape.h"
　　 　　#include "Point.h"
　　 　　
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　class Circle : public Shape
　　 　　{
　　 　　public:
　　 　　void Input()
　　 　　{
　　 　　cout << endl << "輸入圓的參數";
　　 　　cout << endl << "輸入圓心點的坐標：" << endl;
　　 　　center.Put();
　　 　　cout << endl << "輸入半徑：";
　　 <!-- frame contents --> <!-- /frame contents --> 　　cin >> radius;
　　 　　}
　　 　　
　　 　　void Print()
　　 　　{
　　 　　cout << endl << "圓的參數為";
　　 　　cout << endl << "圓心點的坐標：" << endl;
　　 　　center.Get();
　　 　　cout << endl << "半徑：" << radius;
　　 　　}
　　 　　virtual ~Circle(){};
　　 　　
　　 　　private:
　　 　　int radius;
　　 　　Point center;
　　 　　};
　　 　　
　　 　　#endif
　　
　　 　　【說明】圓的類定義與實現。繼續Shape類的行為。
　　
　　 　　#ifndef Line_H
　　 　　#define Line_H
　　 　　
　　 　　#include "Shape.h"
　　 　　#include "Point.h"
　　 　　
　　 　　class Line : public Shape
　　 　　{
　　 　　public:
　　 　　void Input()
　　 　　{
　　 　　cout << endl << "輸入直線的參數";
　　 　　cout << endl << "輸入端點1的坐標：" << endl;
　　 　　point1.Put();
　　 　　cout << endl << "輸入端點2的坐標：" << endl;
　　 　　point2.Put();
　　 　　}
　　 　　
　　 　　void Print()
　　 　　{
　　 　　cout << endl << "直線的參數為";
　　 　　cout << endl << "端點1的坐標：";
　　 　　point1.Get();
　　 　　cout << endl << "端點2的坐標：";
　　 　　point2.Get();
　　 　　}
　　 　　
　　 　　virtual ~Line(){};
　　 　　
　　 　　private:
　　 　　Point point1;
　　 　　Point point2;
　　 　　};
　　 　　
　　 　　#endif
　　
　　 　　【說明】直線類的定義與實現。繼續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
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　【說明】這是測試函數，使用方法是在含有main()的cpp文件頭部加入#include “ListTest.h”，然後調用ListTest_Mobject()。這是一個簡單的例子，可以看出，刪除這樣的鏈表節點需要兩個步驟，先delete鏈表節點data域裡指針所指的對象，然後才能刪除鏈表節點。 <!-- frame contents --> <!-- /frame contents --> 同樣，析構這樣鏈表的時候，也需要注重這個問題。不然的話，你的程序運行一次內存就少一點（可能不是這樣，據說操作系統在程序中止時可以回收動態內存，但後面的結論是對的），假如是個頻繁調用的函數，當運行一段時間後，你的系統就癱瘓了。所以，使用這樣的鏈表最好是派生一個新的鏈表類，實現相應的操作。例如這樣：
　　
　　
　　 　　class ShapeList : public List
　　 　　{
　　 　　public:
　　 　　BOOL SL_Remove()
　　 　　{
　　 　　Shape *p = *Get();
　　 　　delete p;
　　 　　return Remove();
　　 　　}
　　 　　};
　　 　　【閒話】不知你是不是對這樣的語句Shape *p = *a.Next();p->Print();不甚理解，還覺得有點羅嗦。那你試試這樣的語句*a.Next()->Print();能不能編譯通過。
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或