C++ 程序设计 OJ4 - 参考答案 MASTER 2017 年 5 月 21 日 1

Transcription

1 C++ 程序设计 OJ4 - 参考答案 MASTER 2017 年 5 月 21 日 1

2 1 SWAP 1 Swap 题目描述 用函数模板的方式实现对不同数据类型的数组中的数据进行输入 从小到大排序和输出 使用如下主函数测试你的模板设计一个函数模板 Swap, 实现任意数据类型的两个数据的交换, 分别用 int 型 double 型和 char 型的数据进行测试 main 函数如下 : int main() int a1, a2; cin >> a1 >> a2; Swap(a1, a2); cout << a1 << "," << a2 << endl; double b1, b2; cin >> b1 >> b2; Swap(b1, b2); cout << b1 << "," << b2 << endl; char c1, c2; cin >> c1 >> c2; Swap(c1, c2); cout << c1 << "," << c2 << endl; return 0; 输入 输入有三行, 第一行两个整数, 第二行两个浮点数, 第三行两个字符 输出 输出三组输入交换之后的结果, 每组用逗号隔开 样例输入 a b 样例输出 3,2 2.3,1.2 b,a 2

3 1 SWAP 1 #include <iostream> 2 using namespace std ; template <c l a s s T> 6 void Swap(T &a, T &b) 7 8 T temp = a ; 9 a = b ; 10 b = temp ; i n t main ( ) i n t a1, a2 ; 17 cin >> a1 >> a2 ; 18 Swap( a1, a2 ) ; 19 cout << a1 << "," << a2 << endl ; double b1, b2 ; 22 cin >> b1 >> b2 ; 23 Swap( b1, b2 ) ; 24 cout << b1 << "," << b2 << endl ; char c1, c2 ; 27 cin >> c1 >> c2 ; 28 Swap( c1, c2 ) ; 29 cout << c1 << "," << c2 << endl ; return 0 ; 32 3

4 2 函数模板 2 函数模板 题目描述 用函数模板的方式实现对不同数据类型的数组中的数据进行输入 从小到大排序和输出 使用如下主函数测试你的模板 int main() const int LEN = 5; int type; while (cin >> type) switch (type) case 0: int a1[len]; Input(a1, LEN); Sort(a1, LEN); Output(a1, LEN); break; case 1: char a2[len]; Input(a2, LEN); Sort(a2, LEN); Output(a2, LEN); break; case 2: double a3[len]; Input(a3, LEN); Sort(a3, LEN); Output(a3, LEN); break; return 0; 输入 输入包含多组测试数据 每组数据为两行, 第一行为一个整数 type, 表示数据类型 (0 1 2 分别表示 int char double) 第二行为 5 个数组元素 输出 对于每一组测试数据, 将其排序后在一行内输出, 每个元素后跟一个空格 样例输入 A B C B A 样例输出 A A B B C 4

5 2 函数模板 1 #include <iostream> 2 using namespace std ; 3 4 template <c l a s s T> 5 void Input (T * array, i n t n) 6 7 f o r ( i n t i =0; i<n ; i++) 8 cin>>array [ i ] ; template <c l a s s T> 12 void Sort (T * array, i n t N) f o r ( i n t i =0; i<n 1; i++) 15 f o r ( i n t j=i +1; j<n; j++) 16 i f ( array [ i ]> array [ j ] ) T temp ; 19 temp = array [ i ] ; 20 array [ i ] = array [ j ] ; 21 array [ j ] = temp ; template <c l a s s T> 26 void Output ( const T * array, i n t N) f o r ( i n t i =0; i<n; i++) 29 cout<<array [ i ]<<" " ; 30 cout<<endl ; i n t main ( ) const i n t LEN = 5 ; 36 i n t type ; 37 while ( cin >> type ) switch ( type ) case 0 : 42 i n t a1 [LEN ] ; 43 Input ( a1, LEN) ; Sort ( a1, LEN) ; Output ( a1, LEN) ; break ; case 1 : 46 char a2 [LEN ] ; 47 Input ( a2, LEN) ; Sort ( a2, LEN) ; Output ( a2, LEN) ; break ; case 2 : 5

