数据结构（c语言描述）

《数据结构（c语言描述）》由会员分享，可在线阅读，更多相关《数据结构（c语言描述）（25页珍藏版）》请在金锄头文库上搜索。

1、2:05 AM,数据结构（C语言描述）,计算机系 刘延芳,2:05 AM,第一章 绪 论,1.1 引 言 1.2 数据结构发展简史及学科地位 1.3 什么是数据结构 1.4 基本概念和术语 1.5 算法概念、算法的描述和 算法评价练习,2:05 AM,引 言,20世纪40年代(1946),为了解决弹道轨迹计算问题而产生计算机。早期，计算机应用范围局限于科学和工程计算,处理对象是纯数值性信息,人们称这类问题为“数值计算”。 如今,计算机应用远远超出数值计算范围,渗透人类生活的一切领域。计算机处理对象也从纯数值发展到非数值性和具有一定结构的信息。 现代计算机科学的观点，把计算机程序处理的一切数值的

2、、非数值信息、乃至程序统称数据（Data），而计算机只是处理数据的工具。 处理对象的转变导致系统和应用程序的规模越来越大，结构也相当复杂，单凭程序员经验和技巧已难以设计效率高、可靠性强的程序。 数据的表示方法和组织形式成为处理数据效率的关键。即研究数据的特性以及数据间存在的关系数据结构（Data Structure）,本章介绍了数据结构这门学科诞生的背景,发展历史以及在计算机 科学中所处的地位,重点介绍了数据结构有关的概念和术语,读者学 习本章后应能掌握数据,数据元素,逻辑结构,存储结构,数据处理,数 据结构,算法设计等基本概念,并了解如何评价一个算法的好坏。,2:05 AM,发展简史及学科地

3、位,数据结构随着计算机产生和发展而发展起来的一门较新学科。 1968年开始设立这门课，由美国教授开创数据结构的最初体系。观点是：认为程序设计的实质是对确定的问题选择一种好的结构，加上一种好的算法。 研究内容：软件设计中常用的基本技术 地位：核心课程之一，也是非计算机专业的主修课程之一 数据结构是介于数学、计算机硬件和软件之间的学科。,2:05 AM,什么是数据结构,用计算机解决一个具体问题的步骤： 1.从具体问题中抽象出一个适当的数学模型 2.设计一个解此数学模型的算法 3.编出程序、进行测试、调整直至得到最终解答 例如：在(有规律)学生通讯录中，1.按照索引查找某一学生 2.插入和删除一个学

4、生记录？ 数据结构直接影响算法的选择和效率。 数据结构：研究程序设计中计算机操作对象及其关系和运算的一门学科,2:05 AM,基本术语(1),1.数据:一切能够输入到计算机中并被其处理的信息(文字,表格图像等)。 2.数据元素:也称结点,记录,顶点。是组成数据的基本单位。通常作为一个整体考虑和处理。如图：每一行作为基本单位考虑。 3.字段:一个结点中含有若干个字段(也叫数据项).是构成数据的最小单位。 4.逻辑结构：结点与结点间的逻辑关系。如图:逻辑上是种线性关系。 5.存储结构：数据在计算机中的存储表示。如图：表格数据可有多种存储表示(如：数组、文件等) 6.数据结构：组成数据元素之间构造关

5、系。,2:05 AM,数据逻辑结构,1.逻辑结构的四种基本结构： (1)集合：结构中的数据元素除了同属于一种类 型外，别无其它关系。 (2)线性结构 ：结构中的数据元素间存在一对一的关系。 (3)树形结构 ：结构中的数据元素间存在一对多的关系。 (4)图形或网状结构：结构中的数据元素之间存在多对多的关系。 2.数据的逻辑结构分为线性结构和非线性结构两大类。 (1)线性结构:包括数组、链表、 栈、队列、优先级队列等; (2)非线性结构:包括树、图等.,2:05 AM,存 储 结 构,常见存储结构： (1)顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构. 即逻辑上相邻

6、,物理上也相邻. (2)链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。 (3)索引存储结构: (4)散列存储结构:,2:05 AM,基本术语(2),一般：把数据的逻辑结构统称为数据结构，把数据的物理结构统称为存储结构。 说明：一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。我们的重点是算法的设计。,数据 数据元素 字段,数据结构,分解,描述,逻辑结构:结点与结点间的逻辑关系。不依赖于具体形式 存储结构：数据在计算机中的存储表示。 运算：是最终目的,2:05 AM,基本术语(3),7.数据处理：对数据进行查找、插入、删除、合并、排序统计

7、及简单计算等操作过程。 8.数据类型：指程序设计语言中各变量可取的数据种类。 即是一个值的集合和定义在此值集上的一组操作总称按“数据类型”性质分类： (1)原子类型：其值是不可分解的.(整,实,字,枚,指,空类型) (2)结构类型：其值按某种结构组成(由若干成分)，如：数组,例如：C语言中，整型变量 其值集：在某个区间上整数操作：加,减,乘,除,求模等运算,2:05 AM,算法的概念,1.算法解决某一类问题的求解方法执行特定计算的有穷过程（即指令的有限序列） 2.算法的特点： (1)动态有穷:即有限性;经过有限步骤后，算法一定要终止。 (2)确定性:指令无二义性.在任何条件下,算法只有一条惟一

