数据结构基本概念..docx
数据结构的分类及袅示算法及算法分析例求10个正整数中最大数的算法。述算法的方法有根多：1流程图，4然语言，计算机语言开始为io个元素M3到M9摘入数值流程图描述max=a0自然语言描述攵机语言描述(1)给10个元素a0a9输入数值；卜2)把第一个元素a 0赋给用于保存最大值元素的I 变量max;| (3)把表示下标的变量i赋初值1;| (4)如果iv=10,则向下执行，否则输出最大值max后 结束算法；(5)如果a0>max,则将ai赋给max,否则不改变 max的值,这使得max始终保存着当前比较过I的所有元素的最大值；| (6)使下标i增1，以指示下一个元素；I (7)转向第(4)步继续执行.main()(int i,max,a10;printf(“请输入10个整数巧；for(i=0;i<=10;i+) scanf(u%dn,&ai);max=a0;i=1；while(i<10) if(ai>max) max=ai;i+；printf(“10个整数中的最大值为:",max);二算法的基本特征:I）输入：0个或多个输入；2）输出：1个或多个输出；音I、露谶£.算法必须在有限步内结束，且每一步都是在有限 4）确定性：在任何条件下，相同的输入只能得到相同的输出 5）可行性：组成算法的操作必须能够在计算机上实现。三评价算法好坏的标举同一个问题可以构造不同的算法，最终选择哪一个 算法？这涉及如何评价一个算法好坏的问题。正确性可读性健壮性：当输入非法数据时，算法应做出适当反映或处理。执行算法所耗费的时间（时间复杂度）I执行算法所耗费的存储空间（空间复杂度）算法效率1 时间复杂度一个算法执行所耗费的时间，从理论上是不能算出来的, 必须上机运行测试才能知道。但我们不可能也没有必要对每 个算法都上机测试，这是由于本身算法的实现也要耗费时间 和精力的。因此，我们只需知道哪个算法花费的时间多，哪 个算法花费的时间少就可以了。(1时间频度一个算法花费的时间与算法中语句的执行次数成正比例，哪个算 法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为时间频 度。记为T(n。n称为问题的规模。例：求下列算法的时间频度for(i=l;iv=n;i+ for(j =1; j <=i; j+分析：时间频度 T(n=l+2+3+n n ( n 1 = 2 x=x+l;(2时间复杂度设T(n的一个辅助函数为g(n,定义为当n大于等于某一足够大 的正整数nO时，存在两个正的常数A和B (其中ASB)，使得AST(n/g(ngB均成 立，则称g(n是T(n的同数量级函数。把T(n表示成数量级的形式为：T(n=O(g(n 其中。为Order (即数量级)的首字母。例如：若T(n=n(n+l/2,则有 l/4<T(n/n2<l,故它的时间复杂度为O(n2,即T (n与n2数量级相同。按数量级递增排列，常见的时间复杂度有：在各种不同算法中，若算法中语 句执行次数为一个常数，则时间复杂度为0(12空间复杂度(1空间频度一个算法在执行时所占有的内存开销，称为空间频 度.( 2空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所 占用的内存开销规模。2.1敦据结构的有关概念1戴林;宋况对象的符号友示。在计算机科学中，救搪的含义非有广泛，我们也一切能够输入到计算机中并极计算机程序处理的信息，包括丈李 上表格，图象等，都称为教搪。如：一个个人书库管理程序所要处理的数据是一张表格。OOOOO2TP1844 Autnorxvare 5 1 速成 0000031684 Lots Noles网摺办公平台 0Q0004pP2143lAcceSS 200QArTM« 000。05bpi 11O PowerBuilder6 软用教程1 一 一 « 一 一 一 一 一 J» 一 0000061397 Delphi数据库编程技术 000007|TP2711 83MS SCLSaiver 7 0000008：7P3239 Visjal。每用载程 ” (，一 一 a *<« * »«*« MOB-000009i-P1787电子商务万事逋 - *aV 一 I000010；：*P42致据给询孙易2 I f 6更堪澳金主3 * *9 9 j刘前出*« *:罗合潼 * * *翎* . * * *回海频看猾蜡蹄TL取燮 民季军技总孑手QL 一央一 人番洁科一电一电人干一 T I .- 一, f - i 1««|4 一 » <<*4 ;*M*a*4< c - c « c c - c c - c c - c - o-o»o 0-0 0-0-0 00- -I ， 2 9-3 5-3 5-3.- 4-12 27 3-3 2-1-«»个人量录号I书号J书名f诸出就杜|价格|»000001TP2233Windows MT4.0中文联程泓健空电学i业叔弟无未卜数据的基本单位O在计算机桓序中通帝作为一个整体考虑和处理。在如前所示的个人书库中，为了便于处理，把其中的每一行 （代表一本书）作为一个基本单位来考虑，故该数据由10个数据元素构成。TP223?数据元素之间的逻辑关系分为：元素之间没有关系一集合元素之间具有线性关系一线性数据结构（线性表结构）（3）元素之间具有层次关系一层次数据结构（树结构）（4）元素之间具有网状关系一网状数据结构（图结构）例1:某班学生基本情况登记表，记录了每个学生的学号、姓 名、专业、政治面貌，表中的记录是按学生的学号顺序排 列的.学号关系是一种线性结构关系藐面治员员员员员员员员政党团团团党团团团机机机机机机忙机 业算第算算算噂算算 专让计计计日计计计福 辉 名洪文军辉祥斌力令 姓王孙谢李沈余巩孔梵002003004005006007008学生基本情况登记表的图示例2家族的族谱例2家族的族谱家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员A,B, C, D, E, F, G, H, I,J,他们之间的血缘关系可以用如下图表示。家族树的图示表示OO 0 Oo G e 060这种分支的结构关系被称为树结构。它很象一棵倒置 的树，A是树的根。品南科技八号土木学院文艺学院制造学院教师 学生其他人员99级2000 级 2001 级 2002 级子树叶子致弊的存储每拘卜建科结构在计算机存胫看中的映像，必须依赖于计算机。四种基本的存储方柒：（1）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）（3） ,素引存储方法f4）数列存储方法同一种述辑结构可集用不同的存错方法（以上四种之一 或姐合），这主要考虑的是运算方便及算头的时空要求。Iki §2.2数据结构的表示9表示图示表示是由顶点和边构成的图，其中顶点表 示数据，边表示数据之间的结构关系;学生基本情况表的图示表示家族树的图示表示元姐表示用号二元组（D； S）表示数据结构，其中D 是数据元素集合，S是D上关系的集合。学生基本情况表的二元组表示（D, S）D = 001, 002, 003, 004, 005, 006, 007, 008S = <001, 002>, <002, 003>, <003,004>, <004, 005>, <005, 006>,<006, 007>, <007, 008> 家族树的二元组表示（D, S）D = A, B, C, D, E, F, G, H, I, JS = （A, B>, <B, C>, <C, D>, <D, E>, <E, F>, <F, G>t <G, H>, <H, I>, <1, J> §2.3算法与算法分析国1一什么是算法？算法是对特定问题求斛步腺的一种拈述.
