01.绪论

数据结构与算法前期课程数据结构计算机基础C/C++语言离散数学线性代数后期课程操作系统计算机组成原理编译原理数据库原理软件工程计算机网络承上启下计算机科学课程体系C/C++语言数据结构软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）1.1数据结构研究的内容随着计算机技术的发展，计算机应用的范围更广，所处理的数据更复杂。如果要提高数据处理的效率，就必须研究数据本身的特性、数据之间的关系，已经如何有效地将数据组织存储在计算机内。理论课逐步求精的程序设计过程问题数学模型数据结构抽象数据类型源程序实验课数据结构课程的内容课程设计用计算机解决具体问题大致需要下列几个步骤：1）首先从具体问题抽象出一个数学模型；2）然后设计一个解此数学模型的算法；3）最后编写程序、测试、调整直至最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述。下面请看三个例子。【例1-1】公司员工信息管理。某公司要用计算机管理员工信息。要求做以下操作：当招聘新员工时，能够把员工信息添加进来；当有员工辞职时，能够删除该员工信息；可以修改员工信息；能够以某种方式检索员工信息。员工号姓名性别年龄住址电话所属部门01002王清男25南京路23号3564财务01003李丽圆女28甘肃路59号3698总务………………………………模型——线性表员工号姓名性别年龄住址电话所属部门【例1-2】NBA季后赛对阵形势。进入季后赛的16只球队，分成东部和西部两个赛区，每赛区8只球队进行淘汰赛，胜者进入下一轮，这样在两个赛区中分别产生一名冠军，最后在这两名冠军之间产生总冠军。现在希望得到各队对阵形势以及输赢情况。模型——树【例1-3】泰山3日游。某旅行社想要开辟泰山旅游线路，为了降低成本，决定采用火车作为交通工具，但希望乘车时间越少越好，以便增加游览时间，从而吸引更多游客。模型——图数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。主要研究：数据元素之间固有的逻辑关系——数据逻辑结构；数据元素及关系在计算机内的表示——数据存储结构；对数据结构的操作——算法。1.2基本概念和术语数据数据元素数据对象数据结构数据是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符、声音、图像等)的集合，它是计算机操作对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据的集合表示数据={x|x是计算机操作的对象}1.2.1数据1.2.2数据元素数据结构中讨论的基本单位数据整体中相对独立的单位两类数据元素不可分割的“原子”型数据元素整数5，字符N等多个数据项构成的数据元素数据项是数据不可分割的最小标识单位。员工号姓名性别年龄电话所属部门01002王清男253564财务1.2.3数据对象性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象集合：N={0，±1，±2，…}，字母字符数据对象集合：C={‘A’，‘B’，…，‘Z’}。1.2.4数据结构定义是相互之间存在一种或多种特定关系的数据元素的集合。特点数据元素集合相同，而其上的关系不同，则构成的数据结构不同。内容数据的逻辑结构数据的存储结构数据的操作【例1-4】宿舍管理的数据结构数据元素班主任，班长1，班长2，舍长1…舍长p,学生1…学生n。关系班主任，班长1，班主任，班长2，班长1，舍1，……，班长2，舍长p舍长1，学生1，……，舍长p，学生n数据结构的形式定义：数据结构是一个二元组DS=(D,R)其中：D是数据元素的有限集，R是D上关系的有限集。关系的表示序偶：有序对。例如：班主任，班长1前驱：序偶中第一元素为第二元素的前驱后继：序偶中第二元素为第一元素的后继数据结构的三个方面数据结构的三个方面1数据的逻辑结构3数据的运算：检索、排序、插入、删除、修改等2数据的存储结构(亦称物理结构)非线性结构线性结构线性表栈队列串树形结构图形结构集合结构顺序存储链式存储散列存储索引存储数据的逻辑结构对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。数据的逻辑结构可看作是从具体问题抽象出来的数学模型。数据的存储结构数据元素及其关系在计算机内的表示。逻辑结构可以映射为以下四种存储结构：顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：借助指针表达数据元素间的逻辑关系。不要求逻辑上相邻的数据元素在物理位置上也相邻。索引存储结构：在存储数据元素的同时，还建立附加的索引表。通过索引表，可以找到存储数据元素的节点。散列存储结构：根据散列函数和处理冲突的方法确定数据元素的存储位置。数据的操作在数据的逻辑结构上定义的操作算法。如插入、删除同一种数据的逻辑结构可以映射为多种存储结构今后在学习每一种数据结构时都会从逻辑结构、存储结构和操作三方面入手。1.3抽象数据类型数据元素集合以及定义在该集合上的一组操作，简称为ADT（AbstractDataType）。“抽象”指与具体实现无关，仅考虑能做什么，而不考虑如何做。形式描述ADT=(D，R，P)其中：D是数据对象，R是D上的关系集，P是D的基本操作集。抽象数据类型重要特性数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的实现面向对象——类面向过程——结构体【例1-5】复数数据类型的抽象描述分析：定义——实部＋i虚部实部和虚部的取值范围——实数复数的操作——＋、－、×、％ADT复数的数据类型抽象数据对象：D={e1,e2|实数}数据关系：R1={e1,e2|e1是复数的实部，e2是复数的虚部}用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)操作结果：用sum返回两个复数z1，z2的和值。EndADTComplex思考如何进行复数相加Complexr1,r2,sum;Add(r1,r2,&sum);【例1-6】矩形数据类型抽象描述分析：定义——长、宽长和宽的取值范围——实数矩形的操作——初始化(构造)矩形、计算矩形的周长和面积ADTRECtangleis数据对象：D={e1,e2|实数}数据关系：R1={e1,e2|e1是长，e2是宽}基本操作:InitRectangle(r,len,width);操作结果：初始化矩形长和宽Circumference(r);操作结果：计算矩形周长Area(r);操作结果：计算矩形面积EndRECtangle1.4算法分析算法就是求解问题的一系列步骤的集合。通常把具体存储结构上的操作实现步骤或过程称为算法【例1-7】求n个整数中的最大值。1.将第1个数赋值给max；2.初始化计数器变量i为1；3.当in时，执行以下语句：(1)比较a[i]与max，若a[i]max，则将a[i]赋值max；(2)i自增1；4.返回max的值。程序＝数据结构＋算法算法的特性（性质）有穷性：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。确定性：每条指令必须有确切的含义，不能有二义性。可行性：算法中描述的操作都是用已经实现的基本运算组成。输入：可以有0、1、或多个输入量。输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。考虑下列两段描述：(1)描述一voidexam1(){n＝2;while(n%2＝＝0)n＝n+2;coutnendl;}华中科大考研题(2)描述二voidexam2(){y=0;x=5/y;coutx‘,’yendl;}这两段描述均不能满足算法的特征,试问它们违反了哪些特征？解：(1)算法是一个死循环,违反了算法的有穷性特征。(2)算法包含除零错误,违反了算法的可行性特征。算法的评价（设计准则）正确性除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。健壮性算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。可读性易于理解、实现和调试。高效性执行时间短（时间效率）、占用存储空间少（空间效率）时间复杂度一般用算法中语句被执行的次数来表示算法的时间效率（算法的时间复杂度）。【例1-8】分析下面程序段的时间复杂度。(1)inti,sum=0;(2)for(i=0;in;i++)(3)sum=sum+i;(4)returnsum;T(n)=2n+3，且T(n)是n数量级的。渐进时间复杂度：忽略次要语句的执行次数，只对重要的语句（原操作）和执行最频繁的语句进行计数，同时对计算结果只取其最高次幂，且略去系数不写。渐近时间复杂度常简称为时间复杂度，用“大o”表示。T(n)=2n+3=O(n)（1次）（n+1次）（n次）（1次）也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。例如,T(n)=3n2-5n+10000=O(n2)本质上讲，是一种最高数量级的比较一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶。一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。各种不同数量级对应的值存在着如下关系：O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)【例1-9】分析以下算法的时间复杂度。intfun(intn){inti,j,k,s;s=0;for(i=0;i=n;i++)for(j=0;j=n;j++)for(k=0;k=n;k++)s++;return(s);}基本语句或基本操作解：该算法的基本操作是语句s++,其频度：T(n)=O(n3)则该算法的时间复杂度为O(n3)。