C++中單鏈表的建立與基本操作
來源：本站原創(chuàng)|時間：2020-01-10|欄目：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é)點。
我們可以認為，該鏈表是一個班級學生的記錄，其中key表示學號，name為學生的名字，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)鍵字進行查詢，我們以查詢學生的姓名（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為要查詢的同學的姓名。遍歷查詢所有的同學的姓名，當有結(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表示要刪除的同學的姓名。程序中，通過一個循環(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ù)，格式為：學號，姓名，年齡（年齡為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<<"請輸入一個按照姓名查詢的一個同學的姓名：";
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é)點中的一個同學中的名字，系統(tǒng)會刪除他的信息：";
cin>>name;
if(CLDeleteNode(head,name))cout<<"數(shù)據(jù)刪除成功！"<<endl;
CLAllNode(head);
return 0;
}
程序運行結(jié)果示例：
上一篇：如何在C++中建立一個順序表
欄 目：C語言
下一篇：C++類中的常數(shù)據(jù)成員與靜態(tài)數(shù)據(jù)成員之間的區(qū)別
本文標題：C++中單鏈表的建立與基本操作
本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/3969.html
您可能感興趣的文章
- 04-02c語言沒有round函數(shù) round c語言
- 01-10深入理解C++中常見的關(guān)鍵字含義
- 01-10使用C++實現(xiàn)全排列算法的方法詳解
- 01-10c++中inline的用法分析
- 01-10深入理解鏈表的各類操作詳解
- 01-10用C++實現(xiàn)DBSCAN聚類算法
- 01-10全排列算法的非遞歸實現(xiàn)與遞歸實現(xiàn)的方法(C++)
- 01-10C++大數(shù)模板(推薦)
- 01-10淺談C/C++中的static與extern關(guān)鍵字的使用詳解
- 01-10用C語言實現(xiàn)單鏈表的各種操作(一)
閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機閱讀
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 08-05織夢dedecms什么時候用欄目交叉功能？
- 01-11ajax實現(xiàn)頁面的局部加載
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10delphi制作wav文件的方法
- 04-02jquery與jsp,用jquery
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10C#中split用法實例總結(jié)