数据库绪论(数据库)

《数据库绪论(数据库)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程简介：计算机软件的基础知识———数据结构课时安排：数据结构——52学时上机——12学时课程设计——18周（1周时间）教材：数据结构C语言版严蔚敏吴伟民（清华）参考书：数据结构及应用算法教程严蔚敏（清华大学出版社）数据结构尹人昆（清华大学出版社）课程介绍数据结构在课程体系中的地位程序设计基础高级程序设计离散数学DataStructure数据库原理操作系统软件工程……第一章绪论1.1什么是数据结构记住一个公式：程序=数据结构+算法第一章绪论1.1什么是数据结构书目文件按书名按作者名按分类号索引表线性表树●●●●●●●●●●●●第一章绪论1.1什么是数据结构图ABCDEFGHI44.6

2、32.85.921.341.167.398.785.610.556.412.18.718.252.579.2居民区示意图ABCDEFGHI32.85.921.341.110.512.18.779.2铺设煤气管道设计图第一章绪论1.1什么是数据结构多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列；算法的描述（伪代码）算法设计的要求正确性(correctness)：功能必须正确可读性(readability)：通过注释、分块等完成健壮性(robustness)：能经受非法操

3、作的检验高效：高速度、低存储第一章绪论1.4算法和算法分析算法效率:依据算法编制的程序在计算机上执行所消耗的时间算法转化成的程序在计算机上运行所消耗的时间取决于：硬件的速度书写程序的语言问题的规模编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适，采用时间复杂度比较合适第一章绪论1.4算法和算法分析时间复杂度：基本操作（元操作）重复执行的次数的阶数T(n)=o(f(n))例1：N*N矩阵相乘voidmult_matrix(intc[][],inta[][],intb[

4、][],intn){//a、b、c均为n阶方阵，c为a和b的乘积for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)s=s+a[i][k]*b[k][j];}//mult_matrix第一章绪论1.4算法和算法分析voidselect_sort(inta[],intn)｛//将a中的整数序列重新排列成从小到大的有序整数序列for(i=0;i

5、lect_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、常量的描述#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintstatus;enumbool{TRUE,FALSE};第一章绪论1.3抽象数据类型的描述2、数据结构的描述typedefstruct{inty;intm

6、;}datetype;第一章绪论1.3抽象数据类型的描述typedefstruct{charid[8];charname[32];charauthor[16];charcategory[4];datetypepdata;}booktype;3、基本操作的函数描述定义时：函数类型函数名（函数参数）｛//算法说明语句序列｝//函数名调用时：函数名(实际参数)或函数名(实参1，实参2,…)第一章绪论1.3抽象数据类型的描述4、内存的动态分配与释放指针变量=new数据类型；delete指针变量；……第一章绪论1.3抽象数据类型的描述一、基本概念和术语1、集合：若干具有共同可辨特征的事物的“聚

7、合”，其中每个事物称为集合的元素或成员。表示方法：直接列出集合中的元素。person={张三，李四，王二麻子}描述集合的元素的共同特征person={p

8、p是在当前教室听课的学生}第一章绪论1.2基本概念和术语一、基本概念和术语2、数据：对客观信息的一种描述，是由能被计算机识别和处理的数值、字符等符号构成的集合。3、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素可以是不能再分“原子”，也可以是由多个款项（数据项）组成。第