资源描述：
《数据结构及单链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.2数据结构定义及概念1.1什么是数据结构建立数学模型是分析具体问题的过程，包括：分析具体问题中操作对象找出这些对象间的关系，并用数学语言描述数学模型分两类：1）数值计算类：例：根据三条边，求三角形面积。假定：三条边依次为a,b,c三个实型数，满足：a>0,b>0,c>0,a+b>c,b+c>a,c+a>b,则s=area=12）非数值计算类：例1:5个整数组成的集合：D={20,-5，66,15,44}其中:20,-5,66等称为数据元素(元素)，元素与元素之间关系是它们同属于集合D。D={20,
2、-5,66,15,44}是一个数据对象例2:一列整数：(线性结构)L=(20,-5，66,15,44）其中:元素与元素之间在L中是前后关系或线性关系。L=(20,-5,66,15,44)是一个线性表。2例3一张登记表DL序号姓名性别年龄1李刚男25记录12王霞女29记录23刘大海男40记录34李爱林男44记录4其中：姓名、性别、年龄是数据项(item)、数据域(field)；(姓名，性别，年龄)是记录(record),C语言将"记录"(record)定义为”结构”(struct)；登记表也是一个线性表
3、。3例4树状结构其中:A、B、C等是结点(node)；A与B,B与E,A与C之间是层次关系或父子关系。河南工业大学(A)电气学院(B)管理学院(C)理学院(D)自动化系(E)电气系(F)测控系(G)4例5图状结构ABDCEFG其中：A、B、C等是顶点(vertex),图中任意两个顶点之间都可能有关系。5例6田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。姓名项目项目项目丁一跳高跳
4、远100马二标枪铅球张三标枪100200李四铅球200跳高王五跳远2006用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。某选手比赛的项目必定有边相连（不能同时比赛）。对图上的每个顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。同色可以同时比赛。姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BF7姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王
5、五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛8综上几个例子可见，描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。9计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法+数据结构=程序1976年，瑞士N.Wirth教授1
6、01.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。11数据结构数据结构定义1----在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间
7、的关系称为结构(Structure)。数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D，S)(1-1)其中：D是数据元素的有限集，S是D上关系的有限集。数据结构主要指逻辑结构和物理结构12数据之间的相互关系称为逻辑结构，即从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。通常分为四类基本结构：集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构结构中的数据元素之间存在一对一的关系。树形结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数
8、据元素之间存在多对多的关系13物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），依赖于计算机。存储结构可分为4大类：顺序、链式、索引、哈希14顺序存储结构数据结点结构把逻辑上相邻的结点存储在物理位置相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现，通常在程序设计中用数组表示。顺序存储是把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。连续存放。逻辑上相邻，物理上也相邻；结构简单，易实现；插入、删除操作不便（
