C++中單鏈表的建立與基本操作
更新時間：2013年10月14日 09:54:32 作者：
以下是對C++中單鏈表的建立與基本操作進行了詳細的介紹，需要的朋友可以過來參考下，希望對大家有所幫助
準備數(shù)據(jù)
準備在鏈表操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)
示例代碼如下：
復(fù)制代碼 代碼如下:
struct Data //數(shù)據(jù)結(jié)點類型
{
string key; //關(guān)鍵字
string name;
int age;
};
struct CLType //定義鏈表結(jié)構(gòu)
{
Data nodeData;
Data *nextNode;
};
定義了鏈表數(shù)據(jù)元素的類型Data以及鏈表的數(shù)據(jù)結(jié)構(gòu)CLType。結(jié)點的具體數(shù)據(jù)保存在一個結(jié)構(gòu)Data中，而指針nextNode用來指向下一個結(jié)點。
我們可以認為，該鏈表是一個班級學(xué)生的記錄，其中key表示學(xué)號，name為學(xué)生的名字，age為年齡。
追加結(jié)點
追加結(jié)點就是在鏈表末尾增加一個結(jié)點。表尾結(jié)點的地址部分原來保存的是空地址NULL，此時需要將其設(shè)置為新增結(jié)點的地址（即原表尾結(jié)點指向新增結(jié)點），然后將新增節(jié)點的地址部分設(shè)置為空地址NULL，即新增結(jié)點為表尾。
由于一般情況下，鏈表只有一個頭指針head，要在末尾添加結(jié)點就需要從頭指針head開始逐個檢查，直到找到最后一個結(jié)點（即表尾）。
追加結(jié)點的操作步驟如下：
（1）首先分配內(nèi)存地址，保存新增結(jié)點。
（2）從頭指針head開始逐個檢查，直到找到最后一個結(jié)點（即表尾）。
（3）將表尾結(jié)點的地址設(shè)置為新增結(jié)點的地址。
（4）將新增結(jié)點的地址部分設(shè)置為空地址NULL，即新增結(jié)點成為表尾。
示例代碼如下：
復(fù)制代碼 代碼如下:
CLType * CLAddEnd(CLType *head,Data nodeData)
{
CLType *node,*htemp;
if(!(node = new CLType))
{
cout<<"分配內(nèi)存失??！"<<endl; //分配內(nèi)存失敗
return NULL;
}
else
{
node->nodeData = nodeData; //保存結(jié)點數(shù)據(jù)
node->nextNode = NULL; //設(shè)置結(jié)點指針為空，即作為表尾
if(head == NULL) //當鏈表是空表的時候
{
head = node;
return head;
}
htemp = head;
while(htemp->nextNode != NULL) //查找鏈表的末尾
{
htemp = htemp->nextNode;
}
htemp->nextNode = node;
return head;
}
}
輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)nodeData為結(jié)點保存的數(shù)據(jù)。程序中，使用new關(guān)鍵字申請動態(tài)空間，如果內(nèi)分配成功，node中將保存指向該內(nèi)存區(qū)域的指針。
然后，將傳入的nodeData保存到申請的內(nèi)存區(qū)域，并設(shè)置該結(jié)點指向下一結(jié)點的指針值為NULL。
插入頭結(jié)點
插入頭結(jié)點就是在鏈表首部添加結(jié)點的過程，和在表尾插入結(jié)點相反，這個操作是在表頭上插入結(jié)點，作為頭結(jié)點。
插入頭結(jié)點的步驟如下：
（1）首先分配內(nèi)存，保存新增的結(jié)點。
（2）使新增姐弟那指向頭指針head所指向的結(jié)點
（3）然后使頭指針head指向新增結(jié)點
示例代碼如下：
復(fù)制代碼 代碼如下:
CLType *CLAddFirst(CLType *head,Data nodeData)
{
CLType *node;
if(!(node = new CLType))
{
cout<<"分配內(nèi)存失敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保存結(jié)點數(shù)據(jù)
node->nextNode = head; //指向頭指針所指向的指針
head = node; //頭指針指向新增結(jié)點
return head;
}
}
輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)nodeData為結(jié)點中保存的數(shù)據(jù)。程序中首先使用new關(guān)鍵字申請一個新的保存結(jié)點的內(nèi)存空間，如果申請成功，node中將保存指向該內(nèi)存區(qū)域的指針。
然后，將傳入的nodeData保存到申請的內(nèi)存區(qū)域中，并使新增的結(jié)點指向頭指針head所指向的結(jié)點，然后設(shè)置頭指針head重新指向新增結(jié)點。
查找結(jié)點
查找結(jié)點就是在鏈表結(jié)構(gòu)中查找需要的元素。對于鏈表結(jié)構(gòu)來說，一般可以分為按照結(jié)點序號查找和按照關(guān)鍵字查詢兩類。
按照結(jié)點序號查詢
即查詢鏈表中的第多少個結(jié)點，其示例代碼如下：
復(fù)制代碼 代碼如下:
CLType *CLFindNodeNum(CLType *head,int k)
{
CLType *htemp;
int i = 1;
htemp = head; //保存鏈表頭指針
for(i = 1;i<k&&htemp;i++) //找到該結(jié)點
{
htemp = htemp->nextNode;
}
return htemp; //返回指向第k個結(jié)點的指針
}
輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)k為要查詢的結(jié)點的序號。通過序號進行多次循環(huán)，獲得指向該結(jié)點的指針，然后返回指針。
按照關(guān)鍵字查詢
即根據(jù)鏈表中結(jié)點的某一個關(guān)鍵字進行查詢，我們以查詢學(xué)生的姓名（name）為例，其示例代碼如下：
復(fù)制代碼 代碼如下:
CLType *CLFindNodeKey(CLType *head,string name)
{
CLType * htemp;
htemp = head; //保存鏈表頭指針
while(htemp)
{
if(htemp->nodeData.name == name) //當結(jié)點關(guān)鍵字和傳入關(guān)鍵字相同
{
return htemp; //返回該結(jié)點指針
}
htemp = htemp->nextNode;
}
return NULL;
}
輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)name為要查詢的同學(xué)的姓名。遍歷查詢所有的同學(xué)的姓名，當有結(jié)點的姓名與所查詢的姓名相同的時候，則返回該結(jié)點的指針。
插入結(jié)點
插入結(jié)點就是在鏈表中間部分的位置增加一個結(jié)點。
插入結(jié)點的步驟如下：
（1）分配內(nèi)存空間，保存新增的結(jié)點。
（2）找到要插入的邏輯位置，也就是找到插在那個結(jié)點的后面。
（3）修改插入位置結(jié)點的指針，使其指向新增結(jié)點，而使新增結(jié)點指向原插入位置所指向的結(jié)點。
示例代碼如下：
復(fù)制代碼 代碼如下:
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
CLType *node,*nodetemp;
if(!(node = new CLType)) //申請結(jié)點
{
cout<<"申請內(nèi)存失敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保存結(jié)點中的數(shù)據(jù)
nodetemp=CLFindNodeNum(head,k-1);//通過按照結(jié)點序號查找函數(shù)找到插入點前一個結(jié)點（關(guān)鍵結(jié)點）
if(nodetemp)
{
node->nextNode = nodetemp->nextNode;//插入的結(jié)點指向關(guān)鍵結(jié)點的下一個節(jié)點
nodetemp->nextNode = node; //關(guān)鍵結(jié)點指向插入點
}
else
{
cout<<"沒有找到正確的插入位置"<<endl;
delete node;
}
}
return head; //返回頭指針
}
輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)findkey為鏈表中進行查找的結(jié)點關(guān)鍵字，找到該結(jié)點后將在該結(jié)點后面添加結(jié)點數(shù)據(jù)，nodeData為新增結(jié)點的數(shù)據(jù)。程序中首先使用new申請結(jié)點空間，然后調(diào)用CLFindNodeNum函數(shù)查找指向結(jié)點，然后執(zhí)行插入操作。
刪除結(jié)點
刪除結(jié)點就是將鏈表中的某個結(jié)點數(shù)據(jù)刪除，并不影響其位置前后的結(jié)點。
刪除結(jié)點操作的步驟如下：
（1）查找需要刪除的結(jié)點。
（2）使前一結(jié)點指向當前節(jié)點的下一結(jié)點。
（3）刪除該結(jié)點
刪除結(jié)點可以通過結(jié)點的序號確定要刪除的結(jié)點，當然也可以通過結(jié)點的關(guān)鍵字確定要刪除的結(jié)點。
我們以通過關(guān)鍵字刪除結(jié)點為例，示例代碼如下：
復(fù)制代碼 代碼如下:
int CLDeleteNode(CLType *head,string name)
{
CLType *node,*htemp; //node用于刪除結(jié)點的前一個結(jié)點
htemp = head;
node = head;
while(htemp)
{
if(htemp->nodeData.name == name)//找到關(guān)鍵字，執(zhí)行刪除操作
{
node->nextNode = htemp->nextNode;//使前一結(jié)點指向當前節(jié)點的下一結(jié)點
delete htemp; //釋放該結(jié)點的空間（即，刪除了結(jié)點）
return 1;
}
else
{
node = htemp; //指向當前節(jié)點
htemp = htemp->nextNode; //指向下一個結(jié)點
}
}
return 0; //刪除失敗
}
head為鏈表頭指針，輸入?yún)?shù)name表示要刪除的同學(xué)的姓名。程序中，通過一個循環(huán)，按關(guān)鍵字在整個鏈表中查找要刪除的結(jié)點。如果找到被刪除的結(jié)點，則設(shè)置上一結(jié)點（node指針所指結(jié)點）指向當前結(jié)點（h指針所指結(jié)點）的下一個結(jié)點，即在邏輯上將該結(jié)點刪除，然后對該結(jié)點執(zhí)行delete操作，釋放結(jié)點占用的內(nèi)存空間，即在物理上將其刪除。
計算鏈表長度
計算鏈表長度也就是統(tǒng)計鏈表中結(jié)點的數(shù)量。順序表中計算鏈表長度比較方便，但在鏈表中鏈表的長度卻需要通過遍歷鏈表來獲得，因為鏈表在物理上不是連續(xù)存儲的。
示例代碼如下：
復(fù)制代碼 代碼如下:
int CLLength(CLType *head)
{
CLType *htemp;
int Len = 0;
htemp = head;
while(htemp) //遍歷整個數(shù)組
{
Len++; //累加結(jié)點的數(shù)量
htemp = htemp->nextNode; //處理下一個結(jié)點
}
return Len;
}
參數(shù)head是鏈表的頭指針，程序中通過while來遍歷指針，Len作為計數(shù)器，通過記錄循環(huán)的次數(shù)，來獲得鏈表的長度，當指針為NULL時截止，然后返回計數(shù)器的值。
顯示所有結(jié)點
遍歷所有的結(jié)點，并輸出。
復(fù)制代碼 代碼如下:
void CLAllNode(CLType *head)
{
CLType *htemp;
htemp = head;
while(htemp) //遍歷整個數(shù)組
{
nodeData = htemp->nodeData; //獲取結(jié)點數(shù)據(jù)
cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl;
htemp = htemp->nextNode; //處理下一個結(jié)點
}
}
輸出結(jié)點的函數(shù)，沒有返回值，所有定義為void。每次都通過CLType類型的結(jié)點獲得其nodeData的值
鏈表操作完整示例
完整示例的代碼比較長，要耐心看哈…… :)
復(fù)制代碼 代碼如下:
#include<iostream>
#include<string>
using namespace std;
struct Data //數(shù)據(jù)結(jié)點類型
{
string key; //關(guān)鍵字
string name;
int age;
};
struct CLType //定義鏈表結(jié)構(gòu)
{
Data nodeData;
CLType *nextNode;
};
CLType * CLAddEnd(CLType *head,Data nodeData)
{
CLType *node,*htemp;
if(!(node = new CLType))
{
cout<<"分配內(nèi)存失??！"<<endl; //分配內(nèi)存失敗
return NULL;
}
else
{
node->nodeData = nodeData; //保存結(jié)點數(shù)據(jù)
node->nextNode = NULL; //設(shè)置結(jié)點指針為空，即作為表尾
if(head == NULL) //當鏈表是空表的時候
{
head = node;
return head;
}
htemp = head;
while(htemp->nextNode != NULL) //查找鏈表的末尾
{
htemp = htemp->nextNode;
}
htemp->nextNode = node;
return head;
}
}
CLType *CLAddFirst(CLType *head,Data nodeData)
{
CLType *node;
if(!(node = new CLType))
{
cout<<"分配內(nèi)存失敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保存結(jié)點數(shù)據(jù)
node->nextNode = head; //指向頭指針所指向的指針
head = node; //頭指針指向新增結(jié)點
return head;
}
}
CLType *CLFindNodeNum(CLType *head,int k)
{
CLType *htemp;
int i = 1;
htemp = head; //保存鏈表頭指針
for(i = 1;i<k&&htemp;i++) //找到該結(jié)點
{
htemp = htemp->nextNode;
}
return htemp; //返回指向第k個結(jié)點的指針
}
CLType *CLFindNodeName(CLType *head,string name)
{
CLType * htemp;
htemp = head; //保存鏈表頭指針
while(htemp)
{
if(htemp->nodeData.name == name) //當結(jié)點關(guān)鍵字和傳入關(guān)鍵字相同
{
return htemp; //返回該結(jié)點指針
}
htemp = htemp->nextNode;
}
return NULL;
}
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
CLType *node,*nodetemp;
if(!(node = new CLType)) //申請結(jié)點
{
cout<<"申請內(nèi)存失敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保存結(jié)點中的數(shù)據(jù)
nodetemp=CLFindNodeNum(head,k-1); //通過按照結(jié)點序號查找函數(shù)找到插入點前一個結(jié)點（關(guān)鍵結(jié)點）
if(nodetemp)
{
node->nextNode = nodetemp->nextNode; //插入的結(jié)點指向關(guān)鍵結(jié)點的下一個節(jié)點
nodetemp->nextNode = node; //關(guān)鍵結(jié)點指向插入點
}
else
{
cout<<"沒有找到正確的插入位置"<<endl;
delete node;
}
}
return head; //返回頭指針
}
int CLDeleteNode(CLType *head,string name)
{
CLType *node,*htemp; //node用于刪除結(jié)點的前一個結(jié)點
htemp = head;
node = head;
while(htemp)
{
if(htemp->nodeData.name == name) //找到關(guān)鍵字，執(zhí)行刪除操作
{
node->nextNode = htemp->nextNode; //使前一結(jié)點指向當前節(jié)點的下一結(jié)點
delete htemp; //釋放該結(jié)點的空間（即，刪除了結(jié)點）
return 1;
}
else
{
node = htemp; //指向當前節(jié)點
htemp = htemp->nextNode; //指向下一個結(jié)點
}
}
return 0; //刪除失敗
}
int CLLength(CLType *head)
{
CLType *htemp;
int Len = 0;
htemp = head;
while(htemp) //遍歷整個數(shù)組
{
Len++; //累加結(jié)點的數(shù)量
htemp = htemp->nextNode; //處理下一個結(jié)點
}
return Len;
}
void CLAllNode(CLType *head)
{
CLType *htemp;
Data nodeData;
htemp = head;
cout<<"鏈表長度為："<<CLLength(head)<<endl;
while(htemp) //遍歷整個數(shù)組
{
nodeData = htemp->nodeData; //獲取結(jié)點數(shù)據(jù)
cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl;
htemp = htemp->nextNode; //處理下一個結(jié)點
}
}
int main()
{
CLType *node,*head = NULL;
Data nodeData;
string name;
int k;
cout<<"請先輸入鏈表中的數(shù)據(jù)，格式為：學(xué)號，姓名，年齡（年齡為0時停止輸入）"<<endl;
while(1)
{
cin>>nodeData.key>>nodeData.name>>nodeData.age;
if(nodeData.age==0)break;
head=CLAddEnd(head,nodeData); //在鏈表的尾部添加結(jié)點
}
CLAllNode(head); //顯示所有的結(jié)點
//演示在頭部插入數(shù)據(jù)
cout<<"請輸入一個結(jié)點，并在鏈表的頭部插入"<<endl;
cin>>nodeData.key>>nodeData.name>>nodeData.age;
head=CLAddFirst(head,nodeData);
CLAllNode(head);
//演示在中間位置插入一個數(shù)據(jù)
cout<<"請輸入一個在鏈表內(nèi)部插入的結(jié)點："<<endl;
cin>>nodeData.key>>nodeData.name>>nodeData.age;
cout<<"請輸入插入點的位置：";
cin>>k;
head=CLInsertNode(head,k,nodeData);
CLAllNode(head);
//演示按照序號查詢數(shù)據(jù)
cout<<"請輸入按照結(jié)點查詢的一個結(jié)點序號：";
cin>>k;
node=CLFindNodeNum(head,k);
cout<<"您所查詢的結(jié)點是："<<endl;
cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
//演示按照姓名查詢數(shù)據(jù)
cout<<"請輸入一個按照姓名查詢的一個同學(xué)的姓名：";
cin>>name;
node=CLFindNodeName(head,name);
cout<<"您所查詢的結(jié)點是："<<endl;
cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
//演示刪除數(shù)據(jù)信息
cout<<"請輸入結(jié)點中的一個同學(xué)中的名字，系統(tǒng)會刪除他的信息：";
cin>>name;
if(CLDeleteNode(head,name))cout<<"數(shù)據(jù)刪除成功！"<<endl;
CLAllNode(head);
return 0;
}
程序運行結(jié)果示例：
相關(guān)文章
C語言數(shù)據(jù)結(jié)構(gòu)二叉樹簡單應(yīng)用
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)二叉樹簡單應(yīng)用的相關(guān)資料,需要的朋友可以參考下2017-05-05
C++ 內(nèi)聯(lián)函數(shù)inline案例詳解
這篇文章主要介紹了C++ 內(nèi)聯(lián)函數(shù)inline案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細介紹了C++實現(xiàn)日期類的相關(guān)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-09-09
簡單掌握Linux系統(tǒng)中fork()函數(shù)創(chuàng)建子進程的用法
fork()函數(shù)只能在類Unix系統(tǒng)下使用,因為需要引入unistd頭文件,這里我們就來簡單掌握Linux系統(tǒng)中fork()函數(shù)創(chuàng)建子進程的用法,需要的朋友可以參考下2016-06-06
這篇文章主要為大家詳細介紹了MFC實現(xiàn)漂亮界面之美化按鈕，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02
Qt6.0+vs2019環(huán)境配置的實現(xiàn)教程
這篇文章主要介紹了Qt6.0+vs2019環(huán)境配置的實現(xiàn)教程，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)消消樂小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要介紹C++中的long long與__int64,在C++ Primer當中提到的64位的int只有l(wèi)ong long,但是在實際各種各樣的C++編譯器當中,64位的int一直有兩種標準.一種是long long,還有一種是__int64,非主流的VC甚至還支持_int64,下面文章將介紹具體內(nèi)容,需要的朋友可以參考一下2021-11-11
C++實現(xiàn)LeetCode(59.螺旋矩陣之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(59.螺旋矩陣之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
詳解C語言內(nèi)核中的鏈表與結(jié)構(gòu)體
Windows內(nèi)核中是無法使用vector容器等數(shù)據(jù)結(jié)構(gòu)的，當我們需要保存一個結(jié)構(gòu)體數(shù)組時，就需要使用內(nèi)核中提供的專用鏈表結(jié)構(gòu)。本文分享了幾個內(nèi)核中使用鏈表存儲多個結(jié)構(gòu)體的通用案例，希望對你有所幫助2022-09-09