第
1 
章

概
述


【知识结构图】
第1章知识结构参见图1-1。


图1-1 知识结构图

【学习要点】
本章知识点包括三条主线:①编程环境,包括高级语言基础语法;②数据结构,包括相
关基本概念及含义;③算法,包括算法的基本概念、描述方法及时间复杂度的分析方法。
学习数据结构主要抓住两个方面:逻辑结构和存储结构,需重点把握两者之间的关系。
学习算法以基本概念和特性为基本点,重点是算法效率分析。

1.1 编程环境
1.1 
Jva编程环境
1.a
Java的开发工具很多,而且各有优缺点。目前,比较流行的Java开发工具有EditPlus、
Jcreator、Eclipse、MyEclipse、Jbuilder、NetBeans等,本书使用的开发工具为MyEclipse。
MyEclipse是一个非常优秀的用于开发Java、J2EE 的Eclipse插件集合,功能强大,支
持的开发工具十分广泛,例如JavaServlet、AJAX 、JSP 、JSF 、Struts、Spring、Hibernate、


数据结构(从概念到Java 实现)

EJB3 、JDBC数据库链接工具等,几乎囊括了目前所有的主流开源产品。图1-2为
MyEclipse2013的编辑界面。


图1-2 MyEclipse2013的编辑界面
在进行实验时,启动MyEclipse后要进行以下几步准备工作。

(1)新建JavaProject,如图1-3所示,输入Projectname 。
图1-3 新建JavaProject 

【本书命令规则】第1章实验项目名命名为Chapter01,第2章实验项目名命名为

Chater02,以此类推。p(2)新建JavaPackage,如图1-4所示,输入Packagename 。
【本书命令规则】第1章第一个实验包命名为cgdg.第二个实验包命名为

om.lsy1_1, 
com.ls2;第2章第一个实验包命名为com.ls1,第二个实验包命名为com.

gdg.y1gdg.y2_
gdls_2,以(_) 此类推。

g.y2

(3)新建JavaInterface,如图1-5所示;或新建JavaClas,如图1-6所示。

第
1 
章
概述003 


图1-4 新建JavaPackage 


图1-5 新建JavaInterface 

1.2 
C++编程环境
1.
C++的开发工具很多,而且各有优缺点。目前,比较流行的C++开发工具有kDevelop、
AnjutaDevstudio、codeblock、Visual-MigGW 、Ideone、EclipseCDT 、Compiler、Codelite、
NetbeansC++、DevC++、Ultimate++、DigitalMars、C-Fre
、TinyCCompiler、VisualStudio 
等。本书使用的开发工具为VisualStudio2015 。

VisualStudio2015是一款由开发人员工作效率工具、云服务和扩展组成的集成套件, 
适用于Web、Windows商店、桌面、Android和iOS的应用程序和游戏。图1-7为Visual 
Studio2015的新建项目界面。


数据结构(从概念到Java 实现)


图1-6 新建JavaClas 


图1-7 新建项目


第
1 
章
概述005 

在进行C+
+ 
实验时,启动VisualStudio2015(以下简称VS2015)后,可以通过建立
Win32 控制台应用程序来调试C++程序。

(1)单击VS2015 的“文件”→“新建”→“项目”,如图1-7所示。
(2)选择VisualC++→“Win32 控制台应用程序”,输入相应的应用程序名称和应用程
序位置,单击“确定”按钮,如图1-8所示。
图1-8 选择Win32 控制台应用程序

(3)进入程序向导,单击“下一步”按钮,如图1-9所示。
图1-9 应用程序向导


数据结构(从概念到Java 实现)

(4)选择控制台应用程序和空项目,如图1-10所示。
图1-10 选择应用程序类型

(5)在完成上面的步骤后,在右边的“解决方案管理器”中选择“源文件”,右击选择“添
加”→“新建项”,如图1-11所示。
图1-11 新建源文件

(6)选择“C++文件(.pp)”,单击“添加”按钮,如图112所示。
c


第
1 
章
概述007 


图1-12 新建C++文件

(7)打开应用程序开发界面,可以编写代码,如图1-13 所示。
图1-13 打开应用程序开发界面

(8)编写好代码后,单击调试按钮或者按Ctrl+F5 组合键进行调试。

数据结构(从概念到Java 实现)

008 

1.2 数据结构
数据结构是一门研究非数值计算的程序设计问题的操作对象,以及它们之间的关系和
操作等相关问题的学科。1968年美国教授高德纳(DoadE.uh) 计算机程序设计艺

nlKnt在《

术》第一卷《基本算法》中系统地阐述了数据的逻辑结构和存储结构及其操作,开创了数据结

构课程体系。同年,数据结构作为一门独立的课程,在计算机科学的课程体系中开始出现。

数据结构对于程序设计来说非常重要,占据重要地位。

