關于線性表那些事

概念

線性表是零個或多個具有相同特性的數據元素組成的有限序列，該序列中所含元素的個數叫做線性表的長度挨稿，線性表有以下幾個特點：

  • 首先是一個序列

  • 其次是有限的

  • 可以是有序的也可以是無序的

  • 線性表的開始元素沒有前驅元素只有后繼元素猖任，線性表的結束元素沒有后繼元素只有前驅元素，除了開頭元素和結尾元素以外，每個元素都有且只有一個前驅元素和后繼元素

線性表的結構分為順序結構和鏈式結構

順序結構

順序表就是把線性表中的所有元素按照某種邏輯順序屉符，依次存儲到從指定位置開始的一塊連續(xù)的存儲空間析恋，重點是連續(xù)的存儲空間良哲。

數組長度和線性表的長度區(qū)別：數組長度是存放線性表的存儲空間的長度，存儲分配后這個量一般是不變的助隧，線性表的長度是線性表中數據元素的個數筑凫，隨著線性表插入和刪除操作的進行，這個量是變化的并村。

關于順序表的創(chuàng)建和初始化


#define SUCCESS 1

#define FAIL 0

typedef int elemType;

typedef int status;

typedef struct {

    elemType *data;

    int length;

}Sqlist;

status initList(Sqlist *list){

    list->data =  malloc(sizeof(elemType) * MAXSIZE);

    if(!list->data) exit(FAIL);

    list->length = 0;

    return SUCCESS;

}

插入算法步驟

  • 如果插入位置不合理巍实，拋出異常；

  • 如果線性表長度大于等于數組長度哩牍，則拋出異彻睿或動態(tài)增加容量夸浅；

  • 從最后一個元素開始向前遍歷到第i個位置，分別將它們都向后移動一個位置蚪黑；

  • 將要插入的元素填入位置i處；

  • 長度+1

代碼如下：

status insertData(Sqlist *list,int index,elemType data){
    if((index<1) || (index>list->length+1)) return FAIL;

    //存儲空間已滿
    if(L->length == MAXSIZE) return FAIL;

    //插入數據不在表尾,則先移動出空余位置
    if(index <= list->length){
        for(int j = list->length-1; j>=index-1;j--){
            list->data[j+1] = L->data[j];
        }
    }

    list->data[index-1] = data;
    ++list->length;//長度+1
    return SUCCESS;
}

刪除步驟

  • 如果刪除位置不合理，拋出異常；

  • 取出刪除元素；

  • 從刪除位置開始遍歷到最后一個元素位置纬朝，分別將它們都向前移動一個位置；

  • 長度減1

代碼如下：

status listDelete(Sqlist *list,int i){

    //線性表為空
    if(list->length == 0) return FAIL;

    //i值不合法判斷
    if((i<1) || (i>list->length+1)) return FAIL;
    for(int j = i; j < list->length;j++){
        //被刪除元素之后的元素向前移動
        list->data[j-1] = list->data[j];
    }

    //表長度-1;
    list->length --;
    return SUCCESS;
}

鏈式結構

鏈式結構如圖所示

鏈式結構.png

鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素骄呼，這組存儲單元可以是連續(xù)的共苛，也可以是不連續(xù)的。這就意味著蜓萄，這些數據元素可以存在內存未被占用的任意位置俄讹。

在順序存儲結構中，每個數據元素只需要存儲數據元素就可以了∪频拢現在鏈式結構中患膛，處理要存儲數據元素信息之外，還要存儲它的后繼元素的存儲地址耻蛇。

在鏈表中踪蹬，為了方便定位鏈表，我們一般會在創(chuàng)建鏈表的時候臣咖，先給他一個頭節(jié)點跃捣，頭節(jié)點沒有實際內容的作用，作為一個鏈表的哨兵夺蛇，可以方便定位疚漆。

鏈表主要分成單向鏈表、單向循環(huán)鏈表刁赦、雙向鏈表娶聘、雙向循環(huán)鏈表，下面我們分別來講講甚脉。

單向鏈表

單向鏈表每一個節(jié)點丸升，都包含一個data和一個指向下一個節(jié)點的指針


單向鏈表.png

