数据结构第01章-绪论-c

数据结构,信息科学与技术学院周桂红电话公室：信息楼211,一、课程简介,“数据结构”是计算机类专业重要的专业技术基础课程，程序=数据结构+算法是提高软件设计水平以及学习后续课程所必需的基础。,一、课程简介,课程中介绍软件设计中常用的基本技术：常见的数据结构及其在计算机中的存储结构和操作实现：线性表、栈、队列、树和二叉树、图等常用的排序和查找方法及其性能。基本的算法设计技术。,一、课程简介,通过对这些内容的学习，达到以下教学目的：熟练地掌握各种常用结构的特性，理解各种运算的实现方法及其性能，并能在实际应用中，根据具体问题的要求，设计出合理的数据结构和运算。然而，由于该课程中的知识点多，而且许多内容较抽象，特别是其中大量的算法以及所用到的递归技术，动态存储结构，以及缺乏有效的实验条件，使学习数据结构课程的难度较大。因此，需要有必要的思想准备。,二、教学环节组成,整个课程的教学包括：课堂教学和实验教学两部分。共有4.5个学分课堂教学：48课时，3学分1-17周，保留一周备用或学校统一安排考试系统学习相关的知识体系和应用方法-基础理论实验教学：24学时，1.5学分由多个实验单元组成，分别围绕各部分的知识及其应用方法，对给定的问题，设计出合理的数据结构，以及算法实现，（时间和空间复杂度分析）并通过上机过程，调试算法和程序，验证、综合运用所学知识，提高解决实际问题的能力。,三、教材和参考书,教材：数据结构，周桂红主编，北京邮电大学出版社，2010。数据结构与程序设计，C+语言描述（英文版），RobertL.Kruse,AlexanderJ.Ryba，高等教育出版社).教材和参考书照片高教社外文版教材.JPG说明：理论教学、实验教学是互为补充的整个知识体系中的一部分。每本教材都有其优点和适用条件，但也存在不足。不能仅限于一本教材，需多方面参考，应多读几本，互为补充。,三、教材和参考书（2）,教学参考书：数据结构（C语言版），严蔚敏，吴伟民编著，清华大学出版社，1999。数据结构（C语言篇）习题与解析，李春葆编著，清华大学出版社，2002。,四、学习要求和建议,课堂教学的要求：不旷课、迟到、早退-保持听课和知识的完整性。事先作必要的预习-有备而来，主动学习，而不是被动学习认真听课，记笔记-便于后续的复习和回忆，因为单纯的听课而不记笔记达不到“完整记录”的效果。认真完成作业：-帮助复习、深化，乃至综合理解和运用知识提交作业：作业本，电子信箱平时成绩的计算方法，考试的门槛总结和复习：学习需要不断升华，提升对知识的理解深度。-从厚到薄，从薄到厚-实践，认识，再实践，再认识-温故而知新考勤的要求：必要的督促，作为平时成绩的组成部分。必须学会按照规则办事。,四、学习要求和建议（续1）,实验教学：作为教学的重要组成部分，围绕课程的知识的学习和应用能力的培养而开展的教学环节。非实践不能得真谛非实验不能探精微实践教学是实现教学目标的重要组成部分是检验和深化理论知识的重要手段实际解决问题的能力培养创新意识和能力的培养良好治学态度的培养,四、学习要求和建议（续2）,实验教学的要求每项实验任务都是需要完成的。实验前，要认真准备：理解教学要求，编写实验程序，组织好实验数据，并估计可能出现的问题。提交实验预习报告。实验过程中：认真观察过程，记录数据和结果，并分析有关的原因，及时调整。实验后：在系统分析试验数据和结果的基础上，对相关的原理进行总结。提交实验报告，培养良好的治学态度，掌握描述规范。平时成绩的计算方法，考试的门槛,第一章绪论,数据结构的研究对象,基本概念和术语,抽象数据类型,算法的评价,重点1.数据结构的定义2.数据的逻辑结构和存储结构及定义在结构上的算法及其实现3.算法复杂度的分析,本章要求,计算机解题的步骤提出问题建模设计算法存储数据编程调试结果在用计算机解决实际问题时，一般要经过以下几个步骤：首先，对具体问题抽象出数学模型，然后针对模型设计出求解算法，选择或设计合适的数据结构存储相关数据，最后编程序上机调试，直至得到最终的解。,1.1研究对象,1.1研究对象,问题求解之一：问题建模：一般情况下，实际应用问题可能会各式各样，如：我们所熟悉的工资表的处理问题，学生成绩管理问题，电话号码查询，数据加密、压缩问题等。这些问题中，无论是所涉及到的数据，还是其操作要求，都可能存在一定的差异。尽管如此，许多问题间还是具有一定相似之处的。例如：虽然工资表和学生成绩表的具体信息（栏目）不同，但如果将两个表中的每个人的工资信息和成绩信息分别看作一个整体，则这两个表结构之间就有了某些共性。从操作方面来看，虽然对这两种表的操作存在差异，但也存在一些相同或相似的基本操作。如查询一个人的工资信息和成绩信息，修改有关信息等。,1.1研究对象,正因为许多不同的问题之间存在着的某些共性，可以将一个具体问题用这些共性的形式描述出来-问题建模。问题建模通常包括：所描述问题中的数据对象的集合；对象间关系及其描述；问题求解的要求及方法等。建立问题模型的好处：通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后借助于这一模型来实现。数据结构、离散数学及许多数学课程中就介绍了许多模型。例如：要描述一个群体中个体之间的关系时，可以采用”数据结构”和”离散数学”中所介绍的图结构。要描述一个工程内的关系或进展情况时，我们可以采用”数据结构”中所介绍的AOV网或AOE网等。即使所建立的模型没有现成的求解方法，借助于已有的模型的适当组合也相对易于构造求解方法。,1.1研究对象,问题求解之二：构造求解算法通过问题建模，将一个具体的问题转换成一个用模型所描述的抽象的问题。借助于这一模型以及已有的知识（例如数据结构中有关图结构的基本知识），可以相对容易地描述出原问题的求解方法，即算法。算法设计过程中可能会涉及到多种技术，例如：递归。需要更多地实践。算法设计是计算机专业的核心能力，从某种意义上说，该算法不仅能实现原问题的求解，而且还可能实现许多类似的具体问题的求解，尽管这些具体问题的背景及其描述形式可能存在较大的差异。,1.1研究对象,问题求解之三：选择或设计存储结构在构造出求解算法之后，需要考虑在计算机上实现求解了。为此，需要做两方面的工作：选择或设计合适的存储结构，以便将问题所涉及到的数据存储到计算机中。（这包括数据中的基本对象及对象之间的关系）不同的存储形式对问题的求解实现有较大的影响，所占用的存储空间也可能有较大的差异。设计程序，实现问题求解。存储形式和问题要求决定了程序设计的方法。另外，程序设计环境（如VC）的熟练掌握也是本课程的学习过程中需要注意的教学目标之一。,问题求解之四：测试如何认定所设计的算法及程序能正确实现预定的功能和目标？理论证明：这是计算机科学领域曾经开展过的工作。由于算法和程序的复杂性急剧增长，因而难以实用。测试：通过对所开发的系统或模块，运行给定的测试数据，以发现存在的错误，而不是证明其正确。这是当前软件开发领域普遍采用方法，通常要占系统开发以上的工作量。详细描述可参考“软件工程”相关的描述。所设计的算法和程序，需要经过充分的测试才能交付使用。对程序的测试态度反映出学生的治学态度：如果是认真、负责的态度，就会认识到，任何设计都难免有疏漏，或者受环境的影响。因而需要高度重视。对程序的测试设计也反映出学生的治学能力：如何设计测试用例？需要依据多种方法、策略和实践。,1.1研究对象,问题求解的过程框架：,实际问题,求解算法,测试,程序设计,数据结构组织,数据结构课程中的内容,数学模型,数据结构：计算机类专业核心课程之一,1.2术语,下面介绍课程中所涉及到的一些术语数据（data）能够输入到计算机中，并能被计算机处理的符号的集合。例如，工资表，学生成绩，电话号码簿，电子字典，,工资表示例,学生成绩表示例,*工资表,*班级*课程成绩表,1.2术语,群体之间的认识关系图,家族关系示例,一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。,1.2术语,虽然数据的形式及运算存在较大的差异，但存在共性：由若干具有独立意义的个体所组成，个体间存在着某些关系。对这些数据的运算也有某些相似之处。例如，在家族关系数据中，组成数据的基本个体是个人信息，其中各人之间存在着多种关系，如父子关系、兄弟关系、祖先后代关系等。其中有些关系是直接表示出来的，还有一些关系则是隐含的。对家族关系数据，通常要涉及到查询特定个体间的关系、插入和删除个体等。,由前述示例可见，数据可以分解为元素的集合-数据元素（dataelement）构成数据的基本单位（具有完整的独立意义）。例如，工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素、记录、结点、顶点等。数据项（字段）元素的具体描述信息。,表中一行对应一个元素,表中一列对应一个字段,数据结构是相互之间存在一种或多种特定关系的数据元素的集合。元素之间的关系称为结构。形式定义为一个二元组Data_Structure=（D，S）其中：D是数据元素的有限集，S是D上关系的有限集,1.2术语,1.2术语,数据结构（datastructure）构成数据的元素之间的结构关系。数据元素之间存在以下几类内在的关系：线性结构：元素之间具有次序关系树形结构（树型结构）：元素之间的关系类似于现实中的树。图结构（网状结构）：元素间的关系较复杂。集合：元素之间没有关系。,逻辑结构,逻辑结构：数据结构中数据元素之间的逻辑关系。是从实际问题抽象出来的数据模型，是独立于计算机存储器的。通常按元素间存在的逻辑关系的不同特征，将数据结构分为四类：集合结构线性结构树型结构图型结构,集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。,例子：从大街上随意的找五个人组成一个小组，编号分别为1、2、3、4、5，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。,组成集合的数据元素之间不存在任何的关系,线性结构：数据元素之间存在“一对一”线性关系的数据结构。,例：学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一条和最后一条以外，每条记录都只有唯一的前驱和后继元素。,元素之间是1：1关系，都只有唯一的前驱和唯一的后继.,树型结构：数据元素之间存在“一对多”逻辑关系的数据结构。,例：一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业,元素之间的关系是1：n，每个元素都只有唯一的前驱元素，但可以有多个后继元素,图型结构：数据元素之间存在“多对多”逻辑关系的数据结构。,例：五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。,元素之间的关系是m:n，每个元素都可以有多个前驱元素和多个后继元素,数据结构的不同层次的表示和实现逻辑结构：数据结构中数据元素之间的逻辑关系。物理结构：数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。,存储结构又称物理结构：是数据的结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。分类：存储空间的不同分配方式分为：顺序存储链式存储索引存储散列存储,数据的物理结构数据元素的表示,顺序存储结构：所有元素存放在一片连续的存储空间中，逻辑上相邻的元素在内存中的物理位置也是相邻的。特点：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,顺序存储结构,链式存储结构,数据的物理结构关系的表示,链式存储结构：对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表称为链式存储结构。它通常借助于程序设计语言中的指针来实现。特点:借助指示元素存储地址的指针表示数据元素之间的逻辑关系。,更一般地，数据结构包括以下几个方面：逻辑结构元素之间的内在结构关系（逻辑关系）线性、树形（树型）、图（网状）、集合存储结构数据结构在内存中的实现形式运算-对数据所施加的运算。有关数据结构几个方面的联系图,逻辑结构,分析,运算实现（算法）,运算定义,数据结构的组成,背景,应用,1.3抽象数据类型（ADT）,抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述：ADT（，R，）其中，D是数据对象，R是D上的关系集，P是对D的基本操作集。,抽象数据类型（ADT）,ADTList数据对象：D=ai|aiElemSet,i=1,2,nn0数据关系：R1=|ai-1,aiD,I=2,n基本操作：InitList(,如何描述存储结构,可以借用高级程序语言中提供的数据类型来描述存储结构，例如用所有高级语言中的“一维数组”类型来描述顺序存储结构，以C语言提供的“指针”来描述链式存储结构。,数据元素typedefstructintnumber;charname8;intage;ElemType;,顺序存储ElemTypeSlist100;,链式存储typedefstructLNodeElemTypeelem;structLNode*next;*LinkList;,数据类型,在一种程序设计语言中，变量所具有的数据种类。例如，在C语言中数据类型分为基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义,ADT描述工具,类C语言重在描述数据结构和算法不能直接运行，需要转换交换赋值ab实际c=a;a=b;b=c;,抽象数据类型的表示与实现,采用伪码和C语言之间的类C语言作为描述工具，如下说明：1、预定义的常量和类型/函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2/Status是函数的类型，其值是函数结果状态代码typedefintstatus；,2、数据结构的表示（存储结构）用类型定义（typedef）描述，元素类型约定为ElemType，在使用时该数据类型自行定义。3、基本操作算法的函数描述函数类型函数名（函数参数表）/算法说明语句序列/函数名注：参数的传递输出语句:printf(格式串,表达式1,表达式n);注：通常省略格式串9、注释：单行注释/文字序列多行注释/*文字序列（可以多行）*/,10、基本函数：求最大值max(表达式1，表达式n)求最小值min(表达式1，表达式n)求绝对值abs(表达式)求不足整数值floor(表达式)求进位整数值ceil(表达式)判定文件结束eof(文件变量)或eof判定行结束eoln（文件变量）或eoln,11、逻辑运算约定：与运算m=n;n=r;returnm;其对应的递归函数如下：inthcf(intm,intn)if(n=0)returnm;elsereturnhcf(n,m%n);,1.4算法及其描述,例2.“韩信点兵”问题的求解方法有一队士兵，确切人数不知，但若每人一组，则余人；每人一组，余人；每人一组，余人；每人一组，余人。请解答下列问题：至少有多少人？若已知人数在500010000之间，问有多少个答案？解：初学者容易想到用逐个试探的方法来求解，这样显然很耗时间，特别是在所求解的值非常大时。求解方法是：逐个满足条件，在寻找满足下一个条件的解时保证前面条件继续成立。如何做到这一点？可以这样实现：探索满足下一个条件的的值时，以累加前面各数的最小公倍数来试探。由此得到求解的程序段。,1.4算法及其描述,问题（）的语言程序段如下：n=2;/满足3人一组余2while（n%5！=3）n=n+3;/在保证3人一组余2的前提下寻找满足5人一组余3的n值while（n%7！=5）n=n+15;/在满足前两个条件的前提下寻找满足7人一组余5的n值while（n%11！=4）n=n+105;/在满足前三个条件的前提下寻找满足11人一组余4的n值其中每次所加上的是前面数的最小公倍数3，15，105问题（2）的语言程序段如下：while（n5000）n=n+1155;while（n=10000）printf(“%8d”,n);n=n+1155;/输出满足条件的各解,1.5算法和算法分析,1.算法（Algorithm）的定义（Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.算法是规则的有限集合，是为解决特定问题而规定的一系列操作。）程序数据结构算法算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。,(1)有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。(2)确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。(3)可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。(4)输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。(5)输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,算法具有以下五个特性：,算法设计的原则,1.正确性:,a.程序中不含语法错误,b.程序对于几组给定的输入数据能得出满足要求的结果,c.程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入能得出满足要求的结果,d.程序对一切合法输入都能得出满足要求的结果,2.可读性：算法主要是为了人的阅读与交流，其次才是为了计算机执行，因此算法应该易于理解；另外，晦涩难懂的程序易于隐藏较多错误而难于调试,3.健壮性：当输入的数据非法时，算法应当恰当地做出反应或进行相应的处理，而不是产生莫名其妙的错误输出；并且处理错误的方法不应该始终段程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次进行处理,4.高效率和低存储量需求：效率：指算法的执行时间存储量：算法执行过程中所需的最大存储空间两者都与问题的规模有关,与算法效率有关的因素,算法采取的策略问题的规模程序设计语言编译的代码质量机器执行指令的速度,重点考虑时间因素。一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。假定，每条语句一次执行的时间都是相同的，为单位时间。这样对时间的分析就可以独立于软硬件系统。,算法分析,算法分析时间复杂度,for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;,原操作原操作重复执行的次数与问题规模n之间的关系：f(n)时间复杂度：T(n)=O(f(n),当问题的规模n趋于无穷大时，把f(n)的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）记作T(n)：,它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同。,1.5算法分析,例：求解以下程序段的时间复杂度：for（i=1;i=n;i+）x=x+1;该语句的流程图如下:由此可知，相应的时间复杂度为为O(n),语句执行次数,i=n,N,Y,i=1；,x=x+1；,i+；,共：3n+2次,练习：,1.求下列语句段的时间复杂度：(1)for(i=1;in;i+)for(j=1;j=i;j+)x+;(2)i=1;while(in)i=i*2;(3)for(i=1;i=n;i+)for(j=1;j=n;j+)for(k=1;k=n;k+)x+;（4）for(i=1;in;i+)for(j=1;jn;j+)x+;for(k=1;kn;k+)x+;,for(i=1;i=n,+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;f(n)n3T(n)=O(n3),常见函数的增长率,常见的渐进时间复杂度随问题规模n的扩大而增长且增长的速度是不同的，其大小次序如下：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n),算法分析空间复杂度,一个算法的空间复杂度（SpaceComplexity）定义为该算法所耗费的存储空间，它也是问题规模n的函数，记为S(n)=O(f(n)渐近空间复杂度也简称为空间复杂度。是对一个算法在运行过程中临时占用存储空间大小的度量。一个算法在计算机存储器上所占用的存储空间包括：存储算法本身所占用的存储空间算法的输入输出数据所占用的存储空间算法在运行过程中临时占用的存储空间,案例分析,问题：你本科毕业分配在一家大型银行工作。银行要求你写一个程序处理当天的所有业务，统计出每个账户的总交易金额。例：账号12345678当天有三笔业务，分别是23.5元、230元和510元，因此总共763.5元。现在要求你统计出该银行所有账号当天的交易总额“Easy!NoProblem”yousay.Except.,Except,每天有2亿笔业务数据随机存放银行每天只有一个小时的时间（2am-3am）用来完成该项任务；超出规定时