C++教程:鏈表的創建和遍歷

2020-05-23 14:26:50

字體：大中小

來源：轉載

供稿：網友

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

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

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

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