C++ "鏈鏈"不忘@必有迴響之雙向鏈表

C++ "鏈鏈"不忘@必有迴響之雙向鏈表

1. 前言

寫過一篇與單鏈表相關的博文（//blog.51cto.com/gkcode/5681771），實際應用中，雙向循環鏈表的功能更強大。

單鏈表中，查詢一個已知結點的後驅結點的時間複雜度為O(1)。因結點本身不存儲與前驅結點相關的地址資訊，查詢前驅結點需要從頭結點掃描一次，所以時間複雜度是O(n)。

雙向鏈表在結點類型中增加了可以存儲前驅結點地址的指針位，如下圖所示：

8.png

如此，無論查詢已知結點的後驅結點還是前驅結點的時間複雜度都是O(1)，缺點是需要付出空間上的代價。

在權衡演算法性能時，會優先考慮時間複雜度的優劣，往往會採用空間換時間的策略。

結點的類型定義：

typedef int dataType;
//結點
struct LinkNode {
	//數據成員
	dataType  data;
	//後驅結點的地址
	LinkNode *next;
	//前驅結點的地址
	LinkNode *pre;
	//構造函數
	LinkNode(dataType data) {
		this->data=data;
		this->next=NULL;
		this->pre=NULL;
	}
};

2. 雙向鏈表

雙向鏈表中除了有存儲頭結點的head指針變數外，一般還會增加一個存儲尾結點的tail指針變數。這樣，可以實現從頭至尾或從尾至頭對鏈表進行遍歷。

為了操作的方便，初始化鏈表時都會提供一個空白的頭結點作為標識結點。

在雙向鏈表中，如果尾結點的後驅指針位存儲頭結點地址，頭結點的前驅指針位存儲尾結點地址，如此形成一個首尾相連的閉環，則稱此鏈表為雙向循環鏈表。

9.png

雙向鏈表需要提供對結點上的數據進行常規維護的操作，如：

  • 鏈表初始化。
  • 創建鏈表。
  • 查找。
  • 後插入、前插入。
  • 刪除。
  • ……

演算法的整體思路和單鏈表相似，因結點中多了一個前驅結點資訊，為各種操作帶來便利的同時，也多了需要關注的細節。
下文將介紹雙向鏈表中的幾個重要函數。

2.1 初始化

如果是雙向循環鏈表，初始化時：

  • head和tail指向空白頭結點。
  • 且head的前驅結點和tail的後驅結點也指向空白頭結點。這個過程也可以放到創建鏈表時實現。

11.png

class LinkList {
	private:
		//頭指針
		LinkNode *head;
    	//尾指針
		LinkNode *tail;
		//鏈表的長度
		int length;
	public:
        //構造函數
		LinkList() {
			this->initLinkList();
		}
		//初始化鏈表
		void  initLinkList() {
             //頭指針存儲空白頭結點地址
			this->head=new LinkNode(0);
			//尾指針和頭指針位置相同
			this->tail=this->head;
             //尾結點的後驅結點是頭結點
			this->tail->next=this->head;
             //頭結點的前驅結點是尾結點
			this->head->pre=this->tail; 
		}
       //……其它函數

2.2 創建鏈表

可以使用頭部插入或尾部插入演算法創建鏈表，本文僅介紹尾部插入創建演算法，頭部創建演算法可自行了解。如下演示使用尾部創建法構建以數列{7，3}為數據的鏈表。

  • 創建值為7的新結點n。

10.png

  • 設置新結點n的前驅結點為原尾結點。
n->pre=tail;

12.png

  • 設置新結點n的後驅結點為原尾結點的後驅結點。
n->next=tail->next;

13.png

  • 設置原尾結點的後驅結點為新結點n。
tail->next=n;

14.png

  • 新結點n成為新的尾結點。
tail=n;

15.png

  • 設置頭結點的前驅結點為新的尾結點。
head->pre=tail;

16.png

重複上述流程，最終完成鏈表的創建過程。

17.png

是否可以無視上述創建流程中的順序？

全局而言，順序基本是要遵循上述的要求，原則是新結點->尾結點->頭結點。

