C++程序设计案例实训教程第3章

时间:2022-08-31 19:04:57

3章  数    组

数组是类型名、标识符和维数组成的复合数据类型。类型名规定了存放在数组中元素的类型,标识符也就是数组名称,而维数则指定数组中包含元素的个数。数组实际上是内存中连续存储的一组同种数据类型的元素(变量),每个数组有一个唯一的名称,通过在名称后面加索引(index)的方式可以引用它的每一个元素。本章举的实例都是关于数组的,如一维和多维数组元素排序,从一个数组赋值到另一个数组,数组在内存中占用的字节数。

本章重点讲解了多维数组、字符数组的实际应用实例,初学者应反复多实践,加深理解。另外还举了综合应用的实例,涉及类模板的概念,读者应举一反三,提高编程能力。

3.1  什么是数组

数组是在内存中连续存储的一组同种数据类型的元素(变量),每个数组有一个唯一的名称,通过在名称后面加索引(index)的方式可以引用它的每一个元素。

案例3-1  推箱子(数组元素移动)

【案例描述】

数组是数目固定、类型相同的若干个变量的有序集合,它在实际应用中非常广泛。本实例用数组存储箱子的体积,用适当的方法把箱子按体积从小到大排放好,结果如图3-1所示。

 

3-1  推箱子(数组元素移动)

【实现过程】

首先定义存放箱子体积的数组v[n],数组大小为n = 10,用一个for语句输出排序前数组中每个元素的值;然后采用的是冒泡排序,该算法是依次比较相邻的两个数,将小数放在前面,大数放在后面,对排序后的数组再用一个for输出显示数组中每个元素的值。代码如下:

#include <iostream>

using namespace std;

 

int main ()

{

  const int n = 10; //数组大小

  //定义双精度型并初始化

  double v[n] = { 20.5, 35.8, 43.3, 32.5, 36.9,

                  22.3, 29.4, 33.7, 25.9, 30.6 };

 

  cout << "排序前数组的值为:\n";

  for (int i=0; i<n; i++) cout << " " << v[i]; //打印数组的值

  cout << endl;

 

  //实现冒泡排序

  bool changed;

  do{

     changed = false;

     for (int i=0; i<n-1; i++) { //for循环实现从1n

 if ( v[i] > v[i+1] ){ //交换记录

           double swap = v[i]; //swap仅作暂存单元

              v[i] = v[i+1];

            v[i+1] = swap;

           changed = true;

        }

     }

  }while (changed);

 

  cout << "排序后数组的值为:\n";

  for ( i=0; i<n; i++) cout << " " << v[i]; //打印数组的值

  cout << endl;

  system("pause");

  return 0;

}

【案例分析】

1一种典型的数组声明格式为:type name [elements];,这里的type可以是任何一种有效的对象数据类型,如 intfloat等,name是一个有效的变量标识,而由方括号[]引起来的elements域指明数组的大小,即可以存储多少个元素。代码中声明数组double v[n];,数据类型为double,v为变量标识,n表示数组的大小。

2)上述代码采用冒泡排序算法,其中用到了do{…}while和for两个循环,循环中采用交换数值。double swap = v[i]; v[i] = v[i+1]; v[i+1] = swap;3句,实现了移动数组元素把小数放到前面的功能。

 

注意:C++允许数组初始化时方括号[ ]中的内容为空白,而数组的长度将由后面的花括号{}中数值的个数决定。如double v[] = { 20.5, 35.8, 43.3};,数组长度为3

案例3-2  一个简单的数据统计系统 (综合)

【案例描述】

本实例是综合的例子,目的是对C++的特点做进一步理解。如定义字符串、输入字符串、比较字符串大小并进行统计、打印字符串等。本例效果如图3-2所示。

 

3-2  一个简单的数据统计系统(综合)

【实现过程】

定义字符数组s[100],读取字符数组,利用for循环进行统计,然后打印出统计结果。其代码如下:

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

int a,b,c; //定义统计小写字母、大写字母和阿拉伯数字的变量

char s[100]; //定义输入字符数组

a=0,b=0,c=0;       //初始化

cout<<"请输入测试的字符串:"<<endl;

gets(s);   //读取字符串

for(int i=0;i<strlen(s);i++)  

{   

if(s[i]>='a'&&s[i]<='z') a++; //小写字母个数  

if(s[i]>='A'&&s[i]<='Z') b++; //大写字母个数

if(s[i]>='0'&&s[i]<='9') c++; //阿拉伯数字

}  

cout<<"小写字母个数:"<<a<<endl;   //打印结果

cout<<"大写字母个数:"<<b<<endl;

cout<<"阿拉伯数字个数:"<<c<<endl;

system("pause");

}

【案例分析】

1)库函数gets()实现从标准输入设备(键盘)读取字符串,直到读取换行符结束,但读取的换行符会被丢弃,最后在末尾添加'\0'字符。调用格式gets(s);s为字符串变量,可以是字符串数组名或字符串指针。

2)库函数strlen()实现取字符串长度。上述代码s[i]>='a'用于比较字符的大小。

 

注意:gets(s)函数中的变量s为一个字符串或字符指针。如果为单个字符,编译连接不会有错误,但运行后会出现“Null pointer asignment”的错误。

案例3-3  输出字符串的每个字符(for访问数组)

【案例描述】

字符串用来存储一个以上字符的非数字值的变量,在编程中会经常用到。编程中定义了字符串或字符串数组并赋值,需要输出字符串的每个字符,如下载一个文本文件,若其内容存储在字符串中,需要一个字符一个字符地读取。本实例输出一个字符串和钻石图形,效果如图3-3所示。

【实现过程】

程序分两个演示:demo1()定义1个字符串c[12],并进行初始化,用for语句逐个输出单字符;demo2()代码定义和初始化一个二维字符串数组,然后逐个引用数组元素,每次输出一个字符,打印出一个漂亮的钻石图形。代码如下:

#include <iostream>

using namespace std;

int demo1()

{

//字符串进行初始化

static char c[12]="I am happy!";

int i;

for(i=0;i<12;i++) //for循环逐个引用数组元素

cout<<c[i]; //每次输出一个字符

cout<<endl;

   return 0;

}

void demo2( )

{

//二维字符串数组初始化

char diamond[][7]={"  *"," * *","*   *","*    *","*   *"," * *","  *"};

int i,j;

for (i=0;i<7;i++)

{

for (j=0;j<7;j++)

cout<<diamond[i][j]; //逐个引用数组元素,每次输出一个字符

cout<<endl;

}

}

int main()

{

   demo1();

   cout <<"\n"; //换行

   demo2();

   cout << "\n";

   system("pause");

   return 0;

}

【案例分析】

1C++语言将字符串按字符数组来处理。例如,字符串常量GOOD!",在机器内被处理成一个无名的字符型一维数组,存储为" GOOD!"'\0'C++语言中约定用'\0'作为字符串的结束标志,结束标志占内存空间,但不计入串的长度。有了结束标志'\0',程序就依据标志判断字符串是否结束,而不是根据定义时设定的长度。可以用字符串的形式为字符数组赋初值,如代码char c[12]="I am happy!";,长度为12字节,以'\0'结尾。

