软考软件设计师专题讲义九：常用数据结构

 　2. 常用数据结构

　　2.1线性表

　　在数据结构中，线性结构常称为线性表，是最简单、最常用的一种数据结构，它是由n个相同数据类型的结点组成的有限序列。

　　其特点是：在数据元素的非空有限集合中，

　　u ◆存在唯一的一个被称做"第一个"的数据元素

　　u ◆存在唯一的一个被称做"最后一个"的元素数据元素

　　u ◆除第一个之外，集合中的每个数据元素均只有一个前驱

　　u ◆除最后一个之外，集合中每个数据元素均只有一个后继

　　一个由n个结点e0，e1…，en-1组成的线性表记为：(e0，e1…，en-1)。线性表的结点个数称为线性表的长度，长度为0的线性表称为空的线性表，简称空表。对于非空线性表，e0是线性表的第一个结点，en-1是线性表的最后一个结点。线性表的结点构成了一个序列，对序列中两个相邻结点ei和ei-1，称前者是后者的前驱结点，后者是前者的后继结点。

　　线性表最重要的性质是线性表中结点和相对位置是确定的。

　　线性表的结点也称为表元，或称为记录，要求线性表的结点一定是同一类型的数据。线性表的结点可由若干个成分组成，其中唯一标识表元的成分成为关键字，简称键。

　　线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。对线性表的基本运算如下：

　　u INITIATE(L)初始化操作

　　u LENGTH(L) 求长度函数

　　u GET(L，i) 取元素函数

　　u PRIOR(L，elm)求前驱函数

　　u NEXT(L，elm) 求后继函数

　　u LOCATE(L，x) 定位函数

　　u INSERT(L，i，b)插入操作

　　u DELETE(L，i) 删除操作

　　有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。根据存储方式的不同，其上述的运算实现也不一样。

　　u◆ 顺序存储：是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。

　　顺序存储方式优点：能直接访问线性表中的任意结点。

　　线性表的第i个元素a[i]的存储位置可以使用以下公式求得： LOC(ai)=LOC(a1)+(i-1)*l

　　式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。

　　顺序存储的缺点：

　　1) 线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少;

　　2) 执行线性表的插入和删除操作要移动其他元素，不够方便;

　　◆链式存储

　　线性表链接存储是用链表来存储线性表。

　　单链表(线性链表)：

　　从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。链表的每个表元除要存储线性表结点的信息以外，还要有一个成分来存储其后继结点的指针。

　　线性链表的特点是：每个链表都有一个头指针，整个链表的存取必须从头指针开始，头指针指向第一个数据元素的位置，最后的节点指针为空。当链表为空时，头指针为空值;链表非空时，头指针指向第一个节点。

　　链式存储的缺点：

　　1) 由于要存储地址指针，所以浪费空间;

　　2) 直接访问节点不方便;

　　循环链表：

　　循环链表是另一种形式的链式存储结构，是单链表的变形。它的特点就是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任意一个结点出发都可以找到表中的其他结点。

　　循环链表和单向链表基本一致，差别仅在于算法中循环的条件不是结点的指针是否为空，而是他们的指针是否等于头指针，

　　循环链表最后一个结点的 link 指针不为 0 (NULL)，而是指向了表的前端。

　　为简化操作，在循环链表中往往加入表头结点。

　　循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。

　　循环链表的示例：