数据结构的基本概念和术语

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

1、第1章绪论1.1数据结构的基本概念和术语1.2算法描述工具C语言1.3算法描述与分析习题一1.1数据结构的基本概念与术语1.1.1引言在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。所谓数学模型一般指具体的代数方程等。然而，有些实际问题无法用数学方程表示。现在来分析几个这方面的典型实例，它们的主要特点是处理数据信息的存储与检索等，而不是单纯的数值计算。例如：图书档案类问题、棋类对奕问题、交通或通信网问题。表1.1学籍表首先分析图书目录卡或学籍档案类问题。设一个班级有

2、30个学生，这个班级的学籍表如表1.1所示。我们可以把每个学生的信息看成一个记录，表中的每个记录又由7个数据项组成。该学籍表由30个记录组成，记录之间是一种顺序关系。这种表通常称为线性表，数据之间的逻辑结构称为线性结构，其主要操作有检索、查找、插入或删除等。现在再来分析棋类对奕问题，与之相类似的还有体育竞技比赛问题。在体育竞技中，先从基层的预选比赛开始，获胜者再继续参加比赛，最后可以赛出一个冠军来。在此，可把预选赛的参加者看成树叶，比赛最后所产生的冠军看成一个树根，这样就形成一个树形结构。又如，可以把一所高校名称看成树根，把下设的若干个系名看成它的树

3、枝中间结点，把每个系分出若干专业方向看成树叶，这样也是一个树形结构。如图1.1所示。图1.1专业设置树中的每个结点可以包含较多的信息，结点之间的关系不再是顺序的，而是分层、分叉的树形结构。对于树结构的主要操作是遍历、查找、插入或删除等。最后分析交通或通信网问题。如果把若干个城镇看成若干个顶点，再把城镇之间的道路看成边，它们可以构成一个网状的图。如图1.2所示。图1.2交通示意图图1.2中每个顶点的信息可以代表一个城镇的主要简况，各个顶点之间的关系纵横交错更加复杂，这种关系称之为图状或网状结构。在实际应用中，假设某地区有4个城镇，有一调查小组要对该地区

4、每个城镇进行调查研究，并且每个城镇仅能调查一次，试问调查路线怎样设计才能以最高的效率完成此项工作？这就是一个图论方面的问题。交通图的存储和管理确实不属于单纯的数值计算问题，而是一种非数值的信息处理问题。一般来说数据结构就是研究一类普通数据的表示及其相关的运算操作。数据结构是一门主要研究怎样合理地组织数据、建立合适的数据结构、提高计算机执行程序所用的时间效率和空间效率的学科。1968年，美国的D.E.Knuth教授开创了数据结构的最初体系，他的名著《计算机程序设计技巧》较为系统地阐述了数据的逻辑结构和存储结构及其操作。随着计算机科学的飞速发展，到20世

5、纪80年代初期数据结构的基础研究已日臻成熟。“数据结构”是计算机专业中的一门专业基础课。它为操作系统、数据库原理、编译原理等后继专业课程的学习奠定了基础。数据结构涉及到各方面的知识，如计算机硬件范围的存储装置和存取方法；在计算机软件范围中的文件系统，数据的动态存储与管理，信息检索；数学范围的许多算法知识，还有一些综合性的知识，如编码理论、算子关系、数据类型、数据表示、数据运算、数据存取等各方面的知识。因此，数据结构是数学、计算机硬件、软件三者之间的一门核心课程。1.1.2数据结构有关概念与术语在计算机科学中，数据(data)是描述客观事物的数字、字符

6、以及所有能够输入到计算机中并被计算机处理的信息的总称。除了数字、字符之外，还有用英文、汉字或其他语种字母组成的词组、语句，以及表示图形、图像和声音等信息也可称之为数据。数据元素(dataelement)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。例如，图1.1“专业设置树”中的一个专业，图1.2“交通图”中的一个城镇都可称为一个数据元素。数据元素除了可以是一个数字或一个字符串以外，它也可以由一个或多个数据项组成。例如，表1.1中每个学生的学籍信息作为一个数据元素，在表中占一行。每个数据元素由序号、学号、姓名、性别、英语成绩等七个数据项

7、组成。数据项(dataitem)是有独立含义的数据的最小单位，数据项有时也称为字段(field)。数据对象(dataobject)是具有相同性质的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合Ｎ＝{0，±1，±2，…}，字母字符数据对象是集合C＝{'A'，'B'，…，'Z'}。本节表1.1中的学籍表也可看成一个数据对象。数据的逻辑结构(datastructure)是带有结构的数据元素的集合，它是指数据元素之间的相互关系，即数据的组织形式。我们把数据元素间的逻辑上的联系称之为数据的逻辑结构，如前文所介绍的线性结构、树形结构、图状或网状结构。

8、它体现数据元素间的抽象化相互联系，逻辑结构并不涉及数据元素在计算机中具体的存储方式，是独立于计算机的。然而，