線性表的類型定義

線性表是n個(gè)數(shù)據(jù)元素的有限序列。在稍復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成矾瑰，此時(shí)把數(shù)據(jù)元素稱為記錄跷坝，含有大量記錄的線性表稱為文件酵镜。例如：

• 每一行稱作數(shù)據(jù)元素
• 姓名碉碉、年齡、學(xué)號(hào)和成績(jī)稱為數(shù)據(jù)項(xiàng)

由此可見(jiàn)淮韭，線性表中數(shù)據(jù)元素可以是各式各樣的垢粮，但同一線性表中的元素必定具有相同特性。相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系靠粪。除首尾蜡吧，每個(gè)元素都有唯一前驅(qū)和唯一后繼。

• 抽象數(shù)據(jù)類型線性表的定義

ADT List{
    數(shù)據(jù)對(duì)象：D = {ai | ai ∈ ElemSet, i =1,2,  ... , n, n≥0}
    數(shù)據(jù)關(guān)系：R1 = {<ai-1,ai> | ai-1, ai∈D庇配， i=2 ,3, ..., n}
    基本操作：
        InitList( &L )
            操作結(jié)果：構(gòu)造一個(gè)空的線性表L斩跌。
        DestroyList(&L )
            初始條件：線性表L已存在
            操作結(jié)果：銷毀線性表L
        ClearList(& L )
            初始條件：線性表L已存在
            操作結(jié)果：將L重置為空表
        ListEmpty( L )  //判斷是否為空
            初始條件：線性表L已存在
            操作結(jié)果：若L為空表，則返回True捞慌，否則返回False
        ListLength( L )
            初始條件：線性表L已存在
            操作結(jié)果：返回線性表L中元素個(gè)數(shù)
        GetElem( L, i, &e )
            初始條件：線性表L已存在
            操作結(jié)果：用e返回L中第i個(gè)元素
        LocateElem( L, e, compare() )
            初始條件：線性表L已存在耀鸦，compare()是數(shù)據(jù)元素判定函數(shù)
            操作結(jié)果：返回L中第一個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。若不存在則返回0
        PriorElem( L, cur_e, &pre_e )
            初始條件：線性表L已存在
            操作結(jié)果：若cur_e是L的數(shù)據(jù)元素且不是第一個(gè)啸澡，則用pre_e返回其前驅(qū)袖订；否則操作失敗，pre_e無(wú)定義
        NextElem( L, cur_e, &next_e )
            初始條件：線性表L已存在
            操作結(jié)果：若cur_e是L的數(shù)據(jù)元素且不是最后一個(gè)嗅虏，則用next_e返回其后繼洛姑；否則操作失敗，pre_e無(wú)定義
        ListInsert(& L, i ,e )
            初始條件：線性表L已存在, 1<= i <= ListLength(L)+1
            操作結(jié)果：在L的第i個(gè)位置之前插入e皮服，L的長(zhǎng)度自增一
        ListDelete(& L , i , &e)
            初始條件：線性表L已存在且非空楞艾，1<= i <= ListLength(L)
            操作結(jié)果：刪除L中第i個(gè)元素，并用e返回其值龄广，L長(zhǎng)度減一
        ListTraverse( L, visit() )
            初始條件：線性表L已存在
            操作結(jié)果：對(duì)L中每個(gè)數(shù)據(jù)元素調(diào)用visit(), 一旦visit()失敗硫眯，則操作失敗
}ADT List
/*
對(duì)抽象類型線性表，還可以進(jìn)行一些更為復(fù)雜的操作择同。如两入，合并或拆分表等
*/

算法 2.1——?dú)w并線性表

• 歸并
  用LA和LB表示A和B兩個(gè)集合，現(xiàn)要求一個(gè)新的集合A = A∪B敲才。即擴(kuò)大LA裹纳，將存在于LB而不存在于LA的元素插入到LA中
• 算法實(shí)現(xiàn)

void union(List &La, List Lb){
    La_len = ListLength(La);Lb_len = ListLength(Lb);
    for (i=1; i<=Lb_len; ++i){
        GetElem(Lb, i, e);  //遍歷Lb中元素
        if( !ListLocate(La, e, equal) ){  //判斷e是否在La中
            ListInsert(La, ++La_len, e );  //將e插入至La末尾
        }
    }
}

