公共基础课本

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

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

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

3、K阖，当n=0时，称为空議。3.线性表顺序存储结构的基木特点：(1)所冇元素所占的存储空间是连续的(2)各元素在存储空间中是按逻辑顺用依次存放的4.在长度为n的顺序存储的线性表小，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素的平均个数是为n/2。1.4栈和队列1.栈：限定在一端进行插入与删除的线性表。2.栈的结构特点：先进后出或后进先出3.栈的基木运算：入栈运算、退栈运算、读栈顶元素(1)±溢：当栈空间已满，不能再入栈时，称为“上溢”。(2)卜-溢：当栈空间已空，不能再出栈时，称为"卜-溢”。4.队列：允许在一端进行插入、而在另一端进行删除的线性表5.

4、队列的结构特点：先进先出或后进后出6.循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。7.循环队列屮元素个数：(分两种情况)(1)队尾指针〉队头指针：元素个数=队尾指针・队头指针(2)队尾指针＜队头指针：元索个数=队尾指针+队列容量-队头指针1.5线性链表1.线性表的链式存储结构称为线性链表。2.在链式存储结构中，每个数据结点由两部分纽成：一部分存放数据元索的值，称为数据域；另-部分存放下一结点的存储地址，称为指针域。3.在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元索•的逻辑关系可以不一致,而数据元索Z间的逻辑关系是由指

5、针域來确定的。1.线性链表的优点：在线性链表中插入或删除-个元素时，不需要移动元素的位置，只需改变指针的指向就行了。2.循环链农的优点：只耍指出农中任何一个结点的位置，就可以从它出发访问到农中其他所有的结点，而线性单链农做不到这一点。1.6树与二叉树1.树是一种简单的非线性结构。2.树的基本术语：父结点；根结点；子结点；叶子结点；结点的度；树的度；树的深度根结点在第1层。叶子结点没有子树。3.二叉树：只有一个根结点，每一个结点最多有2颗子树，且分别叫做左子树和右子树。4.二叉树的基木性质：（1）在二叉树的第k层上，最多有2小（k〉二1）个结点（2）深度为m的二叉树最多有2"-1个结点

6、（3）度为0的结点（叶子结点）是比度为2的结点多一个（4）具有n个结点的二叉树，其深度至少为[iog2n]+l》当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2》当完全二叉树总结点n为奇数时，叶子节点的个数为：（n+l）/25.二叉树的遍历：前序遍历（根-左-右）；中序遍历（左-根-右）；后序遍历（左-右-根）1.7査找技术1•顺序查找：最坏情况下，需比较n次。2.二分法查找：绘坏情况下，需比较loag2n次。1.8排序技术1.2.3.交换类排序：（1）（2）插入类排序：（1）（2）选择类排序：（1）（2）冒泡排序法:n（n-l）/2（最坏情况下）快速排序法：n（n-l）/2（

7、最坏情况下）0（nlog2n）（平均情况下）简单插入排序法：n（n-l）/2（故坏情况下）希尔排序法：0（r?"）（域坏情况下）简单选择法：n（n-l）/2（瑕坏情况下）堆排序法：（Xnlogm）（最坏悄况下）第2章程序设计基础1.程序设计风格：清晰第一，效率笫二2.注释一般分为：序言性注释和功能性注释3.结构化程序设计的原则：自顶向下，逐步求粘，模块化，限制使用goto语句4.结构化程序的基本结构：顺序结构、选择结构、重复结构（循环结构）5.对象：客观世