2)代码char diamond[][7]={}定义为1个二维字符串数组并初始化。二维字符串数组的一般格式为:类型说明符 数组名[常量表达式1][常量表达式2],如float a[3][4],千万不能写成floata[3,4],分行给二维数组初始化如int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}},一一对应赋值如int a[3][4]={{1,2,3,4,5,6,7,8,9,10,11,12}},如果数组的元素都赋值,第一维可以省略,但第二维必须有。

 

注意:字符串与字符数组的区别在于:字符数组char  a[ ]={'C','H','I','N','A'};,在内存中以'A'结束,长度占5字节;而字符串char  c[ ]="CHINA"; ,在内存中以'\0'结束,长度占6字节。

 

案例3-4  循环改写一段字符串(for访问数组)

【案例描述】

在实际编程中,应对指定的符合条件的字符串进行相应的处理。本例将一行姓名字符串中的每个单词的第一个字母改成大写,效果如图3-4所示。

【实现过程】

程序定义字符串st和name,提示输入测试人数,输入每个人的姓名,将姓名字符串中每个单词的第一个字母改写成大写。代码如下:

 

3-4  循环改写一段字符串(for访问数组)

#include<iostream.h>

#include<iostream>

#include<stdio.h>

int main(void)

{

    char st[1000];

    char name[12];

    int i=0;

    char c;

int num; //输入测试人数

    cout<<"姓名字符串中的每个单词的第一个字母改写成大写:"<<endl;

    strcpy( st, "" ); //字符串清空

    cout <<"输入测试人数:"<<endl;

    cin >> num;

    cout << "输入每个人姓名:"<<endl;

do {

        cin >> name; //输入每个人的姓名

        strcat( st,name); //连接两个字符串

if(i<num)

          strcat( st," " );

i++;

} while (i<num); //如果大于测试人数,则退出主程序

    st[strlen(st)-1]='\0'; //字符串最后一个字母为'\0'

    cout<<"输入的所有人的名字:"<<endl;

cout<<st<<endl;

    if(st[0]>='a'&&st[0]<='z') //首字母改为大写

        st[0]=st[0]-32;

    for(i=0;c=st[i]!='\0';i++)

    {

        if(st[i]==' '&&st[i+1]!=' ')

            st[i+1]=st[i+1]-32; //每个单词的第一个字母改写成大写

    }

     cout<<"最后第一个字母改写成大写结果为:"<<endl;

     cout<<st<<endl;

     system("pause");

     return 0;

}

【案例分析】

1)库函数strcat( st,name)实现连接两个字符串的功能。代码char st[1000]char name[12]strcpy( st, "" );,把空字符串赋值给char st[1000],也就是st清空。

2)代码中st[0]=st[0]-32;的作用是将首字母改为大写。这是因为字母中ASCII值的大写和小写字母相差32if(st[i]==' '&&st[i+1]!=' ')表示字符串中的字符为空格。

 

注意:字符串如char str[12]="The String";,其中str为字符数组在内存中存储的地址,它一经定义,便成为常量不可再赋值。

3.2  一维数组

案例3-5  内存输出(打印数据)

【案例描述】

数组是数目固定、类型相同的若干个变量的有序集合,它存储在内存中占用内存空间,通过编程,可以取得内存中的地址。本实例取数组和指定元素在内存中的地址,结果如图3-5所示。

【实现过程】

子程序demo1()定义存储9个整数的数组Number,逐个显示数组元素,因为数组也是一个变量声明,所以能找到地址;demo2()中显示输出Number、取地址&Number和第一个元素地址&Number[0];demo3()中显示输出数组Number,取第一个元素地址&Number[0],移动数组1的位置,取第二个元素地址&Number[1],再移动数组1的位置,取第三个元素地址&Number[2]地址。代码如下:

#include <iostream>

using namespace std;

int demo1()

{

    int Number[] = { 61, 38, 31, 30, 31, 30, 31, 31, 30 };

    cout << "显示数组元素:";

    cout << "\nNumber 1:  " << Number[0]; //打印Number[0]

    cout << "\nNumber 2:  " << Number[1];

    cout << "\nNumber 3:  " << Number[2];

    cout << "\nNumber 4:  " << Number[3];

    cout << "\nNumber 5:  " << Number[4];

    cout << "\nNumber 6:  " << Number[5];

    cout << "\nNumber 7:  " << Number[6];

    cout << "\nNumber 8:  " << Number[7];

    cout << "\nNumber 9:  " << Number[8];

    cout << endl;

    return 0;

}

int demo2()

{

    int Number[] = { 61, 38, 31, 30, 31, 30, 31, 31, 30 };

    cout << "\n Number    :  " << Number; //打印Number内容

    cout << "\n&Number    :  " << &Number; //打印取地址&Number内容

    //打印第一个元素地址&Number[0]的内容

    cout << "\n&Number[0] :  " << &Number[0] << endl;  

    cout << endl;

    return 0;

}

int demo3()

{

    int Number[] = { 61, 38, 31, 30, 31, 30, 31, 31, 30 };

    cout << "整数(integer)占用字节: " << sizeof(int) << " bytes";

    cout << "\n Number:    " << Number; //打印Number的内容

    cout << "\n&Number[0]: " << &Number[0] ;    //打印第1个元素地址&Number[0]的内容

    cout << "\n Number+1:  " << Number+1;  

    cout << "\n&Number:[1] " << &Number[1] ;     //打印第2个元素地址&Number[1]的内容

    cout << "\n Number+2:  " << Number+2;

    cout << "\n&Number:[2] " << &Number[2]<<endl ;//打印第3个元素地址&Number[2]的内容

    return 0;

 

}

void main()

{

demo1();

demo2();

demo3();

system("pause");

return;

}

【案例分析】

1demo2()表明数组Number、数组地址&Number和第一个元素地址&Number[0]具有相同的值。C++语言的指针使用符号“&”来取得变量的地址。因此,&Number表示取得数组变量地址。数组Number、数组地址&Number具有相同的值,而且在代码中看到Number、&Number和&Number[0]都有相同的值,这表明变量的名字实际上代表第一个元素地址。

2demo3 ()int占用4字节,存在int数据类型的数组Number移动一个位置,存储空间移动4字节,这样就能很好地理解代码。

 

注意:这里举的是一维数组的实例,二维或多维存储在内存中的地址是不是与一维同样规律?读者可修改代码看看。

案例3-6  一维数组的应用

【案例描述】

本实例输入数据到一维数组中,然后读取存储在数组中的数据进行运算。本例效果如图3-6所示。

 

3-6  一维数组的应用

【实现过程】

从键盘接收10个整数实现求其平均数和输出小于平均数的功能。代码如下:

#include <iostream>

using namespace std;

main()

{

  int a[10],i,sum=0; //定义数组和整型变量

  float ave=0; //存储平均值

  for(i=0;i<=9;i++) //09循环

 {

   cout<<"请输入整数:";

   cin>>a[i]; //输入整数

   sum=sum+a[i]; //求输入整数和

  }

   ave=sum/10.0; //求整数和的平均

   cout<<"平均数:"<<ave;

   cout<<"小于平均数:";

   for(i=0;i<=9;i++) //09循环

   {

  if(a[i]<ave)   

  cout<<" "<<a[i]<<endl; //输出整数

   }

   system("pause");

}

