為實習準備的資料結構（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的介紹

2. 增

Rect a;
···
test.push_back(a);
test.push_front(a);
//頭尾插入（雙向鏈表）

//定點插入
test.insert(test.begin()+10,a);	//在第十個節點之前插入a

3. 刪

//洗掉test頭部的元素
test.erase(test.begin());

//洗掉test從頭到尾的元素
test.erase(test.begin(), test.end());

test.pop_back();
test.pop_front();

其實增刪還是推薦使用迭代器來，因為直接對資料進行操作會存在一定的危險，
在本文第三部分詳細講述了List迭代器操作增刪，

除了這個函式：test.clear();這個函式安全得很，反正都清理掉了，

4. 查、改

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

要遍歷還是首推迭代器，所有和遍歷有關的還是用迭代器，

5. 排

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

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

6. 大小

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

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

7. 其他
   (1)壓縮list

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

	(2)合并list

test.splice(test.end(),test2);//將test2剪切到test后面

最后還是要提一下頭檔案：
分不清楚就都寫上

#include<algorithm>
#include<list>