[理学]数据结构 第1章 绪论.pptVIP

数 据 结 构 第1章　绪　论 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 1.1 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： 数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。 1.2 学习数据结构的意义 　　计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 　　数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。 1.3 数据结构涵盖的内容 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} d1 d5 d2 d4 d3 　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 1.4 什么是抽象数据类型 1.4.1 数据类型与抽象数据类型的区别 1.4.2 抽象数据类型如何定义 例：给出自然数(Natural Number )的抽象数据类型定义。 1.4.3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 1.5 算法效率的度量 1.5.1 什么是算法？如何评判算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 1.5.3 计算举例 1.5.1 什么是算法？如何评判一个算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 3n+2=O(n) 1.5.3 计算举例 本章小结 数据结构课程—— 数据结构＋算法＝程序，涉及数学、计算机硬件和软件。 数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。 数据结构内容——数据的逻辑结构、存储结构和基本运算 数据结构学习工具——抽象数据类型和伪码（类C） 算法效率指标——时间效率和空间效率 作业： 复习C语言，重点是结构类型和递归概念。 补：Ｃ语言的数据类型 基本数据类型 int (三个限定词short, long, unsigned) float　(float, double, long double) char 指针类型 数组类型 字符串 无字符串类型，将其定义成字符数组 字符串长度？字符串所占字符空间？ 头文件string.h strlen(string), strcpy(str1,str2), strcat(str1,str2)… 结构体类型 共用体类型 枚举类型 定义类型 补：用Ｃ语言描述算法的注意事项 避免可能出现二义性的表达式（++, --） 避免使用转向语句（goto, break） 避免使用预处理（预处理器对语法不敏感） 避免函数返回值隐含说明（int） 例 int i; int *p=i; int *q=p; swap(int x,int y) { int temp; temp=x; x=y; y=temp; } main() { int a,b; scanf(%d,%d,a,b); if(ab) swap(a,b); printf(\n%d,%d\n,a,b); } swap(int *p1, int *p2) { int p; p=*p1; *p1=*p2; *p2=p; } main() { int a,b; int *pointer_1,*pointer_2; scanf(%d,%d,a,b); pointer_1=a; pointer_2=b; if(ab)swap(pointer_1,pointer_2); printf(