算法2.2——?dú)w并排序

• 歸并排序
  線性表La和Lb中元素按值非遞減有序排列，要求將La和Lb合并紧武，并保證值非遞減剃氧。
  如La = （1，2阻星，3她我，3，5）；Lb = （2番舆，2，4矾踱，8）
  歸并為：Lc = （1恨狈，2，2呛讲，2禾怠，3，3贝搁，4吗氏，5，8）

相對(duì)于一個(gè)排序一個(gè)長(zhǎng)表雷逆，將兩個(gè)短表排序后歸并的效率要更高一些

• 問(wèn)題解析
  將Lc設(shè)置為空表弦讽，然后將La和Lb中元素逐個(gè)插入Lc即可。插入元素滿足c = a≤ b?a:b膀哲，其中a往产，b分別屬于La和Lb

• 算法實(shí)現(xiàn)

void MergeList(List La, List Lb, List &Lc){
    InitList(Lc);
    i = j = 1; k = 0;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=La_len)&&(j<=Lb_len)){  //當(dāng)La和Lb均非空時(shí)
        GetElem(La, i, ai);
        GetElem(Lb, j, bj);
        if(ai <= bj){
            ListInsert(Lc, ++k, ai);
            ++i;
        }
        else{
            ListInsert(Lc, ++k, bj);
            ++j;
        }
    }
    while(i <= La_len){  //La非空時(shí)
        GetElem(La, i++, e);
        ListInsert(Lc, ++k, e);
    }
    while(j <= Lb_len){
        GetElem(Lb, j++, e);
        ListInsert(Lc, ++k, e);
    }
}

上述兩個(gè)算法的時(shí)間復(fù)雜度取決于抽象數(shù)據(jù)類型List定義中基本操作的執(zhí)行時(shí)間。如GetElem（定位）和ListInsert與表長(zhǎng)無(wú)關(guān)某宪，因此時(shí)間復(fù)雜度為O(1)仿村，LocateElem（逐個(gè)元素操作）與表長(zhǎng)有關(guān)，則算法2.1時(shí)間復(fù)雜度為O(ListLength(La) * ListLength(Lb))兴喂，2.2為O(ListLength(La) + ListLength(Lb))蔼囊。

線性表的順序表示和實(shí)現(xiàn)

線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。他的特點(diǎn)是衣迷，為表中相鄰的元素a1和a2賦以相鄰的存儲(chǔ)位置LOC(a1)和LOC(a2)畏鼓。換句話說(shuō)，以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系蘑险。
假設(shè)每個(gè)元素需占用m個(gè)存儲(chǔ)單元滴肿，并以所占的第一個(gè)單元的存儲(chǔ)地址作為元素的存儲(chǔ)位置。則線性表的第i個(gè)元素ai的存儲(chǔ)位置滿足LOC(ai) = LOC(a1) + (i-1)*m佃迄。式中LOC(a1)稱作線性表的起始位置或基地址泼差。
順序表只要確定了存儲(chǔ)的起始位置，就可以隨機(jī)存取線性表中任一數(shù)據(jù)元素呵俏，因此順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)堆缘。

• C語(yǔ)言中常用一維動(dòng)態(tài)數(shù)組描述數(shù)據(jù)結(jié)構(gòu)中的順序存儲(chǔ)結(jié)構(gòu)。描述如下

//---線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)---
#define LIST_INIT_SIZE    100  //線性表存儲(chǔ)空間初始分配量
#define LISTINCREMENT    10  //線性表存儲(chǔ)空間分配增量
typedef struct{
    ElemType    *elem;  //存儲(chǔ)空間基地址普碎，等價(jià)于數(shù)組名
    int         length;  //當(dāng)前長(zhǎng)度
    int         listsize;  //當(dāng)前分配的存儲(chǔ)容量
}SqList;

• typedef是自定義數(shù)據(jù)類型 Sqlist是自定義數(shù)據(jù)類型名

順序表的初始化操作就是

