资源描述：
《数据结构与算法教程 教学课件 作者 朱明方 吴及 第1章 绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、为什么要学习本课程？——学习本课程目的☞训练数据抽象能力；——确定数据结构(确定算法的前提)☞训练算法设计与描述能力；——编码(编程)的前提☞掌握常用数据结构与基本运算；☞进一步掌握设计方法；为解决非数值计算问题(数据处理问题)打基础提高程序(软件)设计能力——计算机应用的基本能力Wirth指出，程序设计的实质：算法+数据结构=程序课程主要内容：♦二元关系、数据结构的概念、算法及其效率分析；♦顺序表及其运算、应用(栈、队列)；♦数组与矩阵压缩存储；♦链表及其运算、广义表；♦树与二叉树(表示、存储、运算、应用)；♦图(概念、存储、遍历、典型应用)；♦查找技术(顺序表、索引表、散列表、树表、字
2、符串匹配)；♦排序方法(交换、插入、选择、归并、基数、拓扑、外部排序)。第一章绪论1.1数据抽象与二元关系一、数据抽象二、集合的笛卡尔积三、二元关系1.2数据结构的基本概念一、什么是数据结构二、数据结构的表示三、抽象数据类型1.3算法描述与算法分析一、算法的基本特征二、算法描述三、算法设计的常用方法四、算法的时间复杂度与空间复杂度1.1数据抽象与二元关系一、数据抽象1.数据抽象是数据处理中首先要解决的问题——得到数据模型问题1.1统计全年级学生的成绩，要求：①按学分积排序输出全年级学生的姓名、学号、班级、成绩；②按①排序的基础上，按总学分排序输出学生的信息学生集合抽象若干学生记录(姓名、学
3、号、班级、成绩)；元素间的关系抽象学生之间的成绩高低关系。抽象结果：学生成绩表1.1数据抽象与二元关系问题1.2某设备的部件构成关系如下：部件编号部件组成p1p1p2p2p3p1,p2p4p1,p3p5p2,p3p6p3,p4p7p2,p6,p8p8p5,p6问：如何安排这些部件的加工流程？1.1数据抽象与二元关系数据抽象：部件抽象数据元素；组成关系抽象数据元素之间的前后关系；抽象结果：数据元素间的关系图(图结构)；选择算法：存储关系图，采用拓扑分类方法处理——以顺序存储表示实现处理结果：加工装配顺序表1.1数据抽象与二元关系数据元素之间的前后关系图:p6p1p2p3p4p5p8p71.1
4、数据抽象与二元关系数据；2.解决数据处理问题的一般步骤：建立数学模型组织数据、确定求解方法编码、处理测试：查错、纠错；编码：写出程序;组织数据、确定求解方法：建立数学模型、确定数据间的关系(数据抽象)：实体、实体间的联系数据集合、数据元素间的关系；客观事物确定存储表示、确定处理算法；1.1数据抽象与二元关系二、集合的笛卡尔积(CartesianProduct——二元关系的源头)集合A对集合B的笛卡尔积,记作:A×B,定义为:A×B={(a,b),a∈A且b∈B}例:A={a1,a2}，B={0,1,2}则:A×B={(a1,0),(a1,1),(a1,2),(a2,0),(a2,1),(a
5、2,2)}问:B×A=?根据定义显然有:A×B≠B×A(A、B不为空)(A×B)×C≠A×(B×C)(A、B、C均不为空)思考:n个集合的笛卡尔积?1.1数据抽象与二元关系三、二元关系1.定义：设集合M、N,M×N的任意一个子集——M到N的一个二元关系；2.意义：表示集合M、N元素间的某种相关性。表示集合中元素间的关系，如：{（学生，毕设题目）}。当M=N时，表示同一集合中各元素间的关联.——M上的一个二元关系，简称关系。如：{（先修课程，后续课程）}(思考:n元关系？)若R是集合M上的一个关系，且有(a,b)∈R,称：a是b的关于R的前件（直接前驱）；b是a的关于R的后件（直接后继）;1
6、.1数据抽象与二元关系3.关系的基本性质设R是集合M上的一个关系：(1)自反性：对于每个a∈M，有(a,a)∈R；反自反性：对于所有a∈M，有(a,a)R；(2)对称性：当(a,b)∈R时，必有(b,a)∈R；反对称性：当(a,b)∈R且(a≠b)时，必有(b,a)R；(3)传递性：当(a,b)∈R且(b,c)∈R时，必有(a,c)∈R；1.1数据抽象与二元关系4.等价关系与等价类(1)等价关系非空集合上自反的、对称的和传递的关系。若R是非空集S上的等价关系，a,b是S中的任意元素，若有∈R，则称a等价于b，记作a～b。例，有网络站点集合C={u1,u2,u3,u4,u5,u
7、6}，C上的“同网段”关系——等价关系。因为：③若u1、u2同网段，u2、u3同网段，u1、u3必同网段。②若u1、u2同网段，则u2、u1同网段。①任何站点都和自己同网段。自反性对称性传递性设站点集合C中：u1、u2、u3是同网段的，u4、u5、u6在一个网段，则集合C的同网段关系为：R={,,,,,,,,<
