《第1周绪论第7讲-本周小结数据结构.pdf》由会员分享，可在线阅读，更多相关《第1周绪论第7讲-本周小结数据结构.pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1从数据结构角度求解问题的过程 问题 数据的逻辑数据的逻辑 结构结构 提取 数据运算数据运算 （运算描述）（运算描述） 抽象数据类型抽象数据类型 （ADT） 1/20 数据的逻辑数据的逻辑 结构结构 数据运算数据运算 （运算描述）（运算描述） ADT = + 映射映射 存储结构存储结构 算法算法 运算描运算描 述实现述实现 好算法好算法 算法分析算法分析 逻辑层面 实现层面 分析层面 设 计 好 存 储 结 设 计 好 存 储 结 构 使 算 法 更 优 构 使 算 法 更 优 2/20 描述一个集合的抽象数据类型描述一个集合的抽象数据类型ASet，其中所有元素为正整数，其中所有元素为正整数，
2、 集合的基本运算包括：集合的基本运算包括： （1）由整数数组a0.n-1创建一个集合。 （2）输出一个集合的所有元素。 （3）判断一个元素是否在一个集合中。 （4）求两个集合的并集。 （5）求两个集合的差集。 （6）求两个集合的交集。 在此基础上设计集合的在此基础上设计集合的顺序存储结构顺序存储结构，并，并实现各基本运算的算法实现各基本运算的算法。 3/20 解：解：抽象数据类型抽象数据类型ASet的描述如下：的描述如下： 4/20 设计集合的顺序存储结构类型如下：设计集合的顺序存储结构类型如下： typedef struct/集合结构体类型集合结构体类型 int dataMaxSize;/存
3、放集合中的元素，其中存放集合中的元素，其中MaxSize为常量为常量 int length;/存放集合中实际元素个数存放集合中实际元素个数 Set;/将集合结构体类型用一个新类型名将集合结构体类型用一个新类型名Set表示表示 5/20 静态分配方式 采用采用Set类型的变量存储一个集合。对应的基本运算算法设计如下：类型的变量存储一个集合。对应的基本运算算法设计如下： void createset(Set for (i=0;in;i+) s.datai=ai; s.length=n; void dispset(Set s)/输出一个集合输出一个集合 int i; for (i=0;is.leng
4、th;i+) printf(%d ，s.datai); printf(n); 6/20 bool inset(Set s，int e)/判断判断e是否在集合是否在集合s中中 int i; for (i=0;is.length;i+) if (s.datai=e) return true; return false; 7/20 void add(Set s1，Set s2，Set for (i=0;is1.length;i+)/将集合将集合s1的所有元素复制到的所有元素复制到s3中中 s3.datai=s1.datai; s3.length=s1.length; for (i=0;is2.len
5、gth;i+)/将将s2中不在中不在s1中出现的元素复制到中出现的元素复制到s3中中 if (!inset(s1，s2.datai) s3.datas3.length=s2.datai; s3.length+; 8/20 void sub(Set s1，Set s2，Set s3.length=0; for (i=0;is1.length;i+)/将将s1中不出现在中不出现在s2中的元素复制到中的元素复制到s3中中 if (!inset(s2，s1.datai) s3.datas3.length=s1.datai; s3.length+; 9/20 void intersection(Set
6、s1，Set s2，Set s3.length=0; for (i=0;is1.length;i+)/将将s1中出现在中出现在s2中的元素复制到中的元素复制到s3中中 if (inset(s2，s1.datai) s3.datas3.length=s1.datai; s3.length+; 10/20 Set数据数据 createset(Set int a=1，2，3，4，5; int b=2，3，4，5，6，7，8; int n=5，m=7; createset(s1，a，n); createset(s2，b，m); printf( s1:); dispset(s1); printf( s2
7、:); dispset(s2); printf( s3=s1 s2n); add(s1，s2，s3); printf( s3:); dispset(s3); printf( s4=s1-s2n); sub(s1，s2，s4); printf( s4:); dispset(s4); printf( s5=s1s2n); intersection(s1，s2，s5); printf( s5:); dispset(s5); 集合数据结构的应用集合数据结构的应用 12/20 2算法描述输出型参数 算法：算法：输入输入 输出输出 返回值返回值 函数名函数名( (输入参数输入参数， 输出参数输出参数) )
8、 /实现代码实现代码; ; 采用引用类型参数 13/20 设计一个算法求整数集合设计一个算法求整数集合s中偶数元素个数。中偶数元素个数。 算法算法集合集合s偶数元素个数偶数元素个数m void Evennumbers(Set s，int for (int i=0;is.length;i+) if (s.datai%2=0) m+; 14/20 3算法时间复杂度分析 非递归算法非递归算法 递归算法递归算法 算法类别：算法类别： 15/20 确定问题规模确定问题规模n 用复杂度表示用复杂度表示T(n) 找基本操作语句找基本操作语句 求基本操作的执行次数求基本操作的执行次数T(n) 16/20 确定
9、问题规模确定问题规模n 确定终止情况确定终止情况 确定递推情况确定递推情况 由递推式求出由递推式求出T(n) 用复杂度表示用复杂度表示T(n) 17/20 有如下递归算法，分析调用有如下递归算法，分析调用max(a，0，n- -1)的时间复杂度。的时间复杂度。 int max(int a，int i，int j) int mid=(i+j)/2，max1，max2; if (imax2)?max1:max2; else return ai; 18/20 int max(int a，int i，int j) int mid=(i+j)/2，max1，max2; if (imax2)?max1:m
10、ax2; else return ai; 设设调用调用max(a，0，n- -1)的执的执 行时间为行时间为T(n) 递归算法递归算法max(a，i，j)的执行的执行 时间为时间为T1(n)（n=j- -i+1） 有有T(n)=T1(n) T(n)=O(1)当当n=1（i=j的情况）的情况） T(n)=2T(n/2)+1当当n1（i1 T(n) = 2T(n/2) + 1 = 22T(n/22) + 1 + 1 = 22T(n/22) + 2 + 1 = = 2kT(n/2k) + 2k-1 + + 2 + 1（k=log2n） = 2k + 2k-1 + + 2 + 1 = 2*2k - - 1 = O(n) 20/20 调用调用max(a，0，n- -1)的时的时 间复杂度为间复杂度为O(n)