数据结构（C语言描述）.ppt

《数据结构（C语言描述）.ppt》由会员分享，可在线阅读，更多相关《数据结构（C语言描述）.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构（C语言描述）语言描述）计算机系计算机系 刘延芳刘延芳1/6/2023第章第章 程序程序第一章第一章 绪绪 论论l1.1 引引 言言 l1.2 数据结构发展简史及学科地位数据结构发展简史及学科地位l1.3 什么是数据结构什么是数据结构l1.4 基本概念和术语基本概念和术语l1.5 算法概念算法概念、算法的描述算法的描述和和 算法评价算法评价l 练习练习1:38 AM第章第章 程序程序引引 言言l20世纪世纪40年代年代(1946),为了解决弹道轨迹计算问题而产生计算机。早为了解决弹道轨迹计算问题而产生计算机。早期，计算机应用范围局限于科学和工程计算期，计算机应用范围局限于科学和

2、工程计算,处理对象是纯数值性信处理对象是纯数值性信息息,人们称这类问题为人们称这类问题为“数值计算数值计算”。l如今如今,计算机应用远远超出数值计算范围计算机应用远远超出数值计算范围,渗透人类生活的一切领域。渗透人类生活的一切领域。计算机处理对象也从纯数值发展到计算机处理对象也从纯数值发展到非数值性非数值性和具有一定结构的信息。和具有一定结构的信息。l现代计算机科学的观点，把计算机程序处理的一切数值的、非数值信现代计算机科学的观点，把计算机程序处理的一切数值的、非数值信息、乃至程序统称数据（息、乃至程序统称数据（Data），），而计算机只是处理数据的工具。而计算机只是处理数据的工具。l处理对象

3、的转变导致系统和应用程序的规模越来越大，结构也相当复处理对象的转变导致系统和应用程序的规模越来越大，结构也相当复杂，单凭程序员经验和技巧已难以设计效率高、可靠性强的程序。杂，单凭程序员经验和技巧已难以设计效率高、可靠性强的程序。l数据的表示方法和组织形式成为处理数据效率的关键。即研究数据的数据的表示方法和组织形式成为处理数据效率的关键。即研究数据的特性以及数据间存在的关系特性以及数据间存在的关系数据结构（数据结构（Data Structure）本章介绍本章介绍了数据结构这门学科诞生的背景了数据结构这门学科诞生的背景,发展历史以及在计算机发展历史以及在计算机科学中所处的地位科学中所处的地位,重点

4、介绍了数据结构有关的概念和术语重点介绍了数据结构有关的概念和术语,读者学读者学习本章后应能掌握数据习本章后应能掌握数据,数据元素数据元素,逻辑结构逻辑结构,存储结构存储结构,数据处理数据处理,数数据结构据结构,算法设计等基本概念算法设计等基本概念,并了解如何评价一个算法的好坏。并了解如何评价一个算法的好坏。1:38 AM第章第章 程序程序发展简史及学科地位发展简史及学科地位l数据结构随着计算机产生和发展而发展起来的一门较新学科。数据结构随着计算机产生和发展而发展起来的一门较新学科。l1968年年开始设立这门课，由美国教授开创数据结构的最初体系。观点是：开始设立这门课，由美国教授开创数据结构的最

5、初体系。观点是：认为程序设计的实质是对确定的问题选择一种好的结构，加上一种好的认为程序设计的实质是对确定的问题选择一种好的结构，加上一种好的算法。算法。l研究内容：软件设计中常用的基本技术研究内容：软件设计中常用的基本技术l地位：核心课程之一，也是非计算机专业的主修课程之一地位：核心课程之一，也是非计算机专业的主修课程之一l数据结构是介于数学、计算机硬件和软件之间的学科。数据结构是介于数学、计算机硬件和软件之间的学科。1:38 AM第章第章 程序程序什么是数据结构什么是数据结构l用计算机解决一个具体问题的步骤：用计算机解决一个具体问题的步骤：l1.从具体问题中抽象出一个适当的数学模型从具体问题

