详解三种线性表的操作

线性表是最基本、最简单、也是最常用的一种数据结构。线性表的操作主要分为查找、插入、删除三种，每种操作都对应不同的算法。

线性表分为顺序表和链表，而链表又分为单链表和双链表。下面我们来看这三种线性表的查找、插入和删除的相关操作。

一、顺序表操作：

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.插入数据元素算法

在顺序表L的第p个（0<p<length）个位置上插入新的元素e，如果p的输入不正确，则返回0，代表插入失败；如果p的输入正确，则将顺序表第p个元素及以后元素右移一个位置，腾出一个空位置插入新元素，顺序表长度增加1，插入操作成功，返回1。

int insertElem(Sqlist &L,int p,int e) //L是顺序表的长度，要发生变化，所以用引用型

{

    int i

    if (p<0 || p>L.length || L.length==maxsize) //如果插入e的位置p小于0，或者是大于L的长度，或者是L的长度已经等于了顺序表最大存储空间

        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.删除数据元素算法

将顺序表的第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的下一个结点继续指向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个元素存储在数组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]                         //将数组元素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                             //该节点指向为空

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

    {

        s = (LNode*)malloc(sizeof(LNode));       //新申请一个结点，指针s指向这个结点

        s -> data = a[i]                         //将数组元素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));  //创建一个新节点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);

尽管我们知道这些线性表的操作的实现是基于算法的，但是每种操作的算法都是不尽相同的，需要我们花时间去慢慢理解。在本站的数据结构和算法教程中对线性表基本操作的算法实现有详细的解读，想提升自己的算法知识的小伙伴可以去观看学习。