  • 新結點：先設置新結點的前驅和後驅結點的地址。新結點的相應存儲位都是空白的，先設置前驅還是後驅不影響結果。
  • 尾結點：修改原尾結點的後驅結點地址為新結點，原尾結點的使命完成後，再指定新結點為新的尾結點。
  • 頭結點：修改頭結點的前驅地址為新尾結點。

編碼實現：

//尾部插入方式創建鏈表
void createFromTail(int n) {
	LinkNode *newNode,*p,*tail;
	//頭結點地址
	p=this->head;
    //尾結點地址
    tail=this->tail;
    for(int i=0; i<n; i++) {
        //構建一個新結點
        newNode=new LinkNode(0);
        cout<<"請輸入結點數據"<<endl;
        cin>>newNode->data;
        //原來的尾結點成為新結點的前驅結點
        newNode->pre=tail;
        //新結點的後驅結點為原來的尾結點的後驅結點 
        newNode->next=tail->next;
        //原尾結點的後驅結點為新結點
        tail->next=newNode; 				
        //新結點成為新的尾結點
        tail=newNode;
        //頭結點的前驅為新尾結點
        head->pre=tail; 
    }
    this->head=p;
    this->tail=tail;
}

測試尾部創建：

int main(int argc, char** argv) {
	LinkList list {};
	list.createFromTail(2);
	//沒刪除之前
	cout<<"顯示創建結果:"<<endl;
	LinkNode *head= list.getHead();
	cout<<"從頭結點向尾結點方向搜索："<<endl;
	cout<<head->next->data<<endl;
	cout<<head->next->next->data<<endl;
	LinkNode *tail=list.getTail();
	cout<<"從尾結點向頭結點方向搜索 ："<<endl;
	cout<<tail->data<<endl;
	cout<<tail->pre->data<<endl; 
	head=tail->next;
	cout<<"從尾結點的後驅資訊位得到頭結點資訊 ："<<endl;
	cout<<head->next->data<<endl;
	cout<<head->next->next->data<<endl;
	return 0;	
}

執行結果：

18.png

2.3 查找

因雙向循環鏈表的頭尾是相連的，其查詢方案可以有多種變化：

  • 按位置查找： 按位置查找建議從頭結點開始。
  • 按值查找： 按值查找可以從頭結點或從尾結點開始。
  • 查詢所有： 查詢所有可以從頭結點也可以從尾結點開始。

2.3.1 按位置查找

設空白頭結點編號為0，從頭結點向尾結點掃描過程中，給掃描到的結點依次編號，當查詢到和指定參數相同的編號時停止。

//按位置查詢結點（從頭部掃描到尾部） 
LinkNode * findNodeByIndex(int index) {
    int j=0;
    LinkNode *p=this->head;
    if(index==j)
        //如果 index 值為 0 ，返回空白頭結點
        return p;
    //第一個數據結點	
    p=p->next;
    //設置第一個數據結點的編號為 1 ，當然這不是絕對，可以根據自己的需要設置編號
    j=1;
    while(p!=this->head && j<index) {
        p=p->next;
        j++;
    }
    if(j==index)return p;
    else return NULL;
}

2.3.2 按值查找

按值查找可以有 2 種方案：

  • 頭結點向尾結點方向查找。
//按值查詢結點
LinkNode * findNodeByVal(dataType val) {
    //從第一個數據結點開始查找
    LinkNode *p=this->head->next;
    //當 p 再次指向頭結點結束查找，這也空白結點存在的意義
    while(p!=this->head && p->data!=val ) {
        p=p->next;
    }
    if(p!=this->head) {
        return p;
    } else {
        return NULL;
    }
}
  • 尾結點向頭結點方向查找。
LinkNode * findNodeByValFromTail(dataType val) {
    //從尾結點開始查找
    LinkNode *p=this->tail;
    while(p!=this->head && p->data!=val ) {
        //向頭結點方向
        p=p->pre;
    }
    if(p!=this->head) {
        return p;
    } else {
        return NULL;
    }
}

2.3.3 查詢所有