在初始化單向鏈表的時候，需要注意頭節(jié)點是沒有內容的牺氨，->next下一個節(jié)點才是真正的首元節(jié)點狡耻，代碼如下：

Status InitList(LinkList *L){
    *L = (LinkList)malloc(sizeof(Node));
    //存儲空間分配失敗
    if(*L == NULL) return ERROR;
    //將頭結點的指針域置空
    (*L)->next = NULL;
    return OK;
}

單向鏈表插入和刪除

先來看下示意圖：

單向鏈表插入刪除.png

插入的主要步驟：

  • 定義一個指針指向鏈表頭節(jié)點，初始化j從1開始猴凹；

  • 當j < i 時夷狰，就遍歷鏈表，讓p的指針向后移動郊霎，不斷指向下一個結點沼头，j累加1；

  • 若到鏈表末尾p為空歹篓，則說明第i個結點不存在瘫证；否則查找成功，在系統(tǒng)中生成一個空結點s

  • 將數據元素e賦值給 s->data庄撮；

  • 單鏈表的插入標準語句 s->next; p->next=s;

  • 返回成功

刪除的主要步驟

  • 定義兩個指針指p背捌、s指向鏈表頭節(jié)點，初始化i從1開始

  • 判斷當前鏈表是否只有頭節(jié)點洞斯，如果不存在其他節(jié)點毡庆，return error，否則繼續(xù)執(zhí)行

  • 判斷是否刪除的首元節(jié)點烙如，刪除第一個節(jié)點的時候需要注意把頭節(jié)點的指針移動到下一個節(jié)點

  • 釋放么抗，并返回成功

代碼如下：
單向鏈表插入

Status ListInsert(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    //尋找第i-1個結點
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    //第i個元素不存在
    if(!p || j>i) return ERROR;
    //生成新結點s
    s = (LinkList)malloc(sizeof(Node));
    //將e賦值給s的數值域
    s->data = e;
    //將p的后繼結點賦值給s的后繼
    s->next = p->next;
    //將s賦值給p的后繼
    p->next = s;
    return OK;
}

單向鏈表刪除

Status ListDelete(LinkList *L,int i,ElemType *e){
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    //查找第i-1個結點,p指向該結點
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }

    //當i>n 或者 i<1 時,刪除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;

    //q指向要刪除的結點
    q = p->next;

    //將q的后繼賦值給p的后繼
    p->next = q->next;

    //將q結點中的數據給e
    *e = q->data;

    //讓系統(tǒng)回收此結點,釋放內存;
    free(q);
    return OK;
}

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

先來看一下單向循環(huán)鏈表和單向鏈表的區(qū)別，單向循環(huán)鏈表圖如下

單向循環(huán)鏈表.png

單向循環(huán)鏈表就像一個首尾相接的蛇亚铁，他的最后一個節(jié)點的next不是指向NULL蝇刀，而是指向了首元節(jié)點，以此達到循環(huán)徘溢。在初始化的時候吞琐，需要注意

初始化的時候，需要創(chuàng)建一個新的節(jié)點指向自身然爆，往里面增加節(jié)點的時候需要注意最后一個節(jié)點需要指向首元節(jié)點站粟。


#define ERROR 0
#define OK 1
#define MAXSIZE 20

typedef int Status; /* Status是函數的類型,其值是函數結果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據實際情況而定曾雕，這里假設為int */

//定義結點
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

Status CreateList(LinkList *L){
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("輸入節(jié)點的值奴烙，輸入0結束\n");
    while(1) {
        scanf("%d",&item);
        if(item==0) break;
        //如果輸入的鏈表是空。則創(chuàng)建一個新的節(jié)點剖张，使其next指針指向自己 
        (*head)->next=*head;
        if(*L==NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L) exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        } else {
          //輸入的鏈表不是空的切诀，尋找鏈表的尾節(jié)點，使尾節(jié)點的next=新節(jié)點搔弄。新節(jié)點的next指向頭節(jié)點
            for (target = *L; target->next != *L; target = target->next);
            temp=(LinkList)malloc(sizeof(Node));
            if(!temp) return ERROR;
            temp->data=item;
            temp->next=*L;  //新節(jié)點指向頭節(jié)點
            target->next=temp;//尾節(jié)點指向新節(jié)點
        }
    }
    return OK;
}

