當(dāng)前位置：首頁 > IT技術(shù) > 編程語言 > 正文

數(shù)據(jù)結(jié)構(gòu)與算法 線性表
2022-04-25 23:06:40


一、線性表的定義

線性表(List)：由零個或多個數(shù)據(jù)元素組成的有限序列。

這里需要強調(diào)幾個關(guān)鍵的地方：

  • 首先它是一個序列，也就是說元素之間是有個先來后到的。
  • 若元素存在多個，則第一個元素?zé)o前驅(qū)，而最后一個元素?zé)o后繼，而其他元素都有且只有一個前驅(qū)和后繼。
  • 另外，線性表強調(diào)是有限的，事實上無論計算機發(fā)展多強大，它所處理的元素都是有限的。

二、數(shù)據(jù)類型的定義

數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱（整型、浮點型、字符型）。

三、線性表的抽象數(shù)據(jù)類型

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的元素個數(shù)。
//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);
        }
    }
}

四、線性表的順序存儲結(jié)構(gòu)

線性表的順序存儲結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。（像C語言的數(shù)組）

物理上的存儲方式實際上就是在內(nèi)存中找個初始地址，然后通過占位的形式，把一定的內(nèi)存空間給占了，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素依次存放在這塊空地中。

順序存儲結(jié)構(gòu)的結(jié)構(gòu)代碼

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;//線性表當(dāng)前長度
} SqList;

大家看到了，這里我們封裝了一個結(jié)構(gòu)，事實上就是對數(shù)組進行封裝，增加了一個當(dāng)前長度的變量罷了。

總結(jié)下，順序存儲結(jié)構(gòu)封裝需要三個屬性：

1.存儲空間的起始位置，數(shù)組data，它的存儲位置就是線性表存儲空間的存儲位置。

2.線性表的最大存儲容量：數(shù)組的長度MAXSIZE

3.線性表的當(dāng)前長度：length

地址計算方法

假設(shè)ElemType占用的是C個存儲單元（字節(jié)），那么線性表中第i+1個數(shù)據(jù)元素和第i個數(shù)據(jù)元素的存儲位置關(guān)系是(Loc表示獲得存儲位置的函數(shù))：LOC(ai+1) = LOC(ai) + c;

所以對于第i個數(shù)據(jù)元素ai的存儲位置可以由a1推算出：LOC(ai) = LOC(a1) + (i-1)*c;

通過這個公式，我們可以隨時計算出線性白哦中任意位置的地址，不管它是第一個還是最后一個，都是相同的時間。那么它的存儲時間性能當(dāng)然就為O(1)，我們通常稱為隨機存儲結(jié)構(gòu)。

獲得元素操作

實現(xiàn)GetElem的具體操作，即將線性表L中的第i個位置元素值返回。就程序而言非常簡單了，我們只需要把數(shù)組第i-1下標(biāo)的值返回即可。

GetElem.c

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
//Status是函數(shù)的類型，其值是函數(shù)結(jié)果的狀態(tài)碼，入OK等。
//初始條件：順序線性表L已存在，1 <= i <= ListLength(L)
//操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值

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.如果線性表長度大于等于數(shù)組長度，則拋出異?；騽討B(tài)增加數(shù)組容量；

3.從最后一個元素開始向前遍歷到第i個位置，分別將他們都向后移動一個位置；

4.將要插入元素填入位置i處；

5.線性表長度+1。

ListInsert.c

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e,L長度+1

