数据结构2017.ppt

第一章 概述 一、数据结构的基本概念 1、数据结构：简单的说是指数据之间的关系。 内容分为三个方面：逻辑结构、存储结构和运算。 2、数据：客观事物的计算机表示 3、数据元素：数据的基本单位。（可由数据项组成） 4、数据对象：是性质相同的数据元素的集合。 5、序偶：设A、B是两个集合，对于a∈A和b∈B，有序集合a,b 叫做序偶。其中a称为序偶的第一元素，b称为序偶的第二元素。 ;二、数据的逻辑结构：是对数据之间关系的描述（简称数据结构） 1、分类： ①线性结构：线性表 除第一个结点之外，每个结点只有一个前驱结点；除最后一个之外，每个结点均只有一个后继结点。 ②非线性结构：树和图 树形结构：除根结点之外，每个结点均只有一个前驱结点； 每个结点的后继结点不唯一。 图结构：每个结点的前驱后继结点均不唯一 2、形式上的表示（用二元组） B=（K，R） 其中K是数据元素的有限集合，R是K上关系的有限集合。;3、例：已知A是二元组表示的数据结构， 画出对应的图形表示，并指出属于何种结构。 A=(K, R ),其中： K={a, b ,c ,d ,e ,f ,g ,h } R={a, b,b, c,c ,d,d, e,e ,f,f, g,g, h} 4、习题：有下列几种用二元组表示的数据结构，画出它们分别对应的图形表示，并指出它们分别属于何种结构。 ①B=(K, R ),其中：K={a, b ,c, d, e, f, g, h} R={d, b,d, g,d, a,b, c,g, e,g, h,e, f} ②C=(K, R),其中: K={1, 2, 3, 4, 5, 6 } R={(1, 2),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 5),(4, 6)} 这里的圆括号对表示两结点是双向的。 ③D=(K, R),其中: K={ 48, 25, 64, 57, 82, 36, 75 } R={r} r={25, 36,36, 48,48, 57,57, 64,64, 75,75, 82， 48, 25, 48, 64,64, 57,64, 82,82, 75};三、数据的存储结构：是逻辑结构在计算机存储器中的实现。 1、线性结构的存储方式 顺序、链接、索引、散列 2、树形结构的存储方式 链接、顺序（特定） 3、图结构的存储方式 矩阵、链接 四、数据的运算：是逻辑结构上定义的操作算法。 插入、删除、更新、查找、排序 五、算法及复杂性 1、算法的概念：是解决实际问题的计算机的方法（运算序列） 2、特性：有穷性、确定性、可行性、输入和输出 3、频度：针对语句而言，指语句重复执行的次数 4、时间复杂度：算法中简单操作的次数表示的数量级用O()表示。;第二章 线性表 第一节 线性表的基本概念和运算 一、基本概念 线性表：n （n≥0）个数据元素的有限序列（） 二、线性表的基本运算 　　1、SETNULL(L) 2、LENGTH(L) 3、GET(L) 　 4、LOCATE(L,x) 5、INSERT(L,x,i) 6、DELETE(L,i) 7、PRIOR(L,ai) 8、NEXT(L,ai) ;第二节 顺序表 一、顺序表 1、顺序存储：在地址连续的空间依次存储线性表的元素 2、存储结构图 3、地址计算loc（ai）=loc(a1)+(i-1)×L 二、数据运算(常用一维数组实现，设线性表的长度为n) 1、插入：将x插入到线性表的第i位置 若i〉n +1 则插入出错 否则 for（j=n；j=i；j- -） a[j+1]=a[j]； a[i]=x；n=n+1； 2、删除：将线性表的第i位置元素删除 若i〉n则删除出错 否则for（j=i；jn；j++） a[j]=a[j+1]； n=n-1；;3、习题： ①、一个向量（顺序表）第4元素的存储