1. 為順序表分配一個(gè)預(yù)定義大小(LIST_INIT_SIZE)的數(shù)組空間
2. 將線性表當(dāng)前長(zhǎng)度設(shè)為“0”（具體參見(jiàn)算法2.3）
3. 一旦因插入元素導(dǎo)致空間不足（大于listsize）時(shí)吼肥，可進(jìn)行再分配，即為順序表增加一個(gè)大小為存儲(chǔ)LISTINCREMENT個(gè)數(shù)據(jù)元素的空間

• 上述代碼等價(jià)于

struct List{
    ElemType* elem;
    int length;
    int listsize;
}
#typedef List SqList;

算法 2.3——初始化線性表

• 算法實(shí)現(xiàn)

Status InitList_Sq(SqList &L){ //SqList是自定義的數(shù)據(jù)類型
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));// malloc分配一個(gè)滿足他的存儲(chǔ)空間，并返回指向它的指針
    if(! L.elem)  {exit(OVERFLOW);}  //存儲(chǔ)分配失敗缀皱，溢出
    L.length = 0;  //空表長(zhǎng)度為0
    L.listsize = LIST_INIT_SIZE;  //初始存儲(chǔ)容量
    return OK;
}

順序存儲(chǔ)結(jié)構(gòu)下線性表元素的插入與刪除

由于邏輯上相鄰的數(shù)據(jù)元素在物理位置上也是相鄰的斗这，因此必須移動(dòng)元素才能反應(yīng)這個(gè)邏輯關(guān)系的變化。

算法 2.4——插入

• 插入：在第i（1≤ i≤ n）個(gè)元素之前插入一個(gè)元素時(shí)啤斗，需將第n至第i（共n-i+1）個(gè)元素向后移動(dòng)一個(gè)位置
• 算法實(shí)現(xiàn)

Status ListInsert_Sq (SqList& L, int i, ElemType e){
    //在順序表L第i個(gè)位置之前插入新元素e
    //i的合法值為 1≤ i≤ ListLength_Sq(L)+1
    if (i<1 || i>= L.length + 1)  
        return ERROR;
    if (L.length > L.listsize){    // 當(dāng)前長(zhǎng)度大于當(dāng)前分配的存儲(chǔ)容量表箭，即當(dāng)前存儲(chǔ)空間已滿 增加分配
        newbase = (ElemType* )realloc(L.elem, (L.listsize+LISTCREMENT)*sizeof(ElemType));
        if(!newbase)  
            exit(OVERFLOW);  //若重新分配失敗，證明溢出
        L.elem = newbase;  //新基地址钮莲，相當(dāng)于數(shù)組名
        L.listsize += LISTINCREMENT;  //增加存儲(chǔ)容量
    }
    q = &(L.elem[i-1])  //q是插入位置免钻，elem等價(jià)于數(shù)組名
    for (p = &(L.elem[L.length-1]); p>= q; --p){  //從末尾開(kāi)始，將q及以后的所有元素向右移動(dòng)
        *(p+1) = *p;
    }
    *q = e;  //插入e
    ++L.length;  //表長(zhǎng)增一
    return OK;
}// ListInsert_Sq

算法 2.5——?jiǎng)h除

• 刪除：刪除第i（1≤ i≤ n）個(gè)元素時(shí)崔拥，需將第i至第n（共n-i）個(gè)元素向前移動(dòng)一個(gè)位置
• 算法實(shí)現(xiàn)

Status ListDelete_Sq(SqList& L, int i, ElemType &e){  //用e返回被刪除的元素
    //i的合法值為1<= i <= L.length极舔，與插入操作不同
    if(i<1 || i>L.length)
        return ERROR;
    p = &(L.elem[i-1]);
    e = *p;
    q = &(L.elem[L.length-1]);  //等價(jià)于 q = L.elem+L.length-1
    for(p ; p<= q; p++ ){
        *(p-1) = *p;
    }
    --L.length;
} //ListDelete_Sq

插入與刪除算法時(shí)間主要耗費(fèi)在移動(dòng)元素上，故移動(dòng)元素的操作為基本操作链瓦，而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除的位置拆魏。

插入和刪除元素的時(shí)間復(fù)雜度

• 插入元素時(shí)間復(fù)雜度：假設(shè)Pi是在第i個(gè)元素元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的期望值（平均次數(shù)）為：
  
  （1）