Ststus ListInsert(SqList *L,int i;ElemTYpe e){
    int k;
    if(L->length == MAXSIZE){//順序線性表已經(jīng)滿了
        return ERROR;
    }
    if(i<1 || i>L->length){//當(dāng)i不在范圍內(nè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)
//操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用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;
}

性能分析

現(xiàn)在我們分析一下，插入和刪除的時間復(fù)雜度。

最好的情況：插入和刪除操作剛好要求在最后一個位置，因為不需要移動任何元素，所以此時的時間復(fù)雜度為O(1)。

最壞的情況：如果要插入和刪除的位置是第一個元素，那就意味著要移動所有的元素像后或者向前，所以這個時間復(fù)雜度為O(n)。

至于平均情況，就去中間值O((n-1)/2) = O(n)。

線性表的優(yōu)缺點

線性表的順序存儲結(jié)構(gòu)，在存、讀數(shù)據(jù)時，不管是哪個位置，時間復(fù)雜度都是O(1)。而在插入或刪除時，使勁復(fù)雜度都是O(n)。

這就說明，他比較適合元素個數(shù)比較穩(wěn)定，不經(jīng)常插入和刪除，而更多的操作是存取數(shù)據(jù)的應(yīng)用。

優(yōu)點：
1、無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間。
2、可以快速的存取表中的任意位置的元素。

缺點：
1、插入和刪除操作需要移動大量元素。
2、當(dāng)線性表長度變化較大時，難以確定存儲空間的容量。
3、容易造成存儲空間的“碎片”。

五、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以存在內(nèi)存中未被占用的任意位置。

比起順序存儲結(jié)構(gòu)每個數(shù)據(jù)元素只需要存儲一個位置就可以了?，F(xiàn)在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，除了要存儲數(shù)據(jù)元素信息外，還要存儲它的后繼元素的存儲地址（指針）。

我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為執(zhí)指針域。指針域中存儲的信息稱為指針或鏈。這兩部分信息組成數(shù)據(jù)元素稱為存儲映像，稱為節(jié)點(Node)。

因為此鏈表的每個節(jié)點中包含一個指針域，所以叫做單鏈表。

對于線性表來說，總得有個頭有個尾，鏈表也不例外。我們把鏈表中的第一個節(jié)點的存儲位置叫做頭指針，最后以客觀節(jié)點指針為空(NULL)

頭指針與頭節(jié)點的異同

頭節(jié)點的數(shù)據(jù)域一般不存儲任何信息

頭指針：
頭指針是指鏈表指向第一個節(jié)點的指針，若鏈表有頭節(jié)點，則是指向頭節(jié)點的指針。
頭指針具有標(biāo)識作用，所以常用頭指針冠以鏈表的名字（指針變量的名字）。
無論鏈表是否為空，頭指針均不為空。
頭指針是鏈表的必要元素。

頭節(jié)點：
頭節(jié)點是為了操作的統(tǒng)一和方便而設(shè)立的，方在第一個元素的節(jié)點前，其數(shù)據(jù)域一般無意義（但也可以用來存放鏈表的長度）。
有了頭節(jié)點，對在第一個元素節(jié)點前插入節(jié)點和刪除第一個節(jié)點其操作與其他節(jié)點的操作就統(tǒng)一了。
頭節(jié)點不一定是鏈表的必須要素。

我們在C語言中可以用結(jié)構(gòu)指針來描述單鏈表

typedef struct Node{
    ElemType data;//數(shù)據(jù)域
    struct Node *Next;//指針域
}Node;
typedef struct Node *LinkList;

我們看到節(jié)點由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼節(jié)點地址的指針域組成。

單鏈表的讀取

在線性表的順序存儲結(jié)構(gòu)中，我們要計算任意一個元素的存儲位置是很容易的。

但是在單鏈表中，由于第i個元素到底在哪？我們壓根沒辦法一開始就知道，必須得從第一個節(jié)點開始挨個找。

因此，對于單鏈表實現(xiàn)獲取第i個元素的數(shù)據(jù)的操作GetElem，在算法上相對要麻煩一些。

獲得鏈表第i個數(shù)據(jù)的算法思路：

1、申明一個節(jié)點p指向鏈表的第一個節(jié)點，初始化j從1開始；

2、當(dāng)j<i時，就遍歷鏈表，讓p的指針像后移動，不斷指向下一個節(jié)點，j+1;

3、若到鏈表末尾p為空，則說明第i個元素不存在；

4、若查找成功，返回節(jié)點p的數(shù)據(jù)。

GetElem.c

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值

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個元素為止。

由于這個算法的時間復(fù)雜度取決于i的為止，當(dāng)i=1時，則不需要遍歷，而i=n時則遍歷n-1次才可以。因此最壞情況的時間復(fù)雜度為O(n)。

由于單鏈表的結(jié)構(gòu)中沒有定義表長，所以不能實現(xiàn)知道要循環(huán)多少次，因此也就不方便使用for來控制循環(huán)。

其核心思想叫做“工作指針后移”，這其實也是很多算法的常用技術(shù)。

單鏈表的插入

假設(shè)存儲元素e的節(jié)點為s，要實現(xiàn)節(jié)點p、p->next和s之間邏輯關(guān)系

我們思考后發(fā)覺根本用不著驚動其他節(jié)點，只需要讓s->next和p->next的指針做一點變化。

s->next = p->next;
p->next = s;

那么我們考慮一下大部分初學(xué)者最容易搞壞腦子的問題：這兩句代碼的順序可以可以交換過來？

p->next = s;
s->next = p->next;

如果先執(zhí)行p->next = s 的話會先被覆蓋為s的地址，那么s->next = p->next其實就等于s->next = s 了。

所以這兩句是無論如何不能弄反的，這點初學(xué)者一定要注意。

單鏈表第i個數(shù)據(jù)插入節(jié)點的算法思路：

1、聲明一節(jié)點p指向鏈表頭節(jié)點，初始化j從1開始；

2、當(dāng)j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一節(jié)點，j累加1;

3、若到鏈表末尾p為空，則說明第i個元素不存在；

4、否則查找成功，在系統(tǒng)中生成一個空節(jié)點s；

5、將數(shù)據(jù)元素e復(fù)制給s->data;

6、單鏈表的插入剛才兩個標(biāo)準(zhǔn)語句；

7、返回成功。

//初始條件：鏈表L已經(jīng)存在，1<=i<=ListLength(L)
//操作結(jié)果：在L中第i個位置前插入新的數(shù)據(jù)元素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;
}