單向循環(huán)鏈表插入和刪除

插入的主要步驟：

  • 定義一個指針target指向鏈表頭節(jié)點趾牧，初始化j從1開始；

  • 當j < i 時肯污，就遍歷鏈表翘单，讓target的指針向后移動，不斷指向下一個結點蹦渣，j累加1哄芜；

  • 若到鏈表末尾target為空，則說明第i個結點不存在柬唯；否則查找成功认臊，在系統(tǒng)中生成一個空結點s

  • 將數據元素e賦值給 temp->data = data；

  • 單鏈表的插入標準語句 temp->next = target->next; target->next = temp;

  • 返回成功

需要注意的是锄奢，在插入節(jié)點的時候失晴，我們需要判斷插入位置是否是第一個節(jié)點剧腻。如果是第一個節(jié)點，需要讓新的節(jié)點next指向原節(jié)點涂屁，并且頭節(jié)點指向新增加節(jié)點书在，修改尾節(jié)點。

刪除的主要步驟

  • 定義兩個指針指temp拆又、taeget向鏈表頭節(jié)點儒旬，初始化i從1開始

  • 判斷當前鏈表收否只有頭節(jié)點，如果不存在其他節(jié)點帖族，return error栈源，否則繼續(xù)執(zhí)行

  • 刪除找到的節(jié)點，修改前一個節(jié)點的next指向竖般，釋放被刪除的節(jié)點

  • 返回成功

刪除需要注意頭節(jié)點

代碼定義如下


Status ListInsert(LinkList *L, int place, int num) {
    LinkList temp, target;
    int i;
    if (place == 1) {
        //如果插入的位置為1,則屬于插入首元結點,所以需要特殊處理
        //1. 創(chuàng)建新結點temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
        //2. 找到鏈表最后的結點_尾結點,
        //3. 讓新結點的next 執(zhí)行頭結點.
        //4. 尾結點的next 指向新的頭結點;
        //5. 讓頭指針指向temp(臨時的新結點)
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (target = *L; target->next != *L; target = target->next);
        temp->next = *L;
        target->next = temp;
        *L = temp;
    } else {
        //如果插入的位置在其他位置;
        //1. 創(chuàng)建新結點temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;
        //2. 先找到插入的位置,如果超過鏈表長度,則自動插入隊尾;
        //3. 通過target找到要插入位置的前一個結點, 讓target->next = temp;
        //4. 插入結點的前驅指向新結點,新結點的next 指向target原來的next位置 ;
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) ;
        temp->next = target->next;
        target->next = temp;
    }
    return OK;
}

Status  LinkListDelete(LinkList *L, int place) {
    LinkList temp, target;
    int i;

    //temp 指向鏈表首元結點
    temp = *L;
    if (temp == NULL) return ERROR;
    if (place == 1) {
        if ((*L)->next == (*L)) {
            (*L) = NULL;
            return OK;
        }
        target->next = (*L)->next;
        for (target = *L; target->next != *L; target = target->next) ;

        temp = *L;
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    } else {
        for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) ;
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}

雙向鏈表和雙向循環(huán)鏈表

雙向鏈表相比較單向鏈表甚垦，多了一個前驅，而雙向循環(huán)鏈表的則在雙向鏈表的情況下涣雕，多了首尾的指向

雙向鏈表.png
雙向循環(huán)鏈表.png

初始化

雙向和雙向循環(huán)鏈表創(chuàng)建.png

對比的代碼如下

// 雙向鏈表
Status CreateList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));
    if ((*L) == NULL) return ERROR;
    (*L)->prior = NULL;
    (*L)->next = NULL;
    return OK;
}

// 雙向循環(huán)鏈表
Status CreateList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));
    if ((*L) == NULL) return ERROR;
    (*L)->prior = *L;  // 這里和上面不一樣制轰，指向自己，
    (*L)->next = *L; 
    return OK;
}

插入

