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

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

一、順序表操作：

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

int findElem (Sqlist L,int e)

{

    int i;

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

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

            return i;                    //如果找到與e值相等的值，則返回該值對應的位置

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

}

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

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

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

{

    int i

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

        return 0;

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

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

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

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

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

}

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

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

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

{

    int i;

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

        return 0;

    e=L.data[p];               //將要刪除的值賦值給e

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

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

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

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

}

二、單鏈表操作

1.單鏈表的歸并操作

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

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

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

    {

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

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

        Lnode *r;                           //r始終指向C的終端結點

        C = A;                              //用A的頭結點來做C的頭結點

        C-> = NULL;                         //

        free(B);

        r = C;

        while(p!=NULL&&q!=NULL)             //當p和q都不為空時，選取p與q中所指結點中較小的值插入C的尾部

        {

            if(p->data<=q->data)            //如果p結點的值小于等于q結點的值，則將p的結點指向r,即C，p的下一個結點繼續(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個元素存儲在數(shù)組a中，用尾插法（即從尾部插入）建立鏈表C

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

{

    LNode *s,*r;                                 //s用來指向新申請的結點，r始終指向C的終端結點

    int i;

    C = (LNode * )malloc(sizeof(LNode));         //申請一個頭結點空間

    C -> next = NULL                             //初始化一個空鏈表

    r = C;                                       //r為指針，指向頭結點C，此時的頭結點也是終端結點

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

    {

        s = (LNode*)malloc(sizeof(LNode));       //新申請一個結點，指針s指向這個結點

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

                                                 //此時，結點值域和指針都有了，一個完整的結點就建好了，要想把這個結點插進鏈表C中

                                                 //只需要將頭結點指針指向這個結點就行

        r -> next = s;                           //頭結點指針指向結點s

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

    }

    r -> next = NULL;                            //直到終端結點為NULL，表示插入成功

}

3.單鏈表的頭插法

頭插法和尾插法是相對應的一種方法，頭插法是從鏈表的頭部開始插入，保持終端結點不變；尾插法是從鏈表的尾部開始插入，保持頭結點不變。

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

{

    LNode *s;                                 

    int i;

    C = (LNode * )malloc(sizeof(LNode));         //申請C的結點空間

    C -> next = NULL                             //該節(jié)點指向為空

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

    {

        s = (LNode*)malloc(sizeof(LNode));       //新申請一個結點，指針s指向這個結點

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

                                                 //此時，結點值域和指針都有了，一個完整的結點就建好了，要想把這個結點插進鏈表C中

                                                 //只需要讓這個結點的指針指向鏈表C的開始結點即可

        s -> next = C -> next;                           //結點s指向C指針的開始結點

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

    }

}

三、雙鏈表操作

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

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

{

    DLNode *s,*r;

    int i;

    L = (DLNode*)malloc(sizeof(DLNode)); //新建一個結點L

    L -> prior = NULL;

    L -> next = NULL;

    r = L;                               //r指針指向結點L的終端結點，開始頭結點也是尾結點

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

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

        s -> data = a[i]                      //結點s的值域為a[i]

        r -> next = s;                        //r指針的后繼指針指向s結點

        s ->prior = r;                        //s的前結點指向r

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

    }    

    r -> next = NULL;                         //直到r指針指向為NULL

}

2.查找結點的算法

在雙鏈表中查找值為x的結點，如果找到，則返回該結點的指針，否則返回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.插入結點的算法

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

s -> next = p -> next;

s -> prior = p;

p -> next = s;

s -> next -> prior = s;

4.刪除結點的算法

要刪除雙鏈表中p結點的后繼結點，核心思想就是先將p的后繼結點給到q,然后讓p指向q的后繼結點，q的后繼結點的前結點就是p，然后把q釋放掉，具體代碼如下：

q = p -> next;

p -> = q -> next;

q -> next -> prior = p;

free(q);

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