资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,计算机基础知识,概述,计算机系统,数字和信息编码,计算机网络,程序设计基础,数据库设计基础,数据结构与算法,软件工程基础,多媒体技术,主 要 内 容,一、,计算机的发展,二、,计算机的分类,三、,计算机的应用,概述,一、,计算机的发展,1,、,计算机的起源,1946,年,2,月,14,日，第一台电子计算机,ENIAC,（,Electronic Numerical Integrator And Calculator,，电子数字积分计算机）研制成功,。,计算机体系结构的形成,EDVAC,其主要思想有以下,3,点：,（,1,）,采用二进制表示数据。,（,2,）,“存储程序”，即程序和数据一起存储在内存中，计算机按照程序顺序执行。,（,3,）,计算机由运算器、控制器、存储器、输入设备和输出设备,5,个部分组成。,概述,2,、,计算机的,分代,按所用的逻辑元器件的不同，将其发展分为四个阶段,。,概述,二、,计算机的,分类,高性能计算机,微型计算机,工作站,服务器,嵌入式计算机,概述,三、,计算机的,应用,科学计算,数据处理,自动控制,计算机辅助设计,电子商务,人工智能,多媒体及网络应用,概述,一、计算机系统的组成,二、计算机的工作原理,三、计算机的主要技术指标,计算机系统,一、计算机系统的组成,计算机系统,二、计算机的工作原理,1,、存储程序,存储程序和程序控制，计算机的工作过程就是执行程序的过程，按照程序的顺序一步步取出指令，自动地完成指令规定的操作。,“存储程序”原理：,（,1,）用二进制形式表示数据与指令。,（,2,）指令与数据都存放在存储器中，使计算机在工作时能够自动高速地从存储器中取出指令加以执行。程序中的指令通常是按一定顺序一条条存放，计算机工作时，只要知道程序中第一条指令放在什么地方，就能依次取出每一条指令，然后按规定的操作执行程序。,计算机系统,2,、程序控制,计算机的工作过程是程序,的,执行过程。,计算机系统,三、计算机的主要技术指标,字长,字长是指计算机运算部件一次能同时处理的二进制数据的位数,运算速度,运算速度是指每秒钟所能执行的指令条数,主频,主频即,CPU,的时钟频率,存贮容量,存贮容量指存贮器所能寄存的数字或指令的数量,存取周期,存取周期指存贮器进行一次完整的存取操作所需要的时间,计算机系统,一、计算机中的数据,二、计算机中信息的表示,三、字符的编码,数字和信息编码,一、计算机中的数据,数据可分为数值数据和字符数据。,（,1,）数值数据用以表示量的大小、正负，如整数、小数等。,（,2,）字符数据也称为非数值数据，用以表示一些符号、标记，如英文字母、各种专用字符及标点符号等。,1,、基本概念,数制,：也称为“计数制”，是用一组固定的符号和统一的规则来表示数值的方法。任何一个数制都包含两个基本要素：基数和位权。例如人们常用的十进制，钟表使用的六十进制，计算机使用的二进制等。,基数,：一个数制中所包含的数字符号的个数称为该数制的基数，用,R,表示。如二进制有,0,和,1,两个数字符号，其基数为,2,；十进制有,0,到,9,十个数字符号，其基数为,10,。,数字和信息编码,位权,：任何一个,R,进制的数都是由一串数码表示的，其中每一位数码表示的实际值的大小，除数字本身的数制外，还与它所处的位置有关。该位置上的基准值称为位权。位权的大小是以基数为底，数码所在的位置序号为指数的整数次幂。对于,R,进制数，小数点前第一位的位权为,R,0,，小数点前第二位的位权为,R,1,，小数点后第一位的位权为,R,1,，小数点后第二位的位权为,R,2,，依此类推。,例如：十进制数,123.45,可按权展开表示为,123.45,110,2,+210,1,+310,0,+410,1,+510,2,其中,10,2,、,10,1,、,10,0,、,10,-1,、,10,-2,就是每个数码所处位置对应的权。,2,、计算机中的数制,在计算机内部一律采用二进制表示数据信息，编程时还常常使用八进制和十六进制。为了区分不同数制的数，约定对于任一,R,进制的数,N,，记为（,N,）,R,数字和信息编码,3,、各种数制之间的转换,在计算机内部一律采用二进制表示数据信息，编程时还常常使用八进制和十六进制。为了区分不同数制的数，约定对于任一,R,进制的数,N,，记为（,N,）,R,（,1,）非十进制数转换成十进制数,方法：对该,N,进制数“按权展开求和”即可。,例如：,二进制转十进制,（,100.01,）,2,1,2,2,+0,2,1,+0,2,0,+0,2,1,+1,2,2,4+0+0+0+0.25=(4.25),10,八进制转十进制,（,101,）,8,1,8,2,+0,8,1,+1,8,0,64+0+1=(65),10,十六进制转十进制,（,A3.2,）,16,A,16,1,+3,16,0,+2,16,1,160+3+0.125=(163.125),10,数字和信息编码,（,2,）十进制数转换成非十进制数,方法：将十进制数转换成其它任意,N,进制数，将此数分成整数与小数两部分并分别转换，然后再拼接起来。,整数部分：对被转换的十进制整数连续除以对应,N,进制的基数，直到商为,0,为止，所得的余数（从末位读起）就是这个数的,N,进制表示。简单的说，就是“除基取余倒排列（先低位后高位）”。,例如：,（,20,）,10,（,10100,）,2,数字和信息编码,2,20,10,2,5,2,2,2,1,2,0,余数,0,0,1,0,1,低,高,小数部分：对被转换的十进制小数连续乘以对应的,N,进制的基数，选取每次进位产生的整数，直到满足精度要求为止（小数部分可能永远不会得到,0,）。简单的说就是“乘基取整顺排列（先高位后低位）”。小数部分转换时可能是不精确的，要保留多少位小数，主要取决于用户对数据精确度的要求。,例如：,（,0.234,）,10,（,0.0011,）,2,（保留小数点后,4,位）,数字和信息编码,0.234,2,整数,(0).468 0,2,(0).936 0,2,(1).872 1,2,(1).744 1,综上所述：,十进制数,20.234,转换成二进制数为（,20.234,）,10,（,10100.0011,）,2,（,2,）二进制、八进制和十六进制数的相互转换,方法：,由于二位、八位和十六位这三种进制数的权之间有一定的内在联系，,n,位二进制数最多能够表示,2,n,种状态，,8,1,2,3,、,16,1,2,4,，即,1,位八进制数相当于,3,位二进制数，,1,位十六进制数相当于,4,位二进制数。,将二进制数转换成八进制数,方法：把一个二进制数转换为八进制数时，以小数点为中心向左右两边延伸，每三位为一组，中间的,0,不省，到了两头不够分组时就用,0,补足位数，算出每一组相对应的十进制数，然后将这些十进制数组合起来就成了一个八进制数。,例如：,（,11101000011.11101,）,2,（,3503.72,）,8,数字和信息编码,011 101 000 011 .111 010,3 5 0 3 7 2,将,八,进制数转换成,二,进制数,方法：以小数点为界，向左或向右每一位八进制数用相应的,3,位二进制数组取代即可。例如：,（,3503.72,）,8,（,11101000011.11101,）,2,数字和信息编码,3 5 0 3 .7 2,011 101 000 011 .111 010,将,二,进制数转换成,十六,进制数,方法：把一个二进制数转换为十六进制数时，以小数点为中心向左右两边延伸，每四位为一组，中间的,0,不省，到了两头不够一组时用,0,补足位数，算出每一组相对应的十进制数，然后将这些十进制数组合起来就成了一个十六进制数。,例如：,（,100011101000011.11000101,）,2,（,4743.C5,）,16,将,十六,进制数转换成,二,进制数,方法：以小数点为界，向左或向右每一位十六进制数用相应的四位二进制数取代，然后将其连在一起。,例如：,（,4743.C5,）,16,（,100011101000011.11000101,）,2,数字和信息编码,二、计算机中信息的表示,位,位是计算机数据的最小单位，也称为比特（,bit,，缩写为小写字母,b,）,字节,字节（,Byte,，缩写为大写字母,B,）是计算机中的基本存储单位，一个字节由八位二进制位构成，即,1B=8b,。,1KB=1024B,1MB=1024KB,1GB=1024MB,1TB=1024GB,字,字长,数字和信息编码,三、字符的编码,BCD,码,BCD,码是用若干个二进制数表示一个十进制数的编码。,ASCII,码,ASCII,码使用指定的,7,位或,8,位二进制数组合来表示,128,或,256,种可能的字符。标准,ASCII,码也叫基础,ASCII,码，使用,7,位二进制数（剩下的,1,位二进制为,0,）来表示所有的大写和小写字母，数字,0,到,9,、标点符号，以及在美式英语中使用的特殊控制字符。,汉字编码,（,1,）国标码,（,2,）外码,（,3,）字形码,（,4,）机内码,数字和信息编码,一、计算机网络的概念、组成及分类,二、网络体系结构,三、网络安全,四、,Internet,基础,计算机网络,一、计算机网络的概念、组成及分类,1,、计算机网络的定义,计算机网络应具有以下要素：,（,1,）至少拥有两台计算机,（,2,）使用传输介质和通信设备把若干台计算机连接在一起,（,3,）把多台计算机连接在一起，形成一个网络，是为了资源共享。,（,4,）为了正确地通信，需要有一个共同遵守的约定,通信协议。,2,、计算机网络的组成,资源子网,（,1,）,主机,（,2,）终端,（,3,）网络软件,计算机网络,通信子网,（,1,）通信控制处理机,（,2,）通信线路,（,3,）通信设备,3,、计算机网络的分类,按照覆盖的地理范围分类,（,1,）局域网,(,),（,2,）城域网,(,),（,3,）广域网,(,),计算机网络,按网络拓扑结构分类,（,a,）星型拓扑,（,b,）环型拓扑,（,c,）总线型拓扑,（,d,）树型拓扑,（,e,）网状拓扑,（,f,）混合型拓扑,计算机网络,按传输介质分类,（,1,）有线网,（,2,）无线网,按适用范围分类,（,1,）公用网,（,2,）专用网,按传播方式分类,（,1,）点到点网络,（,2,）广播式网络,按网络控制方式分类,（,1,）集中式,（,2,）分布式,计算机网络,二、网络体系结构,1,、网络协议,协议要素：,（,1,）语法：规定用户数据与控制信息的结构与格式,（,2,）语义：规定通信双方需要发出何种控制信息、完成何种动作及做出何种响应等。,（,3,）时序：又称“同步”，用于规定事件实现顺序的详细说明，即通信双方动作的时间、速度匹配和事件发生的顺序等。,2,、,OSI,参考模型,OSI,参考模型从下到上由物理层、数据链路层、网络层、传输层、会话层、表示层和应用层组成。低层（物理层、数据链路层）执行的功能与物理通信相关，如构建帧、传输含有包的信号；中间层（网络层、传输层、会话层）协调结点间的网络通信，如确保通信会话无中断、无差错地持续进行；高层（表示层、应用层）的工作直接影响软件应用和数据表示，包括数据格式化、加密以及数据与文件传输管理。,计算机网络,现实生活处理一些复杂问题时，人们通常会采用层次化的解决方式。例如在网络购物系统中。,计算机网络,OSI,参考模型中，划分层（子模块）要遵循以下原则：,（,1,）各层（子模块）具有相对的独立性，保持层间交互的信息最少。,（,2,）单向调用：各层（子模块）只能引用其下层提供的服务。,（,3,）增值服务：在使用下层服务的基础上，各层完成特定的通信功能。,计算机网络,3,、,TCP/IP,参考模型,TCP/IP,参考模型是将多个网络进行无缝连接的体系结构，共包含,4,个功能层，由下往上依次为：网络接口层、网络互连层、传输层和应用层，每一层负责不同的通信功能。,TCP/IP,参考模型的分层与,OSI,参考模型的分层不同，它的分层更加注重互联设备间的数据传输。但是，,OSI,参考模型和,TCP/IP,参考模型的分层有一个大致的对应关系。,计算机网络,4,、,TCP/IP,参考模型与,OSI,参考模型的比较,两者层数不一样,两者服务类型不同,概念区分不同,通用性不同,计算机网络,三、网络安全,1,、网络安全概述,一个安全的计算机网络应具有以下特征：,（,1,）完整性,（,2,）保密性,（,3,）不可否认性,（,4,）可用性,（,5,）可控性,计算机网络,2,、网络安全的内容,计算机网络安全主要有以下内容：,（,1,）保密,（,2,）鉴别,（,3,）访问控制,（,4,）攻击防范,3,、防火墙技术,分为,包过滤型防火墙和应用级防火墙。,4,、病毒与木马,计算机病毒具有几个明显的特征：传染性、破坏性、隐蔽性、潜伏性和寄生性。,计算机网络,5,、计算机病毒的防治,（,1,）建立良好的安全习惯,（,2,）及时升级操作系统的安全补丁,（,3,）关闭或删除系统中不需要的服务,（,4,）安装专业的防病毒软件,（,5,）定期进行数据备份,6,、网络信息安全的防控,（,1,）从数据传输方面加大安全保护力度。,（,2,）从访问控制方面提高安全指数。,（,3,）加大培养网络人才的步伐，致力于开发网络技术。,（,4,）从技术层面提高管理力度。,（,5,）努力提高用户对网络安全的认识程度。,计算机网络,四、,Internet,基础,1,、,Internet,概述,为了便于管理，因特网采用了层次网络的结构，即采用主干网、中间层网和底层网的逐级覆盖的结构：,计算机网络,2,、,WWW,服务,WWW,（,World Wide Web,）服务，又称,Web,服务，是,Internet,上被广泛应用的一种信息服务。它是一种基于超文本方式的信息查询服务，提供交互式图形界面，具有强大的信息连接功能，使得成千上万的用户通过简单的图形界面就可以访问各个组织的最新信息和各种服务。,HTML,和,Web,URL,URL,由三部分组成：第一部分表示访问信息的方式或使用的协议，如,FTP,表示使用文件转换协议进行文件传输；第二部分表示提供服务的主机名及主机名上的合法用户名；第三部分是所访问主机的端口号、路径或检索数据库的关键词等。因此，,URL,的一般形式为：,访问方式或协议：,/,例如，,Transfer Protocol,，,FTP,）用于实现计算机之间的文件传输，它的主要作用就是让用户连接上一个运行着,FTP,服务器程序的远程计算机，实现既可以查看远程计算机有哪些文件，也可以把文件从远程计算机上拷到本地计算机，或把本地计算机的文件发送到远程计算机的功能。下图是,FTP,的工作过程。,计算机网络,电子邮件服务,发送邮件：为用户准备报文、创建信封，并将报文装进信封，暂存起来。,接收邮件：定期检查邮箱，有新邮件时就向用户发出通知；用户读取邮件时为用户显示邮件清单等。,电子邮件地址的典型格式是：,其中，,是“,at”,的意思，,之前是用户选择代表自己的字符组合或代码，,之后是为用户提供电子邮件服务的服务供应商名称，如,wyq,。,计算机网络,电子邮件不同于普通的信件，但它的工作原理又和传统信件的处理流程有相似之处。电子邮件的发送主要涉及,3,个步骤，电子邮件的工作过程如下图：,计算机网络,网络信息搜索服务,搜索引擎按其工作方式主要分为,3,类：全文搜索引擎、目录索引搜索引擎和元搜索引擎。,其他应用,（,1,）,通信服务,（,2,）,网上教学,（,3,）,电子商务,（,4,）,生活娱乐,（,5,）,网上医疗咨询,（,6,）,企业管理,（,7,）,云盘,计算机网络,4,、,Internet,的接入方式,专线连接,专线连接是指用光缆、电缆，或者通过卫星、微波等无线通信方式，或租用电话专线、将网络连通。,局域网连接,局域网的覆盖范围一般是方圆几千米之内，其具备的安装便捷、成本节约、扩展方便等特点使其在各类办公室内运用广泛。,无线连接,“无线连接”是指使用,WiFi,、,4G,等无线技术建立设备之间的通讯链路，为设备之间的数据通讯提供基础，也称为无线链接，常用的实现无线链接的设备有无线路由器、蜂窝设备等。,电话拨号连接,通过电话线接入到,Internet,，对家庭用户来说是最为经济、简单的一种方式。目前普遍采用的是,ADSL,（非对称数字用户线路）方式。,计算机网络,一、程序设计风格,二、结构化程序设计,三、面向对象的程序设计,程序设计基础,一、程序设计风格,1,、源程序文档化,（,1,）符号名的命名,（,2,）程序的注释,序言性注释,功能性注释,（,3,）视觉组织,2,、数据说明,3,、语句结构,4,、输入和输出,程序设计基础,二、结构化程序设计,1,、结构化程序设计的原则,（,1,）自顶向下,（,2,）逐步求精,（,3,）模块化,（,4,）限制使用,goto,语句,程序设计基础,二、结构化程序设计,2,、结构化程序的基本结构,程序设计基础,顺序结构,分支结构,循环结构,三、面向对象的程序设计,1,、面向对象方法的主要优点,可重用性、稳定性好、可维护性好以及易于开发。,2,、对象、属性和操作,一个对象由对象名、属性和操作三个部分组成。,对象,对象是面向对象方法中最基本的概念。对象是指现实世界中具体存在的实体，可以用来表示客观世界中的任何实体，对象是实体的抽象。,对象的基本特点：标识惟一性，分类性，多态性，封装性，模块独立性好。,程序设计基础,属性,属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。每一个对象都有自己的属性（包括自己特有的属性和同类对象的共同属性）。属性值应该指的是纯粹的数据值，而不能指对象。属性反映对象自身状态变化，表现为当前的属性值。,操作,操作描述了对象执行的功能，操作也称为方法或服务。,3,、类,类是指具有共同属性、共同方法的对象的集合。,4,、消息,消息由三部分组成：,（,1,）接收消息的对象的名称,（,2,）消息标识符，也称消息名,（,3,）零个或多个参数,程序设计基础,5,、继承,继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。,6,、多态性,多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,程序设计基础,计算机基础知识,概述,计算机系统,数字和信息编码,计算机网络,程序设计基础,数据库设计基础,数据结构与算法,软件工程基础,多媒体技术,主 要 内 容,一、数据库系统的基本概念,二、数据模型,三、关系代数,四、数据库设计方法和步骤,数据库设计基础,一、数据库系统的基本概念,1,、基本概念,数据：实际上就是描述事物的符号记录。,数据库（,DB,）：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。,数据库管理系统（,DBMS,）：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。,数据库管理员（,DBA,）：对数据库进行规划、设计、维护、监视等的专业管理人员。,数据库系统（,DBS,）：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。,数据库应用系统：由数据库系统、应用软件及应用界面三部分组成,。,数据库设计基础,2,、数据库系统的发展,数据库管理发展至今已经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。,3,、数据库系统的基本特点,（,1,）数据的高集成性。,（,2,）数据的高共享性与低冗余性。,（,3,）,数据独立性,。,（,4,）,数据统一管理与控制。,数据库设计基础,4,、数据库系统的内部结构体系,数据库系统的三级模式,（,1,）,概念模式,（,2,）外模式,（,3,）,内模式,数据库系统的两级映射,（,1,）概念模式,/,内模式的映射,（,2,）外模式,/,概念模式的映射,数据库设计基础,二、数据模型,1,、数据模型,数据模型的概念,数据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供一个抽象的框架。,数据模型所描述的内容有三个部分，它们是数据结构、数据操作和数据约束。,数据模型的分类,（,1,）概念数据模型,（,2,）逻辑数据模型,（,3,）物理数据模型,数据库设计基础,2,、实体联系模型及,E-R,图,E-R,模型的基本概念,实体：客观存在并可相互区别的事物称为实体。,属性：实体所具有的某一特性称为实体的属性，一个实体可以有多个属性。例如学生的学号、姓名、性别、出生年月、班级等等。,联系：现实世界中事物间的关系。实体集的关系有一对一（,1,：,1,）、一对多（,1,：,n,）、多对多（,n,：,n,）的联系。,例下图中一个学生对应唯一的学号，一个学生只有一个姓名，这就是一对一的关系。一个系有多个学生，这就是一对多的关系。一个学生可以选修多门课程，而一门课程也可以由多名学生选修，则实体集学生与实体集课程之间是多对多的联系。,数据库设计基础,E-R,模型的图示法,数据库设计基础,数据模型分类,数据模型有层次模型、网状模型和关系模型三种。,层次模型示意图：网状模型示意图：,数据库设计基础,部门,管理,销售,员工,商品,工人,设备,数据模型分类,数据模型有层次模型、网状模型和关系模型三种。,关系模型示意图：,关系中的数据约束,实体完整性约束,参照完整性约束,用户定义的完整性约束,数据库设计基础,学号,姓名,性别,出生年月,班级,籍贯,2020102,张洁然,男,01-2-99,20,动画,1,班,广西南宁,2020103,李一明,男,05-3-99,20,美术,2,班,江苏南京,2020104,王丽,女,20-5-99,20,管理,3,班,福建福州,2020105,刘宏,女,10-5-99,20,旅游,4,班,福建厦门,三、关系代数,1,、关系的数据结构,关系是由若干个不同的元组所组成，因此关系可视为元组的集合。,关系模型的基本运算包括：插入；删除；修改；查询（包括投影、选择、笛卡尔积运算）等。,2,、关系操纵,3,、集合运算及选择、投影、连接运算,（,1,）并（）,（,2,）差（）,（,3,）交（）,（,4,）广义笛卡尔积（,）,数据库设计基础,有两个关系,R,和,S,，分别进行并、差、交和广义笛卡尔积运算。,数据库设计基础,3,、集合运算及选择、投影、连接运算,（,5,）选择、投影与连接,数据库设计基础,姓名,出生日期,性别,张洁然,01-2-99,男,李一明,05-3-99,男,王丽,20-5-99,女,刘宏,10-5-99,女,姓名,出生日期,性别,张洁然,01-2-99,男,李一明,05-3-99,男,选择,姓名,性别,张洁然,男,李一明,男,投,影,选择出,性别是男的学生名单,只查询性别为“男”的所有学生的“姓名”和“性别”,列,3,、集合运算及选择、投影、连接运算,（,5,）连接运算,数据库设计基础,学号,课程,成绩,2020103,数学,80,2020106,语文,85,学号相等,条件联接,自然联接,条件连接：当要满足某个给定条件时实现连接，称为条件连接。,等值连接：从关系与关系的笛卡尔积中选取和属性值相等的那些元组。,自然连接：自然连接是一种特殊的等值连接，它要求在结果中把重复的属性去掉。,数据库设计基础,四、数据库设计方法和步骤,1,、需求分析阶段,需求分析阶段是数据库设计的第一个阶段，任务主要是收集和分析数据，这一阶段收集到的基础数据和数据流图是下一步设计概念结构的基础。需求分析反映了用户的实际要求，将直接影响到后面各个阶段的设计，并影响到设计结果是否合理和实用。,2,、概念设计阶段,将需求分析得到的用户需求抽象为信息结构即概念模型的过程就是概念设计。,3,、逻辑设计阶段,逻辑结构设计是将概念结构设计阶段完成的概念模型，转换成能被选定的数据库管理系统,(DBMS),支持的数据模型。,数据库设计基础,逻辑设计一般分为三步进行：,（,1,）从,E-R,图向关系模式转化,（,2,）数据模型的优化,（,3,）关系视图设计,4,、物理设计阶段,为一个给定的逻辑模型选取一个最合适应用要求的物理结构的过程，就是数据库的物理设计。,5,、数据库实施阶段,数据库实施阶段包括两项重要的工作：一是数据的载入，二是应用程序的编码和调试。,6,、数据库运行维护阶段,数据库设计基础,一、数据结构的基本概念和算法,二、线性表及其顺序存储结构,三、栈和队列,四、树与二叉树,五、查找与排序技术,数据结构与算法,一、数据结构的基本概念和算法,1,、算法的定义,算法是对数据运算的描述，而数据结构是指数据的逻辑结构和存储结构。,算法,+,数据结构程序。,2,、算法的基本特征,可行性,确定性,有穷性,拥有足够的情报,数据结构与算法,3,、算法的复杂度,时间复杂度,算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。,空间复杂度,算法空间复杂度是指执行这个算法所需要的内存空间，包括三个方面：一是存储算法本身所占用的存储空间；二是算法在运行过程中临时占用的存储空间；三是算法中的输入输出数据所占用的存储空间。,时间空间复杂度之间的关系,4,、算法设计的要求,正确性、可读性、健壮性、时间效率高和存储量低,数据结构与算法,5,、数据结构的定义,数据的逻辑结构,数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。,数据的物理结构,数据的物理结构是指数据结构在计算机存储器上的存储表示，也称为存储结构。,数据的存储结构有顺序存储、链接存储、索引存储和散列存储四种等。,对各种数据结构进行的运算,创建（,Create,）：建立一个数据结构。,删除（,Delete,）：从一个数据结构中删除一个数据元素。,插入（,Insert,）：把一个数据元素插入到一个数据结构中。,修改（,Modify,）：对一个数据结构中的数据元素进行修改。,数据结构与算法,对各种数据结构进行的运算,访问（,Access,）：对一个数据结构进行访问。,撤销（,Destroy,）：消除一个数据结构。,查找（,Search,）：根据指定关键字对一个数据结构进行查找。,排序（,Sort,）：按照指定的关键字对一个数据结构进行从小到大或从大到小的排序。,6,、数据结构的图形表示,在数据结构的图形表示中，对于数据集合,D,中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系,R,中的每一个二元组，用一条有向线段从前件结点指向后件结点。,数据结构与算法,二、线性表及其顺序存储结构,1,、线性表的定义,线性表的特征,（,1,）有且仅有一个开始结点，它没有直接前驱，只有一个直接后继。,（,2,）有一个终端结点，它没有直接后继，只有一个直接前驱。,（,3,）其他结点都有一个直接前驱和直接后继。,（,4,）元素之间为一对一的线性关系。,2,、线性表的顺序存储,线性表的顺序存储结构也称为顺序表。,3,、线性表的基本运算,线性表的运算有插入、删除和查找等,数据结构与算法,顺序表的插入运算,在一般情况下，要在第,i,（,1in,）个元素之前插入一个新元素时，首先要从最后一个（即第,n,个）元素开始，直到第,i,个元素之间共,n-i+1,个元素依次向后移动一个位置，移动结束后，第,i,个位置就被空出，然后将新元素插入到第,i,项。插入结束后，线性表的长度就增加了,1,。,顺序表的删除运算,在一般情况下，要删除第,i,（,1in,）个元素时，则要从第,i+1,个元素开始，直到第,n,个元素之间共,n-i,个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了,1,。,进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（,n-1,）,/2,个元素,。,三、栈和队列,1,、栈,栈的概念,栈是限定仅在表尾进行插入或删除操作的线性表。,数据结构与算法,栈的运算,栈的基本运算有,3,种：进栈、出栈和读栈顶元素。,进栈。插入元素称为入栈运算。,出栈。出栈是栈的删除运算，它将删除栈顶元素。,读栈顶元素是将,top,指针指向的元素赋给一个指定变量，,top,指针及栈中元素个数不变。,2,、队列,队列的概念,队列是一种先进先出（,First In First Out,，缩写为,FIFO,）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。下图是队列的示意图：,a1,a2,an,数据结构与算法,出队,入队,队首,front,队尾,rear,队列的运算,队列的基本运算有：初始化队列、入队操作、出队操作、读队头元素和判队空操作。,入队。入队的队列的插入运算，它是在队尾插入一个新的元素。操作步骤是：先执行,rear,加,1,，使,rear,指向新的队列的位置，然后将数据元素保存到队尾（,rear,所指的当前位置），元素个数加,1.,出队。出队是队列的删除运算，它将删除队首元素。操作步骤是：先将,front,指向的队首元素取出，然后执行,front,加,1,，使,front,指向新的队首位置，元素个数减,1,。,循环队列,所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。,数据结构与算法,四、树与二叉树,1,、树,树的定义,树的特点：,每个结点有零个或多个子结点。,没有父结点的结点称为根结点。,每一个非根结点有且只有一个父结点。,除了根结点外，每个子结点可以分为多个不相交的子树。,树的基本术语,结点。结点（,Node,）是指一个数据元素及其若干指向其子树的分支。,结点的度、树的度。一个结点含有的子结点的个数称为该结点的度。一棵树中，最大的结点的度称为树的度。,数据结构与算法,树的基本术语,叶子结点、非叶子结点。度为,0,的结点称为叶结点，相应地度不为,0,的结点称为非叶子结点。除根结点外，分支结点又称为内部结点。,孩子结点、双亲结点和兄弟结点。一个结点含有的子树的根结点称为该结点的孩子结点或者子结点。若一个结点含有子结点，则这个结点称为其子结点的父结点或双亲结点。具有相同父结点的结点互称为兄弟结点。,层次、堂兄弟结点。从根开始定义起，根为第,1,层，根的子结点为第,2,层，以此类推。双亲在同一层的结点互为堂兄弟。,结点的祖先和子孙。结点的祖先指从根到该结点所经分支上的所有结点。结点的子孙指以某结点为根的子树中任一结点都称为该结点的子孙。,树的高度或深度。树中结点的最大层次。,森林。由,m,（,m=0,）棵互不相交的树的集合称为森林。若将一棵树的根结点删除，剩余的子树就构成了森林。,数据结构与算法,2,、二叉树,二叉树的定义,二叉树（,binary tree,）是指树中节点的度不大于,2,的有序树，它是一种最简单且最重要的树。,根据二叉树的定义可知，二叉树的结点度数只能为,0,（叶子结点）、,1,（只有,1,棵子树）或,2,（有,2,棵子树）。,二叉树的基本形态,（,a,）空二叉树,(b),单结点二叉树,（,c,）右子树为空（,d,）左子树为空,(e),左右子树都不为空,数据结构与算法,A,A,A,满二叉树和完全二叉树,满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。,完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,数据结构与算法,二叉树的性质,二叉树的存储结构,在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。,二叉树的遍历,前序遍历（,DLR,）：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树。并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。如下图二叉树，它的前序遍历为：,FCADBEHGM,。,数据结构与算法,二叉树的遍历,中序遍历（,LDR,）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树。并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。如下图二叉树，它的中序遍历为：,ACBDFHEMG,。,后序遍历（,LRD,）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点。并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。如下图二叉树，它的后序遍历为：,ABDCHMGEF,。,数据结构与算法,五、查找与排序技术,1,、顺序查找,顺序查找的基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。,2,、二分法查找,二分查找又称为折半查找，是一种效率较高的查找方法。在查找过程中，先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。二分查找必须在具有顺序存储结构的有序表中进行。,数据结构与算法,3,、排序技术,排序是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一种操作。,排序算法分为交换类排序法、插入类排序法和选择类排序法等。,（,1,）交换类排序法,冒泡排序,快速排序,（,2,）插入类排序法,简单插入排序,希尔排序,（,3,）选择类排序法,简单选择排序,堆排序,数据结构与算法,类别,排序方法,基本思想,时间复杂度,交换类,冒泡排序,相邻元素比较，不满足条件时交换,n(n-1)/2,快速排序,选择基准元素，通过交换，划分成两个子序列,O(nlog,2,n),插入类,简单插入排序,待排序的元素看成为一个有序表和一个无序表，将无序表中元素插入到有序表中,n(n-1)/2,希尔排序,分割成若干个子序列分别进行直接插入排序,O(n,1.5,),选择类,简单选择排序,扫描整个线性表，从中选出最小的元素，将它交换到表的最前面,n(n-1)/2,堆排序,选建堆，然后将堆顶元素与堆中最后一个元素交换，再调整为堆,O(nlog,2,n),数据结构与算法,几种排序的比较：,一、软件工程基本概念,二、结构化分析方法,三、结构化设计方法,四、软件测试,五、程序调试,软件工程基础,一、软件工程基本概念,1,、软件,计算机软件是包括程序、数据及相关文档的完整集合。其中，程序是按事先设计的功能和性能要求执行的指令序列；数据是使程序能正常操纵信息的数据结构；文档是与程序开发、维护和使用有关的资料。软件,=,程序,+,数据,+,文档。,2,、软件危机与软件工程,软件危机,所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。,软件工程,软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。,软件工程基础,3,、软件生命周期,软件生命周期是软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。,软件工程基础,时期,阶段,任务,文档,软件计划,问题定义,理解用户要求，划清工作范围,计划任务书,可行性分析,可行性方案及代价,需求分析,软件系统的目标及应完成的工作,需求规格说明书,软件开发,概要设计,系统的逻辑设计,软件概要设计说明书,详细设计,系统模块设计,软件详细设计说明书,软件编码,编写程序代码,程序、数据、详细注释,软件测试,单元测试、综合测试,测试后的软件、测试大纲、测试方案与结果,软件维护,软件维护,运行和维护,维护后的软件,4,、软件设计的目标和原则,软件设计的目标,开发出具
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
