緒論

線性表是資料結構中比較常見也比較重要的一種線性結構，簡言之，線性表是n個資料元素的有限序列，而線性表又有兩種常見的實作方式，其中比較常考的就是鏈表了，
鏈表實作順序表的時候，與順序表最大不同之處在于，鏈表中兩個邏輯位置在一起的元素，物理地址并不連續，因為鏈表的每個會有一個指向下一項的指標，指標所指地址對應的值才是與該元素邏輯上相鄰的值，本文我們會從單鏈表出發，循序漸進帶大家了解雙鏈表和回圈鏈表，
、

單鏈表的實作

上文我們說到，鏈表里最典型的就是單鏈表了，什么是單鏈表，顧名思義，就是指只有一個指標用來與表中其他元素相對應，

單鏈表的定義

我們可以很清晰的看到，每一項都會一個指標來指向下一項，但是我們也能發現，我們的最后一項好像沒有指，其實最后一項指標是指向了NULL，也就是我們的空，
結合上圖我們可以很清楚地看到，對于一個鏈表，它一共需要兩種型別地變數，一個資料項，一個指向下一項的指標，

下面展示一些 行內代碼片，

// 定義一個單鏈表   用typedef將struct list重命名為List,將List *命名為ListNode
typedef struct list{
	int data;
	struct list *next;
}List,*ListNode;

單鏈表的初始化

對于任何一個資料結構，我們對它的操作無非就是創建，銷毀，增刪改查這幾個最基本的操作，只有能掌握這幾個最基本的操作，我們才能擴展更多功能
對于一個單鏈表，其實也是可以分為兩種，一種是帶有頭結點的，一種是不帶頭結點的，這兩種的區別是什么呢？

這個例子就是個不帶頭結點的
而下面這種就是帶頭結點的

我們可以清楚的感覺到，兩者最大的區別就在于帶頭結點的鏈表更符合人的計數方式，對于我們而言，更好維護和操作，并且能夠看出來，帶頭結點的單鏈表，他的頭結點是沒有data值的，因為我們并不需要它幫我們存取值，只是為了方便計數，所以他的data為預設型別，接下來我們來嘗試初始化一個單鏈表，這里我講的所有方法都是基于帶頭結點的，有興趣的朋友們可以自己嘗試下不帶頭結點該怎么定義

// 初始化一個單鏈表，因為有頭結點，所以頭結點的下一項才是真正的資料第1項
//為此我們就得給頭結點的指標所指的值來表示真實的第一項
void init(ListNode &L)
{
	//之所以用&是因為我們需要把處理之后的值回傳到我們的主函式里，而不是復制一個新的值僅僅在函式堆疊里處理
	//引數我們傳入進來一個指標，指向的是一個List元素
	L=(List *)malloc(sizeof(List));//在記憶體中申請一個空間存放頭結點
	L->next=NULL;
	//一個沒有任何元素的鏈表就初始化結束了
}

單鏈表的插入洗掉

對于單鏈表，我們要是想洗掉某一位上的元素，很明顯，第一步我們肯定是先找到這個位置的前一位，然后再將此位置前一位元素的next指標指向我們要插入的部分，而我們要插入的部分的next指標指向原本在這個位置的元素
比如我們在第三個位置插入P結點

然后我們先找到第二個位置b，找到之后我們把a->next指向p，p->next指向b

用代碼實作時，我們把其封裝到一個insert函式里面，這里我們應該看出來，我們應該有三個引數，分別是List * &L一個鏈表，int n,第n個位置，int e 需要插入的元素