6 2 函数模板 50 double a3 [LEN ] ; 51 Input ( a3, LEN) ; Sort ( a3, LEN) ; Output ( a3, LEN) ; break ; return 0 ; 56 6

7 3 单向链表类模板 3 单向链表类模板 题目描述 设计一个单向链表的类模板, 类模板的说明如下 : template <class T> class List private: T data; List * next; static List * tail; // 指向最后一个结点 static List * head; // 指向头结点 public: List():next(NULL) // 构造头结点 head = tail = this; List(T newnode):data(newnode),next(null) // 构造新结点 void Append(T node); // 往后面添加结点 bool Insert(T node, T posnode); // 在结点 posnode 第一次出现的后面插入新结点, 插入成功返回 true, 否则 false void DeleteNode(T node); // 删除结点, 注意可能有多个相同的结点需要删除 void DeleteList(); // 删除整个链表 void DisplayList(); // 显示链表 ; 你的任务是实现这个类模板中的成员函数, 然后使用如下所示的 main() 函数测试你实现的类模板 int main() List<int> list1; list1.append(1); list1.deletenode(1); list1.append(2); list1.append(3); list1.append(4); list1.insert(10,2); list1.append(5); list1.append(3); list1.append(3); list1.displaylist(); list1.deletenode(3); list1.displaylist(); list1.deletelist(); list1.displaylist(); List<char> list2; list2.append('a'); list2.append('b'); list2.append('c'); list2.append('d'); list2.insert('e','b'); list2.insert('f','d'); list2.append('g'); list2.append('g'); list2.append('g'); list2.displaylist(); list2.deletenode('g'); list2.displaylist(); list2.deletelist(); list2.displaylist(); return 0; 7

8 3 单向链表类模板 1 #include <iostream> 2 using namespace std ; 3 4 template <c l a s s T> 5 c l a s s L i s t 6 p r i v a t e : 7 T data ; 8 L i s t * next ; 9 s t a t i c L i s t * t a i l ; // 10 s t a t i c L i s t * head ; //½ 11 public : 12 L i s t ( ) : next (NULL) //¹¹½ head = t a i l = t h i s ; L i s t (T newnode ) : data ( newnode ), next (NULL) //¹¹½ void Append(T node ) ; //º 19 bool I n s e r t (T node, T posnode ) ; //ĺposnodeµ ½, ² µ»true false 20 void DeleteNode (T node ) ; //³½, Ľµ³ 21 void D e l e t e L i s t ( ) ; //³ t± 22 void DisplayList ( ) ; //ʾt± 23 ; template <c l a s s T> 26 List<T> * List<T>:: t a i l ; 27 template <c l a s s T> 28 List<T> * List<T>:: head ; template <c l a s s T> 31 void List <T>:: Append(T node ) t a i l >next = new L i s t ( node ) ; 34 t a i l = t a i l >next ; template <c l a s s T> 38 bool List<T>:: I n s e r t (T node, T posnode ) f o r ( L i s t * f i n d = head >next ; f i n d!= NULL; f i n d = find >next ) 41 i f ( find >data == posnode ) //½ L i s t * temp = new L i s t ( node ) ; 44 i f ( find >next == NULL) // 㣬 p o s n o d e t a i l temp >next = NULL; 47 find >next = t a i l = temp ; 48 return true ; 49 e l s e // 㣬 ²», ²» t a i l 8

9 3 单向链表类模板 50 temp >next = find >next ; 51 find >next = temp ; 52 return true ; return f a l s e ; template <c l a s s T> 59 void List <T>:: DeleteNode (T node ) L i s t * f i n d = head >next, * pre = head ; 62 while ( f i n d!= NULL) i f ( find >data == node ) i f ( find >next == NULL) // 㣬 ³ µ t a i l pre >next = NULL; 69 t a i l = pre ; 70 d e l e t e f i n d ; 71 f i n d = NULL; 72 e l s e //IJ³µ» 73 pre >next = find >next ; 74 d e l e t e f i n d ; 75 f i n d = pre >next ; e l s e //Ľ²»³µ 78 pre = f i n d ; 79 f i n d = find >next ; template <c l a s s T> 85 void List<T>:: D e l e t e L i s t ( ) L i s t * current = head >next ; 88 L i s t * temp ; 89 while ( current!= NULL) temp = current ; 92 head >next = current >next ; 93 current = current >next ; 94 d e l e t e temp ; t a i l = head ; 97 head >next = NULL; 98 9

