文档介绍：数据的存储结构:数据在计算机中的存储方式。顺序存储(常用于存储具有线性结构的数据)链式存储(运用到指针)数据的存储方式索引存储(每个结点有唯一的索引号)散列存储(思想:构造一个从集合K到存储区域M的一个函数h)二、算法有穷性:一个算法必须在有穷步之后终止,即必须在有限时间内完成。确定性:算法的每一步必须有确切的定义,无二义性。可行性:算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。算法设计的要求:正确、可读、健壮、高效。算法的时间复杂度:指执行算法所需要的计算工作量,即算法执行过程中所需要的基本运算的次数。算法的空间复杂度:指执行这个算法所需要的内存空间。算法的平均情况下=(最好情况下+最坏情况下)/2O(1)常阶数时间复杂度O(n)线性阶O(n2)平方阶三、线性表A1A2A3A4A5…A1是A2的直接前驱,A2是A1的直接后继。顺序存储(简称顺序表)线性表的存储方式链式存储(简称线性链表)按链的类别分单链表线性链表循环链表双向链表双向循环链表静态链表按节点分配方式分动态链表四、栈(先进后出的线性表)栈顶:允许插入和删除的一端。栈低:不允许插入和删除的另一端。栈的存储方式顺序存储链式存储五、队列定义:一端插入操作,一端删除操作;(先进先出的线性表)允许插入的一端为队尾,允许删除的一端为对头。注意:头指针并不是结点,只是一个指针,头指针可以没有data域。六、树结点的度:结点拥有的子树个数。树的度:树中所有结点的度的最大值。叶子:度为0的结点(终端结点)。分支结点:度不为0的结点(非终端结点)。树的深度:树中结点的最大层次值,又名树的高度。双亲与孩子:结点的子树的根称为该结点的孩子结点,而该结点称作孩子结点的双亲结点。祖先与子孙:结点的祖先是指从根到该结点经历分支上得所有结点,以结点为根的子树中的任一结点都是该结点的子孙。兄弟:具有同一双亲结点的孩子结点之间互称为兄弟(有堂兄弟之分)。七、二叉树特点1、每个结点最多有两棵子树。2、子树有左右次序。满二叉树(有2k-1个结点)特点1、每一层的结点数都是最大值,即它是具有最多结点数的二叉树。2、不存在度数为1的结点,且树叶都在最底层。完全二叉树特点1、若某个结点没有左孩子,则它一定没有右孩子。2、完全二叉树的任一结点的右分支下的子孙的最大层次为L,则其左分支下的子孙最大层次为L或L+1。满二叉树与完全二叉树的关系1、满二叉树是完全二叉树,完全二叉树不一定是满二叉树2、满二叉树最底层,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。二叉树的存储方式顺序存储链式存储二叉树是非线性结构先序遍历:先访问根结点,然后访问左子树、右子树,又称根序访问。中序遍历:先访问左子树,然后访问根结点、右子树。后序遍历:先访问左子树,然后访问右子树、根结点。八、软件开发软件开发方法是在总体设计阶段完成的任务。软件开发工具是在实现阶段完成的任务。软件开发费用是在可行性研究阶段完成的任务。软件系统功能是在需求分析阶段完成的任务。]九、图无向图:顶点V的度是和V想并联的边的数目。有向图:分为入度和出度。入度:把指向V的边的条数称为顶点V的入度,ID(V)。出度:把从顶点V发出去的边的条数称为顶点V的出度,OD(V)。D(V)=ID(V)+OD(V).邻接矩阵存储图的存储方式邻接表存储十、排序直接插入排序法插入排序希尔排序法冒泡排序法交换排序法快速排序法直接选择排序法选择排序法堆排序排序分为内排序(在内存中处理)和外排序(在内存不足情况下,使用外存)。关键码可以是排序码,但排序码不一定是关键码。如:把一个班的所有同学的学号、年龄、身高看成一个记录的三个字段;如果按全班同学的身高进行排序,身高是排序码,但不是关键码;如果按全班同学的学号进行排序,学号是排序码,也是关键码,因为每个学生的学号不同。十一、文件操作feof(文件指针);功能:当feof的返回值为零时,表示文件未结束;当返回值为非零值时,则表示文件结束。ferror(文件指针);功能:当ferror函数的返回值为零时,则表示文件未出错;当返回值为非零值时则表示文件出错了。clearer(文件指针);功能:用于清除文件指针所指向的文件的出错标志和文件结束标志,使它们的值为零。假设在调用一个输入函数时出现错误,这时ferror函数值为一个非零值,在调用clearer函数后,ferror函数值为零。字符的输入和输出fputc(ch,fp);将一个字符输出到文件,当输出成功时,fputc的返回值为所输出的字符;当输出失败时,fputc的返回值为EOF,它的值为-=fgetc(fp);正确写法;fgetc(ch,fp);错误写法。EOF函数适用,while(ch!=EOF);文件使用方式含义“r”(只读)为输入打开一个文本文件“