線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的操作主要分為查找、插入、刪除三種，每種操作都對(duì)應(yīng)不同的算法。

線性表分為順序表和鏈表，而鏈表又分為單鏈表和雙鏈表。下面我們來(lái)看這三種線性表的查找、插入和刪除的相關(guān)操作。

一、順序表操作：

1.按元素值的查找算法，

int findElem (Sqlist L,int e)

{

    int i;

    for (i=0,i<L.length,++i)   //遍歷L長(zhǎng)度中的每個(gè)位置

        if(e == L.data[i])          //獲取每個(gè)位置對(duì)應(yīng)的值和e值進(jìn)行判斷，這里的等于可以是大于、小于

            return i;                    //如果找到與e值相等的值，則返回該值對(duì)應(yīng)的位置

    return -1;                        //如果找不到，則返回-1

}

2.插入數(shù)據(jù)元素算法

在順序表L的第p個(gè)（0<p<length）個(gè)位置上插入新的元素e，如果p的輸入不正確，則返回0，代表插入失敗；如果p的輸入正確，則將順序表第p個(gè)元素及以后元素右移一個(gè)位置，騰出一個(gè)空位置插入新元素，順序表長(zhǎng)度增加1，插入操作成功，返回1。

int insertElem(Sqlist &L,int p,int e) //L是順序表的長(zhǎng)度，要發(fā)生變化，所以用引用型

{

    int i

    if (p<0 || p>L.length || L.length==maxsize) //如果插入e的位置p小于0，或者是大于L的長(zhǎng)度，或者是L的長(zhǎng)度已經(jīng)等于了順序表最大存儲(chǔ)空間

        return 0;

    for (i=L.length-1;i>=p;--i)    //從L中的最后一個(gè)元素開(kāi)始遍歷L中位置大于p的每個(gè)位置

        L.data[i+1]=L.data[i];    //依次將第i個(gè)位置的值賦值給i+1

    L.data[p]=e;                  //將p位置插入e

    ++(L.length);                 //L的長(zhǎng)度加1

    return 1;                     //插入成功，返回1

}

3.刪除數(shù)據(jù)元素算法

將順序表的第p個(gè)位置的元素e進(jìn)行刪除，如果p的輸入不正確，則返回0，代表刪除失敗；如果p的輸入正確，則將順序表中位置p后面的元素依次往前傳遞，把位置p的元素覆蓋掉即可。

int deleteElem (Sqlist &L,int p,int &e)    //需要改變的變量用引用型

{

    int i;

    if(p<0 || p>L.length-1)    //對(duì)位置p進(jìn)行判斷，如果位置不對(duì)，則返回0，表示刪除失敗

        return 0;

    e=L.data[p];               //將要?jiǎng)h除的值賦值給e

    for(i=p;i<L.length-1;++i)  //從位置p開(kāi)始，將其后邊的元素逐個(gè)向前覆蓋

        L.data[i]=L.data[i+1]; 

    --(L.length)               //將表的長(zhǎng)度減1

    return 1;                  //刪除成功，返回1

}

二、單鏈表操作

1.單鏈表的歸并操作

A和B是兩個(gè)單鏈表，其中元素遞增有序，設(shè)計(jì)一個(gè)算法，將A和B歸并成一個(gè)按元素值非遞減有序的鏈表C，C由A、B組成。

分析：已知A、B中的元素遞增有序，要使歸并后的C中的元素依然有序，可以從A、B中挑出最小的元素插入C的尾部，這樣當(dāng)A、B中所有元素都插入C中時(shí)，C一定是遞增有序的。

void merge(LNode *A,LNode *B,LNode *&C)

    {

        LNode *p = A->next;                 //用指針p來(lái)追蹤鏈表A的后繼指針

        LNode *p = B->next;                 //用指針p來(lái)追蹤鏈表B的后繼指針

        Lnode *r;                           //r始終指向C的終端結(jié)點(diǎn)

        C = A;                              //用A的頭結(jié)點(diǎn)來(lái)做C的頭結(jié)點(diǎn)

        C-> = NULL;                         //

        free(B);

        r = C;

        while(p!=NULL&&q!=NULL)             //當(dāng)p和q都不為空時(shí)，選取p與q中所指結(jié)點(diǎn)中較小的值插入C的尾部

        {

            if(p->data<=q->data)            //如果p結(jié)點(diǎn)的值小于等于q結(jié)點(diǎn)的值，則將p的結(jié)點(diǎn)指向r,即C，p的下一個(gè)結(jié)點(diǎn)繼續(xù)指向p

            {

                r->next = p;p = p->next;

                r=r->next;

            }

            else

            {

                r->next=q;q=q-next;

                r=r->next;

            }

        }

        r->next = NULL;

        if(p!=NULL)r->next=p;

        if(q!=NULL)r->next=q;  

}

2.單鏈表的尾插法

已知有n個(gè)元素存儲(chǔ)在數(shù)組a中，用尾插法（即從尾部插入）建立鏈表C

void createlistR(LNode *&C,int a[],int n)        //需要不斷變化的值用引用型