【案例分析】

1)这是简单的一维数组的应用,定义数组a[10],然后进行赋值和读取。一维数组是由数字组成的、以单纯的排序结构排列的、结构单一的数组,是二维数组和多维数组的基础。

2)数组是一个由若干同类型变量组成的集合,引用这些变量时可用同一个名字。

3)数组均由连续的存储单元组成,最低地址对应数组的第一个元素,最高地址对应最后一个元素。数组可以是一维的,也可以是多维的。

案例3-7  整数从大到小排序(比较法)

【案例描述】

续演示一维数组应用的例子。本实例是读取数组中的元素并进行排序,效果如图3-7所示。

 

3-7  整数从大到小排序(比较法)

【实现过程】

用比较法对10个整数按从大到小的顺序进行排序。代码如下:

#include <iostream>

using namespace std;

main()

{

  int a[10]={7, 15, 4, 12, 9, 3, 10, 0, 24, 6}; //定义数组

  int i,j,temp;      //定义整数变量  

  for(i=0;i<9;i++) //09循环

for(j=i+1;j<10;j++) //09循环

if (a[i]<a[j]) //a[i]a[j]比较

{

temp=a[i];a[i]=a[j];a[j]=temp; //a[i]a[j]交换

}

for(i=0;i<=9;i++) //输出比较后的整数

cout<<" "<<a[i];

  cout<<endl;                            //换行

  system("pause"); }

【案例分析】

1)定义数组时赋初值,即数组的初始化。例如:

int a[5]={ 1,2,3,4,5 };

2)利用比较法进行比较。

① a[1]a[9]a[0]进行比较,若比a[0]大,则与a[0]进行交换,保证a[0]是最大数。

② a[2]a[9]a[1]进行比较,若比a[1]大,则与a[1]进行交换,保证a[1]是次大数。

③ 依此类推。

 

注意:在对全部的数组元素赋初值时,允许省略数组元素的个数。如int a[]={ 1,2,3,4,5 };也就等价于int a[5]={ 1,2,3,4,5 }

实例3-8  传统杀毒软件基本实现原理(文件关键字定位)

【案例描述】

反病毒软件的任务是实时监控和扫描磁盘。部分反病毒软件通过在系统中添加驱动程序的方式进驻系统,并且随操作系统一起启动。大部分杀毒软件还具有防火墙功能。本例演示的是进程中是否包含可疑文件名,有则杀掉,效果如图3-8所示。

 

3-8  传统杀毒软件基本实现原理(文件关键字定位)

【实现过程】

反病毒软件的实时监控方式因软件而异。有的反病毒软件,是通过在内存里划分一部分空间,将电脑中流过内存的数据与反病毒软件自身所带的病毒库(包含病毒定义)的特征码相比较,以判断是否为病毒。另一些则在所划分到的内存空间中,虚拟执行系统或用户提交的程序,根据其行为或结果作出判断。而扫描磁盘的方式,即和上面提到的实时监控的第一种工作方式基本一样,稍有不同的是反病毒软件会将磁盘上所有的文件(或者用户自定义扫描范围内的文件)做一次检查。部分代码如下:

BOOL ProcessVXER (void)  //扫描进程

{

DWORD lpidProcess[1024],cbNeeded_1,cbNeeded_2;

HANDLE hProc;

HMODULE hMod[1024];

char ProcFile[MAX_PATH];

char FileName[FIVE]={LOW};

BOOL returnvalue=FALSE;

int Pcount=LOW;

int i;

EnablePrivilege(SE_DEBUG_NAME);  //提升权限

//枚举进程

if (!(EnumProcesses(lpidProcess,sizeof(lpidProcess),&cbNeeded_1)))

{  printf("EnumProcesses() GetLastError reports %d\n",erron);

return 0;  }

for (i=LOW;i<(int)cbNeeded_1/4;i++)

{  //打开找到的第一个进程

hProc=OpenProcess(PROCESS_ALL_ACCESS,FALSE,(unsigned long)lpidProcess);

if (hProc)

{  //枚举进程模块

if (EnumProcessModules(hProc,hMod,sizeof(hMod),&cbNeeded_2))

{  //枚举进程模块文件名,包含全路径

if (GetModuleFileNameEx(hProc,hMod[0],ProcFile,sizeof(ProcFile)))

{   printf("[%5d]\t%s\n",lpidProcess,ProcFile); //输出进程

     //可以考虑将其注释掉,这样就不会输出进程列表了

Pcount++;

strcpy(FileName,"C:\\WINNT\\system32\\");

strcat(FileName,name); //把文件名+路径复制到FileName变量中

//查找进程中是否包含FileName

if (strcmp(FileName,ProcFile)==LOW)

{  

//如果包含,则杀掉;KillProc为自定义的杀进程函数

if (!(KillProc(lpidProcess)))

{   printf("KillProc() GetLastError reports %d\n",erron);

CloseHandle(hProc);

exit(0);   }

DeleteFile(FileName); //进程杀掉后,再将文件删除

}  }  }  }  }

CloseHandle(hProc); //关闭进程句柄

printf("\nProcess total:%d\n",Pcount); //打印进程各数

returnvalue=TRUE;

return 0;

}

【案例分析】

1)一个杀毒软件一般由扫描器、病毒库与虚拟机组成,并由主程序将它们组合为一体。简单地说杀毒软件的实现原理就是匹配特征码。当扫描得到一个文件时,杀毒软件会检测这个文件中是否包含病毒库中所包含的特征码。如果有则查杀;如果没有即使这个文件确实是一个病毒,它也会把它当作正常文件来看待。

2)上面代码主要进程操作函数如:EnumProcessModules枚举进程,GetModuleFileNameEx枚举进程模块文件名。

 

注意:程序编译时用到psapi.lib,运行时用到psapi.dll;在VC++使用时,需加入以下代码:#include "PSAPI.H" #pragma comment (lib,"Psapi.lib")。

3.3 多维数组

多维数组(Multidimensional Arrays)可以描述为数组的数组。例如,一个二维数组可以想象成一个有同一数据类型的二维表格。多维数组并不局限于二维。若需要可以定义任意多维,不过程序编写中需要三维以上的时候并不多。

案例3-9  数据复制(复制一组数组到另一组数组)

【案例描述】

数组存储的元素可以从一个数组复制到另一个数组,通过在数组名称后面加索引(如a[2]),实现对指定位置的元素进行复制操作。本实例将一个二维数组a的行和列的元素互换,然后存到另一个二维数组b中,结果如图3-9所示。

【实现过程】

程序初始化一个二维数组a,定义一个二维数组b,执行两个for循环,按行、列的顺序输出a的值,同时把值赋给b中对应的列、行中;再执行两个for循环按行、列的顺序输出b的值,把数组b

中的值加10后赋值给对应列、行的数组a中;最后执行两个for循环按行、列的顺序输出a的值。代码如下:

#include<iostream>

using namespace std;

int main()

