C++教程:鏈表的創(chuàng)建和遍歷

2020-05-23 14:26:50

字體：大中小

供稿：網(wǎng)友

接下來，我們把鏈表的創(chuàng)建和遍歷分析得更加具體化：

由于第一個(gè)結(jié)點(diǎn)也是動態(tài)分配的，因此一個(gè)鏈表始終要有一個(gè)指針指向它的表頭，否則我們將無法找到這個(gè)鏈表。我們把這個(gè)表頭指針稱為head。
在創(chuàng)建一個(gè)多結(jié)點(diǎn)的鏈表時(shí)，新的結(jié)點(diǎn)總是連接在原鏈表的尾部的，所以我們必須要有一個(gè)指針始終指向鏈表的尾結(jié)點(diǎn)，方便我們操作。我們把這個(gè)表尾指針稱為pEnd。
每個(gè)結(jié)點(diǎn)都是動態(tài)分配的，每分配好一個(gè)結(jié)點(diǎn)會返回一個(gè)指針。由于head和pEnd已經(jīng)有了各自的崗位，我們還需要一個(gè)指針來接受剛分配好的新結(jié)點(diǎn)。我們把這個(gè)創(chuàng)建結(jié)點(diǎn)的指針稱為pS。
在遍歷的過程中，需要有一個(gè)指針能夠靈活動作，指向鏈表中的任何一個(gè)結(jié)點(diǎn)，以讀取各結(jié)點(diǎn)的數(shù)據(jù)。我們把這個(gè)訪問指針稱為pRead。
我們把創(chuàng)建鏈表和遍歷各自寫為一個(gè)函數(shù)，方便修改和維護(hù)。

做完了這些分析，我們可以開始著手寫這個(gè)程序了：（程序9.6.1）
#include "iostream.h"
struct node//定義結(jié)點(diǎn)結(jié)構(gòu)類型
{
char data;//用于存放字符數(shù)據(jù)
node *next;//用于指向下一個(gè)結(jié)點(diǎn)（后繼結(jié)點(diǎn)）
};
node * create();//創(chuàng)建鏈表的函數(shù)，返回表頭
void showList(node *head);//遍歷鏈表的函數(shù)，參數(shù)為表頭
int main()
{
node *head;
head=create();//以head為表頭創(chuàng)建一個(gè)鏈表
showList(head);//遍歷以head為表頭的鏈表
return 0;
}
node * create()
{
node *head=NULL;//表頭指針，一開始沒有任何結(jié)點(diǎn)，所以為NULL
node *pEnd=head;//表為指針，一開始沒有任何結(jié)點(diǎn)，所以指向表頭
node *pS;//創(chuàng)建新結(jié)點(diǎn)時(shí)使用的指針
char temp;//用于存放從鍵盤輸入的字符
cout <<"Please input a string end with '#':" <<endl;
do//循環(huán)至少運(yùn)行一次
{
cin >>temp;
if (temp!='#')//如果輸入的字符不是結(jié)尾符#，則建立新結(jié)點(diǎn)
{
pS=new node;//創(chuàng)建新結(jié)點(diǎn)
pS->data=temp;//新結(jié)點(diǎn)的數(shù)據(jù)為temp
pS->next=NULL;//新結(jié)點(diǎn)將成為表尾，所以next為NULL
if (head==NULL)//如果鏈表還沒有任何結(jié)點(diǎn)存在
{
head=pS;//則表頭指針指向這個(gè)新結(jié)點(diǎn)
}
else//否則
{
pEnd->next=pS;//把這個(gè)新結(jié)點(diǎn)連接在表尾
}
pEnd=pS;//這個(gè)新結(jié)點(diǎn)成為了新的表尾
}
}
while (temp!='#');//一旦輸入了結(jié)尾符，則跳出循環(huán)
return head;//返回表頭指針
}
void showList(node *head)
{
node *pRead=head;//訪問指針一開始指向表頭
cout <<"The data of the link list are:" <<endl;
while (pRead!=NULL)//當(dāng)訪問指針存在時(shí)（即沒有達(dá)到表尾之后）
{
cout <<pRead->data;//輸出當(dāng)前訪問結(jié)點(diǎn)的數(shù)據(jù)
pRead=pRead->next;//訪問指針向后移動
}
cout <<endl;
}
運(yùn)行結(jié)果：
Please input a string end with '#':
Tomato#
The data of the link list are:
Tomato

這個(gè)程序的功能是把輸入的字符串保存到鏈表中，然后把它輸出。從程序中我們可以看出，create函數(shù)的主要工作有：
①做好表頭表尾等指針的初始化。
②反復(fù)測試輸入的數(shù)據(jù)是否有效，如果有效則新建結(jié)點(diǎn)，并做好該結(jié)點(diǎn)的賦值工作。將新建結(jié)點(diǎn)與原來的鏈表連接，如果原鏈表沒有結(jié)點(diǎn)，則與表頭連接。
③返回表頭指針。
下圖9.6.1給出了create函數(shù)創(chuàng)建鏈表的過程。

程序中showList函數(shù)的主要工作有：
①初始化訪問指針。
②如果訪問指針不為空，則輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，否則函數(shù)結(jié)束。
③訪問指針向后移動，并重復(fù)第二項(xiàng)工作。

注意，雖然上述程序可以運(yùn)行，但是它沒有將內(nèi)存釋放，嚴(yán)格意義上來說，它是一個(gè)不完整的程序。

上一篇：C++教程:鏈表的查詢

下一篇：C++教程:什么是鏈表