C++中單鏈表的建立與基本操作

更新時間：2013年10月14日 09:54:32 作者：

以下是對C++中單鏈表的建立與基本操作進(jìn)行了詳細(xì)的介紹，需要的朋友可以過來參考下，希望對大家有所幫助

準(zhǔn)備數(shù)據(jù)

準(zhǔn)備在鏈表操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)

示例代碼如下：

struct Data   //數(shù)據(jù)結(jié)點(diǎn)類型 
{
 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é)點(diǎn)的具體數(shù)據(jù)保存在一個結(jié)構(gòu)Data中，而指針nextNode用來指向下一個結(jié)點(diǎn)。

我們可以認(rèn)為，該鏈表是一個班級學(xué)生的記錄，其中key表示學(xué)號，name為學(xué)生的名字，age為年齡。

追加結(jié)點(diǎn)

追加結(jié)點(diǎn)就是在鏈表末尾增加一個結(jié)點(diǎn)。表尾結(jié)點(diǎn)的地址部分原來保存的是空地址NULL，此時需要將其設(shè)置為新增結(jié)點(diǎn)的地址（即原表尾結(jié)點(diǎn)指向新增結(jié)點(diǎn)），然后將新增節(jié)點(diǎn)的地址部分設(shè)置為空地址NULL，即新增結(jié)點(diǎn)為表尾。

由于一般情況下，鏈表只有一個頭指針head，要在末尾添加結(jié)點(diǎn)就需要從頭指針head開始逐個檢查，直到找到最后一個結(jié)點(diǎn)（即表尾）。

追加結(jié)點(diǎn)的操作步驟如下：

（1）首先分配內(nèi)存地址，保存新增結(jié)點(diǎn)。

（2）從頭指針head開始逐個檢查，直到找到最后一個結(jié)點(diǎn)（即表尾）。

（3）將表尾結(jié)點(diǎn)的地址設(shè)置為新增結(jié)點(diǎn)的地址。

（4）將新增結(jié)點(diǎn)的地址部分設(shè)置為空地址NULL，即新增結(jié)點(diǎn)成為表尾。

示例代碼如下：

復(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é)點(diǎn)數(shù)據(jù) 
  node->nextNode = NULL;     //設(shè)置結(jié)點(diǎn)指針為空，即作為表尾 
  if(head == NULL)      //當(dāng)鏈表是空表的時候 
  {
   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é)點(diǎn)保存的數(shù)據(jù)。程序中，使用new關(guān)鍵字申請動態(tài)空間，如果內(nèi)分配成功，node中將保存指向該內(nèi)存區(qū)域的指針。

然后，將傳入的nodeData保存到申請的內(nèi)存區(qū)域，并設(shè)置該結(jié)點(diǎn)指向下一結(jié)點(diǎn)的指針值為NULL。

插入頭結(jié)點(diǎn)

插入頭結(jié)點(diǎn)就是在鏈表首部添加結(jié)點(diǎn)的過程，和在表尾插入結(jié)點(diǎn)相反，這個操作是在表頭上插入結(jié)點(diǎn)，作為頭結(jié)點(diǎn)。

插入頭結(jié)點(diǎn)的步驟如下：

（1）首先分配內(nèi)存，保存新增的結(jié)點(diǎn)。

（2）使新增姐弟那指向頭指針head所指向的結(jié)點(diǎn)

（3）然后使頭指針head指向新增結(jié)點(diǎn)

示例代碼如下：

復(fù)制代碼代碼如下:

CLType *CLAddFirst(CLType *head,Data nodeData)
{
 CLType *node;
 if(!(node = new CLType))
 {
  cout<<"分配內(nèi)存失敗"<<endl;
  return NULL;
 }
 else
 {
  node->nodeData = nodeData;  //保存結(jié)點(diǎn)數(shù)據(jù) 
  node->nextNode = head;  //指向頭指針?biāo)赶虻闹羔?
  head = node;   //頭指針指向新增結(jié)點(diǎn) 
  return head;
 } 
} 

輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)nodeData為結(jié)點(diǎn)中保存的數(shù)據(jù)。程序中首先使用new關(guān)鍵字申請一個新的保存結(jié)點(diǎn)的內(nèi)存空間，如果申請成功，node中將保存指向該內(nèi)存區(qū)域的指針。

然后，將傳入的nodeData保存到申請的內(nèi)存區(qū)域中，并使新增的結(jié)點(diǎn)指向頭指針head所指向的結(jié)點(diǎn)，然后設(shè)置頭指針head重新指向新增結(jié)點(diǎn)。

查找結(jié)點(diǎn)

查找結(jié)點(diǎn)就是在鏈表結(jié)構(gòu)中查找需要的元素。對于鏈表結(jié)構(gòu)來說，一般可以分為按照結(jié)點(diǎn)序號查找和按照關(guān)鍵字查詢兩類。

按照結(jié)點(diǎn)序號查詢

即查詢鏈表中的第多少個結(jié)點(diǎn)，其示例代碼如下：

復(fù)制代碼代碼如下:

CLType *CLFindNodeNum(CLType *head,int k)
{
 CLType *htemp;
 int i = 1;
 htemp = head;      //保存鏈表頭指針 
          for(i = 1;i<k&&htemp;i++)     //找到該結(jié)點(diǎn) 
          {
        htemp = htemp->nextNode;
         }
          return htemp;      //返回指向第k個結(jié)點(diǎn)的指針 
} 

輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)k為要查詢的結(jié)點(diǎn)的序號。通過序號進(jìn)行多次循環(huán)，獲得指向該結(jié)點(diǎn)的指針，然后返回指針。

按照關(guān)鍵字查詢

即根據(jù)鏈表中結(jié)點(diǎn)的某一個關(guān)鍵字進(jìn)行查詢，我們以查詢學(xué)生的姓名（name）為例，其示例代碼如下：

復(fù)制代碼代碼如下:

CLType *CLFindNodeKey(CLType *head,string name)
{
 CLType * htemp;
 htemp = head;       //保存鏈表頭指針 
 while(htemp)
 {
  if(htemp->nodeData.name == name) //當(dāng)結(jié)點(diǎn)關(guān)鍵字和傳入關(guān)鍵字相同 
  {
   return htemp;    //返回該結(jié)點(diǎn)指針 
  }
  htemp = htemp->nextNode; 
 }
 return NULL; 
} 

輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)name為要查詢的同學(xué)的姓名。遍歷查詢所有的同學(xué)的姓名，當(dāng)有結(jié)點(diǎn)的姓名與所查詢的姓名相同的時候，則返回該結(jié)點(diǎn)的指針。

插入結(jié)點(diǎn)

插入結(jié)點(diǎn)就是在鏈表中間部分的位置增加一個結(jié)點(diǎn)。

插入結(jié)點(diǎn)的步驟如下：

（1）分配內(nèi)存空間，保存新增的結(jié)點(diǎn)。

（2）找到要插入的邏輯位置，也就是找到插在那個結(jié)點(diǎn)的后面。

（3）修改插入位置結(jié)點(diǎn)的指針，使其指向新增結(jié)點(diǎn)，而使新增結(jié)點(diǎn)指向原插入位置所指向的結(jié)點(diǎn)。

示例代碼如下：

復(fù)制代碼代碼如下:

CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
 CLType *node,*nodetemp;
 if(!(node = new CLType))    //申請結(jié)點(diǎn) 
 {
  cout<<"申請內(nèi)存失敗"<<endl;
  return NULL; 
 } 
 else
 {
  node->nodeData = nodeData;  //保存結(jié)點(diǎn)中的數(shù)據(jù)
  nodetemp=CLFindNodeNum(head,k-1);//通過按照結(jié)點(diǎn)序號查找函數(shù)找到插入點(diǎn)前一個結(jié)點(diǎn)（關(guān)鍵結(jié)點(diǎn)） 
  if(nodetemp)
  {
   node->nextNode = nodetemp->nextNode;//插入的結(jié)點(diǎn)指向關(guān)鍵結(jié)點(diǎn)的下一個節(jié)點(diǎn) 
   nodetemp->nextNode = node;    //關(guān)鍵結(jié)點(diǎn)指向插入點(diǎn) 
  } 
  else
  {
   cout<<"沒有找到正確的插入位置"<<endl;
   delete node;
  }
 } 
 return head;      //返回頭指針 
} 

輸入?yún)?shù)head為鏈表頭指針，輸入?yún)?shù)findkey為鏈表中進(jìn)行查找的結(jié)點(diǎn)關(guān)鍵字，找到該結(jié)點(diǎn)后將在該結(jié)點(diǎn)后面添加結(jié)點(diǎn)數(shù)據(jù)，nodeData為新增結(jié)點(diǎn)的數(shù)據(jù)。程序中首先使用new申請結(jié)點(diǎn)空間，然后調(diào)用CLFindNodeNum函數(shù)查找指向結(jié)點(diǎn)，然后執(zhí)行插入操作。

刪除結(jié)點(diǎn)

刪除結(jié)點(diǎn)就是將鏈表中的某個結(jié)點(diǎn)數(shù)據(jù)刪除，并不影響其位置前后的結(jié)點(diǎn)。

刪除結(jié)點(diǎn)操作的步驟如下：

（1）查找需要刪除的結(jié)點(diǎn)。

（2）使前一結(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的下一結(jié)點(diǎn)。

（3）刪除該結(jié)點(diǎn)

刪除結(jié)點(diǎn)可以通過結(jié)點(diǎn)的序號確定要刪除的結(jié)點(diǎn)，當(dāng)然也可以通過結(jié)點(diǎn)的關(guān)鍵字確定要刪除的結(jié)點(diǎn)。

我們以通過關(guān)鍵字刪除結(jié)點(diǎn)為例，示例代碼如下：

復(fù)制代碼代碼如下:

int CLDeleteNode(CLType *head,string name)
{
 CLType *node,*htemp;    //node用于刪除結(jié)點(diǎn)的前一個結(jié)點(diǎn)
 htemp = head;
 node =  head;
 while(htemp)
 {
  if(htemp->nodeData.name == name)//找到關(guān)鍵字，執(zhí)行刪除操作 
  {
   node->nextNode = htemp->nextNode;//使前一結(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的下一結(jié)點(diǎn)
   delete htemp;     //釋放該結(jié)點(diǎn)的空間（即，刪除了結(jié)點(diǎn)）
   return 1; 
  }
  else
  {
   node = htemp;     //指向當(dāng)前節(jié)點(diǎn) 
   htemp = htemp->nextNode;  //指向下一個結(jié)點(diǎn) 
  } 
 } 
  return 0;        //刪除失敗 
} 

head為鏈表頭指針，輸入?yún)?shù)name表示要刪除的同學(xué)的姓名。程序中，通過一個循環(huán)，按關(guān)鍵字在整個鏈表中查找要刪除的結(jié)點(diǎn)。如果找到被刪除的結(jié)點(diǎn)，則設(shè)置上一結(jié)點(diǎn)（node指針?biāo)附Y(jié)點(diǎn)）指向當(dāng)前結(jié)點(diǎn)（h指針?biāo)附Y(jié)點(diǎn)）的下一個結(jié)點(diǎn)，即在邏輯上將該結(jié)點(diǎn)刪除，然后對該結(jié)點(diǎn)執(zhí)行delete操作，釋放結(jié)點(diǎn)占用的內(nèi)存空間，即在物理上將其刪除。

計算鏈表長度