• 刪除元素時(shí)間復(fù)雜度：假設(shè)Qi是刪除第i個(gè)元素的概率澡绩，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的期望值（平均次數(shù)）為：

  
  
  （2）
  
  

  不失一般性稽揭，可以假定在線性表的任何位置上插入或刪除元素都是等概率的，即

  
  
  
  則式(1)和式(2)可分別簡(jiǎn)化為
  
  （3）
  
  
  （4）

由此可見(jiàn)肥卡，平均需要移動(dòng)約一半的元素溪掀。若表長(zhǎng)為n，算法ListInsert_Sq和ListDelete_Sq的時(shí)間復(fù)雜度為O(n)步鉴。

算法 2.6——順序表的union

• 歸并（順序表）：基本操作是“進(jìn)行兩個(gè)元素的比較”揪胃，若L中存在與e相同的元素ai，則比較次數(shù)為1<= i <= L.length氛琢，否則為表長(zhǎng)喊递，即算法LocateElem_Sq的時(shí)間復(fù)雜度為O(L.length)，所以對(duì)于La和Lb而言阳似，其時(shí)間復(fù)雜度為O(La.length*Lb.length)
• 算法實(shí)現(xiàn)

int LocateElem_Sq(SqList L, ElemType e, Status ( *compare)(ElemType, ElemType)){
    //在順序線性表L中查找第1個(gè)與e滿足compare()的位序
    //若找到則返回位序骚勘，否則返回0
    i = 1;
    np = L.elem;    //數(shù)組名，第一個(gè)元素存儲(chǔ)位置
    while (i <=  L.length && !( *compare) ( *p++, e)){  //判斷是否存在滿足compare函數(shù)的元素
        i++;
    }
    if( i <= L.length){
        return i;
    }
    return 0;
}

算法 2.7——順序表的歸并

• 歸并排序（順序表） 顯然順序表歸并的基本操作是“元素賦值”撮奏，算法時(shí)間復(fù)雜度為O(La.length + Lb.length)俏讹。已知La和Lb中元素單調(diào)非減排列，現(xiàn)要求構(gòu)造Lc歸并排列畜吊。
• 算法實(shí)現(xiàn)

void MergeList_Sq( SqList La, SqList Lb, SqList& Lc){
    //用Lc返回新的列表
    pa = La.elem;  pb = Lb.elem;
    //需要為L(zhǎng)c的三個(gè)屬性都賦值 
    Lc.listsize = Lc.length = La.length + Lb.length;  //偽代碼連續(xù)賦值
    pc = Lc.elem =  (ElemType* )malloc(sizeof(ElemType )* Lc.listsize);
    if(! pc)
        exit(OVERFLOW);
    pa_last = La.elem + La.length -1;    //取末尾位置
    pb_last = Lb.elem + Lb.length -1;
    while( pa <= pa_last && pb <= pb_last ){
        if(*pa >= *pb)
            *pc++ = *pb++;
        else
            *pc++ = *pa++;
    }
    while (pa <= La.length){
        *pc++ = *pa++;
    }
    while (pb <= Lb.length){
        *pc++ = *pb++;
    }
}  //MergeList_Sq

順序表的優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)
  1. 節(jié)省存儲(chǔ)空間
  2. 對(duì)第i個(gè)節(jié)點(diǎn)操作易于實(shí)現(xiàn)
  3. 容易查找一個(gè)節(jié)點(diǎn)的前驅(qū)和后繼
• 缺點(diǎn)
  1. 插入和刪除操作困難

線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

不要求邏輯上相鄰的元素在物理位置上也相鄰
一個(gè)線性表由若干個(gè)結(jié)點(diǎn)組成泽疆，每個(gè)結(jié)點(diǎn)至少含有兩個(gè)域：數(shù)據(jù)域（信息域）和指針域（鏈域），這樣的結(jié)點(diǎn)形成存儲(chǔ)的線性表稱作鏈表
在使用鏈表時(shí)玲献，關(guān)心的只有它所表示的線性表中數(shù)據(jù)元素之間的邏輯順序殉疼，而不是在存儲(chǔ)器中的實(shí)際位置梯浪。

線性鏈表（單鏈表）

• 邏輯關(guān)系
  數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的。指針為數(shù)據(jù)元素之間的邏輯關(guān)系的映像瓢娜，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素其存儲(chǔ)的物理位置不要求緊鄰挂洛。
