2016C++程序实例

请严格按照《复习大纲》逐条复习，本《答疑》为疑问较多内容及不同算法描述，望大家认真阅读。其中未提到但大纲中有的内容，请自行在教案中查找复习，例如：求和运算、折半查找、求素数、因子、偶数拆分成两素数和、枚举类问题等等。

一、排序：选择、冒泡、插入；升序、降序；a[0]、a[1]开始存数；（见教案） 设有const int N=10;

int a[N],*p,*q,t;

选择法排序：

for(p=a;p

for(q=p+1;q

if(*p>*q)

{ t=*p;*p=*q;*q=t;}

指针移动 P指针实现i的作用 q指针实现j的作用 指针移动 P指针实现i的作用 q指针实现j的作用 起泡法排序：

for(p=a;p

for(i=0;i< N-1;i++) 或

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

插入法排序：方法一： for(i=1;i

for(j=i-1;j>=0&&t

1

for(q=0;q

if(*q>*(q+1))

{ t=*q;*q=*(q+1);*(q+1)=t;}

for(j=0;j

if(*(p+j)>*(p+j+1))

{ t=*(p+j); *(p+j)=*(p+j+1); *(p+j+1)=t;}

指针不动，使用下标 *(p+i)相当于a[i] 8 for(j=0;j

if(p[j]> p[j+1])

{ t=p[j]; p[j]= p[j+1]; p[j+1]=t;} 指针不动，使用指针p替代数组名a p[i]相当于a[i] a[j+1]=a[j]; a[j+1]=t;} 补充方法二： for(i=1;i

for(j=i-1;j>=0;j--) if(a[b] }

分析：假设已知输入数列：3 2 1 7 0 第一轮i=1,i<5为真 {b=1,j=0,

{ j>=0为真,if(a[1]=0为假，退出内层循环}}，此时数列：2 3 1 7 0 做i++，即i=2。 第二轮i=2,i<5为真 {b=2,j=1,

{j>=0为真,if(a[2]=0为真，if(a[1]

此时数列：1 2 3 7 0

再做j--,即j=-1,则j>=0为假，退出内层循环}} 做i++，即i=3。 第三轮i=3,i<5为真， {b=3,j=2,

{j>=0为真,if(a[3]=0为真，

if(a[3]=0为真，

if(a[3]=0为假，退出内层循环。}}

做i++，即i=4，此时数列：1 2 3 7 0 第四轮i=4,i<5为真，

{b=4,j=3,

{j>=0为真,if(a[4]=0为真，if(a[3]

此时数列：1 2 0 3 7

再做j--,即j=1,则j>=0为真，if(a[2]

此时数列：1 0 2 3 7

再做j--,即j=0,则j>=0为真，if(a[1]

2

将数据分区：已排区、未排区 已排区：假定第一个已排好，第一轮结束已排区为2个数…… 每轮用未排区第一个数在已排区从后向前比较、交换、直到排好 例：已知数据 3 2 1 7 0，假设已排好第一个数3 第一轮：2 3 1 7 0 第二轮：1 2 3 7 0 第三轮：1 2 3 7 0 第四轮：0 1 2 3 7 此时数列：0 1 2 3 7

再做j--,即j=-1,则j>=0为假，退出内层循环}} 做i++，即i=5，i<5为假，退出外层循环

二、删除数据：实验7-3（不采用另外的数组，直接在原数组输出）

i=n-1;

while(i>=0)

{if(a[i]

while(j

教材P95/例4-11

#include #include

using namespace std; void main() {int i,j,c=0;

string a=\”; char b='t';

注意string型变量在使用时经常如字符for(i=0;i< a.size();i++) 型数组的操作，如此题：a[0]=’W’、if(a[i]==b)

a[1]=’h’、a[2]=’a’…… { c++; for(j=i;j< a.size();j++) a[j]=a[j+1]; //删除字符的作用 i--;} cout<

}

#include using namespace std;

a[0]~a[pos-1]为没有重复数的数列； void main( )

例：数据：2 3 2 7 2 3 8 1 3 2 { int a[10],i,j,pos=1; 兰为pos-1的位置，黄为操作的数据 cout<<\第一轮i=1：2 3 2 7 2 3 8 1 3 2 for(i=0;i<10;i++) cin>>a[i]; 第二轮i=2：2 3 2 7 2 3 8 1 3 2 第三轮i=3：2 3 7 7 2 3 8 1 3 2 for(i=1;i<10;i++)

第四轮i=4：2 3 7 7 2 3 8 1 3 2 { for(j=0; j

第五轮i=5：2 3 7 7 2 3 8 1 3 2 3 第六轮i=6：2 3 7 8 2 3 8 1 3 2 第七轮i=7：2 3 7 8 1 3 8 1 3 2 第八轮i=8：2 3 7 8 1 3 8 1 3 2 第九轮i=9：2 3 7 8 1 3 8 1 3 2

if(a[i]==a[j]) break;

if(j>=pos) {a[pos]=a[i];pos++;} }//可写成if(j= =pos)

cout<<\for(i=0; i

三、插入数据：

或 for (i=0;x=p;i--) a[i+1]=a[i]; // 向后移动数据 a[p]=x; //或 a[i+1]=x; // 插入数据

四、最大公约数最小公倍数（实验5-2、实验11-2）

注意： 1、第一次a%b是在循环内还是循环外； 2、注意哪个变量存放最大公约数；

五、求交集（教材P124/例5-11）

4