数据结构——线性表杂记

什么是线性表

线性表是一种常用的数据结构，表示元素之间一对一的相邻关系。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。

线性表是具有相同数据类型的n (n>=0)个数据元素的有限序列。其中n为表长，当n=0 时该线性表是一个空表。若用L命名线性表，则其一般表示如下： L=(a1, a2, …, ai, ai+1, …, an)

其中，a1是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

由此，我们得出线性表的特点如下：

表中元素的个数有限。
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序。
表中元素都是数据元素，每一个表元素都是单个元素。
表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。
表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究竟表示什么内容。

三种特殊线性表

栈
队列
串

从数据结构角度看，栈和队列是操作受限的线性表，它们的逻辑结构相同

串是重要的非数值处理对象，它是以字符作为数据元素的线性表

//这里我们主要讨论下栈与队列概念/区别

栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。

如：在建筑工地上，使用的砖块从底层一层一层向上放，使用时从最上面一层一层的拿。所以为后进先出。

队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

如：在生活中排队上车，排队的规则是不允许插队，后来的人需要站在队尾，每次总是对头先上车。所以为先进先出。

栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下：

线性表

Insert(L,i,x) 
(1≤i≤n+1) 
Delete(L,i) 
(1≤i≤n)

Insert(L,i,x)

(1≤i≤n+1)

Delete(L,i)

(1≤i≤n)

如线性表允许在表内任一位置进行插入和删除

栈

Insert(L,n+1,x) 
Delete(L,n)

Insert(L,n+1,x)

Delete(L,n)

而栈只允许在表尾一端进行插入和删除

队列

Insert(L,n+1,x) 
Delete(L,1)

Insert(L,n+1,x)

Delete(L,1)

队列只允许在表尾一端进行插入，在表头一端进行删除

END

学习哇

参考：百度/谷歌 (ง •̀_•́)ง

标签线性表下的文章