• 頭結(jié)點(diǎn)
  本身不存放數(shù)據(jù)，指針域指向第一個(gè)元素的地址恋腕。使對(duì)第一個(gè)元素的操作與對(duì)其他元素的操作保持一致抹锄。用頭指針指向頭結(jié)點(diǎn)。

• 結(jié)構(gòu)示意圖

  
  

結(jié)構(gòu)指針

typedef struct Lnode{
    //單鏈表存儲(chǔ)結(jié)構(gòu)
    ElemType data;  //數(shù)據(jù)域
    struct Lnode *next; //單鏈表指針域
}LNode, *LinkList;  // 此行直接定義了 鏈LNode 和 頭指針LinkList 類型名

LinkList L; //LinkList是指針類型的struct Lnode,L為單鏈表的頭指針

鏈表的嵌套定義：嵌套定義的前提是已知所需分配的空間荠藤。鏈表可嵌套定義是因?yàn)?strong>所有指針變量所需空間大小是確定的，不受指針基類型的影響获高。

算法 2.8——GetElem在單鏈表中的實(shí)現(xiàn)

• 在單鏈表中取元素：在單鏈表中哈肖，取得第i個(gè)元素的信息，必須從頭指針出發(fā)尋找念秧。
• 算法實(shí)現(xiàn)

Status GetElem_L(LinkList L, int i, ElemType& e){  
    //假設(shè)L是帶頭結(jié)點(diǎn)鏈表的頭指針淤井， 用e返回獲得的結(jié)果
    p = L->next; j =1;  //初始化指針，使p指向第一個(gè)結(jié)點(diǎn)摊趾；用j作為計(jì)數(shù)器
    while(p && j<i){
        p = p->next;
        ++j;
    }
    if( !p||j>i)
        return ERROR;
    e = p -> data;
    return OK:
}

GetElem時(shí)間復(fù)雜度

while循環(huán)體中的語(yǔ)句頻度和被查元素在表中位置有關(guān)币狠，若1< i≤ n則頻度為 i-1，否則為n砾层。因此時(shí)間復(fù)雜度為線性O(shè)(n)漩绵。

算法 2.9——單鏈表插入新結(jié)點(diǎn)

• 插入： 為在a和b元素中插入新元素x，根據(jù)插入操作的邏輯定義肛炮，首先要修改結(jié)點(diǎn)a中的指針域止吐，令其指向結(jié)點(diǎn)x，而結(jié)點(diǎn)x的指針域指向結(jié)點(diǎn)b侨糟。假設(shè)s為指向結(jié)點(diǎn)x的指針碍扔，則上述操作的語(yǔ)句描述為： s->next = p->next; p->next = s

• 插入元素原理圖

  
  
• 算法實(shí)現(xiàn)

Status ListInsert_L (LinkList& L, int i, ElemType e){
    //在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置前插入元素e
    p = L; j = 0;  //初始化p為頭指針
    while( p && j < i-1){  //尋找 i-1結(jié)點(diǎn)
        p = p->next;  
        ++j;
    }
    if(!p || j>i-1){
        return ERROR;
    }
    s = (ElemType* ) malloc( sizeof( ElemType));
    s -> data = e;  s -> next = p -> next;
    p -> next = s;
    return OK;
}

算法 2.10——單鏈表刪除結(jié)點(diǎn)

• 刪除元素原理圖

• 算法實(shí)現(xiàn)

Status ListDelete_L(LinkList& l, int i, ElemType& e){
    //刪除單鏈表L第i個(gè)元素并用e返回值
    p = L; j = 0;
    while(p ->next && j<i-1 ){  //尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)
        p = p->next;
        ++j;
    }
    if ( !( p->next) || j>i-1)  //插入位置不合法
        return ERROR;
    q = p->next; p->next = q->next;  //刪除結(jié)點(diǎn)
    e = q->data;
    free(q);  //釋放被刪除的結(jié)點(diǎn)
    return OK;
}

二者的時(shí)間復(fù)雜的都是O(n)

malloc函數(shù)