10 3 单向链表类模板 template <c l a s s T> 101 void List<T>:: DisplayList ( ) f o r ( L i s t * temp = head >next ; temp!= NULL; temp = temp >next ) 104 cout<<temp >data<<" " ; 105 cout<<endl ; i n t main ( ) List<int> l i s t 1 ; 111 l i s t 1. Append (1) ; 112 l i s t 1. DeleteNode (1) ; 113 l i s t 1. Append (2) ; 114 l i s t 1. Append (3) ; 115 l i s t 1. Append (4) ; 116 l i s t 1. I n s e r t (10,2) ; 117 l i s t 1. Append (5) ; 118 l i s t 1. Append (3) ; 119 l i s t 1. Append (3) ; 120 l i s t 1. DisplayList ( ) ; 121 l i s t 1. DeleteNode (3) ; 122 l i s t 1. DisplayList ( ) ; 123 l i s t 1. D e l e t e L i s t ( ) ; 124 l i s t 1. DisplayList ( ) ; List<char> l i s t 2 ; 127 l i s t 2. Append( 'A' ) ; 128 l i s t 2. Append( 'B' ) ; 129 l i s t 2. Append( 'C' ) ; 130 l i s t 2. Append( 'D' ) ; 131 l i s t 2. I n s e r t ( 'E', 'B' ) ; 132 l i s t 2. I n s e r t ( 'F', 'D' ) ; 133 l i s t 2. Append( 'G' ) ; 134 l i s t 2. Append( 'G' ) ; 135 l i s t 2. Append( 'G' ) ; 136 l i s t 2. DisplayList ( ) ; 137 l i s t 2. DeleteNode ( 'G' ) ; 138 l i s t 2. DisplayList ( ) ; 139 l i s t 2. D e l e t e L i s t ( ) ; 140 l i s t 2. DisplayList ( ) ; return 0 ;

11 4 STACK 类模板 4 Stack 类模板 题目描述 实现一个 Stack 类模板并测试这一模板. template<class T, int SIZE = 20> class Stack private: T array[size]; // 数组, 用于存放栈的元素 int top; // 栈顶位置 ( 数组下标 ) public: Stack(); // 构造函数, 初始化栈 void Push(const T & ); // 元素入栈 T Pop(); // 栈顶元素出栈 void Clear(); // 将栈清空 const T & Top() const; // 访问栈顶元素 bool Empty() const; // 测试栈是否为空 bool Full() const; // 测试是否栈满 int Size(); // 返回当前栈中元素个数 ; 测试函数 : int main() Stack<int,10> intstack; int n; cin >> n; //n<=10 for (int i = 0; i < n; i++) int temp; cin >> temp; intstack.push(temp); for (int i = 0; i < n; i++) cout << intstack.top() << " "; intstack.pop(); cout<<endl; if(intstack.empty()) cout<<"now, intstack is empty."<<endl; Stack<string,5> stringstack; stringstack.push("one"); stringstack.push("two"); stringstack.push("three"); stringstack.push("four"); stringstack.push("five"); cout<<"there are "<<stringstack.size()<<" elements in stringstack."<<endl; stringstack.clear(); if(stringstack.empty()) cout<<"now, there are no elements in stringstack"<<endl; return 0; 输入 参考样例 输出 参考样例 11

