為實習準備的資料結構（2）-- 詳盡連結清單篇

在這裡插入圖檔描述

C連結清單

連結清單在C語言的資料結構中的地位可不低。後面很多的資料結構，特别是樹，都是基于連結清單發展的。

是以學好連結清單，後面的結構才有看的必要。

初識連結清單

連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。連結清單由一系列結點（連結清單中每一個元素稱為結點）組成，結點可以在運作時動态生成。每個結點包括兩個部分：一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針域。 相比于線性表順序結構，操作複雜。由于不必須按順序存儲，連結清單在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者通路特定編号的節點則需要O(n)的時間，而線性表和順序表相應的時間複雜度分别是O(logn)和O(1)。

但是連結清單失去了數組随機讀取的優點，同時連結清單由于增加了結點的指針域，空間開銷比較大。

連結清單有很多種不同的類型：單向連結清單，雙向連結清單以及循環連結清單。

單連結清單

在這裡插入圖檔描述

單連結清單實作

話不多說啊，這裡我隻想直接放代碼：

#include <stdio.h>	//初學者，C語言開手
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
#include <assert.h>

//節點資料結構體
typedef struct test
{	
	char name[12];		//名字
	char pwd[8];		//密碼
	int number;			//編号
	int flag;			//區分管理者和使用者	// 	0 超級管理者 1 管理者  2 普通使用者 3 屏蔽使用者
	int money;			//僅使用者有存款，初始500
} TEST_T;

//如果不多來一個資料域，怎麼能展現出通用連結清單的優勢
typedef struct reported
{
	int amount;//交易金額
	int rflag; //交易方式	1、存款 2、取款 3、轉賬轉出 4、轉賬轉入
	int lastmoney;//餘額
	int lastmoney2;//收款者的餘額
	int number1;//付款賬戶
	int number2;//入款賬戶
	char time[12];//操作時間	
} REPORT_T;

//節點描述結構體
typedef struct point
{
	void *pData;				//指向資料域
	struct point *next;			//指向下一個節點	
} POINT_T;

POINT_T * head ;
extern POINT_T * head;           

複制

這還是個通用連結清單的頭呢！！！

//建立結點
POINT_T * creat(void *data )	//建立一個屬于結構體point的函數，
//傳入結構體test的指針便可以用以操作test變量，
{								//并傳回一個point的指針用以操作point函數
	POINT_T *p=NULL;
	
	p=(POINT_T *)malloc(sizeof(POINT_T));
	if(p==NULL)
	{
		printf("申請記憶體失敗");
		exit(-1);
	}
	memset(p,0,sizeof(POINT_T));
	
	p->pData=data;
	p->next=NULL;	//處理幹淨身後事
	return p;
}

//新增節點
void add(POINT_T * the_head,void *data )				//這裡的data不會和上面那個沖突嗎？
{
	POINT_T * pNode=the_head;							//把頭留下
	POINT_T *ls=creat(data);
	//後面再接上一個
	while (pNode->next != NULL)							//周遊連結清單，找到最後一個節點
	{
		pNode=pNode->next;
	}
	pNode->next=ls;			//ls 臨時
}

//删除節點
void del(POINT_T * the_head, int index)
{
	POINT_T *pFree=NULL;					//用來删除
	
	POINT_T *pNode=the_head;
	int flag=0;
	while (pNode->next!=NULL)
	{
		if(flag==index-1)
		{
			pFree=pNode->next;				//再指向資料域就爆了
			pNode->next=pNode->next->next;	//這裡要無縫銜接
			free(pFree->pData);				//先釋放資料
			free(pFree);					//釋放指針
			break;
		}
		pNode=pNode->next;
		flag++;	
	}	
}

//計算節點數
int Count(POINT_T * the_head)
{
	int count=0;
	POINT_T *pNode1=the_head;
	while (pNode1->next!=NULL)
	{
		pNode1=pNode1->next;
		count++;		
	}	
	return count;
}

