练习题（一）

一、编程题。根据程序要求，写出函数的完整定义。

1．写一个函数，找出给定字符串中大写字母字符（即’A’-‘Z’这26个字母）的个数（如字符串”China Computer Wrold”中大写字母字符的个数为3个）。

函数的原型：          int CalcCapital (char *str);

函数参数：  str为所要处理的字符串；

函数返回值：所给字符串中数字字符的个数

2．写一个函数，用递归函数完成以下运算:

sum(n) =  1 – 1/2 + 1/3 – 1/4 + … -(1/n)*(-1)ⁿ        （其中n>0）

函数原型：         float sum(int n);

函数参数：n为正整数。

函数返回值：相应于给定的n，右边表达式运算结果。

提示：你可以使用递归表达式： sum(n) = sum(n-1) -(1/n)*(-1)ⁿ

3. 给定新数值，在一个按节点所存放数值从大到小排序的链表中，找适当位置插一个新节点，仍保持有序的链表，写一个函数，完成此操作。

函数的原型：   Node * InsNode(Node * head,  int newValue);

其中，链表节点的定义如下：

struct Nodee{

    int Value;     //存放数值

    Node * next;     //指向链表中的下一个节点

};

函数参数：函数的第一个参数head指向链表头一节点的指针，如果链表为空，则head的值为NULL。第二个参数newValue为所给定的插入新节点的新数值。

函数返回值：当成功地插入新的节点时，函数返回指向新链表头一节点的指针，否则，若不能申请到内存空间，则返回NULL。

4．写一个函数，找出给定数组中具有最小值的元素。

函数的原型：

 char MinCode(char charAry[]);

函数参数：charAry所要处理的字符数组名；

函数返回值：返回具有最小ASCII码的字符。

二、理解问答题：

下面的文件stack.h是一个堆栈类模板Stack的完整实现。在这个文件中，首先定义了一个堆栈元素类模板StackItem，然后，在这个类的基础上定义了堆栈类模板Stack。在Stack中使用链表存放堆栈的各个元素，top指针指向链表的第一个节点元素，bottom指针指向链表的最后一个节点元素，成员函数push()将一个新节点元素加入（压进）到堆栈顶部，pop()从堆栈顶部删除（弹出）一个节点元素。为方便起见，程序中加上了行号。阅读程序，根据程序后面的问题作出相应解答。

1.         /*---------------------------------------------------------- -------------------*/

2.         /********************* 文件stack.h ************************/

3.         /*---------------------------------------------------------- -------------------*/

4.         template <class Type>

5.         class Stack;

6.         /***************** 定义模板类StackItem ******************/

7.         template<class Type>

8.         class StackItem

9.         {

10.       public:

11.         StackItem(const Type & elem):item(elem) {}

12.         ~StackItem() {}

13.       private:

14.         Type item;

15.         StackItem * nextItem;

16.       friend  class Stack<Type>;

17.     };

18.     /***************** 定义模板类Stack *********************/

19.     template <class Type>

20.     class Stack

21.     {

22.       public:

23.         Stack():top( NULL), ____(A)_____ {}

24.         ~Stack();

25.         Type pop();

26.         void push(const Type &);

27.         bool is_empty() const { return ____(B) ______ ; }

28.       private:

29.         StackItem<Type> * top;

30.         StackItem<Type> * bottom;

31.     };

32.     //模板类Stack的函数成员pop()的实现。

33.     //从堆栈顶弹出一个节点，并返回该节点的值

34.     template<class Type>

35.     Type Stack<Type>::pop()

36.     {

37.       StackItem<Type> *ptop;      //指向顶部节点的临时指针

38.       Type retVal;                        //返回值

39.       ______(C) ________;

40.       retVal = top->item;

41.       top = top->nextItem;

42.       delete ptop;

43.       return retVal;

44.     }

45.     //模板类Stack的函数成员push()的实现

46.     template<class Type>

47.     void Stack<Type>::push(const Type & newItem)

48.     {

49.       StackItem<Type> *pNew = new StackItem<Type>( newItem);

50.         ______(D)___________;

51.       if (bottom == NULL)  bottom = top = pNew;

52.       else   _____(E)_________;

53.     }

54.     //模板类Stack的析构函数~Stack()的实现

55.     template<class Type>

56.     Stack<Type>::~Stack()

57.     {

58.       StackItem<Type> *p = top, *q;

59.       while(p != NULL) {

60.         q = p->nextItem;

61.         delete p;

62.         p = q;

63.       }

64.     }

问题1： 程序中有几处填空，将它们完成。

（A）_________________________________________________

（B）_________________________________________________

（C）_________________________________________________

（D）_________________________________________________

（E）_________________________________________________

问题2：程序第4，5行有什么作用？如果没有这两行语句，程序还正确吗？

问题3：程序中多处出现const，请分别说明它们各自表示什么含义。

问题4：程序中模板类Stack的析构函数主要做了什么事情？为什么要这么做？

问题5：下面的程序使用了stack.h文件中定义的类模板，请说明下列程序中定义堆栈对象的语句(1-5)是否正确。

       #include “stack.h”

       void main()

       {

               Stack  q1;                                                          //       1

              Stack<float> q2;                                                //         2

              Stack<float> q3(10);                                          //         3

              Stack<float> q4[10];                                          //         4

              Stack<float> *q5 = new Stack<int>;            //       5

               //....

               delete q5;

       }

答：