單鏈表的刪除

假設(shè)元素a2的節(jié)點為q，要實現(xiàn)節(jié)點q刪除單鏈表的操作，其實就是將它的前繼節(jié)點的指針繞過指向后繼節(jié)點即可。

那我們要做的，實際上就是一步：

p->next = p->next->next;
或
q = p->next;
p->next = q->next;

單鏈表的刪除節(jié)點的算法思路：

1、申明節(jié)點p指向鏈表第一個節(jié)點，初始化j = 1;

2、當(dāng)j<i時，就遍歷鏈表，讓P的指針向后移動，不斷指向下一個節(jié)點，j累加1;

3、若到鏈表末尾p為空，則說明第i個元素不存在；

4、否則查找成功，將欲刪除節(jié)點p->next賦值給q;

5、單鏈表的刪除標(biāo)準(zhǔn)語句p->next = q->next;

6、將q節(jié)點中的數(shù)據(jù)賦值給e,作為返回；

7、釋放q節(jié)點。

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

我們發(fā)現(xiàn)無論是單鏈表插入還是刪除算法，他們其實都是由兩部分組成：第一部分就是遍歷查找第i個元素，第二部分就是實現(xiàn)插入和刪除元素。

從整個算法來書，我們很容易可以退出他們的時間復(fù)雜度都是O(n)。

在詳細點分析：如果在我們不知道第i個元素的指針位置，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線性表的順序存儲結(jié)構(gòu)是沒有太大優(yōu)勢的。

但如果，我們希望從第i個位置開始，插入連續(xù)10個元素，對于順序存儲結(jié)構(gòu)意味著，每一次插入都需要移動n-1個位置，所以每次都是O(n)。

而單鏈表，我們只需要在第一次時，找到第i個位置的指針，此時為O(n),接下來只是簡單的通過復(fù)制移動指針而已，時間復(fù)雜度都是O(1)。

顯然，對于插入或刪除數(shù)據(jù)越頻繁的擦歐總，單鏈表的效率優(yōu)勢就越是明顯。

單鏈表的正表創(chuàng)建

對于順序存儲結(jié)構(gòu)的線性表的整表創(chuàng)建，我們可以用數(shù)組的初始化來直觀理解。

而單鏈表和順序存儲結(jié)構(gòu)就不一樣了，它不像順序存儲結(jié)構(gòu)數(shù)據(jù)這么集中，它的數(shù)據(jù)可以是分散在內(nèi)存各個角落的，它的增長也是動態(tài)的。

對于每個鏈表來說，它所占用空間的大小和位置是不需要魚線分配劃定的，可以根據(jù)系統(tǒng)的情況和實際的需求即時生成。

創(chuàng)建單鏈表的過程是一個動態(tài)生成鏈表的過程，從“空表”的初始狀態(tài)起，依次建立各個元素節(jié)點并逐個插入鏈表。

所以，單鏈表整表創(chuàng)建的算法思路如下：

1、聲明一個節(jié)點P和計數(shù)器變量i；

