公共基础(课本)

《公共基础(课本)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、公共基础（课本）公共基础课木总结第1章数据结构与算法1.1算法算法的基木特征：可行性、确定性、冇穷性（冇限的时间）、拥冇足够的情报。*算法的控制结构：算法中各操作之间的执彳J•顺序。包括：顺序、选择、循环算法的复杂度：时间复朵度（算法所需要的计算工作量，即算法所执行的基本运算次数）、空间复杂度（执行这个算法所需耍的内存空间）1.2数据结构的皐本概念数据纠构I在数据结构中没有前件的结点称为根结点，没有后件的结点为叶子结点（终端结点）。数据结构研究的三个问题：1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结

2、构。3）対各种数据结构进行的运算。数据的存储结构（物理结构）:数据的逻辑结构在计算机存储空间中的存放形式。（常用：顺序、链接、索引等结构）数据结构分类：线性结构、非线性结构。窃线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。（线性表、栈、队列、线性链表）*非线性结构：不满足线性结构特点的数据结构。树、二叉树、图1.3线性表及其顺序存储线性表由一组数据元索组成。数据的逻辑结构：指反应数据元素之间逻辑关系的数据结构。线性表屮的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数n称为线性表的长度。线性表可以为空表：

3、n=0o线性表是一种存储结构，它的存储方式：顺序和链式。线性表的顺序存储结构有两个基本特点：1.所有元索所占的存储空间是连续的。2.各元索在存储空间中是按逻辑顺序依次存放的，前后件两个元索在存储空间中是紧邻的。在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，它们所需移动元素的平均个数是为n/2。1.4栈和队列H栈顶：允许插入与删除的一端。栈底：不允许插入与删除的一端。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈中冗索个数I-栈顶+1栈的基本运算：入栈运算（上溢）、退栈运算（下溢）、读栈顶元索栈的存储方式和线性表类似，也冇两种：顺序栈和链式栈。队尾（

4、rear）:允许插入的一-端。队头（front）:允许删除的一•端。队列是按照"先进先出”或“后进后出”的原则组织数据的。駅中元素个数-対头（队尾〉对头）队中元索个数I-对头+容量（队尾〈对头）线性链表队列的基本运算：入队运算、退队运算循环队列：将队列存储空间的最后一个位世绕到第一个位置，形成逻辑上的坏状空间1.5线性链表*在链式存储结构屮，每个数据结点由两部分组成：数据域（存放数据元索的值）父结点、指针域（存放下一结点的存储地址）。*在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不-•致，而数据元素Z间的逻辑关系是由指针域來确定的。*线

5、性链表的优点：在线性链表中插入或删除一个元素时，不需要移动元素的位置，只需改变指针的指向就行了。*循坏链表的优点：只要指出表屮任何一个结点的位置，就可以从它出发访问到表中具他所冇的结点，而线性单链表做不到这一点。栈和队列也可采用链式存储结构1.6树与二叉树公共基础课本总结第1页共5页叶子结点没冇子树。-•义树的性质2颗子树，且分别称为该结点的左子树与右子树。0（叶了结点）、1（只有1颗了树）或2（有2颗了树）1.在二叉树的第k层上，最多有22.深度为m的二叉树最多有2满二叉树

6、完全二冬树mk-1（k>=l）个结点T个结点3.度为0的结点（叶子结点）总是比度为2的结点多一个4.具有n个结点

7、的二叉树，其深度至少为[log2n]+l5.具有n个结点的完全二叉树，深度为[log2n]+l:义树的遍助2各了结点。*根据完全二叉树的定义可得岀：度为1的结点的个数为0或1。顺序金找一般二叉树采用链式存储结构，对于满二叉树与完全二叉树来说，可以按层序进行顺序存储。分类：前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）:分汕作找*当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2*当完全二叉树总结点n为奇数时，叶子节点的个数为：（n+l）/21.7查找技术n（最坏）。适用范甬：无序线性表、线性表的链式存储结构。Iog2n（最坏）。适用范围：顺序存储的线性表。1・8排序技术交

8、换类持:序插入次摊序选抒荚排序n（n-l）/2（最坏）快速排序法:n（n-l）/2（最坏）0（nlog2n）（平均）秤序设汁凤格

9、n（n~l）/2（最坏）希尔排序法：0（n）（最坏）n（n-l）/2（最坏）堆排序法：（）（nl（）g结构化秤序设计酹丽

10、结鞫化程序的惟木结构

11、2n）（最坏）1.5笫2面向对彖方法拘优点

12、章程序设计基础1.1程序设计方法与风格

13、对網注释-•般分为：序言性注释和功能性注释2.2结构化程序设计goto语句囲I