計算鏈表長度也就是統(tǒng)計鏈表中結(jié)點(diǎn)的數(shù)量。順序表中計算鏈表長度比較方便，但在鏈表中鏈表的長度卻需要通過遍歷鏈表來獲得，因?yàn)殒湵碓谖锢砩喜皇沁B續(xù)存儲的。

示例代碼如下：

復(fù)制代碼代碼如下:

int CLLength(CLType *head)
{
 CLType *htemp;
 int Len = 0;
 htemp = head;
 while(htemp)       //遍歷整個數(shù)組
 {
  Len++;        //累加結(jié)點(diǎn)的數(shù)量
  htemp = htemp->nextNode;    //處理下一個結(jié)點(diǎn) 
 } 
 return Len;
} 

參數(shù)head是鏈表的頭指針，程序中通過while來遍歷指針，Len作為計數(shù)器，通過記錄循環(huán)的次數(shù)，來獲得鏈表的長度，當(dāng)指針為NULL時截止，然后返回計數(shù)器的值。

顯示所有結(jié)點(diǎn)

遍歷所有的結(jié)點(diǎn)，并輸出。

復(fù)制代碼代碼如下:

void CLAllNode(CLType *head) 
{
 CLType *htemp;
 htemp = head;
 while(htemp)       //遍歷整個數(shù)組
 {
  nodeData = htemp->nodeData;   //獲取結(jié)點(diǎn)數(shù)據(jù) 
  cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl; 
  htemp = htemp->nextNode;    //處理下一個結(jié)點(diǎn) 
 } 
}

輸出結(jié)點(diǎn)的函數(shù)，沒有返回值，所有定義為void。每次都通過CLType類型的結(jié)點(diǎn)獲得其nodeData的值

鏈表操作完整示例

完整示例的代碼比較長，要耐心看哈…… :)

復(fù)制代碼代碼如下:

