数据结构(C语言描述)第1章-绪论07课件

1、 数据结构（C语言版）二零零七年 简 介数据结构是计算机专业的一门专业基础课，在计算机学科中起着承上启下的作用，在计算机技术的各个领域也有着广泛的应用。学习这门课需要程序设计语言作为其基础，学习前要有比较扎实的程序设计基本功（这部分内容本课程中将不予涉及），同时又为后续的数据库等一系列课程提供知识基础。数据结构这门课程涉及数据的组织、存储以及运算的一般方法。希望通过这门课的学习，掌握数据结构的基本概念，掌握求解问题的思路与方法，具备数据抽象的能力。 数值问题和非数值问题的比较 数值问题 对象：len，wide，area 用数值表示 对象之间的关系： area=lenwide，可用方程或函数表示

2、。 数据存储：可用程序设计语言中的实型变量存储数据。 非数值问题 对象：课程 用课程名表示 对象之间的关系：课程间有“次序”关系（不能用方程或函数表示，可用图来表示） 数据存储：数据及数据之间的关系存储。第一章 绪论学习要点 熟悉数据、数据对象、数据元素、数据类型、数据结构等基本概念，特别是数据的逻辑结构与物理结构概念及其关系。 了解算法的定义、算法的特性、算法的时间代价、算法的空间代价。掌握计算语句频度和估算算法时间复杂度的方法。1.1 概述1.2 数据结构的基本概念1.3 数据类型和抽象数据类型1.4 算法第一章 绪论1.1 概述计算机解题步骤具体问题数学模型算法编程、调试数据处理的种类和

3、能力数 (整数,实数)字符、字符串、文字、图形、图象、声音数值数据非数值数据1.2 数据结构的基本概念数据：是对客观事物的符号表示。学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004.例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。数据元素是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。数据项是数据不可分割的最小单位。数据对象是性质相同的数据元素的集合。一个数据项一个数据元素学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五87747362010

4、04.整个表的记录是学生成绩数据数据结构是相互之间存在一种或多种特定关系的数据元素之间的集合。数据结构的分类线性结构 :元素间为严格的一对一关系。 如上面的成绩表中各元素 集合:元素间为松散的关系。 树形结构：元素间为严格的一对多关系 图状结构(网状结构):元素间为多对多关系 数据结构的形式定义为：数据结构是一个二元组：Data-Structure=（D，R）有限个数据元素的集合有限个节点间关系的集合例4 为毕业设计小组设计一个数据结构。假设每个小组的关系由一名教师指导一到十名学生。则数据结构的二元组表示如下：Group=(P,R)其中：PT,G1,Gn 1n10 R| 1in, 1n10 逻

5、辑结构：“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。物理结构：数据结构在计算机中的表示称为物理结构。又称存储结构。计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。顺序结构 （元素在存储器中的相对位置）链式结构 （元素地址的指针）元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m顺序存储每个元素所占用的存储单元个数所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。1536元素21400元素11346元素3 元素

6、41345h链式存储 每个节点都由两部分组成：数据域和指针域。数据域存放元素本身的数据，指针域存放指针。数据元素之间逻辑上的联系由指针来体现。所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。数据类型：是一个值的集合和定义在这个值集上一组操作总称。例如，C语言中的整形变量:其值为某个区间上的整数，定义在其上的操作为：加、减、乘、除和取模等算术运算。分类：(按值的不同特性)原子类型 ：每一个对象仅由单值构成的类型 ；结构类型 ：每一个对象可由若干成分按某种结构构成的类型。 1.3 数据类型和抽象数据类型 抽象数据类型（ADT

7、）作用：抽象数据类型可以使我们更容易描述实际问题。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。好处：可提高软件的复用程度。 使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。原子类型值不可分解，如int固定聚合类型值由确定数目的成分按某种结构组成，如复数可变聚合类型值的成分数目不确定，如学生基本情况抽象数据

