第二章基本数据结构及其运算.ppt

《第二章基本数据结构及其运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章基本数据结构及其运算2.1数据结构的基本概念2.2线性表及顺序存储结构2.3线性表链表及其运算2.4数组2.5树与二叉树2.6图本章主要介绍:数据结构、数据逻辑结构、数据存储结构的基本概念；几种常用的数据结构(线性表、栈、队列、数组、树与二叉树、图），阐明这些数据结构内在的逻辑关系，讨论它们在计算机中存储的常用方式：顺序存储和链式存储，以及在这些数据结构上进行各种运算的算法。重点：理解数据结构、数据逻辑结构和存储结构的概念，掌握常用的数据结构中各数据内在的逻辑关系，在计算机中的存储方式，以及在其上进行各种运算的算法。难点：正确区分数

2、据逻辑结构和存储结构，掌握常用数据结构在计算机中的存储方式，及在其上进行各种运算的算法。1、数据元素之间的固有逻辑关系，称为数据的逻辑结构数据结构主要研究和讨论三方面问题：2、数据元素及其关系在计算机中的存储方式，称为数据的物理结构或存储结构3、施加在数据结构上的操作，称为数据结构的运算。数据处理的本质就是对数据结构施加各种运算，常见的运算有：查找、排序、插入、删除等。2.1数据结构的基本概念例1、无序表的顺序查找与有序表的对分查找。2.1.1两个例子2、尽量节省数据处理过程中所占用的存储空间1、提高数据处理的速度主要目的是提高数据处理的

3、效率：1234567891012345678910data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]132442772830121321242830427725(a)无序表data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]211225(b)有序表图2.1数据元素存放顺序不同的两个表表(a)只能采用顺序查找，将x与表中每一个元素进行比较，查找效率较低。因表(b)中的元素是有序排列，可找到其中

4、间元素data[4]，将x与它进行比较，有三种可能：x=data[4]x>data[4]x

5、0970162张军男1880970163王伟男2065970164胡涛男1995……………9519男胡涛9701649019女曾小波9701619317女梅玲9701689121男李启明970159成绩年龄性别姓名学号成绩在90分及以上的学生情况登记表成绩在80~89分之间的学生情况登记表8018男张军970162……………8319女李小青9701578620男张小明970156成绩年龄性别姓名学号从该例可看出，在对数据进行处理时，可根据所做的运算不同，将数据组织成不同的形式，也可提高数据处理的效率成绩在70~79分之间的学生情况登记表7

6、818女刘华9701607520男刘健9701697019男赵凯970158成绩年龄性别姓名学号成绩在60~69分之间的学生情况登记表6520男王伟9701636118男吕永华970167成绩年龄性别姓名学号2.1.2什么是数据结构数据结构：互相有关联的数据元素的集合。例：向量和矩阵就是数据结构，在这两个数据结构中，数据元素之间有位置上的关系数据：反映客观事物信息集合，在现实生活中称信息在计算机中称数据；即数据是符号化的信息。它由数据元素组成数据元素(元素)：数据集合中的一个元素，是数据的基本单位。数据元素具有广泛的含义，现实世界中的一切

7、个体可以是数据元素例：描述四季的季节名{春、夏、秋、冬}可以作为季节(数据)的数据元素描述学生特征的信息:(970158、赵凯、男、1970、70)，(970159、李启明、男、21、91)，(970162、张军、男、18、80)…可以作为学生情况登记表(数据)的数据元素甚至每一个客观存在的事件：如一次借书、一次比赛等也可作为数据元素总之，在数据处理领域，每一个需要处理的对象都可抽象成数据元素要表示一个数据结构，需表示出：1、数据元素的集合，记为D2、在D中各数据元素之间的关系，记为R则：数据结构B=(D,R)在数据处理领域，数据元素之间

8、的任何关系都可以用前后件关系描述例1：春、夏、秋、冬四季，春是夏的前件，夏是春的后件为反映春、夏、秋、冬这四个元素之间的前后件关系，一般采用二元组表示，也称二元关系(春,夏)、(夏,秋)、(秋