C++中單鏈表的樹立與根本操作。本站提示廣大學習愛好者：（C++中單鏈表的樹立與根本操作）文章只能為提供參考，不一定能成為您想要的結果。以下是C++中單鏈表的樹立與根本操作正文
預備數據
預備在鏈表操作中須要用到的變量及數據構造
示例代碼以下：
struct Data //數據結點類型
{
string key; //症結字
string name;
int age;
};
struct CLType //界說鏈表構造
{
Data nodeData;
Data *nextNode;
};
界說了鏈表數據元素的類型Data和鏈表的數據構造CLType。結點的詳細數據保留在一個構造Data中，而指針nextNode用來指向下一個結點。
我們可以以為，該鏈表是一個班級先生的記載，個中key表現學號，name為先生的名字，age為年紀。
追加結點
追加結點就是在鏈表末尾增長一個結點。表尾結點的地址部門本來保留的是曠地址NULL，此時須要將其設置為新增結點的地址（即原表尾結點指向新增結點），然後將新增節點的地址部門設置為曠地址NULL，即新增結點為表尾。
因為普通情形下，鏈表只要一個頭指針head，要在末尾添加結點就須要從頭指針head開端逐一檢討，直到找到最初一個結點（即表尾）。
追加結點的操作步調以下：
（1）起首分派內存地址，保留新增結點。
（2）從頭指針head開端逐一檢討，直到找到最初一個結點（即表尾）。
（3）將表尾結點的地址設置為新增結點的地址。
（4）將新增結點的地址部門設置為曠地址NULL，即新增結點成為表尾。
示例代碼以下：
CLType * CLAddEnd(CLType *head,Data nodeData)
{
CLType *node,*htemp;
if(!(node = new CLType))
{
cout<<"分派內存掉敗！"<<endl; //分派內存掉敗
return NULL;
}
else
{
node->nodeData = nodeData; //保留結點數據
node->nextNode = NULL; //設置結點指針為空，即作為表尾
if(head == NULL) //當鏈表是空表的時刻
{
head = node;
return head;
}
htemp = head;
while(htemp->nextNode != NULL) //查找鏈表的末尾
{
htemp = htemp->nextNode;
}
htemp->nextNode = node;
return head;
}
}
輸出參數head為鏈表頭指針，輸出參數nodeData為結點保留的數據。法式中，應用new症結字請求靜態空間，假如內分派勝利，node中將保留指向該內存區域的指針。
然後，將傳入的nodeData保留到請求的內存區域，並設置該結點指向下一結點的指針值為NULL。
拔出頭結點
拔出頭結點就是在鏈表首部添加結點的進程，和在表尾拔出結點相反，這個操作是在表頭上拔出結點，作為頭結點。
拔出頭結點的步調以下：
（1）起首分派內存，保留新增的結點。
（2）使新增姐弟那指向頭指針head所指向的結點
（3）然後使頭指針head指向新增結點
示例代碼以下：
CLType *CLAddFirst(CLType *head,Data nodeData)
{
CLType *node;
if(!(node = new CLType))
{
cout<<"分派內存掉敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保留結點數據
node->nextNode = head; //指向頭指針所指向的指針
head = node; //頭指針指向新增結點
return head;
}
}
輸出參數head為鏈表頭指針，輸出參數nodeData為結點中保留的數據。法式中起首應用new症結字請求一個新的保留結點的內存空間，假如請求勝利，node中將保留指向該內存區域的指針。
然後，將傳入的nodeData保留到請求的內存區域中，並使新增的結點指向頭指針head所指向的結點，然後設置頭指針head從新指向新增結點。
查找結點
查找結點就是在鏈表構造中查找須要的元素。關於鏈表構造來講，普通可以分為依照結點序號查找和依照症結字查詢兩類。
依照結點序號查詢
即查詢鏈表中的第若干個結點，其示例代碼以下：
CLType *CLFindNodeNum(CLType *head,int k)
{
CLType *htemp;
int i = 1;
htemp = head; //保留鏈表頭指針
for(i = 1;i<k&&htemp;i++) //找到該結點
{
htemp = htemp->nextNode;
}
return htemp; //前往指向第k個結點的指針
}
輸出參數head為鏈表頭指針，輸出參數k為要查詢的結點的序號。經由過程序號停止屢次輪回，取得指向該結點的指針，然後前往指針。
依照症結字查詢
即依據鏈表中結點的某一個症結字停止查詢，我們以查詢先生的姓名（name）為例，其示例代碼以下：
CLType *CLFindNodeKey(CLType *head,string name)
{
CLType * htemp;
htemp = head; //保留鏈表頭指針
while(htemp)
{
if(htemp->nodeData.name == name) //當結點症結字和傳入症結字雷同
{
return htemp; //前往該結點指針
}
htemp = htemp->nextNode;
}
return NULL;
}
輸出參數head為鏈表頭指針，輸出參數name為要查詢的同窗的姓名。遍歷查詢一切的同窗的姓名，當有結點的姓名與所查詢的姓名雷同的時刻，則前往該結點的指針。
拔出結點
拔出結點就是在鏈表中央部門的地位增長一個結點。
拔出結點的步調以下：
（1）分派內存空間，保留新增的結點。
（2）找到要拔出的邏輯地位，也就是找到插在誰人結點的前面。
（3）修正拔出地位結點的指針，使其指向新增結點，而使新增結點指向原拔出地位所指向的結點。
示例代碼以下：
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
CLType *node,*nodetemp;
if(!(node = new CLType)) //請求結點
{
cout<<"請求內存掉敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保留結點中的數據
nodetemp=CLFindNodeNum(head,k-1);//經由過程依照結點序號查找函數找到拔出點前一個結點（症結結點）
if(nodetemp)
{
node->nextNode = nodetemp->nextNode;//拔出的結點指向症結結點的下一個節點
nodetemp->nextNode = node; //症結結點指向拔出點
}
else
{
cout<<"沒有找到准確的拔出地位"<<endl;
delete node;
}
}
return head; //前往頭指針
}
輸出參數head為鏈表頭指針，輸出參數findkey為鏈表中停止查找的結點症結字，找到該結點後將在該結點前面添加結點數據，nodeData為新增結點的數據。法式中起首應用new請求結點空間，然後挪用CLFindNodeNum函數查找指向結點，然後履行拔出操作。
刪除結點
刪除結點就是將鏈表中的某個結點數據刪除，其實不影響其地位前後的結點。
刪除結點操作的步調以下：
（1）查找須要刪除的結點。
（2）使前一結點指向以後節點的下一結點。
（3）刪除該結點
刪除結點可以經由過程結點的序號肯定要刪除的結點，固然也能夠經由過程結點的症結字肯定要刪除的結點。
我們以經由過程症結字刪除結點為例，示例代碼以下：
int CLDeleteNode(CLType *head,string name)
{
CLType *node,*htemp; //node用於刪除結點的前一個結點
htemp = head;
node = head;
while(htemp)
{
if(htemp->nodeData.name == name)//找到症結字，履行刪除操作
{
node->nextNode = htemp->nextNode;//使前一結點指向以後節點的下一結點
delete htemp; //釋放該結點的空間（即，刪除結點）
return 1;
}
else
{
node = htemp; //指向以後節點
htemp = htemp->nextNode; //指向下一個結點
}
}
return 0; //刪除掉敗
}
head為鏈表頭指針，輸出參數name表現要刪除的同窗的姓名。法式中，經由過程一個輪回，按症結字在全部鏈表中查找要刪除的結點。假如找到被刪除的結點，則設置上一結點（node指針所指結點）指向以後結點（h指針所指結點）的下一個結點，即在邏輯大將該結點刪除，然後對該結點履行delete操作，釋放結點占用的內存空間，即在物理大將其刪除。
盤算鏈表長度
盤算鏈表長度也就是統計鏈表中結點的數目。次序表上鉤算鏈表長度比擬便利，但在鏈表中鏈表的長度卻須要經由過程遍歷鏈表來取得，由於鏈表在物理上不是持續存儲的。
示例代碼以下：
int CLLength(CLType *head)
{
CLType *htemp;
int Len = 0;
htemp = head;
while(htemp) //遍歷全部數組
{
Len++; //累加結點的數目
htemp = htemp->nextNode; //處置下一個結點
}
return Len;
}
參數head是鏈表的頭指針，法式中經由過程while來遍歷指針，Len作為計數器，經由過程記載輪回的次數，來取得鏈表的長度，當指針為NULL時截止，然後前往計數器的值。
顯示一切結點
遍歷一切的結點，並輸入。
void CLAllNode(CLType *head)
{
CLType *htemp;
htemp = head;
while(htemp) //遍歷全部數組
{
nodeData = htemp->nodeData; //獲得結點數據
cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl;
htemp = htemp->nextNode; //處置下一個結點
}
}
輸入結點的函數，沒有前往值，一切界說為void。每次都經由過程CLType類型的結點取得其nodeData的值
鏈表操作完全示例
完全示例的代碼比擬長，要耐煩看哈…… :)
#include<iostream>
#include<string>
using namespace std;
struct Data //數據結點類型
{
string key; //症結字
string name;
int age;
};
struct CLType //界說鏈表構造
{
Data nodeData;
CLType *nextNode;
};
CLType * CLAddEnd(CLType *head,Data nodeData)
{
CLType *node,*htemp;
if(!(node = new CLType))
{
cout<<"分派內存掉敗！"<<endl; //分派內存掉敗
return NULL;
}
else
{
node->nodeData = nodeData; //保留結點數據
node->nextNode = NULL; //設置結點指針為空，即作為表尾
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<<"分派內存掉敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保留結點數據
node->nextNode = head; //指向頭指針所指向的指針
head = node; //頭指針指向新增結點
return head;
}
}
CLType *CLFindNodeNum(CLType *head,int k)
{
CLType *htemp;
int i = 1;
htemp = head; //保留鏈表頭指針
for(i = 1;i<k&&htemp;i++) //找到該結點
{
htemp = htemp->nextNode;
}
return htemp; //前往指向第k個結點的指針
}
CLType *CLFindNodeName(CLType *head,string name)
{
CLType * htemp;
htemp = head; //保留鏈表頭指針
while(htemp)
{
if(htemp->nodeData.name == name) //當結點症結字和傳入症結字雷同
{
return htemp; //前往該結點指針
}
htemp = htemp->nextNode;
}
return NULL;
}
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
CLType *node,*nodetemp;
if(!(node = new CLType)) //請求結點
{
cout<<"請求內存掉敗"<<endl;
return NULL;
}
else
{
node->nodeData = nodeData; //保留結點中的數據
nodetemp=CLFindNodeNum(head,k-1); //經由過程依照結點序號查找函數找到拔出點前一個結點（症結結點）
if(nodetemp)
{
node->nextNode = nodetemp->nextNode; //拔出的結點指向症結結點的下一個節點
nodetemp->nextNode = node; //症結結點指向拔出點
}
else
{
cout<<"沒有找到准確的拔出地位"<<endl;
delete node;
}
}
return head; //前往頭指針
}
int CLDeleteNode(CLType *head,string name)
{
CLType *node,*htemp; //node用於刪除結點的前一個結點
htemp = head;
node = head;
while(htemp)
{
if(htemp->nodeData.name == name) //找到症結字，履行刪除操作
{
node->nextNode = htemp->nextNode; //使前一結點指向以後節點的下一結點
delete htemp; //釋放該結點的空間（即，刪除結點）
return 1;
}
else
{
node = htemp; //指向以後節點
htemp = htemp->nextNode; //指向下一個結點
}
}
return 0; //刪除掉敗
}
int CLLength(CLType *head)
{
CLType *htemp;
int Len = 0;
htemp = head;
while(htemp) //遍歷全部數組
{
Len++; //累加結點的數目
htemp = htemp->nextNode; //處置下一個結點
}
return Len;
}
void CLAllNode(CLType *head)
{
CLType *htemp;
Data nodeData;
htemp = head;
cout<<"鏈表長度為："<<CLLength(head)<<endl;
while(htemp) //遍歷全部數組
{
nodeData = htemp->nodeData; //獲得結點數據
cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl;
htemp = htemp->nextNode; //處置下一個結點
}
}
int main()
{
CLType *node,*head = NULL;
Data nodeData;
string name;
int k;
cout<<"請先輸出鏈表中的數據，格局為：學號，姓名，年紀（年紀為0時停滯輸出）"<<endl;
while(1)
{
cin>>nodeData.key>>nodeData.name>>nodeData.age;
if(nodeData.age==0)break;
head=CLAddEnd(head,nodeData); //在鏈表的尾部添加結點
}
CLAllNode(head); //顯示一切的結點
//演示在頭部拔出數據
cout<<"請輸出一個結點，並在鏈表的頭部拔出"<<endl;
cin>>nodeData.key>>nodeData.name>>nodeData.age;
head=CLAddFirst(head,nodeData);
CLAllNode(head);
//演示在中央地位拔出一個數據
cout<<"請輸出一個在鏈表外部拔出的結點："<<endl;
cin>>nodeData.key>>nodeData.name>>nodeData.age;
cout<<"請輸出拔出點的地位：";
cin>>k;
head=CLInsertNode(head,k,nodeData);
CLAllNode(head);
//演示依照序號查詢數據
cout<<"請輸出依照結點查詢的一個結點序號：";
cin>>k;
node=CLFindNodeNum(head,k);
cout<<"您所查詢的結點是："<<endl;
cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
//演示依照姓名查詢數據
cout<<"請輸出一個依照姓名查詢的一個同窗的姓名：";
cin>>name;
node=CLFindNodeName(head,name);
cout<<"您所查詢的結點是："<<endl;
cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
//演示刪除數據信息
cout<<"請輸出結點中的一個同窗中的名字，體系會刪除他的信息：";
cin>>name;
if(CLDeleteNode(head,name))cout<<"數據刪除勝利！"<<endl;
CLAllNode(head);
return 0;
}
法式運轉成果示例：
