数据结构基本概念与算法评价(数据结构基本概念和术语)

导语：数据结构基本概念

一、什么是数据结构

1、用计算机解决一个具体问题的步骤

（1）分析问题，确定数据模型。

（2）设计相应的算法。

（3）编写程序，运行并调试程序直至得到正确的结果。

2、需要从数据入手来分析并得到解决问题的方法

（1）结构化数据：

数据：是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。

数据元素：是数据的基本单位（例如，A班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理

数据项：是具有独立含义的数据最小单位，也称为成员或域（例如，A班中每个数据元素即学生记录是由学号、姓名、性别和班号等数据项组成）。

（2）数据对象

数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。

如大写字母数据对象是集合C={&39;，&39;，&39;，…，&39;}；1～100的整数数据对象是集合N={1，2，…，100}。

注：默认情况下，数据结构中的数据都指的是数据对象。

（3）数据结构

数据结构是指所涉及的数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。可时把数据结构看成是带结构的数据元素的集合。

（4）数据元素之间的关系 结构,现实世界的结构是纷繁复杂的

数据结构中讨论的元素关系主要是指相邻关系或邻接关系。

（5）一个数据结构的几个方面：

数据元素之间的逻辑关系：数据的逻辑结构。

数据元素及其关系在计算机存储器中的存储方式：数据的存储结构（或物理结构）。

施加在该数据上的操作：数据运算。

二、数据的逻辑结构

数据的逻辑结构是面向用户的，它反映数据元素之间的逻辑关系而不是物理关系。

数据的逻辑结构是独立于计算机的。

（1）由于数据逻辑结构是面向用户的，可以采用表格、图等用户容易理解的形式表示。

（2）二元组

为了更通用地描述数据的逻辑结构，通常采用二元组表示数据的逻辑结构，一个二元组如下：

B=(D，R)

其中，B是一种逻辑数据结构，D是数据元素的集合，在D上数据元素之间可能存在多种关系，R是所有关系的集合。即：

D={di | 0≤i≤n-1，n≥0}

R={rj | 1≤j≤m，m≥0}

例：R={rj | 1≤j≤m，m≥0}

R中的某个关系rj（1≤j≤m）是序偶（将两个元素 x,y 有顺序地放在一起构成一个组合(x,y)称为序偶）的集合。

对于rj中的任一序偶<x，y>（x，y∈D），把x叫做序偶的第一元素，把y叫做序偶的第二元素，又称序偶的第一元素为第二元素的前驱元素，称第二元素为第一元素的后继元素。如在<x，y>的序偶中，x为y的前驱元素，而y为x的后继元素。

若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。

对于对称序偶，即满足这样的条件：若<x，y>∈r（r∈R），则<y，x>∈r（x，y∈D），可用圆括号代替尖括号，即(x，y)∈r。

（3）集合

集合：结构中数据元素之间除了的关系外，没有其他关系，与数学中的集合概念相同。

（4）线性结构

线性结构：若结构是非空的，则有且仅有一个开始元素和终端元素，并且所有元素最多只有一个前驱元素和一个后继元素。

（5）树形结构

树形结构：若结构是非空的，则有且仅有一个元素为开始元素（也称为根结点），可以有多个终端元素，每个元素有零个或多个后继元素，除开始元素外每个元素有且仅有一个前驱元素。

（6）图形结构

图形结构：若结构是非空的，则每个元素可以有多个前驱元素和多个后继元素。

三、数据的存储结构

（1）数据在计算机存储器中的存储方式就是存储结构。它是面向程序员的。

设计存储结构的这种映射应满足两个要求：

存储所有元素、存储数据元素间的关系

（2）在软件开发中，人们设计了各种存储结构。归纳为4种基本的存储结构。

顺序存储结构、链式存储结构、索引存储结构、哈希（散列）存储结构

练1：如下图，利用擅长的语言编写学生类。

该存储称为顺序存储结构，结构的特性是：

所有元素存放在一片地址连续的存储单元中。

逻辑上相邻的元素在物理位置上也是相邻的，所以不需要额外空间表示元素之间的逻辑关系。

练2：

如下图，利用擅长的语言编写学生类。

该存储称为链式存储结构，结构的特性是：

数据元素存放在任意的存储单元中，这组存储单元可以是连续的，也可以是不连续的。

通过指针域来反映数据元素的逻辑关系。

四、数据的运算

（1）将数据存放在计算机中的目的是为了实现一种或多种运算。

运算包括功能描述（或运算功能）和功能实现（或运算实现）。

前者是基于逻辑结构的，是用户定义的，是抽象的。后者是基于存储结构的，是程序员用计算机语言或伪码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。

例如，对于高等数学成绩表这种数据结构，可以进行一系列的运算：

增加一个学生成绩记录、删除一个学生成绩记录、求所有学生的平均分、查找序号为i的学生分数等。

（2）同一运算，在不同存储结构中的实现过程是不同的。

练习：查找序号为i的学生分数，利用自己擅长的语言完成

其本身就是运算的功能描述。但在顺序存储结构和链式存储结构中的实现过程不同的。

注：

同一逻辑结构可以对应多种存储结构。

同样的运算，在不同的存储结构中，其实现过程是不同的。

五、数据类型

（1）数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称

（2）数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。

（3）在程序设计语言提供的数据类型支持下，就可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。

（4）抽象数据类型（ADT）

指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。

抽象数据类型 = 逻辑结构 ＋ 抽象运算

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小萱创作整理编辑！