编程练习(比C要难)(91-100)
91、请编写一个 C 函数，该函数给出一个字节中被置 1 的位的个数。
【参考答案】unsigned int TestAsOne0(char log) {
int i;
unsigned int num=0, val;
for(i=0; i<8; i++) {
val = log >> i; //移位
val &= 0x01; //与1相与
if(val)
num++;
}
return num;
}
92、编写一个函数，函数接收一个字符串,是由十六进制数组成的一组字符串,函数的功能是把接到的这组字符串转换成十进制数字.并将十进制数字返回。
【参考答案】BOOL HexToDec( LPCTSTR shex,int& idec ) {
int i,mid;
int len = lstrlen( shex );
if( len>8 )
return FALSE;
mid = 0;
idec = 0;
for( i=0;i<len;i++ ) {
if( shex[i]>='0'&&shex[i]<='9' )
mid = shex[i]-'0';
else if( shex[i]>='a'&&shex[i]<='f' )
mid = shex[i] -'a' +10;
else if( shex[i]>='A'&&shex[i]<='F' )
mid = shex[i] -'A' +10;
else
return FALSE;
mid <<= ((len-i-1)<<2); // 移位表示变为2的n次方倍
idec =idc+mid;
}
return TRUE;
}
93、输入一个字符串，将其逆序后输出 。
【参考答案】void main(){
char a[50];memset(a,0,sizeof(a));
int i=0,j;
char t;
cin.getline(a,50,'\n');
for(i=0,j=strlen(a)-1;i<strlen(a)/2;i++,j--) {
t=a[i];
a[i]=a[j];
a[j]=t;
}
cout<<a<<endl;
}
94、编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。
【参考答案】void frequency( String& s, char& A[ ], int& C[ ], int &k )
{
int i, j, len = s.length( );
if ( !len ) { cout << "The string is empty. " << endl; k = 0; return; }
else
{
A[0] = s[0]; C[0] = 1; k = 1; /*语句s[i]是串的重载操作*/
for ( i = 1; i < len; i++ ) C[i] = 0; /*初始化*/
for ( i = 1; i < len; i++ )
{ /*检测串中所有字符*/
j = 0; while ( j < k && A[j] != s[i] ) j++; /*检查s[i]是否已在A[ ]中*/
if ( j == k )
{ A[k] = s[i]; C[k]++; k++ }/*s[i]从未检测过*/
else C[j]++;/*s[i]已经检测过*/
}
}
}
95、假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。
【参考答案】循环队列类定义#include <assert.h>
template <class Type> class Queue {//循环队列的类定义
public:
Queue ( int=10 );
~Queue ( ) { delete [ ] elements; }
void EnQueue ( Type & item );
Type DeQueue ( );
Type GetFront ( );
void MakeEmpty ( ) { length = 0; }//置空队列
int IsEmpty ( ) const { return length == 0; }//判队列空否
int IsFull ( ) const { return length == maxSize; }//判队列满否
private:
int rear, length;//队尾指针和队列长度
Type *elements;//存放队列元素的数组
int maxSize;//队列最大可容纳元素个数
}；
template <class Type>Queue<Type>:: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) {//建立一个最大具有maxSize个元素的空队列。<span style="white-space:pre"></span>elements = new Type[maxSize];<span style="white-space:pre"></span>//创建队列空间<span style="white-space:pre"></span> assert ( elements != 0 );<span style="white-space:pre"></span>//断言: 动态存储分配成功与否}template<class Type> void Queue<Type> :: EnQueue ( Type &item ) {<span style="white-space:pre"></span>assert ( ! IsFull ( ) );<span style="white-space:pre"></span>//判队列是否不满，满则出错处理<span style="white-space:pre"></span>length++;<span style="white-space:pre"></span>//长度加1<span style="white-space:pre"></span>rear = ( rear +1) % maxSize;<span style="white-space:pre"></span>//队尾位置进1<span style="white-space:pre"></span>elements[rear] = item;<span style="white-space:pre"></span>//进队列}template<class Type> Type Queue<Type> :: DeQueue ( ) {<span style="white-space:pre"></span>assert ( ! IsEmpty ( ) ); <span style="white-space:pre"></span>//判断队列是否不空，空则出错处理<span style="white-space:pre"></span>length--;<span style="white-space:pre"></span>//队列长度减1<span style="white-space:pre"></span>return elements[(rear-length+maxSize) % maxSize];<span style="white-space:pre"></span>//返回原队头元素值}template<class Type> Type Queue<Type> :: GetFront ( ) {<span style="white-space:pre"></span>assert ( ! IsEmpty ( ) );<span style="white-space:pre"></span>return elements[(rear-length+1+maxSize) % maxSize];<span style="white-space:pre"></span>//返回队头元素值}
96、已知A[n]为整数数组，试写出实现下列运算的递归算法：
(1) 求数组A中的最大整数。(2) 求n个整数的和。
(3) 求n个整数的平均值。
【参考答案】
#include <iostream.h>
class RecurveArray
{//数组类声明
private: int *Elements;//数组指针
int ArraySize;//数组尺寸
int CurrentSize;//当前已有数组元素个数
public :
RecurveArray ( int MaxSize =10 ) :
ArraySize ( MaxSize ), Elements ( new int[MaxSize] ){ }
~RecurveArray ( ) { delete [ ] Elements; }
void InputArray();//输入数组的内容
int MaxKey ( int n );//求最大值
int Sum ( int n );//求数组元素之和
float Average ( int n );//求数组元素的平均值
};
void RecurveArray :: InputArray ( )
{//输入数组的内容
cout << "Input the number of Array: \n";
for ( int i = 0; i < ArraySize; i++ ) cin >> Elements[i];
}
int RecurveArray :: MaxKey ( int n )
{//递归求最大值
if ( n == 1 ) return Elements[0];
int temp = MaxKey ( n - 1 );
if ( Elements[n-1] > temp ) return Elements[n-1];
else return temp;
}
int RecurveArray :: Sum ( int n ) {//递归求数组之和
if ( n == 1) return Elements[0];
else return Elements[n-1] + Sum (n-1);
}
float RecurveArray :: Average ( int n ) {//递归求数组的平均值
if ( n == 1) return (float) Elements[0];
else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n;
}
int main ( int argc, char* argv [ ] ) {
int size = -1;
cout << "No. of the Elements : ";
while ( size < 1 ) cin >> size;
RecurveArray ra ( size );
ra.InputArray();
cout<< "\nThe max is: " << ra.MaxKey ( ra.MaxSize ) << endl;
cout<< "\nThe sum is: " << ra.Sum ( ra.MaxSize ) << endl;
cout<< "\nthe avr is: " << ra.Average ( ra.MaxSize ) << endl;
return 0;
}
97、已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：
(1) 求链表中的最大整数。(2) 求链表的结点个数。
(3) 求所有整数的平均值。
【标准答案】
#include <iostream.h>//定义在头文件"RecurveList.h"中
class List;
class ListNode {//链表结点类
friend class List;
private:
int data;//结点数据
ListNode *link;//结点指针
ListNode ( const int item ) : data(item), link(NULL) { }//构造函数
};
class List {//链表类
private:
ListNode *first, current;
int Max ( ListNode *f );
int Num ( ListNode *f );
float Avg ( ListNode *f, int& n );
public:
List ( ) : first(NULL), current (NULL) { }//构造函数
~List ( ){ }//析构函数
ListNode* NewNode ( const int item );//创建链表结点, 其值为item
void NewList ( const int retvalue );//建立链表, 以输入retvalue结束
void PrintList ( );//输出链表所有结点数据
int GetMax ( ) { return Max ( first ); }//求链表所有数据的最大值
int GetNum ( ) { return Num ( first ); }//求链表中数据个数
float GetAvg ( ) { return Avg ( first ); }//求链表所有数据的平均值
};
ListNode* List :: NewNode ( const int item ) {//创建新链表结点
ListNode *newnode = new ListNode (item);
return newnode;
}
void List :: NewList ( const int retvalue ) {//建立链表, 以输入retvalue结束
first = NULL; int value; ListNode *q;
cout << "Input your data:\n";//提示
cin >> value;//输入
while ( value != retvalue )
{//输入有效
q = NewNode ( value );//建立包含value的新结点
if ( first == NULL ) first = current = q;//空表时, 新结点成为链表第一个结点
else { current->link = q; current = q; }//非空表时, 新结点链入链尾
cin >> value;//再输入
}
current->link = NULL;//链尾封闭
}
void List :: PrintList ( )
{//输出链表
cout << "\nThe List is : \n";
ListNode *p = first;
while ( p != NULL ) { cout << p->data << ' '; p = p->link; }
cout << ‘\n’;
}
int List :: Max ( ListNode *f )
{//递归算法 : 求链表中的最大值
if ( f ->link == NULL ) return f ->data;//递归结束条件
int temp = Max ( f ->link );//在当前结点的后继链表中求最大值
if ( f ->data > temp )
return f ->data;//如果当前结点的值还要大, 返回当前检点值
else return temp;//否则返回后继链表中的最大值
}
int List :: Num ( ListNode *f )
{//递归算法 : 求链表中结点个数
if ( f == NULL ) return 0;//空表, 返回0
return 1+ Num ( f ->link );//否则, 返回后继链表结点个数加1
}
float List :: Avg ( ListNode *f , int& n )
{//递归算法 : 求链表中所有元素的平均值
if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件
{
n = 1; return ( float ) (f ->data );
}
else
{ float Sum = Avg ( f ->link, n ) * n; n++; return ( f ->data + Sum ) / n; }
}
#include "RecurveList.h"//定义在主文件中
int main ( int argc, char* argv[ ] )
{
List test; int finished;
cout << “输入建表结束标志数据 ：”;
cin >> finished;//输入建表结束标志数据
test.NewList ( finished );//建立链表
test.PrintList ( );//打印链表
cout << "\nThe Max is : " << test.GetMax ( );
cout << "\nThe Num is : " << test.GetNum ( );
cout << "\nThe Ave is : " << test.GetAve () << '\n';
printf ( "Hello World!\n" );
return 0;
}
98、字符串的替换操作replace (String &s, String &t, String &v)是指：
若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。【参考答案】
String & String :: Replace ( String & t, String &v)
{
if ( ( int id = Find ( t ) ) == -1 ) //没有找到，当前字符串不改，返回
{ cout << “The (replace) operation failed.” << endl; return *this; }
String temp( ch );//用当前串建立一个空的临时字符串
ch[0] = '\0'; curLen = 0;//当前串作为结果串，初始为空
int j, k = 0, l;//存放结果串的指针
while ( id != -1 ) {
for ( j = 0; j < id; j++) ch[k++] = temp.ch[j];
curLen += id + v.curLen;//修改结果串连接后的长度
if ( curLen <= maxLen ) l = v.curLen; //确定替换串v传送字符数l
else { l = curLen - maxLen; curLen = maxLen; }
for ( j = 0; j < l; j++ ) ch[k++] = v.ch[j];
//连接替换串v到结果串ch后面
if ( curLen == maxLen ) break;//字符串超出范围
for ( j = id + t.curLen; j < temp.curLen; j++ )
temp.ch[j- id - t.curLen] = temp.ch[j];//删改原来的字符串 temp.curLen -= ( id + t.curLen );
id = temp.Find ( t ); }
return *this;
}
99、试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。
【参考答案】
void Josephus( int A[ ], int n, s, m ){
int i, j, k, tmp;
if ( m == 0 ) {
cout << "m = 0是无效的参数！" << endl;
return;
}
for ( i = 0; i < n; i++ ) A[i] = i + 1;/*初始化，执行n次*/
i = s - 1;/*报名起始位置*/
for ( k = n; k > 1; i-- ) {/*逐个出局，执行n-1次*/
if ( i == k ) i = 0;
i = ( i + m - 1 ) % k;/*寻找出局位置*/
if ( i != k-1 ) {
tmp = A[i];/*出局者交换到第k-1位置*/
for ( j = i; j < k-1; j++ ) A[j] = A[j+1];
A[k-1] = tmp;
}
}
for ( k = 0; k < n / 2; k++ ) {/*全部逆置, 得到出局序列*/
tmp = A[k]; A[k] = A[n-k+1]; A[n-k+1] = tmp;
}
}
100、编写类 String 的构造函数、析构函数和赋值函数已知类 String 的原型为：
class String请编写 String 的上述 4 个函数。 【标准答案】
{
public:
String(const char *str = NULL); // 普通构造函数
String(const String &other); // 拷贝构造函数
~ String(void); // 析构函数
String & operate =(const String &other); // 赋值函数
private:
char *m_data; // 用于保存字符串
};
// String 的析构函数
String::~String(void)
{
delete [] m_data;
// 由于 m_data 是内部数据类型，也可以写成 delete m_data;
}
// String 的普通构造函数
String::String(const char *str)
{
if(str==NULL)
{
m_data = new char[1]; // 若能加 NULL 判断则更好
*m_data = ‘\0’;
}
else
{
int length = strlen(str);
m_data = new char[length+1];
strcpy(m_data, str);
}
}
// 拷贝构造函数
String::String(const String &other)
{
int length = strlen(other.m_data);
m_data = new char[length+1]; // 若能加 NULL 判断则更好
strcpy(m_data, other.m_data);
}
// 赋值函数
String & String::operate =(const String &other)
{
if(this == &other)
return *this;
delete [] m_data;
int length = strlen(other.m_data);
m_data = new char[length+1];
strcpy(m_data, other.m_data);
return *this;
}