2、初始化一空鏈表L;

3、讓L的頭節(jié)點的指針指向NULL,即建立一個帶頭節(jié)點的單鏈表；

4、循環(huán)實現(xiàn)后繼節(jié)點的復(fù)制和插入。

頭插法建立單鏈表

頭插法從一個空表開始，生成新節(jié)點，讀取數(shù)據(jù)存放到新節(jié)點的數(shù)據(jù)域中，然后將新節(jié)點插入到當(dāng)前鏈表的表頭上，直到結(jié)束為止。

簡單來說，就是把新加進的元素放在表頭后的第一個位置：

先讓新節(jié)點的next指向頭節(jié)點之后

然后讓表頭的next指向新節(jié)點

void CreateListHead(LinkList *L,int n){
    LinkList p;
    int i;

    srand(time(0));//初始化隨機數(shù)字

    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;

    for(i=0;i<n;i++){
        p = (LinkLIst)malloc(sizeof(Node));//生成新節(jié)點
        p->data = rand()%100+1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

尾插法建立單鏈表

頭插法建立鏈表雖然算法簡單，但生成的鏈表中節(jié)點的次序和輸入的順序相反。

void CreateListTail(LinkList *L,int n){
    LinkList p,r;
    int i;

    srand(time(0));//初始化隨機數(shù)字

    *L = (LinkList)malloc(sizeof(Node));
    r = *L;

    for(i=0;i<n;i++){
        p = (LinkLIst)malloc(sizeof(Node));//生成新節(jié)點
        p->data = rand()%100+1;
        r->next = p;
        r = p;//備注：初學(xué)者可能很難理解這句，重點解釋。
    }
    r->next = NULL;
}

單鏈表的整表刪除

單鏈表整表刪除的算法思路如下：

1、申明節(jié)點p和q;

2、將第一個節(jié)點賦值給p，下一節(jié)點賦值給q；

3、循環(huán)執(zhí)行釋放p和將q復(fù)制給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;
}

六、單鏈表結(jié)構(gòu)與順序存儲結(jié)構(gòu)優(yōu)缺點

我們分別從存儲分配方式、時間性能、空間性能三方面來做對比。

存儲分配方式

順序存儲結(jié)構(gòu)用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

單鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，用一組任意的存儲單元存放線性表的元素。

時間性能

  • 1.查找

順序存儲結(jié)構(gòu)O(1)

單鏈表O(n)

  • 2.插入和刪除

順序存儲結(jié)構(gòu)需要平均移動表長一般的元素，時間為O(n)

單鏈表在計算出某位置的指針后，插入和刪除時間僅為O(1)

空間性能

順序存儲結(jié)構(gòu)需要預(yù)分配存儲空間，分大了，容易造成空間浪費，分小了，容易發(fā)生溢出。

單鏈表不需要分配存儲空間，只要有就可以分配，元素個數(shù)也不受限制。

經(jīng)驗性結(jié)論：

若線性表需要頻繁查找，很少進行插入和刪除操作時，宜采用順序存儲結(jié)構(gòu)。

若需要頻繁插入和刪除時，宜采用單鏈表結(jié)構(gòu)。

七、靜態(tài)鏈表

在講解原理之前，先讓大家直到這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表，這種描述方法叫做游標(biāo)實現(xiàn)法。

線性表的靜態(tài)鏈表存儲結(jié)構(gòu)

#define MAXSIZE 1000
typedef struct{
    ElemType data;//數(shù)據(jù)
    int cur;//游標(biāo)
}Component,StaticLinkList[MAXSIZE];

對靜態(tài)鏈表進行初始化相當(dāng)于初始化數(shù)組：

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;
}

我們對數(shù)組的第一個和最后一個元素做特俗處理，他們的data不存放數(shù)據(jù)。

我們通常把未使用的數(shù)組元素稱為備用鏈表。

數(shù)組的第一個元素，即下標(biāo)為0的那個元素的cur就存放備用鏈表的第一個節(jié)點的下標(biāo)。

數(shù)組的最后一個元素，即下標(biāo)為MAXSIZE-1的cur則存放第一個有數(shù)值的元素的下標(biāo)，相當(dāng)于單鏈表中的頭節(jié)點作用。

靜態(tài)鏈表的插入操作