{

int a[2][3] = {{10,20,30},{40,50,60}};

int b[3][2];

int i,j;

cout<<"array a:"<<endl;

for(i=0;i<=1;i++) //i取值为01,对应数组a的行(数组是从0开始算的)

{

for(j=0;j<=2;j++) //j取值为012,对应数组a的列

{

cout<<a[i][j]<<" ";

b[j][i]=a[i][j];

}

cout<<endl;

}

cout<<"array b:"<<endl;

for(i=0;i<=2;i++) //i取值为012,对应数组b的行

{

for(j=0;j<=1;j++) //j取值为01,对应数组b的列

{

cout<<b[i][j]<<" ";

                a[j][i]=b[i][j]+10;

}

cout<<endl;

}

cout<<"array a:"<<endl;

for(i=0;i<=1;i++) //i取值为01,对应数组a的行(数组是从0开始算的)

{

for(j=0;j<=2;j++) //j取值为012,对应数组a的列

{

cout<<a[i][j]<<" ";

}

cout<<endl;

}

     system("pause");

return 0;

}

【案例分析】

1)代码int a[2][3] = {{1,2,3},{4,5,6}};,定义为整型的二维2´3数组,并且初始化值。

2)代码中第一次是两个for循环,实现二维数组ab的行和列的元素互换。数组的索引总是从0开始,如a数组中第2行第3列元素的表达式为:a [1][2]

 

注意:多维数组只是一个抽象的概念,因为只需要把各个索引的乘积放入一个简单的数组中,就可以获得同样的结果。例如:a[4][5];,效果上等价于a [20]; (4 * 5 = 20),唯一的区别是编译器能帮我们记住每一个想象中的维度的深度。

案例3-10  查找二维坐标点(二维for

【案例描述】

二维数组编程中经常要排序和查找元素。本实例定义一组二维坐标,要求对坐标按照x从小到大排序,如果两个点的x坐标相同,那么就按照点的y坐标从小到大排序。本例效果如图3-10所示。

 

3-10  查找二维坐标点(二维for

【实现过程】

1)定义一个二维坐标点结构Point,对xy的坐标值进行冒泡排序,输出排序后点的坐标。每行包括两个用空格分隔的整数,分别是点的x坐标和点的y坐标。代码如下:

#include <iostream>

#include <iostream.h>

typedef struct Point //定义一个二维点

{

int x;

int y;

}Po;

//对坐标按照x从小到大排序,如果两个点的x坐标相同,则按照点的y坐标从小到大排序

void Sort(Po P[], int m)

{

int i,j;

int tx,ty; //交换用的临时变量

int flag;

for(i=m-1;i>0;i--) //冒泡排序

{

flag=0;

for(j=0;j<=i-1;j++)

{

if(P[j].x>P[j+1].x) //大于后一个数组点

{

tx=P[j].x;      

ty=P[j].y;

P[j].x=P[j+1].x;

P[j].y=P[j+1].y;

P[j+1].x=tx;    

P[j+1].y=ty;

flag=1;

}

             //如果两个点的x坐标相同,那么就按照点的y坐标从小到大排序

else if(P[j].x==P[j+1].x&&P[j].y>P[j+1].y)

{

tx=P[j].x;     

ty=P[j].y;

P[j].x=P[j+1].x;

P[j].y=P[j+1].y;

P[j+1].x=tx;   

P[j+1].y=ty;

flag=1;

}

}

if(flag==0)break; //这轮没有交换,不用进入下一轮排序

}

cout <<"排序后的坐标 :"<<endl;

for(i=0;i<m;i++)

{

cout <<P[i].x<<" "<<P[i].y<<endl;

}

cout <<endl;

}

2)主程序提示输入一个正整数n,表示有n组测试用例。对于每组测试用例,会提示输入一个正整数m,表示需要排序的点的数量,然后循环m次,提示每行输入两个整数,分别表示点的x坐标和y坐标。代码如下:

void main()

{

Po P[5];

int i;

int n,m;

cout <<"输入你要多少组测试用 :"<<endl;

cin>>n; //输入一个正整数n,表示有n组测试用例

while(n!=0)

{

       cout <<"需要排序的坐标点的数量 :"<<endl;

cin >>m; //每组测试会输入一个正整数m,表示需要排序的点的数量

    cout <<"开始输入点的XY坐标 :"<<endl;

for(i=0;i<m;i++) //m行,每行包括两个整数

{

cin >>P[i].x>>P[i].y; //分别表示点的x坐标和y坐标

}

Sort(P,m);

n--;

}

system("pause");

}

【案例分析】

1)数组声明的语法形式为:type name [elements];type可以是任何一种有效的对象数据类型,如intfloat等;也可以是一个结构,如本例二维坐标点结构typedef struct Point。

2)在Sort()函数中,用两个for循环实现xy坐标值的冒泡排序,该算法是依次比较相邻的两个数,将小数放在前面,大数放在后面。

 

注意:从这个实例可以知道数组的数据类型可以是一个结构,后面实例还演示了数组是类模板的数据类型。

案例3-11  查找矩阵中最大的元素(二维for

【案例描述】

继续037实例的内容。编程中会碰到查找矩阵中最大的元素,如矩阵存储的是一个年级的学生成绩,需要找到最高分及其学生所在的班级。本例效果如图3-11所示。

 

3-11  查找矩阵最大的元素(二维for

【实现过程】

定义一个二维数组,存储矩阵的值,有一个3´4的矩阵,要求编程找出矩阵中值最大的那个元素以及它所在的行和列。代码如下:

#include <iostream>

using namespace std;

main()

{

int a[3][4]={{3,5,1,8},{4,6,11,7}, {9,3,5,2}}; //定义数组

int i,j,row,col,max; //定义整型变量

max=a[0][0]; //存储最大的元素

for(i=0;i<3;i++) //03循环

 for(j=0;j<4;j++) //04循环

   {

   if(a[i][j]>max) //a[i]max比较

       {

 max=a[i][j];row=i;  col=j; //maxa[i][j]

}

}

cout<<"矩阵最大的元素:"<<max<<endl;

cout<<"所在的行:"<<row<<",列:"<<col<<endl;

system("pause");

}

【案例分析】

1)二维数组初始化与一维数组类似,如:

int a[4][3]={{123},{456},{789}, {101112}};

2)在初始化二维数组时,如果给出数组中所有元素的初值,可以不写第一维的长度,但第二维的长度不可省略。如:

int a[4][3]={{123},{456},{789},{101112}};

等价于

int a[][3]={ {123},{456},{789},{101112}};

 

注意:只对部分二维数组元素初始化时,其他元素会自动为0,例如:int a[3][3]={{0,1},{0,0,2},{3}};。初始化后各元素值为:a[0][0]=0 a[0][1]=1 a[0][2]=0 a[1][0]=0 a[1][1]=0 a[1][2]=2 a[2][0]=3  a[2][1]=0 a[2][2]=0。