12 4 STACK 类模板 1 #inc lude <iostream> 2 #include<s t r i n g > 3 /*#include <c s t d l i b >*/ 4 using namespace std ; 5 6 template<c l a s s T, i n t SIZE = 20> 7 c l a s s Stack 8 9 p r i v a t e : 10 T array [ SIZE ] ; // 飬 µ 11 i n t top ; // ã ± 12 public : 13 Stack ( ) ; // ¹¹ ³» 14 void Push ( const T & ) ; // 15 T Pop ( ) ; // 16 void Clear ( ) ; //½«17 const T & Top ( ) const ; // 18 bool Empty() const ; //² 19 bool Full ( ) const ; //² 20 i n t S i z e ( ) ; // µ»± 21 ; template<c l a s s T, i n t SIZE> 24 Stack<T, SIZE >:: Stack ( ) : top ( 1) template<c l a s s T, i n t SIZE> 27 void Stack<T, SIZE >:: Push ( const T &item ) 28 i f (! Full ( ) ) array[++top ] = item ; template<c l a s s T, i n t SIZE> 32 T Stack<T, SIZE >::Pop ( ) 33 i f (! Empty() ) return array [ top ]; 34 e l s e e x i t (1) ; template<c l a s s T, i n t SIZE> 38 void Stack<T, SIZE >:: Clear ( ) top = 1; template<c l a s s T, i n t SIZE> 41 const T & Stack<T, SIZE >::Top ( ) const 42 i f (! Empty() ) return array [ top ] ; 43 e l s e e x i t (1) ; template<c l a s s T, i n t SIZE> 47 bool Stack<T, SIZE >::Empty() const return top == 1; template<c l a s s T, i n t SIZE> 12

13 4 STACK 类模板 50 bool Stack<T, SIZE >:: Full ( ) const return top == SIZE 1; template<c l a s s T, i n t SIZE> 53 i n t Stack<T, SIZE >:: S i z e ( ) return top +1; i n t main ( ) Stack<int,10> intstack ; i n t n ; 60 cin >> n ; //n<=10 61 f o r ( i n t i = 0 ; i < n ; i++) i n t temp ; 64 cin >> temp ; 65 intstack. Push (temp) ; f o r ( i n t i = 0 ; i < n ; i++) cout << intstack. Top ( ) << " " ; 71 intstack. Pop ( ) ; cout<<endl ; i f ( intstack. Empty( ) ) cout<<"now, intstack is empty."<<endl ; Stack<s t r i n g,5> s t r i n g S t a c k ; 78 s t r i n g S t a c k. Push ( "One" ) ; 79 s t r i n g S t a c k. Push ( "Two" ) ; 80 s t r i n g S t a c k. Push ( "Three" ) ; 81 s t r i n g S t a c k. Push ( "Four" ) ; 82 s t r i n g S t a c k. Push ( "Five" ) ; 83 cout<<"there are "<<s t r i n g S t a c k. S i z e ( )<<" elements in stringstack."<<endl ; 84 s t r i n g S t a c k. Clear ( ) ; 85 i f ( s t r i n g S t a c k. Empty( ) ) cout<<"now, there are no elements in stringstack"<<endl ; return 0 ; 88 13

14 5 MYQUEUE 类模板 5 MyQueue 类模板 题目描述 设计一个 MyQueue 类模板, 类模板说明如下 : template <class Type> class MyQueue; template <class Type> std::ostream & operator<<(std::ostream &, const MyQueue<Type> &); template <class Type> class QueueItem // private class: no public section friend class MyQueue<Type>;// 友元类 QueueItem(const Type &t) :item(t), next(0) // 构造函数,next 指针为空指针, 将 t 的值赋给 item Type item; //value stored in this element QueueItem *next; // pointer to next element in the MyQueue // 通过友元函数重载 << 运算符模板函数, 要写上 << 后的 <Type> friend std::ostream & operator<< <Type> (std::ostream &, const MyQueue<Type> &); ; template <class Type> class MyQueue public: MyQueue() : head(0), tail(0) // Empty MyQueue MyQueue(const MyQueue &Q) :head(0), tail(0) CopyElements(Q); ;// 拷贝构造函数 MyQueue & operator=(const MyQueue &);// 重载 = 运算符 ~MyQueue() Destroy(); // return element from head of MyQueue Type & Front() return head->item; const Type & Front() const return head->item; void Push(const Type &); //add element to back of MyQueue void Pop(); // remove element from head of MyQueue bool Empty() const return head == 0; void Display() const; private: QueueItem<Type> *head; QueueItem<Type> *tail; void Destroy(); //delete all the elements void CopyElements(const MyQueue &); friend std::ostream & operator<< <Type> (std::ostream &, const MyQueue<Type> &); ; 实现这个类模板中的成员函数, 然后使用如下所示的 main() 函数测试这一类模板 int main() MyQueue<int> qi; qi.push(1); qi.push(2); qi.push(3); qi.push(4); qi.push(5); qi.pop(); qi.display(); cout<<"\n"; cout<<qi; cout<<endl; MyQueue<int> qi2(qi); qi2.display(); cout<<endl; MyQueue<int> qi3; qi3 = qi; 14