雙向鏈表的插入和單向列表的插入對比胞谭，其實是相似的垃杖，不同之處在于，雙向鏈表在找到需要插入的節(jié)點后丈屹，需要先指定插入節(jié)點的prior和next调俘，然后再確定proir->next 和 next->prior，大致步驟如下

  • 判斷插入的位置是否合法旺垒，不合法return error彩库，創(chuàng)建節(jié)點temp和指向頭節(jié)點的鏈表p，i從1開始

  • 遍歷鏈表先蒋，讓p的指針向后移動骇钦，不斷指向下一個結點，i累加1竞漾；

  • 若到鏈表末尾p為空眯搭，則說明第i個結點不存在；否則查找成功业岁，在系統(tǒng)中生成一個空結點temp

  • 將數據元素e賦值給 temp->data = e鳞仙；

  • 指定temp的前驅和后驅

  • 替換temp的前驅的后驅，temp后驅的前驅

  • 返回成功

需要注意的是笔时，在插入節(jié)點的時候棍好，我們需要判斷插入位置是否是第一個節(jié)點。如果是第一個節(jié)點，需要讓新的節(jié)點next指向原節(jié)點借笙，并且頭節(jié)點指向新增加節(jié)點扒怖，修改尾節(jié)點。

雙向循環(huán)鏈表步驟比雙向鏈表业稼，少了一步判斷首元節(jié)點盗痒，因為循環(huán)鏈表的尾節(jié)點就是指向首元節(jié)點。但是需要判斷尾節(jié)點的指向

代碼如下：

// 插入
Status ListInsert(LinkList *L, int place , ElemType v) {
    if (place < 1) return ERROR;
    LinkList temp = (LinkList)malloc(sizeof(Node));

    if (temp == NULL) return ERROR;
    temp->data = v;
    temp->prior = NULL;
    temp->next = NULL;
    // 找到插入前的節(jié)點
    LinkList p = *L;
    // 找到插入位置 (place 位置的前一個結點)
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }

    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        p->next->prior = temp;
        temp->next = p->next;
        temp->prior = p;
        p->next = temp;
    }
    return OK;
}

Status ListInsert(LinkList *L, int place , ElemType v) {
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    // 新節(jié)點
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->data = v;
    temp->prior = NULL;
    temp->next = NULL;

    // 找到插入前的節(jié)點
    LinkList p = *L;

    // 找到插入位置 (place 位置的前一個結點)
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }

    // 注意：因為有頭節(jié)點盼忌，所有新節(jié)點一定是在頭節(jié)點之后，所以頭指針L掂墓，一定指向頭節(jié)點
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        p->next->prior = temp;
        temp->next = p->next;
        temp->prior = p;
        p->next = temp;
    }
    return OK;
}

刪除

雙向鏈表對比與單向鏈表的刪除谦纱，需要注意是不是刪除尾節(jié)點，因為尾節(jié)點的next需要為NULL君编；雙向循環(huán)鏈表的刪除對比單向循環(huán)鏈表跨嘉，仍然需要考慮是不是尾節(jié)點，因為他有下一個節(jié)點吃嘿，把下一個節(jié)點和他前一個節(jié)點建立互相指向祠乃，釋放自己。因為有頭節(jié)點的引入兑燥，所以我們不需要額外關注頭指針的指向了亮瓷。

代碼示例如下：

