文档介绍:第二章基本数据结构及其运算第2章基本数据结构及其运算(有*号的标题表示最基本的内容)* 、数据结构概述数据、数据元素、数据结构、逻辑结构、物理结构、算法、特征、评价二、顺序表线性表、顺序表、描述、创建、插入、删除等算法三、链表单链表、循环链表、双向链表、双向循环链表判空、插入、删除、定位等操作指针域、数据域、头节点、?数据(Data)能存于计算机、并能被计算机处理的符号集合。它是客观事物的一种符号表示。?数据元素(Element)是数据的基本单位、数据集合中的个体。?数据结构(Data Structure)是带有结构特征的数据元素的集合;它有三个要素:DS=数据的逻辑结构+存储结构+. 数据的逻辑结构概念:客观事物本身存在的结构形式及关系。特点:描述数据间的顺序(逻辑)关系,抽象地反映数据元素的结构,而不管它们在计算机中如何存放。与物理存放位置无关描述方法:用二元组来描述:DS=(D,R)其中:D:是数据元素的有限集合;R:是数据元素之间关系的集合。成员:由1名教师、1~3名研究生、1~6名本科生组成;?成员关系是:教师指导研究生、研究生指导1~2名本科生。?数据结构的形式化描述:定义DS如下:Group=(D,R)其中:D={T,G1,…,Gn,S11,…Snm} 1 ≤ n ≤ 3 , 1 ≤ m ≤ 2 R={R1,R2} R1={<T,Gi>|1 ≤ i ≤ n , 1 ≤ n ≤ 3} R2={<Gi,Sij>|1 ≤i ≤n ,1 ≤j ≤ m , 1 ≤ n ≤ 3 , 1 ≤ m ≤ 2 }-举例?(1)线性结构:一对一的次序关系?(2)树形结构:一对多的层次关系?(3)图或网状结构:多对多的关系?(4)集合:属性相同,、数据的存储结构数据的存储结构是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放形式。逻辑结构在存储器中的映射,又称物理结构。数据存储结构分类1. 顺序存储结构2. 链式存储结构3. 索引存储结构(略)4. 散列存储结构(略)1. 顺序存储结构概念:把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构:d1 d2 ……dnd1 d2 ……dn数据域数据域特点:?连续存放;逻辑上相邻,物理上也相邻。?结构简单,易实现。?插入、删除操作不便(需大量移动元素)。2. 链式存储结构概念:以链表形式将数据元素存放于任意存储单元中,可连续存放,也可以不连续存放,以指针实现链表间的联系。数据结点结构:d1...d2dn^特点:?非连续存放,借助指针来表示元素间的关系;?插入、删除操作简单,只要修改指针即可;?结构较复杂,需要额外存储空间。数据域指针域