数据结构第一章.

数据结构（C语言版）2019/12/292开设本课程的必要性以及课程的特点：1.重要的专业技术基础课编写好的程序有两方面要求：用合适的算法来设计程序的流程采用简洁适用的数据结构来表示程序中的数据和变量《数据结构》包含了以上两方面的概念。2.以“程序设计语言”的相关知识为基础3.实践性强2019/12/293第一章绪论为什么要学数据结构数据结构的主要内容如何学习2019/12/2941.1什么是数据结构数据结构：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。1.研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储器内的存储方式。3.研究如何在数据的各种结构（逻辑的和物理的）的基础上对数据实施一系列有效的基本操作。逻辑结构存储结构算法数据结构课程研究的主要内容2019/12/2951.1什么是数据结构例1：图书馆的书目检索系统自动化问题。建立一个按图书编号顺序排列的书目文件，以及分别按书名、作者名、分类号等顺序排列的索引表。图书目录文件示例按登录号顺序排列的书目文件登录号书名作者分类号………001高等数学樊映川S01……002理论力学罗运祥L01……003高等数学华罗庚S01……004线性代数栾汝书S02………………………………高等数学001，003，…理论力学002，…线性代数004，……………樊映川001，…华罗庚003，…栾汝书004，……………L002，…S001，003，……………按书名顺序排列的索引表按作者名顺序排列的索引表按分类号顺序排列的索引表2019/12/2971.1什么是数据结构计算机处理的对象：目录卡片上的书目信息（登录号、书名、作者名、分类号、出版单位和出版时间等）计算机的主要操作：按照某个特定要求对书目文件进行查询在这种模型中，对象之间是简单的线性关系，称谓线性的数据结构。2019/12/2982019/12/2991.1什么是数据结构例2：计算机和人对弈问题。假设井字棋由两人对弈，棋盘为3×3的方格。当一方三个棋子占同一行、或同一列、或同对角线便为取胜方。计算机处理的对象：对弈过程中可能出现的棋盘状态--------格局井字棋对弈“树”………………………………∶∶∶2019/12/29111.1什么是数据结构“树根”是对弈开始时的棋盘格局，所有的“叶子”是可能出现的结局，对弈过程就是从树根沿树叉到某个叶子的过程。计算机的主要操作：选择合适的格局，从树根沿树叉到能够取胜的某个叶子。“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构。2019/12/29121.1什么是数据结构例3：多叉路口交通灯的管理问题。在多叉路口设置几种颜色的交通灯才能既使车辆相互不碰撞，又能达到车辆的最大流通。计算机处理的对象：通路五叉路口交通管理示意图图中一个顶点表示一条通路，通路之间相互矛盾的关系以两个顶点之间的连线表示。在结点内用相同数字表示相同的颜色，即可同时通行ABCDEABACADBABCBDDADBDCEAEBECED11112221121112223333442019/12/29141.1什么是数据结构设置交通灯问题等价为对图的顶点染色问题，要求对图上的每一顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能少。计算机的主要操作：对表示通路的顶点进行染色通常这类交通、道路问题的数学模型是一种称谓“图”的数据结构。2019/12/29151.1什么是数据结构例4：建立最小代价通信网络。在n个城市之间建立通信网络，要求在其中任意两个城市之间都有直接的或间接的通信线路，在已知某些城市之间直接通信线路预算造价的情况下，使网络的造价最低。6v1v3v4v2v6v5651654325v1v3v4v2v6v5514322019/12/29161.1什么是数据结构综上四个例子可见，描述这类非数值计算问题的数学模型都不是用通常的数学分析的方法得到，无法用数学的公式或方程来描述，而是诸如表、树和图之类的数据结构。数据结构是研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等的学科。数据结构研究的范围：研究数据的逻辑结构和存储结构，并在这种结构上定义相关的运算，设计并实现相应的算法，分析算法的效率。2019/12/29171.1什么是数据结构数据结构在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。2019/12/29181.2基本概念和术语1.数据（Data）：描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。数值数据如：整数、实数非数值数据如：字符串、图像、声音2.数据元素（DataElement）：数据的基本单位，通常看作一个整体进行考虑和处理。在数据结构中数据元素有时称为结点（node）、记录（record）或顶点（vertex）。2019/12/29191.2基本概念和术语3.数据项（DataItem）:组成数据元素的基本单位，数据项按其是否可以划分，分为组合项和原子项。例:一条书目信息包括书名、作者名等数据项。这一完整的书目信息称为数据元素即一条书目记录，记录中的字段为数据项。书目信息出版时间作者书名年月2019/12/29201.2基本概念和术语4.关键字（Key）：数据元素中能起标识作用的数据项。例：书目信息中的登录号和书名。能起唯一识别标识作用的称为“主关键字”（简称主码）；反之称为“次关键字”（简称次码）。通常一个数据元素只有一个主码，但可以有多个次码。5.关系：指集合中元素之间的某种相关性。在集合中的元素之间可能存在一种或多种关系。教师和学生的“教学”关系，有时关系用数学符号表示，如｛＜教师，学生＞｝，｛＜丁一、乙二＞｝。在集合论中＜x,y＞表示x相对于y的“顺序”关系。2019/12/29211.2基本概念和术语6.数据对象（DataObject）：性质相同的数据元素的集合，是数据的一个子集。•Boolean＝｛false,true｝•Digit＝｛0,1,2,3,4,5,6,7,8,9｝•Letter＝｛A,B,C,…,Z,a,b,c,…z｝•NaturalNumber＝｛0,1,2,…｝•Integer＝｛0,±1,±2,±3,…｝•String＝｛a,b,…,aa,ab,ac,…｝•图书数据对象2019/12/29221.2基本概念和术语7.数据关系（DataRelation）：在数据对象中各数据元素之间存在着某种关系，反映了数据对象中数据元素所固有的一种结构。数据元素之间的任何关系都可用前驱和后继来描述。前驱和后继关系所表示的实际意义随着数据对象的不同而不同。8.结构（Structure）：数据元素之间所具有的关系。2019/12/29231.2基本概念和术语9.数据结构（DataStructure）：相互之间具有一种或多种特定关系的数据元素的集合。例：一个班的学生名单是一个接着一个排列的，可用“线性表”结构来表示。上级单位与多个下级单位的关系、父辈与子辈的关系，需要用“树结构”来表示。各城市之间的交通联系或电讯联系用“图结构”表示。数据结构包括逻辑结构和物理结构两个层次。2019/12/29241.2基本概念和术语线性结构：结构中的数据元素存在1:1的关系树形结构：结构中的数据元素存在1:M的关系图状或网状结构：结构中的数据元素存在M:M的关系数据结构的四类基本结构集合：与数学中的集合概念相同（元素之间除了“同属于一个集合”的关系外，别无其它关系）2019/12/2925数据元素之间具有的逻辑关系（结构）。线性关系（线性结构）如线性表、数组、堆栈、队列、串、文件等具有某种逻辑结构的数据在计算机存储器中的存储方式（存储映象）。顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。非线性关系（非线性结构）如树、二叉树、图等其他存储结构：索引、哈希存储结构逻辑结构物理结构1.2基本概念和术语数据结构包括逻辑结构和物理结构两个层次。2019/12/2926例:逻辑结构a1a2a3a30…d1d2d3d4…d30a2a1a3a4a30存储结构1）顺序存储结构线性结构（线性表）刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………姓名性别民族年龄其他2019/12/29272）链式存储结构…d1d2d3d4a1a2a3a30∧list…a2a1a4a3d4d1d5d32019/12/29281.2基本概念和术语10.数据结构的形式定义数据结构是一个二元组Data＿Structure＝（D,R）其中，D是数据元素的有限集合，R是D上关系的有限集。例：在计算机科学中，复数如下定义：复数是一种数据结构Complex＝(C,R)其中：C是含有两个实数的集合｛c1，c2｝;R＝｛P｝，而P是定义在集合C上的一种关系｛＜c1，c2＞｝，其中有序偶＜c1，c2＞表示c1是复数的实部，c2是复数的虚部。2019/12/29291.2基本概念和术语存储结构涉及数据元素及其关系在存储器中的物理位置，但直接使用物理位置来描述比较复杂。我们使用高级语言来讨论及描述数据结构，可以借用高级语言的“数据类型”来描述存储结构。例：用一维数组来描述顺序存储结构用指针来描述链式存储结构2019/12/29301.2基本概念和术语11.数据类型（DataType）：一个值的集合和定义在这个值集上的一组操作的总称。整型值集----某个区间上的整数操作----加、减、乘、除和取模等算术运算2019/12/29311.2基本概念和术语数据类型是数据结构在程序设计语言中的实现。按“值”的不同特性，高级程序语言中的数据类型可分为两类：原子类型：值是不可分解的。例：C语言中的基本类型(字符型、整型、浮点型、枚举型)、指针类型和空类型。结构类型：值由若干成分按某种结构组成，是可分解的，其成分可以是结构的也可以是非结构的。例：数组类型2019/12/29321.2基本概念和术语例：用C语言编程时，书目信息数据元素可定义如下：Typedefstruct｛inty;//yearintm;//Month｝datetype;//日期类型Typedefstruct｛charid［8］;//登录号charname［32］;//书名charauthor［16］;//作者datetypepdate;//出版日期｝booktype;//书目类型元素之间的关系可借用“数组”和“指针”来描述。2019/12/29331.2基本概念和术语12.抽象数据类型（AbstractDataType，简称ADT）：一个数学模型以及定义在该模型上的一组操作。仅取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。抽象数据类型可用三元组表示ADT＝（D，S，P）D是数据对象，用结点的有限集合表示；S是D上的关系的集合，用结点间的序偶的集合来表示；P是对D的基本操作的集合。2019/12/29341.2基本概念和术语本书的ADT定义格式ADT抽象数据类型名｛数据对象：＜数据对象的定义＞数据关系：＜数据关系的定义＞基本操作：＜基本操作的定义＞｝ADT抽象数据类型名基本操作的定义格式：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉例：抽象数据类型三元组的定义ADTTriplet｛数据对象D：D＝｛e1，e2，e3｜e1，e2，e3∈Element（定义了关系运算的某个集合）｝数据关系R：R1＝｛＜e1，e2＞，＜e2，e3＞｝基本操作P：InitTriplet（＆T，v1，v2，v3）操作结果：构造了三元组T，元素e1、e2和e3分别被赋以v1、v2和v3的值。DestroyTriplet（＆T）操作结果：