数据结构与算法

1.线性表

定义

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

若用 L 命名线性表，则其一般表示如下：

L=(a1,a2,...ai,ai+1,...,an)

其中，a1 是唯一的“第一个”数据元素，又称为表头元素；an 是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

特点

线性表常见的特点如下：

• 表中元素的个数是有限的；

• 表中元素具有逻辑上的顺序性，在序列中各元素排列有先后次序；

• 表中元素都是数据元素，每一个表元素都是单个元素；

• 表中元素的数据类型都相同，这意味着每一个表元素占有相同数量的存储空间；

• 表中元素具有抽象性，就是说，仅讨论表元素之间的逻辑关系，不考虑表元素究竟表示什么内容

分类

线性表的基本操作

InitList(L); //初始化表。构造一个空的线性表；
Legnth(L); //求表长度。返回线性表L的长度，即L中数据元素的个数；
LocateElem(L, e); //按值查找操作。在表L中查找具有给定关键字值的元素；
GetElem(L, i); //按位查找操作。获取表L中第i个位置的元素的值；
ListInsert(L, i, e); //插入操作。在表L中第i个位置上插入制定元素；
ListDelete(L, i, e); //删除操作。删除表L中第i个位置上的元素；
PrintList(L); //输出操作。按前后顺序输出线性表L的所有元素的值；
Empty(L); //判空操作

1.1 线性表的顺序表示(顺序表)

线性表的顺序存储又称之为顺序表。

它是用一组连续地址的存储单元，依次存储线性表的数据元素，从而使得逻辑上相邻的两个元素在物理上也相邻。

特点

• 顺序表中元素的逻辑顺序与物理顺序相同

2. 链表