第 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 链式存储结构