//查找固定節點資料
POINT_T * find(POINT_T *the_head,int index)
{
	int f=0;
	POINT_T *pNode=NULL;
	int count=0;
	pNode=the_head;
	
	count=Count(the_head);
	
	if(count<index)	
		printf("find nothing");
	
	while(pNode->next!=NULL)
	{
		if(index==f)
			return pNode;
		pNode=pNode->next;
		f++;		
	}
}           

複制

尾插法

若将連結清單的左端固定，連結清單不斷向右延伸，這種建立連結清單的方法稱為尾插法。尾插法建立連結清單時，頭指針固定不動，故必須設立一個搜尋指針，向連結清單右邊延伸，則整個算法中應設立三個連結清單指針，即頭指針head、搜尋指針p2、申請單元指針pl。尾插法最先得到的是頭結點。

上面那個就是。

循環連結清單

在這裡插入圖檔描述

我不喜歡搞的花裡胡哨，把循環連結清單單獨拿出來呢，是因為之前有幾道題給我留下了印象。

判斷連結清單是否有環

就像那電影裡的情節，男主女主在小樹林裡迷路了，到處都是樹，他們兜兜轉轉，又回到了原點。

連結清單一旦成環，沒有外力的介入是繞不出來的。

我舉個栗子：

//ListNode* reverseList(ListNode* head)
//{
//    ListNode* node_temp;
//    ListNode* new_head;
//
//    node_temp = head;
//    //周遊一個節點，就把它拿下來放到頭去
//    while (head->next != NULL)
//    {
//        //先考慮隻又兩個節點的情況 
//        head = head->next;
//        new_head = head;
//        new_head->next = node_temp;
//        node_temp = new_head;
//    }
//    return new_head;
//}           

複制

我也不知道當時是哪兒來的靈感，寫出了這麼個玩意兒。後來怎麼着了？後來卡死了呗，就擱那兒繞圈，繞不出來了。

那要這麼去判斷一個連結清單是否有環呢？

其實說簡單也簡單，快慢指針就解決了，快指針兩步走，慢指針一步走，隻要兩個指針重合了，那就說明有環，因為快指針繞回來了。

時間複雜度為線性，空間複雜度為常數。

說不簡單也不簡單，因為你去判斷一個連結清單是否有環，那頂多是在測試環節，放在釋出環節未免顯得太刻意，連代碼是否安全都不能保證。

而且，有環的話一般是運作不過的，不用測，運作逾時妥妥要考慮一下環的情況，一調試就知道了。

尋找連結清單入環點

這個就比較需要腦子了，前邊那個有手就行的。

我這個人，懶了點，來張現成的圖吧。

在這裡插入圖檔描述

看啊，在相遇之前呢，慢指針走的距離很好求的：L1 = D+S1;

快指針走的距離：設它在相遇前繞了n圈（n>1），那麼：L2 = D+S1+n(S1+S2);

不過，還有一個等量關系，不要忽略掉，快指針的速度是慢指針的兩倍，是以：L2 = 2L1;

那麼就是：n(S1+S2)-S1 = D;

再轉換一下就是：(n-1)(S1+S2)+S2 = D;

那也就是說，在相遇時候，把一個==慢指針==放在==連結清單頭==，開始周遊，把一個==慢指針==放在==相遇點==開始轉圈，當它倆相遇的時候，就是入環點了。

其實吧，用腦子想一開始很難想出來，用手想就快多了。

環的大小就不用我多說了吧，相遇之後，定住快指針，慢指針再繞一圈，再相遇的時候就是一圈了。

雙向連結清單

在這裡插入圖檔描述

參考單連結清單。

LeetCode 上的連結清單題

記一段曾經的問題代碼

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
    
};

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {    //傳進來的參數不為空
    ListNode* temp1 = list1;
    ListNode* temp2 = list2;
	
	//ListNode* temp3 = new ListNode(0);	這要是放這裡了問題就大了
	
    while (temp1->next != NULL && temp2!= NULL) {
        if (temp1->next->val >= temp2->val) {
            ListNode* temp3 = new ListNode(0);  //這個要放在這裡，新插入的節點一定要是新鮮的
            temp3->val = temp2->val;  //這裡要注意，對新指針指派，一定要隻指派給單指針，不要把後面一串全弄過去，會出現環狀連結清單
            temp3->next = temp1->next;
            temp1->next = temp3;
            temp2 = temp2->next;
        }
        temp1 = temp1->next;
    }
    if (temp2!= NULL) {
        temp1->next = temp2;
    }
    return list1;
}           

