搜索
数据结构第1章绪论任雪萍renxp@hdu.edu.cn1.1什么是数据结构•利用计算机处理的问题类型–数值计算问题，主要用不同的数学方程来描述•例1利用有限元计算方法进行结构静力分析计算•例2利用环流模式方程进行天气预报计算–非数值计算问题，主要用不同的数据结构来描述•例1图书馆书目检索•例2计算机和人对奕问题•例3交通灯的控制系统计算机程序输入数据输出数据1.1什么是数据结构•程序–为计算机处理问题编制一组指令集•算法–处理问题的策略•数据结构–问题的数学模型Algorithm+DataStructures=Programs算法+数据结构=程序--NiklausWirth1.1什么是数据结构•数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。•数据结构课程所处的地位。1.2基本概念•数据（data）–是对客观事物的符号化表示，是构成信息和知识的原始材料•数据项（dataitem）–是构成数据的相对独立的基本单位，它反映客观事物的某种特性•数据元素（dataelement）–是构成数据的基本单元•数据对象（dataobject）–是具有相同性质的数据元素的集合，是数据的一个子集。整数数据对象是集合Ｎ＝{０，±１，±2，…}数据、数据项、数据元素例•例1–某个学生的姓名为“张三”，年龄为21岁，并有一张个人照片，那么姓名、年龄、照片就是三个不同的数据，分别用字符、数字和图像三种数据类型来表示•例2–结合姓名、年龄、照片三个数据，就构成了描述张三这个人的一个相对完整的组合数据—“学生”–对于“学生”这个数据而言，“姓名”、“年龄”、“照片”是三个分立的数据单位，也称数据项•例3–一个班级由多个学生组成，那么张三、李四等每个学生就是构成“班级”这个数据的数据元素1.2基本概念•数据结构（datastructure）–是相互之间存在一种或多种特定关系的数据元素的集合数据结构的二元组表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集数据结构例•例如一维数组是一种数据结构Array=D,S–数据元素的集合是D={a1,a2,…,an}–数据元素关系的集合是S={a1,a2,a2,a3,…an-1,an}其中ai-1,ai为有序对1.2基本概念•在一个数据结构中，数据元素之间的关系通常可分为4类基本的结构–集合•结构中的数据元素之中同属一个集合–线性结构•结构中的元素之间存在一个对一个的关系–树型结构•结构中的数据元素之间存在一个对多个的关系–图状结构或网状结构•结构中的数据元素之间存在多个对多个的关系数据结构例•学生选课问题–该问题可以用三张数据表来表示，每张表中每条记录为数据元素•如表中数据元素是无序的，则数据表构成集合结构•如表中数据元素是有序的，则数据表构成线性结构张三李四王五数据结构操作系统编译原理数据库原理学生表课程表选课表学号姓名课程号课程名称学号课程号成绩S0001张三C0001数据结构S0001C000185S0002李四C0002操作系统S0001C000376S0005王五C0003编译原理S0002C000190C0004数据库原理S0002C000483S0003C000292–数据结构例树……..……..…...…...…...…...数据结构例•地图表示问题–左图的地图经抽象可以得到右图的结构–右图构成了图状的数据结构南京市镇江市常州市无锡市苏州市上海市湖州市嘉兴市杭州市1.2基本概念•数据的逻辑结构–抽象描述数据元素之间的逻辑关系•数据的存储结构（也称物理结构）–数据的逻辑结构在计算机存储器中的实现•顺序存储结构：在物理存储上数据是按逻辑顺序存放的•链式存储结构：在物理存储上数据非顺序存放，而是通过指针链来描述数据间的逻辑关系•索引存储结构:存储地址连续，借助索引表来表示元素间的逻辑关系•散列存储结构:按散列函数来确定存储位置元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈、队列、串数组、广义表树形结构图形结构数据结构的三个方面：集合索引、散列存储1.2基本概念•在软件开发过程中，数据的逻辑结构和存储结构分别在不同的时期考虑–算法设计时，考虑的是数据的逻辑结构–算法实现时，考虑的是数据的存储结构1.2基本概念•数据类型–一个值的集合和定义在这个值集上的一组操作的总称–数据类型可分为•原子类型：数据的值是不可分解的•结构类型（复合类型）：数据的值是由若干成份（数据项或数据元素）构成的C/C++语言的数据类型•字符型char整型int浮点型float双精度浮点型double•逻辑型（C++）•指针型*•引用型&（C++）•空类型void•数组[]、结构体struct、联合体union、枚举enum等复合类型•用户自定义的数据类型typedeftypedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;预定义常量和类型•＃defineTRUE1•＃defineFALSE0•＃defineOK1•＃defineERROR0•＃defineINFEASIBLE-1•＃defineOVERLOW-2•typedefintStatus1.2基本概念•抽象数据类型（ADT，AbstractDataType）–是指一个数学模型以及定义在该模型上的一组操作–可以用三元组定义(D,S,P)•D是数据对象•S是D上的关系集•P是对D的基本操作集–抽象数据类型和数据类型实际上是一个概念抽象数据类型例ADTSet//集合的抽象数据类型{数据对象：D＝{ai|ai∈ElemType,i=1,2,...,n,n≥0}数据关系：R={ai≠aj|ai,aj∈D}基本操作：Init()操作结果：构造一个空的集合。Destroy()操作结果：销毁集合。IsEmpty()操作结果：判断集合是否为空，如为空，则返回TRUE；否则返回FALSE。Insert(e)操作结果：在集合中加入一个元素。如元素已存在，返回FALSE；否则返回TRUE。Remove(e)操作结果：在集合中移除一个元素。如元素存在，则返回TRUE；否则返回FALSE。IsMember(e)操作结果：判断在集合中是否存在元素。FindFirst(&e)操作结果：找到集合中的第一个元素。如成功，返回TRUE；如果集合为空，返回FALSE抽象数据类型例FindFirst(&e)操作结果：找到集合中的第一个元素。如成功，返回TRUE；如果集合为空，返回FALSEFindNext(&e)初始条件：已经执行过FindFirst或FindNext操作操作结果：在上一次查找的前提下，找到集合中的下一个元素；如成功，返回TRUE；如上次查找已到最后一个元素，返回FALSE。Union(s)操作结果：与另一个集合s做并运算，返回并集。Intersection(s)操作结果：与另一个集合s做交运算，返回交集。Difference(s)操作结果：与另一个集合s做差运算，返回差集。}软件系统开发过程中的数据层次模型•在软件系统开发的全过程中，对客观现实中存在的事物，存在三个观察层面–应用层是用户通过物理观察得到的客观事物的视图，是可以用自然语言描述的，或用图形、图像、音频、视频等物理量表达的在概念层次上的数据。–逻辑层（抽象层）是从应用层次抽象出来的数据视图，利用抽象数据类型进行形式化描述。–实现层明确地用某种数据结构来表达抽象数据类型，并用某种具体的程序设计语言进行代码实现。应用层逻辑层（抽象层）实现层观察归纳、抽象编写程序代码客观事物1.3算法和算法分析•算法（algorithm）–解决某一特定问题的具体步骤的描述，是指令的有限序列–五个特征•有穷性•确定性•可行性•输入•输出–算法设计的要求•正确性：四个层次•可读性•健壮性（当输入数据不合法时，算法也能做出相关处理，而不是产生异常）•高效率与低存储量需求1.3算法和算法分析•算法效率的度量–事后统计的方法•可采用一些程序运行性能跟踪与测量工具（如Profiler）–事前分析估算的方法•不考虑算法的实现语言、编译器、运行的硬件平台，只考虑在一定问题规模下算法运行的时间复杂度和空间复杂度和算法执行时间相关的因素1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度1.3算法和算法分析•时间的复杂度–从算法中选取一对于所处理问题来说是基本操作的原操作，该基本操作重复执行的次数－语句频度(frequencycount)作为算法的时间量度。–基本操作重复执行的次数一般为问题规模n的某个函数f(n)，因此时间的复杂度T(n)记作T(n)=O(f(n))•上式表示随着问题规模n的增长，算法执行时间T(n)和f(n)同比增长分析下列3个算法(片段)(a)x=x+1;语句频度:1时间复杂度:T(n)=O(1)(b)for(i=1;i=n;i++)x=x+1;语句频度:n时间复杂度:T(n)=O(n)(c)for(j=1;j=n;j++)for(k=1;k=n;k++)x=x+1;语句频度:n2时间复杂度:T(n)=O(n2)分析算法voidsimsort(ara[],intn){for(i=1;in;i++)for(j=i;j=n;j++)if(a[i].dataa[j].data){m=a[i];a[i]=a[j];a[j]=m;}for(i=1;i=n;i++)couti“”a[i].num“”a[i].dataendl;}2)1(123......)2()1(nnnnn最大语句频度：时间复杂度例•语句++x为三个算法的基本操作，问题规模为n•三段程序中基本操作的执行次数分别为1、n和n2•故三段程序的时间复杂度分别为O(1)、O(n)和O(n2)，称为常量阶、线性阶和平方阶//例1{++x;//基本操作s=0;}//例2for(i=0;in;++i){++x;//基本操作s+=x;}//例3for(i=0;in;++i)for(j=0;jn;++j){++x;//基本操作s+=x;}时间复杂度例•语句++x为算法的基本操作•算法中基本操作的执行次数是0+1+….+(n–2)=(n–1)(n–2)/2//例4for(i=2;i=n;++i)for(j=2;j=i-1;++j){++x;//基本操作s+=x;}怎样估算？1.忽略低次幂n2/2+3n/2-n2/22.忽略常系数n2/2-n2最大语句频度：3.所以算法的时间复杂度:T(n)=O(n2)0+1+….+(n–2)=(n–1)(n–2)/2如何估算时间杂度分析下列算法(片段)•(1){i=1;k=0;•while(i=n-1)•{k=k+10*i;•i++;•}•}•(2){i=1;k=0;n=100;•do{•k=k+10*i;•i++;•}while(i==n);•}语句频度时间复杂度n-1T(n)=0(n)1T(n)=0(1)1.3算法和算法分析•空间的复杂度–根据问题规模n，算法执行所需要的存储空间大小的量度–空间的复杂度S(n)记作S(n)=O(f(n))算法的存储量1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间1．输入数据所占空间2．程序本身所占空间若输入数据所占空间只取决于