计算机科学概论第5章数据结构与算法.ppt

第5章 数据结构与算法,计算机科学概论,理解数据结构的概念，理解数据结构的逻辑和存储结构； 理解算法的概念和算法的基本特性，了解算法复杂度的度量方法； 理解线性数据结构，理解顺序存储和链式存储的存储方法； 描述栈和队列、串和数组这几个线性数据结构的概念； 了解非线性的数据结构，了解树、二叉树以及图的概念和数据结构； 理解排序的概念，描述插入、选择、气泡和快速排序的算法； 理解查找的概念，描述顺序查找和折半查找的算法，并能够比较它们 理解递归的概念，能够在实践中了解递归的应用教 学 目 的,1,2,3,学 习 内 容,数据结构概述,线性结构,非线性结构,基本算法,递归,4,5,学 习 重 点,数据结构的基本概念 算法的描述、流程图的使用以及算法的复杂度的衡量 顺序存储和链式存储的方法 栈、队列、串和数组的概念和用法 二叉树数据结构 查询、排序和递归算法,第一节 数据结构概述,1 数据结构概述,1.1《数据结构》研究的对象 (1) 对所加工的对象进行逻辑组织 (2) 如何把加工对象存储到计算机中去 (3) 数据运算 数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作 [例5-1] 设有一个号码薄，有N个人的姓名和号码。

要求设计一个程序，按人名查找号码，若不存在则给出不存在的信息1 数据结构概述,1.2 数据结构相关概念 1.基本概念和术语数据元素、结点、数据项、关键字或主关键字、 次关键字、数据对象、数据结构2.数据结构 特性相同的数据元素构成的集合中，如果在数据元素之间存在一种或多种特定的关系，则称之为数据结构 Data-Structure=(D,R)其中，D是数据元素的有限集，R是D上关系的有限集1 数据结构概述,3.四类基本的数据结构 集合结构在集合结构中，数据元素间的关系是“属于同一个集合”集合是元素关系极为松散的一种结构，各元素间没有直接的关联 线性结构该结构的数据元素之间存在着一对一的关系 树型结构该结构的数据元素之间存在着一对多的关系 图形结构该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构1 数据结构概述,[例5-2] 线性数据结构=(D,S) D={1,2,3,4,5,6,7,8,9,10} S={,,,,,,, ,},1 数据结构概述,[例5-3] 图形数据结构=(D,R) D={1, 2, 3, 4, 5, 6, 7, 8, 9} R={,,,,,,,, ,,,,,},1 数据结构概述,[例5-4] 树形结构 =（D,R） D={a, b, c, d, e, f, g, h, i, j, k, l} R={,,,,,,,,, ,},1 数据结构概述,1.3 数据结构的分类1、按数据结构的性质划分数据的逻辑结构——数据元素之间的逻辑关系（设计算法—— 数学模型）数据的物理结构——数据结构在计算机中的映像（存储结构，算法的实现）2、按数据结构的操作来划分静态结构——经过操作后，数据的结构特征保持不变（如数组）。

半静态结构——经过操作后，数据的结构特性只允许很小变迁（如栈、队列）动态结构——经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）1 数据结构概述,1.3 数据结构的分类3、按数据结构在计算机内的存储方式来划分顺序存储结构——借助元素在存储器的相对位置来表示数据元素之间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素之间的逻辑关系索引存储结构——在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址散列存储结构——根据结点的关键字直接计算出该结点的存储地址 说明：四种存储方法可结合起来对数据结构进行存储映像1 数据结构概述,1.4 算法及其描述和算法分析1、算法的概念及特征算法: 对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列算法具有以下五个重要的特征：1）有穷性：一个算法必须保证执行有限步之后结束2）确切性：算法的每一步骤必须有确切的定义3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。

没有输出的算法没有实际意义5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成1 数据结构概述,1.4 算法及其描述和算法分析2、算法的描述: 1）流程图 2）伪代码——类程序设计语言3、算法的基本结构 :1）顺序结构 2）分支结构3）循环结构,1 数据结构概述,1 数据结构概述,,算法基本结构示意图,1.4 算法及其描述和算法分析4、算法效率衡量方法与准则 :时间复杂度：指算法从开始执行到处理结束所需要的总时间T（n）= O（f(n)）空间复杂度：指算法从开始执行到处理结束所需的存储量空间的总和 S（n）= O（g(n)）,1 数据结构概述,1.4 算法及其描述和算法分析5、算法与数据结构的关系: 计算机科学家沃斯（N.Wirth）提出的: “算法+数据结构=程序”揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构算法与数据结构是互相依赖、互相联系的一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据1 数据结构概述,第二节 线性结构,2.1 线性表1.线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同的属性，表中相邻元素间存在“序偶”关系。