6、中抽象出一个适当的数学模型l2.设计一个解此数学模型的算法设计一个解此数学模型的算法l3.编出程序、进行测试、调整直至得到最终解答编出程序、进行测试、调整直至得到最终解答l例如：在例如：在(有规律有规律)学生通讯录中，学生通讯录中，1.按照索引查找某一学生按照索引查找某一学生 2.插入和删插入和删除一个学生记录？除一个学生记录？l数据结构直接影响算法的选择和效率。数据结构直接影响算法的选择和效率。l数据结构：数据结构：研究程序设计中计算机研究程序设计中计算机操作对象操作对象及其及其关系和运算关系和运算的一门学科的一门学科1:38 AM第章第章 程序程序基本术语基本术语(1)l1.数据数据:一切

7、能够输入到计算机中并被其处理一切能够输入到计算机中并被其处理的信息的信息(文字文字,表格图像等表格图像等)。l2.数据元素数据元素:也称结点也称结点,记录记录,顶点。是组成数据的基本单位。通常作顶点。是组成数据的基本单位。通常作为一个整体考虑和处理。为一个整体考虑和处理。如图：每一行作为基本单位考虑如图：每一行作为基本单位考虑。l3.字段字段:一个结点中含有若干个字段一个结点中含有若干个字段(也叫数据项也叫数据项).是构成数据的最是构成数据的最小单位。小单位。l4.逻辑结构：逻辑结构：结点与结点间的逻辑关系。结点与结点间的逻辑关系。如图如图:逻辑上是种线性关系逻辑上是种线性关系。l5.存储结构

8、：存储结构：数据在计算机中的存储表示。数据在计算机中的存储表示。如图：表格数据可有多如图：表格数据可有多种存储表示种存储表示(如：数组、文件等如：数组、文件等)l6.数据结构数据结构：组成数据元素之间构造关系。组成数据元素之间构造关系。登录号登录号书号书号书书 名名作者作者出版社出版社价格价格00001TP22高等数学高等数学陈灯陈灯高等教育高等教育56.0000002TP23实用英语实用英语丁萍丁萍电子工业电子工业20.5000003TP24电子商务通电子商务通江涛江涛中央电大中央电大18.801:38 AM第章第章 程序程序数据逻辑结构数据逻辑结构l1.逻辑结构的四种基本结构：逻辑结构的四

9、种基本结构：l(1)集合：集合：结构中的数据元素除了同属于一种类结构中的数据元素除了同属于一种类 型外，别型外，别无其它关系。无其它关系。l(2)线性结构线性结构：结构中的数据元素间存在一对一的关系。：结构中的数据元素间存在一对一的关系。l(3)树形结构树形结构：结构中的数据元素间存在一对多的关系。：结构中的数据元素间存在一对多的关系。l(4)图形或网状结构：图形或网状结构：结构中的数据元素之间存在多对多的结构中的数据元素之间存在多对多的关系。关系。l2.数据的逻辑结构分为线性结构和非线性结构两大类。数据的逻辑结构分为线性结构和非线性结构两大类。l(1)线性结构线性结构:包括数组、链表、包括数

10、组、链表、栈、队列、优先级队列等栈、队列、优先级队列等;l(2)非线性结构非线性结构:包括树、图等包括树、图等.1:38 AM第章第章 程序程序存存 储储 结结 构构常见存储结构：常见存储结构：l(1)顺序存储结构：顺序存储结构：特点是借助于数据元素的相对存储位置特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构来表示数据元素之间的逻辑结构.l即逻辑上相邻即逻辑上相邻,物理上也相邻物理上也相邻.l(2)链式存储结构：链式存储结构：特点是借助于指示数据元素地址的指针特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。表示数据元素之间的逻辑结构。l(3)索引存储结构索引存储结

11、构:l(4)散列存储结构散列存储结构:1:38 AM第章第章 程序程序基本术语基本术语(2)l一般：一般：把数据的逻辑结构统称为数据结构把数据的逻辑结构统称为数据结构，把数据的物理结构统称为存，把数据的物理结构统称为存储结构。储结构。l说明：说明：一个算法的设计取决于选定的数据（逻辑）结构一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现，而算法的实现依赖于采用的存储结构。我们的重点是算法的设计。依赖于采用的存储结构。我们的重点是算法的设计。数据数据 数据元素数据元素 字段字段数据结构数据结构分解分解描述描述l逻辑结构逻辑结构:结点与结点间的逻辑关系。不依赖于具体形式结点与结点间的逻辑关

