二级C语言第1章_数据结构与算法.ppt

第1章 数据结构与算法 1.1 算法 1.2 数据结构的基本概念 1.3 线性表及其顺序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树和二叉树 1.7 查找技术 1.8 排序技术 1.1 算法 算法的基本概念 算法的复杂度分析 算法的基本概念 通俗的定义： 算法是指解题方案的准确而完整的描述。 算法的基本特征 1.可行性 2.确定性 3.有穷性 4.拥有足够的情报 算法的严格定义： 算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 算法的基本要素 (1) 算法中对数据的运算和操作 ①算术运算 ②逻辑运算 ③关系运算 ④数据传输 (2) 算法的控制结构 传统流程图、N-S结构化流程图、算法描述语言等。 算法设计基本方法 1. 列举法 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。 例：设每只母鸡值3元，每只公鸡值2元，两只小鸡值1元。现要用100元钱买100只鸡，设计买鸡方案。 假设买母鸡I只，公鸡J只，小鸡K只。 2. 归纳法 通过列举少量的特殊情况，经过分析，最后找出一般的关系。 3. 递推 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。 4. 递归 将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。 5. 减半递推技术 所谓“减半”，是指将问题的规模减半，而问题的性质不变。 所谓“递推”，是指重复“减半”的过程。 例：二分法求方程实根 6. 回溯法 通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。 例：迷宫问题 算法的复杂度分析 算法的时间复杂度 算法的空间复杂度 执行算法所需要的内存空间。 1. 2 数据结构的基本概念 什么是数据结构 数据结构的图形表示 线性数据结构与非线性数据结构 目的：提高数据处理的效率 提高数据处理的速度 尽量节省计算机存储空间 数据结构三个方面的问题： (1)数据的逻辑结构 (2)数据的存储结构 (3)对各种数据结构进行的运算 什么是数据结构 数据结构是指相互有关联的数据元素集合。 现实世界中客观存在的一切个体都可以是数据元素。 描述一年四季的季节名 春，夏，秋，冬 可以作为季节的数据元素； 表示数值的各个数 18，11，35，23，16，… 可以作为数值的数据元素； 前后件关系 前后件关系(也称为直接前驱和直接后继)是数据元素之间的自然存在的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。 一般来说，数据元素之间的任何关系都可以用前后件关系来描述。 数据的逻辑结构 一个数据结构应包含两方面的信息 （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系（即逻辑关系） 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构有两个要素： 数据元素的集合D； 反映D中各数据元素之间的前后件关系R。 数据的逻辑结构 数据结构可以表示成 B＝（D，R） 其中B表示数据结构。 为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。 设a与b是D中的两个数据，则二元组 （a，b） 表示a是b的前件，b是a的后件。 数据的逻辑结构 例如 B＝（D，R） D＝{春，夏，秋，冬} R＝{(春，夏)，(夏，秋)，(秋，冬)} 家庭成员数据结构 B＝（D，R） D＝{父亲，儿子，女儿} R＝{(父亲，儿子），(父亲，女儿）} 数据的存储结构（数据的物理结构） 数据的逻辑结构在计算机存储空间中的存放形式。 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。 常用的存储结构有： 顺序、链接、索引等存储结构。 采用不同的存储结构，其数据处理的效率是不同的。 数据结构的图形表示 数据集合D中的每一个数据元素用中间标有元素值的方框表示（数据结点，结点） 用一条有向线段从前件结点指向后件结点。 如:一年四季数据结构的图形表示 家庭成员间辈份