零基础学数据结构第1章概述

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第1章 数据结构概述,本章重点和难点：,1、数据结构的基本概念,2、什么是抽象数据类型,3、如何计算算法的时间复杂度,1.1 为什么要学习数据结构,1数据结构的发展变迁,数据结构在计算机科学与技术专业中是一门综合性的专业基础课。在国外，数据结构作为一门独立的课程是从1968 年才开始设立的。,1968年，美国的唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。,1.1 为什么要学习数据结构,2数据结构的地位,在我国，数据结构已经不仅仅是计算机专业的核心课程，还是其他非计算机专业的主要选修课程之一。数据结构的研究不仅涉及到计算机硬件的研究范围，而且与计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,1.1 为什么要学习数据结构,开发所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂问题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构方面的有关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。,1.1 为什么要学习数据结构,在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。,学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。,1.2 基本概念和术语,1数据（data）,数据是描述客观事物的符号，能输入到计算机中并能被计算机程序处理的符号集合。它是计算机程序加工的“原料”。例如，一个文字处理程序（如Microsoft word）的处理对象就是字符串，一个数值计算程序的处理对象就是整型和浮点型数据。因此，数据的含义非常广泛，如整型、浮点型等数值类型及字符、声音、图像、视频等非数值数据都属于数据范畴。,1.2 基本概念和术语,2数据元素（data element）,数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑和处理。一个数据元素可由若干个数据项（data item）组成，数据项是数据不可分割的最小单位。例如，一个学校的教职工基本情况表包括编号、姓名、性别、籍贯、所在院系、出生年月、职称等数据项。这里的数据元素也称为记录。教职工基本情况如表1.1所示。,1.2 基本概念和术语,表1.1 教职工基本情况表,编 号,姓 名,性 别,籍 贯,所在院系,出生年月,职 称,05002,胡志刚,男,河南,化工学院,1970.10,教授,01156,张琳,女,北京,文学院,1978.08,副教授,03527,李燕,女,陕西,信息学院,1981.11,讲师,1.2 基本概念和术语,3数据对象（data object）,数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，正整数数据对象是集合N=1，2，3，字母字符数据对象是集合C=A，B，C，。,1.2 基本概念和术语,4数据结构（data structure）,数据结构即数据的组织形式，它是数据元素之间存在的一种或多种特定关系的数据元素集合。在现实世界中，任何事物都是有内在联系的，而不是孤立存在的，同样在计算机中，数据元素不是孤立的、杂乱无序的，而是具有内在联系的数据集合。例如，表1.1的教职工基本情况表是一种表结构，学校的组织机构是一种层次结构，城市之间的交通路线属于图结构，如图1.1、图1.2所示,。,1.2 基本概念和术语,1.2 基本概念和术语,5数据类型（data type）,数据类型是用来刻画一组性质相同的数据及其上的操作。数据类型是按照值的不同进行划分的。,在C语言中，按照取值的不同，数据类型还可以分为两类：原子类型和结构类型。原子类型是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型是由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据组成的，结构体类型的值也是由若干个类型范围的数据构成，它们的类型都是相同的。,1.3 数据的逻辑结构与存储结构,1.3.1 逻辑结构,数据元素之间存在4种结构类型：,（1）集合。结构中的数据元素除了同属于一个集合外，数据元素之间没有其它关系。这就像我们数学中的自然数集合，集合中的所有元素都属于该集合，除此之外，没有其它特性。例如，数学中的正整数集合5，67，978，20，123，18，集合中数除了属于正整数外，元素之间没有其它关系，数据结构中的集合关系就类似于数学中的集合。集合表示如图1.3所示。,1.3 数据的逻辑结构与存储结构,（2）线性结构。结构中的数据元素之间是一对一的关系。线性结构如图1.4所示。数据元素之间有一种先后的次序关系，a,b,c是一个线性表，其中，a是b的前驱，b是a的后继。,（3）树形结构。结构中的数据元素之间存在一种一对多的层次关系，树形结构如图1.5所示。这就像学校的组织结构图，学校下面是教学的院系、行政机构的部和处及一些研究所。,1.3 数据的逻辑结构与存储结构,（4）图结构。结构中的数据元素是多对多的关系。图1.6就是一个图结构。城市之间的交通路线图就是多对多的关系，a，b，c，d，e，f，g是7个城市，城市a和城市b、e、f都存在一条直达路线，而城市b也和a、c、f存在一条直达路线。,1.3 数据的逻辑结构与存储结构,1.3.2 存储结构,存储结构,也称为,物理结构，,指的是数据的逻辑结构在计算机中存储形式。,数据元素的存储结构形式通常有两种：顺序存储结构和链式存储结构。采用顺序存储的字符串”abcdef”的存储结构如图1.7所示。链式存储是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。字符串”abcdef”的链式存储结构如图1.8所示。,1.3 数据的逻辑结构与存储结构,数据的逻辑结构和物理结构是密切相关的，今后在学习数据结构的过程中，读者将会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。,1.4 抽象数据类型及其描述,1.4.1 什么是抽象数据类型,抽象数据类型（abstract data type，简称ADT）是描述具有某种逻辑关系的数学模型，并对在该数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与在计算机内部表示无关。计算机中的整数数据类型是一个抽象数据类型，不同的处理器可能实现方法不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。,1.4 抽象数据类型及其描述,抽象数据类型不仅包括在计算机中已经定义了的数据类型，例如整型、浮点型等，还包括用户自己定义的数据类型，例如结构体类型、类等。,一个抽象数据类型定义了一个数据对象、数据对象个数据元素之间的关系及对数据元素的操作。抽象数据类型通常是指用户定义，用来解决应用问题的数据模型，包括数据的定义和操作。例如，C+的类就是一个抽象数据类型，它包括用户类型的定义和在用户类型上的一组操作。,1.4 抽象数据类型及其描述,抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后进行建立起一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。,1.4 抽象数据类型及其描述,1.4.2 抽象数据类型的描述,本书把抽象数据类型分为两个部分来描述：数据对象集合和基本操作集合。其中，数据对象集合包括数据对象的定义及数据对象中元素之间关系的描述，基本操作集合是对数据对象的运算的描述。,数据对象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定义格式为：,基本操作名（参数表）：初始条件和操作结果描述。,1.4 抽象数据类型及其描述,例如，线性表的抽象数据类型描述如下：,1数据集合,线性表的数据对象集合为a1，a2，an，每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。,1.4 抽象数据类型及其描述,2基本操作集合,线性表的基本操作主要有：,（1）InitList(&L)：初始化操作，建立一个空的线性表L。这就像是在日常生活中，一所院校为了方便管理，建立一个教职工基本情况表，准备登记教职工信息。,（2）ListEmpty(L)：若线性表L为空，返回1，否则返回0。这就像是刚刚建立了教职工基本情况表，还没有登记教职工信息。,（3）GetElem(L,i,&e)：返回线性表L的第i个位置元素值给e。这就像在教职工基本情况表中，根据给定序号查找某个教师信息。,（4）LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功返回该元素在表中的序号表示成功，否则，返回0表示失败。这就像在教职工基本情况表中，根据给定的姓名查找教师信息。,（5）InsertList(&L,i,e)：在线性表L中的第i个位置插入新元素e。这就类似于经过招聘考试，引进了一名教师，这个教师信息被登记到教职工基本情况表中。,1.4 抽象数据类型及其描述,可能你会在大多数教材上看到线性表的抽象数据类型用以,下方式描述：,ADT List,数据对象：D=ai|aiElemSet，i=1，2，n，n0,数据关系：R=|ai-1，aiD，i=2，3，n,1.4 抽象数据类型及其描述,需要注意的是，在基本操作的描述过程中，参数传递有两种方式：一种是数值传递，另一种是引用传递。前者仅仅是将数值传递给形参，并不返回结果；后者其实是把实参的地址传递给形参，实参和形参其实是同一个变量，被调用函数通过修改该变量的值返回给调用函数，从而把结果带回。在描述算法时，通过在参数前加上&，表示引用传递，如果参数前没有&，表示是数值传递。,1.5 算法,1.5.1 数据结构与算法的关系,算法与数据结构关系密切。两者既有联系又有区别。,数据结构与算法的联系可用一个公式描述：程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的。算法的操作对象是数据结构。,1.5 算法,数据结构与算法的区别在于：数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。,1.5 算法,1.5.1 什么是算法,算法(algorithm)是解决特定问题求解步骤的描述，在计算机中表,现为有限的操作序列。操作序列包括了一组操作，每一个操作都完成,特定的功能。例如，求n个数中最大者的问题，其算法描述如下：,1定义一个变量max和一个数组a，分别用来存放最大数和数组,的元素，并假定第一个数最大，赋给max，即：,max=a0;,1.5 算法,2依次把数组a中其余的n-1个数与max进行比较，遇到较大的数时，将其赋给max。,for(i=1;in;i+),if(maxai),max=ai;,最后，max中的数就是n个数中的最大者。,1.5 算法,1.5.2 算法的五大特性,算法具有以下5个特性。,（1）,有穷性,。有穷性指的是算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。,（2）,确定性,。算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，也就是相同的输入只能有一个唯一的输出结果。,（3）,