理论基础 —— 线性表 —— 单链表
【實現類】
單鏈表的基本思想就是用指針表示結點之間的邏輯關系，因此要正確的對指針變量、指針、指針所指結點、結點的值進行區分。
設 p 是一個指針變量，則 p 的值是一個指針，若指針?p 指向某個 Node 類型的結點，則該結點用 *p 來表示，并稱?*p 為結點變量，有時為了敘述方便，常將 " 指針變量 " 稱為 " 指針 "，將 " 指針 p 所指的結點 " 稱為 " 結點 p "。
在單鏈表中，結點 p 由兩個域組成，其中，存放數據元素的部分用 p->data 表示，其值是一個數據元素；存放后繼結點地址的指針部分用 p->next 表示，其值是一個指針。
template <class T> struct Node{//結點T data;//數據域Node *next;//指針域 };template <class T> class linkList{ private:Node<T> *first;//頭指針 public:linkList();//無參構造函數linkList(T a[],int n);//有參構造函數~linkList();//析構函數int getLength();//獲取單鏈表的長度T getElement(int i);//獲取單鏈表的第i個元素int getPosition(T x);//獲取單鏈表中值為x的元素序號void insertElement(int i,T x);//在單鏈表中第i個位置插入值為x的元素T deleteElement(int i);//刪除單鏈表的第i的元素void print();//按序號依次輸出單鏈表各元素 };【構造函數】
1.帶頭結點的構造函數
1）無參構造函數
帶頭結點的無參構造函數，只需要生成一個頭結點，讓頭指針指向頭結點，并將頭結點的指針域置空。
template <class T> linkList<T>::linkList(){//無參構造函數first=new Node<T>;//頭指針指向頭結點first->next=NULL;//頭結點的指針域置為空 }2）頭插法的有參構造函數
頭插法就是每次將新申請的結點插到頭結點的后面，即始終讓新結點在第一的位置。
使用頭插法建立有參構造函數，首先應建立一個頭結點，讓頭指針指向頭結點，同時將頭結點的指針域置空（與無參構造函數相同），此后，對于 n 個數組元素：
- 建立一個結點，為結點的數據域賦值
- 將新結點的指針域指向頭結點的指針域所指向的地址
- 令頭結點的指針域指向新結點
3）尾插法的有參構造函數
尾插法就是每次將新申請的結點插到終端結點的后面，即始終讓新結點在最后的位置。
使用尾插法建立有參構造函數，首先應建立一個頭結點，然后再建立一個尾指針，代表單鏈表中最后一個數據元素的位置。此后，對于 n 個數據元素：
- 建立一個結點，為結點的數據域賦值
- 將尾指針指針域指向新建立的結點
- 更改尾指針地址為新結點地址
最后，當單鏈表建立完畢時，將尾指針的指針域置空
template <class T> linkList<T>::linkList(T a[],int n){//尾插法的有參構造函數first=new Node<T>;Node<T> *r=first;//尾指針初始化for(int i=0;i<n;i++){Node<T> *s=new Node<T>;//建立一個新結點s->data=a[i];為新結點數據域賦值r->next=s;//尾指針指針域指向新結點r=s;//更改尾指針地址為新結點地址}r->next=NULL;//單鏈表建立完畢，將尾指針指針域置空 }2.不帶頭結點的構造函數
1）無參構造函數
不帶頭結點的無參構造函數，只需讓頭指針指向為空。
template <class T> linkList<T>::linkList(){//無參構造函數first=NULL;//頭指針置為空 }2）頭插法的有參構造函數
頭插法就是每次將新申請的結點插到頭結點的后面，即始終讓新結點在第一的位置。
使用頭插法建立有參構造函數，首先令頭指針置為空（與無參構造函數相同），此后，對于 n 個數組元素：
- 建立一個結點，為結點的數據域賦值
- 將新結點的指針域指向頭指針所指向的地址
- 更改頭指針地址為新結點地址
?3）尾插法的有參構造函數
尾插法就是每次將新申請的結點插到終端結點的后面，即始終讓新結點在最后的位置。
使用尾插法建立有參構造函數，首先令頭指針置為空（與無參構造函數相同），再建立一個尾指針，代表單鏈表中最后一個數據元素的位置，然后建立一個初始結點，將其作為頭結點：
- 初始結點的數據域賦值為第 1 個數據元素的值
- 初始結點的指針域指向頭指針指向的地址
- 更改頭指針地址為初始結點地址
- 更改尾指針地址為初始結點地址。
此后，對于 n 個數據元素：
- 建立一個結點，為結點的數據域賦值
- 將尾指針指針域指向新建立的結點
- 更改尾指針地址為新結點地址
?3.帶頭結點和不帶頭結點的單鏈表的比較
| 操作 | 帶頭結點 | 不帶頭結點 |
| 空表 | first=new node<T>; first->next=NULL; | first=NULL |
| 在空表中插入一個結點 s | Node<T> *s=new node<T>; s->next=first->next; | Node<T> *s=new node<T>; first=s; |
| 插入一個結點，使其成為首元結點 | Node<T> *s=new node<T>; s->next=first->next; | Node<T> *s=new node<T>; s->next=first; |
| 在某一結點 p 后插入結點 s | Node<T> *s=new node<T>; s->next=p->next; | Node<T> *s=new node<T>; s->next=p->next; |
【析構函數】
單鏈表中的結點是用 new 申請的，在釋放單鏈表的對象時無法自動釋放這些結點的存儲空間，因此析構函數應將單鏈表中的結點的存儲空間釋放
template<class T> linkList<T>::~linkList(){while(first!=NULL){Node<T> *q=first;//暫存要被釋放的結點first=first->next;//first指向要被釋放的結點的下一個結點delete q;//刪除結點} }【獲取線性表長度】
求單鏈表的長度時，在將單鏈表掃描同時建立一個累加器，直到掃描到鏈表尾，時間復雜度為 O(n)
template<class T> int linkList<T>::getLength(){int count=0;//累加器Node<T> p=first->next;//工作指針while(p!=NULL){//p不為空p=p->next;//指向下一結點count++;//累加器+1}return count; }【查找元素】
1.按位查找
按位查找時，不能像順序表按序號訪問，只能從頭指針出發順著 next 域逐個結點向下搜索
- 工作指針 p、位置累加器初始化
- 直到 p 為空或指向第 i 個節點：工作指針后移、位置累加器+1
- 若 p 為空，則第 i 個元素不存在，拋出位置異常；否則查找成功，返回節點 p 的數據元素
2.按值查找
按值查找時，需要對單鏈表中的元素依次進行比較，時間復雜度為 O(n)
- 工作指針 p、位置累加器初始化
- 直到 p 為空：工作指針后移、位置累加器+1
- 若在循環中找到元素，則返回序號，即位置累加器的值；若退出循環，則查找失敗，單鏈表中沒有相關值
【插入操作】
1.帶頭結點的插入
在單鏈表中的第 i 個位置插入元素，需要先找到第 i-1 個元素，若找不到則拋出位置異常，若找到則將新結點插入位置 i
- 工作指針 p 、位置計數器初始化
- 查找第 i-1 個節點，并使工作指針 p 指向該節點
- 若查找不成功(P==NULL)，說明位置錯誤，拋出位置異常，否則生成一個元素值為 x 的新節點 s，并將 s 插入到 p 之后
2.不帶頭結點的插入
不帶頭結點的插入與帶頭結點的插入十分相似，區別僅在于當插入位置是第一個位置時
template<class T> void linkList<T>::insertElement(int i,T x){if(i==1){//若在第一個位置插入Node<T> *s=new Node<T>;//新申請一個結點s->next=first;//新結點的指針域指向頭指針所指向的結點first=s;//令頭指針指向新結點return;}int pos=1;//位置累加器Node<T> *p=first;//工作指針while(p!=NULL&&pos<i-1){//p不為空且位置小于i-1p=p->next;//指向下一結點pos++;//累加器+1}if(p==NULL)throw "插入位置異常";else{Node<T> *s=new Node<T>;//新申請一個結點s->data=x;//新結點數據域賦值為xs->next=p->next;//新結點s指向工作結點p之后的結點p->next=s;//工作結點p指向新結點s} }【刪除操作】
在單鏈表中刪除第 i 個位置的元素，需要先找到第 i-1 個元素，若找不到則拋出位置異常，若找到將第 i-1 個結點指針域所指向的結點刪除
- 工作指針 p 、位置計數器初始化
- 查找第 i-1 個節點，并使工作指針 p 指向該節點
- 若查找不成功(P==NULL)，說明位置錯誤，拋出位置異常，否則將被刪結點從鏈表中摘下并釋放存儲空間
【遍歷輸出】
遍歷輸出即按照單鏈表的指針指向依次輸出線性表各元素
- 建立一個臨時結點，令臨時結點地址為頭指針指向的結點
- 當臨時結點不為空時，輸出數據域，并指向下一結點
?
總結
以上是生活随笔為你收集整理的理论基础 —— 线性表 —— 单链表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 剪花布条（HDU-2087）
- 下一篇： Blackboard Fibonacci