线性表之顺序表示(顺序表)

---

在进入顺序表的讨论之前，我们应该明白顺序表和单链表都属于线性表。对于线性表的基本定义和操作我们不做详述，但是我们列出线性表的基本特点作为前提：

• 表中元素个数有限
• 表中元素在逻辑上具有顺序性
• 表中元素的数据类型都必须相同，并且占用存储空间大小相同
  注：线性表是一种逻辑结构，顺序表和链表是指存储结构。
  下面正式进入本节的学习。

一.顺序表

1.顺序表的定义

线性表的顺序存储又称为顺序表。表示在逻辑上相邻的两个元素的物理存储位置也相邻。如图：

结构图(图片源于百度).jpg

通常我们将顺序表的存储结构定义为：

#define Maxsize 50 
typedef struct{
  ElemType data[MaxSize];   //顺序表的元素
  int length;  // 顺序表的当前长度
}

上面是进行静态分配地址的顺序表，可以明显发现数组的空间已经固定，一旦空间占满，程序将会崩溃。于是，在此基础上，人们提出了动态顺序表的概念：

#define InitSize 100
typedef struct{
ElemType *data;
int MaxSize,length;
}

初始化分配：

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

通过上述的定义，我们能够总结出顺序表的特征：

• 随机访问，能够在O(1)找到指定元素
• 存储密度高，每个节点只存储数据元素
• 删除和插入需要移动大量元素

2.顺序表的操作

(1).插入操作

bool listInsert(Sqlist &L,int i,ElemType e){
if(i<1||i>L.length+1)
        return false;
if(L.length>maxsize)
        return false;
for(int j=L.length;j>=i;j--){
  L.data[j]=L.data[j-1];
  L.data[i-1]=e;
  L.length++;
        return true;
}
}

(2).删除操作

bool listDelet(Sqlist &l,int i,int &e){
if(i<1||L.length)
        return false;
e=L.data[i-1];
for(int j=i;j<L.length;j++)
    L.data[j-1]=L.data[j];
L.length--;
return true;
}

(3).按值查找

int LocateElem(Sqlist L,ElemType e){
     int i;
     for(i=0;i<L.length;i++)
     if(L.data[i]==e)
          return i+1;
return 0;
}

二.顺序表的应用