【精品数据结构】绪 论

《【精品数据结构】绪 论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第一章第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求1.1什么是数据结构“数据结构”作为一门计算机专业基础课，是编译原理，操作系统，数据库等课程的基础。也是设计及实现系统程序和大型应用程序的重要基础。“数据结构”的主要内容是研究数据的逻辑结构，存储结构及对每种结构所定义的运算。程序设计的实质是数据表示和数据处理1)数据表示--把原始数据从机外表示转化为机内表示。2)数据处理--编写程序，对机内的数据进行各种操作，获得所需结

2、果。例1、职工档案管理问题工作证号姓名性别出生日期职称0001刘晓军男19491001工程师0003张　红女19650506助工0007李　华女19461118高工...............每位职工的档案由五个项目构成，所有职工的档案组成一张数据表。要管理这张表，至少可进行以下操作(运算)：查找、读取、插入、删除、更新、排序等。用计算机解决上述管理问题，设计人员要完成二项任务：第一，将档案表转化为机内表示，让计算机直接处理；——数据表示第二，编写计算机程序实现人工管理的要求。——数据处理在大多数情况下，这些数据并不是没有组织，数据之间往往具有重要的结构关系，这就是数据结

3、构的内容。那么，什么是数据结构呢？先看以下几个例子。例1：学籍管理问题：某班学生基本情况表，记录了每个学生的学号，姓名，专业，政治面貌，表中的记录是按学生的学号顺序排列的。学号姓名专业政治面貌001王丽计算机党员002孙文计算机团员003谢小军计算机团员004李辉计算机团员005刘慧计算机党员006余军计算机团员007李力计算机团员008张爱东计算机团员001003002004006005008007在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性的数据结构。线性表例2、人机对奕问题……..……..…...…...…...….

4、..树例3、多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED可见：描述这类非数值计算问题的数学模型不再是数学方程，而是线性表、树和图之类的数据结构。简言之，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。图1.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小

5、单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据对象可以是有限的，也可以是无限的。例：整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}结构（Structure):是数据之间彼此存在的相互关系。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。这种关系体现在三个方面：1、数据之间的逻辑关系2、数据在计算机内的存储方式3、数据在计算机内的运算数据的结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结

6、构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。数据结构的形式定义：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例：复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。例：5个结点的顺序表示D={d1,d2,d3,d4,d5}S=

7、{,,,}d1—d5为元素（结点），表示结点di与dj的关系.d2d3d5d1d4例：5个结点的树型表示D={d1,d2,d3,d4,d5}S={,,,}d1—d5为元素（结点），表示结点di与dj的关系.d2d3d5d1d4数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两