第5章 会计信息化软件系统理论基础ppt
- 1. 第五章 会计信息化软件系统 理论基础
- 2. 5.1 数据结构 5.2操作系统 5.3软件工程方法 5.4网络技术基础
- 3. 5.1数据结构 Data Structure Curriculum & It’s Research Field
- 4. 数据结构:Data_Structure=(D,R) 其中: D是数据元素的集合。 R是该集合中所有元素之间的关系的有限集合。 数据结构：是一门计算机语言学的基础学科，它不属于任何一门语言，其体现的是几乎所有标准语言的算法的思想。
- 5. 一、数据结构课程的产生与发展 计算机处理的数据 •最初是为了纯粹的数值计算 • 随着计算机的发展，人们逐步探求用计算机来 处理和加工非数值问题：字符、图像、声音、表格等。 处理非数值数据为程序设计提出了新的课题： 数据的表示？+数据的组织存储？+数据对象的有效运算？——〉《数据结构》
- 6. 1、“数据结构”作为一门独立的课程在国外是从 1968年才开始设立的。 2、1968年美国唐·欧·克努特教授开创了数据结构 的最初体系。 3、 “数据结构”在计算机科学中是一门综合性的专业基础课。 4、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。
- 7. 二、数据结构课程的研究内容•计算机处理问题： 问题的数学模型——〉编程求解 数据结构+算法=程序设计 算法：处理问题的策略 数据结构：问题的数学模型
- 8. 2、人机对弈问题
- 9. 三、相关的概念 1、数据：数据是客观事物的符号的表示，在计算机中指能够输入到计算机并被计算机程序处理的符号的总合。是计算机加工的“原料”。 如整数、实数、字符、图像、声音等。
- 10. 2、数据元素：是数据结构中讨论的数据的基本单位，在计算机里通常作为一个整体进行考虑。是数据结构中讨论的基本单位。数据元素有时包含若干数据项。 如描述一个职工的纪录： 数据元素 编号 姓名 性别 年龄 职务 职称 数据项
- 11. 3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。 4、数据结构：是相互存在着某种逻辑关系的数据元素的集合。 带结构的数据元素的集合 指的是数据元素之间存在的关系
- 12. 数据结构包括“逻辑结构” 和“物理结构”两个层面。 逻辑结构：是对数据元素之间的逻辑关系的描述。 物理结构 ：是逻辑结构在计算机中的表示和实现（映像），故又称“存储结构”，存储结构中的每一个数据元素叫做节点，节点中的数据项称为数据域。
- 13. 数据在计算机中表示方式： 顺序映像（顺序存储结构）：以相 对的存储位置表示后继 关系。如前述的职工档案管理程序，所有职工的纪录组成一张表，这张表就使一个顺序存储结构。计算机在为这张表分配存储空间时分配一个连续的存储空间。 非顺序映像（链式存储结构）：
- 14. 链式存储结构里相邻节点间的具体存储位置不是一个顺序关系，查询节点需要借助于指针。 在不同的编程环境中， 存储结构可有不同的描 述方法。当用高级程序 设计语言进行编程时， 通常可用高级编程语言 中提供的数据类型描述 之。
- 15. 5、数据类型： 在程序设计时，我们必须先对变量进行声明，不同的数据类型他的取值范围不同，施加其上的操作也不同： 如：整型 （int） 取值范围：-32768 ~ 32767 可行的操作：+，-，*，/，% 对于浮点型来说，不可以进行% 操作。
- 16. 数据类型 是一个值的集合和定义在此集合上的一组操作的总称。 尽管同一个数据类型在不同的CPU上处理的方法不同，对程序原来说他们是相同的，程序员可以不考虑具体机器的实现方法。也就是说这些数据类型仅仅取决于它的逻辑特性，与在计算机内的实现无关。在数学抽象的角度上看可以称之为抽象数据类型。
- 17. 四、算法和算法分析 算法是为了解决某类问题而规定的一个有限长的操作序列， 算法的特征： 1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出
- 18. 有穷性：在执行有穷步骤之后一定能结束。 确定性：对于每种情况下所应执行的操作， 在算法中都有确切的规定 。 可行性：算法中的所有操作都可以通过已经 实现的基本操作运算有限次实现之 。 有输入输出：每个算法都要有算法需要加工 的数据，经加工后获得一定的结果。
- 19. 1、算法设计的要求： 正确性、可读性、健壮性、效率与低存储量要求。 2、算法分析： 算法的效率：指算法的时间效率。 衡量算法效率的方法： 1、事后统计法： 2、事前分析法：
- 20. 一个算法所需要的时间取决于多个方面：1、算法采用的策略 2、问题的规模 3、采用的语言 4、机器的运算速度 5、编译程序产生的机器代码的质量
- 21. 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 如： int s; for(int i=0;i<n;i++) s+=i; 问题的规模是n,程序的运算工作量和n成线性的增长关系 ，或者说它可以看作是n的函数f(n)。
- 22. 随着规模的增大，算法执行所需要的时间的增长率和f(n)的增长率是相同的。用时间复杂度来表示算法的时间效率， T (n) = O(f(n)) 称T (n) 为算法的(渐近)时间复杂度
- 23. 如何估算时间复杂度？ 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = ∑原操作的执行次数×原操作的执行时间
- 24. 算法的实行时间和原操作的执行次数是成正比的。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
- 25. 如上例中，时间复杂度为O(n) 例： （a） {++x;s+=x;} （b）for (i=1;i<=n;++i) {++x;s+=x;} （c）for (j=1;j<=n;++j) for (k=1;k<=n;k++){++x;s+=x;} 基本操作： {++x;s+=x;} a的执行次数：1 时间复杂度O(1) b的实行次数：n 时间复杂度O(n) c的执行次数：n2 时间复杂度O(n2)
- 26. 例：两矩阵相乘 #define n 100 void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n]) { int i,j,k for (i=1;i<=n;++i) n+1 for (j=1;j<=n;++j) n*(n+1) { C[i][j]=0; n2 for (k=1;k<=n,k++) n2(n+1) C[i][j]=C[i][j]+a[i][k]*b[k][j]; n3 } } 最后的时间复杂度为O(n3)。
- 27. 算法的空间效率： 是指除输入和程序之外的辅助变量所占额外空间。
该用户的其他文档
相关PPT