程序设计=数据结构+算法

1.1 
基本概念
2.
1.数据
数据是所有能被输入计算机中,且能被计算机处理的符号的总称,如实数、整数、字符
(串)、图形和声音等。数据是计算机操作对象的集合。数据不仅包括整型、浮点型这些数值
型数据,还包括声音、视频、图像等多媒体数据。

2.数据元素
数据元素是数据(集合)中的一个“个体”,是数据结构中讨论的基本单位,不同场合也叫
结点、顶点、记录。比如,在人类中数据元素是人,禽类的数据元素有猪、牛、马、羊等。

3.数据项
数据项是数据结构中讨论的最小单位,不可再分割,一个数据元素由若干个数据项组
成。比如,人这个数据元素,可以包括眼、鼻、嘴、耳等数据项,也可以包括姓名、年龄、性别等
数据项。

4.数据对象
数据对象是性质相同的数据元素的集合,是数据的子集。在某些场合,将数据对象简称
为数据。
如表1-1所示,学生成绩表是一个数据对象,表中的一行称为数据元素,表中的一列称
为数据项。

表1-
1 
学生成绩表

学号姓名高等数学计算机导论大学英语
201900 张三90 56 89 
201900 李四80 87 67 
201900 丁一67 67 87 
201900 马二98 90 67 
201900 王五56 87 68 

5.数据结构
数据结构是相互之间存在一种或多种关系的数据元素的集合。在计算机中,数据元素


第1 章
概述009 
之间存在的一种或多种特定关系,也就是数据的组织形式。按照视点的不同,把数据结构分
为逻辑结构和存储结构,逻辑结构是面向问题的,而存储结构是面向计算机的。
数据结构可用二元组形式定义为: 
Data_Structures=(D, R) 
其中,D是数据元素的有限集合,R是D上关系的有限集合。
1.2.2 逻辑结构
数据的逻辑结构是指各个数据元素之间的逻辑关系,是呈现在用户面前的、能感知到的
数据元素的组织形式。它与数据的存储无关,是独立于计算机的。按照数据元素之间的逻
辑关系可将数据结构划分为线性结构和非线性结构两大类,非线性结构又分为树结构、图结
构和集合结构,如图1-14所示。
1.线性结构
线性结构中数据元素之间存在“一对一”的关系,即如果结构非空,则有且仅有一个首结
点和尾结点,首结点没有前驱但有一个后继结点,尾结点没有后继但有一个前驱结点,其余
结点有且仅有一个前驱和一个后继结点,如图1-15所示。
图1-14 逻辑结构 
图1-15 线性结构
2.树结构
树结构中数据元素之间存在“一对多”的关系,即如果结构非空,则有一个根结点,该结
点没有前驱结点,其余结点有且仅有一个前驱,所有结点都可以有多个后继结点,如图1-16 
所示。
图1-16 树结构

数数数数据据据据据结结结结结构构构构构(((((从从从从从概概概概概念念念念念到到到到到JJJJJaaaaavvvvvaaaaa实实实实实现现现现现))))
0103.图结构
图结构中数据元素之间存在“多对多”的关系,即如果结构非空,则任何结点都可以有任
意个前驱和后继,如图1-17所示。
4.集合结构
集合结构中数据元素之间是一种松散的关系,元素之间除了“同属于一个集合”之外无
其他关系,如图1-18所示。
图1-17 图结构图1-18 集合结构
1.2.3存储结构
存储结构也称物理结构,是逻辑结构在计算机中的表示,即逻辑结构在存储器中的实
现,依赖于计算机。基本的存储结构有顺序存储结构和链式存储结构两种。另外,还有索引
存储结构和哈希存储结构两种。
1.顺序存储结构
顺序存储结构以相对的存储位置来表示数据元素之间的逻辑关系,逻辑位置关系与存
图1-19 顺序存储结构
储位置关系是一致的。如图1-19所示,a1 是a0 的
后继结点,是a2 的前驱结点。
这种结构的主要特点:所有元素存放在一片
连续的存储单元中,整个存储结构中只含数据元
素值本身的信息。
在程序设计语言中,数组就是这样的存储结构。例如,当要建立一个长度为6的整型数
组时,计算机就在按照一个整型所占的空间大小乘以6,在内存中开辟一段空的连续的地址
空间,第一个数据元素存入第一个位置,第二个元素存入第二个位置,依次存放所有的元素。
2.链式存储结构
链式存储结构以附加信息(指针)表示后继关系,即每个结点除了存储数据元素值本身
之外,还需存储表示逻辑关系的指针。这种结构的主要特点:所有元素存放在可以不连续
的存储单元中,逻辑上相邻的元素其存储位置不一定相邻,如图1-20所示,其中h表示头
指针。
图1-20 链式存储结构