数据结构概述

                                                                                                                                       版权归为数据结构标准教程 书籍

1.1数据结构：

计算机科学是一门研究数据表示和数据处理的科学，在利用计算机进行数据处理时，实际需要处理的数据元素一般有很多。要提高数据处理效率，节省存储空间，如何组织数据就成了关键问题。而数据结构用来反映一个数据的内部构成，即数据由哪些成分构成，以什么方式和结构构成。

1.1.1基本概念：

1.数据

数据(Date)是外部世界信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序的加工的原料。计算机程序处理各种各样的数据，可以是数值数据，如整数、实数或复数，主要用于工程计算、科学计算和商务处理等；也可以是非数值数据，如字符、文字、图形、图像、声音等。

2.数据元素和数据项

数据元素(Data Element)是数据的基本但闻，在计算机程序中通常作为一个整体进行考虑和处理。数据元素有时也被成为元素、结点、顶点、记录等。

一个数据元素可由若干个数据项(Data Item)组成。数据项是不可分割的、含有独立意义的最小数据单位。数据项有时也被称为字段(Field)或域(Domain)。例如，在数据库信息处理系统中，数据表的一条记录就是一个数据元素。这条记录中的学生学号、姓名、性别、籍贯、出生年月日、成绩等字段就是数据项。

数据项分为两种。一种叫做初等项，如学生的性别 籍贯等，在处理时不能再进行分割；另一种叫做组合项，如学生的成绩，它可以再分为数学、物理、化学等更小的项。

3.数据对象

数据对象(Data Object)是性质相同的数据元素的集合。它是数据的一个子集，具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质，属于同一数据对象，

数据元素是数据元素类的一个实例。例如，整数数据对象是{0,1,2,3,·······}，字符数据对象是{a,b,c,d,······}。在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。

4.数据类型

数据类型(Data Type)是高级程序设计语言中得概念，是数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性。程序中的每个变量、常量或表达式的结果都应该属于某种确定的数据类型。例如，C语言中的整型变量，其取值范围为某个区间上的整数(区间大小因计算机而异)，定义在其上的操作为 加 减 乘 除和取模等算数运算。

5.数据结构

简单地说，数据结构(Data Structure)是指数据与数据之间的关系。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构(Structure)。

例如，有一张学生选课表，这个表就是数据；成绩表中记录了班级每个学生选课的成绩，每个学生的姓名为一行组成一条记录。每个记录由姓名、学号、课程成绩等字段组成，每个记录就是一个结点也称为数据元素；每个字段就是数据项。姓名字段取值范围为字符型，而课程成绩字段取值为整型。学生选课成绩表的数据是一组学生成绩信息，这组信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系，按照学号升序排列。

1.1.2数据结构概念

数据结构是指互相之间存在着一种对多种关系的数据元素的集合。根据数据元素之间关系所不同的特性，通常有以下4类基本结构。

·集合结构：在集合结构中，数据元素间的关系是“属于同一个集合”。集合结构是元素关系极为松散的一种结构。

·线性结构：该结构的数据元素之间存在着一对一的关系，即一个数据元素只与另一个数据元素有关系。

·树性结构：该结构的数据元素之间存在着一对多的关系，即一个数据元素只与另外多个数据元素有关系。

·图性结构：该结构的数据元素之间存在着多对多的关系，即数据元素之间有多个关系。图形结构也称作网状结构。

如图1-1所示为上述4类基本结构的示意图。

                  图1-1 4类基本结构的示意图

说明：由于集合石数据元素之间关系极为松散的一种结果，因此也可用其他结构来表示。

从上面所介绍的数据结构的概念中可知，一个数据结构有两个要素：

一个是数据元素的集合；另一个是关系的集合。在形式上，数据结构通常可以采用一个二进组来表示，形式如下。

                   Data_Structure=(D,R)

其中，D是有限个数据元素的集合；R是D上关系的有限数据元素的集合。