《数据结构名师课件5》由会员分享，可在线阅读，更多相关《数据结构名师课件5（96页珍藏版）》请在金锄头文库上搜索。
1、,DATA,10,65,865,数据结构与算法,课 程 简 介课程内容：计算机软件的基础知识数据结构数据结构算法程序数据结构：问题的数学模型线性结构：线性表、栈、队列非线性结构：树、图算法：处理问题的策略查找、排序（算法基础）,数据结构的教学要求： 学会分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构以及相应的算法。简而言之分析待处理的对象的特性以及各 处理对象之间存在的关系。,教材： 数据结构（C语言版） 严蔚敏 清华大学出版社课时安排：76学时 （60/16） 4.5学分,与其他课程的关系,先修课：程序设计语言C程序设计语言算法描述的基础之一后续课：算法基础,1.1 什
2、么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法的描述和算法分析,第一章 绪 论,对问题的解决方法是：寻找问题 分析问题 解决问题而对计算机来说： 从具体问题 数学模型 设计算法 编程 测试 调整 解决问题,1.1 什么是数据结构,例1 书目自动检索系统,书目文件,例2 人机对奕问题,结论描述这类非数值计算问题的数学模型不是数学方程，而是树、表和图之类的数据结构。数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。,1.2 基本概念和术语数据（Data)信息的载体所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计
3、算机处理的信息的某种特定的符号表示形式。 例如：数字、字母、汉字、图形、图像、声音都称为数据。,数据元素（Data element）构成数据的基本单位，具有独立意义，可以分割成若干个具有不同属性的项（字段），也称节点（node）或记录（record）。,数据项（Data item）数据不可分割的最小 单元，也称域(field)。 数据元素可以是数据项的集合数据对象（Data Object） 性质相同的数据元素的集合。 e.g. C=A，B，Z ,字母字符数据对象,数据结构（Data Structure） -带结构的数据元素的集合。 研究数据结构，包括研究数据的逻辑结构和数据的存储结构。,假设用
4、三个 4 位的十进制数表示一个含 12 位数的十进制数。,3214,6587,9345 a1(3214),a2(6587),a3(9345),则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,例如:,又例，在2行3列的二维数组a1, a2, a3, a4, a5, a6中六个元素之间存在两个关系:,行的次序关系:列的次序关系:,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3a4 a5 a6,row = ,再例，在一维数组 a1, a2, a3,
5、a4, a5, a6 的数据元素之间存在如下的次序关系:,| i=1, 2, 3, 4, 5,可见，不同的“关系”构成不同的“结构”,或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,数据的逻辑结构不考虑具体存储形式，只抽象反映数据元素的逻辑关系。可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,数据结构的形式定义为:,数据结构是一个二元组,Data_Structures = (D, S),其中:D 是数据元素的有限集， S 是 D上关系的有限集。,数据的存储（物理）结构,逻辑结构在计算机（存储器）中的表示（或称映象），包括数据元素的表示和关系的表示，,“数据元素”的映
6、象 ？,“关系”的映象 ？,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,关系的映象方法：,（表示x, y的方法）,顺序映象,以相对的存储位置表示后继关系,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C,而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息,x y,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,在不同的编程环境中，,存储结构可有不同的描述方法。,当用高级程序设计语言进行
7、编程时，通常可用高级编程语言中提供的数据类型描述之。,例如:,以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型。,typedef int Long_int 3,定义长整数为:,存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,算法和数据结构是计算机程序设计的“两大支柱”。,Niklaus Wirth： Algorithm + Data Structures = Programs,
8、程序设计:算法: 数据结构:,为计算机处理问题编制 一组指令集,处理问题的策略,问题的数学模型,1.3 抽象数据类型的表示与实现,一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如C语言或伪代码等。本书选用C语言作为描述算法的工具。 现简单说明C语言的语法结构如下：,补充内容一：C语言语法 1预定义常量和类型： # define TRUE 1； # define FALSE -1； # define ERROR NULL；,2函数的形式 数据类型 函数名 （形式参数） 形式参数说明； 内部数据说明； 执行语句组； /*函数体*/ 函数的定义主要由函数名和函
9、数体组成，函数体用花括号“”和“”括起来。函数中用方括号括起来的部分为可选项，函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成，两个语句之间用“；”号分隔。可将函数中的表达式的值通过return语句返回给调用它的函数。最后的花括号“”之后的/*函数体*/为注释部分，可舍。,3赋值语句简单赋值：变量名=表达式，它表示将表达式的值赋给左边的变量；特殊赋值： 变量+，它表示变量加1后赋值给变量； 变量-， 它表示变量减1后赋值给变量；,4条件选择语句if （表达式） 语句；if （表达式） 语句1； else 语句2；switch （表达式）
10、case 判断值1： 语句组1； break； case 判断值2： 语句组2； break； case 判断值n： 语句组n； break； default：语句组； break； ,注意：switch case语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句组；若不一致，则执行default下的语句组；其中的方括号代表可选项。,5循环语句 for语句 for（表达式1；表达式2；表达式3） 循环体语句；首先计算表达式1的值，然后求表达式2的值，若结果为真（非零）则执行循环体语句，最后对表达式3运算，如此循环，直到表达式2的值为假（零）时止。,
11、while语句 while （条件表达式） 循环体语句； while循环首先计算条件表达式的值，若条件表达式的值非零，则执行循环体语句，然后再次计算条件表达式，重复执行，直到条件表达式的值为假时退出循环，执行该循环之后的语句。, do-while语句 do 循环体语句; while（条件表达式）该循环语句首先执行循环体语句。然后再计算条件表达式的值，若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。,6输入、输出语句输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，当要输出字符
12、数据时，用putchar函数实现。,7其他一些语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过 程或跳出情况语句。（3）exit语句：表示出现异常情况时，控制退出语句。8注释形式 /*字符串*/ or /文字序列。,9一些基本的函数如： max函数，用于求一个或几个表达式中的最大值； min函数，用于求一个或几个表达式中的最小值； abs函数，用于求表达式的绝对值； eof函数，用于判定文件是否结束； eoln函数，用于判断文本行是否结束。,10结构体 struct student int num; char name20; char sex; int age; float score; char addr30; ;,11.可用typedef 自己定义数据类型,typedef struct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;,补充内容二：指针,（一）指针概述：地址的概念与取地址运算： 内存以字节编码，每个编码都是一个地址。我们原先学过的变量、数组、函数等都放在内存中，我们怎样知道机器将某种数据放在内存的什么地方呢？,
