準備數據
準備在鏈表操作中需要用到的變量及數據結構
示例代碼如下：
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;
}
程序運行結果示例：
