https://www.cnblogs.com/953-zjf/p/LinkList.html
(一)連結清單的幾個基本概念
頭節點：是單連結清單的頭 ，是一個特殊的節點，隻有指針域，沒有資料域。
節點：由兩部分構成，第一部分是資料域，存儲的是該節點的内容，第二部分是指針域，用來存儲下一節點的位址，通過改位址可以通路下一個節點。
單連結清單：由頭節點和若幹節點組成的連結清單。
這是一個有三個節點的連結清單。
(二)連結清單的存儲結構
(1)從上篇文章我們得知順序表在計算機中存儲的位置是連續的，就像宿舍樓一層的房間，都是相鄰的，但連結清單不一樣，連結清單不一定是相鄰的，隻不過每一個節點都會存儲下一個節點的位址。比如說，小明有小紅的位址，小紅呢有小白的位址，小白又有小蘭的位址，小黑有小明的位址，他們五個是一個班的，是以他們之間就形成了一個關系：
這就是一個單連結清單的結構，單是指隻有前驅節點有後繼節點的位址，隻有單向性，當然也有雙向連結清單，後面遇到了我們再講。
(2)上面是我們自己抽象化的一個連結清單，在計算機中的存儲結構是下圖：
(三)代碼分析
(1)頭檔案
#include //基本的輸入輸出using namespace std; //聲明命名空間#include //字元串頭檔案
(2)預處理
#define OK 1#define ERROR 0#define ElemType int
(3)建立節點，很明顯，這裡要用到結構體，結構體有兩個成員，一個是資料域，一個是指針域。
typedef struct LNode{ struct LNode *next; //節點指針域 string data; //節點資料域}*LinkList,LNode; //一個是結構體指針，一個是結構體名稱
(4)初始化函數，建立一個頭節點，并将指針域置空。
ElemType Init_Linklist(LinkList &L) //初始化連結清單{ L = new LNode; //建立一個頭節點 L->next = NULL; //并将頭節點的指針域置空 return OK;}
(5)輸對外連結表函數，這個函數呢，是将單連結清單中的每個元素按順序輸出，為了美觀，用"->"隔開。 實作步驟： ①定義一個節點指針，指向第一個節點。(注意：這裡的第一個節點是頭節點之後的第一個。) ②while判斷目前節點是否為空，如果不是空，就輸出該節點内容，然後指針下移，下面的if是最後一個節點不輸出"->"，這樣連結清單看起來會更美觀。
void Printf_LNode(LinkList L) //周遊輸對外連結表内容{ cout<<"連結清單内容："; LNode *p = L->next; //節點指針，用來周遊節點 while(p) { cout<data; //輸出節點的資料域 p = p->next; if(p) //判斷下一個節點是否為空，如果是就不輸出"->" { cout<<"->"; } } cout<<endl;}
(6)前插法建立連結清單，即每次在第一個節點的位置插入新節點。咱們先自己想一下這個過程，首先，我們要建立一個節點吧，然後将新節點的指針域指向下一個節點，再把上一個節點的指針域指向自己，不就插入成功了嘛。看一下圖檔：
實作步驟： ①輸出提醒，并得到你要建立節點的個數n。 ②建立一個節點指針，便于後面改指針的操作。 ③初始化頭節點，并将指針域置空。 ④要建立n個節點，自然需要循環n次，首先開辟一個新節點，并讓p指向新節點，将新節點的指針指向下一個節點，再讓上一個節點指向自己，然後在輸入該節點的内容。 ⑤輸對外連結表。
void Create_LinkList_h(LinkList &L) //前插法建立單連結清單{ int n; cout<<"請輸入你要建立的連結清單的結點個數:"; cin>>n; LNode *p; L = new LNode; //初始化頭節點 L->next = NULL; cout<<"将要采用頭插法建立單連結清單，請逆序輸入"<"個節點内容:"; for(int i = 0;i < n;i++) //循環建立節點 { p = new LNode; p->next = L->next; L->next = p; cin>>p->data; } Printf_LNode(L); //輸對外連結表内容}
(7)後插法建立連結清單，尾插法是将每個元素插在最後，故稱為後插法。與前插法大緻相同，不過比前插法多一個節點指針，首先建立一個節點，然後自己的指針域為空，因為自己已經是最後一個節點了，然後讓上一個節點指向自己，然後插入成功。 實作步驟： ①首先得到你要輸入的節點個數n ②初始化頭節點 ③定義一個節點指針r，并指向L ④循環n次，每一次都先申請一個節點，輸入節點内容，因為是後插，是以每一個節點的指針域都指向空，然後再讓上一個節點指向自己，然後r後移一個節點。
void Create_LinkList_r(LinkList &L) //尾插法建立連結清單{ int n; //節點個數 cout<<"請輸入你要建立的連結清單的結點個數:"; cin>>n; L = new LNode; //初始化頭節點 L->next = NULL; LNode *r = L; cout<<"将要采用尾插法建立單連結清單，請輸入"<"個節點内容:"; for(int i = 0;i < n;i++) //循環建立節點 { LNode *p; p = new LNode; cin>>p->data; p->next = NULL; r->next = p; r = p; } Printf_LNode(L);}
(8)取值，通過輸入的位置， 周遊連結清單，找到對應位置的值，然後指派即可。 實作步驟： ①首先輸入你要取得元素的位置 ②定義一個新的節點指針，并指向頭節點的下一個節點，同時呢也定義一個j，用來記錄節點的值。 ③用while循環，讓指針連續下移到相應位置，同時判斷j的值是否達到n。 ④如果已經移到空節點了，或者說j已經大于n了，就表明越界了。 ⑤如果沒有越界，就指派即可。
ElemType Get_ElemType(LinkList L,string &name){ int n; //元素位置 cout<<"請輸入你要取得元素的位置:"; cin>>n; LNode *p = L->next; //建立節點指針，并指向下一個節點 int j = 1; while(p&&j//指針移到要取得位置 { p = p->next; j++; } if(!p || j>n) //判斷是否越界 { return ERROR; } name = p->data; //取值}
(9)插入節點，其實也就是先開辟一個節點，然後讓新節點指向下一個節點，再讓新節點的上一個節點指向自己，就插入成功了。 實作步驟： ①首先得到你要插入的位置 ②定義一個節點指針，指向第一個節點 ③指針連續下移，移到n-1的節點。 ④判斷是否越界 ⑤建立一個節點和一個指向新節點的指針s，然後輸入插入的節點的值。 ⑥改指針，将上一個節點的指針賦給新節點，然後讓上一個節點指向自己，就插入成功了。
ElemType Insert_LNode(LinkList &L) //插入節點函數{ int n; //插入得位置 cout<<"請輸入你要插入的位置："; cin>>n; LNode *p = L->next; int j = 1; while(p&&j1)) { p = p->next; j++; } if(!p || j > (n - 1)) //判斷是否越界 { return ERROR; } LNode *s; //指向建立節點的指針 s = new LNode; cout<<"請輸入你要插入的元素:"; cin>>s->data; //輸入新節點的資料域内容 s->next = p->next; p->next = s; Printf_LNode(L); //輸出單連結清單}
(10)删元素，其實跟之前插元素的實作差不多，都是先移到你要删除的位置，然後把你想要删除節點的指針域賦給前一個節點，然後釋放節點即可。 實作步驟： ①輸出一邊目前連結清單的内容，然後挑選并得到你要删除的位置，同時定義一個節點指針q。 ②定義一個節點指針指向第一個節點，并定義一個計數變量j。 ③指針p連續下移到要删除的元素的前一個位置，然後在把該節點的指針域(q = p->next)，賦給節點指針q，這樣q就指向了我們要删除的節點，然後讓q指向我們要删除的節點的下一個節點，然後釋放q節點即可。
ElemType Del_LNode(LinkList &L) //删除節點函數{ int n; LNode *q; //首先定義一個節點指針 Printf_LNode(L); cout<<"請輸入你要删除的位置:"; cin>>n; LNode *p = L->next; int j = 1; while(p&&(j< n - 1)) //指針下移 { p = p->next; ++j; } if(!p || j > (n - 1)) //判斷是否越界 { return ERROR; } q = p->next; p->next = q->next; delete q; Printf_LNode(L);}
(11)菜單函數，隻是一些普通的輸出，就不用解釋了吧。
void Menu() //菜單函數{ cout<<"<<<<<<<<<<<<<<>>>>>>>>>>>>>>"<<endl; cout<<"1.初始化單連結清單"<<endl; cout<<"2.頭插法建立一個單連結清單"<<endl; cout<<"3.尾插法建立一個單連結清單"<<endl; cout<<"4.取單連結清單中的某個元素"<<endl; cout<<"5.在單連結清單某個位置插入元素"<<endl; cout<<"6.在單連結清單删除某個位置的元素"<<endl; cout<<"7.輸對外連結表内容"<<endl; cout<<"8.菜單"<<endl; cout<<"9.退出系統！"<<endl; cout<<"輸入對應選項，執行對應操作"<<endl;}
(12)主函數：首先建立一個連結清單指針，輸出菜單，然後進入while循環，通過switch輸入不同的選項進入不同的case，然後執行不同的函數，這裡為了能夠退出系統(跳出循環)使用了goto語句來結束循環。這裡需要特别說明的可能就是case 4和case 5，定義了兩個标志變量，用來記錄程式退出的值，看是否出錯。
int main(){ LinkList La; //連結清單指針 int select; Menu(); while(1) //循環輸入選項 { cout<<"請輸入選項："; cin>>select; switch(select) //判斷選項，并執行對應的函數 { case 1: { Init_Linklist(La); cout<<"初始化後單連結清單為空，要想進行操作，請先建立一個單連結清單"<<endl; Create_LinkList_h(La); break; } case 2: { Create_LinkList_h(La); break; } case 3: { Create_LinkList_r(La); break; } case 4: { int flag; //标志變量，用來記錄退出碼，用來判斷是否為正常退出 string name; flag = Get_ElemType(La,name); if(!flag) { cout<<"取出失敗，越界!"<<endl; } cout<endl; break; } case 5: { int flag; flag = Insert_LNode(La); //标志變量，用來記錄退出碼，用來判斷是否為正常退出 if(!flag) { cout<<"插入失敗,越界！"<<endl; } break; } case 6: { Del_LNode(La); break; } case 7: { Printf_LNode(La); break; } case 8: { Menu(); break; } case 9: { cout<<"多謝使用"<<endl; goto unloop; //使用goto語句，跳轉，使程式結束 } default: { cout<<"輸入有誤！"<<endl; break; } } } unloop:return 0; //跳轉到程式結束語句}
(四)完整代碼
#include //基本的輸入輸出using namespace std; //聲明命名空間#include //字元串頭檔案#define OK 1#define ERROR 0#define ElemType inttypedef struct LNode{ struct LNode *next; //節點指針域 string data; //節點資料域}*LinkList,LNode; //一個是結構體指針，一個是結構體名稱ElemType Init_Linklist(LinkList &L) //初始化連結清單{ L = new LNode; //建立一個頭節點 L->next = NULL; //并将頭節點的指針域置空 return OK;}void Printf_LNode(LinkList L) //周遊輸對外連結表内容{ cout<<"連結清單内容："; LNode *p = L->next; //節點指針，用來周遊節點 while(p) { cout<data; //輸出節點的資料域 p = p->next; if(p) //判斷下一個節點是否為空，如果是就不輸出"->" { cout<<"->"; } } cout<<endl;}void Create_LinkList_h(LinkList &L) //前插法建立單連結清單{ int n; cout<<"請輸入你要建立的連結清單的結點個數:"; cin>>n; LNode *p; L = new LNode; //初始化頭節點 L->next = NULL; cout<<"将要采用頭插法建立單連結清單，請逆序輸入"<"個節點内容:"; for(int i = 0;i < n;i++) //循環建立節點 { p = new LNode; p->next = L->next; L->next = p; cin>>p->data; } Printf_LNode(L); //輸對外連結表内容}void Create_LinkList_r(LinkList &L) //尾插法建立連結清單{ int n; //節點個數 cout<<"請輸入你要建立的連結清單的結點個數:"; cin>>n; L = new LNode; //初始化頭節點 L->next = NULL; LNode *r = L; cout<<"将要采用尾插法建立單連結清單，請輸入"<"個節點内容:"; for(int i = 0;i < n;i++) //循環建立節點 { LNode *p; p = new LNode; cin>>p->data; p->next = NULL; r->next = p; r = p; } Printf_LNode(L);}ElemType Get_ElemType(LinkList L,string &name){ int n; //元素位置 cout<<"請輸入你要取得元素的位置:"; cin>>n; LNode *p = L->next; //建立節點指針，并指向下一個節點 int j = 1; while(p&&j//指針移到要取得位置 { p = p->next; j++; } if(!p || j>n) //判斷是否越界 { return ERROR; } name = p->data; //取值}ElemType Insert_LNode(LinkList &L) //插入節點函數{ int n; //插入得位置 cout<<"請輸入你要插入的位置："; cin>>n; LNode *p = L->next; int j = 1; while(p&&j1)) { p = p->next; j++; } if(!p || j > (n - 1)) //判斷是否越界 { return ERROR; } LNode *s; //指向建立節點的指針 s = new LNode; cout<<"請輸入你要插入的元素:"; cin>>s->data; //輸入新節點的資料域内容 s->next = p->next; p->next = s; Printf_LNode(L); //輸出單連結清單}ElemType Del_LNode(LinkList &L) //删除節點函數{ int n; LNode *q; //首先定義一個節點指針 Printf_LNode(L); cout<<"請輸入你要删除的位置:"; cin>>n; LNode *p = L->next; int j = 1; while(p&&(j< n - 1)) //指針下移 { p = p->next; ++j; } if(!p || j > (n - 1)) //判斷是否越界 { return ERROR; } q = p->next; p->next = q->next; delete q; Printf_LNode(L);}void Menu() //菜單函數{ cout<<"<<<<<<<<<<<<<<>>>>>>>>>>>>>>"<<endl; cout<<"1.初始化單連結清單"<<endl; cout<<"2.頭插法建立一個單連結清單"<<endl; cout<<"3.尾插法建立一個單連結清單"<<endl; cout<<"4.取單連結清單中的某個元素"<<endl; cout<<"5.在單連結清單某個位置插入元素"<<endl; cout<<"6.在單連結清單删除某個位置的元素"<<endl; cout<<"7.輸對外連結表内容"<<endl; cout<<"8.菜單"<<endl; cout<<"9.退出系統！"<<endl; cout<<"輸入對應選項，執行對應操作"<<endl;}int main(){ LinkList La; //連結清單指針 int select; Menu(); while(1) //循環輸入選項 { cout<<"請輸入選項："; cin>>select; switch(select) //判斷選項，并執行對應的函數 { case 1: { Init_Linklist(La); cout<<"初始化後單連結清單為空，要想進行操作，請先建立一個單連結清單"<<endl; Create_LinkList_h(La); break; } case 2: { Create_LinkList_h(La); break; } case 3: { Create_LinkList_r(La); break; } case 4: { int flag; //标志變量，用來記錄退出碼，用來判斷是否為正常退出 string name; flag = Get_ElemType(La,name); if(!flag) { cout<<"取出失敗，越界!"<<endl; } cout<endl; break; } case 5: { int flag; flag = Insert_LNode(La); //标志變量，用來記錄退出碼，用來判斷是否為正常退出 if(!flag) { cout<<"插入失敗,越界！"<<endl; } break; } case 6: { Del_LNode(La); break; } case 7: { Printf_LNode(La); break; } case 8: { Menu(); break; } case 9: { cout<<"多謝使用"<<endl; goto unloop; //使用goto語句，跳轉，使程式結束 } default: { cout<<"輸入有誤！"<<endl; break; } } } unloop:return 0; //跳轉到程式結束語句}
(五)運作結果
程式在健壯性方面還有很多不足，各位大神如果有什麼好的想法或者發現我的某些錯誤，歡迎指正！最後希望大家給我一個支援，謝謝！