第6章算法与数据结构要点.pptx

第6章 算法与数据结构;;6.1算法概述6.1.1算法及特性;;6.1.2 算法的描述方式;6.1.3 算法的度量;;;;;6.2 数据结构概述6.2.1什么是数据结构;6.2.2 数据结构的基本术语 ;2. 数据元素（Data Element） 数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成（Data Item）。 ;3. 数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0， ±1， ±2， …}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。; 4.数据结构 ：数据之间的相互关系;在形式上，数据结构通常用一个二元组来描述： Data_structure=(D,S) 其中，D为数据结构的有限集，S是D上关系的有限集。 例：一年四季名称所组成的数据结构可以表示为： B=(D,R) D={春，夏，秋，冬} R={春，夏,夏，秋,秋，冬} 例：假设家庭成员组成的数据结构可以表示成： B=(D,R) D={祖父，叔叔，父亲，儿子，女儿，孙子} R={祖父，父亲,祖父，叔叔,父亲，儿子,父亲，女儿,儿子，孙子} ; 5. 存储结构 存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。 逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。 ;顺序映象 （顺序存储结构） 顺序映象用元素在存储器中的相对位置表示数据元素之间的 逻辑关系。 非顺序映象（非顺序存储结构） 非顺序映像借助指示元素存储地址的指针表示元素之间的逻 辑关系。 用一维数组来描述顺序存储结构，用指针来描述链式存储结构。 ;6.3 线性结构;（a1, a2, … ai-1，ai, ai＋1 ，…, an） ; 线性表的特点可概括如下： 同一性 有穷性 有序性 线性表是最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。;线性表的顺序存储结构 ;线性表顺序存储特点：;;线性表顺序表示的优点是：  (1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；  (2）可方便地随机存取表中的任一元素。  其缺点是： （1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低; （2）预分配空间（浪费）； （3）表的扩充不方便。 ;3 链式存储; 由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。 单链表中第一个结点无前趋，应设一个头指针H指向第一个结点。 单链表中最后一个结点没有直接后继，则指定最后一个结点的指针域为“空”（NULL）。 整个链表的存取必须从头指针开始。 ;单链表的逻辑状态 ;;链表的运算效率分析;栈（Stack）：具有一定操作约束的线性表 ?只在一端（栈顶，Top）做 插入、删除 ;队列(Queue)：具有一定操作约束的线性表 ?插入和删除操作：只能在一端插入（队尾），而在另一端删除（队头）。 数据插入：入队列 数据删除：出队列 先来先服务 先进先出：FIFO ;串(String)是零个或多个字符组成的有限序列。一般记为：  S= ‘a1a2...an’ (n≥0) 其中S是串的名字，用单引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度，n=0时的串称为空串 (Null String)。 ; 串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 假如有串A=‘China Beijing’，B=‘Beijing’，C=‘China’，则它们的长度分别为13、7和5。B和C是A的子串，B在A中的位置是7，C在A中的位置是1。 当且仅当两个串的值相等时，称这两个串是相等的，即只有当两个串的长度相等，并且每个对应位置的字符都相等时才相等。 ; 串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了