数据结构适用教程ch01课件.ppt

1、下面给出三个简单的例子加以说明下面给出三个简单的例子加以说明学生基本情况表学生基本情况表 表示某高校的专业设置情况表示某高校的专业设置情况 描述若干个城镇之间的公路网描述若干个城镇之间的公路网 机械制造机械工程系机电一体化计算机网络计算机应用 计算机科学系技术学院电子工程系电子应用电气自动化4235ABE DC4045705520例例1.1 1.1 已知集合已知集合A和和B，现要求一个新的集合，现要求一个新的集合A=A-B。分析：假设用线性表分析：假设用线性表LA和和LB分别表示集合分别表示集合A和和B ，只要将同在只要将同在LA和和LB中的元素从中的元素从LA中删除即可。中删除即可。算法描述

2、如下：算法描述如下：viod Difference(Linear_List LA,Linear_List LB)n=Length(LB);for(i=1;i=n;i+)x=GetElem(LB,i);k=Locate(LA,x);if(k!=0)Delete(LA,k);/*x在在LA和和LB中中*/*Difference*/算法描述：算法描述：算法算法 1.1 void sort(ElemType SMAXSIZE，int n)*对数组对数组S中的中的n个数据按由大到小的顺序排序并输出个数据按由大到小的顺序排序并输出,nMAXSIZE*/for(i=1;in;i+)for(j=i；j=n；j

3、+)if(SiscoreSjscore)t=Si；Si=Sj；Sj=t；for(i=1；i=n；i+)printf(“%8d%8d%8dn”，i，Si.no，Siscore);/*sort*/算法的性能标准算法的性能标准表示法表示法 )，(1)(log2n)(n)nlog2n)(n2)(n3)(2n)(3n)(n!)T(n)30002000100005101520200log2n100n5n2n/22nABvoid sort(ElemType SMAXSIZE，int n)*对数组对数组S中的中的n个数据按由大到小的顺序排序并输个数据按由大到小的顺序排序并输出出,nMAXSIZE*/for(i=1;in;i+)for(j=i；j=n；j+)if(SiscoreSjscore)t=Si；Si=Sj；Sj=t；for(i=1；i=n；i+)printf(“%8d%8d%8dn”,i,Si.no,Si.score);/*sort*/)T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)又有又有T(n)=O(max(n2,n)=O(n2)T(n)=O(f(n)*g(n)=O(n2)空间复杂度度量空间复杂度度量