  • 從頭結點向尾結點方向查詢所有結點。
void showSelf() {
    if(this->head==NULL)return;
    //得到第一個數據結點
    LinkNode *p=this->head->next;
    while(p!=this->head) {
        cout<<p->data<<"\t";
        p=p->next;
    }
}
  • 從尾結點向頭結點方向查詢所有結點。
void showSelf_() {
    if(this->tail==NULL)return;
    LinkNode *p=this->tail;
    while(p!=this->head) {
        cout<<p->data<<"\t";
        p=p->pre;
    }
}

2.4 插入

插入有前插入和後插入 2 種方案，於雙向鏈表而言，其時間複雜度都為O(1)。

2.4.1 後插入

把新結點插入到已知結點的後面，稱為後插入，其插入流程如下所示：

  • 找到已知結點p，創建新結點n。

19.png

  • 設置n結點的前驅結點為已知結點p，設置其後驅結點為已知結點p的後驅結點。
n->pre=p;
n->next=p->next;

21.png

  • 設置p結點的後驅結點為n結點。
p->next=n;

22.png

  • 設置結點n為其後驅結點的前驅結點。
n->next->pre=n;

23.png

編碼實現：

	//後插入
int instertAfter(dataType val,dataType data) {
    //按值查找到結點
    LinkNode *p=this->findNodeByVal(val);
    if (p==NULL) {
        //結點不存在，返回 false
        return false;
    }
    //創建新結點
    LinkNode *n=new LinkNode(0);
    n->data=data;
    //設置 p 結點為新結點的前驅結點 
    n->pre=p;
    //新結點的後驅結點為已知結點 p 的後驅結點
    n->next=p->next;
    //已知結點的後驅結點為新結點
    p->next=n;  
    //已知結點的原後驅結點的前驅結點為新結點
    n->next->pre=n;
    return true;
}

測試後插入：

int main(int argc, char** argv) {
	LinkList list {};
	//創建 7,3 兩個結點
    list.createFromTail(2);
    //在結點 7 後面插入值為 9 的結點
	list.instertAfter(7,9);
	list.showSelf();
    return 0;
}

執行結果：

24.png

2.4.2 前插入

把新結點插入到已知結點的前面，稱為前插入，因結點有前驅結點的地址資訊，雙向鏈表的前或後插入都較方便。

  • 找到已知結點p，創建新結點n。

25.png

  • 設置結點n的前驅結點為p的前驅結點，設置其後驅結點為p結點。
n->pre=p->pre;
n-next=p;

26.png

  • 設置p結點的前驅結點的後驅結點為n。
p->pre->next=n;
或
n->pre->next=n;

27.png

  • 設置p結點的前驅結點為n結點。
p->pre=n;

28.png

編碼實現：

//前插入
int insertBefore(dataType val,dataType data) {
    //按值查找到結點
    LinkNode *p=this->findNodeByVal(val);
    if (p==NULL)
        return false;
    //查找前驅結點
    LinkNode *p1=this->head;
    while(p1->next!=p) {
        p1=p1->next;
    }
    //構建新結點
    LinkNode *n=new LinkNode(0);
    n->data=data;
    //新結點的後驅為 p 結點
    n->next=p;
    //新結點的前驅為 p 的前驅
    n->pre=p->pre;
    //p 的前驅結點的後驅結點為 n
    p->pre->next=n;
    //p 的前驅結點為 n
    p->pre=n;
    return true;
}

測試前插入：

int main(int argc, char** argv) {
	LinkList list {};
	//創建 7,3 兩個結點
	list.createFromTail(2);
    //在值為 7 的結點前面插入值為 9 的結點
	list.insertBefore(7,9);
	list.showSelf();
    return 0;
}

執行結果：

29.png

2.5 刪除

2.5.1 刪除結點

刪除已知結點的基本操作流程：

  • 查找到要刪除的結點p。

30.png

