编译技术DS02实现基础.pptVIP

第2章 实现基础 ;? 如何利用程序设计语言实现上述抽象类型？;第2章 实现基础 ;第2章 实现基础 ;指针;第2章 实现基础 ;注意事项： A、申请了内存空间后，必须检查是否分配成功。 B、当不需要再使用申请的内存时，记得释放；释放后应该把原本指向这块内存的指针变量 指向NULL，防止程序后面不小心使用了该指针。（释放的是内存，不是指针变量） C、这两个函数应该是配对使用。如果申请后不释放就是内存泄露；如果无故释放（还未使用就释放）那就是什么也没有做。释放只能一次，如果释放两次及两次以上会出现错误（释放空指针例外，释放空指针其实也等于啥也没做，所以释放空指针释放多少次都没有问题）。 D、虽然malloc()函数的类型是(void *),任何类型的指针都可以转换成(void *),但是最好还是在前面进行强制类型转换，因为这样可以躲过一些编译器的检查。;（4） 用指针实现动态顺序存储结构 int * p; p=(int *) malloc(10*sizeof(int)); if(p==NULL) return; int p[10]; ; 结构;第2章 实现基础 ;共用体 【定义】共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。;枚举类型的声明形式如下： enum 枚举类型名 {变量值列表};;枚举类型应用说明： 对枚举元素按常量处理，不能对它们赋值。 如，不能写：sun=0; 枚举元素具有缺省值，它们依次为： 0,1,2,......。 也可以在声明时另行指定枚举元素的值，如： enum weekday {sun=7,mon=1,tue,wed,thu,fri,sat}; 枚举值可以进行关系运算。 如： weekday today； if(today==tue) ; 整数值不能直接赋给枚举变量，如需要将整数赋值给枚举变量，应进行强制类型转换。 如：today=(weekday)3;;链表;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); }