数据结构(长安大学)讲课PPT1

数据结构教师：杨云班级：24020803/04学院：长安大学信息工程学院地址：WM1506Email：[e-mail]课堂要求1按照学号坐，手机振动2写学习计划（考试，考研，编程）3统一尺寸作业本4考试严禁作弊，发现后本课程成绩记0‹‹数据结构››教材与参考书1.《数据结构》(C语言版)严蔚敏等清华大学出版社2009.72.《数据结构算法-VisualC++6.0程序集》侯识忠等中国水利水电出版社2005.53.《数据结构课程辅导与习题解析》胡元义等人民邮电出版社2003.34.《数据结构》算法实现及解析高一凡等清华大学出版社2008.75.《数据结构》知识点与典型例题解析杨明等清华大学出版社2005.96.任一本C语言教程（看基础部分），任一本操作系统教程（看存储管理一章）本课程的任务1.基本数据结构的定义、特性、运算与算法1.1线性结构：线性表；栈,队列,双队列（操作受限的线性表）；数组,串（线性表的高级语言表示）。1.2非线性结构：树,二叉树；图,网络。2.数据结构的存储结构与实现（顺序存储和链式存储结构）选择存储结构,设计算法3.查找算法：顺序,折半,分块,哈希,二叉排序树等4.排序算法：内部排序,外部排序5.文件（存在外存上的表）6.基本应用与综合应用注：第8章和带**号的章节自主学习。基本要求1.精读教材与阅读参考书；2.完成一定数量的书面作业；3.使用C或C++完成5个以上的上机作业。数据结构---------------------------------------------第一章绪论1.1什么是数据、结构(关系)、数据结构？1.2基本概念和术语1.3算法和算法分析第一章概述1.1什么是数据、结构(关系)、数据结构？例15个整数组成的集合：D={20,-5，66,15,44}其中:20,-5,66等称为数据元素(元素)，元素与元素之间关系是它们同属于集合D。D={20,-5,66,15,44}是一个数据对象例2一列整数：L=(20,-5，66,15,44）其中:元素与元素之间在L中是前后关系或线性关系。L=(20,-5,66,15,44)是一个线性表。例3一张登记表DL序号姓名性别年龄1李刚男25记录12王霞女29记录23刘大海男40记录34李爱林男44记录4其中：姓名、性别、年龄是数据项(item)、数据域(field)；(姓名，性别，年龄)是记录(record),C语言将记录(record)定义为”结构”(struct)；登记表也是一个线性表。例4二叉树TABDCEFG其中:A、B、C等是结点(node)；A与B,B与C,A与D之间是层次关系或父子关系。例5无向图GABDCEFG其中：A、B、C等是顶点(vertex),图中任意两个顶点之间都可能有关系。1.2基本概念和术语1.数据（data)----所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图象、图形等。2.数据元素(dataelement)---数据的基本单位。（元素、记录、结点、顶点）在计算机程序中通常作为一个整体进行考虑和处理。3.数据项(dataitem)----是数据的不可分割的最小单位。如：姓名、年龄等一个数据元素可由一个或多个数据项组成。如:(姓名、年龄)4.数据对象(dataobject)——由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。例1由4个整数组成的数据对象D1={20,-30,88,45}例2由正整数组成的数据对象D2={1,2,3,...}例3由26个字母组成的数据对象D3={A,B,C,...,Z}其中：D1，D3是有穷集，D2是无穷集。5.抽象数据对象ElemSet={某种同类型的数据元素}6.数据结构(datastructure)----相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系称为结构。四类基本结构：集合线性结构树形结构图状结构1.线性表2.栈线性结构3.队列,双队列4.数组数据结构5.字符串非线性1.树,二叉树结构2.图数据结构(逻辑结构)分类7.存储结构----数据结构在计算机存储器中的映象(mapping)。存储结构也称为：存储表示,物理结构,物理表示。(1)顺序存储结构(向量,一维数组)例.chara[5]={'A','B','C','D'}；ABCDE01234a是一维数组(2)非顺序存储结构(链接表）例.单链表datanext┌─┬┐┌─┬┐┌─┬┐┌─┬─┐Head─→│A│┼→│B│┼→│C│┼→│D│^│└─┴┘└─┴┘└─┴┘└─┴─┘4个结点的单链表8.数据类型（datatype)---是一个值的集合和定义在这个值上的一组操作的总称。(1)原子类型(如：int,char,float等)(2)结构类型(如：数组,结构,联合体等）9.抽象数据类型(AbstractDataType)----与计算机的实现无关的数据类型。形式定义：ADT抽象数据类型名{1.数据对象；2.数据关系:一个或多个关系；3.一组基本操作/运算}ADT抽象数据类型名注意：ElemType是抽象元素类型。1.3算法和算法分析1.算法----求解一个特定任务的指令的有限序列。例.求a[0..n-1]中n个数的平均值(假定n0)。floataverage(floata[],intn){inti；floats=0.0；//累加器赋初值for(i=0；in；i++)s=s+a[i]；//a[i]累加到s中s=s/n；//计算平均值printf(“ave=%f”,s)；//输出return(s)；//返回}其中：a,n为输入量；s为输出量。2.算法的5个特征(1)有穷性：在有限步(或有限时间)之后算法终止。例.{i=0；s=0；while(i10)s++；i++；}(2)确定性：无二义性。例.{x=5；y=10；z=x+++y；printf(“%d,%d,%d”,x,y,z)；}x+++y解释为：x+(++y)？(x++)+y？(3)可行性：可以在计算机上实现。for(i=1,s=0；i1000000000000；++i)s++；？？？(4)输入：有0或多个输入量。(5)输出：至少有一个输出量。3.算法设计要求(1)正确性a.无语法错误；b.对n组输入产生正确结果；c.对特殊输入产生正确结果；d.对所有输入产生正确结果。(2)可读性：“算法主要是为了人的阅读与交流”。(3)健壮性scanf(“%d”,&x)；y=log10(x)；？？？(4)高效与低存储量下列描述不符合算法的什么特征和要求？例1voidsuanfa1(){inti,s=0；for(i=0；i=0；i++)//死循环s++；//不能终止}例2floatsuanfa2(){intx,y；scanf(“%d”,&x)；y=sqrt(x)；//当x0时,出错return(y)；}算法描述举例问题：设一维数组a[0..n-1]中已有n个整数,其中n为常数,试设计算法:求a[]中的最大值。算法基本思想:1.maxai=a[0]；2.i=1；3.若i=n-1,则：3.1若a[i]maxai,则maxai=a[i]；3.2i++；3.3转34.maxai为最大值。Ｃ函数(算法)//求数组a中n个元素的最大值inta_maxint(inta[],intn){intj,maxai=a[0]；//最大值的初值for(j=1；j=n-1；j++)if(a[j]maxai)//比较元素大小maxai＝a[j]；//新的最大值printf(maxai＝%d\n,maxai)；//输出returnmaxai；}4.算法的时间复杂度----算法(或程序)中基本操作(或语句)重复执行的次数的总和。设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)；时间复杂度记作T(n),有：T(n)=O(f(n))例1{ints；scanf(“%d”,&s)；s++；printf(“%d”,s)；}其中：语句频度为：f(n)=f(1)=3时间复杂度为：T(n)=O(f(n))=O(3)=O(1）O(1)称成为常量阶/常量数量级例2分析下面的算法voidsum(inta[],intn){ints=0,i；//1次for(i=0；in；i++)//n次s=s+a[i]；//n次printf(“%d”,s)；//1次}其中：语句频度为：f(n)=1+n+n+1时间复杂度为：T(n)=O(f(n))=O(2n+2)=O(n）O(n)称成为线性阶/线性数量级例3分析下面的算法1.voidsum(intm,intn)2.{inti,j,s=0；//1次3.for(i=1；i=m；i++)//m次4.{for(j=1；j=n；j++)//m*n次5.s++；//m*n次6.printf(“%d”,s)；//m次7.}8.}其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1当m=n时,f(n)=2n2+2n+1T(n)=O(f(n))=O(2n2+2n+1)=O(n2)O(n2)称成为平方阶/平方数量级例4分析下面的算法1.voidsum(intn)2.{inti,j,s=0；//1次3.for(i=1；i=n；i++)//n次4.{for(j=1；j=i；j++)//?次5.s++；//?次6.printf(“%d”,s)；//n次7.}8.}例4分析下面的算法其中：第4行的次数为1+2+...+n=n(1+n)/2第5行的次数为1+2+...+n=n(1+n)/2f(n)=1+n+n(n+1)+n=n2+3n+1T(n)=O(f(n))=O(n2）O(n2）称成为平方阶/平方数量级例5冒泡排序的C语言算法//对数组a中n个数按递增次序作冒泡排序1.Voidbubble1(inta[],intn)2.{inti,j,temp；3.for(i=0；i=n-2；i++)//？次4.for(j=0；j=n-2-i；j++)//？次5.if(a[j]a[j+1])//？次6.{temp=a[j]；//？次7.a[j]=a[j+1]；//？次8.a[j+1]=temp；//？次9.}10.for(i=0；in；i++)//n次11.printf(“%d”,a[i])；//n次12.}思考：在最好情况下，f(n)=?T(n)=O(f(n))=?在最坏情况下，f(n)=?T(n)=O(f(n))=?例6冒泡排序的“类C语言”算法//对数组a中n个数按递增次序作冒泡排序1.voidbubble2(inta[],intn)2.{for(i=n-1,change=TRUE；i1&&change；i--)3.{change=FALSE；//change为交换标志4.for(j=0；ji；++j)5.if(a[j]a[j+1])6.{a[j]--a[j+1]；//交换元素7.change=TRUE；//修改交换标志8.}9.}10.}思考：在最好情况下，f(n)=?T(n)=O(f(n))=?在最坏情况下，f(n)=?T(n)=O(f(n))=?5.算法的空间复杂度----执行算法所需存储空间的大小。实际问题实际问题数据类型建立数据类型算法构造求解算法选择存储结构测试编程本章小结：存储结构（物理结构）——同样的逻辑结构≠同样的存储结构学习数据结构的方法①逻辑结构②运算定义③存储结构④实现运算⑤算法分析本章结束!