数据结构之线性表

线性表的基本概念

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列。

其中，当n=0是成为空表。

线性表的特点

1. 对于一个非空的线性表，有且仅有一个开始结点(a1),它没有直接前驱。
2. 有且仅有一个终端结点(an),它没有直接后继。
3. 除了开始结点和终端结点以外，其余的结点有且仅有一个直接前驱和一个直接后继。

线性表的基本操作（逻辑结构层次）

1. 初始化线性表InitList(L).
   初始化条件：表不存在。
   操作结果：其作用是建立一个空表L.
2. 求线性表的长度GetLength(L)
   初始条件：线性表L存在。
   操作结果：返回线性表的L的长度。
3. 按照位置查找元素GetElem(L,i,x)。
   初始条件：线性表L存在，i是表中元素的位置，x是找到该元素的返回值。
   操作结果：在线性表中查找第i位的元素，有，则利用x返回该元素，并返回1；否则返回0。
4. 按照数值查找元素Locate(L,x)
   初始条件：线性表L存在，x是给定的一个待查的数值元素。
   操作结果：在线性表L中查找与x数值相同的元素，若线性表中存在一个或多个这样的元素，则返回元素所在位置的最小值或地址值；否则返回0或NULL.
5. 插入操作InsElem(L,i,x)
   初始条件：线性表存在，并且插入位置正确.
   操作结果：在作用是在线性表的第i位置插入一个值为x的新元素，使得线性表长度+1
6. 删除操作DelElem(L,i,x)
   初始条件：线性表存在，并且删除位置正确.
   操作结果：在作用是删除线性表在第i位置上的元素并用x将其储存，使得线性表长度-1
7. 显示操作DisList(L)
   初始条件：线性表存在，且非空。
   操作结果：依次扫描线性表L,并输出各个元素的值。
8. 等等。。。

线性表的存储

顺序表