首先是獲得空閑分量的下標(biāo)：
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;//數(shù)組的最后一個元素

    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;
}

靜態(tài)鏈表的刪除操作

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;
}

靜態(tài)鏈表優(yōu)缺點總結(jié)

  • 1、優(yōu)點

在插入和刪除操作時，只需要修改游標(biāo)，不需要移動元素，從而改進了在順序存儲結(jié)構(gòu)中的插入和刪除操作需要移動大量元素的缺點

  • 2、缺點

沒有解決連續(xù)存儲分配（數(shù)組）帶來的表長難以確定的問題

失去了順序存儲結(jié)構(gòu)隨機存取的特性。

  • 3、總結(jié)

總的來說，靜態(tài)鏈表其實是為了給沒有指針的編程語言設(shè)計的一種實現(xiàn)單鏈表功能的方法。

盡管我們可以用單鏈表就不用靜態(tài)鏈表了，但這樣的思考方式是非常巧妙的，應(yīng)該理解其思想，以備不時之需。

單鏈表小結(jié)騰訊面試題

題目：快速找到未知長度單鏈表的中間節(jié)點。

既然是面試題就一定有普通方法和高級方法，而高級方法，而高級方法無疑會讓面試官大大加分！

普通方法很簡單，首先遍歷一遍單鏈表以確定單鏈表的長度L。然后再次從頭節(jié)點觸發(fā)循環(huán)L/2次找到單鏈表的中間節(jié)點。

算法的復(fù)雜度為：O(L+L/2) = O(3/2L)

能否再優(yōu)化一下這個時間復(fù)復(fù)雜度呢？

有一個很巧妙的方法：利用快慢指針！

利用快慢指針原理：設(shè)置兩個指針*search、*mid都指向單鏈表的頭節(jié)點。其中*search的移動速度是*mid的2倍。當(dāng)*search指向末尾節(jié)點的時候，*mid正好就在中間了。這也是標(biāo)尺的思想。

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;
}

八、循環(huán)鏈表

對于單鏈表，由于每個節(jié)點只存儲了向后的指針，到了尾部標(biāo)識就停止了向后鏈的操作。也就是說，按照這樣的方式，只能索引后繼節(jié)點不能索引前驅(qū)節(jié)點。

這會帶來什么問題呢？

例如不從頭節(jié)點出發(fā)，就無法訪問到全部節(jié)點。

事實上要解決這個問題也并不麻煩，只需要將單鏈表中終端節(jié)點的指針由空指針改為指向頭節(jié)點，問題就結(jié)了。

將單鏈表中終端節(jié)點的指針端由空指針改為指向頭節(jié)點，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表成為單循環(huán)鏈表，簡稱循環(huán)鏈表。

初始化循環(huán)鏈表

//鏈表存儲結(jié)構(gòu)定義
typedef struct CLinkList{
    int data;
    struct ClinkList *next;
}

void ds_init(node **pNode){
    int item;
    node *temp;
    node *target;

    printf("輸入節(jié)點的值，輸入0完成初始化");

    while(1){
        scanf("%d",&item);
        fflush(stdin);

        if(item == 0){
           return;
        }

        if((*pNode == NULL)){
            //循環(huán)鏈表中只有一個節(jié)點
            *pNode = (node*)malloc(sizeiof(struct ClinkList));
            if(!(*pNode)){
                exit(0);
            }
            (*pNode)->data = item;
            (*pNode)->next = *pNode;
        }else{
            //找到next指向第一個節(jié)點的節(jié)點
            for(target = (*pNode);target->next!=(*pNode);target = target->next){
                
            }
            //生成一個新的節(jié)點
            temp = (node *)malloc(sizeof(struct CLinkList));
            if(!temp){
                exit(0);
            }

            temp->data = item;
            temp->next = *pNode;
            target->next = temp;
        }
    }
}

循環(huán)鏈表的插入

void ds_insert(node **pNode,int i){
    node *temp;
    node *target;
    node *p;
    int item;
    int j;

    printf("輸入要插入節(jié)點的值：");
    scanf("%d",&item);

    if(i == 1){
        //新插入的節(jié)點作為第一個節(jié)點
        temp = (node *)malloc(sizeof(struct CLinkList));

        if(!temp){
            exit(0);
        }
        temp->data = item;

        //尋找到最后一個節(jié)點
        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;
    }
}

