正在学习数据结构、算法与应用C++语言描述这本书，将对本书中的习题进行练手与总结。本答案仅供参考，如有错误，还请指正。
本文代码均已用viusual studio 2019进行验证。
题1：
void swap(int& x ,int& y)
{
int temp = x;
x = y;
y = temp;
}
题2：编写一个模板函数count，返回值是[0:n-1]的数值个数。测试你的代码
#include <iostream>
using namespace std;
template<class T>
int count(T* a, int n)
{
int number = 0;
for (int i = 0; i < n; i++)
number++;
return number++;
}
int main()
{
int n;
cin >> n;
int a[5] = {1,2,3,4,5};
int ans = count(a,n);
cout << ans << endl;
return 0;
}
题3：编写一个模板fill ,给数组a[start ,end -1 ]赋值value。测试你的代码
#include <iostream>
using namespace std;
template<class T>
void fill(T* a, int start, int end, const T &value)
{
for (int i = start; i < end; i++)
{
a[i] = value;
}
return;
}
int main()
{
int a[9] = {1,2,3,4,5,6,7,8,9};
fill(a, 0, 5, 5);
for (auto i : a)
{
cout << i << " ";
}
}
题4：编写一个模板函数inner__product,返回值为内积。测试你的代码
#include <iostream>
using namespace std;
template <class T>
T& inner__product(T* a, T* b, int value)
{
T res = 0;
for (int i = 0; i < value; i++)
{
res += a[i] * b[i];
}
return res;
}
int main()
{
int a[2] = { 1,2 };
int b[2] = { 3,4 };
int ans = inner__product(a, b, 2);
cout << "the inner product is "<<ans << endl;
}
题5： 编写一个模板函数iota，使得a[i]= value +i,0<=i <n。测试你的代码
#include <iostream>
using namespace std;
template <class T>
void iota(T* a, const T& value, const int n)
{
for (int i = 0; i < n; i++)
{
a[i] = value + i;
}
return;
}
int main()
{
int a[5];
iota(a, 2, 5);
for (int i = 0; i < 5; i++)
{
cout << "a[" << i << "] is " << a[i] << " "<< std::endl;
}
}
题6：编写一个模板is_sorted,当且仅当a[0:n-1]有序时，返回true。测试你的代码
#include <iostream>
using namespace std;
template <class T>
bool is_sorted(T* a, int n)
{
int upGrade = 1;
int downGrade = 1;
for(int i = 0; i < n-1 ; i++)
{
if (a[i + 1] > a[i])
upGrade++;
else if (a[i + 1] < a[i])
downGrade++;
}
if ((upGrade == n) || (downGrade == n))
return true;
return false;
}
int main()
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
bool ret = is_sorted(a, 9);
cout << "the array a is sored : " << (ret ? "true" : "flase") << endl;
return 0;
}
题7：编写一个函数模板mismatch，返回值是使得a[i]不等于b[i]成立的最小索引i，0 <= i < n。
#include <iostream>
using namespace std;
template <class T>
T& mismatch(T* a, T* b, int n)
{
for (int i = 0; i < n; i++)
{
if (a[i] != b[i])
return i;
}
return n;
}
int main()
{
int a[5] = { 1,2,3,4,5 };
int b[5] = { 1,2,3,3,5 };
int c[5] = { 1,2,3,4,5 };
int ans1 = mismatch(a, b, 5);
int ans2 = mismatch(a, c, 5);
if (ans1 == 5)
cout << "the two array are the same" << endl;
else
cout << "the least index is " << ans1 << endl;
if (ans2 == 5)
cout << "the two array are the same" << endl;
else
cout << "the least index is " << ans2 << endl;
}
题8：下面的函数投是具有不同签名的函数吗？为什么？
1.int abc(int a, int b, int c)
2.float abc(int a, int b, int c)
答：是的，因为函数返回类型不同，是abc函数的重载，具有不同签名。
题9：下面语句调用分别调用哪个abc函数？那一句会出现错误？为什么？
1.count<<abc(1, 2, 3)<<endln
答：函数调用的签名与程序1.1中abc函数的签名一致。因此，调用程序1.1的abc函数
2.count<<abc(1.0F, 2.0F, 3.0F)<<endln
答：函数调用的签名与程序1.2的abc函数的签名一致。因此，调用程序1.2的abc功能
3.count<<abc(1, 2, 3.0F)<<endln
答：函数调用的签名与abc函数的签名不一致。由于可以实现从float到int和从int到float的类型转换，c++无法解决使用哪个函数，并给出编译时错误。
4.count<<abc(1.0, 2.0, 3.0)<<endln
答：实际参数的类型是double。c++无法解决使用哪个函数，并给出一个编译时错误，因为可以将double类型转换为int和float类型。
题10：修改程序1-8，使抛出的异常类型是整型。如果a,b,c都小于0，那么抛出的异常值是1；如果a,b,c都等于0，那么抛出的异常值是2.否则没有异常。编写一个主函数，应用修改后的代码；若有异常抛出，则捕捉异常；根据异常值输出信息。
#include <iostream>
using namespace std;
int abc(int a, int b, int c)
{
if (a < 0 && b <0 && c <0)
throw 1;
else if (a == 0 && b == 0 && c == 0)
throw 2;
return a + b * c;
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
try { cout << abc(a, b, c) << endl; }
catch (int e)
{
cout << e << endl;
return 1;
}
return 0;
}
题11：
#include <iostream>
using namespace std;
template<class T>
int count(T* a, int n)
{
if (n < 1)
throw "Error";
int number = 0;
for (int i = 0; i < n; i++)
{
number++;
}
return number++;
}
int main()
{
int n;
int c[5] = {1, 2,3,4,5};
cin >> n;
try {cout << count(c,n) << endl;}
catch(const char* e)
{
cout << e << endl;
return 1;
}
return 0;
}
题12：为程序make2dArray编写一个通用型算法，他的第三个参数不是整数numberOfColumns，而是一位数组rowSize.
template <class T>
void make2dArray(T**& x, int numberOfRows, int rowsize[])
{
x = new T * [numberOfRows];
for (int i = 0; i < numberOfRows; i++)
x[i] = new T[rowsize[i]];
}
template <class T>
void delete2dArray(T**& x, int numberOfRows)
{
for (int i = 0; i < numberOfRows; i++)
delete[] x[i];
delete[] x;
x = NULL;
}
题13：
#include <iostream>
using namespace std;
template <typename T>
void change_length_1d (T* &x, T*& new_x, int old_length, int new_length) {
int size = 0;
if (old_length <= new_length) {
size = old_length;
} else {
size = new_length;
}
new_x = new T [new_length];
for (int i = 0; i < size; ++i) {
new_x[i] = x[i];
}
delete [] x;
}
int main() {
int* old_array = new int [5] { 0, 1, 2, 3, 4 };
int* new_array_smaller;
int* new_array_bigger;
change_length_1d(old_array, new_array_bigger, 5, 6);
for (int i = 0; i < 6; ++i) {
cout << new_array_bigger[i] << " ";
}
cout << endl;
change_length_1d(new_array_bigger, new_array_smaller,6, 2);
for (int i = 0; i < 2; ++i) {
cout << new_array_smaller[i] << " ";
}
return 0;
}
题14：
#include <iostream>
#include <algorithm>
using namespace std;
template<class T>
void changeLength2D(T** a, int oldNum1,int oldNum2, int newNum1,int newNum2)
{
T** temp = new T*[newNum1]; // new array
for(int i=0;i<newNum1;i++)
{
temp[i]=new T[newNum2];
}
int num1 = min(oldNum1, newNum1); // number to copy
int num2=min(oldNum2,newNum2);
for(int i=0;i<num1;i++)
{
copy(a[i],a[i]+num2,temp[i]);
}
for(int i=0;i<oldNum1;i++)
{
delete [] a[i];// deallocate old memory
}
delete[]a;
a = temp;
for (int i=0;i<num1;i++)
for(int j=0;j<num2;j++)
cout<<temp[i][j]<<endl;
}
int main()
{
int m=3,n=2;
int**a=new int*[m];
for(int i=0;i<m;i++)
{
a[i]=new int[n];
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
a[i][j]=j;
changeLength2D(a,3,2,4,2);
return 0;
}
15题：略
16题：
//currency.cpp
void currency::input()
{
signType thesign;
unsigned long thedollars;
unsigned int thecents;
cin >> (int&)thesign >> thedollars >> thecents;
setValue(thesign, thedollars, thecents);
}
currency currency::subtract(const currency& x) const
{
long a1, a2, a3;
currency result;
a1 = dollars * 100 + cents;
if (sign == sminus)
a1 = -a1;
a2 = x.dollars * 100 + x.cents;
if (x.sign == sminus)
a2 = -a2;
a3 = a2 -a1;
if (a3 < 0)
{
result.sign = sminus;
a3 = -a3;
}
else
result.sign = splus;
result.dollars = a3 / 100;
result.cents = a3 - result.dollars * 100;
return result;
}
currency& currency::percent(double x)
{
long a1, a2;
currency result;
a1 = dollars * 100 + cents;
a2 = (long)(a1 * x / 100);
result.sign = sign;
result.dollars = a2 / 100;
result.cents = a2 - result.dollars * 100;
return result;
}
currency& currency::multiply(double x)
{
currency result;
long a1, a2;
a1 = dollars * 100 + cents;
a2 = a1 * x;
result.sign = sign;
result.dollars = (long)a2 / 100;
result.cents = a2 - result.dollars * 100;
return result;
}
currency& currency::divide(double x)
{
currency result;
long a1, a2;
a1 = dollars * 100 + cents;
a2 = a1 / x;
result.sign = sign;
result.dollars = (long)a2 / 100;
result.cents = a2 - result.dollars * 100;
return result;
}
17题：使用程序1-19的代码完成练习16
//currency.h
void input()
{
double theValue;
cin >> theValue;
setValue(theValue);
}
currency subtract(const currency& x)
{
currency result;
result.amount = amount - x.amount;
return result;
}
currency percent(float x)
{
currency result;
result.amount = (long) (amount * x / 100);
return result;
}
currency multiply(float x)
{
currency result;
result.amount = (long) (amount * x);
return result;
}
currency divide(float x)
{
currency result;
result.amount = (long) (amount / x);
return result;
}
题19：编写非递归程序计算n！，测试你的代码。
#include <iostream>
using namespace std;
int func1(int n);
int main()
{
int number;
cin >> number;
try { cout << func1(number) << endl; }
catch (const char* e)
{
cout << e << endl;
return 1;
}
}
int func1(int n)
{
int res = 1;
if (n < 0)
throw "error: n <0";
if (n == 0 || n == 1)
return 1;
while (n > 1)
{
res *= n;
n--;
}
return res;
}
题20：
//递归法
int Fibonacci(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
{
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
//非递归法
int Fibonacci2(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
int num0 = 0;
int num1 = 1;
int res = 0;
for (int i = 1;i < n; i++)
{
res = num1 + num0 ;
num0 = num1;
num1 = res;
}
return res;
};
题21：
//递归法
int function(int n)
{
if (n % 2 == 0)
return n / 2;
if (n % 2 == 1)
return function(3 * n + 1);
}
//非递归法
int function2(int n)
{
if (n % 2 == 0)
return n / 2;
if (n % 2 == 1)
return n + (n + 1) / 2;
}
题22：
int Ackermann(int i,int j)
{
if(i==1&&j>=1)
return pow(2,double(j));
else if(i==2&&j==1)
return Ackermann(i-1,2);
else if(i>=2&&j>=2)
return Ackermann(i-1,Ackermann(i,j-1));
}
题23：
int gcd(int x,int y)
{
if(x<y)
{
int temp=x;
x=y;
y=temp;
}
if(y==0)
return x;
else
return gcd(y,x%y);
}
题24：
template<class T>
bool function(const vector<T>& a, int x, int pos)
{
int n = a.size();
if (pos >= n)
return false;
if (x == a[pos] && pos < n)
return true;
else
return in_the_array(a, x, pos + 1);
}
题25：
template <typename T>
void Subset_Generation(vector<T> a, int n, vector<int> b) {
if (n == 0) {
for (int i = 0; i < b.size(); i++)
cout << b[i];
cout<<endl;
}
else
{
b[n-1]=0;
Subset_Generation(a,n-1,b);
b[n-1]=1;
Subset_Generation(a,n-1,b);
}
}
题26：
void function(int n)
{
if(n==1)
cout<<1;
else
{
function(n-1);
cout<<n;
function(n-1);
}
}
题27~题44
本文持续更新中......
网友评论