c语言公共基础知识.doc

实用标准:..:是指解题方案的准确而完整的描述。算法复杂度:算法时间复杂度和算法空间复杂度。两个之间没有联系的。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;线性结构条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。线性表的顺序存储结构具有以下两个基本特点:(1)线性表中所有元素的所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。。1、先进后出FILO;1、支持子程序调用;2、具有记忆功能;3、可以不用顺序存放数据;4、只能够在top首部进行操作,bottom是绝对不动的;5、栈的存放数据的个数为num=(bottom–top)+1;队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。1、Rear指针指向队尾,front指针指向队头。3、先进先出FIFO,或者是后进后出LILO2、循环队列里面的个数计算方法:A、rear>front的时候,num=rear–front;B、rear<front的时候,num=rear+n–front;,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构,也可用于表示非线性结构。,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。二叉树的基本性质:必考的题目(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;(2)深度为m的二叉树最多有2m-1个结点;(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;(4)二叉树中n=n0+n1+n2满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历:(一般画个图要你把顺序写出来)(1)前序遍历(DLR),根左右(2)中序遍历(LDR),左根右(3)后序遍历(LRD):长度为n的线性表,找出一个数据,最差的情况为比较n次。长度为n的线性表,找出一个最大数据,最差的情况为比较n-1次。二分法查找只适用于顺序存储的有序表