1、软件技术基础软件技术基础制作主讲段景山段景山段景山段景山段景山第一篇第一篇 数据结构数据结构第一章第一章数据结构的基本概念数据结构的基本概念段景山段景山数据结构数据结构u1.1 数据及数据元素的概念数据及数据元素的概念段景山段景山数据及数据元素数据及数据元素段景山段景山数据结构的概念数据结构的概念n1.2、数据结构的概念、数据结构的概念u数据结构讨论计算机系统中数据的组织形式及其数据结构讨论计算机系统中数据的组织形式及其相互相互关系关系u是相互之间存在一种和多种特定是相互之间存在一种和多种特定关系关系的数据元素的数据元素的集合的集合段景山段景山例：用数据结构描述整数例：用数据结构描述整数I*1
2、、组成整数数据的全部元素的集合、组成整数数据的全部元素的集合I I 0，1，2，32、I中元素的关系集合中元素的关系集合RE3、I*的运算集合的运算集合P，比如算术四则运算，比如算术四则运算4、P中诸运算的运算规则中诸运算的运算规则RU，如乘、除法优先于加、减法等如乘、除法优先于加、减法等 I*I，RE，P，RU数据结构的概念数据结构的概念段景山段景山数据结构的概念数据结构的概念n元素间的逻辑关系元素间的逻辑关系逻辑结构逻辑结构n元素在计算机系统中的存储方式，物元素在计算机系统中的存储方式，物理空间关系理空间关系存储结构存储结构n操作指令的集合操作指令的集合 算法算法段景山段景山例：班级里的同
3、学例：班级里的同学可能有各种各样的逻辑关系。比如班长、班委、可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的群众等。形成相应的逻辑结构逻辑结构。上课时，大家的座次形成上课时，大家的座次形成存储结构存储结构座次（存储结构）可能与逻辑关系有关，也可能无关。座次（存储结构）可能与逻辑关系有关，也可能无关。数据结构的概念数据结构的概念段景山段景山数据结构的概念数据结构的概念段景山段景山n2.1、描述法、描述法u二元组二元组u关系：一般抽象为前驱与后继关系，关系：一般抽象为前驱与后继关系，即表明结构中，一个元素的前一个元素是谁，它的后即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是
4、谁一个元素又是谁B （K，R）K：元素集合：元素集合R：元素间关系的集合：元素间关系的集合数据的逻辑结构数据的逻辑结构段景山段景山n2.2、图示法、图示法u图形要素：图形要素：结点结点和和有向线段有向线段u结点：表示一个数据元素，一般以方形框代表结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点不管多么复杂的结点，都看作是一个结点u有向线段：表示元素之间的关系。有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭尾指向的结点是前驱。箭头指向的结点是后继箭头指向的结点是后继K iK hK jKi的前驱的前驱Ki的后继的后继数据的逻辑结构数据的逻辑结构段景山段景山n3
5、、数据的存储结构（物理结构）、数据的存储结构（物理结构）u是数据元素在计算机系统存储器中的存放方式是数据元素在计算机系统存储器中的存放方式u是数据逻辑结构在存储器中的存放方式是数据逻辑结构在存储器中的存放方式数据的存储结构数据的存储结构段景山段景山0300030103020303030403050306030703080309K1K2K3K4K1K2K3K4数据的存储结构数据的存储结构段景山段景山0300030103020303030403050306030703080309K1K2K3K4K5K6K1K2K3K4K5K6数据的存储结构数据的存储结构段景山段景山数据的存储结构数据的存储结构段景
6、山段景山u连续顺序地存放数据元素连续顺序地存放数据元素u若数据的逻辑结构也是顺序（线性）的，则逻辑若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了结构和物理结构完全统一了u连续存放的数据元素可以在内存中容易找到连续存放的数据元素可以在内存中容易找到数据的存储结构数据的存储结构段景山段景山u在元素中附加指针项，通过指针可以找到关系元素在元素中附加指针项，通过指针可以找到关系元素元素指针元素指针 结点结点元素元素指针指针数据的存储结构数据的存储结构段景山段景山03000310032003300340035003700380K1K2K3K4K5K6K1K2K3K4K5K6通过指针，
7、可以方便地找到关系结点通过指针，可以方便地找到关系结点指向后继结点的指针指向后继结点的指针数据的存储结构数据的存储结构段景山段景山0300030103020303030403050306030703080309K1K2K3K41234数据的存储结构数据的存储结构段景山段景山DJS041019 33ZXM262413 63数据的存储结构数据的存储结构段景山段景山1、物理结构是元素在内存中的存储方式，与元素、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位物理结构着眼于结点在内存中的定位2、简单的逻辑结
8、构可能和物理结构一致、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序存储方法例：线性逻辑关系与顺序存储方法3、利用物理结构在内存中找到一个结点，而为什、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定么要找这个结点却由元素间的逻辑关系决定任何一个算法的设计取决于选定的数据逻辑结任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构构，而算法的实现依赖于采用的存储结构4、逻辑结构与存储结构是一个问题的两个方面、逻辑结构与存储结构是一个问题的两个方面数据的逻辑结构和存储结构数据的逻辑结构和存储结构段景山段景山例：班级的逻辑关系与课堂上的座
9、次例：班级的逻辑关系与课堂上的座次例：一个树形关系结构用索引方式存储例：一个树形关系结构用索引方式存储1234561234560300030103020303030403050306030703080309K1K2K3K4K5K6数据的逻辑结构和存储结构数据的逻辑结构和存储结构段景山段景山u算法是为解决某一特定类型问题规定的运算规则算法是为解决某一特定类型问题规定的运算规则的有穷集合的有穷集合有穷性有穷性确定性确定性有效性有效性输入输入输出输出特特点点非无限执行，必须在有限步骤内结束非无限执行，必须在有限步骤内结束非二义，下一步必须是明确的非二义，下一步必须是明确的每一步是可执行的每一步是可执
10、行的外部输入零个或多个外部输入零个或多个至少一个至少一个算法算法段景山段景山n4.2、算法与程序、算法与程序u相似相似：都是解决问题的方法和步骤，是指令的集合：都是解决问题的方法和步骤，是指令的集合u区别区别：有穷性有穷性描述方法描述方法u联系：联系：程序用某种程序设计语言来实现算法程序用某种程序设计语言来实现算法程序使用程序设计语言程序使用程序设计语言算法可以使用框图及其他语言算法可以使用框图及其他语言算法算法段景山段景山算法算法段景山段景山算法算法段景山段景山u创建、插入、删除、更新、检索、排序创建、插入、删除、更新、检索、排序u注意：每个问题都有一种和多种算法注意：每个问题都有一种和多种算法找到效率最高的找到效率最高的以最容易理解的方式设计以最容易理解的方式设计设计的算法不容易出错或出错情况较少设计的算法不容易出错或出错情况较少算法算法段景山段景山作业作业
