数据结构第1章资料

1、数 据 结 构计算机科学与技术(jsh)学院曲立平Email： 共五十五页一、课程性质与教学(jio xu)目的 数据结构主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。 数据结构是计算机科学中一门综合性的专业基础课，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。 通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统(co zu x tn)、编译原理和数据库等课程奠定基础。7/27/20222共五十五页二、教学内容第1章 绪论第2章-第

2、5章 线性数据结构第6章树形数据结构第7章图状数据结构第9章 查找第10章排序第12章 文件(wnjin)结构7/27/20223共五十五页三、基本(jbn)要求从数据结构的逻辑结构、存储(cn ch)结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图、和文件等常用的数据结构。掌握在各种常用的数据结构上实现的排序和查找运算。对算法的时间和空间复杂性有一定的分析能力。针对简单的应用问题，应能选择合适的数据结构及设计有效的算法解决。7/27/20224共五十五页学时(xush)：课程讲授学时(xush)64 四、学分及学时(xush)分配7/27/20225共五十五页五、参考

3、书目严蔚敏等著 数据结构 清华大学出版社范策等著 算法与数据结构 机械工业出版社李春保 数据结构与习题解析(ji x) 清华大学出版社 谢楚屏等编著 数据结构 人民邮电出版社7/27/20226共五十五页六、与相关课程(kchng)的联系先修课程：高级语言程序设计(chn x sh j)（C）、离散数学后续课程：操作系统、数据库原理等7/27/20227共五十五页第一章 绪论(xln)重点和难点重点：了解有关(yugun)数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。难点：无知识点数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间

4、复杂度7/27/20228共五十五页1.1 什么(shn me)是数据结构用计算机解决一个具体的问题，需要经过以下几个步骤：从具体问题抽象出一个适当的数学模型；设计一个解此数学模型的算法；编出程序；进行测试、调整直至(zhzh)得到最终解答。寻求数学模型的实质： 分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。7/27/20229共五十五页很多问题求解最后都转化为求解数学方程或数学方程组。在房屋设计或桥梁设计中的结构应力分析计算可化解为线性代数方程组求解的问题，天天看到的天气预报，它的数学模型是一个环流模式方程。预报人口增长情况的数学模型为微分方程。当

5、计算机进入非数值(shz)计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。非数值计算问题的数学模型正是本课程要讨论(toln)的数据结构。7/27/202210共五十五页例如(lr)例1-1：图书馆的书目检索(jin su)自动化问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片7/27/202211共五十五页例如(lr)例1-1：图书馆的书目检索(jin su)自动化问题书目文件按书名按作者名按分类号索引表线性的数据结构7/27/202212共五十五页例1-2：人机对奕问题(wnt).树形的数据结构(sh j ji u)7/27/20

6、2213共五十五页例1-3：多岔路(chl)口交通灯的管理问题CEDABABACADBABCBDDADBDCEAEBECED7/27/202214共五十五页瑞士的计算机专家在1976年出版了一本书，书名为算法+数据结构 = 程序设计，它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组指令，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。简单地说，数据结构是一门讨论描述现实世界实体(sht)的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。 2.数据结构(sh j ji u)课程7/27/202215共五十

7、五页1.2 基本概念和术语(shy)数据(shj)是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机加工的“原料”。包括：图像、声音、数值、字符串等。数据元素是数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。例如：5，N，记录，格局，顶点。数据项:一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。7/27/202216共五十五页关键字能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 “主” 关键字，否则(fuz)称之为 “次” 关键字。例如：记录。数据对象是性质相同的数据元素的集合。是数据的一个子集。例如：整数数据对象是集合N=0，1，

8、2，字母字符数据对象是集合C=“A”，“B”，“Z”2数据(shj)对象、数据(shj)结构7/27/202217共五十五页数据结构相互之间存在(cnzi)一种或多种特定关系的数据元素的集合。四类基本结构：集合：数据元素间除“同属于一个集合”外，无其它关系。线性结构：数据元素间存在一个对一个的关系。树形结构：数据元素间存在一个对多个的关系。图形结构：数据元素间存在多个对多个的关系。7/27/202218共五十五页集合线性结构树形结构图状结构（网状结构）7/27/202219共五十五页数据结构的形式定义数据结构是一个二元组 Data_Structure=(D,S) 其中(qzhng)，D是数据元

9、素的有限集，S是D上关系的有限集。 例如： list=(D,R) 其中：D=1,2,3,4,5,6,7 R=,图形(txng)表示12345677/27/202220共五十五页逻辑结构对数据元素之间存在的逻辑关系的描述；可以用一个(y )数据元素的集合和定义在此集合上的若干关系表示。物理结构（存贮结构）数据逻辑结构在计算机中的表示和实现。包含数据元素的映象和关系的映象。数据元素可以用一个“位串”表示，例如，数值“321”可用位串 101000001 表示，字母“A”可用位串 001000001 表示。当数据元素由多个数据项构成时，每个数据项即为表示数据元素的位串中的一个“子位串”。7/27/2