// 雙向鏈表刪除
Status ListDelete(LinkList *L, int place, ElemType *v) {
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    // 找到place位置的節(jié)點
    LinkList p = (*L)->next; // 從首元節(jié)點開始
    int i = 1
    for (; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    if (i < place) return ERROR;
    *v = p->data;
    if (p->next == NULL) {
        p->prior->next = NULL;
        free(p);
    } else {
        // p是任意位置的節(jié)點
        // 1、將p的后一個節(jié)點指向p的前一個節(jié)點
        // 2降瞳、將p的前一個節(jié)點指向p的后一個節(jié)點
        // 3嘱支、釋放
        p->next->prior = p->prior;
        p->prior->next = p->next;
        free(p);
    }
    return 1;
}

// 雙向循環(huán)鏈表刪除
Status ListDelete(LinkList *L, int place, ElemType *v) {
    if (place < 1) return ERROR;
    LinkList p = (*L)->next; // 從首元節(jié)點開始
    int i = 1;
    for (; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    if (i < place) return ERROR;
    *v = p->data;
    // p是任意位置的節(jié)點
    // 1、將p的后一個節(jié)點指向p的前一個節(jié)點
    // 2挣饥、將p的前一個節(jié)點指向p的后一個節(jié)點
    // 3除师、釋放

    p->next->prior = p->prior;
    p->prior->next = p->next;
    free(p);
    return 1;
}

結尾

總算把單向鏈表、單向循環(huán)鏈表扔枫、雙向鏈表汛聚、雙向循環(huán)鏈表理了一遍，但是結尾處有點匆忙短荐，下次有時間再補一下圖片和詳細優(yōu)化吧倚舀。寫博客真的好累啊(′▽｀)

?著作權歸作者所有,轉載或內容合作請聯系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個濱河市忍宋，隨后出現的幾起案子瞄桨，更是在濱河造成了極大的恐慌，老刑警劉巖讶踪，帶你破解...
    沈念sama閱讀 206,214評論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件芯侥，死亡現場離奇詭異，居然都是意外死亡，警方通過查閱死者的電腦和手機柱查，發(fā)現死者居然都...
    沈念sama閱讀 88,307評論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門廓俭，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人唉工，你說我怎么就攤上這事研乒。” “怎么了淋硝？”我有些...
    開封第一講書人閱讀 152,543評論 0贊 341
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵雹熬，是天一觀的道長。 經常有香客問我谣膳，道長竿报，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 55,221評論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任继谚，我火速辦了婚禮烈菌，結果婚禮上，老公的妹妹穿的比我還像新娘花履。我一直安慰自己芽世，他們只是感情好，可當我...
    茶點故事閱讀 64,224評論 5贊 371
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布诡壁。 她就那樣靜靜地躺著济瓢，像睡著了一般。 火紅的嫁衣襯著肌膚如雪妹卿。 梳的紋絲不亂的頭發(fā)上葬荷，一...
    開封第一講書人閱讀 49,007評論 1贊 284
  • 城市分裂傳說
    那天，我揣著相機與錄音纽帖，去河邊找鬼宠漩。 笑死，一個胖子當著我的面吹牛懊直，可吹牛的內容都是我干的扒吁。 我是一名探鬼主播，決...
    沈念sama閱讀 38,313評論 3贊 399
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼室囊，長吁一口氣：“原來是場噩夢啊……” “哼雕崩！你這毒婦竟也來了？” 一聲冷哼從身側響起融撞，我...
    開封第一講書人閱讀 36,956評論 0贊 259
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤盼铁，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后尝偎，有當地人在樹林里發(fā)現了一具尸體饶火，經...
    沈念sama閱讀 43,441評論 1贊 300
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡鹏控，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 35,925評論 2贊 323
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現自己被綠了肤寝。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片当辐。...
    茶點故事閱讀 38,018評論 1贊 333
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖鲤看，靈堂內的尸體忽然破棺而出缘揪，到底是詐尸還是另有隱情，我是刑警寧澤义桂，帶...
    沈念sama閱讀 33,685評論 4贊 322
  • ?日本核電站爆炸內幕
    正文 年R本政府宣布找筝，位于F島的核電站，受9級特大地震影響慷吊，放射性物質發(fā)生泄漏袖裕。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 39,234評論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一罢浇、第九天 我趴在偏房一處隱蔽的房頂上張望陆赋。 院中可真熱鬧沐祷，春花似錦嚷闭、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,240評論 0贊 19
  • 一樁弒父案胞锰，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至兢榨，卻和暖如春嗅榕，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背吵聪。 一陣腳步聲響...
    開封第一講書人閱讀 31,464評論 1贊 261
  • 情欲美人皮
    我被黑心中介騙來泰國打工凌那， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人吟逝。 一個月前我還...
    沈念sama閱讀 45,467評論 2贊 352
  • 代替公主和親
    正文 我出身青樓帽蝶，卻偏偏與公主長得像，于是被迫代替她去往敵國和親块攒。 傳聞我的和親對象是個殘疾皇子励稳，可洞房花燭夜當晚...
    茶點故事閱讀 42,762評論 2贊 345