线性结构 - 顺序表小结

对于非空的线性表和线性结构，其特点如下：
存在唯一的一个被称作 "第一个" 的数据元素
存在唯一的一个被称作 "最后一个" 的数据元素
除了第一个之外，结构中的每个数据元素均有一个前驱
除了最后一个之外，结构中的每一个数据元素都有一个后继

顺序存储

指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像。

顺序表

是在计算机内存中以数组的形式保存的线性表，是将表中的结点依次存放在计算机内存中一组地址连续的存储单元。

/* 空间大小 */
#define MAXSIZE 100
/* ElemType是数据类型，具体类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* 顺序表结构设计 */
typedef struct {
    ElemType *data; /* 存储数据 */
    int length;     /* 顺序表中数据的个数 */
}SeqList;

存储结构要体现数据的逻辑结构，顺序表的存储结构，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系

只要确定了起始位置，表中任一数据元素的地址都通过下列公式得到：
Location(ki) = Location(a1) + (i - 1) * Length; 1 < i < n
其中，Length是元素占用存储单元的长度。

顺序表的基本操作 (c语言)

1. 构建一个空的顺序表

// 1. 分配MAXSIZE大小的数组空间
// 2. 分配失败
// 3. 空表长度置0

Status initList(SeqList *L) {
    
    L->data = malloc(sizeof(ElemType) * MAXSIZE);
    
    if (!L->data) return ERROR;
    
    L->length = 0;
    
    return OK;
}

2. 销毁

// 已知条件： 顺序表L已存在
// 1. 释放存储空间
// 2. 表长度置0

Status destroyList(SeqList *L) {
    
  free(L->data);
  
  L->data = NULL;
  
  L->length = 0;
  	
  return OK;
}

3. 置空

// 初始条件：顺序线性表L已存在
// 清空顺序表，只需要将顺序表的长度置为0

Status clearList(SeqList *L) {
    /* 将顺序表置为空表，即表长度为0 */
    L->length = 0;
    return OK;
}

4. 判断是否为空

// 初始条件：顺序线性表L已存在
// 判断L的length是否等于0

Status isEmptyList(SeqList L) {
    if (L.length == 0) {
        return TRUE;
    }else return FALSE;
}

5. 表中数据元素的个数

// 初始条件：顺序线性表L已存在
// 返回L的length，即数据元素个数

Status lengthOfList(SeqList L) {
    return L.length;
}

6. 遍历

// 初始条件：顺序线性表L已存在
// 从第一个数据元素，按顺序输出

Status traversList(SeqList L) {
    int i;
    for (i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
    return OK;
}

7. 插入

// 初始条件：顺序线性表L已存在，插入位置i满足 1 < i < lengthOfList(L)
// 1. 判断插入位置是否合法
// 2. 判断存储的空间是否已满
// 3. 插入数据不在表尾， 则先移动出空余位置
// 4. 插入位置后，之后的数据后移1位
// 5. 将新元素e，放入第i位置
// 6. 表中数据元素的个数加一

Status insertList(Seqist *L,int i,ElemType e){
    

  if((i<1) || (i>L->length+1)) return ERROR;

  if(L->length == MAXSIZE) return ERROR;
 
  if(i <= L->length){
    for(int j = L->length-1; j>=i-1;j--){
      L->data[j+1] = L->data[j];
    }
  }
  
  L->data[i-1] = e;

  ++L->length;

  return OK;
    
}

8. 删除

// 初始条件：顺序线性表L已存在，删除位置i满足 1 < i < lengthOfList(L)
// 1. 判断删除位置是否合法
// 2. 顺序表是否已为空表
// 3. 删除第 i 位置数据元素
// 4. 表中数据元素的个数减一

Status deleletList(SeqList *L, int i) {
    
  if (i < 1 || i > (L->length + 1)) {
    return ERROR;
  }
    
  if (L->length == 0) {
    return ERROR;
  }
    
  for (int j = i; j < L->length; j++) {
    L->data[j - 1] = L->data[j];
  }

  L->length--;

  return OK;
}

查看demo