鏈表及其基本操作

1、VC+程序設(shè)計(jì)程序設(shè)計(jì)7.2 鏈表與鏈表的基本操作版本號(hào)：V2007.03-07.06 鏈表是一種動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的結(jié)構(gòu)。最簡(jiǎn)單的鏈表稱為單向鏈表，如圖所示： 1249A1356B1475C1021DNULLHead 1249 1356 1475 1021特點(diǎn)：1。頭指針變量head, 它存放一個(gè)地址，用于指向一個(gè)元素。鏈表中的一個(gè)元素稱為結(jié)點(diǎn)。2。每個(gè)結(jié)點(diǎn)至少應(yīng)包含兩個(gè)部分：一為用戶需要的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址。 3?！氨砦病?的地址部分放一個(gè)“Null”（表示“空地址”）。表示鏈表的最后一個(gè)元素，該元素不再指向其它元素。 簡(jiǎn)單鏈表簡(jiǎn)單鏈表 鏈表中各元素在內(nèi)存中一般是不連續(xù)的。要找

2、某一元素，必須先找到上一個(gè)元素，根據(jù)它提供的下一個(gè)元素的地址才能找到下一個(gè)元素?？梢?，如果不提供頭指針，則整個(gè)鏈表都無法訪問。 由于鏈表的每個(gè)結(jié)點(diǎn)中都必須包含一個(gè)指向下一結(jié)點(diǎn)的指針變量和一個(gè)結(jié)點(diǎn)數(shù)據(jù)，因此可以用前面介紹的結(jié)構(gòu)體類型的變量實(shí)現(xiàn)。 在定義一個(gè)結(jié)構(gòu)體類型時(shí)，包含若干成員，而其中成員之一必須是一個(gè)指針變量，該指針變量用于指向下一個(gè)具有相同結(jié)構(gòu)體類型的變量-“結(jié)點(diǎn)”。 struct studentint num;int score;student *next; 建立鏈表一般包括以下幾個(gè)步驟：1、建立鏈表頭 head2、使用動(dòng)態(tài)內(nèi)存分配技術(shù)，在內(nèi)存中動(dòng)態(tài)建立鏈表中的各個(gè)結(jié)點(diǎn)，并使鏈表頭he

3、ad指針next指向第一結(jié)點(diǎn)，同時(shí)，每個(gè)結(jié)點(diǎn)的next指針逐一指向下一結(jié)點(diǎn)。3、使鏈尾結(jié)點(diǎn)的指針next指向空結(jié)點(diǎn)NULL。 例：寫一函數(shù)建立一個(gè)有3名學(xué)生數(shù)據(jù)（學(xué)號(hào)、成績(jī)）的單向鏈表(以輸入num為0表示結(jié)束輸入)。struct studentint num;int score;student *next;student *head, *p1, *p2;1104189.5next1104390next1104785NULLnumscorenext$7.1 $7.1 建立鏈表建立鏈表headp1p21104189nextn=1if(p1-num!=0)head=p1=p2=new studen

4、t;headp1p21104189nextn=2p1 = new studentif(p1-num!=0)P2-next=p1;1104390nextp1headp1p21104189next1104390nextp2=p1headp1p21104189next1104390next1104785nextn=3p1=new student;headp1p21104189next1104390next1104785nextn=3if(p1-num!=0)p2-next=p1p2=p1headp1p21104189.5next1104390next1104785NULLn=4p1=new stud

5、ent;if(p1-num = 0)p2-next=NULL;return(head);00/建立鏈表的C+語言函數(shù)如下：student *creat( void )student *head,*p1,*p2; number=0; /結(jié)點(diǎn)記數(shù)器,全局變量head=NULL p1=p2=new student;/產(chǎn)生第一個(gè)結(jié)點(diǎn) coutp1-num;coutp1-score; while(p1-num!=0) number+; /結(jié)點(diǎn)記數(shù)器if(number=1) head=p1;else p2-next=p1;p2=p1;p1=new student; /產(chǎn)生下一個(gè)結(jié)點(diǎn) coutp1-num;

6、coutp1-score; p2-next=NULL;/鏈表尾delete p1; return(head); 要輸出鏈表，首先要知道鏈表頭的地址，然后用一個(gè)指針指向第一個(gè)結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的數(shù)據(jù)成員p-num和p-score，再使p指向下一結(jié)點(diǎn)，再輸出，直到鏈表的尾結(jié)點(diǎn)p-next=NULL。程序如下：void print(student *head) struct student *p=head; coutn Now,There are number records: n; if(head !=NULL) do coutnumtscorenext; while(p!=NULL);輸出鏈表輸出

