自考数据结构串讲笔记自考乐园版课程代号：02331课程说明串讲目的参考教材：《数据结构》黄刘生主编经济科学出版社更多优质自考资料尽在百度贴吧自考乐园俱乐部（http://tieba.baidu.com/club/5346389）欢迎加入❤...欢迎交流❤...止不住的惊喜等着你.........课程说明知识点：线形表、栈、队列、数组、广义表、树、图、查找和排序。第一章绪论§１．基本概念与术语数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。（一）数据结构概念包括三个方面（三要素）数据之间的逻辑关系（逻辑结构）数据在计算机中的存储方式（存储结构）实现数据操作的算法（数据的运算）（二）、相关术语1、数据：能输入计算机并能计算机程序处理的符号的总称。2、数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。3、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。4、（1）数据的逻辑结构：数据之间的关系。A.集合（无顺序）：B.线性结构（一对一）：C.树形结构（一对多）：D.网状、图结构（多对多）：（２）数据的存储结构（物理结构）数据结构在计算机中的表示。（２种）A.顺序表示借助数据在连续的存储空间中的相对位置表示元素关系。B.链式表示借助数据元素的存储地址的指针表示元素关系。§2.算法和算法分析一、算法定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：有穷性确定性可行性零个或多个输入一个或多个输出大O表示法大O表示同级别例：f(n)=n2,f(n)=1/2(n(n-1)),f(n)=(n-1)(n+2)均表示为：O(n2)加法规则：若T1(n)=O(f1(n)),T2(n)=O(f2(n))则两段程序连在一起的时间代价为:T(n)=T1(n)+T2(n)=O(max(f1(n),f2(n))例:语句段频度f(n)时间复杂度T(n)x=x+11O(1)for(j=1;j<=3n+5;j++)3n+5O(n)x=x+1;for(i=1;i<=3n;i++)3n2O(n2)for(j=1;j<=n;j++)x=x+1;i=0;n+1O(n)while(x!=a[i]&&i<=n)i=i+1;求时间复杂度的原则当重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http://tieba.baidu.com/club/5346389）欢迎加入❤...欢迎交流❤...止不住的惊喜等着你.........算法时间开销随时间规模变化趋势nT(n)随n增大,T(n)增加快,算法坏随问题规模n增大,T(n)趋缓,算法好T(n)的增大趋势:O(1)
