|
我們知道，數(shù)組式計算機根據(jù)事先定義好的數(shù)組類型與長度自動為其分配一連續(xù)的存儲單元，相同數(shù)組的位置和距離都是固定的，也就是說，任何一個數(shù)組元素的地址都可一個簡單的公式計算出來，因此這種結(jié)構(gòu)可以有效的對數(shù)組元素進行隨機訪問。但若對數(shù)組元素進行插入和刪除操作，則會引起大量數(shù)據(jù)的移動，從而使簡單的數(shù)據(jù)處理變得非常復雜，低效。 為了能有效地解決這些問題，一種稱為“鏈表”的數(shù)據(jù)結(jié)構(gòu)得到了廣泛應(yīng)用。 1． 鏈表概述 鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點是用一組任意的存儲單元（可以是連續(xù)的，也可以是不連續(xù)的）存放數(shù)據(jù)元素。 鏈表中每一個元素成為“結(jié)點”，每一個結(jié)點都是由數(shù)據(jù)域和指針域組成的，每個結(jié)點中的指針域指向下一個結(jié)點。Head是“頭指針”，表示鏈表的開始，用來指向第一個結(jié)點，而最后一個指針的指針域為NULL(空地址)，表示鏈表的結(jié)束。 可以看出鏈表結(jié)構(gòu)必須利用指針才能實現(xiàn)，即一個結(jié)點中必須包含一個指針變量，用來存放下一個結(jié)點的地址。 實際上，鏈表中的每個結(jié)點可以用若干個數(shù)據(jù)和若干個指針。結(jié)點中只有一個指針的鏈表稱為單鏈表，這是最簡單的鏈表結(jié)構(gòu)。 再c++中實現(xiàn)一個單鏈表結(jié)構(gòu)比較簡單。例如，可定義單鏈表結(jié)構(gòu)的最簡單形式如下 struct Node { int Data; Node*next; }; 這里用到了結(jié)構(gòu)體類型。其中，*next是指針域，用來指向該結(jié)點的下一個結(jié)點；Data是一個整形變量，用來存放結(jié)點中的數(shù)據(jù)。當然，Data可以是任何數(shù)據(jù)類型，包括結(jié)構(gòu)體類型或類類型。 在此基礎(chǔ)上，我們在定義一個鏈表類list，其中包含鏈表結(jié)點的插入，刪除，輸出等功能的成員函數(shù)。 class list { Node*head; public: list(){head=NULL;} void insertlist(int aDate,int bDate);//鏈表結(jié)點的插入 void Deletelist(int aDate);//鏈表結(jié)點的刪除 void Outputlist();//鏈表結(jié)點的輸出 Node*Gethead(){return head;} }; 2． 鏈表結(jié)點的訪問 由于鏈表中的各個結(jié)點是由指針鏈接在一起的，其存儲單元文筆是連續(xù)的，因此，對其中任意結(jié)點的地址無法向數(shù)組一樣，用一個簡單的公式計算出來，進行隨機訪問。只能從鏈表的頭指針（即head）開始，用一個指針p先指向第一個結(jié)點，然后根據(jù)結(jié)點p找到下一個結(jié)點。以此類推，直至找到所要訪問的結(jié)點或到最后一個結(jié)點（指針為空）為止。 下面我們給出上述鏈表的輸出函數(shù)； void list::outputlist() { Node*current=head; while(current!=NULL) { cout<<current->Data<<" "; current=current->next; } cout<<endl; } 3． 鏈表結(jié)點的插入 如果要在鏈表中的結(jié)點a之前插入結(jié)點b，則需要考慮下面幾點情況。 （1） 插入前鏈表是一個空表，這時插入新結(jié)點b后。 （2） 若a是鏈表的第一個結(jié)點，則插入后，結(jié)點b為第一個結(jié)點。 （3） 若鏈表中存在a,且不是第一個結(jié)點，則首先要找出a的上一個結(jié)點a_k，然后使a_k的指針域指向b，在令b的指針域指向a，即可完成插入。 （4） 如鏈表中不存在a，則插在最后。先找到鏈表的最后一個結(jié)點a_n，然后使a_n的指針域指向結(jié)點b，而b指針的指針為空。 以下是鏈表類的結(jié)點插入函數(shù)，顯然其也具有建立鏈表的功能。 void list::insertlist(int aDate,int bDate) //設(shè)aDate是結(jié)點a中的數(shù)據(jù)，bDate是結(jié)點b中的數(shù)據(jù) { |