複制

翻轉連結清單

ListNode* reverseList(ListNode* head) 
{
    ListNode* node_temp = NULL; //這裡設為NULL
    ListNode* new_head = NULL;   //鍊棧的頭

    //周遊一個節點，就把它拿下來放到頭去
    while (head != NULL)
    {
        node_temp = head;   //先将節點取出
        //先考慮隻又兩個節點的情況 
        head = head->next;  //這個不放這裡又成環了

        node_temp->next = new_head;
	//剛開始相當于是置空的，因為前面并沒有配置設定空間，而是NULL
        new_head= node_temp;
    }
    return new_head;
}               

複制

不好了解啊，這裡要明确幾點：

1、head是目前周遊的節點，可以看成疊代器。

2、new_head= node_temp，但是node_temp的變化不影響new_head。

旋轉連結清單

這個也比較有意思啊，題目時這樣的：給定一個當連結清單，讓你順時針/逆時針旋轉N個位置，==要求原地旋轉==。

我講一下思路吧：

1、将連結清單自成環。

2、從剛剛的頭往後周遊N個位置，N為要旋轉的數。

3、環斷開。

解決。

秀吧，我就是覺得解法好玩，就收藏了。

STL 中的 List

每一個自己寫過連結清單的人都知道，連結清單的節點和連結清單本身是分開設計的。

那我們來看一下List的節點設計：

template <typename T>
struct __list_node
{
	typedef void* void_pointer;
	void_pointer prev;
	void_pointer neet;
	T date;
}           

複制

顯而易見，這是一個通用雙向連結清單的節點（如果對通用連結清單不了解，建議一定要自己動手設計一個）。

在這裡插入圖檔描述

3、List基本函數使用

1. 創#include<list>

   typedef struct rect

   {

   ···

   }Rect;

   list<Rect>test; //聲明一個連結清單，用于存放結構體資料

   //如果想以其他方法初始化list清單，可以移步到下一行那個Vector的介紹

1. 增Rect a;

   ···

   test.push_back(a);

   test.push_front(a);

   //頭尾插入（雙向連結清單）

   //定點插入

   test.insert(test.begin()+10,a); //在第十個節點之前插入aundefined//删除test頭部的元素

   test.erase(test.begin());

   //删除test從頭到尾的元素

   test.erase(test.begin(), test.end());

   test.pop_back();

   test.pop_front();其實增删還是推薦使用疊代器來，因為直接對資料進行操作會存在一定的危險。

   在本文第三部分詳細講述了List疊代器操作增删。

2. 删

除了這個函數：

test.clear();

這個函數安全得很，反正都清理掉了。

1. 查、改

//疊代器
list<int>::iterator p；
for (p = test.begin(); p != test.end(); p++)
	cout << *p << " ";           

複制

要周遊還是首推疊代器。所有和周遊有關的還是用疊代器。

1. 排

#include<algorithm>
sort(test.begin(),test.end());	//從頭到尾，預設從小到大排序

//一般排序都是要自定義排序的：
bool Comp(const int &a,const int &b)
{
    return a>b;
}
sort(test.begin(),test.end(),Comp);	//這樣就降序排序。            

複制

1. 大小

test.size();	//容器已存入資料量
test.capacity();	//容器還能存多少資料量

//其實不用擔心容器不夠大，容量要滿的時候它會自己擴容           

複制

1. 其他

   (1)壓縮list

//去除重複的元素至隻保留一個副本
test.unique();
//已經過大小排序的list才能使用           

複制

(2)合并list           

複制

test.splice(test.end(),test2);//将test2剪切到test後面           

複制

最後還是要提一下頭檔案：

分不清楚就都寫上

#include<algorithm>
#include<list>           

複制

在這裡插入圖檔描述