8、类型分类抽象数据类型表示法：一、三元组表示：（D，S，P）其中D是数据对象，S是D上的关系集，P是对D的基本操作集。二、抽象数据类型的定义格式：ADT 抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注 1 ：它有些类似C语言中的结构（struct）类型，但增加了相关的服务。注 2 ：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。算法的定义ispass(int num44) int i,j; for(i=0;i4;i+)for(j=0;j4

9、;j+) if(numij!=i*4+j+1)return 0; return 1; /*类似华容道游戏中判断游戏是否结束的算法*/定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。 1.4 算法算法的特性有穷性：算法必须在有限步内结束；确定性：组成算法的操作必须清晰无二义性。可行性：组成算法的操作必须能够在计算机上实现。输入：0个或多个输入；输出：1个或多个输出；有穷性haha()/*only a joke,do nothing.*/ main()printf(请稍等.您将知道世界的未日.);while(1)haha(); 确定性float aver

10、age(int *a,int num)int i;long sum=0;for(i=0;inum;i+)sum+=*(a+);return sum/num;main()int score10=1,2,3,4,5,6,7,8,9,0;printf(%f,average(score,10); 输出getsum(int num)int i,sum=0;for(i=1;ib)if(ac) return c;else return a; 程序对于几组输入数据能够得出满足规格说明要求的结果。max(int a,int b,int c)if (ab)if(ac) return a;else return c

11、; /* 8,6,7 */ /* 9,3,2 */程序对于精心选择的典型、苛刻的输入数据能够得出满足规格说明要求的结果。max(int a,int b,int c)if (ab) if(ac) return a; else return c; else if(bc) return b; else return c; 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。算法设计的要求算法效率的度量 算法效率 用依据该算法编制的程序在计算机上执行所消耗的时间来度量。通常用事后统计和事前分析估计这种方法。但同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时

12、间单位衡量算法效率不合适。在三个整数中求最大者max(int a,int b,int c)if (ab)if(ac) return a;else return c; elseif(bc) return b;else return c; /*无需额外存储空间，只需两次比较*/max(int a3)int c,int i;c=a0; for(i=1;ic) c=ai;return c; /*需要两个额外的存储空间，两次比较，至少一次赋值*/*共需5个整型数空间*/ 100个整数同上的算法难写难读/*共需102个整型数空间*/ 算法效率的度量事后统计的方法；事前分析估算的方法；事前估算法要考虑以下的

13、因素： 问题的规模；编写程序时所用的程序设计语言； 机器的速度； 算法所用的策略。撇开这些与机器软硬件有关的因素，可以认为一个特定算法“运行工作量”的大小只依赖与问题的规模，或者说只是问题规模的函数。例 两个n*n矩阵相乘的算法。for（i=1；i=n；+i）for（j=1；j=n；+j）cij=0；for（k=1；k=n；+k）cij+=aik*bkj； 语句到语句执行的次数依次是（n+1）， n（n+1）， n2，（n+1）n2 ， n3。它们之和就是该算法的时间开销T（n）=2n3+3n2+2n+1当n充分大的时候，T（n）与f（n）=n3的数量级相同。于是，该算法的时间复杂度为：T（n

14、）=O（n3），其原语句是语句。 频度：是指该语句重复执行的次数算法的时间复杂度(Time Complexity)一般来说，设算法中所有语句的频度之和记作T(n)，它是问题规模n的某个函数f(n)，记作： T(n) = O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率与f(n) 的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。语句在算法中被重复执行的次数(Frequency Count)+x; s=0; for( j=1; j=n; +j )for ( k=1; k=n; +k) +x; s+=x;for (i=1; i=n; +i) +x; s+=x;T(n)=O(1)T(n)=O(n2)T(n)=O(n)例 求下面程序段的时间复杂度4.for (i=2;i=n;+i)for (j=2;k=1&change;-i) change=FALSE; for(j=0;jaj+1) ajaj+1;change=TRUE;冒泡排序的时间复杂度为?1. O(1) 常量阶，与n无关 2. O(log2 n) 对数阶3. O(n) 线性阶 4. O(n log2 n) n log2 n阶5. O(n2) 平方阶 6. O(n3) 立方阶7. O(2