数据结构大纲

数据结构大纲

第1章 数据结构概述

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构主要有三个方面的内容： 数据的逻辑结构、数据的存储结构和对数据的算法。

逻辑结构：反映数据之间的逻辑关系，是对数据之间关系的描述，主要有集合、线性表、树、图等四种结构。

a.集合结构。集合是元素关系极为松散的一种结构。

b.线性结构。线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。是一对一的关系。

c.树型结构。该结构的数据元素之间存在着一对多的关系。

d.图型结构。该结构的数据元素之间存在着多对多的关系，图型结构也称作网

状结构。

物理结构：反映数据在计算机内部的存储安排，是数据结构在计算机中的实现方法。 主要有顺序、链接、散列、索引等四种基本存储结构，并可以根据需要组合成其它更复杂的结构。

算法：数据进行处理的方法。

用图表示为：

算法：简单地说就是解决特定问题的方法。是对问题求解过程的一种描述。

当一个算法设计好后，还需要对其进行效率分析，以确定一个算法的优劣。评价算法的性能用时间复杂度与空间复杂度来度量。

第2章 线性表

1.

线性表的逻辑特点：

线性表（Linear list）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。

线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。 当n=0时称为空表，即不含有任何元素。 常常将非空的线性表(n>0)记作：

(a1，a2，…an)

这里的数据元素 ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 2.

线性表的存储方式：顺序存储和链式存储

线性表的顺序存储是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。采用顺序存储结构的线性表称为顺序表。

顺序表具有以下两个基本特点：

(1) 线性表的所有元素所占的存储空间是连续的。

(2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间（字节数）相同。因此，要在此结构中查找某一个元素是很方便的，即只要知道顺序表首地址和每个数据元素在内存所占字节的大小，就可求出第i个数据元素的地址，这说明顺序表具有按数据元素的序号随机存取的特点。

线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。

但是，顺序存储结构也有一些不方便之处，主要表现在：

（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；

（2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和

删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。

（3）存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。

线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。

链式存储方式可用于表示线性结构，也可用于表示非线性结构。

链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。

本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。这两种表各有短长，在实际应用中应根据问题的要求和性质来选择使用。通过前面的讨论可知：顺序存储有三个优点：

但它也有两大缺点：

链表的优缺点恰好与顺序表相反。在实际中究竟怎样选取合适的存储结构？通常可考

? 需要预先分配足够大的存储空间。若估计过大，容易导致顺序表后部大量闲置；预先分配过小，又会造成溢出。 ? 在顺序表中做插入/删除操作时，平均移动大约表中一半的元素，因此当n较大时顺序表的操作效率低。 ? 方法简单，各种高级语言中都有数组，容易实现； ? 不用为表示结点间的逻辑关系而增加额外的存储开销； ? 具有按元素序号随机访问的特点。 虑以下几点：

1．基于空间的考虑

顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。若线性表长度n变化较大，则存储规模很难预先正确估计。估计太大将造成空间浪费，估计太小又将使空间溢出机会增多。所以当对线性表的长度或存储规模难以估计时，不宜采用顺序存储结构。顺序表的存储密度为1。

链表不用事先估计存储规模，是动态分配。只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。但链表的存储密度较低。存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于1的。

2．基于时间的考虑

随机存取结构，就是对表中任一结点都可在O(1)时间内直接取得。若对线性表主要做查找，很少做插入和删除操作时，采用顺序存储结构为宜；而在链表中按序号访问的时间性能为O(n)。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。

而在顺序表中做插入、删除操作时，要平均移动表中一半的元素；尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观，这一点不应忽视。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。

3．基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，其使用受语言环境的限制，这也是用户应该考虑的因素之一。

总之，两种存储结构各有特点。选择哪种结构根据实际使用的主要因素决定。通常“较稳定”的线性表选择顺序存储结构；而插/删频繁“动态性“较强的线性表宜选择链式存储结构。

1.栈

第3章-第4章

栈与队列是两种特殊的线性结构。从数据结构角度看它们是线性表，从操作的角度看它们是操作受限的线性表。

栈(stack)是限定仅在表尾的一端进行插入或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶(top)，而另一端称为栈底(bottom)。不含元素的栈称为空栈。