记做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an ) 其中，ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继元素 线性表的长度：表中的元素个数 n 位序：i称元素ai性表中的位序,2 线性结构,2.1 线性表2.线性表的顺序表示和实现 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表2 线性结构,2.1 线性表2.线性表的顺序表示和实现 顺序表——线性表的顺序存储表示 Const LIST_INIT_SIZE=100; (C++规范)Const LISTINCREMENT=10; #define LIST_INIT_SIZE 100 (C规范)Typedef Struct {Elemtype * elem;Int length;Int listsize;Int incrementsize;}SqList;,2 线性结构,2 线性结构,2.1 线性表 3. 线性表的链式表示和实现 链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存贮单元的地址，这两部分信息组成一个“节点”。

2 线性结构,2.1 线性表3.线性表的链式表示和实现 单链表——线性表的链式存储表示 数据域（data）和指针域（next） 存储表示typedef struct Lnode{ElemType data;Struct Lnode *next;}Lnode, *LinkList;,2 线性结构,2 线性结构,2.1 线性表3.线性表的链式表示和实现 双向链表（循环链表）——线性表的链式存储表示 概念：两个指针，分别指向前驱元素和后继元素 typedef struct DuLnode{ElemType data;Struct DuLnode *prior;Struct DuLnode *next;}DuLnode, *DuLinkList;,2 线性结构,2.2 栈和队列 1.栈的定义 栈（Stack）是限定只能在表得一端进行插入和删除操作得线性表，又称限定性线性表结构2.栈的结构特点和操作 栈顶(Top)、栈底(Bottom),先入后出(LIFO) 栈的基本操作InitStack（&S） GetTop(S,&e)DestroyStack(&S) Push(&S, e)ClearStack(&S) Pop(&S,&e) StackEmpty（S） StackTraverse(S)StackLength（S）,2 线性结构,堆栈结构示意图,2 线性结构,2.2 栈和队列 3.队列的定义 队列（Queue）是限定只能在表得一端进行插入在表的另一端进行删除操作的线性表。

4.队列的结构特点和操作 队列头(front)、队列尾(rear)，先入先出(FIFO) 队列的基本操作InitQueue(&Q) GetHead(Q,&e)DestroyStack(&S) EnQueue(&Q,e)ClearQueue(&Q) Dequeue(&Q,&e) QueueEmpty(Q) QueueTraverse(Q)QueueLength(Q),2 线性结构,2.3 串和数组 1.串的定义和表示方法 串定义串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成 字符串，由零个或多个字符组成的有限序列S＝“a0a1.an-1” 串的长度：n 空串：n=0，Null String 子串与主串，子串的位置（从0开始） 串的比较：最大相等前缀子序列,2 线性结构,2.3 串和数组 1.串的定义和表示方法 串的表示方法定长顺序存储表示 两种表示方法：1)下标为0的数组存放长度 (pascal)typedef unsigned char SString[MAXSTLEN+1] ;2)在串值后面加‘\0’结束 (C语言)堆分配存储表示串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。

2 线性结构,2.3 串和数组 2.数组的定义和操作 数组定义数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识数组可以看作线性表的推广数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型 二维数组定义其数据元素是一维数组的线形表 N维数组定义其数据元素是N－1维数组的线形表2 线性结构,2.3 串和数组 2.数组的定义和操作 数组的操作 initarray(&A,n,bound1,bound2.boundn) ——初始化 Destroyarray(&A) —— 删除数组 value(A,&e,index1,index2indexn) —— 赋值 assign(&A,e,index1,index2indexn) —— 分配数组,2 线性结构,2.3 串和数组 3.数组的存储方式和表示 数组元素的两种存储方式 行主序存储 列主序存储 数组中元素在内存映象中的关系: 二维数组A[m][n]LOC[i,j]=LOC[0,0]+(i*n+j)*L 三维数组B[p][m][n]LOC[i,j,k]=LOC[0,0,0]+(i*m*n+j*n+k)*L,2 线性结构,第三节 非线性结构,3.1 树1.树的定义与结构特点 树的定义n(n>=0)个数据元素（结点）的有限集D，若D为空集，则为空树。

否则：在D中存在唯一的称为根的数据元素； 当n>1时，其余结点可分为m（m>0）个互不相交的有限子集T1，T2，，Tm，其中每个子集本身又是一颗树，并成为根的子树。