APP
一、線性表的定義
線性表(List)：由零個或多個數據元素組成的有限序列。
這里需要強調幾個關鍵的地方：
- 首先它是一個序列，也就是說元素之間是有個先來后到的。
- 若元素存在多個，則第一個元素無前驅，而最后一個元素無后繼，而其他元素都有且只有一個前驅和后繼。
- 另外，線性表強調是有限的，事實上無論計算機發展多強大，它所處理的元素都是有限的。
二、數據類型的定義
數據類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱（整型、浮點型、字符型）。
三、線性表的抽象數據類型
Operation
- InitList(*L)：初始化操作，建立一個空的線性表。
- ListEmpty(L)：判斷線性表是否為空表，若線性表為空，返回true,否則返回false。
- ClearList(*L)：將線性表清空。
- GetElem(L,i,*e)：將線性表L中的第i個位置元素值返回給e。
- LocateElem(L,e)：在線性表L中查找與給定值e相等的元素，如果查找成功，返回該元素在表中序號表示成功。否則，返回0表示失敗。
- ListInsert(*L,i,e)：在線性表L中第i個位置插入新元素e。
- ListDeleted(*l,i,*e)：刪除線性表L中第i個位置元素，并用e返回其值。
- ListLength(L)：返回線性表L的元素個數。
//AUB
//La表示A集合，Lb表示B集合
void unionL(List *La,List Lb){
int La_len ,Lb_len,i;
ElemType e;
La_len = ListLength(*La);
Lb_len = ListLength(Lb);
for(i = 1;i<=Lb_len;i++){
GetElem(Lb,i,&e)
if(!LocateElem(*La,e)){
ListInsert(La,++La_len,e);
}
}
}
四、線性表的順序存儲結構
線性表的順序存儲結構，指的是用一段地址連續的存儲單元依次存儲線性表的數據元素。（像C語言的數組）
物理上的存儲方式實際上就是在內存中找個初始地址，然后通過占位的形式，把一定的內存空間給占了，然后把相同數據類型的數據元素依次存放在這塊空地中。
順序存儲結構的結構代碼
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int length;//線性表當前長度
} SqList;
大家看到了，這里我們封裝了一個結構，事實上就是對數組進行封裝，增加了一個當前長度的變量罷了。
總結下，順序存儲結構封裝需要三個屬性：
1.存儲空間的起始位置，數組data，它的存儲位置就是線性表存儲空間的存儲位置。
2.線性表的最大存儲容量：數組的長度MAXSIZE
3.線性表的當前長度：length
地址計算方法
假設ElemType占用的是C個存儲單元（字節），那么線性表中第i+1個數據元素和第i個數據元素的存儲位置關系是(Loc表示獲得存儲位置的函數)：LOC(ai+1) = LOC(ai) + c;
所以對于第i個數據元素ai的存儲位置可以由a1推算出：LOC(ai) = LOC(a1) + (i-1)*c;
通過這個公式，我們可以隨時計算出線性白哦中任意位置的地址，不管它是第一個還是最后一個，都是相同的時間。那么它的存儲時間性能當然就為O(1)，我們通常稱為隨機存儲結構。
獲得元素操作
實現GetElem的具體操作，即將線性表L中的第i個位置元素值返回。就程序而言非常簡單了，我們只需要把數組第i-1下標的值返回即可。
GetElem.c
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函數的類型，其值是函數結果的狀態碼，入OK等。
//初始條件：順序線性表L已存在，1 <= i <= ListLength(L)
//操作結果：用e返回L中第i個數據元素的值
Status GetElem(SqList L,int i,ElemType *e){
if(L.length == 0 || i < 1 || i>L.length){
return ERROR;
}
*e = L.data[i-1];
return OK;
}
插入操作
插入算法的思路：
1.如果插入位置不合理，拋出異常；
2.如果線性表長度大于等于數組長度，則拋出異?；騽討B增加數組容量；
3.從最后一個元素開始向前遍歷到第i個位置，分別將他們都向后移動一個位置；
4.將要插入元素填入位置i處；
5.線性表長度+1。
ListInsert.c
//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結果：在L中第i個位置之前插入新的數據元素e,L長度+1
Ststus ListInsert(SqList *L,int i;ElemTYpe e){
int k;
if(L->length == MAXSIZE){//順序線性表已經滿了
return ERROR;
}
if(i<1 || i>L->length){//當i不在范圍內時
return ERROR;
}
if(i<= L->length){//若插入元素位置不再表尾
//要將插入位置后元素向后移動一位
for(k=L->length-1;k>=i-1;k--){
L->data[k+1] = L->data[k];
}
}
L->data[i-1] = e;//將新元素插入
L->length++;
return OK;
}
刪除操作
刪除算法的思路
1.如果刪除位置不合理，拋出異常；
2.取出要被刪除的元素；
3.從刪除元素位置開始遍歷到最后一個元素位置，分別將他們都向前移動一個位置；
4.表長-1。
ListDeleted.c
//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度-1
Status ListDeleted(SqList *L,int i,ElemType *e){
int k;
if(L->length == 0){
return ERROR;
}
if(i<1 || i>L->length){
return ERROR;
}
*e = L->data[i-1];
if(i<L->length){
for(k=i;k<L->length;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
性能分析
現在我們分析一下，插入和刪除的時間復雜度。
最好的情況：插入和刪除操作剛好要求在最后一個位置，因為不需要移動任何元素，所以此時的時間復雜度為O(1)。
最壞的情況：如果要插入和刪除的位置是第一個元素，那就意味著要移動所有的元素像后或者向前，所以這個時間復雜度為O(n)。
至于平均情況，就去中間值O((n-1)/2) = O(n)。
線性表的優缺點
線性表的順序存儲結構，在存、讀數據時，不管是哪個位置，時間復雜度都是O(1)。而在插入或刪除時，使勁復雜度都是O(n)。
這就說明，他比較適合元素個數比較穩定，不經常插入和刪除，而更多的操作是存取數據的應用。
優點：
1、無需為表示表中元素之間的邏輯關系而增加額外的存儲空間。
2、可以快速的存取表中的任意位置的元素。
缺點：
1、插入和刪除操作需要移動大量元素。
2、當線性表長度變化較大時，難以確定存儲空間的容量。
3、容易造成存儲空間的“碎片”。
五、線性表的鏈式存儲結構
線性表鏈式存儲結構定義
線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以存在內存中未被占用的任意位置。
比起順序存儲結構每個數據元素只需要存儲一個位置就可以了?，F在鏈式存儲結構中，除了要存儲數據元素信息外，還要存儲它的后繼元素的存儲地址（指針）。
我們把存儲數據元素信息的域稱為數據域，把存儲直接后繼位置的域稱為執指針域。指針域中存儲的信息稱為指針或鏈。這兩部分信息組成數據元素稱為存儲映像，稱為節點(Node)。
因為此鏈表的每個節點中包含一個指針域，所以叫做單鏈表。
對于線性表來說，總得有個頭有個尾，鏈表也不例外。我們把鏈表中的第一個節點的存儲位置叫做頭指針，最后以客觀節點指針為空(NULL)
頭指針與頭節點的異同
頭節點的數據域一般不存儲任何信息
頭指針：
頭指針是指鏈表指向第一個節點的指針，若鏈表有頭節點，則是指向頭節點的指針。
頭指針具有標識作用，所以常用頭指針冠以鏈表的名字（指針變量的名字）。
無論鏈表是否為空，頭指針均不為空。
頭指針是鏈表的必要元素。
頭節點：
頭節點是為了操作的統一和方便而設立的，方在第一個元素的節點前，其數據域一般無意義（但也可以用來存放鏈表的長度）。
有了頭節點，對在第一個元素節點前插入節點和刪除第一個節點其操作與其他節點的操作就統一了。
頭節點不一定是鏈表的必須要素。
我們在C語言中可以用結構指針來描述單鏈表
typedef struct Node{
ElemType data;//數據域
struct Node *Next;//指針域
}Node;
typedef struct Node *LinkList;我們看到節點由存放數據元素的數據域和存放后繼節點地址的指針域組成。
單鏈表的讀取
在線性表的順序存儲結構中，我們要計算任意一個元素的存儲位置是很容易的。
但是在單鏈表中，由于第i個元素到底在哪？我們壓根沒辦法一開始就知道，必須得從第一個節點開始挨個找。
因此，對于單鏈表實現獲取第i個元素的數據的操作GetElem，在算法上相對要麻煩一些。
獲得鏈表第i個數據的算法思路：
1、申明一個節點p指向鏈表的第一個節點，初始化j從1開始；
2、當j<i時，就遍歷鏈表，讓p的指針像后移動，不斷指向下一個節點，j+1;
3、若到鏈表末尾p為空，則說明第i個元素不存在；
4、若查找成功，返回節點p的數據。
GetElem.c
//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結果：用e返回L中第i個數據元素的值
Status GetElem(LinkList L,int i,ElemType *e){
int j;
LinkList p;
p = L->next;
j = 1;
while(p && j<i){
p = p->next;
++j;
}
if(!p || j>i){
return ERROR;
}
*e = p->data;
return OK;
}
說白了，就是從頭開始找，知道第i個元素為止。
由于這個算法的時間復雜度取決于i的為止，當i=1時，則不需要遍歷，而i=n時則遍歷n-1次才可以。因此最壞情況的時間復雜度為O(n)。
由于單鏈表的結構中沒有定義表長，所以不能實現知道要循環多少次，因此也就不方便使用for來控制循環。
其核心思想叫做“工作指針后移”，這其實也是很多算法的常用技術。
單鏈表的插入
假設存儲元素e的節點為s，要實現節點p、p->next和s之間邏輯關系
我們思考后發覺根本用不著驚動其他節點，只需要讓s->next和p->next的指針做一點變化。
s->next = p->next;
p->next = s;
那么我們考慮一下大部分初學者最容易搞壞腦子的問題：這兩句代碼的順序可以可以交換過來？
p->next = s;
s->next = p->next;
如果先執行p->next = s 的話會先被覆蓋為s的地址，那么s->next = p->next其實就等于s->next = s 了。
所以這兩句是無論如何不能弄反的，這點初學者一定要注意。
單鏈表第i個數據插入節點的算法思路：
1、聲明一節點p指向鏈表頭節點，初始化j從1開始；
2、當j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一節點，j累加1;
3、若到鏈表末尾p為空，則說明第i個元素不存在；
4、否則查找成功，在系統中生成一個空節點s；
5、將數據元素e復制給s->data;
6、單鏈表的插入剛才兩個標準語句；
7、返回成功。
//初始條件：鏈表L已經存在，1<=i<=ListLength(L)
//操作結果：在L中第i個位置前插入新的數據元素e，L的長度加1
Status ListInsert(LinkList *L,int i,ElemType e){
int j;
LinkList p,s;
p = *L;
j = 1;
while(p && j<i){
p = p->next;
j++;
}
if(!p || j>i){
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
單鏈表的刪除
假設元素a2的節點為q，要實現節點q刪除單鏈表的操作，其實就是將它的前繼節點的指針繞過指向后繼節點即可。
那我們要做的，實際上就是一步：
p->next = p->next->next;
或
q = p->next;
p->next = q->next;
單鏈表的刪除節點的算法思路：
1、申明節點p指向鏈表第一個節點，初始化j = 1;
2、當j<i時，就遍歷鏈表，讓P的指針向后移動，不斷指向下一個節點，j累加1;
3、若到鏈表末尾p為空，則說明第i個元素不存在；
4、否則查找成功，將欲刪除節點p->next賦值給q;
5、單鏈表的刪除標準語句p->next = q->next;
6、將q節點中的數據賦值給e,作為返回；
7、釋放q節點。
Status ListDeleted(LinkList *L,int i,ElemType e){
int j;
LinkList p,q;
p = *L;
j = 1;
while(p && j<i){
p = p->next;
j++;
}
if(!(p->next) || j>i){
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}效率PK
我們發現無論是單鏈表插入還是刪除算法，他們其實都是由兩部分組成：第一部分就是遍歷查找第i個元素，第二部分就是實現插入和刪除元素。
從整個算法來書，我們很容易可以退出他們的時間復雜度都是O(n)。
在詳細點分析：如果在我們不知道第i個元素的指針位置，單鏈表數據結構在插入和刪除操作上，與線性表的順序存儲結構是沒有太大優勢的。
但如果，我們希望從第i個位置開始，插入連續10個元素，對于順序存儲結構意味著，每一次插入都需要移動n-1個位置，所以每次都是O(n)。
而單鏈表，我們只需要在第一次時，找到第i個位置的指針，此時為O(n),接下來只是簡單的通過復制移動指針而已，時間復雜度都是O(1)。
顯然，對于插入或刪除數據越頻繁的擦歐總，單鏈表的效率優勢就越是明顯。
單鏈表的正表創建
對于順序存儲結構的線性表的整表創建，我們可以用數組的初始化來直觀理解。
而單鏈表和順序存儲結構就不一樣了，它不像順序存儲結構數據這么集中，它的數據可以是分散在內存各個角落的，它的增長也是動態的。
對于每個鏈表來說，它所占用空間的大小和位置是不需要魚線分配劃定的，可以根據系統的情況和實際的需求即時生成。
創建單鏈表的過程是一個動態生成鏈表的過程，從“空表”的初始狀態起，依次建立各個元素節點并逐個插入鏈表。
所以，單鏈表整表創建的算法思路如下：
1、聲明一個節點P和計數器變量i；
2、初始化一空鏈表L;
3、讓L的頭節點的指針指向NULL,即建立一個帶頭節點的單鏈表；
4、循環實現后繼節點的復制和插入。
頭插法建立單鏈表
頭插法從一個空表開始，生成新節點，讀取數據存放到新節點的數據域中，然后將新節點插入到當前鏈表的表頭上，直到結束為止。
簡單來說，就是把新加進的元素放在表頭后的第一個位置：
先讓新節點的next指向頭節點之后
然后讓表頭的next指向新節點
void CreateListHead(LinkList *L,int n){
LinkList p;
int i;
srand(time(0));//初始化隨機數字
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for(i=0;i<n;i++){
p = (LinkLIst)malloc(sizeof(Node));//生成新節點
p->data = rand()%100+1;
p->next = (*L)->next;
(*L)->next = p;
}
}尾插法建立單鏈表
頭插法建立鏈表雖然算法簡單，但生成的鏈表中節點的次序和輸入的順序相反。
void CreateListTail(LinkList *L,int n){
LinkList p,r;
int i;
srand(time(0));//初始化隨機數字
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(i=0;i<n;i++){
p = (LinkLIst)malloc(sizeof(Node));//生成新節點
p->data = rand()%100+1;
r->next = p;
r = p;//備注：初學者可能很難理解這句，重點解釋。
}
r->next = NULL;
}單鏈表的整表刪除
單鏈表整表刪除的算法思路如下：
1、申明節點p和q;
2、將第一個節點賦值給p，下一節點賦值給q；
3、循環執行釋放p和將q復制給p的操作；
Status ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}六、單鏈表結構與順序存儲結構優缺點
我們分別從存儲分配方式、時間性能、空間性能三方面來做對比。
存儲分配方式
順序存儲結構用一段連續的存儲單元依次存儲線性表的數據元素。
單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的元素。
時間性能
- 1.查找
順序存儲結構O(1)
單鏈表O(n)
- 2.插入和刪除
順序存儲結構需要平均移動表長一般的元素，時間為O(n)
單鏈表在計算出某位置的指針后，插入和刪除時間僅為O(1)
空間性能
順序存儲結構需要預分配存儲空間，分大了，容易造成空間浪費，分小了，容易發生溢出。
單鏈表不需要分配存儲空間，只要有就可以分配，元素個數也不受限制。
經驗性結論：
若線性表需要頻繁查找，很少進行插入和刪除操作時，宜采用順序存儲結構。
若需要頻繁插入和刪除時，宜采用單鏈表結構。
七、靜態鏈表
在講解原理之前，先讓大家直到這種用數組描述的鏈表叫做靜態鏈表，這種描述方法叫做游標實現法。
線性表的靜態鏈表存儲結構
#define MAXSIZE 1000
typedef struct{
ElemType data;//數據
int cur;//游標
}Component,StaticLinkList[MAXSIZE];
對靜態鏈表進行初始化相當于初始化數組：
Status InitList(StaticLinkList space){
int i;
for(i=0;i<MAXSIZE-1;i++){
space[i].cur = i+1;
}
space[MAXSIZE-1].cur = 0;
return OK;
}我們對數組的第一個和最后一個元素做特俗處理，他們的data不存放數據。
我們通常把未使用的數組元素稱為備用鏈表。
數組的第一個元素，即下標為0的那個元素的cur就存放備用鏈表的第一個節點的下標。
數組的最后一個元素，即下標為MAXSIZE-1的cur則存放第一個有數值的元素的下標，相當于單鏈表中的頭節點作用。
靜態鏈表的插入操作
首先是獲得空閑分量的下標：
int Malloc_SLL(StaticLinkList space){
int i = space[0].cur;
if(space[0].cur){
space[0].cur = space[i].cur;
//把它的下一個分量用來作為備用。
}
return i;
}
Status ListInsert(StaticLinkList L ,int i,ElemType e){
int j,k,l;
k = MAX_SIZE - 1;//數組的最后一個元素
if(i<1 || i>ListLength(L)+1){
return ERROR;
}
j = Malloc_SLL(L);
if(j){
L[j].data = e;
for(l=1;l<i-1;l++){
k = L[k].cur;
}
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}
靜態鏈表的刪除操作
void Free_SSL(StaticLinkList space,int k){
space[k].cur = space[0].cur;
space[0].cur = k;
}
Status ListDeleted(StaticLinkList L ,int i){
int j,k;
if(i<1 || j>ListLength(L)){
return ERROR;
}
k = MAX_SIZE-1;
for(j=1;j<=i-1;j++){
k = L[k].cur;
}
j - L[k].cur;
L[k].cur = L[j].cur;
Free_SLL(L,j);
return OK;
}靜態鏈表優缺點總結
- 1、優點
在插入和刪除操作時，只需要修改游標，不需要移動元素，從而改進了在順序存儲結構中的插入和刪除操作需要移動大量元素的缺點
- 2、缺點
沒有解決連續存儲分配（數組）帶來的表長難以確定的問題
失去了順序存儲結構隨機存取的特性。
- 3、總結
總的來說，靜態鏈表其實是為了給沒有指針的編程語言設計的一種實現單鏈表功能的方法。
盡管我們可以用單鏈表就不用靜態鏈表了，但這樣的思考方式是非常巧妙的，應該理解其思想，以備不時之需。
單鏈表小結騰訊面試題
題目：快速找到未知長度單鏈表的中間節點。
既然是面試題就一定有普通方法和高級方法，而高級方法，而高級方法無疑會讓面試官大大加分！
普通方法很簡單，首先遍歷一遍單鏈表以確定單鏈表的長度L。然后再次從頭節點觸發循環L/2次找到單鏈表的中間節點。
算法的復雜度為：O(L+L/2) = O(3/2L)
能否再優化一下這個時間復復雜度呢？
有一個很巧妙的方法：利用快慢指針！
利用快慢指針原理：設置兩個指針*search、*mid都指向單鏈表的頭節點。其中*search的移動速度是*mid的2倍。當*search指向末尾節點的時候，*mid正好就在中間了。這也是標尺的思想。
GetMidNode.c
Status GetMidNode(LinkList L,ElemType *e){
LinkList search,mid;
mid = search = L;
while(search->next != NULL){
//search移動的速度是mid的2倍
if(search->next->next !=NULL){
search = search->next->next;
mid = mid->next;
}else{
search = search->next;
}
}
*e = mid->data;
return OK;
}
八、循環鏈表
對于單鏈表，由于每個節點只存儲了向后的指針，到了尾部標識就停止了向后鏈的操作。也就是說，按照這樣的方式，只能索引后繼節點不能索引前驅節點。
這會帶來什么問題呢？
例如不從頭節點出發，就無法訪問到全部節點。
事實上要解決這個問題也并不麻煩，只需要將單鏈表中終端節點的指針由空指針改為指向頭節點，問題就結了。
將單鏈表中終端節點的指針端由空指針改為指向頭節點，就使整個單鏈表形成一個環，這種頭尾相接的單鏈表成為單循環鏈表，簡稱循環鏈表。
初始化循環鏈表
//鏈表存儲結構定義
typedef struct CLinkList{
int data;
struct ClinkList *next;
}
void ds_init(node **pNode){
int item;
node *temp;
node *target;
printf("輸入節點的值，輸入0完成初始化");
while(1){
scanf("%d",&item);
fflush(stdin);
if(item == 0){
return;
}
if((*pNode == NULL)){
//循環鏈表中只有一個節點
*pNode = (node*)malloc(sizeiof(struct ClinkList));
if(!(*pNode)){
exit(0);
}
(*pNode)->data = item;
(*pNode)->next = *pNode;
}else{
//找到next指向第一個節點的節點
for(target = (*pNode);target->next!=(*pNode);target = target->next){
}
//生成一個新的節點
temp = (node *)malloc(sizeof(struct CLinkList));
if(!temp){
exit(0);
}
temp->data = item;
temp->next = *pNode;
target->next = temp;
}
}
}
循環鏈表的插入
void ds_insert(node **pNode,int i){
node *temp;
node *target;
node *p;
int item;
int j;
printf("輸入要插入節點的值：");
scanf("%d",&item);
if(i == 1){
//新插入的節點作為第一個節點
temp = (node *)malloc(sizeof(struct CLinkList));
if(!temp){
exit(0);
}
temp->data = item;
//尋找到最后一個節點
for(target = (*pNode);target->next != (*pNode);target = target->next){}
temp->next = (*pNode);
target->next = temp;
*pNode = temp;
}else{
target = *pNode;
for(j = 1;j<(i-1);++j){
target = target->next;
}
temp = (node *)malloc(sizeof(struct CLinkList));
if(!temp){
exit(0);
}
temp->data = item;
p = target->next;
target->next = temp;
temp->next = p;
}
}循環鏈表返回節點位置
int ds_search(node *pNode,int item){
node *8target;
int i;
for(target = pNode;target->data!=elem && target->next != pNode;++i){
target = target->next;
}
if(target->next == pNode){
return 0;
}else{
return i;
}
}循環鏈表的特點
回顧一下，在單鏈表中，我們有了頭節點時，我們可以用O(1)的時間訪問第一個節點，但對于要訪問最后一個節點，我們必須要挨個向下索引，所以需要O(n)的時間。
如果用上今天我們學的循環鏈表的特點，用O(1)的時間就可以由鏈表指針訪問到最后一個節點。
不過我們需要改造一下現有的循環鏈表，我們不用頭指針，而是用指向指端節點的尾指針來表示循環鏈表，此時查找開始節點和終端節點都很方便了。
判斷單鏈表中是否有環
又環的定義是，鏈表的尾部節點指向了鏈表中的某個節點（不一定是第一個節點）。
那么要判斷單鏈表中是否有環，主要有一下兩種方法。
方法一：使用p、q兩個指針，p總是向前走，但q每次都從頭開始走，對于每個節點，看p走的步數是否和q一樣。如圖，當p從6走到3時候，用了6步，此時若q從head出發則只需要兩部就到3，因為步數不等，出現矛盾，存在環。
方法二：使用p、q兩個指針，p每次向前走一步，q每次向前走兩步，若在某個時候p==q,則存在環。
循環鏈表的應用-約瑟夫問題
據說著名猶太歷史學家Josephus有過以下的故事：
在羅馬人占領橋塔帕特后，39個猶太人與Josephus及它的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人，排成一個圓圈，由第一個人開始報數，沒報數到第三個人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，它將朋友與自己安排在第16個與第31個位置，于是逃過了這場游戲。
問題：用循環鏈表模擬約瑟夫問題，把41個人的順序編號輸出。
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}node;
node *create(int n){
node *p = NULL;
node *head;
p = head;
node *s;
int i =1;
if(0 != n){
while(i<=n){
s = (node *)malloc(sizeof(node));
s->data = i++;
p->next = s;
p = s;
}
s->next = head->next;
}
//free(head);
return s->next;
}
int main(){
int n = 41;
int m = 3;
int i;
node *p = create(n);
node *temp;
m %= n;//m = 2
while(p != p->next){
for(i = 1;i<m-1;i++){
p = p->next;
}
printf("%d->",p->next->data);
temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
}
printf("%d ",p->data);
return 0;
}
循環鏈表的應用-魔術師發牌問題
問題描述：魔術師利用一副牌中的13張黑牌，預先將他們排好后疊放在一起，牌面朝下。對著觀眾說：“我不看牌，只數數就可以猜到每張牌是什么”
#include <stdio.h>
#include <stdlib.h>
#define CardNumber 13
typedef struct node{
int data;
struct node *next;
}sqlist,*linklist;
linklist CreateLinkList(){
linklist head = NULL;
linklist s,r;
int i;
r = head;
for(i = 1;i<=CardNumber;i++){
s = (linklist)malloc(sizeof(sqlist));
s->data = 0;
if(head == NULL){
head = s;
}else{
r->next = s;
}
r = s;
}
r->next = head;
return head;
}
//發牌順序計算
void Magician(linklist head){
linklist p;
int j;
int Countnumber =2;
p = head;
p->data = 1;//第一張牌數1
while(1){
for(j = 0;j<Countnumber;j++){
p = p->next;
if(p->data != 0){//該位置有牌的話，則下一個位置
//p->next;
j--;
}
}
if(p->data == 0){
p->data = Countnumber;
Countnumber++;
if(Countnumber == 14){
break;
}
}
}
}
int main(){
linklist head;
head = CreateLinkList();
Magician(head);
int i;
for(i = 0;i<13;i++){
printf("%d-->",head->data);
head = head->next;
}
return 0;
}
循環鏈表的應用-拉丁方陣問題
拉丁方陣是一種n*n的方陣，方陣中恰有n種不同的元素，每種元素恰有n個，并且每種元素在一行和一列中恰好出現一次。著名數學家個物理學家歐拉使用拉丁字母來作為拉丁方陣里元素的符號，拉丁方陣因此而得名。
1 2 3
2 3 1
3 1 2
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}node;
node * makeList(int n){
node *head = NULL;
node *temp;
node *s;
int i;
temp = head;
for(i=1;i<=n;i++){
s = (node *)malloc(sizeof(node));
s->data = i;
if(head == NULL){
head = s;
}else{
temp->next = s;
}
temp = s;
}
temp->next = head;
return head;
}
int main(){
int n,i,j,k;
printf("請輸入方陣的大?。?);
scanf("%d",&n);
node * head;
node * temp;
head = makeList(n);
temp = head;
for(i = 1;i<=n;i++){
for(j = 1;j<=n;j++){
printf("%d ",temp->data);
temp = temp->next;
}
temp = head;
for(k=1;k<=i;k++){
temp = temp->next;
}
printf(" ");
}
return 0;
}
九、雙向鏈表
雙向鏈表節點結構
typedef struct DualNode{
ElemType data;
struct DualNode *prior;//前驅節點
struct DualNode *next;//后繼節點
}DualNode，*DualList;既然單鏈表可以有循環鏈表，那么雙向鏈表當然也可以有
雙向鏈表的插入
插入操作其實并不復雜，不過順序很重要，千萬不能寫反了。
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
關鍵在于交換的過程中不要出現矛盾，例如第四步先被執行了，那么p->prior就會提前變為s,使得插入的工作出錯。
雙向鏈表的刪除操作
如果剛才的插入操作理解了，那么再來理解接下來的刪除操作就容易多了。
p->prior->next = p->next;
p->next->prior = p->proor;
free(p);
最后總結一下，雙向鏈表相對于單鏈表來說，是要更復雜一點，買個節點多了一個prior指針，對于插入和刪除操作的順序大家要格外小心。
不過，雙向鏈表可以有效提高算法的時間性能，說白了就是用空間來換取時間。
????
本文摘自 ：https://blog.51cto.com/u
