C++中單鏈表的建立與基本操作
準備數(shù)據(jù)
準備在鏈表操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)
示例代碼如下:
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é)點成為表尾。
示例代碼如下:
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é)點
示例代碼如下:
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é)點,其示例代碼如下:
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)為例,其示例代碼如下:
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é)點。
示例代碼如下:
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é)點為例,示例代碼如下:
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ù)存儲的。
示例代碼如下:
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é)點,并輸出。
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的值
鏈表操作完整示例
完整示例的代碼比較長,要耐心看哈…… :)
#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-05C++ 內(nèi)聯(lián)函數(shù)inline案例詳解
這篇文章主要介紹了C++ 內(nèi)聯(lián)函數(shù)inline案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-09-09簡單掌握Linux系統(tǒng)中fork()函數(shù)創(chuàng)建子進程的用法
fork()函數(shù)只能在類Unix系統(tǒng)下使用,因為需要引入unistd頭文件,這里我們就來簡單掌握Linux系統(tǒng)中fork()函數(shù)創(chuàng)建子進程的用法,需要的朋友可以參考下2016-06-06Qt6.0+vs2019環(huán)境配置的實現(xiàn)教程
這篇文章主要介紹了Qt6.0+vs2019環(huán)境配置的實現(xiàn)教程,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03C++實現(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