基本数据结构 之 线性表、数组、广义表

抽象数据类型ADT

抽象数据类型(abstract data type, ADT)是一些操作的集合。抽象数据类型是数学的抽象;在ADT的定义中根本没涉及如何实现操作的集合。这可以看作是模块化设计的扩充。

对诸如表、集合、图和它们的操作一起可以看作是抽象数据类型,就像整数、实数和布尔量是数据类型一样。整数、实数及布尔量有与它们相关的操作,而抽象数据类型也有与它们自己相关的操作。对于集合ADT,我们可以有诸如并(union)、交(intersection)、测定大小(size)以及取余(complement)等操作。或者,我们也可以只要两种操作:并和查找(find)。这两种操作又在该集合上定义了一种不同的ADT。

 

线性表

线性表示最常用、最简单的一种数据结构,简言之,线性表是n个数据元素的有限序列。其一般描述为:

A = (a1,a2, …, an)

它的最基本的特点是每个数据元素最多只能又一个直接前趋,每个数据元素最多只能有一个直接后继;只有第一个数据元素么没有直接前趋,而最后一个数据元素没有直接后继。

线性表示一个比较灵活的数据结构,它的长度根据需要增长或缩短,也可以是对线性表的数据元素进行不同的操作(如访问数据元素,插入、删除数据元素等)。

一般对线性表的操作有:get(), set(), remove(), add(), size(), contains(), index()等

 

顺序表

顺序表示计算机内存中以数组的形式保存的线性表,是指用一组地址点许的存储单元依次存储数据元素的线性结构。

 

链表

链表(linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(pointer)。

由于不必按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表 顺序表 快得多; 但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而 顺序表相应的时间复杂度分别是O(logn) 和O(1)。

使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了节点的指针域,空间开销比较大。

 

单向链表

链表中最简单的一种是单向链表,它包含两个域:信息域和指针域。如图2-4:

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-16-%e4%b8%8b%e5%8d%8810-04-52

(data是数据域,存放数据元素的值;next是指针域,存放相邻的下一个节点的地址。)

每个节点只有一个指针的链表即为单向链表,或者单链表。单向链表只可向一个方向遍历。

 

双向链表

双向链表每个节点有两个指针,如图2-11:

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-16-%e4%b8%8b%e5%8d%8810-03-56

双向链表中不仅有指向后一个节点的指针,还要指向前一个节点的指针。这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。
一般在需要大批量的另外存储数据在链表中的位置的时候用。

 

循环链表

在一个循环链表中,首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。
循环链表中第一个节点之前就是最后一个节点,反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-16-%e4%b8%8b%e5%8d%8810-03-46

顺序表和链表的比较

线性表的存储有两种:顺序存储表和链式存储表。具体存储方式可根据具体问题的要求和性质决定。

在实际应用中,考虑何种存储结构,主要从以下两个方面考虑:
1. 基于空间的考虑
顺序表的存储空间是静态分配的,在程序执行之前一般必须明确规定它的存储规模。
若线性表的长度n变化较大,则存储规模难于预先确定。
因此,在线性表的长度变化较大,难以估计其存储规模时,以采用动态链表作为存储结构为好;
反之如果存储规模比较小,并且线性表的长度一般固定时,可使用顺序存储。
2. 基于时间的考虑
顺序表时由向量实现的,它是一种随机存取结构,对表中任一结点都可在O(1)世界内直接地存取,
而链表中的结点需顺序存取,应从头指针其顺着链指针扫描结点才能获得。
因此,若 对线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表的存储结构比较好。
反之,如果在线性表中需要做较多的插入和删除,应采用链式存储。

 

数组

数组是数据结构的基本形式,它是一种顺序式的结构。数组是存储统一类型数据的数据结。

使用数组是需要定义数组的大小和存储数据的数据类型。

数组分为一维数组和多维数组。

 

一维数组

一维数组是指下标的个数只有一个的数组,有时称为向量,是最基本的数据类型。

 

多维数组

 

广义表

广义表是线性表的扩展,具体定义为n(n>=0)个元素的有限集合。其中元素又一下两种类型:

  • 一个原子元素(指不可再分的元素)
  • 一个可以再分的元素(或称为一个子表)

如果所有元素都是原子元素,则称为线性表,如果含有子表,则是广义表。n的值是广义表的长度,如果n=0,称广义表为空表。

 

常见的广义表为:

A=();  B=(());  C=(alb);  D=(A,B,C);   E=(a,E)

广义表中含有元素的个数称为广义表的长度,广义表中含有的括号对数称为广义表的深度。

从上述定义和例子可推出列表的3歌重要结论:

  1. 列表的元素可以是子表,而子表的元素还可以是子子表…由此,列表是一个多层次的结构。
  2. 列表可为其他列表所共享。如列表D可以直接引用其他列表。
  3. 列表可以是一个递归的表,即列表也可以是其本身的一个子表。如E。

 

广义表的存储

广义表的存储方法有很多种,一般采用链表存储。采用链表存储是的节点存储的逻辑结构如图4-2:

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-25-%e4%b8%8a%e5%8d%8810-27-30

其中flag表示标志位,当flag为0时,该节点表示原子元素,当flag为1时,该节点表示子表;当flag为0时,info表示元素元组的值,当flag为1时,info表示指针,指向该子表的第一个结点;link表示指针,指向广义表的下一个元素。

 

 

References:

《数据结构与算法分析–java语言描述》

wikipedia

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注