c语言公共基础第一章.doc

第一章 数据结构与算法第一节 算 法一、算法的基本概念算法：是解题方案准确而完整的描述。二、算法的基本特征：* 1)可行性 2）确定性 3）有穷性 4）拥有足够的情报 /*输入输出*/ 三、算法的基本要素：1、算法中对数据的运算和操作 算术运算,关系运算,逻辑运算,数据传输2、算法的控制结构 顺序结构,选择结构,循环结构四、算法设计的基本方法：1、列举法：列举所有可能的情况2、归纳法：通过列举少量特殊情况，经过分析，最后找出一般关系。3、递推：指从已知的初始条件出发， 逐次推出所要求的各中间结果和最后结果。4、递归：复杂-简单-更简单-最简单5、减半递推技术（二分法）：减半是将问题的规模减半，而问题的性质不变，再重复减半（有序表）。6、回溯法：（警察破案）/*结果到条件*/ 线索-试探-成功 失败：返回重新找线索 五、算法的时间复杂度概念：指执行算法所需要的计算工作量（算法所执行的基本运算次数)六、算法的空间复杂度：概念：一般是指执行这个算法时所需要的内存空间。第二节 数据结构的基本概念一、 数据结构数据结构：是指相互关联的数据元素的集合(B)内容:1)表示数据元素的信息(D) 2)各元素之间的前后件关系(R)1、数据的逻辑结构：反映数据元素之间所固有的逻辑关系。 B=（D，R）父儿女例如： D=父亲，儿子，女儿R=（父亲，儿子），（父亲，女儿）D2D5D1D3D4D6 B=D,RD=D1,D2,D3,D4,D5,D6R=D1,D2,D1,D3,D3,D4,D5,D4,D5,D62、数据的存储结构：是指数据的逻辑结构在计算机存储空间中的存放形式。注意：存储结构与逻辑结构可以相同，也可以不同，一种逻辑结构可以有多种存储结构。二、 数据结构的图形表示用方框表示元素（D）用有向线段表示前驱与后继（前件与后件）的关系例如：春夏秋冬 概念： 根结点：没有前驱（前件）的结点(春) 终端结点：没有后继（后件）的结点(冬)三、 线性结构和非线性结构线性结构满足如下条件：1、有且仅有一个根结点；2、每一个结点最多有一个前驱（前件），也最多有一个后继（后件）；3、一个线性结构中插入或删除任何一个结点后还是线性结构；4、如果一个数据结构不是线性结构，则称为非线性结构。第三节 线性表及其顺序存储结构一、 线性表的基本概念1、线性表的容量：存储单元个数2、线性表的长度：元素的个数3、线性表的顺序存储结构的基本特点：1)所有元素所占的存储空间是连续的；2)各数据元素在存储空间中是按逻辑顺序依次存放的。4、元素地址计算公式 Adr(ai)=adr(a1)+(i-1)*k A1起始地址 K每个元素所占空间长度例如：二、 顺序表的插入运算 特点：长度+1 元素向后移动插入前 插入后12345678910123456789101030405020 容量：10长度：4三、 线性表的删除运算 特点：长度-1 元素向前移动删除前 删除后10805020401 12 23 34 45 56 67 7容量：7长度：5第四节 栈和队列DBCA一、 栈及其基本运算 top栈是一种特殊的线性表 bottom栈顶指针（top） 栈底指针（bottom）1、栈特点：1）“先进后出，后进先出”原则；2）只能在一端进行插入与删除元素这一端叫栈顶（top） 2、栈基本运算1）入栈的运算：top+1，然后插入元素 注： 有“上溢”错误。（满）2）出栈运算：首先将栈顶元素赋给一个指定的变量，top-1 注：可能有“下溢”错误。（空）3) 读栈顶元素：将栈顶元素赋给一个指定的变量，栈指针不变。四、 队列及其基本运算队列也是特殊的线性表BACDE Front rear 1、队列的特点： 1）“先进行出，后进后出”的原则； 2）队列允许在一端进行插入、而在另一端进行删除队头指针（front） 删除队尾指针（rear） 插入2、循环队列：将队列存储空间的最后一个位置绕到第一个 rear frontm . .321 循环队列空的状态：s=0,或front=rear=m循环队列满的状态：s=1,且front=rear第五节 线性链表一、 线性链表的基本概念线性表的链式存储结构称为线性链表。指针域数据域 结点数据域：存储数据元素的值指针域：存储后件结点的地址头指针：head指向第一个元素的结点最后一个结点没后件指向空：null 或0二、 线性链表的分类 1.单向链表headan 0a3a2a1 2.双向链表：每个结点设有两个指针域 和一个数据域 F 0 Dhead A 3.循环链表有如下几个特点： 1）在循环链表中增加一个表头节点 2）循环链表中最后一个节点的指针域不是空，而是指向表头节点an A2A14带链的栈：a1a2a3an 0TOP 5带链的队列：a1a2a3an 0front 三、 线性表的链式存储结构的基本特点： 1)所有元素所占的存储空间可以不连续的； 2)各数据元素在存储空间与逻辑顺序可以不一致第六节 树与二叉树一、 树的基本概念树的基本概念：树是一种非线性结构。 1.父结点：结点的前件2.子结点:结点的后件3.根结点:没有前件4.叶子结点:没有后件5.结点的度:一个结点拥有后件个数6.树的度:所有结点中最大的度7.树的深度:树的层次 树图二、 二叉树及其基本性质（非线性结构） 1.二叉树的特点：非空二叉树只有一个根结点。每一个结点最多有两棵子树(左子树,右子树) *2.二叉树的基本性质： 性质1：在二叉树的第k层上，最多有2k-1个结点； 性质2：深度为m的二叉树最多有2m-1个结点；性质3：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个；性质4：具有n个结点的二叉树，其深度至少为log2n+1；三、 满二叉树和完全二叉树满二叉树：每一层上的结点都达到最大值 完全二叉树：除最后一层外，每一层上的结点均达到最大值，在最后一层上只缺少右边的若干结点。/*从左到右依次存放*/ 性质5：满二叉树的第k层上有2 k-1结点，且其深度为m的满二叉树有2m-1个结点。 性质6：具有n个结点的完全二叉树的深度为log2n+1 性质7：设完全二叉树共有n个结点。如果从根结点开始，按层序用自然数1,2,.n进行编号，则对于编号为k(1,2,.n)的结点有以下结论： 若k=1,则该结点为根结点。若k>1，则该结点的父结点编号为INT(k/2) 若2*k<=n,则编号为k的结点的左子结点编号为2*k;否则该结点无左子结点 若2k+1<=n,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点四、 二叉树的遍历： 前序遍历：（根左右) 中序遍历：（左根右) 后序遍历：（左右根)第七节 查找技术一、 顺序查找： 1查找条件：1）无序表 2）有序表的链式存储 2设表长度为N，时间复杂度 最好：1次 平均：n/2次 最坏：n次二、 二分查找：1查找条件：有序表的顺序存储2最坏时间复杂度：log2n 第八节 排序技术一、 交换类排序1.冒泡排序:每一趟是一个来回，从前往后扫描,大的向后移，从后向前扫描，小的向前移 2.快速排序二、 插入类排序 1.简单插入排序：每次只插入一个元素 2.希尔排序： 第1次 h=n/21 第2次 h=n/22 注：n为总长度，结果取整例: 5,1,7,3,1,6,9,3,2,7,6三、 选择排序法1简单选择排序：第一次找一个最小的与第一个交换，第二次找一个次小的与第二个交换 2堆排序：父结点大于子结点 堆的完全二叉树四、 排序的最坏时间复杂度 * 1.冒泡排序：n(n-1)/22.快速排序: n(n-1)/23.简单插入排序: n(n-1)/24.简单选择排序: n(n-1)/25.希尔排序： n1.56.堆排序：nlog2n