DS02_实现基础_陈越主编_数据结构探析.ppt

第2章 实现基础 ;? 如何利用程序设计语言实现上述抽象类型？;[方法2] 基于问题分解;[例2.2] 求集合{ 6 5 9 8 2 1 7 3 4 } 的中位数。;第2章 实现基础 ;指针; 结构;共用体 【定义】共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。;链表;head;（3） 单向链表的遍历 ;双向链表;? 双向链表的插入、删除和遍历基本思路与单向链表相同，但需要同时考虑前后两个指针。;[例2.4] 给定一个单链表L，请设计函数Reverse将链表L就地逆转，即不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素……;类型定义typedef;第2章 实现基础 ;[例2.5] 求100到200之间的所有素数。;函数与递归;? 在设计函数时，注意掌握以下原则：;? 递归函数;[例2.8] 设计函数求n!;[例2.9] 汉诺塔（Tower of Hanoi）问题;;[例2.10] 用递归方法求集合的中位数。;ElementType FindKthLargest( ElementType S[ ], int K， int left, int right, ElementType t[ ]) { /* 在S[left]..S[right]中找第K大整数，t是临时数组 */ int i, Large = left, Small = right; /* Large和Small分别指向S1和S2在临时数组中的下一个存放位置 */ ElementType e; /* 分解集合的基准e */ e = S[left]; /* 将第一个元素作为基准 */ for ( i = left; i = right; i++ ) if ( S[i] = e ) /*将比e大的元素放临时数组t左边，小的元素放右边 */ t[Large++] = S[i]; else t[Small--] = S[i]; for ( i = left; i = right; i++ ) /*将临时数组中的元素拷贝回原数组 */ S[i]=t[i]; if ( K Large-left ) /* Large-left代表了集合S1的大小 */ /*在集合S1中继续找 */ return FindKthLargest( S, K, left, Large-1, t ); if ( k == Large-left) /* 找到，返回 */ return e; else /*在集合S2中找 */ return FindKthLargest( S, K-Large+left, Large, right, t); }