循環(huán)鏈表返回節(jié)點位置

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;
    }
}

循環(huán)鏈表的特點

回顧一下，在單鏈表中，我們有了頭節(jié)點時，我們可以用O(1)的時間訪問第一個節(jié)點，但對于要訪問最后一個節(jié)點，我們必須要挨個向下索引，所以需要O(n)的時間。

如果用上今天我們學(xué)的循環(huán)鏈表的特點，用O(1)的時間就可以由鏈表指針訪問到最后一個節(jié)點。

不過我們需要改造一下現(xiàn)有的循環(huán)鏈表，我們不用頭指針，而是用指向指端節(jié)點的尾指針來表示循環(huán)鏈表，此時查找開始節(jié)點和終端節(jié)點都很方便了。

判斷單鏈表中是否有環(huán)

又環(huán)的定義是，鏈表的尾部節(jié)點指向了鏈表中的某個節(jié)點（不一定是第一個節(jié)點）。

那么要判斷單鏈表中是否有環(huán)，主要有一下兩種方法。

方法一：使用p、q兩個指針，p總是向前走，但q每次都從頭開始走，對于每個節(jié)點，看p走的步數(shù)是否和q一樣。如圖，當(dāng)p從6走到3時候，用了6步，此時若q從head出發(fā)則只需要兩部就到3，因為步數(shù)不等，出現(xiàn)矛盾，存在環(huán)。

方法二：使用p、q兩個指針，p每次向前走一步，q每次向前走兩步，若在某個時候p==q,則存在環(huán)。

循環(huán)鏈表的應(yīng)用-約瑟夫問題

據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：

在羅馬人占領(lǐng)橋塔帕特后，39個猶太人與Josephus及它的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人，排成一個圓圈，由第一個人開始報數(shù)，沒報數(shù)到第三個人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，它將朋友與自己安排在第16個與第31個位置，于是逃過了這場游戲。

問題：用循環(huán)鏈表模擬約瑟夫問題，把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;
}

循環(huán)鏈表的應(yīng)用-魔術(shù)師發(fā)牌問題

問題描述：魔術(shù)師利用一副牌中的13張黑牌，預(yù)先將他們排好后疊放在一起，牌面朝下。對著觀眾說：“我不看牌，只數(shù)數(shù)就可以猜到每張牌是什么”

#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;
}

//發(fā)牌順序計算
void Magician(linklist head){
    linklist p;
    int j;
    int Countnumber =2;
    
    p = head;
    p->data = 1;//第一張牌數(shù)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;
}

循環(huán)鏈表的應(yīng)用-拉丁方陣問題

拉丁方陣是一種n*n的方陣，方陣中恰有n種不同的元素，每種元素恰有n個，并且每種元素在一行和一列中恰好出現(xiàn)一次。著名數(shù)學(xué)家個物理學(xué)家歐拉使用拉丁字母來作為拉丁方陣?yán)镌氐姆?，拉丁方陣因此而得名?/p>

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;
    
}

九、雙向鏈表

雙向鏈表節(jié)點結(jié)構(gòu)

typedef struct DualNode{
    ElemType data;
    struct DualNode *prior;//前驅(qū)節(jié)點
    struct DualNode *next;//后繼節(jié)點
}DualNode，*DualList;

既然單鏈表可以有循環(huán)鏈表，那么雙向鏈表當(dāng)然也可以有

雙向鏈表的插入

插入操作其實并不復(fù)雜，不過順序很重要，千萬不能寫反了。

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;

關(guān)鍵在于交換的過程中不要出現(xiàn)矛盾，例如第四步先被執(zhí)行了，那么p->prior就會提前變?yōu)閟,使得插入的工作出錯。

雙向鏈表的刪除操作

如果剛才的插入操作理解了，那么再來理解接下來的刪除操作就容易多了。

p->prior->next = p->next;
p->next->prior = p->proor;
free(p);

最后總結(jié)一下，雙向鏈表相對于單鏈表來說，是要更復(fù)雜一點，買個節(jié)點多了一個prior指針，對于插入和刪除操作的順序大家要格外小心。

不過，雙向鏈表可以有效提高算法的時間性能，說白了就是用空間來換取時間。

????




本文摘自 ：https://blog.51cto.com/u

開通會員，享受整站包年服務(wù)立即開通 >
推薦內(nèi)容