12、系。不依赖于具体形式l存储结构：存储结构：数据在计算机中的存储表示。数据在计算机中的存储表示。l运算：运算：是最终目的是最终目的1:38 AM第章第章 程序程序基本术语基本术语(3)l7.数据处理：数据处理：对数据进行查找、插入、删除、合并、排序统计及简单计对数据进行查找、插入、删除、合并、排序统计及简单计算等操作过程。算等操作过程。l8.数据类型：数据类型：指程序设计语言中各变量可取的数据种类。指程序设计语言中各变量可取的数据种类。l即是一个即是一个值的集合值的集合和定义在此值集上的和定义在此值集上的一组操作一组操作总称总称l按按“数据类型数据类型”性质分类性质分类：l(1)原子类型：其值是

13、不可分解的原子类型：其值是不可分解的.(整整,实实,字字,枚枚,指指,空类型空类型)l(2)结构类型：其值按某种结构组成结构类型：其值按某种结构组成(由若干成分由若干成分)，如：数组，如：数组例如：例如：C语言中，整型变量语言中，整型变量其值集：其值集：在某个区间上整数在某个区间上整数 操作：操作：加加,减减,乘乘,除除,求模等运算求模等运算1:38 AM第章第章 程序程序算法的概念算法的概念l1.算法算法解决某一类问题的求解方法解决某一类问题的求解方法 执行特定计算的有穷过程（即指令的有限序列执行特定计算的有穷过程（即指令的有限序列）l2.算法的特点：算法的特点：l(1)动态有穷动态有穷:即

14、有限性即有限性;经过有限步骤后，算法一定要终止。经过有限步骤后，算法一定要终止。l(2)确定性确定性:指令无二义性指令无二义性.在任何条件下在任何条件下,算法只有一条惟一的执行路算法只有一条惟一的执行路径。径。l(3)输入输入：有：有0N个个 (4)输出输出：有：有1N个个l(5)可行性可行性:每条指令都充分基本每条指令都充分基本,即每条指令均可用有限次的计算机即每条指令均可用有限次的计算机指令来实现。指令来实现。l3.算法与程序比较算法与程序比较l(1)程序是算法在计算机程序设计语言中的具体实现程序是算法在计算机程序设计语言中的具体实现。通常定义一个。通常定义一个算法必须提供足够细节算法必须

15、提供足够细节,才能转化为程序。才能转化为程序。(多个程序表示同一算法多个程序表示同一算法)l(2)算法的有穷性算法的有穷性意味着不是所有程序都是算法意味着不是所有程序都是算法.例如例如;操作系统是一操作系统是一个程序不是算法个程序不是算法,但把操作系统各种任务看成单独问题但把操作系统各种任务看成单独问题,每个问题是由每个问题是由特定算法实现特定算法实现,得到输出结果便终止。得到输出结果便终止。l(3)算法和程序是相互独立的算法和程序是相互独立的。1:38 AM第章第章 程序程序算法的描述算法的描述l1.自然语言自然语言l2.伪代码和伪代码和流程图流程图l3.计算机高级程序语言计算机高级程序语言