假設(shè)p是LinkList類型變量秕重，則執(zhí)行p = (LinkList) malloc (sizeof ( LNode))語(yǔ)句的含義是不同，生成一個(gè)LNode型的結(jié)點(diǎn)，并將其起始位置賦給p溶耘。反之free( p)是回收一個(gè)LNode型結(jié)點(diǎn)二拐，回收后的空間可以備作再次生成節(jié)點(diǎn)的空間。

算法 2.11——逆向建立單鏈表

• 逆向建立單鏈表：從表尾到表頭汰具，時(shí)間復(fù)雜度為O（n）
• 算法實(shí)現(xiàn)

void CreateList_L( LinkList& L, int n){
    //逆序輸入n個(gè)元素的值卓鹿，建立帶表頭節(jié)點(diǎn)的單鏈表L
    L = (LinkList )malloc( sizeof( LNode));  
    L -> next = NULL;  //建立一個(gè)帶有頭結(jié)點(diǎn)的空表
    for ( i=n; i>0; --i){
        p = (LinkList) malloc (sizeof ( LNode));  
        scanf(& p->data);        
        p->next = L->next;
        L->next = p;  //逆序插入結(jié)點(diǎn)
    }
}

算法 2.12——合成有序鏈表

• 合成：鏈表的歸并排列。
• 算法實(shí)現(xiàn)

void MergeList_L(LinkList La, LinkList Lb, LinkList &Lc){
    // 已知La和Lb為 內(nèi)容元素非減的 單鏈表
    pa = La->next; pb = Lb->next; //使pa和pb指向第一個(gè)元素
    pc = Lc = La; //用La的頭節(jié)點(diǎn)作為L(zhǎng)c的頭節(jié)點(diǎn)
    while (pa && pb){
        if(pa->data <= pb->data){
            pc->next = pa;  //將pa插入到pc后
            pc = pa;  //平移pc指針留荔，應(yīng)該等價(jià)于pc = pc->next;
            pa = pa->next;  //平移pa指針
        }
        else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
    }
    pc -> next = pa? pa:pb;
    free(Lb); //不可釋放La吟孙，因?yàn)榇藭r(shí)La和Lc共用一個(gè)地址澜倦。
} //MergeLsit_L

有時(shí)可以借用一維數(shù)組來(lái)描述線性鏈表，結(jié)構(gòu)如下

//------線性表的靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu)------
#define MAXSIZE 100
typedef struct{
    ElemType elem;
    int  cur;
} component, SLinkList[MAXSIZE];

此種類型在不設(shè)“指針”的情況下使用鏈表結(jié)構(gòu)杰妓。
上述結(jié)構(gòu)中藻治，數(shù)組的一個(gè)分量代表一個(gè)節(jié)點(diǎn)，同時(shí)用游標(biāo)cur代替指針指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置巷挥。數(shù)組的第零分量可以看成是頭節(jié)點(diǎn)桩卵，其指針域指示鏈表的第一個(gè)結(jié)點(diǎn)。這種存儲(chǔ)結(jié)構(gòu)仍需預(yù)先分配出一個(gè)較大的空間倍宾，但在插入和刪除元素時(shí)不需要修改移動(dòng)元素雏节，只需要修改指針，仍具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)高职。我們稱這種存儲(chǔ)方式為靜態(tài)鏈表钩乍。
下圖展示了 在SUN后插入GUO并刪除ZHOU的操作。

假設(shè)S為SLinkList型變量怔锌，則S[0].cur指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置寥粹。設(shè) i = S[0].cur; 則S[i].cur表示第二個(gè)結(jié)點(diǎn)在數(shù)組中的位置。i = S[i].cur實(shí)為指針的后移(等價(jià)于 p = p -> next)

算法 2.13——靜態(tài)鏈表定位函數(shù)

• 定位：查找第一個(gè)值為e的元素埃元。若找到則返回位序涝涤，否則返回0
• 算法實(shí)現(xiàn)

int LocateElem_SL(SLinkList L, ElemType e){
    i = S[0].cur; 
    while (i && S[i].data !=e){
        i = S[i].cur;  //遍歷，之道數(shù)據(jù)域等于e
    }
    return i;
}  // LocateElem_SL

