程序构造的基本方法

《程序构造的基本方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计与算法语言——大学计算机知识基础程序构造的基本方法上讲回顾计算机中数据的表示进位计数制基数位权机器数—怎样用二进制表示负数并正确运算原码、补码、反码、移码小数点的表示定点浮点非数值数据的编码汉字编码布尔代数信息科学与工程学院2程序构造的基本方法程序构造的基本方法1.数据组织2.数据处理数据的组织与数据的处理相互影响信息科学与工程学院3程序构造的基本方法1.数据组织两大类型内存数据组织：存放于内部存储器中的数据，数量相对较小外存数据组织：存放于内部（一小部分）和外部（绝大部分）存储器中的数据，数量相对较大，需要专用数据管理系统来协调数据的交换文件系统数据库系统信息科学与工程学

2、院4程序构造的基本方法1.数据组织逻辑组织：一种抽象的描述，只涉及数据之间的组织关系。其组织方法1.简单2.线性3.层次4.网状5.外存物理组织：一种具体的组织形态信息科学与工程学院5程序构造的基本方法1.数据组织简单数据组织方法用于相互之间没有太强关系的少量数据对每一个数据都取一个名称，代表存放数据的空间xyklz信息科学与工程学院6程序构造的基本方法1.数据组织线性数据组织方法用于同类的批量数据，即“向量”，例如一时间段对内某一事物的观测数据{x1,x2,…,xn-1,xn}一个班级全体学生学号整批数据共享一个名称，而其中每一个具体数据通过赋予各自的一个序号给出x1x2x3x4x

3、5x6x7x8x9信息科学与工程学院7程序构造的基本方法1.数据组织线性数据组织方法具体实现（物理组织）方式连续：将这组数据存放在计算机内存中某个连续区域，因此可根据其对应的序号直接计算出每一个数据存储的具体区域，例如：数组非连续：将这组数据分散存放在计算机内存中，需一个联系每一个数据存储位置的附加区域，将后面一个数据存储位置登记到前面一个数据的附加区域，例如：单向链表信息科学与工程学院8程序构造的基本方法1.数据组织线性数据组织——链表（linkedtable，空间换时间）1520002010320102004352030200067203420302-12056662056203

4、4信息科学与工程学院9程序构造的基本方法1.数据组织线性数据组织——在链表中插入元素3201020043520306720342-166205615200056206020602030X信息科学与工程学院10程序构造的基本方法1.数据组织线性数据组织——在链表中删除元素3201020043520306720342-1662056152000XX2030信息科学与工程学院11程序构造的基本方法1.数据组织线性数据组织——栈（stack，先进后出）FirstInLastOut（FILO）压栈（push）出栈（pop）数据操作特点只能在同一端（栈顶）进行每次涉及一个数据栈底栈顶入栈出栈信息

5、科学与工程学院12程序构造的基本方法1.数据组织线性数据组织——队列（queue，先进先出）FirstInFirstOut（FIFO）进队（push）出队（pop）数据操作特点在不同端进行插入和删除操作每次涉及一个数据队尾队头进队出队信息科学与工程学院13程序构造的基本方法1.数据组织层次数据组织方法——树（tree）节点根枝叶子从根到叶子的一条路经上的所有节点构成一个线性关系整个数型结构由多个线性关系叠加构成RootLRLLRLRLLRRLRR信息科学与工程学院14程序构造的基本方法1.数据组织网状数据组织方法——图（graph）允许任意两个数据之间都可存在关系使用一个矩阵定

6、义数据之间的关系使用线性复合的方式表达网状数据组织可定义数据之间的顺序关系可定义数据之间的关系代价ABDEC信息科学与工程学院15程序构造的基本方法1.数据组织外存数据组织方法（大容量数据组织）——文件（file）建立（create）使用打开（open）读/写（read/write）关闭（close）删除（delete）移动（move）信息科学与工程学院16程序构造的基本方法2.数据处理方法——算法定义：一个有穷的指令集，规定一个运算序列特点有零或多个输入（事先得到的）有一或多个输出确定性：每一步都应确切和无歧义定义有穷性有效性算法与数据组织密切相关，是在某种数据组织结构上的一种解决

7、问题的计算方法信息科学与工程学院17程序构造的基本方法2.数据处理方法——算法衡量算法的标准——用相对量级表示时间空间信息科学与工程学院18程序构造的基本方法2.数据处理方法——算法1.算法描述算法是抽象的，但必须通过具象的方式来展示。形式语言：自然语言、类计算机语言、计算机语言图形：流程图、N-S图、PAD图表格2.常用算法信息科学与工程学院19程序构造的基本方法2.数据处理方法——算法用流程图表示基本逻辑控制规则处理顺序单分支双分支信息科学与工程学院2