#include<iostream>
#include<string>
using namespace std;
struct Data   //數(shù)據(jù)結(jié)點(diǎn)類型 
{
 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é)點(diǎn)數(shù)據(jù) 
  node->nextNode = NULL;   //設(shè)置結(jié)點(diǎn)指針為空，即作為表尾 
  if(head == NULL)   //當(dāng)鏈表是空表的時候 
  {
   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é)點(diǎn)數(shù)據(jù) 
  node->nextNode = head;  //指向頭指針?biāo)赶虻闹羔?
  head = node;   //頭指針指向新增結(jié)點(diǎn) 
  return head;
 } 
} 
CLType *CLFindNodeNum(CLType *head,int k)
{
 CLType *htemp;
 int i = 1;
 htemp = head;    //保存鏈表頭指針 
    for(i = 1;i<k&&htemp;i++)   //找到該結(jié)點(diǎn) 
    {
     htemp = htemp->nextNode;
    }
    return htemp;     //返回指向第k個結(jié)點(diǎn)的指針 
} 
CLType *CLFindNodeName(CLType *head,string name)
{
 CLType * htemp;
 htemp = head;    //保存鏈表頭指針 
 while(htemp)
 {
  if(htemp->nodeData.name == name) //當(dāng)結(jié)點(diǎn)關(guān)鍵字和傳入關(guān)鍵字相同 
  {
   return htemp;  //返回該結(jié)點(diǎn)指針 
  }
  htemp = htemp->nextNode; 
 }
 return NULL; 
} 
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
 CLType *node,*nodetemp;
 if(!(node = new CLType))   //申請結(jié)點(diǎn) 
 {
  cout<<"申請內(nèi)存失敗"<<endl;
  return NULL; 
 } 
 else
 {
  node->nodeData = nodeData;  //保存結(jié)點(diǎn)中的數(shù)據(jù)
  nodetemp=CLFindNodeNum(head,k-1);    //通過按照結(jié)點(diǎn)序號查找函數(shù)找到插入點(diǎn)前一個結(jié)點(diǎn)（關(guān)鍵結(jié)點(diǎn)） 
  if(nodetemp)
  {
   node->nextNode = nodetemp->nextNode;  //插入的結(jié)點(diǎn)指向關(guān)鍵結(jié)點(diǎn)的下一個節(jié)點(diǎn) 
   nodetemp->nextNode = node;    //關(guān)鍵結(jié)點(diǎn)指向插入點(diǎn) 
  } 
  else
  {
   cout<<"沒有找到正確的插入位置"<<endl;
   delete node;
  }
 } 
 return head;      //返回頭指針 
} 
int CLDeleteNode(CLType *head,string name)
{
 CLType *node,*htemp;    //node用于刪除結(jié)點(diǎn)的前一個結(jié)點(diǎn)
 htemp = head;
 node =  head;
 while(htemp)
 {
  if(htemp->nodeData.name == name)             //找到關(guān)鍵字，執(zhí)行刪除操作 
  {
   node->nextNode = htemp->nextNode;  //使前一結(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的下一結(jié)點(diǎn)
   delete htemp;   //釋放該結(jié)點(diǎn)的空間（即，刪除了結(jié)點(diǎn)）
   return 1; 
  }
  else
  {
   node = htemp;   //指向當(dāng)前節(jié)點(diǎn) 
   htemp = htemp->nextNode;  //指向下一個結(jié)點(diǎn) 
  } 
 } 
  return 0;     //刪除失敗 
} 
int CLLength(CLType *head)
{
 CLType *htemp;
 int Len = 0;
 htemp = head;
 while(htemp)     //遍歷整個數(shù)組
 {
  Len++;     //累加結(jié)點(diǎn)的數(shù)量
  htemp = htemp->nextNode;    //處理下一個結(jié)點(diǎn) 
 } 
 return Len;
} 
void CLAllNode(CLType *head) 
{
 CLType *htemp;
 Data nodeData; 
 htemp = head;
 cout<<"鏈表長度為："<<CLLength(head)<<endl;
 while(htemp)     //遍歷整個數(shù)組
 {
  nodeData = htemp->nodeData;   //獲取結(jié)點(diǎn)數(shù)據(jù) 
  cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl; 
  htemp = htemp->nextNode;    //處理下一個結(jié)點(diǎn) 
 } 
}
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é)點(diǎn) 
 }
 CLAllNode(head);     //顯示所有的結(jié)點(diǎn)
 //演示在頭部插入數(shù)據(jù) 
 cout<<"請輸入一個結(jié)點(diǎn)，并在鏈表的頭部插入"<<endl;
 cin>>nodeData.key>>nodeData.name>>nodeData.age;
 head=CLAddFirst(head,nodeData);
 CLAllNode(head);
 //演示在中間位置插入一個數(shù)據(jù)
 cout<<"請輸入一個在鏈表內(nèi)部插入的結(jié)點(diǎn)："<<endl; 
 cin>>nodeData.key>>nodeData.name>>nodeData.age;
 cout<<"請輸入插入點(diǎn)的位置：";
 cin>>k;
 head=CLInsertNode(head,k,nodeData);
 CLAllNode(head); 
 //演示按照序號查詢數(shù)據(jù) 
 cout<<"請輸入按照結(jié)點(diǎn)查詢的一個結(jié)點(diǎn)序號：";
 cin>>k;
 node=CLFindNodeNum(head,k);
 cout<<"您所查詢的結(jié)點(diǎn)是："<<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é)點(diǎn)是："<<endl;
 cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
 //演示刪除數(shù)據(jù)信息 
 cout<<"請輸入結(jié)點(diǎn)中的一個同學(xué)中的名字，系統(tǒng)會刪除他的信息：";
 cin>>name;
 if(CLDeleteNode(head,name))cout<<"數(shù)據(jù)刪除成功！"<<endl;
 CLAllNode(head);
 return 0; 
}