数据结构-顺序表

发表于 更新于 分类于
  • 顺序表的描述与表示
  • 顺序表的操作接口定义
  • 顺序表的操作实现

顺序表的描述与表示

首先介绍线性表（Linear List），线性表是一种允许在序列任意位置进行操作的数据结构。采用顺序存储结构表示的线性表称为顺序表。用一组地址连续的存储单元依次存放线性表的数据元素，以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系。

顺序表的类型定义： 

1
2
3
4
5
6
typedef struct {
  ElemType* base;     // 顺序表存储空间的基址
  int length;         // 顺序表当前长度
  int size;           // 顺序表的存储容量
  int increment;      // 顺序表扩容时的增量
}SqList;

本文中预定义的说明

预定义常量和类型

1
2
3
4
5
6
7
8
//函数结果状态代码
#define TRUE      1
#define FALSE     0
#define OK        1
#define ERROR     0
#define OVERFLOW -1

typedef int Status; // 用作函数值类型，表示函数结果状态

数据结构（存储结构）的表示

数据结构的表示用类型定义(typedef)描述。数据元素类型约定为ElemType，读者在使用该数据类型时自行定义，如int、char等简单类型。

扩展引用调用

为了便于算法描述，我们使用了 C++ 语言中的引用调用参数传递方式。

顺序表的操作接口定义

由于采用了顺序存储结构，如果在顺序表中插入或删除元素，则需要移动操作位置之后的所有元素。实际上，如果需要频繁地插入和删除数据，选择顺序表作为抽象数据结构是一个极大的错误。虽然下面给出了删除和插入接口的定义，但在这种情况下应该竭力避免使用顺序表存储结构。

顺序表的接口定义如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 初始化顺序表L
Status InitList_Sq(SqList &L, int size, int inc);
// 销毁顺序表L
void DestroyList_Sq(SqList &L);
// 将顺序表L清空
Status ClearList_Sq(SqList &L);
// 判断顺序表是否为空，是返回 TRUE, 否则返回 FALSE
Status ListEmpty_Sq(SqList L);
// 返回顺序表L中元素个数
int ListLength_Sq(SqList L);
// 用e返回顺序表L中第i个元素的值
Status GetElem_Sq(SqList L, int i, ElemType &e);
// 在顺序表L中查找元素e，查找成功返回该元素在表中第一次出现位置，否则返回-1
int Search_Sq(SqList, ElemType e);
// 遍历顺序表L， 依次对每个元素调用visit()
Status ListTraverse_Sq(SqList L, Status( *visit)(ElemType e));
// 将顺序表L中第i个元素赋值为e
Status PutElem_Sq(SqList &L, int i, ElemType e);
// 在顺序表L表尾添加元素e
Status Append_Sq(SqList &L, ElemType e);
// 删除顺序表L表尾元素，并用e返回
Status DeleteLast_Sq(SqList &L, ElemType &e);
// 在顺序表第i个元素之前插入新的元素e，表长加1
Status InsertList_Sq(SqList &L, int i, ElemType e);
// 删除顺序表的第i个元素，返回到e，表长减1
Status DelElem_Sq(SqList &L, int i, ElemType &e);

顺序表接口实现

初始化顺序表

  • 分配存储空间
  • 给定顺序表容量
  • 给定扩容增量
1
2
3
4
5
6
7
8
9
10
Status InitList_Sq(SqList &L, int size, int inc)
{
  L.base = (ElemType*)malloc(size * sizeof(ElemType));
  if (NULL == L.base)
    return OVERFLOW;
  L.size = size;
  L.increment = inc;

  return OK;
}

销毁顺序表

1
2
3
4
void DestroyList_Sq(SqList &L)
{
  free(L.base);
}

将顺序表清空

1
2
3
4
void ClearList_Sq(SqList &L)
{
  L.length = 0;
}

判断顺序表是否为空

1
2
3
4
5
6
7
Status ListEmpty_Sq(SqList L)
{
  if (L.length == 0)
    return TRUE;
  else
    return FALSE;
}