案例3-12  二分法查找(二维for

【案例描述】

本实例初始化10个数,然后按从小到大的顺序存放在一个数组中。再输入一个数,要求用二分法查找该数。本例效果如图3-12所示。

 

3-12  二分法查找(二维for

【实现过程】

10个数按从小到大的顺序存放在一个数组中,输入一个数要求用二分法查找该数是否是该数组中某个元素的值。如果找不到,则打印“无”;如果找到,则输出该数的位置。代码如下:

#include <iostream>

using namespace std;

main()

{

  int a[10]={1,2,3,4,5,6,7,8,9,10}; //定义一维数组

  int n,front,back,mid; //定义整数

  cout<<"请输入整数:";

  cin>>n; //输入一个整数

  front=0; //开始值

  back=9; //结束值

  while(back!=front) //直到与开始值相等

  {

  mid=(front+back+1)/2; //求平均值

  if(n<a[mid]) //na[mid]比较

  {

  back=mid;                      //结束值等于平均值

  }

      else if(n>a[mid])                  //输入整数大于a[mid]

      front=mid; //开始值等于平均值

      else {

  cout<<"输入整数在数组位置:"<<a[mid-1]<<endl;

  break;

  }

  }

  if (back<=front)                      //结束值小于或等于开始值

  cout<<"输入整数不在数组内"<<endl;

  system("pause");

}

【案例分析】

1)采用二分法查找时,数据必须是排好序的。

2)二分法查找的基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值,则在数列的后半段中继续查找,直到找到为止。

 

注意:当数据量很大时,适宜采用二分法查找。

案例3-13  查找三维坐标点(三维for

【案例描述】

继续039实例的演示,在三维数组编程中实现排序和查找元素。本实例定义一组三维坐标,要求对坐标值按照x从小到大排序;如果两个点的x坐标相同,那么就按照点的y坐标从小到大排序,若y坐标相同,则按z坐标从小到大排序。本例效果如图3-13所示。

 

3-13  查找三维坐标点(三维for

【实现过程】

1)定义一个三维坐标点结构Point,运行xyz坐标值的冒泡排序,排序结束后输出排序好点的坐标。每行包括3个用空格分隔的整数,分别是点的xyz坐标值。代码如下:

#include <iostream>

#include <iostream>

#include <iostream.h>

typedef struct Point //定义一个三维点

{

int x;

int y;

int z;

}Po;

//对坐标按照x从小到大排序,如果两个点的x坐标相同,则按照点的 y 坐标从小到大排序

void Sort(Po P[], int m)

{

int i,j;

int tx,ty,tz; //交换用的临时变量

int flag;

for(i=m-1;i>0;i--) //冒泡排序

{

flag=0;

for(j=0;j<=i-1;j++)

{

//x坐标大于后一个数组点

if(P[j].x>P[j+1].x)

{

tx=P[j].x;      

ty=P[j].y;

tz=P[j].z;

P[j].x=P[j+1].x;

P[j].y=P[j+1].y;

P[j].z=P[j+1].z;

P[j+1].x=tx;    

P[j+1].y=ty;

                P[j+1].z=tz;

flag=1;

}

  //x坐标相同,y坐标大于后一个数组点

else if(P[j].x==P[j+1].x&&P[j].y>P[j+1].y)

{

tx=P[j].x;      

ty=P[j].y;

tz=P[j].z;

P[j].x=P[j+1].x;

P[j].y=P[j+1].y;

P[j].z=P[j+1].z;

P[j+1].x=tx;    

P[j+1].y=ty;

                P[j+1].z=tz;

flag=1;

}         

             //两个点的xy坐标相同,z坐标值大于后一个数组

else if(P[j].x==P[j+1].x&&P[j].y==P[j+1].y&&P[j].z>P[j+1].z)

{

tx=P[j].x;     

ty=P[j].y;

ty=P[j].z;

P[j].x=P[j+1].x;

P[j].y=P[j+1].y;

P[j].z=P[j+1].z;

P[j+1].x=tx;   

P[j+1].y=ty;

P[j+1].z=tz;

flag=1;

}

 

}

if(flag==0)break; //这轮没有交换,不用进入下一轮排序

}

cout <<"排序后的坐标 :"<<endl;

for(i=0;i<m;i++)

{

cout <<P[i].x<<" "<<P[i].y<<" "<<P[i].z<<endl;

}

cout <<endl;

}

2)主程序提示输入一个正整数n,表示有n组测试用例。对于每组测试用例,会提示输入一个正整数m,表示需要排序的点的数量;然后是m行,提示每行输入3个整数,分别表示点的xyz坐标值。代码如下:

void main()

{

Po P[5];

int i;

int n,m;

cout <<"输入你要多少组测试用 :"<<endl;

cin>>n; //输入一个正整数n,表示有n组测试用例

while(n!=0)

{

       cout <<"需要排序的坐标点的数量 :"<<endl;

cin >>m; //每组测试会输入一个正整数m,表示需要排序的点的数量

     cout <<"开始输入点的XY坐标 :"<<endl;

for(i=0;i<m;i++) //m行,每行包括两个整数

{

//分别表示点的x坐标和y坐标

cin >>P[i].x>>P[i].y>>P[i].z;  

}

Sort(P,m);

n--;

}

system("pause");

}

【案例分析】

1)数组的声明可以是任何一种有效的对象数据类型,如intfloat等;也可以是一个结构,如本实例定义的三维坐标点结构typedef struct Point。在Sort()函数中,用3for循环实现xyz坐标值的冒泡排序,与上例不同的是,本例用了3if判断进行坐标值交换。

2)函数void Sort(Po P[], int m)中的Po P[]是函数数组,也就是把数组参数传递给函数。函数参数的传递是将实参的值赋给形参,但对于数组作为参数是一个例外。因为数组的数据太多,将其一一赋值既麻烦,又浪费空间,所以数组作为参数传递给函数的只是数组首元素的地址,函数在需要用到后面的元素时,再按照这个地址和数组下标去查找。也就是说,后面的元素根本没进入函数中,所以在函数里求不出数组的大小。

注意:一个函数的输入参数是一个数组时,必须让这个函数知道数组的大小,因为数组传递给函数的是数组首元素在内存中的地址。

案例3-14  按位数排列

【案例描述】

编程的目的是解决存在的现实问题,本实例把千位数的数字存储在不同的数组中,用for循环和if比较的方法,由小到大排序。本例效果如图3-14所示。

 

3-14  按位数排列

【实现过程】

204位数,编程将这些数按千位由小到大排列,若千位相同,则按十位排列。代码如下:

#include <iostream>

using namespace std;

int main()

{

int  a[10][3]={{1631},{2845},{6456},{1467},{4566},

                             {4518},{5605},{5706},{1365},{3458}};

int i,j,k;

 int t[3];

 for(i=0;i<10;i++)

 {a[i][1]=a[i][0]/1000; //千位数

  a[i][2]=a[i][0]/10%10; //十位数

 }

for(i=0;i<10;i++) //for循环

 for(j=i+1;j<10;j++)

   {     if(a[i][1]<a[j][1]) //千位数比较

              for(k=0;k<2;k++)

              {  t[k]=a[j][k]; a[j][k]=a[i][k];  a[i][k]=t[k]; }//交换

          else   if  (a[i][1]==a[j][1]) //千位数相同

                      if(a[i][2]<a[j][2]) //十位数比较

                         for(k=0;k<2;k++)

                          {   t[k]=a[j][k]; //交换

                              a[j][k]=a[i][k];

  a[i][k]=t[k];       }   

}

cout<<"输出排序后的数:"<<endl;

 for(i=0;i<10;i++)    

 printf("%6d\n",a[i][0]); //输出排序后的数

 system("pause");

 return 0;

}

