第一课本课主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常用术语教学重点：基本概念：数据、数据元素、数据结构(逻辑结构和存储结构)教学难点：数据元素间的四种数据结构教学内容：一、基本概念和术语1．数据（Data）：是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。（在计算机领域中：能被计算机输入、存储、处理、输出的一切信息）例：下表中李明的数学考试成绩为60分，60就是该同学的成绩数据学号姓名语文数学美术20040101李明80609020040102王刚92887220040103李华87717020040104……再例如我们在网络上看的电视节目、下载的mp3歌曲等等图像、声音文件等。2．数据元素（DataElement简称元素）：数据的基本单位，也称节点（node）或记录（record）。可以再由不可分割的数据项组成。数据记录（DataRecord）：数据处理领域组织数据的基本单位。一个数据项数据项：记录属性的描述（字段）。关键项（KeyItem）:能唯一标识一个记录的数据项。关键字（KeyWord或Key）：关键项中的每一个值。关键项学号姓名语文数学一个数据元素美术20040101李明806090关键字20040102王刚92887220040103李华87717020040104……3.数据对象(DataObject):是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。4.数据处理（DataProcessing）:指对数据进行检索、插入、删除、合并、拆分、排序、统计、简单计算、转换、输入、输出等操作过程。5.数据结构（DataStructure）:是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。(1).数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。数据的逻辑结构—只抽象反映数据元素的逻辑关系，独立于计算机，是数据本身所固有的。数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现，必须依赖于计算机。(2).数据结构从逻辑结构划分为：集合结构集合结构是指数据中各元素之间没有任何次序。如一个单位的所有职工，可以认为他们之间没有任何次序，为集合结构。线性结构线性结构是指数据中各元素之间具有1对1的先后次序关系。如学生成绩表中，各个成绩记录之间是按照学生的学号的先后次序排列的。所以，成绩表结构是线性结构。树结构树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。所以，企业的组织结构是一个树结构。图结构图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。(3).数据结构从存贮结构划分为：顺序存贮（向量存贮）所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。链式存贮所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。索引存贮使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。散列存贮通过构造散列函数，用函数的值来确定元素存放的地址。(4).数据结构的描述数据结构可用二元组B=(K,R)的形式来描述。其中，K={a1,a2,…,an}为元素集合，K={ki|1≤i≤n,n≥0}R={r1,r2,…,rm}为关系的集合,R={rj|1≤j≤m,m≥0}说明：1、n=0，则K为空集，B无结构。2、m=0，R为空集，K中元素之间不存在任何关系，彼此独立。3、K上的关系r是序偶集合，表示：(x,y）→无向；<x,y>→有向。（其中x为y的直接前趋；y为x的直接后继）。例1-5设有一个线性表(a1,a2,a3,a4,a5)，它的抽象描述可表示为D=(K,R),其中K={a1,a2,a3,a4,a5},R={<a1,a2>,<a2,a3>,