求顺序表元素个数

1
2
3
4
int ListLength_Sq(SqList L)
{
  return L.length;
}

求第 i 个元素值

1
2
3
4
5
6
7
8
Status GetElem_Sq(SqList L, int i, ElemType &e)
{
  if (i < 0 || i > L.length)
    return ERROR;
  e = L.base[i - 1];

  return OK;
}

顺序查找

1
2
3
4
5
6
7
8
9
10
int Search_Sq(SqList L, ElemType e)
{
  int i = 0;
  while (i < L.length && L.elem[i] != e)
    i++;
  if (i < L.length)
    return i;
  else
    return ERROR;
}

访问每个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
status ListTraverse_Sq(SqList L, Status(*visit)(ElemType e))
{
  int i;

  if (L == NULL || L.length <= 0)
    return ERROR;

  for (i = 0; i < L.length; i++) {
      visit(L.base[i]);
  }  

  return OK;
}

赋值指定位序元素

1
2
3
4
5
6
7
8
9
Status PutElem_Sq(SqList &L, int i, ElemType e)
{
  if (i > L.length || L == NULL)
    return ERROR;

  L.base[i - 1] = e;

  return OK;
}

添加表尾元素

  • 判断表是否已满
    • 若已满，扩容
  • 添加元素
  • 表长 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status Append_Sq(SqList &L, ElemType e)
{
  ElemType *newbase;
  if (L.length == L.size) {
  	 newbase = (ElemType*)realloc(L.base, (L.size + L.increcement) * sizeof(ElemType));
     if (NULL == newbase)
         return OVERFLOW;
      L.base = newbase;
      L.size += L.increcement;
  }

  L.base[L.length] = e;
  L.length++;

  return OK;
}

删除表尾元素

1
2
3
4
5
6
7
8
9
10
Status DeleteLast_Sq(SqList &L, ElemType &e)
{
  if (0 == L.length || NULL == L)
    return ERROR;

  e = L.base[L.length - 1];
  L.length--;

  return OK;
}

插入元素

时间复杂度：\(O(n)\)

  • 判断参数i是否合法，不合法则返回异常
  • 判断表是否已满，已满则扩容
  • 从最后一个元素遍历至第i个元素位置，全部后移一位
  • 赋值，表长加1

由于插入元素需要移动数组元素位置，算法效率不高，因此在频繁需要进行插入操作的问题中，应避免使用此结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Status InsertList_Sq(SqList &L, int i, ElemType e) 
{
 	int k;
    
    if (i < 1 || i > (L.length + 1)) 
        return ERROR;
    if (L.>length == L.>size) {
    	 newbase = (ElemType*)realloc(L.base, (L.size + L.increcement) * sizeof(ElemType));
         if (NULL == newbase)
             return OVERFLOW;
          L.base = newbase;
          L.size += L.increcement;
    }
  
    if (i < L.length + 1)   
        for (k = L.length - 1; k > i - 1; k--)
            L.base[k] = L.base[k - 1];
    L.base[i - 1] = e;
    L.lenght++;
    
    return OK;
}

删除元素

时间复杂度：\(O(n)\)

  • 判断参数i是否合法
  • 判断表是否非空
  • 取出删除元素
  • 从被删元素位置开始向后遍历至最后一个元素，往前挪动一位
  • 表长 - 1 同样地，删除元素也需要移动数组元素，故如需频繁删除元素，也应避免考虑顺序表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status DelElem_Sq(SqList &L, int i, ElemType &e)
{
    int k;
    
 	if (i < 1 || i > L.length) 
        return ERROR;
    if (L.length == 0)
        return ERROR;
    if (i < L.lengh) 
    	for (k = i - 1; k < L.length - 1; k++) 
         	L.base[k] = L.base[k + 1];   
        
    L.length--;
    return OK;
}

顺序表的优缺点

优点

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任一位置的元素

缺点

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的“碎片”

参考资料

  • 《数据结构》（吴伟民，李小妹）
  • 《大话数据结构》