第一章-数据结构概论ppt课件

1、。1，第1章数据结构介绍，赵建华，2，数据结构示例(1)，选课系统的两个数据实体：学生，课程表单中的每个记录都是数据，形成线性关系，3，数据结构示例(2)，从逻辑上讲，学生选修课的相关数据具有多对多的关系。每个(学生/课程)对还具有诸如成绩和时间的属性，这些属性被引入到课程选择表中：学生/课程选择和课程/课程选择之间存在一对多的关系、学生(学生编号、姓名、性别、籍贯)、课程(课程编号、课程名称、性别、籍贯)、课程选择(学生编号、课程编号、年级)、/(根)、bin、lib、用户等、数学、ds、SW、yin、陶、谢、堆栈。数字数据：整数、浮点数和其他非数字数据：字符、字符串、文本、图像数据元素数据

2、的基本单位由几个数据项组成。6，数据和数据结构(2)，并且数据结构：由一组数据元素和该组中所有数据元素之间的关系组成。写为：数据结构=D，R，其中D是数据对象，R是对象中所有数据成员之间关系的有限集合。本文主要讨论数据元素之间的关系。7，数据结构的分类，线性结构的所有元素按照一定的顺序排列在一个序列中。也就是说，元素之间存在一种全序非线性结构，每个元素可能与零个或多个其他元素相关，这可以分为：层次结构：元素之间的偏序关系；组结构：元素之间没有顺序关系。逻辑结构/物理结构、逻辑结构：独立于计算机的数据结构，从解决问题的需要出发，实现必要的功能；物理结构(存储结构):计算机中数据结构表示(图像)的

3、顺序存储方法：逻辑上相邻的元素存储在相邻的存储空间中；链接存储方式：索引存储方式通过附加指针字段实现：在存储元素信息的同时，建立附加索引表；哈希存储方法：根据节点的键码，通过函数计算直接获得(可能的)存储地址。算法的设计依赖于数据(逻辑)结构，而算法的实现依赖于所采用的存储结构。然而，算法的最终效率在很大程度上受到存储结构的影响。9。选择数据结构、确定算法的资源限制、分析问题、确定数据的逻辑结构、确定必须支持的基本操作的步骤，包括插入/删除数据项、搜索和遍历、确定每个操作的资源是空闲的、以及选择适当的物理存储结构。10。数据类型，数据类型：一组具有相同属性的值。以及在这个值集上定义的一组操作的

4、数据类型，确定变量的值域和可用的操作C语言中的数据类型。char int浮点双空字符整数浮点双精度无值。11，抽象数据类型(ADT)，定义：由用户定义，用于表示应用程序问题的数据模型由基本数据类型组成，并包括一组相关的服务(或操作)信息隐藏和数据封装。使用和实现是分开的，每个操作都可以用前置条件和后置条件来描述。12，ADT示例，ADT NaturalNumber is objects:是整数的有序子集，从0开始，以机器可以表示的最大整数结束。函数：适用于所有x，y自然数。True、trueboolean、-、=、=等等都是可用的服务。zero(): pre : True post :返回自然

5、数0自然数是零(x) : pre 3360 true post 3360如果(x=0)返回真否则返回假布尔加(x，Y): pre : x Y=max intpost 3360返回x y NaturalNumber减去(x，Y): pre : rueppost 3360如果(x，Y)返回0eelse返回x“测试选择排序： n”测试列表结束；测试列表。排序()；“排序后”测试列表结束；返回0；，17，算法，定义：有限指令集，指定用于解决特定任务的操作序列特征：输入具有0个或更多输入和输出以及一个或更多输出(处理结果)。每一步的确定性定义都是准确和明确的。有限算法应该在执行有限步骤后结束其有效性。原

6、则上每个操作都应该由计算机来执行。18，算法示例。案例研究：排序问题清除问题：非递减排序解决方案：逐个选择最小数据算法框架：对于(int I=0；I n-1；I) /n-1从ai到an-1的检查；如果最小的整数在ak中，则交换ai和ak；优化程序：程序选择排序，19，算法示例(续)，void selectsort (int a ，const int n)/对于n个整数a 0，a 1，a n-1，按非递减顺序排序(整数1=0；I n-1；I) int k=I；/从ai到an-1检查，找到最小的整数，并把它放在(int j=i 1)的k中；j . n .j)如果(ajak)k=j；/k表示当前找到

7、的最小整数int temp=ai;aI=ak；ak=温度；/交换ai和ak，20、算法的评价标准，正确性：正确执行预定功能并满足性能要求可用性：易用可读性：易于理解；逻辑清晰、简单、结构化；效率：执行算法时对计算机资源的消耗：时间、空间、能量消耗、健壮性：容错、异常处理、简单性：采用的数据结构/方法的简单性。嘿。21，算法的后测试(1)，在算法的某些部分插入时间函数time()，以测量算法完成某个功能所需的时间。顺序搜索行int序列搜索(int a ，const int n，const int x)/a 0，an-11 2 int I=0；3 while (i n 7)。22，算法的后期测试(

8、2)，时间程序void TimeSearch () /Search为0，10，90，100，200，1000 Inta 1001，in 1.(int j=1；j=1000。j)aj=j；/a1=1，a2=2，(j=0；j 10j) nj=10 * j；/n0=0，n1=10，n2=20nj 10=100 *(j 1)； /n10=100，n11=200，n12=300.cout n time endl对于(j=0；j20；j ) 长启动、停止；时间(，数据准备部分，记录开始时间，记录结束时间，1。结果取决于运行环境：系统，编译器，内存， 2。这取决于测试数据。3.但是，如果测试数据与实际数据一

9、致，就能真实反映算法的效率。23岁。算法的预估计和空间复杂度。当问题的规模在某个单位从1增加到N时，求解该问题的算法所占用的空间在某个单位从1增加到S(n)，因此该算法的空间复杂度为S(n)。时间复杂度当问题的规模在某个单位从1增加到n时，算法解决该问题所需的时间在某个单位从1增加到T(n)，因此算法的时间间复杂度为T(n)。嘿。24、空间复杂度、存储空间固定部分中程序指令代码的空间、常量、简单变量、固定长度组件(如数组元素、结构组件、对象的数据成员等)占用的空间。)变量与问题的输入规模、与问题规模相关的变量占用的空间、递归堆栈使用的空间以及new和delete命令动态使用的空间无关。25，空

10、间复杂度的估计，根据算法的描述，给出了与n的函数关系。对于递归算法，应该考虑递归深度和每次调用所需的空间。动态存储分配的空间应该考虑最坏的情况：最大值(新的执行次数-删除的执行次数)。26，空间复杂性的一个例子。示例1:找到表达式ab b * c (ab-c)/(ab) 4.0浮点ABC(浮点a，浮点b，浮点c)返回ab b * c (ab-c)/(ab) 4.0示例2:以迭代方式找到累加和浮点和(浮点a ，对于(int I=0；I n；I)s=aI；返回s；，示例3。递归地实现累积和float rsum(float，constant n)如果(当n=n0，T(n)=c*f(n)时，那么该算法的时间增长率被称为在O(f(n)中，其被表示为T(n)=O(f(n)任何不为零的异常数属于相同的数量级，其被记为O(1)。加法规则适用于并行程序段t (n，m)=t1 (n) t2 (m)=o(最大值(f (n)，g (m) c log2