（一）线性表的介绍
线性表：线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
（1）逻辑上是线性结构，物理结构连续——顺序表。
（2）逻辑上是线性结构，物理结构不连续——链表。
(二) 顺序表基本运算的实现
链接: 顺序表基本运算的实现（第二章：线性表）
(三) 线性表顺序存储的应用：
问题： 已知长度为n的线性表A采用顺序存储结构，设计算法，删除线性表中所有值为x的数据元素。
要求： 时间复杂度为O(n)、空间复杂度为O(1)的算法
一般解法： 用基本运算实现
void delnode1(SqList *&L,ElemType x)
{
int i; ElemType e;
查找第1个值域与x相等的元 素的逻辑位序。若这样的元 素不存在，则返回值为0
while((i=LocateElem(L,x))>0)
{
ListDelete(L, i, e);
} //删除顺序表L的第i个元素
}
这样的解法会消耗大量的时间，假设数组的长度为n，要删除第一个值为x下标为 i 的元素，就要把整体的位置向前移动 n-i 个位置，删除其它一个值为x的元素，也是需要移动所被删除元素之后的那些元素的位置！
举个
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