7、鏈表 從一個(gè)鏈表中刪去一個(gè)結(jié)點(diǎn)，并不一定是真正從內(nèi)存中把它抹掉，而是把它從鏈表中分離開來，即改變鏈接關(guān)系。 headp11104189next1104390next1104785NULL初始 p1=head; 對(duì)鏈表的刪除操作對(duì)鏈表的刪除操作headp1p21104189next1104390next1104785NULL如果不是要?jiǎng)h除的結(jié)點(diǎn)if(p1-num!=num) p2=p1; p1=p1-next;如果找到某一結(jié)點(diǎn)是要?jiǎng)h除的結(jié)點(diǎn)，還要區(qū)分兩種情況：要?jiǎng)h除的是第一個(gè)結(jié)點(diǎn)；要?jiǎng)h除的不是第一個(gè)結(jié)點(diǎn)；此處還要考慮空表的情況。headp1110418911043901104785NULL如果刪

8、除的是第一個(gè)結(jié)點(diǎn)if(p1=head)head=p1-next;headp1p21104189next1104390next1104785NULL如果刪除的不是第一個(gè)結(jié)點(diǎn)else p2-next = p1-next;student *del(student *head, long num) student *p1,*p2; if(head = NULL) coutnum & p1-next!=NULL) p2=p1; p1=p1-next; if(num=p1-num) /找到要?jiǎng)h除的結(jié)點(diǎn)找到要?jiǎng)h除的結(jié)點(diǎn) if(p1=head) /是第一個(gè)結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn) head = p1-next

9、; delete p1; else p2-next = p1-next; delete p1; /不是第一個(gè)結(jié)點(diǎn)不是第一個(gè)結(jié)點(diǎn) cout刪除刪除: numn; number=number-1;/結(jié)點(diǎn)記數(shù)器減一結(jié)點(diǎn)記數(shù)器減一 else /沒有要?jiǎng)h除的結(jié)點(diǎn)沒有要?jiǎng)h除的結(jié)點(diǎn)coutnumnext;delete p1;headp11104189next1104390next1104785NULL初始 p1=head;釋放鏈表的結(jié)點(diǎn)空間headp1110418911043901104785NULL初始 p1=p2=head; p0=&stud;89102p2p0設(shè)已有的鏈表中各結(jié)點(diǎn)的成員是按學(xué)號(hào)

10、由小到大順序排列的。 對(duì)鏈表的插入操作對(duì)鏈表的插入操作headp1110418911043901104785NULLif(p0-num p1-num) & ( p1-next!=NULL) p2=p1; p1=p1-next; /查找要插入結(jié)點(diǎn)的位置查找要插入結(jié)點(diǎn)的位置89102p2p0headp11104189next1104390next1104785NULL找到插入位置后，區(qū)分下列情況：1.插入的是頭結(jié)點(diǎn)；2.插入的是鏈表尾；3.插入的是中間位置；11042nextp2p03. 插入的是中間位置；if(p0-num num) p2-next=p0; p0-next=p1;head

11、p11104189.511043901104785NULLif(p1=head) head=p0; p0-next=p1;11042p01.插入的是頭結(jié)點(diǎn)；headp11104189.511043901104785&（p0-num p1-num）if(p1-next = NULL) p1-next=p0; p0-next =NULL;11042NULLp02.插入的是鏈表尾；student *insert(student *head, student *stud) student *p0,*p1,*p2; p1=head; p0=stud; if(head=Null)/原為空鏈表原為空

12、鏈表 head=p0; p0-next=Null; else while(p0-num p1-num)&(p1-next != Null) /查找插入位置查找插入位置p2=p1; p1=p1-next; ;/插入結(jié)點(diǎn)的函數(shù)插入結(jié)點(diǎn)的函數(shù)insert如下：如下：if(p0-num num)/找到插入位置找到插入位置 if(p1=head)/插入的是頭結(jié)點(diǎn)插入的是頭結(jié)點(diǎn) head=p0; p0-next=p1; else p2-next=p0; p0-next=p1;/插入的是中間位置插入的是中間位置 else if(p1-next = Null) /沒有找到插入位置并且已經(jīng)到鏈尾沒有找到

13、插入位置并且已經(jīng)到鏈尾 p1-next=p0; p0-next=Null; number=number+1; return(head);#include#define Null 0int num;struct studentint num;int score;student *next;void main( void )student *head;int num;head=creat( );print(head);coutnum;head=del(head,num);print(head);student stud;cout輸入要插入的節(jié)點(diǎn)：輸入要插入的節(jié)點(diǎn)：; coutstud.num;co