16、（例如（例如C语言）语言）l4.C语言语法结构语言语法结构1:38 AM第章第章 程序程序自然语言自然语言例：设计算法：求一元二次方程例：设计算法：求一元二次方程ax2+bx+c=0的根。的根。1.计算计算d=b*b-4*a*c2.如果如果d0，计算计算x1=(-b+sqrt(d)/(2*a)3.x2=(-b-sqrt(d)/(2*a)3.如果如果d=0，计算计算x=(-b)/(2*a)4.如果如果d0计算x1x2并显示d=0计算x并显示显示无根流流程程图图1:38 AM第章第章 程序程序计计 算算 机机 语语 言言void solution (float a,float b,float c)

17、float d,x,x1,x2;d=b*b-4*a*c;if (d0)x1=(-b+sqrt(d)/(2*a);x2=(-b-sqrt(d)/(2*a);printf(“两个实根：两个实根：x1=%f,x2=%fn”,x1,x2);else if (d=0)x=(-b)/(2*a);printf(“一个实根：一个实根：x1=%fn”,x);else printf(“不存在实根不存在实根n”);main()float a,b,c;printf(“请输入请输入a,b,c：”);scanf(“%f,%f,%f”,&a,&b,&c);solution (a,b,c);计算机语言计算机语言1:38 AM

18、第章第章 程序程序C语言语法结构语言语法结构(1)1.输入语句输入语句 scanf(“格式字符串格式字符串”，输出项表输出项表)；2.输出语句输出语句 printf(“格式字符串格式字符串”，输出项表输出项表)；3.赋值语句赋值语句 变量名变量名=表达式；表达式；4.条件语句条件语句 if ；或者或者 if else ;1:38 AM第章第章 程序程序C语言语法结构语言语法结构(2)5.循环语句循环语句 while ；do ；while ；for（；;）;6.定义函数语句定义函数语句 （，）；7.调用函数语句调用函数语句 （，）8.返回语句返回语句 return()1:38 AM第章第章 程序

19、程序算法的评价算法的评价l1.算法评价目的算法评价目的:选择合适算法或对已有的算法进行改进选择合适算法或对已有的算法进行改进。l2.通常设计一个好的算法应考虑：通常设计一个好的算法应考虑：l(1)正确性正确性首要条件首要条件l(2)运行时间运行时间:算法的时间复杂度算法的时间复杂度(即即:执行一个简单操作所需执行一个简单操作所需时时 间与操作次数的乘积间与操作次数的乘积)。l(3)占用存储空间占用存储空间:算法的空间复杂度算法的空间复杂度(含存储算法本身含存储算法本身,算法算法输输 入输出数据和算法运行过程中临时占用空间入输出数据和算法运行过程中临时占用空间)。l(4)简单性简单性:算法易于理

20、解算法易于理解,易于编码及调试。易于编码及调试。l3.算法的时间复杂度算法的时间复杂度和空间复杂度和空间复杂度S(n)=O(f(n)一般用数量级一般用数量级来表示来表示。l4.举例举例1:38 AM第章第章 程序程序时间复杂度时间复杂度(Time Complexity)Time Complexity)（1）l算法在计算机中运行时间受很多因素算法在计算机中运行时间受很多因素(与计算机系统的软硬件环境有与计算机系统的软硬件环境有关关)的影响。通常利用语句频度和渐进时间复杂度衡量时间复杂度。的影响。通常利用语句频度和渐进时间复杂度衡量时间复杂度。l1.语句频度语句频度指该语句被执行的次数。指该语句被

21、执行的次数。l(1)任何算法都可分解为简单操作任何算法都可分解为简单操作(如赋值、比较、移位等如赋值、比较、移位等)来执行来执行.l(2)假设执行每条语句所需时间为单位时间假设执行每条语句所需时间为单位时间,则算法运行时间转化则算法运行时间转化为为所有语句执行次数所有语句执行次数,即语句频度之和（即语句频度之和（频度统计法频度统计法）。）。l2.一般情况下一般情况下,语句频度是问题规模语句频度是问题规模n的函数的函数,用用T(n)表示表示,若有某个若有某个辅助函数辅助函数f(n)使：使：l则称则称f(n)与与 T(n)同阶同阶,记作记作:T(n)=O(f(n)lO(f(n)表示时间复杂度表示时

22、间复杂度(或称渐进时间复杂度或称渐进时间复杂度),f(n)是最大语频是最大语频l3.例题例题 求求n！算法时间复杂度算法时间复杂度1:38 AM第章第章 程序程序时间复杂度时间复杂度(Time Complexity)Time Complexity)（2）l4.算法分析的几个方法：算法分析的几个方法：l(1)执行一些简单的输入执行一些简单的输入,输出或赋值语句时输出或赋值语句时,可近似认为需要可近似认为需要O(1)时间时间.l(2)对于对于顺序结构顺序结构,需要依次执行一系列语句所需时间可采用需要依次执行一系列语句所需时间可采用累加求和累加求和的的方式进行估计方式进行估计l(3)对于对于选择结构

23、选择结构,如如if语句。它的时间主要消耗在执行语句。它的时间主要消耗在执行then子句或子句或else子句时所用的时间，但子句时所用的时间，但if语句语句判断条件判断条件本身也消耗本身也消耗O(1)的的时间时间l(4)对于对于循环语句循环语句,它的时间主要耗费在它的时间主要耗费在执行循环体执行循环体以及以及循环条件的检验循环条件的检验上上,可采用可采用乘法计算乘法计算出算法的语频出算法的语频,从而得到算法时间复杂度。从而得到算法时间复杂度。l(5)对于较为对于较为复杂算法复杂算法,采用先采用先分解分解为几个容易估计的部分为几个容易估计的部分,然后利用然后利用求求和和方法计算出整个算法的时间复杂

24、度。方法计算出整个算法的时间复杂度。l5.求两个求两个n*n矩阵相乘算法矩阵相乘算法l6.时间复杂度综合考虑时间复杂度综合考虑1:38 AM第章第章 程序程序时间复杂度综合考虑时间复杂度综合考虑l1.由于算法时间复杂度考虑的只是问题规模由于算法时间复杂度考虑的只是问题规模n的增长率的增长率,在难以精在难以精确计算语句频度的情况下确计算语句频度的情况下,只需求出只需求出关于关于n的增长率或阶数的增长率或阶数即可。即可。l2.有时算法时间有时算法时间复杂度复杂度与算法处理的与算法处理的输入数据集输入数据集有关有关,算法的时间算法的时间复杂度难以确定。这时一般采用算法在复杂度难以确定。这时一般采用算

25、法在最坏的情况下复杂度最坏的情况下复杂度作为作为时间复杂度。时间复杂度。l例如：在排序算法中例如：在排序算法中,要求从小到大排序要求从小到大排序.l若给定输入集为从若给定输入集为从大到小最坏情况大到小最坏情况,时间复杂度为时间复杂度为T(n)=O(n2)l若若不作特别说明不作特别说明,以后各章均为最坏情况时间复杂度。以后各章均为最坏情况时间复杂度。l3.在分析时间复杂度是在分析时间复杂度是,随着问题规模随着问题规模n的增大，各种时间复杂度的增大，各种时间复杂度存在下列大小关系：存在下列大小关系：数量级的大小顺序：数量级的大小顺序：lO(1)O(log2n)O(n)O(nlog2n)O(n2)O

26、(n3)O(2n)(n!)1:38 AM第章第章 程序程序例题例题 求求n！算法时间复杂度算法时间复杂度例题：求例题：求n！算法时间复杂度算法时间复杂度lVoid fact(int n)int i,total;total=1;/*1次次*/for(i=1;i=n;i+)/*n次次*/total=total*i;/*n次次*/printf(“%d”,total);/*1次次*/l算法语频之和为算法语频之和为T(n)=2n+2,取取f(n)=n，则则l因此因此,其同阶表示形式为其同阶表示形式为T(n)=O(n)，即算法时间复杂度即算法时间复杂度O(n)1:38 AM第章第章 程序程序求两个求两个n

27、*n矩阵相乘算法矩阵相乘算法例题：求两个例题：求两个n*n矩阵相乘算法矩阵相乘算法lfor(i=1;i=n;i+)/*语频语频n*/for(j=1;j=n;j+)/*n*n*/c i j=0;/*/for(k=1;k=n;k+)/*/c i j+=a i k*b k j /*算法的主要部分算法的主要部分*/l算法主要部分在第三层循环中算法主要部分在第三层循环中,乘法运算是矩阵相乘算法的基本操乘法运算是矩阵相乘算法的基本操作作,共执行共执行n3。因此因此,整个算法的执行时间与该基本操作重复次数整个算法的执行时间与该基本操作重复次数n3成正比，其时间复杂度为成正比，其时间复杂度为O(n3)1:38

28、 AM第章第章 程序程序举举 例例数量级的大小顺序：数量级的大小顺序：lO(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)(n!)求时间复杂度：求时间复杂度：while (in)i=i*2;O(log2n)次数 1 2 k i242k =nk=log2n1:38 AM第章第章 程序程序练练 习习设设n为正整数，给出下列各种算法关于为正整数，给出下列各种算法关于n的时间复杂度的时间复杂度2.void fun2(int b ,int n)int i,j,k,x;for (i=0;in-1;i+)k=i;for(j=i+1;jbj)k=j;x=bi;bi=bk;bk=x;1.void fun1(int n)i=1,k=100;while (in)k=k+1;i+=2;1:38 AM