线性表的定义

• 线性表就是零个或多个相同数据元素的有限序列

线性表特征（假设a为一张线性表）

• 对非空表，a[0]是表头，无前驱
• a[n-1]是表尾，无后继
• 其它的每个元素a[i]有且仅有一个直接前驱a[i-1]和一个后继a[a+1]

线性表的基本运算（假设L为一张线性表）

• 建立一个空表：Createlist(L)
• 置空表：ClearList(L)
• 判断表是否为空：IsEmpty(L)
  • 若为空返回True(1)，否则返回False(0)
• 求表长：Length(L)
• 取表中的某个元素：GetList(L,i)，即L[i]，要求 0<=i<legth(L)-1
• 定位运算：Locate(L,x) 确定元素x在表L的位置
  • 如果存在返回位置信息，如果不存在返回-1
• 插入：Insert(L,x,i)，将元素x插入到L表的第i个元素之前，且表长+1
• 添加：Add(L,x)，将元素x加入到L表中，且长+1
• 删除：Delete(L,i)，删除表L的第i个元素，且表长-1，要求 0<=i<legth(L)-1
• 复合元素
  • 合并：Merge(L1,L2)，将表L1和表L2合并为一张表，去重
  • 去重：Deduplication(L)，将表L的元素去重

顺序存储

• 顺序存储结构的特点
  • 逻辑上相邻的额元素a[i]，a[i+1]，其存储位置也是相邻的
  • 对数据元素a[i]的存取为随机存取或按地址存取
  • 存储密度高。存储密度D=（数据结构中元素所占存储空间）/（整个数据结构所占空间）
• 顺序存储结构的不足
  • 对表的插入和删除等运算时间复杂度较高

线性表

原文：https://www.cnblogs.com/binHome/p/12818224.html