数据库绪论[数据库].ppt

课程简介： 计算机软件的基础知识———数据结构 课时安排： 数据结构——52学时 上机——12学时 课程设计——18周（1周时间）;数据结构在课程体系中的地位;第一章 绪论;第一章 绪论;树;图;多叉路口交通灯管理问题;算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列；;算法效率:依据算法编制的程序在计算机上执行所消耗的时间 算法转化成的程序在计算机上运行所消耗的时间取决于： ?硬件的速度 ?书写程序的语言 ?问题的规模 ?编译程序产生机器代码质量 ?机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适，采用时间复杂度比较合适;时间复杂度：基本操作（元操作）重复执行的次数的阶数 T(n)=o(f(n)) ;void select_sort(int a[],int n)｛ //将a中的整数序列重新排列成从小到大的有序整数序列 for(i=0;in-1;i++){ j=i; for(k=i+1;kn;++k) if(a[k]a[j] j=k; if(j!=i) {w=a[j];a[j]=a[i];a[i]=w;} } }//select_sort;例 i=1; While(i=n) i=i*2; 2f(n)=n 即f(n)=log2n,T(n)=O(log2n);第一章 绪论;1、常量的描述 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int status; enum bool{TRUE,FALSE}; ;2、数据结构的描述 typedef struct{ int y; int m; }datetype; ;3、基本操作的函数描述 定义时： 函数类型 函数名（函数参数） ｛ //算法说明 语句序列 ｝//函数名 调用时：函数名(实际参数)或 函数名(实参1，实参2,…) ;4、内存的动态分配与释放 指针变量=new 数据类型； delete 指针变量； ……;一、基本概念和术语 1、集合：若干具有共同可辨特征的事物的“聚合”，其中每个事物称为集合的元素或成员。 表示方法： 直接列出集合中的元素。 person={张三，李四，王二麻子} 描述集合的元素的共同特征 person={p|p是在当前教室听课的学生} ;一、基本概念和术语 2、数据：对客观信息的一种描述，是由能被计算机识别和处理的数值、字符等符号构成的集合。 3、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据元素可以是不能再分“原子”，也可以是由多个款项（数据项）组成。 ;一、基本概念和术语 4、关键码：数据元素中能起标识作用的数据项； 5、关系：集合中元素之间的某种相关性。 在集合中的元素之间可能存在一种或多种关系， 如{教师，学生}关系、{张三，李四}关系等。 ;二、数据结构（data structure） 若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为数据结构 根据数据元素间关系的基本特性，有四种基本数据结构： 线性结构、树形结构、图状结构、纯集合结构 ;二、数据结构（data structure） ;第一章 绪论;第一章 绪论;数据类型:一个值的集合和定义在此集合上的一组操作的总称;抽象数据类型:一个数学模型以及定义在该模型上的一组操作。;如线性表的定义为