数据结构与算法(二级培训).ppt

《数据结构与算法(二级培训).ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构与算法第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法与算法分析1.1什么是数据结构一、计算机解决问题的一般过程。1、建立数学模型。2、根据数学模型，设计算法。3、编写程序，调试直至问题的最终解决。二、数值问题与非数值问题。数值问题就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积。非数值问题就是问题中涉及的对象不能用数来表达的那些问题。1）数值问题例1已知：游泳池的长length和宽wide，求面积area。分析：问题涉及的对象：游泳池的长length宽wide，面积area；对象之间的关系：area=

2、lengthwide；main(){intlen,wide,area;scanf(“%d%d%”,&l,&w);area=len*wide;printf(“area=%d”,area);}2）非数值问题例2已知研究生选课情况，安排课程考试的日程。研究生选课情况表姓名选修课1选修课1选修课1张ABE王CEF李DFA赵BF分析：◆问题涉及的对象：课程；◆课程之间的关系：同一个研究生选修的不能按排在同一时间内考试；课程及课程之间的关系可用如下所示的图表示：DEFCBA顶点：表示课程；边：同一研究生选修的课程用边连接课程考试安排问题转化为图的着色问题用尽可

3、能少的颜色为该图的每个顶点着色，使相邻的顶点着上不同的颜色；每一种颜色代表一个考试时间，着上相同颜色的顶点是可以按排在同一时间考试的课程；DEFCBAACEFBD课程着色的过程红色：a，c；黄色：b，d；绿色：e；蓝色：f即a,c可安排在同一时间考试，b,d可安排在同一时间考试;设G表示课程关系图，集合V包含图G中所有尚未着色的顶点，NEW表示可以用新颜色着色的顶点集合。I=1；WHILEV非空DO置NEW为空集合；FOR每个vVDOIFv与NEW中所有的结点间都没有边从V中去掉v；将v加入NEW；（第I天考试课程为NEW中顶点所对应的课程）以某种形式

4、输出NEW中顶点所对应的课程；I=I+1；通过对上个问题的分析，在这个问题的分析解决的过程中我们遇到了以下几个问题：1、如何表示节点以及它们之间的关系（相邻接）2、在计算机中如何存储。3、相应的操作如何描述。（染色过程）3）数值问题与非数值问题的比较数值问题已知游泳池的长length,和宽wide,求面积area。（1）问题涉及的对象：length,wide,area是实数可用数值表示；（2）对象之间的关系：area=lengthwide可用方程或函数表示；（3）数据存储：可用程序设计语言中的实型变量存储；（4）问题求解：用某种计算方法求解；已知研究生选课情况

5、，安排课程考试的日程。1）问题涉及的对象：课程可用课程名表示,不能用数值表示2）对象之间的关系：同一研究生选修的课程不能安排在同一时间考试，同一研究生选修的课程之间有某种“冲突”关系——课程之间的这种关系不能用方程或函数表示3）数据及数据之间的关系如何存储？4）如何求解？非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间关系和操作等的学科。1.2基本概念和术语1、数据：一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所

6、要处理的数据可能是一张如表1-1所示的表格。2．数据元素数据元素（也叫节点），它是组成数据的基本单位。在程序中通常作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。表1-1个人书库3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象的集合N={0，±1，±2，

7、……}，字母数据对象的集合C={‘A’,’B’,……’Z’}。4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。根据数据结构之间关系，通常有下列4类基本结构。集合线性结构树型结构图状结构数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集合。5、数据的逻辑结构：数据元素之间的逻辑关系。数据的存储结构：数据结构在计算机中的表示。本课程中介绍的存储结构有：顺序存储结构链式存储结构索引结构散列结构6、数据类型：数据类型是一个值的集合和定义在这

8、个值集上的一组操作的总称