類似的岛杀，靜態(tài)鏈表可以實(shí)現(xiàn)插入和刪除操作阔拳。所不同的是，malloc和free兩個(gè)函數(shù)需要自己編寫(xiě)楞件。為了分辨哪些分量未被使用衫生，可以將所有未被使用過(guò)的以及被刪除的分量用游標(biāo)構(gòu)成一個(gè)備用的鏈表，每當(dāng)進(jìn)行插入操作時(shí)從備用鏈表上取得第一個(gè)結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)土浸；反之將刪除下來(lái)的新結(jié)點(diǎn)插入到備用鏈表后罪针。

算法 2.14——靜態(tài)鏈表的初始化

• 算法實(shí)現(xiàn)

void InitSpace_SL(SLinkList &space){
    // space[0].cur作為頭指針
    for ( i=0; i<MAXSIZE-1; ++i){
        space[i].cur = i+1;
    }
    space[MAXSIZE-1].cur=0;
}

算法 2.15——靜態(tài)鏈表分配空間

• 分配：在插入新結(jié)點(diǎn)，給新結(jié)點(diǎn)分配空間實(shí)際上就是為結(jié)點(diǎn)從備用鏈表中分配一個(gè)結(jié)點(diǎn)下標(biāo)
• 算法實(shí)現(xiàn)

int Malloc_SL(SLinkList &space){
    // 若備用鏈表非空則返回分配的結(jié)點(diǎn)下標(biāo)黄伊，否則返回0
    i = space[0].cur;
    if(space[0].cur){  // 如果備用鏈表非空
        space[0].cur = space[i].cur;  // 連接備用鏈表頭結(jié)點(diǎn)和第二個(gè)結(jié)點(diǎn)
    }
    return i;
} // Malloc_SL

算法 2.16——靜態(tài)鏈表回收結(jié)點(diǎn)

• 將結(jié)點(diǎn)回收泪酱，即將該結(jié)點(diǎn)放回備用鏈表中
• 算法實(shí)現(xiàn)

void Free_SL(SLinkList &space, int k){
    // 將下標(biāo)為k的空閑結(jié)點(diǎn)回收到備用鏈表
    space[k].cur = space[0].cur;
    space[0].cur = k;
}   

算法 2.17——集合運(yùn)算（A/B）∪（B/A）

• 對(duì)稱差：假設(shè)由終端輸入集合元素，先建立表示集合A的靜態(tài)鏈表S还最，而后在輸入集合B的元素的同時(shí)查找S表墓阀，若存在和B相同的元素，則從S表中刪除拓轻，否則插入S表
• 算法實(shí)現(xiàn)

void difference_SL(SLinkList &space, int &S){
    // 依次輸入A和B的元素斯撮，在一堆數(shù)組space中建立表示（A/B）∪（B/A）
    // 的靜態(tài)鏈表，S為其頭指針扶叉。假設(shè)備用空間足夠大勿锅，space[0].cur為其頭指針帕膜。
    InitSpace_SL(space);
    S = Malloc_SL(space); // 生成S的頭結(jié)點(diǎn)
    r = S; // r指向S的末尾
    scanf(m,n); // 輸入A和B的元素個(gè)數(shù)
    for(j = 1; j <= m; ++j){
        i = Malloc_SL(space); // 分配結(jié)點(diǎn)
        scanf(space[i].data);
        space[r].cur = i; r = i; // 插入到表尾
    }  //for 
    space[r].cur = 0; //偽結(jié)點(diǎn)的指針為空
    for(j = 1; j <= n; ++j){
        scanf(b); p = S;
        k = space[S].cur; // k指向A中的第一個(gè)結(jié)點(diǎn)
        while(k != space[r].cur && space[k].data != b){
            p = k; k = space[k].cur; 
        }  //while
        if( k == space[r].cur){ // 當(dāng)前表中不存在該元素，插入在r所指結(jié)點(diǎn)之后溢十，且r的位置不變
            i = Malloc_SL(space);
            space[i].data = b;
            space[i].cur = space[r].cur;
            space[r].cur = i;
        } //if
        else{
             space[p].cur = space[k].cur;
             Free_SL(space,k);
             if (r == k)  //若刪除的是r所指結(jié)點(diǎn)垮刹，則需修改尾指針 
                 r = p;
        }  //else
    }  //for
}  //difference