C语言学习资料汇编.doc

算法一般具有4个基本特征：可行性、确定性、有穷性、拥有足够的情报。 算法的基本结构是：顺序结构、选择结构、循环结构。 算法的复杂度分为时间复杂度和空间复杂度。 时间复杂度，执行算法所需要的计算工作量（次数）。 空间复杂度，执行算法所需要的内存空间。 数据的逻辑结构：是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关 数据的存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。 数据结构：线性结构（线性表、栈、队列、链表）和非线性结构（树）。 线性表:1 有且只有一个根结点，它无前件。 2 有且只有一个终端结点，它无后件。 3 其他结点，只一个前件，一个后件。 线性表的顺序存储结构特点： 1线性表中所有元素所占的存储空间是连续的； 2线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 栈：（一种特殊的线性表）只允许在一端插入，删除，改写数据。 原则为先进后出。 进栈出栈顺序。 例：进栈顺序：ABCD123 出栈顺序：321DCBA 队列：允许在一端进行插入，而另一端进行删除的线性表。 允许插入一端，尾指针。允许删除的一端，头指针。 原则为先进先出。 循环队列中元素的个数是由队头指针和队尾指针共同决定。循环队列的头指针为front，尾指针为rear，容量为maxSize，则循环队列中元素的个数是【 (rear-front+maxSize) mod maxSize】。线性链表是线性表的链式存储结构。用链表表示线性表的优点是便于插入和删除操作。 线性链表的存储空间不一定连续，且个元素的存储顺序是任意的 满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。 完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 5具有n个结点的完全二叉树，其深度为（log2n）+1 6 设完全二叉树有n个结点，进行编号，取其中一个结点为k， （1）若k=1，说明该结点为根结点，若k?1,则O(n1.5 ) 次。 最坏情况下，堆排序法，O(nlog2n)次。 相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。 程序设计基础： 结构化程序设计的原则：1.自顶向下 2.逐步求精 3.模块化 4.限制使用goto语句 结构化程序设计主要强调程序的易读性 良好的程序设计风格是程序应简单、清晰、可读性好 对象的基本特点：1.标识的惟一性 2.分类性 3.多态性 4.封装性 5.模块独立性好 类是具有共同属性，共同方法的对象的集合。 消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一数据流和控制流。 一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多个参数。 继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。 多态性是对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动。 在面向对象方法中，信息隐蔽是通过对象的封装性来实现的 软件工程基础 软件工程包括3个要素，即方法，工具和过程。 方法是完成软件工程项目的技术手段 工具支持软件的开发、管理、文档生成 过程支持软件开发的各个环节的控制、管理 软件生命周期分为软件定义，软件开发及软件运行维护三个阶段。 软件定义期：包括问题定义、可行性研究和需求分析3个阶段； 软件开发期：包括概要设计、详细设计、实现和测试4个阶段； 运行维护期：即运行维护阶段。 软件生命周期的主要活动阶段：可行性分析、需求分析、软件设计、软件实现、软件测试、运行和维护。 常见的需求分析方法（1）结构化分析方法---主要包括面向数据流的结构化分析方法SA； 面向数据结构的Jackson方法JSD； 面向数据结构的结构化数据系统开发方法DSSD。 （2）面向对象的分析方法OOA 结构化分析方法工具---（1）数据流图DFD，记住DFD图的几个符号： （2）数据字典DD （3）判定树 （4）判定表 程序结构图（SC），N-S图，问题分析图（PAD） 程序流程图（PFD）的几个符号： 从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 从工程管理角度