10、02221共五十五页关系有两种表示方法：顺序存储结构 把逻辑上相邻的结点存储在物理位置上相邻的存储单元 里，结点间的逻辑关系由存储单元的邻接关系来体现。 通常顺序存储结构是借助于语言(yyn)的数组来描述的。链式存储结构 不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑 关系是由附加的指针字段表示的。 通常要借助于语言的指针类型来描述。7/27/202222共五十五页元素n.元素i.元素2元素1存储内容LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址顺序存储结构(jigu)7/27/202223共五十五页 链式存储(cn ch)结构 1536元素21536元素21346元素3134

11、6元素3 元素4 元素4存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 13461400元素1h1400元素1h7/27/202224共五十五页数据(shj)的逻辑结构与存储结构密切相关算法设计取决于选定的逻辑结构。算法实现依赖于采用的存储结构。7/27/202225共五十五页 数据的逻辑(lu j)结构 数据的存储(cn ch)结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表栈队列树形结构图形结构数据结构的三个方面7/27/202226共五十五页数据

12、类型是一个值的集合和定义在这个值集上的所有(suyu)的操作。如，整型。在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。数据类型可分为：原子类型和结构类型。原子类型的值是不可分解的，如：整型、实型、字符型。结构类型的值是由若干成分按某种结构组成的，如：数组、结构体。数据类型可以看成是已经实现(shxin)了的数据结构。7/27/202227共五十五页抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的形式(xngsh)定义：用一个三元组来表示一个抽象数据类型。 ADT = ( D，S，P ) 其中：D 是数据对象， S

13、 是 D 上的关系集， P 是 D 的基本操作集。7/27/202228共五十五页抽象数据类型复数(fsh)的定义ADT Complex 数据对象：D = e1,e2 | e1,e2RealSet 数据关系：R1 = | e1是复数的实部，e2是复数的虚部 基本操作：InitComplex( &Z, v1, v2 )操作结果：构造复数Z，其实部和虚部分别被赋以参数(cnsh)v1和v2的值。 DestroyComplex( &Z)初始条件：复数已存在。操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用 realPart 返回复数Z的实部值

14、。GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用 ImagPart 返回复数Z的虚部值。Add( z1,z2, &sum )初始条件：z1，z2 是复数。操作结果：用sum返回两个复数z1，z2的和值。 ADT ComplexDSP7/27/202229共五十五页ADT 抽象数据类型名数据对象(duxing)：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT 抽象数据类型名描述(mio sh)抽象数据类型的形式 数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述7/2

15、7/202230共五十五页1.3 抽象数据类型的表示(biosh)与实现预定(ydng)义常量和类型#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW 2type int Status;7/27/202231共五十五页数据结构表示（存储结构）用类型（typedef）定义来描述。数据元素类型约定(yudng)为ElemType，由用户在使用时自行定义。基本操作的算法用函数描述函数类型 函数名（函数参数表）/算法说明语句序列/函数名7/27/202232共五十五页

16、赋值语句简单赋值变量名=表达式；串联赋值变量名1=变量名2=变量名k=表达式；成组赋值 (变量名1，变量名k)= (表达式1，表达式k)； 结构名=结构名； 结构名= (值1，值k)； 变量名=表达式； 变量名起始下标终止下标=变量名起始下标终止下标；交换(jiohun)赋值 变量名变量名；条件赋值 变量名=条件表达式？表达式T：表达式F；7/27/202233共五十五页选择(xunz)语句条件语句1 if(表达式) 语句；条件语句2 if(表达式) 语句； else 语句；开关语句1 switch(表达式) case 值1：语句序列1；break; case 值n：语句序列n；break;

17、default：语句序列n+1; 开关语句2 switch(表达式) case 条件1：语句序列1；break; case 条件n：语句序列n；break; default：语句序列n+1; 7/27/202234共五十五页循环语句(yj)for语句 for(赋初值表达式序列；条件；修改表达式序列) 语句；while语句while(条件)语句；do-while语句 do 语句序列； while (条件)；结束语句函数结束语句return表达式；return；case结束语句break；异常结束语句exit(异常代码)；7/27/202235共五十五页输入输出语句输入语句scanf(格式串，变量

18、(binling)，变量n)；输出语句printf(格式串，表达式，表达式n)；注释语句单行注释/文字序列逻辑运算约定与运算&对于A&B，当A的值为时，不再B对求值。 或运算|对于A|B，当A的值为非时，不再B对求值。 7/27/202236共五十五页基本函数(hnsh)求最大值max(表达式，表达式n)求最小值 min(表达式，表达式n)求绝对值abs(表达式)求不足整数值floor(表达式)求进位整数值ceil(表达式)判定文件结束 eof(文件变量)或eof判定行结束 elon(文件变量)或eoln7/27/202237共五十五页typedef struct float realpart

