顺序表的查找、插入、删除、合并操作及其优缺点

顺序表的查找、插入、删除、合并操作，用c++实现相关代码：

#include<iostream>

using namespace std;

//定义线性表顺序存储结构

#define MAXSIZE 100  //线性表最大长度

typedef struct

{

//线性表占用数组空间

int elem[MAXSIZE];

//记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1

int last;

}SeqList;

//顺序表的按内容查找运算

//在顺序表L中查找与e相等的元素，若L.elem[i]=e,则找到该元素，并返回i+1,若找不到，则返回-1

int  Locate(SeqList L, int e)

{

//i为扫描计数器，初值为0，即从第一个元素开始比较

int i = 0;

//顺序扫描表，直到找到值为e的元素或扫描到表尾而没有找到

while ((i<=L.last)&&(L.elem[i]!=e))

{

i++;

}

if (i <= L.last)

{

return (i + 1);//若找到值为e的元素，则返回其序号

}

else

{

return -1;//若没找到，则返回空序号

}

}

//顺序表的插入运算

#define OK 1

#define ERROR 0

//在顺序表L中第i个数据元素之前插入一个元素e,n个元素有n+1个插入位置,1<=i<=L->last + 2

int InsList(SeqList *L, int i, int e)

{

int k = 0;

if ((i<1) || (i>L->last + 2))//判断插入位置是否合法

{

cout << "插入位置i值不合法！" << endl;

return (ERROR);

}

if (L->last >= MAXSIZE - 1)

{

cout << "表已满，无法插入！" << endl;

return (ERROR);

}

for (k = L->last; k >= i - 1; k--)//为插入元素而移动位置

{

L->elem[k + 1] = L->elem[k];

}

L->elem[i - 1] = e;

L->last++;

return (OK);

}

//顺序表的删除运算

//在顺序表L中删除第i个数据元素,并用指针参数e返回其值,1<=i<=L->last + 1

int DelList(SeqList *L, int i, int *e)

{

int k = 0;

if ((i<1) || (i>L->last + 1))//判断删除位置是否合法

{

cout << "删除位置不合法！" << endl;

return (ERROR);

}

*e = L->elem[i - 1];//将删除的元素存放到e所指向的变量中

for (k = i; k <= L->last; k++)//将后面的元素依次前移

{

L->elem[k - 1] = L->elem[k];

}

L->last--;

return (OK);

}

int main()

{

        //

system("pause");

return 0;

}

例：有两个顺序表LA,LB，其元素均为非递减有序排列，编写算法将它们合并成一个顺序表LC，要求LC也是非递减有序排列。

解：算法如下：

//线性表的合并运算

void MergeList(SeqList *LA, SeqList *LB, SeqList *LC)

{

int i = 0, j = 0, k = 0;

while ((i <= LA->last) && (j <= LB->last))

{

if (LA->elem[i] <= LB->elem[j])

{

LC->elem[k] = LA->elem[i];

i++;

k++;

}

else

{

LC->elem[k] = LB->elem[j];

j++;

k++;

}

}

while (i <= LA->last)//当表LA有剩余元素时，则将表LA的剩余元素赋给表LC

{

LC->elem[k] = LA->elem[i];

i++;

k++;

}

while (j <= LB->last)//当表LB有剩余元素时，则将表LB的剩余元素赋给表LC

{

LC->elem[k] = LB->elem[j];

j++;

k++;

}

LC->last = LA->last + LB->last + 1;

}

顺序表的优点：1.无须为表示结点间的逻辑关系而增加额外的存储空间； 

              2.可方便随机存取表中任一元素。

缺点：1.插入或删除运算不方便；

      2.由于顺序表要占用连续的存储空间，存储分配只能预先进行静态分配，当表长变化较大时，难以确定合适的存储规模。