【案例分析】

for循环中对千位数进行比较,然后进行交换;如果千位数相同,那么就进行十位数比较,交换数字。

案例3-15  统计班上男生和女生的人数(数组随机访问)

【案例描述】

现演示一个有趣的程序。班上有26个学生(包括男生和女生),随机安排在10´10的教室里,上下左右移动,哪里有空位置,就安排到那里,最后统计每排男生和女生的数量。本例效果如图3-15所示。

 

3-15  统计班上男生和女生的人数(数组随机访问)

【实现过程】

定义二维数组laby2存储10´10教室的值,一维数组all_letter存储班上男生和女生的值;4个方位变量up、down、right和left,初始化值为true;用两个for循环数组laby,每个元素赋值为'.';然后用while循环对26个学生(代码中是27个,“#”结束指示用)都随机安排位置,是随机算法step=rand()%4,其功能是随机产生一个数和4进行取模运算,switch(step)表示上、下、左和右方向。其代码如下:

#include<iostream>

#include<cstdlib>

#include<ctime>

using namespace std;

#define ROW 10

#define COL 10

//AL代表男生,MZ代表女生

int main()

{

//定义1个二维数组并赋初值

 int laby[ROW][COL],all_letter[27]={'A','B','C','D','E','F','G','H','I','J',

                                 'K','L','M','N','O','P','Q','R','S','T',

         'U','V','W','X','Y','Z','#'};

 int row,col,letter,step;

 bool up,down,right,left;

 up=down=right=left=true; //4个方向都通

 for(row=0;row<ROW;row++) //执行2for循环

  for(col=0;col<COL;col++)

   laby[row][col]='.'; //数组laby初始化为'.'

 srand((unsigned int) time(NULL));

 row=col=letter=0;

 laby[row][col]=all_letter[letter++];

 //std::cout<<row<<col<<all_letter[letter]<<endl;

 while(letter<27) //全部输出26个字母

 {

  step=rand()%4; //值为0123

//step取值0123,表示向上、下、左和右方向移动

  switch(step)

  {

  case 0:if(up=((row-1>=0)&&(laby[row-1][col]=='.')))

   {

 // std::cout<<row<<col<<endl;

    row--;

    laby[row][col]=all_letter[letter++];

    break;

   }

     case 1:if(down=((row+1<ROW)&&(laby[row+1][col]=='.')))

   {

    //std::cout<<row<<col<<endl;

    row++;

    laby[row][col]=all_letter[letter++];

    break;

      }

     case 2:if(left=((col-1>=0)&&(laby[row][col-1]=='.')))

   {

    //std::cout<<row<<col<<endl;

    col--;

    laby[row][col]=all_letter[letter++];

    break;

      }

  case 3:if(right=((col+1<COL)&&(laby[row][col+1]=='.')))

   {

    //std::cout<<row<<col<<endl;

    col++;

    laby[row][col]=all_letter[letter++];

    break;

      }

  }

  if(!up&&!down&&!left&&!right) //4个方向都堵住了

    break;

  up=down=right=left=true; //4个方向都设置为true

 }

 for(row=0;row<ROW;row++) //输出数组的值

 {

  for(col=0;col<COL;col++)

   printf("%3c",laby[row][col]);

   cout<<endl;

 }

 int sex1=0,sex0=0;

for(col=0;col<COL;col++) //输出数组的值

 {

  for(row=0;row<ROW;row++)

  {

if((laby[col][row]>='A')&&(laby[col][row]<='L'))

sex1++;

else if(laby[col][row]!='.')

sex0++;

  }

  std::cout<<""<<col<<"排男生人数:"<<sex1<<" "<<"女生人数:"<<sex0<<endl ;

  sex1=0;sex0=0;

 //  printf("%3c",laby[row][col]);

   cout<<endl;

 }

 return 0;

}

【案例分析】

1)本实例用到两个数组laby和all_letter,数据类型都是整型。数组赋值的时候是字符,其原理是赋值给数组的是字符的ASCII码值;数组all_letter的值从位置0开始,也就是从'A'开始往后移动,数组laby[row][col]的下标是随机的。

2)代码中if ((a%num)!=0)使用了if控制结构;(%)取模运算,step=rand()%4取值固定为0123switch(step)取值是4种可能;for和while表示循环。

 

注意:从本实例中可知道数组下标是随机的,即随便移到哪个下标都可以赋值。

案例3-16  内存指令表(数组+开关)

【案例描述】

本实例涉及使用数组元素作为开关,用switch编写统计输入的一串字母中元音字母(a、e、i、o、u)的总个数和每个元音字母出现的次数。当输入#”时结束输入。本例效果如图3-16所示。

【实现过程】

定义一个字符数组c[],定义变量并初始化a=e=i=o=u=sum=0;,分别为a、e、i、o、u和sum出现的次数及它们的总次数,执行一个循环for,遍历数组的每个元素,循环中用开关语句switch(c[i1]),累加指定字符出现的次数,计算总次数,并且输出每个字符出现的次数及总次数。其代码如下:

#include <iostream>

using namespace std;

int main()

{

int a,e,i,o,u,sum;

char c[]="(*paeNumabieros)[0]#";

a=e=i=o=u=sum=0;   //初始化

const int len = sizeof( c ) / sizeof( c[0] );   //数组长度

for (int i1=0;i1<len;i1++)      //循环

{

if(c[i1]=='#')

break;

switch(c[i1])   //累加指定字符出现的次数

{

case 'a': a++;break;

case 'e': e++;break;

case 'i': i++;break;

case 'o': o++;break;

case 'u': u++;break;

default :break;

}

// cout<<"c[i1]="<<c[i1]<<endl;

}

sum=a+e+i+o+u;

cout<<"每个字符出现次数及它们的和:"<<endl;

cout<<"'a'="<<a<<" "<<"'e'="<<e<<" "<<"'i'="<<i<<" "<<"'o'="<<o<<" "<<"'u'="<<u<<" "<<"sum="<<sum<<endl;

system("pause");

return 0;

}

【案例分析】

1step=rand()%4取值固定为04的数,同理,(rand()%26)取值固定为026的数。前面学过选择结构的格式switch (expression) {case constant1:block 1 break;default:default block of instructions}。计算表达式expression的值,并检查它是否与第一个常量constant1相等,如果相等,程序执行常量1后面的语句块block 1,直到碰到关键字break,然后程序跳转到switch选择结构的结尾处。代码中用c[i1]作为表达式。

2)字符数组c[]中存储的是字符。同样,字符数组和其他的数组操作是一样的,它与其他的数组遵循同样的规则,代码中,switch(c[i1])取得下标i1对应的元素值。

 

注意:switch (expression)开关表达式中,expression是一个可变的值,如代码中switch(c[i1])表达式是一个字符的数组。

案例3-17  同学姓名册(字符数组)

【案例描述】

本实例是简单处理学生信息的小程序,功能是输入学生姓名、性别和年龄,定义一个类,并利用类的成员函数依次显示学生信息。本例用到了字符数组,最终的效果如图3-17所示。

 

说明:本例会涉及第9章类的概念。

 

3-17  同学姓名册(字符数组)

【实现过程】

