首页 > 代码库 > 线性表

线性表

  • 线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。线性表主要由顺序表示或链式表示。在实际应用中,常以栈、队列、字符串等特殊形式使用。
  • 顺序表示:物理位置上相邻
  • 链式表示:逻辑关系上相邻

顺序存储方式:

技术分享
const int maxn = 100;  // 数组的最大长度struct seq_list{    int data[maxn];    ElemType len;     // 当前线性表的长度,应初始化为0};// 查取第i个元素 主要是注意表的状态以及参数的合法性// 线性表非空 + 索引i 是第i个, 故而范围 [1, L.len]bool get_elem(seq_list L, int i, ElemType *e){    if(L.len == 0 || i < 1 || i > L.len) return false;    *e = L.data[i - 1];    return true;}// 往第i个位置插入元素e// 插入得: 线性表未满 + i ∈ [1, L.len + 1] 并且,若不是在尾巴后插入元素,元素需往前调整bool insert_elem(seq_list& L, int i, ElemType e){    if(L.len == maxn || i < 1 || i > L.len + 1)  return false;    if(i != L.len + 1){        for(int j = L.len - 1; j >= i - 1; --j){            L.data[j + 1] = L.data[j];         }    }    L.data[i - 1] = e;    ++L.len;    return true;}// 删除第i个元素,同理,需:线性表非空 + i ∈ [1, L.len]// 如果删除的并非最后一个元素,删除之后(这里可以不做真实的删除操作,直接覆盖并且控制L.len即可// 删除之后需要调整,从第 i + 1个到第 L.len个元素,都往前挪一个位置 并且 --L.lenbool delete_elem(seq_list& L, int i, ElemType *e){    if(L.len == 0 || i < 1 || i > L.len)  return false;    *e = L.data[i - 1];    if(i != L.len){        for(int j = i; j < L.len; ++j){            L.data[j + 1] = L.data[j];        }    }    --L.len;    return true;}
顺序存储

 

线性表