第一章 基本数据结构与算法.ppt

公共基础知识（二级）;笔试考试题型;数据结构概论;数据结构概论;一、数据结构概论;一、数据结构概论;二、算法及其描述;二、算法及其描述;二、算法及其描述;二、算法及其描述;三、线性表;三、线性表;三、线性表;三、线性表;四、线性单链表、双向链表与循环链表的结构及其基本运算;线性表的链式存储结构—单链表 单链表表示法的基本思想是用指针表示结点间的逻辑关系。结点形式为： 所有结点通过指针的链接而组织成单链表。 插入、册除运算在单链表上的实现 插入:INSERT(L,x,i) 在单链表上找到插入位置 生成一个值为X的新结点 将新结点链入 C语言描述： s-next=p-next;p-next=s;;四、线性单链表、双向链表与循环链表;四、线性单链表、双向链表与循环链表;四、线性单链表、双向链表与循环链表;五、栈和队列;五、栈和队列;五、栈和队列;五、栈和队列;六、树;六、树;二叉树的定义 二叉树的逻辑结构、特点和5种基本形态 二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件： 有且仅有一个称为根的结点 根结点外的其余结点分为两个互不相交的集合T1、T2，且T1、T2都是二叉树，并且有序（ T1在T2之前） ，它们分别称为根的左右子树。 二叉树的5种基本形态：;二叉树的定义 满二叉树和完全二叉树的概念 满二叉树是指：除最后一层外，每一层上的所有结点都有两个子结点。深度为k的二叉树具有2k-1个结点。在第i(i=1)层上最多有2i-1个结点。 完全二叉树是指：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。满二叉树也是完全二叉树。 ;二叉树的顺序存储结构 二叉树存储的基本思想（按层编号） 按层编号是指将一棵树中的所有结点按从第一层到最大层、每层从左到右顺序依次标记为1,2,…,n。 对于完全二叉树，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。 对于非完全二叉树，则通过在非完全二叉树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。 二叉树的顺序存储结构图;二叉树的顺序存储结构 二叉树的链式存储结构 二叉链表的结点形式如右： data域称为数据域； lchild称为左孩子指针域； rchild称为右孩子指针域。用于指向本结点的指针（左或右指针） 二叉链表中所有存储结点通过它们的左、右指针的链接而形成整体 每个二叉链表还必须有一个指向根结点的指针，即根指针。 对二叉链表的访问只能从根结点开始。 每个指针域必须有一个值，^为空指针NULL;二叉树的遍历 含义：就是按某种次序系统的“访问”二叉树上的所有结点，使得每个结点均被访问一次，而且仅被访问一次。 二叉树由三个基本单元组成：根结点、左子树和右子树 先左后右遍历二叉树的三种情况：DLR,LDR,LRD 先根（序）遍历：若二叉树为空，执行空操作，否则 访问根结点—先根遍历左子树—先根遍历右子树 中根（序）遍历：若二叉树为空，执行空操作，否则 中根遍历左子树—访问根结点—中根遍历右子树 后根（序）遍历：若二叉树为空，执行空操作，否则 后根遍历左子树—后根遍历右子树—访问根结点;七、查找表;七、查找表;七、查找表;七、查找表;八、基本排序算法;排序的基本概念 排序的含义：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 内部排序与外部排序的概念 内部排序：指在排序的整个过程中，数据全部存放在计算机的内存储器中，并且在内存储器中调整记录间的相对位置。 外部排序：指排序过程中，数据的主要部分存放在外存储器中，借助内存储器逐步调整记录之间的相对位置。 内部排序算法时间复杂性的度量方法 通常只考虑键值的比较次数和记录的移动次数。 当键值是字符串时，比较要占用较多的时间，当记录很大时，为了交换记录的位置，移动记录也要占用较多的时间。这是影响时间复杂性的两个主要因素。;2. 插入排序 基本思想：P23 插入排序包括直接插入排序和希尔排序两种 直接插入排序：依次将每个记录插入到一个有序的子序中去 希尔排序：先将整个待排元素序列分割成若干子序列,并分别进行插入排序，最后再整体进行一次插入排序。 直接插入排序算法的时、空性能： 初始状态若各记录已排好序的情况下，关键字比较次数为n-1,记录移动次数为0，此时的时间复杂度为O(n); 初始状态若各记录是逆序排列时，关键字比较次数为(n+2)(n-1)/2,记录移动次数为(n-1)(n+4)/2，此时的时间复杂度为O(n2); 直接排序是稳定的排序，其平均时间复杂度为O(n2)，空间复杂度为O(1)。;3. 交换排序 指在排序过程中，若两个记录A和B的相对位置不符合排好序的要求，则交换A和B的位置??? 交换排序可分为冒泡排序和快速排序两种。 冒泡排序 基本思想：P24 冒泡排序