数据结构的基本概念

《数据结构的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前言数据结构是计算机系的专业基础课，它不但是计算机学科的理论基础之一，也是软件开发的必备基础。因此，无论是从事计算机行业，还是希望在计算机方面继续深造，都应该学好这门课程。1第1章数据结构的基本概念抽象数据类型和算法描述抽象和实现术语和概念抽象数据类型算法与伪码程序结构化与设计风格程序分析的方法时间复杂性分析渐进式表示法递归式的复杂性计算21.1抽象和实现什么是抽象和实现？抽象是信息隐蔽的方法，用这种方法将数据表示或处理过程中的细节对不需要（或不想）了解的人隐藏起来。实现是已屏蔽掉的繁琐的细节。31.1.1数和变量平时使用的

2、数据类型中哪些是抽象出来的？整型、实型、字符型、枚举型等。抽象出来的数据类型是怎样实现处理过程的？各种计算机语言的编译程序有它们各自所抽象出来的数据类型与计算机自身的数值进制有相应的转换规则，也能够对其进行存储和计算。变量是抽象的吗？其作用是什么？变量是一种抽象。它的作用是减少程序设计人员对内存细节的考虑，而将主要精力用于程序算法的编写。41.1.2两维数组计算机存储是按一维方式还是二维方式？计算机存储区是按字节或字的一维或线性序列方式进行编址。计算机是如何解释带有二维数组的语句的？通过编译程序。二维数组的应用矩阵51.1.

3、3过程和抽象过程是什么？过程是程序设计的基本工具和方法，它将操作符和操作对象的概念一般化，使程序员不受程序设计语言提供的基本数据类型和操作符的约束，可以利用过程自由地定义操作数和操作方法。过程的优点利用过程的优点在于信息的隐蔽和模块化，它实现了对算法的若干部分的封装。抽象都是程序设计语言提供的吗？过程是一种抽象吗？61.2术语和概念1.2.1数据、数据元素和数据对象数据就是指所有能被输入到计算机中，且被计算机处理的符号的集合，它也是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。注意：数据的范围是随着计算

4、机的发展而不断扩大的。数据元素是数据中的一个个体，是数据结构中讨论的基本单位。一个数据元素还可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库表(关系式数据库)中，一个记录可称为一条数据，每一个字段可称为一个数据元素，而每个字段的组成部分可称为一个数据项(例如出生日期中的年、月、日)。数据对象是性质相同的数据元素的集合，是数据的一个子集。71.2.2数据类型在用高级语言编写的程序中，必须对程序中出现的每个变量、常量和表达式，明确说明它们所属的数据类

5、型。数据类型是程序设计语言中对于给定变量的所有可能取值的集合。数据类型是一个值的集合和定义在此集合上的一组操作的总称。每一个对象仅由单值构成的类型称为标量类型或原子类型。每一个对象可由一组值构成的类型称为组合类型或结构类型（有时也称为数据结构）81.2.3抽象数据类型抽象数据类型(abstractdatatype简称ADT)是一种数据类型及在这个类型上定义的一组合法的操作。程序设计语言提供的ADT定义工具Ada提供包、c++提供类使用ADT的作用减少程序的复杂性91.2.4数据结构(带结构的数据元素的集合)定义：数据结构是

6、以某种方式联系在一起的数据元素的集合。数据结构研究的内容数据结构研究的是数据元素之间抽象化的相互关系及这种关系在计算机中的存储表示，对每种结构定义各自的运算，设计出相应的算法，并用某种语言实现该算法。数据结构包含的内容：逻辑结构和物理结构，甚至包括对数据的操作。数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。数据的物理结构又称为数据的存储结构，是指数据在计算机内的表示方法，即存储形式。10比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又

7、包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢?对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。常见的逻辑结构有：线性结构、树形结构、图状结构和集合结构。11存储结构是逻辑结构在存储器中的映像。数据元素的映像方法：用二进制位(bit)的位串表示数据元素。(320)10=(501)8=(101000001)2(A)=(101)8=(001000001)2关系的映像方法（表

8、示的方法）顺序映像：以存储位置的相邻表示后继关系。Y的存储位置和X的存储位置之间相差一个常量C，而C是一个隐含值（与数据在内存中占据的宽度有关），整个存储结构中只含数据元素本身的信息。12链式映像：以附加信息(指针)表示后继关系需要一个和X在一起的附加信息指示Y的存储位置。在不同