14、utstud.score;head=insert(head,&stud);print(head);單鏈表類型模板單鏈表類型模板【例例7.4_h】單鏈表的結(jié)點(diǎn)采用類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)單鏈表的結(jié)點(diǎn)采用類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)函數(shù)作為成員函數(shù)。包括：清空鏈表、查找數(shù)據(jù)、計(jì)算表長(zhǎng)、打印函數(shù)作為成員函數(shù)。包括：清空鏈表、查找數(shù)據(jù)、計(jì)算表長(zhǎng)、打印數(shù)據(jù)、向前生成鏈表、向后生成鏈表、按升序生成鏈表等。數(shù)據(jù)、向前生成鏈表、向后生成鏈表、按升序生成鏈表等。templateclass List;templateclass Node T info; /數(shù)據(jù)域數(shù)據(jù)域 Node *link; /指

15、針域指針域public: Node(); /生成頭結(jié)點(diǎn)的構(gòu)造函數(shù)生成頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T & data); /生成一般結(jié)點(diǎn)的構(gòu)造函數(shù)生成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(Node* p); /在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn) Node* RemoveAfter(); /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) friend class List; /以以List為友元類，為友元類，List可直接訪問可直接訪問Node的私有函數(shù)的私有函數(shù);template Node:Node()link=NULL;template Node:

16、Node(const T & data)info=data;link=NULL;templatevoid Node:InsertAfter(Node* p)p-link=link;link=p;結(jié)點(diǎn)類成員函數(shù)結(jié)點(diǎn)類成員函數(shù):infolinkinfolinkinfolinkp(1)(2)當(dāng)前結(jié)點(diǎn)待插入結(jié)點(diǎn)templateNode* Node:RemoveAfter()Node* tempP=link;if(link=NULL) tempP=NULL; /已在鏈尾已在鏈尾,后面無結(jié)點(diǎn)后面無結(jié)點(diǎn)else link=tempP-link;return tempP;infolinkinfolin

17、kinfolink當(dāng)前結(jié)點(diǎn)tempPlink=tempP-linktemplateclass List Node *head,*tail; /鏈表頭指針和尾指針鏈表頭指針和尾指針public: List(); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表空鏈表) List(); /析構(gòu)函數(shù)析構(gòu)函數(shù) void MakeEmpty(); /清空一個(gè)鏈表，只余表頭結(jié)點(diǎn)清空一個(gè)鏈表，只余表頭結(jié)點(diǎn) Node* Find(T data); /搜索數(shù)據(jù)域與搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length(); /計(jì)算單鏈表長(zhǎng)度計(jì)算單鏈表長(zhǎng)度 void

18、PrintList(); /打印鏈表的數(shù)據(jù)域打印鏈表的數(shù)據(jù)域 void InsertFront(Node* p); /可用來向前生成鏈表可用來向前生成鏈表 void InsertRear(Node* p); /可用來向后生成鏈表可用來向后生成鏈表 void InsertOrder(Node *p); /按升序生成鏈表按升序生成鏈表 Node*CreatNode(T data); /創(chuàng)建一個(gè)結(jié)點(diǎn)創(chuàng)建一個(gè)結(jié)點(diǎn)(孤立結(jié)點(diǎn)孤立結(jié)點(diǎn)) Node*DeleteNode(Node* p); /刪除指定結(jié)點(diǎn)刪除指定結(jié)點(diǎn);再定義鏈表類，操作包括建立有序鏈表、搜索遍歷、再定義鏈表類，操作包括建立有序鏈表、搜索遍歷

19、、插入、刪除、取數(shù)據(jù)等插入、刪除、取數(shù)據(jù)等:鏈表類成員函數(shù)：鏈表類成員函數(shù)：templateList:List( ) head=tail=new Node( ); templateList:List( ) MakeEmpty( ); delete head; templatevoid List:MakeEmpty( ) Node *tempP; while(head-link!=NULL) tempP=head-link; head-link=tempP-link; /把頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)從鏈中脫離 delete tempP; /刪除(釋放)脫離下來的結(jié)點(diǎn) tail=head; /表頭指針與

20、表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈template Node* List:Find(T data) Node *tempP=head-link; while(tempP!=NULL&tempP-info!=data) tempP=tempP-link; return tempP; /搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULLtemplateint List:Length( ) Node* tempP=head-link; int count=0; while(tempP!=NULL) tempP=tempP-link; count+; return count;templatevoid

21、List:PrintList( ) Node* tempP=head-link; while(tempP!=NULL) coutinfolink; coutendl;templatevoid List:InsertFront(Node *p) p-link=head-link; head-link=p; if(tail=head) tail=p;templatevoid List:InsertRear(Node *p) p-link=tail-link; tail-link=p; tail=p;templateNode* List:CreatNode(T data) Node*tempP=new Node(data); return tempP;templatevoid List:InsertOrder(Node *p) Node *tempP=head-li