软件课件：数据结构new.pptVIP

* 第一章 数据结构 　主要内容 ● 数据结构的基本概念 ● 线性结构 ● 非线性结构 ● 查找与排序 1.1数据结构的基本概念 　　1.1.1 什么是数据结构 　　1. 数据结构产生的背景 　　从46年第一台计算机问世到60年代，程序设计一直采用个体或作坊式生产方式，程序设计完全凭个人的经验和技艺，工作效率低，程序可靠性差，正确性得不到保正，这种设计方式 最终导致“软件危机”出现。 　　“危机”震撼了软件界，迫使计算机界回过头来重新考虑程序设计中一些最基本的问题。例如，程序的基本成分是什么？应该用什么方法来设计程序？程序设计方法和技术如何规范和工程化等。直到1968年，相继提出了“结构程序设计”和“软件工程”概念。 　　从结构程序设计到软件工程这个概念的提出，使完全凭个人经验和技艺的程序设计变为一门科学。它要求程序设计人员不但要掌握程序设计方法和一般的程序设计技巧，而且还要研究程序加工的对象，研究数据的特性以及数据之间存在的关系。从而促进了数据结构这门学科的形成和发展。 　　2.什么是数据结构 　　定义：数据结构是由若干数据成分按照一定方式构成的复合数据以及作用于其上的函数或运算。 　　数据结构主要讨论计算机系统中数据的组织形式及其相互关系。其中： 　　数据--包括数值、字母字符、程序段、图形图象、语言等数据信息。 　　数据基本单位--数据元素 或称为数据结点 。 　　结构--指数据元素间的相互关系和约束。 用对数据元素的一些运算表示 　　3.数据结构研究的内容 　　●数据元素之间的逻辑关系是什么？ 　　●适宜选用什么样的存储结构？ 　　●采用什么样的算法访问数据结构效率更高？　　 1.1.2 数据结构中的基本概念 　　数据结构包含三个含义： 　　数据的逻辑结构； 　　数据的存储结构； 　　对数据结构的操作。 　　1.数据的逻辑结构 　　数据的逻辑结构就是人们思维中的、能够看到的数据的结构。研究数据逻辑结构的目的是为了让用户使用更方便。 　　数据逻辑结构分为两大类：线性结构和非线性结构。 　　①线性结构 　　逻辑特征：有且仅有一个开始数据元素和一个终点数据元素，并且所有数据元素都最多只有一个直接前趋和一个直接后继。如下图。 0001 0002 0004 0003 0005 　　②非线性结构 　　逻辑特征：该结构中一个数据元素可能有多个直接前趋和直接后继。 　　树的逻辑特征： 　　?有且仅有一个根元素，且无直接前趋； 　　?除根元素之外，其它元素有且仅有一个直接前趋。可有几个直接后继 　　?除根元素之外，所有其它数据元素都存在一条到根元素到路径。 “图”是其最一般的结构实例 见图 ； “树”是较特殊的结构 见图 。 　　2.数据的存储结构 　　?什么是数据的存储结构： 　　即数据在存储器中的存储形式，也称为数据的物理结构，是数据逻辑结构在存储器中的映象，一般人们是看不到的。 　　?研究数据存储结构的目的： 　　寻找一种既节省存储空间、对数据的存取及处理速度又快的结构形式。 　　?数据存储结构分类： 　　顺序存储结构、链接存储结构、索引存储结构、散列存储结构。 　　⑴顺序存储方法—顺序存储结构 　　把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，元素间的逻辑关系由存储单元的邻接关系体现，即为数据的顺序存储结构。 　　顺序存储结构主要适用于线性数据结构，如线性表、数组等，如图。 L K K+L K+ i-1 L Di地址＝K+ i-1 ×L D1 D2 Dn …… Di …… 　　主要优点：可随机直接存取、删除数据元素。 　　主要缺点： L K K+L K+iL Di地址＝K+i×L D0 D1 Dn …… Di …… 　　①建立这种结构时需要提供元素的最大个数，不方便，而且一旦建立， 长度就不能改变，不能适应动态数据增长的需要； 　　②空间利用率低，平均有一半的空间不能利用； 　　③在插入删除元素时，都需要移动大量元素，降低了访问速度。 　　因此，当数据量不大且可预计时采用这种结构较好。 　　⑵链接存储方法—链接存储结构 　　把逻辑上相邻的数据元素存储在物理位置上不相邻的存储单元里，元素间的逻辑关系由存储单元中的指针来体现，此即数据的链接存储结构—链表。又分为单向链表和双向链表。 data next 　　用于存储数据元素的存储单元分为两部分：其一用于存储数据元素的数据域 data ，另一部分为指针域。 　　●单向链表 　　如果数据元素的指针域中只有指向后继元素的指针 next ，则这种链表一般称为单向链表。如图。 K M N X Y M N X Y D1 D2 D3 D4 ^ D5 　　●双向链表　为方便插入删除操作，往往需要建立双向链接结构, 链中每一个结点都包括三部分，即用于存储数据元素的数据域 data 、指向后继