数据结构与算法2

1、第一章 绪论1.3 什么是数据结构 1.4 基本概念和术语1.5 算法和算法的描述1.1 引言1.2 数据结构的地位1.1 引言数值计算非数值计算研究数据的特性以及数据之间的关系数据结构1.2 数据结构的地位数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数学硬件软件数据结构1.3 什么是数据结构 001高等数学樊映川s01002理论力学罗远祥l01003高等数学华罗庚s01004线性代数栾汝书s02线性表例1 书目检索系统程序=数据结构+算法例2 人机对奕问题树.例3 多叉路口交通灯管理问题cedababacadbabcbddadbdceaebeced图 数据结构: 是研究

2、（程序设计中）计算机的操作对象以及它们之间关系和运算的一门学科。1. 数据:计算机中描述客观事物的符号。2. 节点（数据元素）:数据的基本单位。1.4 基本概念和术语001高等数学樊映川s01002理论力学罗远祥l01003高等数学华罗庚s01004线性代数栾汝书s02节点数据项图状结构多个对多个，如，图。3. 逻辑结构：数据元素之间的逻辑关系。线性结构一个对一个。如，线性表、栈、队列。树形结构一个对多个。如，树。根据数据元素之间的逻辑结构可将数据结构分为三类：4.存储结构（物理结构） ：数据在计算机中的存储表示。算法设计 逻辑结构算法实现 存储结构链式存储结构：借助指示元素存储地址的指针表示

3、数据元素间的逻辑关系。存储结构分为两种：顺序存储结构：借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系。数据的逻辑结构与存储结构密切相关： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 线性结构线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数据结构的两个方面：数据结构的两个方面：7.数据类型:数据的取值范围及其操作的总称。例:c语言中，提供int, char, float, double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef自定义数据类

4、型。typedef struct int num; char name20; float score;student;student stu1,stu2, *p;6.数据结构：数据元素和数据元素关系的集合。5.数据处理：插入、删除、查找、排序、修改等。 8.算法算法：解决特定问题的方法。1.5 算法和算法的描述1.5.1 算法 算法是执行特定计算的有穷过程。这个过程有5个特点： 1.动态有穷：当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止。 2.确定性：算法中的每条指令都必须是清楚的，指令无二义性。 3.输入：具有0个或0个以上由外界提供的量。 4.输出：产生1个或多

5、个结果。 5.可行性：每条指令都充分基本，能在有限的时间内完成。 注意：算法和程序是有区别的，即程序未必能满足动态有穷。在本书中，只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。 一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如pascal语言、c语言或伪代码等。1.5.2 算法的描述本书选用c语言作为描述算法的工具。 # define true 1； # define false -1； # define error null； 1预定义常量和类型：简单说明c语言的语法结构： 数据类型 函数名 （形式参数） 形式参数说明； 内部数据说明； 执

6、行语句组； /*函数名*/ 2函数的形式 函数的定义主要由函数名和函数体组成，函数体用花括号“”和“”括起来。函数中用方括号括起来的部分为可选项，函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成，两个语句之间用“；”号分隔。可将函数中的表达式的值通过return语句返回给调用它的函数。最后的花括号“”之后的/*函数名*/为注释部分，可舍。简单赋值：变量名=表达式，它表示将表达式的值赋给左边的变量； 变量+，它表示变量加1后赋值给变量； 变量-，它表示变量减1后赋值给变量；3赋值语句成组赋值：1.（变量1，变量2，变量3，变量k）=（表达式

7、1，表达式2，表达式3，表达式k）；2.数组名1下标1下标2=数组名2下标1下标2串联赋值：变量1=变量2=变量3=变量k= 表达式；条件赋值：变量名=条件表达式？表达式1：表达式2；交换赋值：变量1变量2，表示变量1和变量2互换；情况语句: switch （表达式） case 判断值1； 语句组1； break； case 判断值2；语句组2； break； case 判断值n；语句组n； break； default：语句组； break； 注 意 ： s w i t c h case语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就 执 行 相 应 的case下的语句组

8、；若不一致，则执行default下的语句组；其中的方括号代表可选项4条件选择语句if （表达式） 语句；if （表达式）语句1；else 语句2； for语句 for（表达式1；表达式2；表达式3）循环体语句；5循环语句 首先计算表达式1的值，然后求表达式2的值，若结果非零则执行循环体语句，最后对表达式3运算，如此循环，直到表达式2的值为零时止。 while循环首先计算条件表达式的值，若条件表达式的值非零，则执行循环体语句，然后再次计算条件表达式，重复执行，直到条件表达式的值为假时退出循环，执行该循环之后的语句。 while语句while （条件表达式） 循环体语句； 该循环语句首先执行循环体

9、语句。然后再计算条件表达式的值，若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。 do-while语句do 循环体语句 while（条件表达式）输入语句：用函数scanf实现，当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，当要输出字符数据时，用putchar函数实现。6输入、输出语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语句：表示出现异常情况时，控制退出语句。8注释形式 可用 /*字符串*/ 单行注

10、释 或 /文字序列。7其他一些语句如： max函数，用于求一个或几个表达式中的最大值； min函数，用于求一个或几个表达式中的最小值； abs函数，用于求表达式的绝对值； eof函数，用于判定文件是否结束； eoln函数，用于判断文本行是否结束。9一些基本的函数设计一个好的算法应考虑以下几个方面： 1正确性 “正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；程序对一切合法的输入数据都能产生满足规格说明要求的结果。1.5.3 算法

11、评价 运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。 通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。lt(n)=o(f(n)2运行时间时间复杂度的计算：例1：+x;s=0;1o(1)lt(n)=o(f(n)for(i=1;i=n;+i)+x;s+=x;no(n)for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;n*no(n2)例2：例3：频度时间复杂度程序void factorsum（n） int n；int i

12、，j；int f，w； f=0； for （i=1，i=n；i+） w=1； for（j=1，j=i；j+） w=w*j； f=f+w； return； 上述算法所用到的运算有乘法、加法、赋值和比较，其基本运算为乘法操作。在上述算法的执行过程中，对外循环变量i的每次取值，内循环变量j循环i次。因为内循环每执行一次，内循环体语句w=w*j只作一次乘法操作，即当内循环变量j循环i次时，内循环体的语句w=w*j作i次乘法。例4 计算f=1！+2！+3！+n！，用c语言描述。整个算法所作的乘法操作总数是：f（n）=1+2+3+n=n（n-1）/2。t(n)=o(n2) 一个算法在计算机存储器上所占用的

13、存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。 分析一个算法所占用的存储空间要从各方面综合考虑。 算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。l空间复杂度： s(n)=o(f(n)3占用的存储空间 最简单和最直接的算法往往不是最有效的，但算法的简单性使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时

14、间和压缩存储空间）比简单性更为重要。4简单性本章小结本章小结本章主要介绍了如下一些基本概念：数据结构：数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据：数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。结点：结点：结点也叫数据元素，它是组成数据的基本单位。逻辑结构：逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。存储结构：存储结构：数据在计算机中的存储表示称为数据的存储结构。数据处理：数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。数据类型：数据类型：