  • 找到結點p的前驅結點，設置其後驅結點為p的後驅結點。
p->pre->next=p->next;

31.png

  • 找到p結點的後驅結點，設置其前驅結點為p結點的前驅結點。刪除p結點。
p->next->pre=p->pre;
delete p;

32.png

編碼實現：

int delNode(dataType data) {
    //按值查找到要刪除的結點
    LinkNode *p= this->findNodeByVal(data);
    if (p==NULL)return false;		
    //設置 p 的前驅結點的後驅結點 
    p->pre->next=p->next;
    p->next->pre=p->pre;
    delete p;
    return true;
}

測試刪除操作：

LinkList list {};
//創建 {7,3,9} 3個結點
list.createFromTail(3);
//LinkNode *res= list.findNodeByValFromTail(4);
list.delNode(3);
list.showSelf();

執行結果：

33.png

2.5.2 刪除所有結點

編碼實現：

void delAll() {
    LinkNode *p=this->head->next;
    //臨時結點
    LinkNode *p1;
    while(p!=this->head) {
        //保留刪除結點的後驅結點
        p1=p->next;
        delete p;
        p=p1;
    }
    this->head=NULL;
}

3. 演算法案例

界定數列的要求：對於一個無序數列，首先在數列中找出一個基數，然後以基數為分界點，把小於基數的數字放在基數前面，反之放在後面。

3.1 演示流程

使用雙向循環鏈表實現界定數列的流程。

  • 已知的無序數列：

1.png

  • 選擇基數。這裡選擇第一個數字 7 作為基數。保存在臨時變數 tmp中。聲明 2 個變數 left、right，分別指向第一個數據和最後一個數據。

2.png

  • 從 right位置開始掃描整個數列，如果 right位置的數字大於 tmp中的值，則繼續向左移動right指針直到遇到比 tmp中值小的數字，然後保存到 left位置。

3.png

  • 對left指針的工作要求：當所處位置的數字比tmp值小時，則向右邊移動直到遇到比tmp值大的數字，然後保存至right。

4.png

  • 重複上述過程，直到 left和right指針重合。

5.png

  • 最後把tmp中的值複製到left和right指針最後所指向的位置。最終實現以數字7界定整個數列。

6.png

3.2 演算法實現

使用雙向鏈表實現上述需求：

  • 初始化鏈表，並以尾部插入方式（保證數列的邏輯順序和物理順序一致）創建數列{7,3,1,9,12,5,8}。
int main(int argc, char** argv) {
	LinkList list {};	
	list.createFromTail(7);
	//沒刪除之前
	cout<<"顯示創建結果:"<<endl; 
	list.showSelf();
	return 0;
}

執行後結果：

7.png

  • 編寫界定演算法。
void  baseNumBound() {
    //第一個數據結點的數據作為界定數字
    int tmp=this->head->next->data;
    //左指針，指向第一個數據結點
    LinkNode *left=this->head->next;
    //右指針，指向尾結點
    LinkNode *right=this->tail;

    while(left!=right) {
        while(left!=right && right->data>tmp) {
            //右指針向左移動
            right=right->pre;
        }
        left->data=right->data;
        while(left!=right && left->data<tmp) {
            //左指針向右移動
            left=left->next;
        }
        right->data=left->data;
    }
    left->data=tmp;
}

測試程式碼：

int main(int argc, char** argv) {
	LinkList list {};
	list.createFromTail(7);
	//沒刪除之前
	cout<<"顯示鏈表的創建結果:"<<endl;
	list.showSelf();
	list.baseNumBound();
	cout<<"\n顯示界定後的數列："<<endl;
	list.showSelf();
	return 0;
}

執行結果：
34.png

使用雙向循環鏈表，實現界定數列簡單、明了。

4. 總結

雙向鏈表的結點多了一個前驅指針位，對其內部數據的維護提供了大大的便利。對於程式而言，已知數據越多，演算法也將會有更大靈活伸縮空間。

Tags:

VirMach 便宜 VPS