1)定义一个学生信息的数据结构,结构的成员有存储姓名的字符指针namebool类型的性别、整型变量age,以及定义一个指针指向下一个结构的值;定义一个类Student,构造函数Student::Student赋值给类姓名、性别、年龄和人数,析构函数Student::~Student释放类内存空间;定义一个成员函数print()显示输出学生情况。其代码如下:

#include<iostream.h>

#include<string.h>

#include<stdio.h>

struct std //定义一个学生信息结构

{

char* name; //姓名

bool sex; //性别

unsigned int age; //年龄

std* next; //指针为指向下一个

};

class Student //定义一个类

{

public:

Student(char a[][15],bool b[],unsigned int c[],int n);

~Student();

void print(); //输出学生信息

private:

std*num,*head,*p;

int size;

};

//构造函数

Student::Student(char a[][15],bool* b,unsigned int* c,int n)

{

size=n;

head=new std;

head->next=NULL;

num=head;

for(int i=0;i<size;i++)

{

p=new std;

p->name=a[i];

p->sex=*(b+i);

p->age=*(c+i);

p->next=NULL;

num->next=p;

num=p;

}

}

Student::~Student() //析构函数

{

p=head->next;

for(int i=0;i<size;i++)

{

num=p->next;

delete p;

p=num;

}

delete head;

// cout<<"析构函数在这里被自动调用!";

cout<<endl;

}

void Student::print() //输出学生的信息

{

p=head->next;

cout<<"学生情况如下:(1代表男性,0代表女性)"<<endl;

cout<<"姓名"<<"  "<<"性别"<<"  "<<"年龄"<<endl;

for(int i=0;i<size;i++)

{

cout<<p->name<<"    "<<p->sex<<"    "<<p->age<<endl;

p=p->next;

}

}

2)主函数定义3个数组,分别存储姓名二维数组stdn、存储性别bool类型数组stds和存储年龄unsigned int类型的数组stda;输入学生姓名、性别、年龄和人数,定义一个Student属性的类SA,为类赋值,并输入学生情况,之后程序依次显示学生信息。代码如下:

void main()

{

const int N=3; //学生个数

char stdn[N][15]; //姓名

bool stds[N]; //性别

unsigned int stda[N]; //年龄

    int stdsex;

unsigned int stdage;

for(int i=0;i<N;i++) //输入每个学生的数据

{

char* stdname;

        stdname=new char[10];

cout<<"输入学生姓名: NO."<<i+1<<":";

cin>>stdname;

     strcpy(stdn[i],stdname);

        cout<<"输入学生性别: NO."<<i+1<<"(1--male,0--female)"<<":";

cin>>stdsex;

        if(stdsex)

stds[i]=true;

else

stds[i]=false;

cout<<"输入学生年龄: NO."<<i+1<<":";

cin>>stdage;

stda[i]=stdage;

}

    Student SA(stdn,stds,stda,N);

SA.print();

cout<<endl;

getchar();

// SA.Student::~Student();  错误:析构函数不能被显式调用

}

【案例分析】

1)字符串实际上就是一串连续字符的序列,所以也可以用简单的字符数组来定义。代码char stdn[N][15];,存储N个最长15个字符的二维数组,字符串中有效内容的结尾处加一个空字符来表示字符结束,它的常量表示可写为0'\0'

2)构造函数如代码中Student::Student,也就是当且仅当声明一个新的对象,或给该类的一个对象分配内存的时候,这个构造函数将自动被调用。析构函数如代码中Student::~Student完成相反的功能,析构函数不能被显式调用,也就是自动释放内存空间。

 

注意:数组其实只是一个指向被分配的内存块的常量指针,数组自己不能够被赋予任何数值,但可以给数组中的每一个元素赋值。

案例3-18  图书管理系统(字符数组综合)

【案例描述】

本实例涉及第9章类的概念,是一个综合例子,实现图书管理中的增、删、改、查功能。程序也提到了类模板的概念,这些对初学者可能比较难理解,后面会有详细的讲解。本例效果如图3-18所示。

 

3-18  图书管理系统(字符数组综合)

【实现过程】

1)定义图书类CBook,成员有编号、书名和价格,构造函数取得图书的编号、书名和价格,成员函数Display()显示图书;定义一个图书类模板BOOKARRAY,定义图书类模板BOOKARRAY,定义图书管理类CbookManager成员函数有AddBook()DeleteBook()ModifyBook()SearchBook(),实现图书管理中的增、删、改、查功能。代码如下:

#include <iostream>

using namespace std;

#include <vector>

using  namespace std;

#include <string.h>

//图书类

class CBook

{

public:

int     m_ID; //编号

char m_name[200]; //书名

float m_price; //价格

public:

CBook(int _ID,char* _name,float _price = 0.0f);

public:

void Display(); //输出

};

CBook::CBook(int _ID,char* _name,float _price)

{

this->m_ID = _ID;

strcpy(this->m_name,_name);

this->m_price = _price;

}

void CBook::Display()

{

printf("%d\t%s\t%.2f\n",this->m_ID,this->m_name,this->m_price);

}

typedef vector<CBook*> BOOKARRAY; //定义图书类模板

//图书管理类

class CBookManager

{

public:

BOOKARRAY m_bookarray; //图书集合

public:

void AddBook(CBook* book); //增加图书

void DeleteBook(int id); //根据编号删除图书

void ModifyBook(CBook* book); //修改图书

void SearchBook(int id); //根据编号查找

void SearchBook(char* name); //根据书名查找

void SearchBook(float price); //根据价格查找

};

void CBookManager::AddBook(CBook* book) //增加图书

{

this->m_bookarray.push_back(book);

}

void CBookManager::DeleteBook(int id) //根据编号删除图书

{

BOOKARRAY::iterator it = this->m_bookarray.begin();

while (it != this->m_bookarray.end())

{

if((*it)->m_ID == id)

{

this->m_bookarray.erase(it);

return;

}

++it;

}

}