19、;float imagpart; complex; / 存储结构的定义/ 基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval );/ 构造复数 Z，其实(qsh)部和虚部分别被赋以参数 realval 和 imagval 的值void DestroyComplex( complex &Z)/ 销毁复数 Zfloat GetReal( cpmplex Z );/ 返回复数 Z 的实部值float Getimag( cpmplex Z );/ 返回复数 Z 的虚部值void add( complex z1, comple

20、x z2, complex &sum );/ 以 sum 返回两个复数 z1，z2 的和/ 基本操作的实现void add( complex z1, complex z2, complex &sum )/ 以 sum 返回两个复数 z1，z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart;利用C语言实现的复数(fsh)类型描述7/27/202238共五十五页1.4 算法(sun f)和算法(sun f)分析算法（Algorithm）是对特定问题求解步骤的一种描述，它是指

21、令(zhlng)的有限序列。算法的特性有穷性：一个算法必需总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性：算法中每一条执行都必须有确切的含义，使算法的执行者或阅读者不会产生二义性。并且在任何条件下，算法都只有一条执行路径。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。输入：有零个或多个的输入。输出：有一个或多个的输出。7/27/202239共五十五页算法的描述采用C语言算法的评价衡量算法优劣的标准(biozhn)正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量7/27/20224

22、0共五十五页算法(sun f)效率的衡量方法事后统计利用(lyng)计算机内记时功能。缺点：必须先运行依据算法编制的程序；所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度时间复杂度和空间复杂度7/27/202241共五十五页时间(shjin)复杂度T(n)=O(f(n)从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量(hng ling)效率的办法所得出的不是时间量，而

23、是一种增长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效率的优劣。除特别指明外，本书以后章节中讨论的时间复杂度均指最坏情况下的时间复杂度。7/27/202242共五十五页例1.1 两个 nn 的矩阵(j zhn)相乘。算法(sun f) 1.1void Mult_matrix(int c,int a,int b，int n)/ a、b和c均为n阶方阵，且c是a和b的乘积for(i=1; i=n; +i)for(j=1; j=n; +j) ci,j=0;for(k=1; k=n; +k)ci,j += ai,k*bk,j;/ Mult_matrix算法的时间复杂度为O (n3)原操作7/2

24、7/202243共五十五页例1.2 对 n 个整数(zhngsh)的序列进行选择排序算法 1.2void select_sort(int a, int n)/ 将 a 中整数(zhngsh)序列重新排列成自小至大有序的整数(zhngsh)序列for( i=0; in-1; +i ) j=i; for( k=i+1; kn; +k )if(ak1&change; -i) change = FALSE; for(j=0; jaj+1) w=aj; aj=aj+1; aj+1= w; change = TRUE / bubble_sort 算法时间复杂度取决于最深循环内包含基本操作的语句的重复执行次

25、数，称语句重复执行的次数为语句的频度。算法的时间复杂度为O (n2)原操作7/27/202245共五十五页空间(kngjin)复杂度S(n)=O(g(n)算法的存储量指的是算法执行过程中所需的最大存储空间。输入数据所占空间程序本身所占空间辅助变量所占空间若算法所需存储量依赖于特定的输入，则通常(tngchng)按最坏情况考虑。7/27/202246共五十五页本章(bn zhn)小结(一)数据是计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个体为一个数据元素。数据元素可以是不可分割的原子，也可以由若干数据项合成，因此在数据结构中讨论的基本单位是数据元素，而最小单位是数据项。数据结构是

26、由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类(s li)：线性结构、树形结构、图状结构和集合结构。7/27/202247共五十五页本章(bn zhn)小结(二)数据的存储结构是数据逻辑结构在计算机中的映象，由关系的两种映象方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它以附加的指针信息（后继元素的存储地址）表示关系。抽象数据类型是一个数学模型以及定义在该模型上的一组操作(cozu)。抽象数据类型的三大要素为数据对象、数据关系和基本操作，同时数据抽象和数据封装是抽象数据类型的两个重要特性。 7/27/202248共五十五页本章(bn zhn)小结(三)算法是对问题求解的一种描述，是为解决一个或一类问题给出的一种确定规则的描述。一个完整的算法应该具有下列五个要素：有穷性、确定性、可行性、有输入和有输出。一个正确的算法应对苛刻且带有刁难性的输入数据也能得出正确的结果，并且对不正确的输入也能作出正确的反映。算法的时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最深层循环内的语句的频度。算法空间(kngjin)复杂度主要取决于算法的输入量和辅助变量所占空间。7/27/202249共五十五页基础知识题(一)简述下