第一章 简单编程 （1）
1.1删除序列中相同的数
有16个数|1,2,2,3,4,4,5,6,6,7,8,8,8,9，10，10|，已按由小到大的顺序排好,存储 在数组a中。试建立一个类ARR,完成删除数组中相同的数，经删除后，数组a中的内容 为 |1,2,3,4,5,6,7,8,9，10
/*C++程序设计实践指导
第一章 简单编程
1.1删除序列中相同的数*/
/*有16个数|1,2,2,3,4,4,5,6,6,7,8,8,8,9，10，10|，已按由小到大的顺序排好,存储 在数组a中。试建立一个类ARR,完成删除数组中相同的数，经删除后，数组a中的内容 为 |1,2,3,4,5,6,7,8,9，10*/
#include<iostream>
#include<iomanip>
using namespace std; //使用标准命名空间std
class ARR{
int m; //数组元素实际个数
int a[100]; //存放原始数组及结果数组
public:
ARR(int x[],int size){ //构造函数，用参数 size 初始化 m，用参数 x 初始化 a
m=size;
for(int i=0;i<m;i++){
a[i]=x[i];
}
}
void delsame(); //完成数组 a中相同元素的删除工作
void show(){ // 将数组以每行5个数的形式输出到屏幕上
cout<<setiosflags(ios::left);
for(int i=0;i<m;i++){
cout<<setw(3)<<a[i];
if((i+1)%5==0)cout<<endl;
}
cout<<resetiosflags(ios::left);
cout<<endl;
}
};
void ARR::delsame(){ //在类的外部定义函数， //完成数组 a中相同元素的删除工作
int i,j;
for(i=0;i<m-1;i++){
if(a[i]==a[i+1]){ // 如果前后相邻的两个元素相同，用这两个元素后的元素覆盖...
//后面那个相同元素。
for(j=i+1;j<m-1;j++)a[j]=a[j+1];//依次向前覆盖，直到数组结束。
m--;//删除一个元素后，元素个数减 1
i--;//有可能出现连续多个相同的数，所以应继续判断当前元素
}
}
}
int main(){
int b[]={1,2,2,3,4,4,5,6,6,7,8,8,8,9,10,10};
ARR v(b,sizeof(b)/sizeof(b[0]));/*定义一个ARR类的对象v，用b及数组元素的个数初始化该对象。*/
v.show();//显示原数组
v.delsame();
v.show();//显示结果数组
return 0;
}
1.2 二维数组的操作运算
编写一个通用程序，求出二维数组（行数和列数必须相等）的非对角线元素之和，即 求两条对角线之外的元素之和。例如，数组值如下，其非对角线元素之和为8。
试建立一个类matrix,用于完成该功能。
#include<iostream>
using namespace std;
/**/
/*将以上以二维数组为数据结构的程序实现改写为以单向链表结构来表示矩阵，可定义数据结构体，如下所示：*/
struct linkNode
{
int row;//存放二维数组的行号
int column;//存放二维数组的列号
int data;//存放二维数组对应行号及列号中的数
linkNode *next; //指向下一个结点的指针
};
class Matrix
{
public:
Matrix(int x[][40],int k);//构造函数，用k初始化数据成员m,用数组X初始化数组a
~Matrix() {};
void process();//完成求和
void show();//按二维方式输出数组，并输出求和结果
private:
int m;//二维数组的行数和列数相等，即二维数组是m行m列的
int sum;//存放非对角线元素之和
int a[40][40];//用于存放二维数组
};
Matrix::Matrix(int x[][40], int k)
{
m = k;
sum = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
a[i][j] = x[i][j];
}
}
}
void Matrix::process()
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
if ((i==j)||(i+j==m-1)) //若元素在对角线上, 不计人累加和
{
continue;
}
sum+=a[i][j];
}
}
}
void Matrix::show()
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
cout<<a[i][j]<<" ";
}
cout << endl;
}
cout << "sum=" << sum << endl;
}
/*在主程序中定义二维数组b[40][40], 存放原始数据，用上述数据作为测试数据。
定义一个 MATRIX类的对象mtx，用数组b及数组的实际行数初始化对象mtx, 完成对该类的测试*/
int main()
{
int b[40][40] = { {1,1,1,1},{ 1,2,2,1 },{ 1,2,2,1 },{ 1,1,1,1 } };
Matrix mtx(b,4);
mtx.process();//处理
mtx.show();//显示
system("pause");
return 0;
}
1.3求任意整数降序数
对一个5位数的任意整数，求出其降序数。例如，整数是82319,则其降序数是 98321。猝法提示:将整数的各位数分解到一维整型数组a中，再将a数组中的元素按降 序排序，最后输出a数组元素值。试建立一个类NUM，用于完成该功能。
#include<iostream>
using namespace std;
class Num
{
public:
Num(int x=0) ;//构造函数，用参数x初始化数据成员n
~Num() {};
void descrease();//将n的各位数值分解到a数组中，并将a数组排列成降序
void descrease1();
void show()//屏幕显示原数及其降序数
{
cout << "n=" << n << endl;
for (int i = 0; i < 5; i++)
{
cout << a[i];
}
cout << endl;
}
private:
int n;//存放5位数的整数
int a[5];//存放其元素的降序排列值
};
Num::Num(int x )
{
n = x;
for (int i = 0; i < 5; i++)
{
a[i] = 0;
}
}
void Num::descrease()
{
int x = n;
int i = 0;
while (x)
{
a[i] = x % 10;
x = x / 10;
i++;
}
//show();
//对数组a[i]中的数用冒泡法降序排序
for (int k = 0; k < 4; k++)/k<5
{
for (int j = 0; j < 4-k; j++)
{
if (a[j]<a[j+1])
{
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}
void Num::descrease1()
{
int x = n;
int i = 0;
while (x)
{
a[i] = x % 10;
x = x / 10;
i++;
}
//show();
//对数组a[i]中的数用选择法降序排序
for (int k = 0; k < 4; k++)k<5
{
for (int j = k+1; j < 5; j++)
{
if (a[k]>a[j ])
{
int tmp = a[k];
a[k] = a[j ];
a[j ] = tmp;
}
}
}
}
/*在主程序中输人一个5位数的任意整数，然后定义一个NUM类的对象num，
用上述输入的数 初始化num，然后完成对该类的测试*/
int main()
{
int n;
cout << "Input n:(82319)";
cin >> n;
Num num(n);
num.descrease();
num.show();
num.descrease1();
num.show();
system("pause");
return 0;
}
1.4正整数转换成字符串
建立一个类STR，将一个任意正整数转换为相应的字符串。例如整数3456转换为字
符串"3456"。
#include<iostream>
using namespace std;
double Str2Num(char* s)//字符型数转为可计算的数
{
double num = 0;
bool decimal = 0;
double exp = 0.1;
while (*s)
{
if (*s == '.')
{
decimal = 1;
s++;
continue;
}
if (!decimal)
{
num = num * 10 + (*s - '0');
}
else
{
num = num + (*s - '0')*exp;
exp *= 0.1;
}
s++;
}
return num;
}
class Num2Str
{
public:
Num2Str(int x) :num(x) {}
~Num2Str() {}
void itoa();//将num转换成字符串并存入字符数组s中
void print()
{
cout << "n=" << num << endl;
cout << "string=";
/*cout<<s<<endl;*/
char *p = s;
cout << p;
cout << endl;
}
private:
int num;//被转换的整数
char s[15];//存放转换完的字符串
};
void Num2Str::itoa()
{
int i = 0;
int x = num;
while (x)
{
s[i] = x % 10 + '0';
x /= 10;
i++;
}
s[i] = '\0';
for (int j = 0; j <=(i-1)/2; j++)//(i/2)-1
{
char c=s[j];
s[j] = s[i - 1 - j];
s[i - 1 - j] = c;
}
}
/*在主程序中输人一个5位数的任意整数，然后定义一个NUM类的对象num，
用上述输入的数 初始化num，然后完成对该类的测试*/
int main()
{
int n;
cout << "Input n:"; cin >> n;
Num2Str n2s(n);
n2s.itoa();
n2s.print();
system("pause");
return 0;
}
1.5求两个整数集合并集
整数集合是由多个不同的整数构成，可将其存放在一个一维整型数组中。两个集合的并集由属于两个集合的全体元素构成，注意不能出现重复元素。例如，集合a[ ]= {1, 3,5,7,9}，集合 b[]={1,2,3,4,5,6}，它们的并集是 c[]=丨1,3,5,7,9,2,4,6|。求 并集的算法是:先将a数组中的全体元素放入c数组，再依次判断b数组中的每一个元素 b[ i]，如果b[i]不属于a数组，则将b[i]加入c数组。试建立一个类SET,完成求两个整 数集合的并集。
#include<iostream>
using namespace std;
class Set
{
public:
Set(int [],int,int [],int);
~Set(){}
void insert(); //求集合a和b的并集c
//int notin(int);//
int notin(int,int [],int);
void output()
{
cout << "k=" << numc << endl;
for (int i = 0; i < numc; i++)
{
cout << c[i] << " ";
}
cout << endl;
}
private:
int a[40], b[40], c[40];//a、b用于存放已知的两个整数集合，c用于存放a、b的并集
int numa, numb, numc;//用于存放a、b和c，3个集合实际元素的个数
};
/*构造函数，初始化数据成员 a、numa 和 b、numb。 同时，将numc初始化为0 .
x和lenl是集合a的初始化数据数组及其元素个数;y和len2是集合b的初始化数据数组及其元素个数。*/
Set::Set(int x[], int len1, int y[], int len2)
{
for (int i = 0; i < len1; i++)
{
a[i] = x[i];
}
for (int i = 0; i < len2; i++)
{
b[i] = y[i];
}
numa = len1; numb = len2; numc = 0;
}
/*整数elem如果不属于集合s,则返回1;否则返回0。
提示:若在数组s中杳找到值为elem的元素,则返回0;若找不到，返回1 */
/*int Set::notin(int elem)//,int s[],int size
{
for (int i = 0; i < numa; i++)
{
if (a[i]==elem)
{
return 0;
}
}
return 1;
}*/
int Set::notin(int elem, int s[], int size)
{
for (int i = 0; i < size; i++)
{
if (s[i] == elem)
{
return 0;
}
}
return 1;
}
void Set::insert()
{
for (int i = 0; i < numa; i++)
{
c[i] = a[i];
numc++;
}
int k = numc;
for (int i = 0; i < numb; i++)
{
if (notin(b[i],c,numc)==1)
//if (notin(b[i])==1)
{
c[k] = b[i];
k++;
numc++;
}
}
}
/*在主程序中定义两个数组int s1[]、int s2[]用于存放两个集合数据,
sl[]的初始数据为1,3,5,7,9；s2[]的初始数据为1,2,3,4,5,6。
定义一个Set类的对象set,用sl、s2以及它们的元素个数初始化set,然后完成对该类的测试*/
int main()
{
int s1[] = { 1,3,5,7,9 };
int s2[] = { 1,2,3,4,5,6 ,9,10,7,10};
Set set(s1, sizeof(s1) / sizeof(s1[0]), s2, sizeof(s2) / sizeof(s2[0]));
set.insert();
set.output();
system("pause");
return 0;
}
1.6分数运算
#include<iostream>
using namespace std;
class Fract
{
public:
Fract(int a = 0, int b = 1) :num(a),den(b) {}
Fract add(Fract);//将参数分数f与对象自身相加，返回约简后的分数对象
int ged(int, int);//求 m、n 的最大公约数
void show()
{
cout << num << "/" << den << endl;;
}
private:
int num, den;
};
Fract Fract::add(Fract f)//将参数分数f与对象自身相加，返回约简后的分数对象
{
Fract sum;
sum.den = den*f.den;
sum.num = num*f.den + f.num*den;
int x=ged(sum.den, sum.num);
sum.den /= x;
sum.num /= x;
return sum;
}
int Fract::ged(int m, int n)//求 m、n 的最大公约数//欧几里得算法//辗转相除法
{
while (int r=m%n)
{
m = n;
n = r;
}
return n;
}
/*在主程序中定义两个分数对象fl和f2,其初值分别是1/5和7/20,
通过fl调用成员函数add 完成fl和f2的相加,将得到的分数賦给分数对象f3,显示分数对象f3*/
int main()
{
Fract f1(1, 5), f2(7, 20), f3;
f3 = f1.add(f2);
f3.show();
system("pause");
return 0;
}
1.7超长数列中n个整数排序
设有一个包含size个数的数列，要求能够把从指定位置m开始的n个数 排列成降序，并输出新的完整的数列。可将数列存放在一维数组中。例如，原数列有10个数，值为 {1,8,3,0,5,9,7,6,9,8},若要求把从第4个数开始的5个数排成降序，则得到的新数列 为{1,8，3,9，7,6,5，0，9，8}。试建立一个类List,来完成上述功能。
#include<iostream>
using namespace std;
class List
{
public:
List(int [],int);//构造函数，用len初始化size,根据size动态分配数组存储空间，arr指向该存储空间
~List()
{
if (arr)
{
delete []arr;
}
}
void sortPart(int,int);//将数列从第m个元素幵始的n个数排成降序
void outPut()
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
private:
int size;//数列元素的个数
int *arr;//数列数组的起始指针
};
List::List(int a[],int len)//构造函数，用len初始化size,根据size动态分配数组存储空间，arr指向该存储空间
{
size = len;
arr = new int[len];
for (int i = 0; i < len; i++)
{
arr[i] = a[i];
}
}
void List::sortPart(int m, int n)//将数列从第m个元素幵始的n个数排成降序
{
for (int i = m-1; i < m+n-1; i++)//冒泡排序
{
for(int j=m-1;j<m+n-2-(i-(m-1));j++)//迷惑迷惑迷惑
{
if (arr[j]<arr[j+1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
/*for (int k = 0; k < 10; k++)/k<5
{
for (int j = 0; j < 9 - k; j++)
{
if (arr[j]<arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}*/
}
/*在主程序中定义数组int a[10]用于存放原始数列，定义一个LIST类的对象tt,
用a数组及数组实际元素的个数初始化该对象，然后把从第4个数开始的5个数按降序排列，完成该类的测试*/
int main()
{
int a[] = { 1,8,3,7,0,5,6,9,9,8 };
List tt(a, sizeof(a) / sizeof(a[0]));
tt.outPut();
tt.sortPart(3,5);
tt.outPut();
system("pause");
return 0;
}
1.8求指定范围内的所有素数
建立一个类PRIMENUM，求指定数据范围内的所有素数（质数）。提示：素数的定义 是“只能被I和它本身整除的整数”，即质数。
#include<iostream>
using namespace std;
class PrimeNum
{
public:
PrimeNum(int n1, int n2) :span1(n1), span2(n2), num(0), arr(NULL){}
~PrimeNum()
{
if (arr)
{
delete[]arr;
}
}
int isPrimeNum(int x);//判断x是否为素数。若是素数，返冋1;否则返回0
void process();//求指定范围内的所有素数，把它们依次存放在数组arr中，并将求出的素数个数赋给num
void print()
{
cout << "num=" << num << endl;
int k = 0;
for (int i = 0; i < num; i++)
{
cout << arr[i] << '\t';
k++;
if (k%5==0)
{
cout << endl;
}
}
cout << endl;
}
private:
int *arr;//依次存放指定范围内求出的所有素数,arr为起始指针。
int span1, span2; //存放指定的数据范围的下限和上限
int num;//存放spanl与span2之间的素数个数
};
void PrimeNum::process()
{
for (int i = span1; i <=span2; i++)
{
if (isPrimeNum(i))
{
//arr = new int;
//arr[num++] = i;
num++;
}
}
arr = new int[num];
int j = 0;
for (int i = span1; i <= span2; i++)
{
if (isPrimeNum(i))
{
arr[j++] = i;
}
}
}
int PrimeNum::isPrimeNum(int x)
{
for (int i = 2; i <x; i++)
{
if (x%i==0)
{
return 0;
}
}
return 1;
}
/*定义一个PrimeNum类的对象test,指定查找范围为100〜200,
即求100〜200之间的所有素数。通过test调用成员函数完成求素数及输出素数的工作*/
int main()
{
PrimeNum test(100, 200);
test.process();
test.print();
system("pause");
return 0;
}