void CBookManager::ModifyBook(CBook* book)  {…//修改图书,代码略}  

void CBookManager::SearchBook(int id)   {…//根据编号查找,代码略}     

void CBookManager::SearchBook(char* name)   {…//根据书名查找,代码略}   

void CBookManager::SearchBook(float price)   {…///根据价格查找,代码略}    

2)主函数演示添加图书、显示所有的图书、按编号删除图书、修改某个编号图书的价格、按书名查找图书。代码如下:

int main()

{

CBookManager bookmanager;

    //添加图书

bookmanager.AddBook(new CBook(1, "真相大白/朱振藩著",52.4f));

    cout <<"显示所有图书:\n";

int len = bookmanager.m_bookarray.size();

cout<<"///////////////////////////\n";

for(int i=0;i<len;i++)

{

bookmanager.m_bookarray[i]->Display();

}

cout<<"///////////////////////////\n";

    cout <<"删除编号为15的图书\n";

    //删除编号为15的图书

bookmanager.DeleteBook(15);

     //修改图书

     cout <<"修改编号为3的价格为50.2f\n";

CBook book(3,"味蕾上的情慾/江映瑤著",50.2f);

bookmanager.ModifyBook(&book);

     cout <<"显示所有图书:\n";

int len2 = bookmanager.m_bookarray.size();

for( i=0;i<len2;i++)

{

bookmanager.m_bookarray[i]->Display();

}

cout<<"///////////////////////////\n";

    //查找图书

    cout <<"查找味蕾上的情慾/江映瑤著\n";

bookmanager.SearchBook("味蕾上的情慾/江映瑤著");

    system("pause");

return 0;

}

【案例分析】

这是一个综合实例,程序用到类和字符数组书名m_nam。m_name[200]存储最多200个字符数据的数组。代码中CBook* book是指向图书类Cbook的指针。

定义类模板,使得一个类可以基于通用类型的成员,而不需要在类生成的时候定义具体的数据类型。如代码中typedef vector<CBook*> BOOKARRAY;,其功能是实现线性表的功能。

 

注意:12章演示了类的实例,本章也演示了类的实例,C++语言中,类的概念非常重要,本实例提到的类模板概念将会在第8章详细介绍。

案例3-19  约瑟问题(把异教徒投入海中排法)

【案例描述】

定义不同的数组可以存储不同的值,再加上一定的算法,就能编程实现不少经典的数学问题。如有个数学问题:15名基督教徒和15名异教徒同乘一条船航行,因航行途中出现危机,领航者为全船覆没,唯一的方法是将全船的一半人投入海中其余人就能幸免。程序演示求把异教徒投入海中的排法。本例效果如图3-19所示。

 

3-19  约瑟问题(把异教徒投入海中排法)

【实现过程】

编程思想是假定把30个人围成一圈;由第一个人起报数,每数至第9人,便把他投入海中,下一个接着从1开始报数,第9人又被投入海中,依此循环,直至剩下15人为止。问题是如何排列使投入海中的人全为异教徒?代码实现如下:

#include <iostream>

using namespace std;

void main()

{

int i,k,m,s,sh,num[30],sea[15],ship[15];

for (i=0;i<30;i++)

num[i]=i+1; //130给每人编号

i=0; //i为每次循环时的计数变量

k=0; //k为按12...9报数时的计数变量

m=0; //m为退出人数

s=0; //存储被投入海者数组的下标

sh=0; //存储在船上的人编号数组的下标

while (m<15)

{

if (num[i]!=0) k++;

if (k==9)

{

sea[s]=num[i];

s++;

num[i]=0;

k=0;

m++;

}

i++;

if (i==30) i=0;

}

for(i=0;i<30;i++) //打印结果

if (num[i]!=0)

{

ship[sh]=num[i];

sh++;

}

 

cout<<"被投入海的序号为:"<<endl;

for(i=0;i<15;i++)

{

    cout<<sea[i]<<"  ";

}

    cout<<endl<<"留在船上的序号为:"<<endl;

    for(i=0;i<15;i++)

{

    cout<<ship[i]<<"  ";

}

cout<<endl;

system("pause");

}

【案例分析】

117世纪法国数学家加斯帕的一本《数学的游戏问题》描述了许多有趣的问题,约瑟问题就是其中一个。

2)输出结果:9 18 27 6 16 26 7 19 30 12 24 8 22 5 23,经过sort排序后输出的结果为:5 6 7 8 9 12 16 18 19 22 23 24 26 27 30,这15个位置就是异教徒的位置了。

案例3-20  数组转置

【案例描述】

数组是连续存储数据的单元,可以对里面的数据进行处理。如存储在数组中的是字库,可以实现字库中数据的转置,从而实现字库旋转的功能。本例是对存储在数组中的值实现行和列转置,效果如图3-20所示。

 

3-20  数组转置

【实现过程】

1)定义两个二维数组array[M][N]、b[N][M],定义函数输入转置前和转置后的数组。代码实现如下:

# include <iomanip.h>

# include <iostream>

# include <iostream.h>

# define M 3

# define N 2

int array[M][N],b[N][M]; //定义两个二维数组

void fun(int array[M][N],int b[N][M])    //输入转置前和转置后的数组

{

int i,j;

for (i=0;i<M;i++) //for循环

for (j=0;j<N;j++)

{

b[j][i]=array[i][j]; //数组转置

}

}

2)主函数for循环输入转置前数组,调用转置函数fun()实现转置功能,打印转置后的数组。代码实现如下:

void main()

{

int i,j;

cout<<"输入数组元素:"<<endl;

for (i=0;i<M;i++)

for (j=0;j<N;j++) //for循环

cin>>array[i][j]; //取得输入数组

cout<<" 数组是:"<<endl;

for (i=0;i<M;i++) //for循环

{

for (j=0;j<N;j++)

cout<<setw(5)<<array[i][j]<<"  ";//打印输入数组

cout<<endl;

}

fun(array,b); //调用转置函数

cout<<"转置后数组是: "<<endl;

    for (i=0;i<N;i++) //for循环

{

for (j=0;j<M;j++)

cout<<setw(5)<<b[i][j]<<"  "; //打印转置数组

cout<<endl;

}

system("pause");

}

【案例分析】

1)代码中用两个for循环输入数值,cin>>array[i][j];是输入数组。

2)函数void fun(int array[M][N],int b[N][M])输入的参数是数组,array是转置前的数组,b[N][M]是转置后的数组。

实例3-21  0-1背包问题 

【案例描述】

N件物品和一个容量为V的背包,假设第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包,可使这些物品的费用总和不超过背包容量,且价值总和最大。本例效果如图3-21所示。

 

3-21  0-1背包问题     

【实现过程】

定义物品数量、背包容量,主函数定义物品权重、物品大小,调用Package()函数用状态转移方程实现。代码实现如下:

#include <iostream>

#include <vector>

using namespace std;

const int MIN=0x80000000;

const int N=3; //物品数量

const int V=5; //背包容量

int f[N+1][V+1];

int Package(int *W,int *C,int N,int V);

void main(int argc,char *argv[])

{

 int W[4]={0,7,5,8}; //物品权重

 int C[4]={0,2,3,4}; //物品大小

 int result=Package(W,C,N,V);

 if(result>0)

 {

  cout<<endl;

  cout<<"the opt value:"<<result<<endl;

  int i=N,j=V;

  while(i)

  {

   if(f[i][j]==(f[i-1][j-C[i]]+W[i]))

   {

    cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<endl; //输出物品权重、物品大小

    j-=C[i];

   }

   i--;

  }

 }

 else

  cout<<"can not find the opt value"<<endl;

 return;

}

int Package(int *W,int *C,int N,int V)

{

 int i,j;

 memset(f,0,sizeof(f)); //初始化为0

 

 for(i=0;i<=N;i++)

 for(j=1;j<=V;j++)     

//此步骤是解决是否恰好满足背包容量

   //若“恰好”满足背包容量,即正好装满背包,则加上此步骤,若不需要“恰好”,则初始化为0

  f[i][j]=MIN;

 for(i=1;i<=N;i++)

   for(j=C[i];j<=V;j++)

   {

    f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);  //状态转移方程

    cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;              //输出结果

   }

  return f[N][V];

}

【案例分析】

背包问题的状态转移方程是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]},这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。

 

注意:f[i][v]有意义的条件是,当且仅当存在一个前i件物品的子集其费用总和为v。所以按照这个方程递推完后,最终的答案并不一定是f[N][V],而是f[N][0..V]的最大值。

3.4  本章练习