数据结构基本概念

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

1、数据结构的概念算法的概念和描述算法的简单分析第一章数据结构为什么要学习数据结构？什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法→数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。软件=程序+文档（软件工程的观点）电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值

2、计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述例1.1电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。非数值计算问题：例1.2田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。非数值计算问题：（1）设用如下六个不同的

3、代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。非数值计算问题----田径赛的时间安排问题解法姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操

4、作对象以及它们之间的关系和操作的学科。数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。《数据结构课程》所处的地位：什么是数据结构？几个概念：数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位

5、，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。什么是数据结构？几个概念：数据类型（DataType)：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义什么是数据结构？几个概念：抽象数据类型(AbstractDataType简称AD

6、T）抽象数据类型是用户在数据类型基础上新定义的数据类型抽象数据类型定义包括数据组成和对数据的处理操作抽象数据类型是数据和数据的使用者的一个接口抽象数据类型的三元组表示（D，S，P）D：数据对象S：D上的关系集P：对D的基本操作什么是数据结构？几个概念：抽象数据类型的定义：包括数据对象定义、数据关系定义和基本操作定义，书写格式为：ADT：抽象数据类型名{数据对象：数据对象的定义数据关系：数据逻辑关系的定义基本操作：基本操作的定义}ADT抽象数据类型名什么是数据结构？定义1----是相互之间存在一种或多种特定关系的数据元素的集合。Data_Structure=(

7、D,S)D：数据对象，S：D上的关系集。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。数据结构的三个方面的含义：逻辑结构---数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。运算（算法）数据结构的三个方面的含义之：逻辑结构---划分方法一（1）线性结构----有且仅有一个开始和一个终端结点，并且所有结

8、点都最多只有一个直接前趋和一个后继。例如：线性表、栈