c语言公共基础知识知识点(自己整理)

《c语言公共基础知识知识点(自己整理)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章数据结构与算法1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。2.算法的有穷性是指算法程序的运行时间是有限的。3.算法的吋间复杂度:执行算法所需要的计算工作量(基本运算次数)。算法的空间复杂度:这个算法所需要的内存空间。两者之间没有必然直接的联系4.程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、处理的数据5等有关。5.线性结构的两大条件：有且只有一个根节点；每一个结点最多只有一个前件，也最多宥一个盾件。6.线性表的顺序存储结构具备如下两个基本特征:(1)线性表中的所有元素所占的存储空问是连续的:(2)

2、线性表屮各数据元素在存储空间屮是按逻辑顺序依次存放的。7.钱是先进后出的线性表。8.队列是先进先出的线性表。9.栈和队列都是线性结构。10.栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。11.循环队列中元素的个数是由队头指针和队尾指针共同决定。12.树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。13.循环队列中的元素个数随队头指针与队尾指针的变化血动态变化。14.由于入队时尾指针句前追赶头指针，出队时头指针向前追赶尾指针，故队空和M吋，头尾指针均相等。

3、15.在栈中，栈底指针不变，桉中元素随栈顶指针的变化而动态变化。16.循环队列是队列的一种顺序存储结构。17.循环链表和双向链表都是线性结构。18.线性链表中数据的插入和删除都不需要移动表中的元素,只需改变结点的指针域即可。19.线性链表中的各数据结点的存储空间吋以不连续，各数据元素的存储顺序与逻辑顺序可以不一致。20.链式存储结构既可以针对线性结构也可以针对非线性结构。21.顺序存储结构的存储一定是连续的，链式存储结构的存储空问不一定是连续他。22.线性表(线性结构)的链式存储结构所需要的存储空间•般要多于顺序存储结构。23.栈支持子

4、程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序屮调用子程序的位置，继续向下执行。24.在任意一棵二叉树中，度为0的叶子节点总是比度为2的节点多一个。25.满二叉树是指这样的一种二叉树：除最盾一M外，每一足上的所宥结点都宥两个子结点。26.完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。2323满二乂树完全二叉树27.二叉树的遍1.前序遍历：①访问根结点；②前序遍历左子树;③

5、前序遍历右子树2.屮序逾历：①屮序過历左子树;②访问根结点；③屮序過历右子树3.后序遍历：①后序遍历左子树;②后序遍历6子树;③访W根结点28.一颗二叉树的前序遍历序列为ABDGCFK,中序遍历序为DGBAFCK,则结点的后序遍历序序列为什么？中序：顺序为左根右。并且，在遍历左、右子树时,仍然先遍历左子树，然后访问根结点，最后遍历右T树。29.顺序查找：最好情况：1次；最坏情况：n次；需要比较n/2次，复杂度为0(n)。二分法查找：最坏情况：1()g2Z?次；复杂度为0(log，)27.排序屮：最坏情况冒泡排序，简单插入排序，简单选择排

6、序，选择排序的最坏情况吋间都为而堆排序的最坏情况时问为0(r,

7、(,g2n)冒泡排序，简单插入排序，简单选择排序，选择排序的最坏情况比较次数都为n(n-l)/2次Ifij堆排序的最坏情况次数为〃log2〃次第二章程序设计基础1.结构化程序设计的基本原则：自顶而下；逐步求精；模块化；限制goto语句使用。2.结构化程序所要求的基本结构：顺序结构；选择（分支）结构；重复（循环）结构。3.对象的基本特点：标识唯一性；分类性；多态性；封装性；模块独立性好。4.对象之问进行通信的构造叫做消息。5.对象的多态性是指同•个操作可以是不同对象的行为,导

8、致完全不同的行为。6.对象不_定必须有继承性。7.继承是面向对象的方法的一个主耍特征。8.继承是指类之间共享屌性和操作的机制。第三章软件工程基础1.1ft指的是计算机系统中与硬件和互依赖的另一部分，也拈程序、数据和有关的文档。2.软件生命周期是指软件产品从提也、实現、使用维护到停止使用退役的过程。3.软件的生命周期宥三大阶段：一.软件定义期：问题定义;可行性研究;需求分析。二.软件开发期：软件设汁（概要设计和详细设计）；软件实现;软件测试。三.运行维护期：运行和维护。4.需求分析阶段的主要工作：需求获取;需求分析;编写需求规格说明书;需

9、求评宙。5.需求分析阶段（结构化分析方法）常用的工具：数据流图（DFD）;数据字典（DD）;判定表;判定树;6.数据字典（DD）是结构化分析的核心。7.软件需求规格说明书有以下几个方面的作用：①便于用户、开