15 5 MYQUEUE 类模板 1 #include <iostream> 2 using namespace std ; 3 4 template <c l a s s Type> c l a s s MyQueue ; 5 template <c l a s s Type> 6 std : : ostream & operator <<(std : : ostream &, const MyQueue<Type> &) ; 7 template <c l a s s Type> c l a s s QueueItem 8 // p r i v a t e c l a s s : no p u b l i c s e c t i o n 9 f r i e n d c l a s s MyQueue<Type>;// 10 QueueItem ( const Type &t ) : item ( t ), next ( 0) // ¹¹ next ½«tµ ³ item 11 Type item ; // value s t o r e d in t h i s element 12 QueueItem * next ; // p o i n t e r to next element in the MyQueue //¹º ģ<< 庯 <<º<Type> 15 f r i e n d std : : ostream & operator<< <Type> ( std : : ostream &, const MyQueue<Type> &) ; 16 ; template <c l a s s Type> c l a s s MyQueue 19 public : 20 MyQueue( ) : head (0), t a i l (0) // Empty MyQueue 21 MyQueue( const MyQueue &Q) : head (0), t a i l (0) CopyElements (Q) ; ; // ½± ¹¹ 22 MyQueue & operator=(const MyQueue &) ; //= 23 ~MyQueue( ) Destroy ( ) ; 24 // return element from head of MyQueue 25 Type & Front ( ) return head >item ; 26 const Type & Front ( ) const r e t u r n head >item ; 27 void Push ( const Type &) ; // add element to back o f MyQueue 28 void Pop ( ) ; // remove element from head o f MyQueue 29 bool Empty() const return head == 0 ; 30 void Display ( ) const ; 31 p r i v a t e : 32 QueueItem<Type> * head ; 33 QueueItem<Type> * t a i l ; 34 void Destroy ( ) ; // d e l e t e a l l the elements 35 void CopyElements ( const MyQueue &) ; f r i e n d std : : ostream & operator<< <Type> ( std : : ostream &, const MyQueue<Type> &) ; 38 ; template<c l a s s Type> void MyQueue<Type >:: Destroy ( ) 42 while (! Empty() ) 43 Pop ( ) ; template<c l a s s Type> void MyQueue<Type >::Pop ( ) 47 QueueItem<Type> * p = head ; 48 head = head >next ; 49 d e l e t e p ; 15

