简述线性表定义和逻辑特征

简述线性表定义和逻辑特征

简述线性表定义和逻辑特征
(1)线性表
概念：实际上是基于前面元素和后面元素之间的一种相邻关系的结构
特点：
1.是由n（n>=0）个元素组成的有序序列
2.都有唯一的第一个元素和唯一一个最后元素，当n=0时，线性表为空表。线性

表每个元素，初第一个外，都有且仅有一个前驱元素，初最后一个元素外，都有

且仅有一个后续元素
3.在该序列中，所有的元素都有相同的结构，要么是同样类型的数据，要么是同

样类型的复杂结构。

(2)顺序表
概念：顺序表是线性表在顺序存储形式下构成的表
特点：
1.顺序表的存储是指在内存中，在一段连续的存储单元中存储的线性表。
2.逻辑结构上相邻的数据元素（直接前驱和直接后续）在存储位置(或物理位置)

上也相邻。根据上述只要知道首地址和每个数据元素所占的字节数，就可以求出

第n个数据元素的地址

(3)链表
概念：链表也是一种有顺序的表，其内容可以存储在一组任意的存储单元中，所

谓任意的存储单元，即这组存储单元可以是连续，也可以是不连续的，这就需要

在存储元素本身信息的同时，还有存储下一个元素的位置，由此构成一个链状结

构，称其为链表。
特点：
1.链表的头部（头结点）只表示整个链表的起始位置，而无任何信息。对于最后

一个结点（尾结点），后面无任何元素，其表示元素的位置的地址用“^”来表

示，程序实现中用“null”来表示
2.每个结点都有两个区域（数据域和指针域）。
3.每个操作都从头结点开始
4.每个节点的指针域都指向下一个结点的地址，尾节点除外（尾节点的指针域为

null）

(4)线性表的逻辑结构
概念：相邻元素之间所满足的前驱和后续的逻辑关系。
特点：
1.每个元素都有唯一的前驱和后续，起始元素和结束元素除外（起始元素只有后

续，结束元素只有前驱）

(5)线性表的存储结构
概念：线性表在计算机中的表示形式，可以分为顺序存储结构和链式存储结构
特点：
(1)顺序存储结构用一段连续的空间来存储，有利于节省存储空间
(2)链式存储结构存储在一组任意的存储单元，所谓的任意存储单元，即这组存