{

    LNode *s,*r;                                 //s用來(lái)指向新申請(qǐng)的結(jié)點(diǎn)，r始終指向C的終端結(jié)點(diǎn)

    int i;

    C = (LNode * )malloc(sizeof(LNode));         //申請(qǐng)一個(gè)頭結(jié)點(diǎn)空間

    C -> next = NULL                             //初始化一個(gè)空鏈表

    r = C;                                       //r為指針，指向頭結(jié)點(diǎn)C，此時(shí)的頭結(jié)點(diǎn)也是終端結(jié)點(diǎn)

    for(i=0;i<n;++i):

    {

        s = (LNode*)malloc(sizeof(LNode));       //新申請(qǐng)一個(gè)結(jié)點(diǎn)，指針s指向這個(gè)結(jié)點(diǎn)

        s -> data = a[i]                         //將數(shù)組元素a[i]賦值給指針s指向結(jié)點(diǎn)的值域

                                                 //此時(shí)，結(jié)點(diǎn)值域和指針都有了，一個(gè)完整的結(jié)點(diǎn)就建好了，要想把這個(gè)結(jié)點(diǎn)插進(jìn)鏈表C中

                                                 //只需要將頭結(jié)點(diǎn)指針指向這個(gè)結(jié)點(diǎn)就行

        r -> next = s;                           //頭結(jié)點(diǎn)指針指向結(jié)點(diǎn)s

        r = r -> next;                           //更新r指針目前的指向

    }

    r -> next = NULL;                            //直到終端結(jié)點(diǎn)為NULL，表示插入成功

}

3.單鏈表的頭插法

頭插法和尾插法是相對(duì)應(yīng)的一種方法，頭插法是從鏈表的頭部開(kāi)始插入，保持終端結(jié)點(diǎn)不變；尾插法是從鏈表的尾部開(kāi)始插入，保持頭結(jié)點(diǎn)不變。

void createlistF(LNode *&C,int a[],int n)        //需要不斷變化的值用引用型

{

    LNode *s;                                 

    int i;

    C = (LNode * )malloc(sizeof(LNode));         //申請(qǐng)C的結(jié)點(diǎn)空間

    C -> next = NULL                             //該節(jié)點(diǎn)指向?yàn)榭?/p>

    for(i=0;i<n;++i):

    {

        s = (LNode*)malloc(sizeof(LNode));       //新申請(qǐng)一個(gè)結(jié)點(diǎn)，指針s指向這個(gè)結(jié)點(diǎn)

        s -> data = a[i]                         //將數(shù)組元素a[i]賦值給指針s指向結(jié)點(diǎn)的值域

                                                 //此時(shí)，結(jié)點(diǎn)值域和指針都有了，一個(gè)完整的結(jié)點(diǎn)就建好了，要想把這個(gè)結(jié)點(diǎn)插進(jìn)鏈表C中

                                                 //只需要讓這個(gè)結(jié)點(diǎn)的指針指向鏈表C的開(kāi)始結(jié)點(diǎn)即可

        s -> next = C -> next;                           //結(jié)點(diǎn)s指向C指針的開(kāi)始結(jié)點(diǎn)

        C -> next = s;                           //更新r指針目前的指向

    }

}

三、雙鏈表操作

1.采用尾插法建立雙鏈表

void createFlistR(DLNode *&L,int a[],int n)

{

    DLNode *s,*r;

    int i;

    L = (DLNode*)malloc(sizeof(DLNode)); //新建一個(gè)結(jié)點(diǎn)L

    L -> prior = NULL;

    L -> next = NULL;

    r = L;                               //r指針指向結(jié)點(diǎn)L的終端結(jié)點(diǎn)，開(kāi)始頭結(jié)點(diǎn)也是尾結(jié)點(diǎn)

    for(i=0;i<n;++i)

    {        s = (DLNode*)malloc(sizeof(DLNode));  //創(chuàng)建一個(gè)新節(jié)點(diǎn)s

        s -> data = a[i]                      //結(jié)點(diǎn)s的值域?yàn)閍[i]

        r -> next = s;                        //r指針的后繼指針指向s結(jié)點(diǎn)

        s ->prior = r;                        //s的前結(jié)點(diǎn)指向r

        r = s;                                //更新指針r的指向

    }    

    r -> next = NULL;                         //直到r指針指向?yàn)镹ULL

}

2.查找結(jié)點(diǎn)的算法

在雙鏈表中查找值為x的結(jié)點(diǎn)，如果找到，則返回該結(jié)點(diǎn)的指針，否則返回NULL值。

DLNode* findNode(DLNode *C,int x)

{

    DLNode *p = C -> next;

    while(p != NULL)

    {

        if(p -> data == x)

            break;

        p = p -> next;

    }

    return p;

}

3.插入結(jié)點(diǎn)的算法

在雙鏈表中p所指的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)s,核心思想就是將p的指向賦值給s,即讓s指向p所指,s的前結(jié)點(diǎn)就是p,p的后結(jié)點(diǎn)就是s,具體代碼如下：

s -> next = p -> next;

s -> prior = p;

p -> next = s;

s -> next -> prior = s;

4.刪除結(jié)點(diǎn)的算法

要?jiǎng)h除雙鏈表中p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，核心思想就是先將p的后繼結(jié)點(diǎn)給到q,然后讓p指向q的后繼結(jié)點(diǎn)，q的后繼結(jié)點(diǎn)的前結(jié)點(diǎn)就是p，然后把q釋放掉，具體代碼如下：

q = p -> next;

p -> = q -> next;

q -> next -> prior = p;

free(q);

盡管我們知道這些線性表的操作的實(shí)現(xiàn)是基于算法的，但是每種操作的算法都是不盡相同的，需要我們花時(shí)間去慢慢理解。在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中對(duì)線性表基本操作的算法實(shí)現(xiàn)有詳細(xì)的解讀，想提升自己的算法知識(shí)的小伙伴可以去觀看學(xué)習(xí)。