数据结构大纲

《数据结构大纲》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、〔据结构大纲第1章数据结构概述数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构主要有三个方面的内容：数据的逻辑结构、数据的存储结构和对数据的算法。逻辑结构：反映数裾之叫的逻辑关系，是对数裾之间关系的描述，主要科集合、线性表、树、图等四种结构。a.集合结构。集合是元素关系极为松散的一种结构。b.线性结构。线性结构的逻辑特征是：若结构是非空集，则有JJ.仅有一个开始结点和一个终端结点，并.II所有结点都最多只有一个直接前驱和一个直接后继。是一对一的关系。c.树型结构。该结构的数据元素之间存在着一对多的关系。d.图

2、型结构。该结构的数据元素之间存在着多对多的关系，图型结构也称作网状结构。物理结构：反映数裾在计算机A部的存储安排，是数裾结构在计算机屮的实现方法。主要冇顺序、链接、散列、索引等四种葙木存储结构，并可以根裾需要组合成艽它更复杂的结构。算法：数裾进行处理的方法。践性猪构线性表栈非践性结构材形猪相用图表示为：教据猪构的三个方面：教据的送辑猪构形猪相教据的存倚猪构瓶序存•味链式存俄教提的运箅：检索、徘序、插入、删除、修改夺算法：简单地说就足解决特定问题的方法。足对问题求解过程的一种描述。当一个算法设计好还需要对R进行效率分析，以确定一个算法的优劣。评价算法的性能川吋间

3、复杂度与空间复杂度來度量。第2章线性表1.线性表的逻辑特点：线性表(Linearlist)是最简单且最常用的一种数据结构。这种结构具奋下列特点：存在一个唯一的没柯前驱的(头)数裾元素；存在一个唯一的没有n•继的(尾)数裾元素；此外，每一个数据元素均冇一个直接前驱和一个直接后继数据元素。线性表L是n(n^O)个具有相同属性的数据元素ai,a2,a3,an组成的有限序列,其中序列中元素的个数n称为线性表的长度。当n=0吋称为空表，即不含旮任何元素。常常将非空的线性表(n>0)记作：(al，a2，—3n)这里的数据元素只是一个抽象的符号，其具体含义在不同的情况F可以

4、不同。2.线性表的存储方式：顺序存储和链式存储线性表的顺序存储足指在内存屮川一块地址连续的存储空间按顺序存储线性表的各个数裾元素。采用顺序存储结构的线性表称为顺序表。顺序农具合以卜W个基本特点：(1)线性表的所有元素所占的存储空间足连续的。(2)线性表巾各数裾元素在存储空间巾是按逻辑顺序依次存放的。由于线性表的所有数据元素属于M—数据类型，所以每个元素在存储器中占用的空间(字节数)相同。因此，要在此结构屮杏找某一个元素是很方便的，即从要知道顺序表首地址和每个数裾元素在内存所占字节的大小，就可求出第i个数据元素的地址，这说明顺序表具冇按数据元素的序号随机存取的特

5、点。线性表的顺序存储结构巾任意数据元素的存储地址可山公式且接导出，因此顺序存储结构的线性表是可以随机存取K中的任意元素。但是，顺序存储结构也柯一些不方便之处，主要表现在：(1)数拋元素最人个数需预先确定，使得商级程序设计语言编译系统需预先分配相成的存储空间；(2)插入与删除运算的效率很低。为了保持线性表屮的数裾元素顺序，在插入操作和删除操作时志移动大fi数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提髙。（3）存储空间不便r扩充。当一个线性衷分配顺序存储空间后，荇线性表的存储空间已满,但还需要插入新的元素，则会发生"上溢"错误。线性表的链式存储

6、结构就足川一组任意的存储单元（可以足不连续的）存储线性表的数据元素。对线性表屮的每一个数裾元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放过接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。链式存储方式可用于表示线性结构，也可用于表示非线性结构。链式存储结构是利川任意的存储单元來存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。木章介绍了线性表的逻辑结构及它的两种存储结构:顺序表和链表。这两种表各行短长，在实际应川中应根据问题的要求和性质來选择使川。通过前而的w论吋知：顺序存储冇三个优点：♦

7、方法简单，各种高级语言中都冇数组，容易实现；今不用为表示结点问的逻辑关系而增加额外的存储开销；今具有按元素序号随机访问的特点。但它也冇两大缺点：今在顺序表中做插入/删除操作时，平均移动大约表中一半的元素，因此当n较人吋顺序表的操作效率低。今需耍预先分配足够大的存储空间。荇估计过大，容易导致顺序表后部大S闲置；预先分配过小，乂会造成溢ili。链表的优缺点恰好与顺序表相反。许实际中究竟怎样选取合适的存储结构？通常可考虑以卩几点：1.基于空间的考虑顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。芯线性表长度n变化较大，则存储规模很难预先汜确估计。

8、佔计人大将造成空间浪费，佔计太小又将使