数据结构（C语言版）教学课件（完整版）.ppt

;数据结构（C语言版）;第一章 绪论;目录;1.1学生成绩系统简介;学号;C语言中的实现方法 ;C语言与数据结构的关系;1.2什么是数据结构;数据结构基本概念和术语;结论：数据、数据元素、数据项反映了数据组织的三个层次：数据可由若干个数据元素构成，而数据元素又可以由一个或若干个数据项组成。;1.2.3 三种数据逻辑结构;【例1.1】画出数据结构DS1的逻辑结构表示图。 【问题描述】有一种数据结构DS1=(D1,R1),其中D1={A,B,C,D}, R1={B,C,A,B,C,D},画出其逻辑结构表示图。 【分析】根据逻辑结构图的画法，经整理，DS1对应的逻辑结构图如图1-2所示，该逻辑结构图中第一个元素为A，最后一个元素为D，B、C分别有一个前驱元素和一个后继元素。 ;线性结构;树形结构;【例1.3】画出数据结构k的逻辑结构表示图。 【问题描述】有一种数据结构K=（D，R）,其中D={a,b,c,d,e,f,g}，R={a,b,a,c,a,d,b,e,c,f,c,g}，画出其逻辑结构图，并指出其逻辑结构的类型。 【分析】画出对应的逻辑结构图1-4所示，该数据结构为树形结构，结点a为树的根结点。 ;图形结构;【分析】为解决教学计划编排问题，我们首先得搞清课程之间的关系，如果我们将课程作为数据元素，将课程之间先后次序用有向边表示，就可以得到如图1-5所示的图形结构。;图形结构是最复杂的数据结构，数据元素之间存在多对多联系，该结构中任何元素都可以有多个直接前趋，也可以有多个后继。;1.2.4 数据物理结构;1.2.4 数据物理结构;1.2.5数据类型;1.3 算法和算法分析;1.3.1算法及其描述;1.3.1算法及其描述;算法的描述方法;【例1.5】分别用传统流程图和结构化流程图描述一个算法。 【问题描述】分别用传统流程图和结构化流程图描述下列问题：给定两个正整数m和n,求最大公约数。 【分析】将数学中求最大公约数的辗转相除法的求解过程进行分解，用标准的流程图基本符号表示成图1-8（a）和（b）图。;;类语言与高级程序设计语言有些类似，有比较严格的外语法，如用if…else…表示选择结构，用while表示循环结构，对内语法如变量定义等无明确要求，这种算法不能直接???计算机上运行，但专业设计人员经常使用伪语言来描述算法，它容易编写、阅读和统一格式。;1.3.2算法性能和复杂度分析;【例1.6】从算法健状性角度来分析如下问题：输入三角形的三条边，计算三角形的面积。【分析】 a.合法输入当输入的三条边a,b,c满足构成三角形的条件（a+bc,a+cb,b+ca）时，算法应能得到正常的结果b.非法输入当输入的三条边a,b,c有不满足构成三角形的条件（a+bc,a+cb,b+ca）时，算法应给出相应的提示信息。 注意：在算法调试过程，测试数据不仅要包括合法输入，还要尽可能多地包含各种形式的非法输入，以检验算法的健状性（或相容性）;算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂度，需要的空间（即存储器）资源的量称作空间复杂度。;在难以精确计算基本操作执行次数的情况下，只要求出它关于n的增长率即可，忽略常数项和低次项，用大O表示法来表示算法的时间复杂度。因此如果某算法T(n)=c*n+2 ，则其时间复杂度可简记为O(n)。;一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法运行过程中临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关，后一种是较理想的情况。 一个好的算法应兼顾时间效率和空间效率。;【例1.7】分析以下算法的复杂度 【问题描述】分析查找一维整数数组中最大元素算法的复杂度，该算法从数组中下标为0的元素开始，遍历数组中的所有元素，在遍历过程中，将当前最大元素保存在变量large中。 int largest (int *array, int n) { int large, i ; large = arra[0] ; for(i=1; in ;i++) if (array[i] large) large = array[i]; return large ; } 【分析】 时间效率：数组array中存放有n个整数，显然，无论那种算法，数据n的值越大，执行的时间越长，因此可将问题的规模定为数组中数据元素的个数n。基本操作是“比较”操作，即将数组中的一个整数和现有的最大整数作比较，上述算法中比较操作的次数为n-1。算法的时间复杂度为O（n）。 空间效率：由于本例中仅需临时存储空间为2个变量，与问题规模n无关，因此空间复杂度为O(1)。;【例1.8】分析以下程序段的复杂度 for (i=0;in;i