// 一定要判斷插入位置是否正確
bool insert(List * &L,int n,int e)
{
	if(n<1)//檢測位置是否合法
	return false;
	List *p=L;
	int j=0
	while(p!=NULL&&j<n-1)//找到插入元素之前的位置
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
	return false;//確認插入有無超出鏈表范圍
	List *s=(List *）malloc(sizeof(List));//存放新元素的data
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

單鏈表的洗掉

其實洗掉的原理和增加也很想，第一步就是找到要洗掉的位置的前一位p,然后讓p直接指向p->next->next即可,然后清理記憶體中的p就行了
比如洗掉第三位的c

bool remove(List * &L,int n)
{
	if(n<1)//檢測位置是否合法
	return false;
	List *p=L;
	int j=0
	while(p!=NULL&&j<n-1)//找到洗掉元素之前的位置
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
	return false;//確認插入有無超出鏈表范圍
	List *q=p->next;
	p->next=q->next;
	free(q);
	return true;
}

單鏈表的查找

寫到這里，估計有好多細心的朋友們發現了，我們之前的一大串尋找第n-1個位置和插入操作基本沒變，變的只是后面的邏輯上的操作，所以，我們可以在用一個方法把之前那一大塊封裝起來，以方便我們維護

List * getNode(List * &L,int n)
{
	if(n<1)//檢測位置是否合法
	return NULL;
	List *p=L;
	int j=0
	while(p!=NULL&&j<n)//找到元素的位置
	{
		p=p->next;
		j++;
	}
	return p;//如果p是NULL,他也會回傳NULL
]

單鏈表的修改

其實只要能寫出來查找，修改只不過是在查找的基礎上，把data項修改了而已

void changeNode(List * &L,int n,int e)
{
	List *p=getNode(List * &L,int n);//直接呼叫我們寫好的查找函式
	if(p!=NULL)
	p->data=e;
]

單鏈表的建立

單鏈表的建立分為兩種模式，一種是頭插法，一種是尾插法
頭插法

比如我們要往這個鏈表中加入新的元素p,頭插法的做法是每次就加入到頭結點的后面

尾插法

比如我們要往這個鏈表中加入新的元素p,尾插法的做法是每次就加入到最后一個結點的后面

對于頭插法

List * createbyhead(List * &L)//一個初始化過的新表
{
	List *p=L;
	int n;
	do{
		scanf("%d",&n);
		List *s=(List *)malloc(sizeof(List));
		s->next=p->next;//新結點的下一節點指向頭結點的下一節點
		p->next=s;//新結點插入到表最頭
		s->data=n;
	}while(getchar()='\n')//輸入回車表示輸入完了
	return p;
}

對于尾插法

List * createbytail(List * &L)//一個初始化過的新表
{
	List *tail=L;//創建一個尾指標tail
	int n;
	do{
		scanf("%d",&n);
		List *p=(List *)malloc(sizeof(List));
		p->data=n;//p指標就是每次我們想插入的新項
		tail->next=p;///把新項插入到表尾
		tail=p;//尾指標再次向后移動
	}while(getchar()='\n')//輸入回車表示輸入完了
	tail->next=NULL;//保證每次尾指標都指向NULL
	return p;
}

雙向鏈表

雙向串列也可以簡稱為雙鏈表，什么是雙鏈表，類比于單鏈表，則雙鏈表就是有兩個指標的鏈表，一個指標指向后繼節點，一個指標指向前驅節點，那我們結合上面介紹的單鏈表，是不會發現，雙鏈表無非是多了個指標，定義如下：

typedef struct Doublelist{
	int data;
	struct Doublelist *next;
	struct Doublelist *prior;
}Dlist;

所以我們用雙向鏈表進行增刪查改的時候，只需要每次兼顧它的前驅指標就是了

雖然雙鏈表要比單鏈表更難一點，但是其實如果我們理解了的話，增刪只不過是對這三個結點的操作罷了，比如初始化init()

void init(Dlist * &L)
{
	L=(Dlist *)malloc(sizeof(Dlist));
	L->next=NULL;
	L->prior=NULL;
}

對于雙鏈表來說，插入是要比單鏈表難一點的，因為對于單鏈表，每次插入都是僅僅限定于插入位置前面的一項和新插入一項的兩個指標，而雙鏈表則需要考慮三個指標（前一項的next指標和新插入一項的prior指標以及next指標）,但是如果理解的話也不是很難

bool insertDlist(Dlist * &L,int n,int e)
{
	if(n<1)
	return false;
	Dlist *p=L;
	int i =0;
	while(p!=NULL&&i<n-1)//先找要插入位置前一個結點
	{	
		p=p->next;
		i++;
	}
	if(p==NULL)
	return false;
	Dlist *q=p-next;
	Dlist *s=(Dlist *)malloc(Dlist);
	s->data=e;
	q->prior=s;
	s->next=q;
	s->prior=p;//不要忘了指向前面的指標
	p->next=s;
	return true
}

而除了增加操作，還有查找，洗掉操做等等，這里我就不在給大家用代碼展示了，希望大家能自己私下用代碼實作

回圈鏈表

回圈鏈表可以分為單回圈鏈表和雙回圈鏈表，回圈鏈表與普通鏈表不同的地方就是，回圈鏈表的尾項指回了首項
我想經過上面對單鏈表的詳細的介紹，到這里大家應該都能熟練的理解鏈表的作業原理了，所以我這里只幫大家粗略介紹下回圈鏈表，具體的細節就不再多說了
回圈鏈表的定義

typedef struct Clist{
	int data;
	struct Clist *next;
};
void init(struct Clist * &L)//回圈鏈表里沒有任何一項會指向NULL，每一項都有所指的東西
{
	L=(struct Clist *)malloc(sizeof(struct Clist));
	L->next=L;
}

至于接下來的一些介面如insert(),remove()我在這里就不再贅述了，因為大家只要掌味訓本原理，寫出來代碼還是相對比較容易的

鏈表與順序表的區別

順序表存盤資料，需預先申請一整塊足夠大的存盤空間，然后將資料按照次序逐一存盤，優點是存盤密度高，因為不需要像鏈表一樣存盤指標，但是因為它的長度是限定的，所以不利于動態調整，但是因為順序表基于陣列下標直接尋址，所以查找的速度比鏈表快，同時洗掉增加時，就沒有鏈表那么簡單的只需要對當前位置的兩個項進行操作簡單了

鏈表和順序表如何選擇？
基于存盤的考慮：
順序表的存盤空間是分配好不變的，在程式執行之前必須明確規定它的存盤空間大小，即事先對”maxsize”要有合適的設定，過大造成浪費，過小造成溢位，在對線性表的長度或存盤規模難以估計時，不宜采用順序表；鏈表不用事先估計存盤規模，
2.基于運算的考慮：
如果經常做的運算是按序號訪問資料元素，顯然順序表優于鏈表；在順序表中做插入，洗掉時，平均移動表中一半的元素，當資料元素的資訊量較大且表較長時，這一點是不應該忽視的；在鏈表中做插入，洗掉，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然鏈表優于順序表，
3.基于環境的考慮：
順序表容易實作，任何高級語言中都有陣列型別，鏈表的操作是基于指標的，相對來講前者簡單些

總結

對于學習資料結構，線性表只是最基礎的，希望我能再接再勵，能搞懂其原理，最后希望大家可以點贊關注支持，謝謝~~~~