软件技术基础03--数据结构基本概念

软件技术基础数据结构的基本概念制作主讲段景山第一篇数据结构第一章数据结构的基本概念数据结构数据的逻辑结构数据的存储结构算法数据结构1数据结构的概念1.1数据及数据元素的概念数据是客观事物在计算机内的抽象描述数据指一些事实，或一些数，或一些符号集合组成数据的“事实”、“数值”或“符号”称为数据元素数据元素可由若干个数据项组成数据项可以认为是数据元素的一个属性。一个复合的元素具有多个属性——数据项3数据、数据元素及数据项例1、学生花名册数据元素数据学生名字的集合每个学生的名字例2、学生成绩表数据数据元素数据项学生成绩的集合每个学生的成绩名字成绩4数据结构的概念1.2、数据结构数据结构讨论计算机系统中数据的组织形式及其相互关系是相互之间存在一种和多种特定关系的数据元素的集合例：大楼中的电梯电梯在楼层中只能逐层移动例：公司的组织关系楼层间的关系是线性的员工间形成树型关系涉及元素的集合元素间的关系在关系里的操作电梯的运动人员的管理5关于对数据结构的理解对数据结构的理解可大致分为三种角度数理角度：强调数据元素间的逻辑关系计算机角度：强调逻辑关系、存储关系和算法的结合——本教材的主流角度与数理角度相比，是将元素间的关系归结为两种关系，结合算法的需要进行抽象建模的角度：强调为解决实际问题而进行抽象，为建立科学、规范的模型而进行灵活调整——本课程推荐的思维角度6例：用数据结构描述整数I*——数理角度的典例1、组成整数数据的全部元素的集合II＝{0，±1，±2，±3……}2、I中元素的关系集合RE3、I*的运算集合P，比如算术四则运算4、P中诸运算的运算规则RU，如乘、除法优先于加、减法等I*＝{I，RE，P，RU}数据结构的概念RE＝{……-10,01,12,……}元素间的关系不止一种……7数据结构的概念例：用数据结构的思想分析以下问题，——建模角度一个十字路口的红绿灯管制四皇后问题：在一个4×4的棋盘上放置4个皇后，互相不会相杀，该怎么放？过河问题：现有一条河，共有八个人要过河，分别是爸爸，妈妈，两个儿子，两个女儿，一个警察，一个犯人。现有一条木伐，一次最多载两个人，在这八人中，有爸妈警察会开船，即这个船上必须有爸妈，警察三个中的一个，船才会开动。船过去无法自动回来。并且要避免以下三件事发生，1警察不在犯人会伤害一家六口。2爸爸不在，妈妈会伤害儿子。3妈妈不在，爸爸会伤害女儿。元素关系运算8数据结构的概念——计算机角度元素集合元素间的关系运算计算机系统元素在计算机系统里的表示字符？字串？整数？元素间的逻辑关系－－逻辑结构元素在计算机系统中的存储方式，物理空间关系－－存储结构操作指令的集合－－算法9数据的逻辑结构与数据的存储结构例：班级里的同学可能有各种各样的逻辑关系。比如班长、班委、组长、群众等。形成相应的逻辑结构。上课时，大家的座次形成存储结构座次（存储结构）可能与逻辑关系有关，也可能无关。数据结构的概念——两种关系为什么要这样抽象出两种关系？设想一个发作业的场景……结论：两种关系的抽象是为了能够完成操作，解决在集合中“找谁来完成”？“如何找到它”？10小结：数据结构包括数据的逻辑结构，数据在计算机系统中的存储结构和数据操作的集合把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度。逻辑结构存储结构算法数据结构的概念要素目标三个要素都与我们所要实现的目标相关有效处理数据提高数据处理运算速度11数据结构的概念三位一体，提前感受逻辑结构不同，物理结构相似，算法相似顺序表和顺序存储的二叉树逻辑结构相同，物理结构不同，算法相似顺序表和链表逻辑结构相同，物理结构相同，算法不同队列和栈12深入思考研究数据结构的作用看以下几段话，谈谈感受小李是经理小李提升为经理小李从职员提升为经理小李从职员越过课长直接提升为经理，这不合常规小李从1000多个职员中越过课长直接提升为经理，这是很不合常规的哪句话包含的信息多，多了什么样的信息结合这个例子，思考研究目的、重点、基础13课堂活动拿出纸笔，开始行动咨讯：是否了解本次行动的目标和内容计划：2~4人自由组合为一组决策：选取主题，或自拟题目实施：按数据结构中的“元素的集合”、“元素的关系”、“运算”来描述主题，至少三句话评价：相互评价描述内容是否适当。14数据结构的概念例：对下列（或自拟）系统，利用数据结构的思想来进行抽象和描述一个十字路口的红绿灯管制一个五叉路口的红绿灯管制包含两部电梯的管理系统包含三部电梯的管理系统一条公交路线书图书馆……元素关系运算15课堂活动评价主题选择是否适当元素抽象是否适当逻辑结构（关系）与物理结构之间是否有区分度算法是否适当，与两个结构之间的描述是否有区分度汇报讲解是否清楚162、数据的逻辑结构数据元素之间关系的描述2.1、描述法二元组关系：一般抽象为前驱与后继关系，即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁B＝（K，R）K：元素集合R：元素间关系的集合数据的逻辑结构172.2、图示法图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表不管多么复杂的结点，都看作是一个结点有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继KiKhKjKi的前驱Ki的后继数据的逻辑结构183、数据的存储结构（物理结构）是数据元素在计算机系统存储器中的存放方式也可以说，是数据逻辑结构在存储器中的存放方式或者：元素及其逻辑关系在存储器内的表示……数据的存储结构存储器的特点：由地址连续的单元构成190300030103020303030403050306030703080309K1K2K3K4K1K2K3K4数据的存储结构逻辑结构物理结构200300030103020303030403050306030703080309K1K2K3K4K5K6K1K2K3K4K5K6数据的存储结构逻辑结构物理结构21数据的存储结构思考：为什么数据逻辑结构与物理结构没有完全统一？存储器的特点：由地址连续的单元构成。－－线性关系存储单元间位置上的线性关系有时不能直接反映复杂的逻辑关系22建立理解模型——图书馆为后续课程内容的理解，我们先观察一个现实生活中的实例——一个不那么现代的图书馆（书店）。图书馆存放了大量的书，都放在书架上23图书馆为便于在海量的图书中寻找到需要的书籍，图书馆往往提供一种索引卡片来帮助找书。索引卡片上除了记录书的概要信息和分类号码等，还有书籍在书架上的位置，如第几个书架，第几排等。24几种物理存储方式3.1顺序存储方法连续顺序地存放数据元素若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了连续存放的数据元素可以在内存中容易找到数据的存储结构253.2、链接存储方法元素在内存中不一定连续存放在元素中附加指针项，通过指针可以找到关系元素元素＋指针结点元素指针数据的存储结构联想：在一套丛书中每一本书中夹一个卡片，记录下一本书在书架上的位置260300030103020303030403050306030703080309K1K2K3K4K1K2K3K4链接式存储结构逻辑结构物理结构指向后继结点的指针2703000310032003300340035003700380K1K2K3K4K5K6K1K2K3K4K5K6通过指针，可以方便地找到关系结点链接式存储结构逻辑结构物理结构283.3索引存储方法为放在内存中的元素建立索引表元素可以离散存放通过查索引表找到需要的元素0300030103020303030403050306030703080309K1K2K3K41234索引表索引号数据的存储结构联想：图书馆的查书卡293.4、散列存储方法结点中设一关键值，利用关键值和相应算式算出结点位置（地址）例：以用户姓名为关键值DJS算式：字母的序号相加04＋10＋19＝33ZXM26＋24＋13＝63数据的存储结构所以，DJS放在33号地址单元ZXM放在63号地址单元联想：通过书的名字就能确定书的位置30小结：数据的逻辑结构与物理结构1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位2、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序存储方法3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构4、逻辑结构与存储结构是一个问题的两个方面数据的逻辑结构和存储结构31例：一个树形关系结构用索引方式存储1234561234560300030103020303030403050306030703080309K1K2K3K4K5K6数据的逻辑结构和存储结构例：一个树形关系结构用链接方式存储例：一个树形关系结构用顺序方式存储？324、算法4.1、算法的概念及特点算法是为解决某一特定类型问题规定的运算规则的有穷集合有穷性确定性有效性输入输出特点非无限执行，必须在有限步骤内结束非二义，下一步必须是明确的每一步是可执行的外部输入零个或多个至少一个算法334.2、算法与程序相似：都是解决问题的方法和步骤，是指令的集合区别：有穷性描述方法联系：程序用某种程序设计语言来实现算法程序使用程序设计语言算法可以使用框图及其他语言算法类似：while(1){……}的语句段，在程序中允许但在算法中不允许344.3、算法语言算法应有严格的描述语言（确定性）一般使用类PASCAL语言在本课程中使用类C语言，即语言风格类似于C要求描述一个算法时必须满足：对输入和输出的描述描述语句准确、无二义保证算法的有穷性和有效性算法35算法算法的写作规范intseq_search(elemtypes[],keytypek,intn){intlow,high,mid;s[n].key=k;i=0;while(s[i].key!=k)i++;if(in)returni;elsereturn-1;}名称输入参数输出类型使用的变量说明初始化算法主体部分36算法例374.4、在数据结构中常见的问题创建、插入、删除、更新、检索、排序……注意：每个问题都有一种或多种算法找到效率最高的以最容易理解的方式设计设计的算法不容易出错或出错情况较少算法38作业教材第一章，12345选取一个主题（可以是一个具体的客观事物，一道经典算法题目等），用数据结构的元素，逻辑结构，存储结构和算法来描述这个主题。元素的抽象：尽量靠近“事实、数值、字符”关系的抽象：尽量使用“前驱、后继”算法的描述：尽量说明输入条件、输出结果、大致步骤。39