8、的执行路径。 (3)输入：有0N个 (4)输出：有1N个 (5)可行性:每条指令都充分基本,即每条指令均可用有限次的计算机指令来实现。 3.算法与程序比较 (1)程序是算法在计算机程序设计语言中的具体实现。通常定义一个算法必须提供足够细节,才能转化为程序。(多个程序表示同一算法) (2)算法的有穷性意味着不是所有程序都是算法.例如;操作系统是一个程序不是算法,但把操作系统各种任务看成单独问题,每个问题是由特定算法实现,得到输出结果便终止。 (3)算法和程序是相互独立的。,2:05 AM,算法的描述,1.自然语言 2. 伪代码和流程图 3.计算机高级程序语言（例如C语言） 4.C语言语法结构,2

9、:05 AM,自然语言,例：设计算法：求一元二次方程ax2+bx+c=0的根。,计算d=b*b-4*a*c 如果d0，计算x1=(-b+sqrt(d) /(2*a) x2=(-b-sqrt(d) /(2*a) 如果d=0，计算x=(-b) /(2*a) 如果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( ) fl

10、oat a, b, c;printf(“请输入a,b,c：”); scanf(“%f,%f,%f”,计算机语言,2:05 AM,C语言语法结构(1),输入语句 scanf(“格式字符串” ，输出项表)； 输出语句 printf(“格式字符串” ，输出项表)； 赋值语句 变量名 = 表达式；条件语句 if ；或者if else ;,2:05 AM,C语言语法结构(2),5. 循环语句 while ；do；while ；for （； ;） ; 定义函数语句（，） ； ,7. 调用函数语句（ ，） 8. 返回语句 return(),2:05 AM,算法的评价,1.算法评价目的:选择合适算法或对已有的

11、算法进行改进。 2.通常设计一个好的算法应考虑： (1)正确性首要条件 (2)运行时间:算法的时间复杂度(即:执行一个简单操作所需时间与操作次数的乘积)。 (3)占用存储空间:算法的空间复杂度(含存储算法本身,算法输入输出数据和算法运行过程中临时占用空间)。 (4)简单性:算法易于理解,易于编码及调试。 3.算法的时间复杂度和空间复杂度S(n)=O(f(n)一般用数量级来表示。 4.举例,2:05 AM,时间复杂度(Time Complexity)（1）,算法在计算机中运行时间受很多因素(与计算机系统的软硬件环境有关)的影响。通常利用语句频度和渐进时间复杂度衡量时间复杂度。 1.语句频度指该语

12、句被执行的次数。 (1)任何算法都可分解为简单操作(如赋值、比较、移位等)来执行. (2)假设执行每条语句所需时间为单位时间,则算法运行时间转化为所有语句执行次数,即语句频度之和（频度统计法）。 2.一般情况下,语句频度是问题规模n的函数,用T(n)表示,若有某个辅助函数f(n)使：则称f(n)与 T(n)同阶,记作: T(n)=O(f(n) O(f(n)表示时间复杂度(或称渐进时间复杂度), f(n)是最大语频 3. 例题 求n！算法时间复杂度,2:05 AM,时间复杂度(Time Complexity)（2）,4.算法分析的几个方法： (1)执行一些简单的输入,输出或赋值语句时,可近似认为

13、需要O(1)时间. (2)对于顺序结构,需要依次执行一系列语句所需时间可采用累加求和的方式进行估计 (3)对于选择结构,如if语句。它的时间主要消耗在执行then子句或else子句时所用的时间，但if语句判断条件本身也消耗O(1)的时间 (4)对于循环语句,它的时间主要耗费在执行循环体以及循环条件的检验上,可采用乘法计算出算法的语频,从而得到算法时间复杂度。 (5)对于较为复杂算法,采用先分解为几个容易估计的部分,然后利用求和方法计算出整个算法的时间复杂度。 5. 求两个n*n矩阵相乘算法 6.时间复杂度综合考虑,2:05 AM,时间复杂度综合考虑,1.由于算法时间复杂度考虑的只是问题规模n的

14、增长率,在难以精确计算语句频度的情况下,只需求出关于n的增长率或阶数即可。 2.有时算法时间复杂度与算法处理的输入数据集有关,算法的时间复杂度难以确定。这时一般采用算法在最坏的情况下复杂度作为时间复杂度。 例如：在排序算法中,要求从小到大排序. 若给定输入集为从大到小最坏情况,时间复杂度为T(n)=O(n2) 若不作特别说明,以后各章均为最坏情况时间复杂度。 3.在分析时间复杂度是,随着问题规模n的增大，各种时间复杂度存在下列大小关系：,数量级的大小顺序： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3) O(2n)(n!),2:05 AM,例题 求n！算法时间复杂度,例

15、题：求n！算法时间复杂度 Void fact ( int n) int i, total ;total = 1; /*1次*/ for ( i = 1; i = n; i +) /*n次*/total = total * i; /*n次*/printf (“%d”, total ) ; /*1次*/ 算法语频之和为T(n)=2n+2,取f(n)=n，则因此,其同阶表示形式为T(n)=O(n)，即算法时间复杂度O(n),2:05 AM,求两个n*n矩阵相乘算法,例题：求两个n*n矩阵相乘算法 for ( 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 /*算法的主要部分*/ 算法主要部分在第三层循环中,乘法运算是矩阵相乘算法的基本操作,共执行n3。因此,整个算法的执行时间与该基本操作重复次数n3成正比，其时间复杂度为O(n3),