一、何为线性表?

线性表,全名为线性存储结构。使用线性表存储数据的方式可以这样理解,即“把所有数据用一根线儿串起来,再存储到物理空间中”。将具有“一对一”关系的数据“线性”地存储到物理空间中,这种存储结构就称为线性存储结构(简称线性表)。

2-1 数据的线性结构.png

1. 两种线性存储结构

线性表存储数据可细分为以下 2 种:

2-2 两种线性存储结构.png

  1. 将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表);
  2. 数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表);

2. 线性表常用术语

数据结构中,一组数据中的每个个体被称为“数据元素”(简称“元素”)。例如,图 1 显示的这组数据,其中 1、2、3、4 和 5 都是这组数据中的一个元素。

某一元素的左侧相邻元素称为“直接前驱”,位于此元素左侧的所有元素都统称为“前驱元素”;

某一元素的右侧相邻元素称为“直接后继”,位于此元素右侧的所有元素都统称为“后继元素”;


二、顺序存储结构(顺序表)

顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据依次存储起来,存储时做到数据元素之间不留一丝缝隙。

由此我们可以得出,将“具有一对一逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。

可以发现,顺序表存储数据同数组非常接近。其实,顺序表存储数据使用的就是数组。

1. 顺序表的初始化

初始化操作就是构造一个空的顺序表。

(1)参数用引用

1
2
3
4
5
6
Status InitList_Sq(SqList &L){     //构造一个空的顺序表L
L.elem=new ElemType[MAXSIZE]; //为顺序表分配数组空间
if(!L.elem) exit(OVERFLOW); //存储分配失败退出
L.length=0; //空表长度为0
return OK;
}

(2)参数用指针

1
2
3
4
5
6
Status InitList_Sq(SqList *L){        //构造一个空的顺序表L
L-> elem=new ElemType[MAXSIZE]; //为顺序表分配数组空间
if(! L-> elem) exit(OVERFLOW); //存储分配失败退出
L-> length=0; //空表长度为0
return OK;
}

2. 顺序表的取值

获取线性表L中的某个数据元素的内容

1
2
3
4
5
6
int GetElem(SqList L,int i,ElemType &e)
{
if (i<1||i>L.length) return ERROR; //判断i值是否合理,若不合理,返回ERROR
e=L.elem[i-1]; //第i-1的单元存储着第i个数据
return OK;
}

3. 顺序表的查找

根据指定数据获取数据所在的位置,在线性表L中查找值为e的数据元素

1
2
3
4
5
6
int LocateELem(SqList L,ElemType e)
{
for (i=0;i< L.length;i++)
if (L.elem[i]==e) return i+1;
return 0;
}

4. 顺序表的插入

【算法步骤】:

  1. 判断插入位置i 是否合法。
  2. 判断顺序表的存储空间是否已满。
  3. 将第n至第i 位的元素依次向后移动一个位置,空出第i个位置。
  4. 将要插入的新元素e放入第i个位置。
  5. 表长加1,插入成功返回OK。

在线性表L中第i个数据元素之前插入数据元素e:

1
2
3
4
5
6
7
8
9
Status ListInsert_Sq(SqList &L,int i ,ElemType e){
if(i<1 || i>L.length+1) return ERROR; //i值不合法
if(L.length==MAXSIZE) return ERROR; //当前存储空间已满
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移
L.elem[i-1]=e; //将新元素e放入第i个位置
++L.length; //表长增1
return OK;
}

5. 顺序表的删除

【算法步骤】:

  1. 判断删除位置i 是否合法(合法值为1≤i≤n)。
  2. 将第i+1至第n 位的元素依次向前移动一个位置。
  3. 表长减1,删除成功返回OK。

将线性表L中第i个数据元素删除:

1
2
3
4
5
6
7
Status ListDelete_Sq(SqList  &L, int i){
if((i<1)||(i>L.length)) return ERROR; //i值不合法
for (j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}

三、链式存储结构(链表)

本文未完成…


参考内容:

[1] http://data.biancheng.net/view/157.html