数据结构第01章绪论_c

数据结构信息科学与技术学院周桂红电话：[phone]办公室：信息楼211数据结构一、课程简介“数据结构”是计算机类专业重要的专业技术基础课程，程序=数据结构+算法是提高软件设计水平以及学习后续课程所必需的基础。c/c++/java程序设计数据结构操作系统计算机网络数据库算法设计与分析…数据结构一、课程简介课程中介绍软件设计中常用的基本技术：–常见的数据结构及其在计算机中的存储结构和操作实现：线性表、栈、队列、树和二叉树、图等–常用的排序和查找方法及其性能。–基本的算法设计技术。数据结构二、教学环节组成整个课程的教学包括：课堂教学和实验教学两部分。共有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.2术语下面介绍课程中所涉及到的一些术语数据（data）——能够输入到计算机中，并能被计算机处理的符号的集合。–例如，工资表，学生成绩，电话号码簿，电子字典，编号姓名基本工资奖金……工资表示例学号姓名考试成绩备注学生成绩表示例****工资表**班级**课程成绩表数据结构1.2术语A1A2A3A5A4A6A8A7群体之间的认识关系图AA2A1A11A3A12A311A21A32A31A121家族关系示例一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。数据结构1.2术语虽然数据的形式及运算存在较大的差异，但存在共性：由若干具有独立意义的个体所组成，个体间存在着某些关系。对这些数据的运算也有某些相似之处。例如，在家族关系数据中，–组成数据的基本个体是个人信息，–其中各人之间存在着多种关系，•如父子关系、兄弟关系、祖先－后代关系等。其中有些关系是直接表示出来的，还有一些关系则是隐含的。对家族关系数据，通常要涉及到查询特定个体间的关系、插入和删除个体等。数据结构由前述示例可见，数据可以分解为元素的集合----数据元素（dataelement）—构成数据的基本单位（具有完整的独立意义）。–例如，工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。–在有些场合下，也称之为元素、记录、结点、顶点等。数据项（字段）——元素的具体描述信息。学号姓名考试成绩备注表中一行对应一个元素表中一列对应一个字段数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。元素之间的关系称为结构。形式定义为一个二元组Data_Structure=（D，S）其中：D是数据元素的有限集，S是D上关系的有限集1.2术语数据结构1.2术语数据结构（datastructure）——构成数据的元素之间的结构关系。–数据元素之间存在以下几类内在的关系：线性结构：元素之间具有次序关系树形结构（树型结构）：元素之间的关系类似于现实中的树。图结构（网状结构）：元素间的关系较复杂。集合：元素之间没有关系。逻辑结构数据结构逻辑结构：数据结构中数据元素之间的逻辑关系。是从实际问题抽象出来的数据模型，是独立于计算机存储器的。通常按元素间存在的逻辑关系的不同特征，将数据结构分为四类：集合结构线性结构树型结构图型结构数据结构集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。例子：从大街上随意的找五个人组成一个小组，编号分别为1、2、3、4、5，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。组成集合的数据元素之间不存在任何的关系数据结构线性结构：数据元素之间存在“一对一”线性关系的数据结构。学号姓名系别学分…0351103王杰计算机3…0351212李丽计算机1…┇┇┇┇…例：学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一条和最后一条以外，每条记录都只有唯一的前驱和后继元素。元素之间是1：1关系，都只有唯一的前驱和唯一的后继.数据结构树型结构：数据元素之间存在“一对多”逻辑关系的数据结构。例：一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业学院数学系计算机系外语系应用专业网络专业软件专业教师学生元素之间的关系是1：n，每个元素都只有唯一的前驱元素，但可以有多个后继元素数据结构图型结构：数据元素之间存在“多对多”逻辑关系的数据结构。例：五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。12345元素之间的关系是m:n，每个元素都可以有多个前驱元素和多个后继元素数据结构数据结构的不同层次的表示和实现逻辑结构：数据结构中数据元素之间的逻辑关系。物理结构：数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。数据结构存储结构又称物理结构：是数据的结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。分类：存储空间的不同分配方式分为：顺序存储链式存储索引存储散列存储数据结构数据的物理结构－－数据元素的表示序号姓名成绩1张三852李四903王五85………属性数据元素数据项数据结点数据域数据结构顺序存储结构：所有元素存放在一片连续的存储空间中，逻辑上相邻的元素在内存中的物理位置也是相邻的。特点：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。数据结构顺序存储结构┇030010302张0304三030685030820310李0312四031490┇┇030010302张0304三03068503080700┇070020702李0704四070690┇链式存储结构数据的物理结构－－关系的表示数据结构链式存储结构：对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表称为链式存储结构。它通常借助于程序设计语言中的指针来实现。特点:借助指示元素存储地址的指针表示数据元素之间的逻辑关系。数据结构更一般地，数据结构包括以下几个方面：逻辑结构——元素之间的内在结构关系（逻辑关系）–线性、树形（树型）、图（网状）、集合存储结构——数据结构在内存中的实现形式运算------对数据所施加的运算。有关数据结构几个方面的联系图逻辑结构分析运算实现（算法）运算定义存储结构抽象数据类型（ADT）数据结构的组成背景应用数据结构1.3抽象数据类型（ADT）抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述：ADT＝（Ｄ，R，Ｐ）其中，D是数据对象，R是D上的关系集，P是对D的基本操作集。数据结构抽象数据类型（ADT）ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,nn≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,I=2,…,n}基本操作：InitList(&L);DestroyList(&L);┇｝数据结构1.4算法及其描述算法描述语言易懂，灵活自然语言不准确准确，严格计算机语言死板伪语言（类语言）：类pascal、类C、类C++本课程中将采用C的函数形式来描述。算法举例：1.求最大公因子（辗转相除法）2.韩信点兵问题数据结构1.4算法及其描述例1.求最大公因子（辗转相除法）求任意两个整数M,N最大公因子(M,N)的方法如下：若M=N*Q+R其中:R为余数,满足O≤R≤N-1则(M,N)=(N,R)且当R=0时，(M,N)=N按照这种方法，可以快速而方便地求出任意两个整数的最大公因子。例如，（1500，550）的求解过程如下：（1500，550）=（550，400）=（400，150）=（150，100）=（100，50）=（50，0）=50最终求得1500和550的最大公因子为50。1500%550＝＞400数据结构1.4算法及其描述由此，可得到求任意两个整数M和N最大公因子的算法的Ｃ语言函数如下：inthcf(intm,intn){while(n!=0){r=m%n;m=n;n=r;}returnm;}其对应的递归函数如下：inthcf(intm,intn){if(n==0)returnm;elsereturnhcf(n,m%n);}数据结构1.4算法及其描述例2.“韩信点兵”问题的求解方法有一队士兵，确切人数不知，但若每３人一组，则余２人；每５人一组，余３人；每７人一组，余５人；每１１人一组，余４人。请解答下列问题：⑴至少有多少人？⑵若已知人数在5000～10000之间，问有多少个答案？解：初学者容易想到用逐个试探的方法来求解，这样显然很耗时间，特别是在所求解的值非常大时。求解方法是：逐个满足条件，在寻找满足下一个条件的解时保证前面条件继续成立。如何做到这一点？可以这样实现：探索满足下一个条件的ｎ的值时，以累加前面各数的最小公倍数来试探。由此得到求解的程序段。数据结构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值｝其中每次所加上的