数据结构——线性表（C++）

一、线性表的定义

线性表：零个或多个数据元素的有限序列。
线性表是最常用且是最简单的一种数据结构。形如：A1、A2、A3….An这样含有有限的数据序列，我们就称之为线性表。

线性表包括顺序表和链表。
顺序表（其实就是数组）里面元素的地址是连续的，
链表里面节点的地址不是连续的，是通过指针连起来的。

二、线性表的抽象数据类型

线性表的抽象数据类型定义如下：

ADT 线性表(List) Data
    线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。
    其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，
    除最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。

Operation
    InitList(*L):初始化操作，建立一个空的线性表。
    ListEmpty(L):若线性表为空，返回true，否则返回false。
    ClearList(*L):线性表清空。
    GetElem(L,i,*e):将线性表L中第i个位置元素返回给e。
    LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功,返回该元素在表中的序列号；否则，返回0表示失败。
    ListInsert(*L,i,e):在线性表的第i个位置插入元素e。
    ListDelete(*L,i,*e):删除线性表L中的第i个元素，并用e返回其值
    ListLength(L):返回线性表L的元素个数。
    PrintList(L):打印线性表

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的。 
对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、线性表的顺序存储

1. 顺序存储定义

顺序表，一般使用数组实现，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定连续的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中，数组大小有两种方式指定，一是静态分配，二是动态扩展。
  顺序表相关的操作跟数组有关，一般都是移动数组元素。

2.顺序存储的实现方式

结构
我们直接来看顺序表的模板类的代码：

const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
	SeqList(){Length = 0;}			//无参数构造方法
	SeqList(DataType a[], int n)	//有参数构造方法
	~SeqList(){}					//析构函数
	int Length(){return Length ;}	//线性表长度
	DataType Get(int i);			//按位查找
	int Locate(DataType x);			//按值查找
	void Insert()
}
1
2
3
4
5
6
7
8
9
10
11
12
13

四、线性表的链式存储

五、其他线性表

参考