数据结构篇之线性表①

定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

1. 线性表中的第一个元素被称为表头元素，最后一个元素被称为表尾元素。
2. 线性表中，除了第一个元素外，每一个元素有且仅有一个直接前驱（前驱）。
3. 线性表中，除了最后一个元素外，每个元素有且仅有一个直接后继（后继）。

线性表特点如下：

• 表中元素个数有限。
• 表中元素具有逻辑上的顺序性，表中元素都有先后顺序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型是相同的，也就是说，每个元素占有相同大小的存储空间。
• 表中的元素具有抽象性，即仅仅讨论元素之间的逻辑关系，不考虑元素究竟是怎么样的内容。

线性表是一种逻辑结构，表示元素一对一的相邻关系，而顺序表和链表是指的存储结构，逻辑结构与存储结构所在的思想维度不一样，不要将其混淆了。 具体可查阅之前的篇章《数据结构与算法概论》。

基本操作

一个数据结构的基本操作是指其最核心、最基本的操作，就像人类婴儿一出生就必须要有鼻子-呼吸、嘴巴-吮吸这些基本功能，数据结构也一样。 而其他的复杂操作实现可以基于基本操作来封装。

线性表应当具备以下基本操作：

• init(&L)-初始化表，构造一个空的线性表。
• length(L)-求表长，返回线性表的长度(表L中的元素个数)。
• locateItem(L,e)-关键词查找，查找出表L中具有给定关键词值的元素。
• getItem(L,i)-位置索引查找，查找出表L中的第i个位置的元素。
• insert(&L,i,e)-插入操作，将元素e插入到表L中的第i个位置。
• delete(&L,i,&e)-删除操作，删除表L中i位置的元素并将元素使用e返回。
• print(L)-输出操作，按照前后顺序输出线性表L中的所有元素。
• empty(L)-判空操作，若表L为空则返回true，否则返回false。
• destroy(&L)-销毁操作，销毁线性表并释放占用的内存。

上文的基本操作仅供参考，根据编程语言、存储结构的不同，算法实现也不同。 上文以&开头的属性类似于指针或者引用的传递。