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