【精品】公共基础课本

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

1、第1章数据结构与算法1・1算法1.算法的概念：是指解题方案的准确而完整的描述2•算法的基木特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报3.算法的复杂度：吋间复杂度和空间复杂度(1)时间复杂度：算法所需要的计算工作量(算法所执行的基本运算次数)(2)空间复杂度：执行这个算法所需耍的内存空间1.2数据结构的基本概念1.数据结构研究的三个问题(1)逻辑结构：指反应数据元素之间逻辑关系的数据结构(2)存储结构(物理结构)：数据的逻辑结构在计算机存储空间中的存放形式。(3)对各种数据结构进行的运算2.数据结构定义：是指带有结构的数据元素的集合。所谓结

2、构就是指数据元素之间的前后件关系。在数据结构中，没有前件的结点称为根结点，没有后件的结点为终端结点(也叫叶了结点)。3.空的数据结构：一个元素都没有的数据结构。4.数据结构的种类：线性结构与非线性结构。A线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。A非线性结构：如果一个数据结构不是线性结构，则称之为非线性结构。1.3线性表及其顺序存储1.线性表是最简单、最常用的一种线性结构。2.非空线性表的结构特征：(1)有且只有一个根结点，无前件(2)有且只有一个终端(叶子)结点，无后件(3)除根结点与终端结点外，其他所有结点有且只有一个

3、前件，也有且只有一个后件。在线性表中结点的个数n称为线性表的长度,当n二0吋，称为空表。3.线性表顺序存储结构的基本特点:(1)所有元素所占的存储空间是连续的(2)各元素在存储空间中是按逻辑顺序依次存放的4.在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素的平均个数是为n/2o1・4栈和队列1.栈：限定在一端进行插入与删除的线性表。2.栈的结构特点：先进后出或后进先出3.栈的基木运算：入栈运算、退栈运算、读栈顶元素(1)±溢：当栈空间已满，不能再入栈吋，称为“上溢”。(2)下溢：当栈空间已空，不

4、能再出栈时，称为“下溢”。4.队列：允许在一端进行插入、而在另一端进行删除的线性表5.队列的结构特点：先进先出或后进后出6•循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。7•循环队列中元素个数：(分两种情况)(1)队尾指针〉队头指针：元素个数二队尾指针-队头指针(2)队尾指针〈队头指针：元素个数二队尾指针+队列容量-队头指针1.5线性链表1.线性表的链式存储结构称为线性链表。2.在链式存储结构中，每个数据结点由两部分组成：一部分存放数据元素的值，称为数据域；另一部分存放下一结点的存储地址，称为指针域。1.在链式存储结构中，存

5、储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。4.线性链表的优点：在线性链表屮插入或删除一个元素时，不需要移动元素的位置，只需改变指针的指向就行了。5.循环链表的优点：只要指岀表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点,而线性单链表做不到这一点。1.6树与二叉树树是一种简单的非线性结构。树的基本术语：父结点；根结点；子结点；叶子结点；结点的度；树的度；树的深度根结点在第1层。叶子结点没有子树。二叉树：只有一个根结点，每一个结点最多有2颗子树，且分别叫做左

6、子树和右子树。二叉树的基本性质：（1）在二叉树的第k层上，最多有2戸（k＞二1）个结点（2）深度为m的二叉树最多有2-1个结点（3）度为0的结点（叶子结点）是比度为2的结点多一个（4）具有n个结点的二叉树，其深度至少为[log2n]+l＞当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2＞当完全二叉树总结点n为奇数时，叶子节点的个数为：（n+l）/25.二叉树的遍历：前序遍历（根-左-右）；中序遍历（左-根-右）；后序遍历（左-右-根）1.7查找技术1•顺序查找:2.二分法查找：1.8排序技术交换类排序：1.2.3.4.1.2.插入类排序:3.选择类

7、排序:最坏情况下，需比较n次。最坏情况下，需比较1oag2n次。(1)(2)(1)(2)(1)(2)冒泡排序法:n（n-l）/2（最坏情况下）快速排序法:n（n-l）/2（最坏情况下）O（nlogm）（平均情况下）简单插入排序法：n（n-l）/2（最坏情况下）希尔排序法：0（nL5）（最坏情况下）简单选择法：n（n-l）/2（最坏情况下）堆排序法：0（nlog2n）（最坏情况下）第2章程序设计基础1.程序设计风格：清晰第一，效率第二2.注释一般分为：序言性注释和功能性注释3.结构化程序设计的原则：自顶向下，逐步求精，模块化，限制使用goto语句4.结构化

8、程序的基本结构：顺序结构、选择结构、重复结构（循环结构）5.对象：客观卅界中的任