16 5 MYQUEUE 类模板 template<c l a s s Type> void MyQueue<Type >:: Push ( const Type & val ) 53 QueueItem<Type> * pt = new QueueItem<Type>( v a l ) ; 54 i f (Empty() ) 55 head = t a i l = pt ; 56 e l s e 57 t a i l >next = pt ; 58 t a i l = pt ; template<c l a s s Type> void MyQueue<Type >:: CopyElements ( const MyQueue<Type> &o r i g ) 63 f o r ( QueueItem<Type> * pt = o r i g. head ; pt ; pt = pt >next ) 64 Push ( pt >item ) ; template<c l a s s Type> MyQueue<Type> & MyQueue<Type >:: operator=(const MyQueue<Type> & o r i g ) 68 f o r ( QueueItem<Type> * pt = o r i g. head ; pt ; pt = pt >next ) 69 Push ( pt >item ) ; 70 return * t h i s ; template<c l a s s Type> void MyQueue<Type >:: Display ( ) const 74 f o r ( QueueItem<Type> * pt = head ; pt ; pt = pt >next ) 75 cout<<pt >item<<" " ; template<c l a s s Type> ostream & operator <<(ostream & os, const MyQueue<Type> & q ) 79 os<<"< " ; 80 QueueItem<Type> * p ; 81 f o r (p = q. head ; p ; p = p >next ) 82 os<<p >item<<" " ; 83 os<<">" ; 84 return os ; i n t main ( ) MyQueue<int > q i ; 90 qi. Push (1) ; 91 qi. Push (2) ; 92 qi. Push (3) ; 93 qi. Push (4) ; 94 qi. Push (5) ; 95 qi. Pop ( ) ; 96 qi. Display ( ) ; 97 cout<<"\n" ; 16

17 5 MYQUEUE 类模板 98 cout<<q i ; 99 cout<<endl ; MyQueue<int> qi2 ( qi ) ; 102 qi2. Display ( ) ; 103 cout<<endl ; MyQueue<int> qi3 ; 106 qi3 = qi ; 107 cout<<qi3 ; return 0 ;

18 6 SEARCH 6 Search 题目描述 设计一个函数模板, 实现在一个给定的数组中查找给定的元素的值是否存在, 如果存在则输出该元素在数组中最小的下标, 如果不存在, 输出 -1 int main() int n, d; cin >> n >> d; int *nvalues = new int[n]; for (int i = 0; i < n; i++) cin >> nvalues[i]; cout << Search(nValues, n, d) << endl; delete[] nvalues; double f; cin >> n >> f; double *dvalues = new double[n]; for (int i = 0; i < n; i++) cin >> dvalues[i]; cout << Search(dValues, n, f) << endl; delete[] dvalues; char c; cin >> n >> c; char *cvalues = new char[n]; for (int i = 0; i < n; i++) cin >> cvalues[i]; cout << Search(cValues, n, c) << endl; delete[] cvalues; return 0; 输入 输入共三组数据, 每组数据占两行 第一组数据的第一行为一个整数 n1 和 d, 第二行是 n1 个整数 第二组数据的第一行为一个整数 n2 和一个浮点数 f, 第二行是 n2 个浮点数 第三组数据的第一行为一个整数 n3 和一个字符 c, 第二行是 n3 个字符 输出 对于每一组输入, 如果给定元素 ( 上述示例中分别为 d,f,c) 存在, 则输出其最小下标 ( 下标从 0 开始计 ), 否则输出 -1 样例输入 j B J F U 样例输出 提示使用模板函数 18 template <class T> int search(const T * array, int arraylength, const T &value)

19 6 SEARCH 1 #include <iostream> 2 using namespace std ; 3 4 template <c l a s s T> 5 i n t Search ( const T * array, i n t arraylen, const T &value ) 6 7 f o r ( i n t i =0; i<arraylen ; i++) 8 i f ( array [ i ] == value ) 9 return i ; 10 return 1; i n t main ( ) i n t n, d ; 16 cin >> n >> d ; 17 i n t *nvalues = new i n t [ n ] ; 18 f o r ( i n t i = 0 ; i < n ; i++) 19 cin >> nvalues [ i ] ; cout << Search ( nvalues, n, d) << endl ; 22 d e l e t e [ ] nvalues ; double f ; 25 cin >> n >> f ; 26 double * dvalues = new double [ n ] ; 27 f o r ( i n t i = 0 ; i < n ; i++) 28 cin >> dvalues [ i ] ; cout << Search ( dvalues, n, f ) << endl ; 31 d e l e t e [ ] dvalues ; char c ; 34 cin >> n >> c ; 35 char * cvalues = new char [ n ] ; 36 f o r ( i n t i = 0 ; i < n ; i++) 37 cin >> cvalues [ i ] ; cout << Search ( cvalues, n, c ) << endl ; 40 d e l e t e [ ] cvalues ; 41 return 0 ; 42 19