第4章：数据结构基本概念什么是数据结构数据数据是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。数据元素数据元素是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。学号姓名性别出生年月入学成绩结构结构是数据元素之间的关系关系2007001张红女1989.15902007002陈琳女1989.10610逻辑结构存储结构对数据的操作数据结构包括以下三方面内容数据结构包括以下三方面内容数据元素之间逻辑上的关系，是从具体问题抽象出来的数据模型，与具体的计算机无关。逻辑结构集合集合线性结构线性结构树型结构树型结构图状结构图状结构某学校教务处的职员表如下表所示：职工号职工号姓名姓名性别性别出生年月出生年月职务职务部门部门01王明华男1962.3.20处长02赵宁男1968.6.14科长教材科03张宁女1964.12.7科长考务科04赵书芳女1972.8.5主任办公室05刘永年男1959.8.15科员教材科06王明理女1975.4.1科员教材科07王敏女1972.6.28科员考务科08张才男1967.3.17科员考务科09马立然男1975.10.1科员考务科10程法男1976.7.5科员办公室集合结构集合结构只存在数据元素集合，不存在关系01040302050607080910线性结构线性结构特点：数据元素之间存在一对一一对一的关系05010308020710040609职工号姓名性别出生年月职务部门01王明华男1962.3.201962.3.20处长02赵宁男1968.6.141968.6.14科长教材科03张宁女1964.12.71964.12.7科长考务科04赵书芳女1972.8.51972.8.5主任办公室05刘永年男1959.8.151959.8.15科员教材科06王明理女1975.4.11975.4.1科员教材科07王敏女1972.6.281972.6.28科员考务科08张才男1967.3.171967.3.17科员考务科09马立然男1975.10.11975.10.1科员考务科10程法男1976.7.51976.7.5科员办公室树树型型结结构构数据元素之间存在一对多一对多的关系01020305060708090410职工号姓名性别出生年月职务部门01王明华男1962.3.20处长处长02赵宁男1968.6.14科长科长教材科03张宁女1964.12.7科长科长考务科04赵书芳女1972.8.5主任主任办公室05刘永年男1959.8.15科员科员教材科06王明理女1975.4.1科员科员教材科07王敏女1972.6.28科员科员考务科08张才男1967.3.17科员科员考务科09马立然男1975.10.1科员科员考务科10程法男1976.7.5科员科员办公室图结构图结构数据元素之间存在多对多多对多的关系03010205060704数据元素数据元素以及数据元素之间的数据元素之间的逻逻辑关系辑关系在计算机内存中的表示。存储结构数据元素的存储数据元素的存储：用一个存储单元(简称结点)存放每一个数据元素,每个存储单元称为一个结点。数据元素之间关系的存储数据元素之间关系的存储：也就是逻辑结构的计算机内部表示。存储结构包括以下两个主要部分顺序顺序存储结构链式链式存储结构索引索引存储结构散列散列存储结构数据的四种常用的存储结构数据的四种常用的存储结构顺序存储结构顺序存储结构3152224地址ff013ff0215ff0322ff0424特点特点：逻辑上相邻的元素物理位置也是相邻的。特点：逻辑上相邻的元素物理位置不一定是相邻的逻辑上相邻的元素物理位置不一定是相邻的。3152224…1016…1200…1250…1600………………15243221016160012000链式存储结构链式存储结构31522240数据的运算数据的运算是定义在逻辑结构逻辑结构上的一系列算法算法。例：查找、排序、增加、修改、删除等算法的概念算法的概念对具体问题求解过程和步骤的一种描述用自然语言描述用流程图描述类程序设计语言算法的描述方法算法的描述方法算法：1）设两个数分放到m和n两个变量中。2）用m除以n，取得余数r3)使m等于n的值，n等于r的值4）若r为0，则m的值即为最大公约数，否则继续执行步骤2例如：求两个数的最大公约数。开始输入整数m，nr=mmodnm=nn=rr=0?输出m结束main(){intm,n,r;scanf(“%d%d”,&m,&n);do{r=m%n;m=n;n=r;}while(r!=0);printf(“%d”,m);}有穷性确定性可行性零个或多个的输入有1个或多个的输出算法的特性算法的特性正确性可读性健壮性效率与低存储量需求算法设计的要求算法设计的要求时间复杂度时间复杂度(算...
