Birdgu C 语言公共知识基础部分 读书札记- 1 -C 语言公共基础知识Birdgu四川成都2012.9.15Birdgu C 语言公共知识基础部分 读书札记- 2 -C 语言基础知识 -1、 算法： 算法的时间复杂度是指执行算法所需要的计算工作量； 算法的有穷性是指算法程序的运行时间是有限的； 算法是指对解决问题准确而完整的描述； 算法的空间复杂度是指执行算法所需要的内存空间； 算法的 4 个特征：可行性、确定性、有穷性和拥有足够的情报；2、E-R 图： 矩形用来表示实体集 椭圆表示属性 菱形表示联系3、结构化分析常用的工具：数据流图（DFD） 、数据字典、判定表、判定树；4、 详细设计过程中常用的图形工具：程序流程图、N-S 图、PAD 图；5、 数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段，其中数据独立性最高的阶段是数据库系统；6、 数据库设计分阶段：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段；软件生命周期分为软件定义阶段、软件开发阶段、软件维护阶段；定义阶段包括（问题定义、可行性研究、需求分析） ，软件开发阶段包括（概要设计、详细设计、实现和测试） ，软件维护包括（软件的运行、维护） ；7、 队列：队列是一种操作受限的线性表。它允许在线性表的一段进行插入操作，另一端进行删除操作。其中允许插入的一端称为队尾（rear） ，允许删除的一端称为队首（front） 。队列具有先进先出的特点；当 frontrear 时，循环队列中元素的个数为 N front + rear（N 为循环队列的容量）;8、 软件危机：软件危机主要表现：软件需求的增长得不到满足；软件开发成本和进度无法控制；软件质量难以保证；软件可维护性差；软件的成本不断提高；软件开发生产率的提高赶不上硬件的发展和应用需求的增长；9、 数据库按数据模型分为层次型数据库、网状型数据库、关系型数据库；数据模型即是数据之间的联系方式；10、软件需求规格说明书应具备完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是无歧义性；11、数据库系统内部徐具有三级模式及二级映射，三级模式分别是概念模式、内模式和外模式，内模式给出了数据库物理存储结构与物理存取方法；二级映射分别是概念模式到内模式以及外模式到概念模式的映射，这种三级模式和二级映射构成数据库系统内部的抽象结构体系；12、软件测试的目的是暴露错误，评价程序的可靠性；而软件调试的目的是发现错误的位置并改正错误；13、关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、参照完整性、自定义完整性；14、软件测试可分为白盒测试和黑盒测试；程序内部逻辑设计测试用例属于白盒测试；黑Birdgu C 语言公共知识基础部分 读书札记- 3 -盒测试不考虑程序的内部结构，只根据程序功能导出测试；常用的黑盒测试方法有等价类划分法、边界值分析法和错误推测法，主要用于软件确认测试；15、栈是一段插入和删除数据的线性表，栈是按照 先进后出 的原则组织数据，栈具有记忆功能，带链的栈的结点存储顺序与其逻辑顺序可以不一致；16、对象的基本特点有：标识唯一性、分类性、多态性、封装性、模块独立性；17、软件测试分为 4 过程：单元测试、集成测试、验收测试、系统测试；18、在二维表中元组是有 n 个元组分量组成的，元组分量是最小的单位；19、数据库应用系统的核心问题是数据库设计；20、数据的储存结构也称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放形式；21、常见的过程设计工具有图形工具（流程图、N-S 图、PAD 图、HIPO 图） 、表格工具（判定表）和语言工具（PDL） ；22、数据库管理系统是一种软件系统，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库系统的核心；23、关系数据库系统采用关系模型作为数九的组织形式。在关系模型中用二维表来表示实体及实体之间的联系；24、面向对象设计方法的三个基本特性即封装、多态、继承；结构化程序设计的原则是：自顶向下、逐步求精、 、模块化和限制使用 goto 语句；25、数据字典是对数据流图中所有元素定义的集合，是结构化分析的核心；26、数据库存取的单位可以是字段或者记录。在职员管理数据库中，一个职员的信息是由全部字段组成的一个记录；27、结构化分析方法是结构化程序设计理念在软件需求分析阶段的运用。而结构化分析就是用数据流图、数据字典、结构化语言、判定树、判定表等工具，来建立一种新的、称为结构化规格说明的目标文档；28、软件测试用例包括输入值集和输出值集，测试用例是软件测试的核心；29、二维表中的一列称为属性；30、为了适应关系数据库系统的处理，必须将 E-R 图转换成关系模式，这是逻辑设计的主要内容；31、软件工程包括三个要素：方法、工具和过程；32、确认测试的任务是验证软件的功能和性能及其他特征是否满足了需求规格说明中确定的各种需求以及软件配置是否完全、正确；33、数据的独立性是指数据库中数据独立于应用程序且不依赖于应用程序，即数据的逻辑结构、存储结构与存放方式的改变不会影响应用程序；34 关系运算的定义35、数据库中有 3 种主要程序设计语言类别的语句：数据定义语句（DDL） 、数据操作语句(DML)及数据控制语句（ DCL） 。其中数据操作语言主要负责数据的插入、删除、查询、修改等操作；36、软件生命周期可分为软件定义、软件开发和软件运行维护 3 个阶段；软件开发期包括概要设计、详细设计、实现和测试 4 个阶段。37、数据库管理系统是数据库系统的核心，它位于用户和操作系统之间，属于系统软件。数据库系统由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台 5 部分组成。数据库技术的发展经历了 3 个阶段，人工管理、文件系统和数据库系统，数据共享最好的阶段是数据库系统阶段，数据库中的数据独立于应用程序而不依赖于应用程序；Birdgu C 语言公共知识基础部分 读书札记- 4 -38、数据库设计分为 6 个设计阶段：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段；39、需求分析阶段常用的工具是数据流图和数据字典；40、线性结构有：线性表、栈、队列、串；41、数据流图是结构化方法的需求分析工具，是描述数据处理过程的工具，是逻辑模型的图形表示，它直接支持系统的功能建模；42、将 E-R 图转换为关系模型实际上就是要将实体、实体属性和实体之间的联系转换为一组关系模式，E-R 图中的属性将被转换为关系中的属性，联系即被转换为关系；43、数据结构指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间逻辑关系；存储结构为数据的逻辑结构在计算机储存空间中的存放形式，有顺序存储、链式储存、引索储存和散列储存 4 中方式；44、二叉树： 在二叉树的第 K 层上至多有 2（K-1） 个结点（K=1 ） ； 深度为 M 的二叉树至多有 2（M-1 ） 个结点； 对任何一棵二叉树，度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个； 二叉树的遍历：前序遍历：访问根节点前序遍历左子树前序遍历右子树；中序遍历：中序遍历左子树访问根结点中序遍历右子树；后序遍历：后序遍历左子树后序遍历右子树访问根结点；45、查找技术： 顺序查找：最坏情况下，需要比较 N 次才能找到该元素； 二分查找：二分查找的限制条件（必须是顺序储存结构、必须有序排列） ，最坏情况下，二分查找需要比较 log2n；46、排序技术： 冒泡排序：最坏情况下，对长度为 N 的线性表排序，冒泡排序需要比较的次数为 N(N-1)/2； 简单插入排序：最坏情况下，比较次数 N(N-1)/2，移动次数 N(N-1)/2； 简单选择排序：最坏情况需要比较 N(N-1)/2；47、数据流图（DFD）： 箭头代表数据流； 圆或椭圆代表加工； 双杠代表储存文件； 方框代表源或潭；48、位运算：a&b相同位的两个数字都为 1，则为 1；若有一个不为 1，则为 0； a|b相同位只要一个为 1 即为 1；a b相同位不同则为 1，相同则为 0； a取反；a b 右移 b 位 ；49、特殊关系运算：口诀：选择抽行、投影抽列、连接合并去残、笛积两两交合、自然连接笛积后选择等值然后去掉重复属性；Birdgu C 语言公共知识基础部分 读书札记- 5 -50、+（或-）的运算结果是使运算对象增 1（或减 1）；运算对象可以是整形变量、实型变量、字符型变量，但不能是常量或表达式；+（或- ）的结合方向是自右向左；51、C 语言中逗号运算符的优先级最低，逗号语句的值是最后一个表达式；52、strcpy（字符数组，字符串），将字符串完整的复制到字符数组中，并将字符数组中原有的内容覆盖；复制时，字符数组应该足够大，复制时连同0一起复制；Strcat(字符数组，字符串)，将字符串连接到字符数组尾端，并在其后加0；53、sizeof 是返回字符串在内存中所占用的空间，是真正的长度；Strlen 是返回字符串的长度，遇到0就结束，不包括0；54、函数的静态局部变量在编译时就赋初值，即只赋初值一次；55、getchar（）的作用是从终端输入一个字符，且只能接受一个字符（回车也是一个字符）；56、contiue 语句的作用是跳过本次循环体中余下尚未执行的语句，接着再一次进行循环条件的判定；57、强制类型转换表示为：（类型名）表达式；如：（int）f；58、getchar 函数读入一个字符时可以得到第一个输入字符的 ASCII 码，无法通过输入相应字符的 ASCII 码得到该字符；59、C 语言得 4 种基本变量：基本型 int、短整型 short int、长整型 long int、无符号型（unsigned int、unsigned short、unsigned long）；60、用%s 格式输入字符串时，空格和回车都作为输入数据的分隔符，不能被读入；61、getchar 函数输入字符串时，见到回车才认为结束；