国产综合色产免费视频,国产在线欧美日韩精品一区

一、線性表的定義

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

這里需要強調幾個關鍵的地方：

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

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

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

三、線性表的抽象數(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);
        }
    }
}

四、線性表的順序存儲結構

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

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

順序存儲結構的結構代碼

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

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

總結下，順序存儲結構封裝需要三個屬性：

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

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

3.線性表的當前長度：length

地址計算方法

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

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

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

獲得元素操作

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

GetElem.c

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

typedef int Status;
//Status是函數(shù)的類型，其值是函數(shù)結果的狀態(tài)碼，入OK等。
//初始條件：順序線性表L已存在，1 <= i <= ListLength(L)
//操作結果：用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ù)組長度，則拋出異常或動態(tài)增加數(shù)組容量；

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

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

5.線性表長度+1。

ListInsert.c

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結果：在L中第i個位置之前插入新的數(shù)據(jù)元素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個數(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)在我們分析一下，插入和刪除的時間復雜度。

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

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

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

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

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

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

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

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

五、線性表的鏈式存儲結構

線性表鏈式存儲結構定義

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以存在內存中未被占用的任意位置。

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

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

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

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

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

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

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

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

我們在C語言中可以用結構指針來描述單鏈表

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

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

單鏈表的讀取

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

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

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

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

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

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

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

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

GetElem.c

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結果：用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個元素為止。

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

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

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

單鏈表的插入

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

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

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

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

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

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

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

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

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

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

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

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

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

6、單鏈表的插入剛才兩個標準語句；

7、返回成功。

//初始條件：鏈表L已經存在，1<=i<=ListLength(L)
//操作結果：在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;
}

單鏈表的刪除

假設元素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、當j<i時，就遍歷鏈表，讓P的指針向后移動，不斷指向下一個節(jié)點，j累加1;

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

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

5、單鏈表的刪除標準語句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)插入和刪除元素。

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

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

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

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

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

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

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

而單鏈表和順序存儲結構就不一樣了，它不像順序存儲結構數(shù)據(jù)這么集中，它的數(shù)據(jù)可以是分散在內存各個角落的，它的增長也是動態(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é)點的復制和插入。

頭插法建立單鏈表

頭插法從一個空表開始，生成新節(jié)點，讀取數(shù)據(jù)存放到新節(jié)點的數(shù)據(jù)域中，然后將新節(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;//備注：初學者可能很難理解這句，重點解釋。
    }
    r->next = NULL;
}

單鏈表的整表刪除

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

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

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

3、循環(huán)執(zhí)行釋放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;
}

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

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

存儲分配方式

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

單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的元素。

時間性能

1.查找

順序存儲結構O(1)

單鏈表O(n)

2.插入和刪除

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

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

空間性能

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

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

經驗性結論：

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

若需要頻繁插入和刪除時，宜采用單鏈表結構。

七、靜態(tài)鏈表

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

線性表的靜態(tài)鏈表存儲結構

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

對靜態(tài)鏈表進行初始化相當于初始化數(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ù)組的第一個元素，即下標為0的那個元素的cur就存放備用鏈表的第一個節(jié)點的下標。

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

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

首先是獲得空閑分量的下標：
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)缺點總結

1、優(yōu)點

在插入和刪除操作時，只需要修改游標，不需要移動元素，從而改進了在順序存儲結構中的插入和刪除操作需要移動大量元素的缺點

2、缺點

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

失去了順序存儲結構隨機存取的特性。

3、總結

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

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

單鏈表小結騰訊面試題

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

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

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

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

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

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

利用快慢指針原理：設置兩個指針*search、*mid都指向單鏈表的頭節(jié)點。其中*search的移動速度是*mid的2倍。當*search指向末尾節(jié)點的時候，*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;
}

八、循環(huán)鏈表

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

這會帶來什么問題呢？

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

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

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

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

//鏈表存儲結構定義
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)的時間。

如果用上今天我們學的循環(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一樣。如圖，當p從6走到3時候，用了6步，此時若q從head出發(fā)則只需要兩部就到3，因為步數(shù)不等，出現(xiàn)矛盾，存在環(huán)。

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

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

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

在羅馬人占領橋塔帕特后，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)鏈表的應用-魔術師發(fā)牌問題

問題描述：魔術師利用一副牌中的13張黑牌，預先將他們排好后疊放在一起，牌面朝下。對著觀眾說：“我不看牌，只數(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)鏈表的應用-拉丁方陣問題

拉丁方陣是一種n*n的方陣，方陣中恰有n種不同的元素，每種元素恰有n個，并且每種元素在一行和一列中恰好出現(xiàn)一次。著名數(shù)學家個物理學家歐拉使用拉丁字母來作為拉丁方陣里元素的符號，拉丁方陣因此而得名。

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é)點結構

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

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

雙向鏈表的插入

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

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

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

雙向鏈表的刪除操作

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

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

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

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

????

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

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

一、線性表的定義

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

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

Operation

四、線性表的順序存儲結構

地址計算方法

獲得元素操作

插入操作

刪除操作

性能分析

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

五、線性表的鏈式存儲結構

線性表鏈式存儲結構定義

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

單鏈表的讀取

單鏈表的插入

單鏈表的刪除

效率PK

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

頭插法建立單鏈表

尾插法建立單鏈表

單鏈表的整表刪除

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

存儲分配方式

時間性能

空間性能

經驗性結論：

七、靜態(tài)鏈表

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

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

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

八、循環(huán)鏈表

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

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

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

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

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

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

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

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

九、雙向鏈表

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

雙向鏈表的插入

雙向鏈表的刪除操作

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

一、線性表的定義

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

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

四、線性表的順序存儲結構

七、靜態(tài)鏈表

八、循環(huán)鏈表

九、雙向鏈表