数据库绪论(数据库).ppt
课程简介：计算机软件的基础知识数据结构课时安排：数据结构52学时上机12学时课程设计18周（1周时间）,教材：数据结构C语言版 严蔚敏 吴伟民（清华）参考书：数据结构及应用算法教程 严蔚敏（清华大学出版社）数据结构 尹人昆（清华大学出版社）,课程介绍,数据结构在课程体系中的地位,第一章 绪论,1.1 什么是数据结构,记住一个公式：程序=数据结构+算法,第一章 绪论,1.1什么是数据结构,书目文件,第一章 绪论,1.1什么是数据结构,第一章 绪论,1.1什么是数据结构,多叉路口交通灯管理问题,算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列；,算法的描述（伪代码）算法设计的要求正确性(correctness)：功能必须正确可读性(readability)：通过注释、分块等完成健壮性(robustness)：能经受非法操作的检验高效：高速度、低存储,第一章 绪论,1.4 算法和算法分析,算法效率:依据算法编制的程序在计算机上执行所消耗的时间算法转化成的程序在计算机上运行所消耗的时间取决于：硬件的速度 书写程序的语言 问题的规模 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适，采用时间复杂度比较合适,第一章 绪论,1.4 算法和算法分析,时间复杂度：基本操作（元操作）重复执行的次数的阶数 T(n)=o(f(n),例1：N*N矩阵相乘void mult_matrix(int c,int a,int b,int n)/a、b、c均为n阶方阵，c为a和b的乘积 for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)s=s+aik*bkj;/mult_matrix,第一章 绪论,1.4 算法和算法分析,void select_sort(int a,int n)/将a中的整数序列重新排列成从小到大的有序整数序列 for(i=0;in-1;i+)j=i;for(k=i+1;kn;+k)if(akaj j=k;if(j!=i)w=aj;aj=ai;ai=w;/select_sort,第一章 绪论,1.4 算法和算法分析,例i=1;While(i=n)i=i*2;2f(n)=n即f(n)=log2n,T(n)=O(log2n),第一章 绪论,第一章 绪论,算法的存储空间的需求：空间复杂度：一个上机执行的程序对数据进行操作的工作单元和所需辅助空间的总的大小。S(n)=O(f(n),1、常量的描述#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 typedef int status;enum boolTRUE,FALSE;,第一章 绪论,1.3 抽象数据类型的描述,2、数据结构的描述 typedef struct int y;int m;datetype;,第一章 绪论,1.3抽象数据类型的描述,typedef struct char id8;char name32;char author16;char category4;datetype pdata;booktype;,3、基本操作的函数描述定义时：函数类型 函数名（函数参数）/算法说明 语句序列/函数名调用时：函数名(实际参数)或 函数名(实参1，实参2,),第一章 绪论,1.3抽象数据类型的描述,4、内存的动态分配与释放 指针变量=new 数据类型；delete 指针变量；,第一章 绪论,1.3抽象数据类型的描述,一、基本概念和术语1、集合：若干具有共同可辨特征的事物的“聚合”，其中每个事物称为集合的元素或成员。表示方法：直接列出集合中的元素。person=张三，李四，王二麻子描述集合的元素的共同特征 person=p|p是在当前教室听课的学生,第一章 绪论,1.2基本概念和术语,一、基本概念和术语2、数据：对客观信息的一种描述，是由能被计算机识别和处理的数值、字符等符号构成的集合。3、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素可以是不能再分“原子”，也可以是由多个款项（数据项）组成。,第一章 绪论,1.2基本概念和术语,一、基本概念和术语4、关键码：数据元素中能起标识作用的数据项；5、关系：集合中元素之间的某种相关性。在集合中的元素之间可能存在一种或多种关系，如关系、关系等。,第一章 绪论,1.2基本概念和术语,二、数据结构（data structure）若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为数据结构根据数据元素间关系的基本特性，有四种基本数据结构：线性结构、树形结构、图状结构、纯集合结构,第一章 绪论,1.2基本概念和术语,二、数据结构（data structure）,第一章 绪论,1.2基本概念和术语,线性结构：数据元素之间存在着“一对一”的线性关系,树型结构：数据元素之间存在着“一对多”的树形关系,图型结构（网状结构）：数据元素之间存在着“多对多”的网络关系,第一章 绪论,1.2基本概念和术语,逻辑结构,物理结构,逻辑结构：对数据元素之间存在的逻辑关系的抽象描述；物理结构：逻辑结构的数据在计算机中的表示和实现，又称为存储结构。,第一章 绪论,1.2基本概念和术语,数据结构的描述形式：struct date int x;/年份 int y;/月份/日期类型struct book char id8;/登录号 char name32;/书名 char author16;/作者 char category4;/分类号 struct data pdate;/出版时间/书目类型,typedef struct int x;int y;datetypetypedef struct char id8;char name32;char author16;char category4;datetype pdate;booktype,数据类型:一个值的集合和定义在此集合上的一组操作的总称,例 C语言中，提供int,char,float,double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型,第一章 绪论,抽象数据类型:一个数学模型以及定义在该模型上的一组操作。,通常用三元组表示为（D，S，P）D：数据对象 S：D上的关系的集合 P：对D的基本操作集ADT 抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名其中基本操作的定义格式为：基本操作名（参数表）初始条件：操作结果：,第一章 绪论,如线性表的定义为,ADT list 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：Rl=|ai-1,aiD,i=1,2,n 基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表。ADT List,第一章 绪论,
