公共基础课本 2.doc

第1章数据结构与算法 1.1算法 1．算法的概念：是指解题方案的准确而完整的描述 2．算法的基本特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报 3．算法的复杂度：时间复杂度和空间复杂度 (1)时间复杂度：算法所需要的计算工作量（算法所执行的基本运算次数） (2)空间复杂度：执行这个算法所需要的内存空间 1.2数据结构的基本概念 1．数据结构研究的三个问题 (1)逻辑结构：指反应数据元素之间逻辑关系的数据结构 (2)存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。 (3)对各种数据结构进行的运算 2．数据结构定义：是指带有结构的数据元素的集合。所谓结构就是指数据元素之间的前后件关系。 在数据结构中，没有前件的结点称为根结点，没有后件的结点为终端结点（也叫叶子结点）。 3．空的数据结构：一个元素都没有的数据结构。 4．数据结构的种类：线性结构与非线性结构。 线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。 非线性结构：如果一个数据结构不是线性结构，则称之为非线性结构。 1.3线性表及其顺序存储 1．线性表是最简单、最常用的一种线性结构。 2．非空线性表的结构特征： (1)有且只有一个根结点，无前件 (2)有且只有一个终端（叶子）结点，无后件 (3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 在线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。 3．线性表顺序存储结构的基本特点： (1)所有元素所占的存储空间是连续的 (2)各元素在存储空间中是按逻辑顺序依次存放的 4．在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素的平均个数是为n/2。 1.4栈和队列 1．栈：限定在一端进行插入与删除的线性表。 2．栈的结构特点： 先进后出 或 后进先出 3．栈的基本运算：入栈运算、退栈运算、读栈顶元素 (1)上溢：当栈空间已满，不能再入栈时，称为“上溢”。 (2)下溢：当栈空间已空，不能再出栈时，称为“下溢”。 4．队列：允许在一端进行插入、而在另一端进行删除的线性表 5．队列的结构特点： 先进先出 或 后进后出 6．循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。 7．循环队列中元素个数：(分两种情况) (1)队尾指针队头指针： 元素个数 = 队尾指针 - 队头指针 (2)队尾指针队头指针： 元素个数 = 队尾指针 + 队列容量 – 队头指针 1.5线性链表 1．线性表的链式存储结构称为线性链表。 2．在链式存储结构中，每个数据结点由两部分组成：一部分存放数据元素的值，称为数据域；另一部分存放下一结点的存储地址，称为指针域。 3．在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 4．线性链表的优点：在线性链表中插入或删除一个元素时，不需要移动元素的位置，只需改变指针的指向就行了。 5．循环链表的优点：只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。 1.6树与二叉树 1．树是一种简单的非线性结构。 2．树的基本术语：父结点；根结点；子结点；叶子结点；结点的度；树的度；树的深度 根结点在第1层。叶子结点没有子树。 3．二叉树：只有一个根结点，每一个结点最多有2颗子树，且分别叫做左子树和右子树。 4．二叉树的基本性质： (1)在二叉树的第k层上，最多有2k-1（k=1）个结点 (2)深度为m的二叉树最多有2m-1个结点 (3)度为0的结点（叶子结点）是比度为2的结点多一个 (4)具有n个结点的二叉树，其深度至少为[log2n]+1 当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2 当完全二叉树总结点n为奇数时，叶子节点的个数为：(n+1)/2 5．二叉树的遍历：前序遍历（根-左-右）；中序遍历（左-根-右）；后序遍历（左-右-根） 1.7查找技术 1．顺序查找： 最坏情况下，需比较n次。 2．二分法查找：最坏情况下，需比较loag2n次。 1.8排序技术 1．交换类排序：（1）冒泡排序法：n(n-1)/2（最坏情况下） （2）快速排序法：n(n-1)/2（最坏情况下） O(nlog2n)（平均情况下） 2．插入类排序：（1）简单插入排序法：n(n-1)/2（最坏情况下） （2）希尔排序法：O(n1. 5)（最坏情况下） 3．选择类排序：（1）简单选择法：n(n-1)/2（最坏情况下） （2）堆排序法： O(nlog2n) （最坏情况下） 第2章程序设计基础