[资料]第一章数据结构与算法(公共基础).pptVIP

1第一章

数据结构和算法

算法算法的基本概念算法复杂度数据结构的基本概念数据结构及图形表示线性结构与非线性结构线性表及其顺序存储结构线性表的基本概念顺序表的插入运算及删除运算线性表的顺序存储结构栈和队列栈及其基本运算队列及其基本运算线性链表线性链表的基本概念循环链表及其基本运算线性链表的基本运算树与二叉树树的基本概念二叉树的存储结构及遍历二叉树及其基本性质查找技术顺序查找二分查找法交换类排序选择类排序插入类排序排序技术彻疏容那氏厉粮琢铝遵俩勃沥疑车驯蚤散沉渐唤测驴媳苑粘朱锡氛阶熄忌第一章数据结构与算法(公共根底)第一章数据结构与算法(公共根底)

2计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。算法〔algorithm〕是一组严谨地定义运算顺序的规那么，并且每一个规那么都是有效的，且是明确的，此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法是指解题方案的准确而完整的描述。一般具有以下几个根本特征：〔1〕可行性〔effectiveness〕：针对实际问题而设计的算法，执行后能够得到满意的结果。〔2〕确定性〔definiteness〕：算法的每一步骤都必须具有明确定义的解释，不允许有多义性。〔3〕有穷性〔finiteness〕：算法必须在有限时间内做完，即算法必须能在执行有限个步骤之后终止。算法的有穷性还应包括合理的执行时间的含义。〔4〕拥有足够的情报：要使算法有效必须为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的，而当提供情报不够时，算法可能无效。综上所述，算法是一组严谨地定义运算顺序的规那么，并且每一个规那么都是有效的，且是明确的，此顺序将在有限的次数下终止。算法啥斑赛画苞拳泵色灌硼惠釜拜醒拌撼棕倍画气朱发盾诸源浆仆怠镑庶堕锤第一章数据结构与算法(公共根底)第一章数据结构与算法(公共根底)

3所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的根本运算次数来度量，而算法所执行的根本运算次数是问题规模的函数，即算法的工作量=f(n)其中n是问题的规模。在同一个问题规模下，如果算法执行所需的根本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量:①平均性态〔AverageBehavior〕所谓平均性态是指各种特定输入下的根本运算次数的加权平均值来度量算法的工作量。设x是所有可能输入中的某个特定输入，p(x)是x出现的概率〔即输入为x的概率〕，t(x)是算法在输入为x时所执行的根本运算次数，那么算法的平均性态定义为A(n)=其中Dn表示当规模为n时，算法执行的所有可能输入的集合。②最坏情况复杂情况〔Worst－CaseComplexity〕所谓最坏情况分析，是指在规模为n时，算法所执行的根本运算的最大次数。它定义为W(n)=max{t(x)}x∈Dn。算法的时间复杂度松登既歇促游链漳塔褥拉裳盲改伦喜所兼谜南糠苞青旗坠化毒颜宪栈干捎第一章数据结构与算法(公共根底)第一章数据结构与算法(公共根底)

4算法的时间复杂度举例例两个nn的矩阵相乘。其中矩阵的“阶〞n为问题的规模。

???算法1.1

voidMult_matrix(intc[][],inta[][],intb[][]，intn)

{

//a、b和c均为n阶方阵，且c是a和b的乘积

for(i=1;i=n;++i)

for(j=1;j=n;++j){

c[i,j]=0;

for(k=1;k=n;++k)

c[i,j]+=a[i,k]*b[k,j];

}

}//Mult_matrix

容易看出，算法中的控制结构是三重循环，每一重循环的次数是n。原操作有赋值，加法和乘法，显然，在三重循环之内的“乘法〞是根本操作，它的重复执行次数是n3。所以时间复杂度为O(n3)秀涎硬迎毛辣滇侦们砍卉澳磋竹鹊畸韧刁鹰造堪师赞廓态须鄙共饲垃工暮第一章数据结构与算法(公共根底)第一章数据结构与算法(公共根底)

5算法的时间复杂度举例例对n个整数的序列进行选择排序。其中序列的“长度〞n为问题的规模。

算法1.2

voidselect_sort(inta[],intn)

{

//将a中整数序列重新排列成自小至大有序的整数序列。

for(i=0;in-1;++i){

j=i;

for(k=i+1;kn;++k)

if(a[k]