題目描述

輸入一系列整數(shù)，將其中最大的數(shù)挑出，并將剩下的數(shù)進(jìn)行排序。

輸入

輸入第一行包括1個(gè)整數(shù)N,1<=N〈=1OOO,代表輸入數(shù)據(jù)的個(gè)數(shù)。

接下來(lái)的一行有N個(gè)整數(shù)。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

第一行輸出一個(gè)整數(shù)，代表N個(gè)整數(shù)中的最大值，并將此值從數(shù)組中去除，將剩

下的數(shù)進(jìn)行排序。

第二行將排序的結(jié)果輸出。

樣例輸入

41342

樣例輸出

4123

#include<iostream>

usingnamespacestd;

typedefintElemType;

^defineMAX1000〃運(yùn)行輸入的數(shù)據(jù)的最大數(shù)目

voidSpecialSort(ElemType*array,int&num);//進(jìn)行特殊排序，num為數(shù)據(jù)的

數(shù)目

voidPrint(ElemType*array,intnum);〃打印結(jié)果

intmain()

(

ElemTypearray[MAX];

intn;〃數(shù)據(jù)的數(shù)目

do

cout<<z/Inputthenumberofelements//;

cin>>n;

}while(n<l||n>MAX);

cout?z，Input，，?n<<，/elements:zz<<endl;

for(inti=0;i<n;++i)cin?array[i];

SpecialSort(array,n);

Print(array,n);

return0;

)

voidSpecialSort(ElemType*array,int&num)

(

〃直接插入排序

for(inti=l;i<num;++i)

if(array[i"array[iT])〃后面的比前面的數(shù)據(jù)小就進(jìn)行挪動(dòng)數(shù)據(jù)

(

ElemTypetmp=array[i];

for(intj=i-l;j>=0&&array[j]>tmp;-j)

array[j+1]=array[j];

array[j+l]=tmp;

)

-num;//num減1,實(shí)際上最大的數(shù)據(jù)還是存在的

)

voidPrint(ElemType*array,intnum)

(

cout?z，\nMaximumElement:〃<<array[num]<<endl;

cout?zzElementsorderedbydescend:，z?endl;

for(inti=0;i<num;++i)

cout<<array[i]<<z，〃；

cout?endl;

1187:最小年齡的3個(gè)職工

時(shí)間限制：1Sec內(nèi)存限制：32MB

提交：45解決：17

題目描述

職工有職工號(hào)，姓名，年齡.輸入n個(gè)職工的信息，找出3個(gè)年齡最小的職工打

印出來(lái)。

輸入

輸入第一?行包括1個(gè)整數(shù)N,k=N<=30,代表輸入數(shù)據(jù)的個(gè)數(shù)。

接下來(lái)的N行有N個(gè)職工的信息：

包括職工號(hào)（整數(shù)），姓名（字符串，長(zhǎng)度不超過(guò)10）,年齡（l〈=age<=100）。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

輸出結(jié)果行數(shù)為N和3的較小值，分別為年齡最小的職工的信息。

關(guān)鍵字順序：年齡》工號(hào)》姓名，從小到大。

樣例輸入

5501Jack6102Nathon100599Lily79923Lucy15814Mickle65

樣例輸出

501Jack6923Lucy15814Mickle65

#include<I0STREAM>

usingnamespacestd;

constintN=30;

typedefstructWorker

{

intNo;〃職工號(hào)

charname[30];〃姓名

intage;〃年齡

Worker()〃無(wú)參的構(gòu)造函數(shù)

No=0;

memset(name,30,0);

age=0;

)

//設(shè)置參數(shù)

voidSet(intpl,char*p2,intp3)

(

No=pl;

strcpy(name,p2);

age=(p3>0&&p3<=100)?p3:0;

)

}Worker;

〃按照職工的年齡排序，只排出n個(gè)中的最小3個(gè)就停止

//針對(duì)數(shù)據(jù)量很大的信息，最好用堆排序

//數(shù)據(jù)量小的話，用冒泡或者簡(jiǎn)單選擇排序就可行了

voidSortByAge(Worker*p,intn);

voidSwap(Worker*p,Worker*q);〃兩個(gè)職工交換位置

voidPrint(Worker*p,intn);〃輸出年齡最小的3個(gè)職工信息

〃到處是指針對(duì)吧！

〃這就到處程序的可讀性不好了，主要是想練練手

〃指針很神奇的，學(xué)C/C++的話一定要用的得靈活才行

intmain()

(

intn;

do

(

cout<<，，Inputthenumberofworkers(1-30):;

cin>>n;

}while(n<l||n>30);

Worker*pwork=newWorker[30];

intno,age;

charname[30];

cout?z?InputtheNo.,NameandAgeofeachworker/z<<endl;

for(inti=0;i<n;++i)

cin>>no>>name>>age;〃輸入職工的參數(shù)

//設(shè)置職工的參數(shù)

(p\vork+i)->Set(no,name,age);

)

SortByAge(pwork,n);〃處理職工信息

〃輸出信息

cout?//\ntheinfoyouwant:，/?endl;

Print(pwork,n);

deletepwork;〃釋放申請(qǐng)的內(nèi)存空間

return0;

)

voidSortByAge(Worker*p,intn)

(

〃冒泡排序每一趟都可以排出最小或最大的值，我都快用膩了

intcount=0;

for(inti=0;i<n-l&&count<=3;++i)

(

for(intj=n-l;j>ij)

(

if(((p+j)->age)<((p+j-l)->age))

Swap(p+j,p+j-1);〃兩個(gè)職工交換位置

)

++count;〃計(jì)數(shù)

)

)

voidSwap(Worker*p,Worker*q)

(

charbuf[30];

inttmp;

〃交換姓名

strcpy(buf,p->name);

strcpy(p->name,q->name);

strcpy(q->name,buf);

〃交換職工號(hào)

tmp=p->No;

p->No=q->No;

q->No=tmp;

〃交換年齡

p->age+=q-〉age;

q->age=p->age-q->age;

p->age-=q->age;

)

voidPrint(Worker*p,intn)

{

for(inti=0;i<n&&i<3;++i)

cout?(p+i)->No<<z，z/<<(p+i)->name?z/，z?(p+i)->age<<endl;

)

1191:矩陣最大值

時(shí)間限制：1Sec內(nèi)存限制：32MB

提交：51解決：24

題目描述

編寫一個(gè)程序輸入一個(gè)5X6的矩陣存儲(chǔ)并輸出，并且求出每行的最大值和每行的

總和。

要求把每行總和放入每行最大值的位置，如果有多個(gè)最大值，取下標(biāo)值最小的那

一個(gè)作為最大值。

最后將結(jié)果矩陣輸出。

輸入

輸入的第一行包括兩個(gè)整數(shù)m和n(l<=m,n<=100),分別代表矩陣的行和列的維

數(shù)。

接下來(lái)的m行每行有n個(gè)數(shù)，代表矩陣的元素。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，輸出按題目要求執(zhí)行后的矩陣。

樣例輸入

3311111111133323232323

樣例輸出

311311311823272823

#include<iostream>

usingnamespacestd;

typedefintElemType;

constintMAX=10;〃設(shè)置矩陣的最大行、列數(shù)

constintN=2;〃測(cè)試的組數(shù)

voidProcess(ElemTypematrix[][MAX],introw,intcol);〃對(duì)矩陣進(jìn)行處理

voidPrint(ElemTypematrix[][MAX],introw,intcol);〃打印矩陣值

intmain()

(

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

(

ElemTypeMatrix[MAX][MAX];

introw,col;

cout<<，zInputtherowandcolofMatrix:z，;

cin>>row>>col;

〃輸入矩陣數(shù)據(jù)

for(inti=0;i<row;++i)

for(intj=0;j<col;++j)

cin?Matrix[i][j];

Process(Matrix,row,col);

cout<<，，\nTheMatrixafterconverting:/z<<endl;

Print(Matrix,row,col);

)

return0;

)

voidProcess(ElemTypematrix[][MAX],introw,intcol)

(

for(inti=0;i<row;++i)

(

intMAX=0;〃MAX標(biāo)示每行的最大元素位置，默認(rèn)為第一個(gè)

ElemTypesum=0;

for(intj=0;j<col;++j)

(

sum+二matrix[i][j];〃累加求和

if(matrix[i][j]>matrix[i][MAX])MAX=j;

matrix[i][MAX]=sum;〃用sum替換最大值

)

)

voidPrint(ElemTypematrix[][MAX],introw,intcol)

(

for(inti=0;i<row;++i)

(

for(intj=0;j<col;++j)

cout?matrix[i][j]?/?";

cout<<endl;

)

cout?endl;

)

1181:遍歷鏈表

時(shí)間限制：1Sec內(nèi)存限制：32MB

提交:88解決：31

題目描述

建立一個(gè)升序鏈表并遍歷輸出。

輸入

輸入的每個(gè)案例中第一行包括1個(gè)整數(shù)：n(l<=n<=1000),接下來(lái)的一行包括n

個(gè)整數(shù)。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

將n個(gè)整數(shù)建立升序鏈表，之后遍歷鏈表并輸出。

樣例輸入

43579

樣例輸出

3579

#include<iostream>

usingnamespacestd;

typedefintElemType;

typedefstructNode

(

ElemTypedata;

Node*next;

}Node,*List;

voidSortWhenlnput(List&L,ElemTypet);〃邊插入邊排序

voidTraverseList(constList&L);〃遍歷鏈表數(shù)據(jù)

voidRecycling(List&L);〃負(fù)責(zé)回收內(nèi)存

intmain()

(

intn;

cout?zzInputN:〃；

cin>>n;

ListL=newNode;

L->next=NULL;

if(L)〃申請(qǐng)內(nèi)存成功

(

ElemTypedata;

cout<<z，Input，z<<n?zzelementszz<<endl;

for(inti=0;i<n;++i)

{

cin>>data;

SortWhenlnput(L,data);

}

cout<<z，elementsorderedbyascend:，z?endl;

TraverseList(L);

)

else

(

cout<<，，MemoryError!/z<<endl;

exit(EXIT_FAILURE);

return0;

voidSortWhenlnput(List&.L,ElemTypet)

(

Node*p=L-〉next;〃獲得L的后續(xù)結(jié)點(diǎn)指針

Node*q=L;〃獲取p的前面一個(gè)結(jié)點(diǎn)的指針

while(p&&p->data<=t)

(

q=P；〃q指向P

p=p->next;//p后移

)

〃新建結(jié)點(diǎn)

Node*s=newNode;

s->data=t;

〃在q的后面插入結(jié)點(diǎn)

s->next=q->next;

q->next=s;

)

〃遍歷鏈表數(shù)據(jù)

voidTraverseList(constList&L)

{

Node*p=L->next;

while(p)

(

cout<<p->data?/?”;

p=p->next;

)

cout?endl;

)

voidRecycling(List&.L)

(

Node*p=L-〉next;〃獲取L的后續(xù)結(jié)點(diǎn)指針

while(p)

(

L->next=p->next;

deletep;〃刪除L的所有后續(xù)結(jié)點(diǎn)

p=L->next;

deleteL;〃刪除頭結(jié)點(diǎn)

L=NULL;//L歸為NULL

1195:最長(zhǎng)&最短文本

時(shí)間限制：1Sec內(nèi)存限制：32MB

提交：32解決：19

題目描述

輸入多行字符串，請(qǐng)按照原文本中的順序輸出其中最短和最長(zhǎng)的字符串，如果最

短和最長(zhǎng)的字符串不止一個(gè)，請(qǐng)全部輸出。

輸入

輸入包括多行字符串，字符串的長(zhǎng)度len,(l<=len<=1000)o

輸出

按照原文本中的順序輸出其中最短和最長(zhǎng)的字符串，如果最短和最長(zhǎng)的字符串不

止一個(gè)，請(qǐng)全部輸出。

樣例輸入

helloshesorryhe

樣例輸出

hehellosorry

#include<iostream>

usingnamespacestd;

#defineN1000〃字符串的最大長(zhǎng)度

SdefineMAXLINE30〃最多可輸入的字符串

intmain()

(

chartxt[MAXLINE][N+l];〃每行存儲(chǔ)一個(gè)字符串，最后一位用于存儲(chǔ)每個(gè)字符

串的長(zhǎng)度

charminline[MAXLINE+l]={0};〃用于存儲(chǔ)最短的字符串在數(shù)組中的位置，最

后位存儲(chǔ)有效位置的數(shù)目

charmaxline[MAXLINE+l]={0};〃用于存儲(chǔ)最長(zhǎng)字符串在數(shù)組中的位置，最后

一位存儲(chǔ)有效位置的數(shù)目

〃設(shè)定輸入字符串"EOF”時(shí)表示輸入結(jié)束

cout?"請(qǐng)輸入字符串(輸入字符串EOF表示輸入結(jié)束)”《endl;

intcount=0;〃記錄輸入的有效字符串的數(shù)目

for(inti=O;i<MAXLINE;++i)

(

cin?txt[i];

if(!strcmp(txt[i],"EOF"))break;〃輸入結(jié)束

txt[i][N]=strlen(txt[i]);〃把該字符串的長(zhǎng)度放在最后一位

++count;

〃整理出最短和最長(zhǎng)的字符串在數(shù)組中的位置

intmax=txt[0][N];〃最大和最小長(zhǎng)度都初始化為第一個(gè)字符串的長(zhǎng)度

intmin=txt[0][N];

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

(

〃處理最短的字符串

if(min>txt[i][N])

{

min=txt[i][N];〃更新min

minline[0]=i;〃更新最短字符串的位置

minline[MAXLINE]=1;〃最短字符串的數(shù)目修改為1

)

elseif(min==txt[i][N])

{

〃出現(xiàn)多個(gè)最短字符串，插入到后面,minline的最后一位也指示了插入的位

置

miniine[miniine[MAXLINE]]=i;

++minline[MAXLINE];〃最短字符串?dāng)?shù)目加1

)

〃處理最長(zhǎng)的字符串

if(max<txt[i][N])

(

max=txt[i][N];//更新max

maxiine[0]=i;〃更新最長(zhǎng)字符串的位置

maxiine[MAXLINE]=1;〃最長(zhǎng)字符串的數(shù)目修改為1

)

elseif(max==txt[i][N])

maxiine[maxiine[MAXLINE]]=i;〃出現(xiàn)多個(gè)最長(zhǎng)字符串，插入到后面

++maxline[MAXLINE];〃最長(zhǎng)字符串?dāng)?shù)目加1

〃輸出最短的和最長(zhǎng)的字符串

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

(

cout<〈end"〈〃最短的字符串“<Xendl;

for(intj=0;j<minline[MAXLINE];++j)

cout<<txt[miniine[j]]<<endl;

cout〈〈endl<〈”最長(zhǎng)的字符串〃<<endl;

for(j=0;j<maxline[MAXLINE];++j)

cout?txt[maxiine[j]]<<endl;

return0;

題目描述

輸入一個(gè)四行五列的矩陣，找出每列最大的兩個(gè)數(shù)。

輸入

輸入第一行包括一個(gè)整數(shù)n(l<=n<=1000),接下來(lái)的四行每行包括五個(gè)整數(shù)。代

表一個(gè)四行五列的矩陣，矩陣元素全部是整數(shù)。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，按照樣例輸出的格式將每列最大的兩個(gè)數(shù)

輸出，如果最大的兩個(gè)數(shù)中的一個(gè)數(shù)在這一列中有多個(gè)相同的值，則行值取行值

小的那一個(gè)。

輸出時(shí)要保留原矩陣的行列順序，即在原矩陣中行值小的，在輸出矩陣中的行值

依然小。

樣例輸入

112498-1498812987078970

樣例輸出

12999878988

提示

每個(gè)數(shù)字后面都要輸出一個(gè)空格

#include<iostream>

usingnamespacestd;

constintR0W=4;

constintC0L=5;

voidProcess(constintarray[ROW][COL],intdata[2][COL]);〃將處理的結(jié)

果放在data中

intmainO

(

intn;

intarray[ROW][COL]；〃存儲(chǔ)矩陣信息

intdata[2][C0L]={0};〃存儲(chǔ)處理結(jié)果

〃輸入矩陣的數(shù)據(jù)

cout?，zInputthenumberofarray(，，?ROW<<，/*，/<<COL<<z，):/z;

cin>>n;

for(inti=0;i<n;++i)

(

for(intj=0;j<ROW;++j)

for(intk=O;k<COL;++k)

cin?array[j][k];

Process(array,data);

cout<<，zTheResult:，z?endl;

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

(

for(intk=O;k<COL;++k)

cout?data[j][k]?z，，z;

cout?endl;

)

)

return0;

)

voidProcess(constintarray[ROW][COL],intdata[2][COL])

(

for(inti=0;i〈COL;++i)〃尋找每一列中的最大的兩個(gè)數(shù)

(

〃初始化為該列的最下面的兩個(gè)數(shù)，并與中上下位置對(duì)應(yīng)

data[0][i]=array[ROW-2][i];

data[l][i]=array[ROW-1][i];

for(intj=ROW-3;j>=0;-j)

(

if(array[j][i]>=data[0][i]||array[j][i]>=data[l][i])

(

if(data[0][i]>=data[l][i])data[l][i]=data[0][i];〃將上面的值往下

挪

data[0][i]=array[j][i];〃較大或者相同但是小標(biāo)較小的數(shù)放在上面

)

)

題目描述

不借用任何字符串庫(kù)函數(shù)實(shí)現(xiàn)無(wú)冗余地接受兩個(gè)字符串，然后把它們無(wú)冗余的連

接起來(lái)。

輸入

每一行包括兩個(gè)字符串，長(zhǎng)度不超過(guò)100。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

不借用任何字符串庫(kù)函數(shù)實(shí)現(xiàn)無(wú)冗余地接受兩個(gè)字符串，然后把它們無(wú)冗余的連

接起來(lái)。

輸出連接后的字符串。

樣例輸入

abcdef

樣例輸出

abcdef

#include<iostream>

usingnamespacestd;

constintN=3;

typedefstructNode

(

charch;

Node*next;

);

intmain()

(

structNode*head[2]={0};

structNode*tail[2]={0};

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

(

〃利用鏈表存儲(chǔ)字符串

cout<<，zInputtwostrings:";

charch;

for(inti=0;i<2;++i)

(

do

(

ch=getchar();

}while(ch='')；〃過(guò)濾掉每個(gè)字符串最前面的所有空格符

while(ch!=，\n&&ch!=，')

(

Node*p=newNode;

if(!p)

(

cout?z/Erroroccuredwhenallocatingmemory!/z<<endl;

exit(0);

p->ch=ch;

p->next=NULL;

if(tail[i])tail[i]->next=p;

elsehead[i]=tai1[i]=p;

tail[i]=p;

ch=getchar();

〃進(jìn)行字符串連接，將鏈表的首尾相接即完成

tail[0]->next=head[l];

〃輸出連接后的字符串

Node*q=head[0];

while(q)

(

cout?q->ch;

q=q->next;

)

cout<<endl;

〃清空申請(qǐng)的內(nèi)存空間

q=head[0];

while(q)

(

head[O]=q->next;

deleteq;

q=head[0];

)

head[O]=head[1]=NULL;

tail[O]=tail[l]=NULL;

cout<<endl;

)

return0;

1199:找位置

題目描述

對(duì)給定的一個(gè)字符串，找出有重復(fù)的字符，并給出其位置，如：

輸出：a,1；a,4；a,5；a,10,b,2；b,11,1,8；1,12,2,9；2,130

輸入

輸入包括一個(gè)由字母和數(shù)字組成的字符串，其長(zhǎng)度不超過(guò)100o

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

按照樣例輸出的格式將字符出現(xiàn)的位置標(biāo)出。

樣例輸入

abcaaAB12abl2

樣例輸出

a:0,a:3,a:4,a:9b:1,b:10c:2A:5B:61:7,1:112:8,2:12

提示

1、下標(biāo)從o開(kāi)始。

2、相同的字母在一行表示出其出現(xiàn)過(guò)的位置。

#include<iostream>

usingnamespacestd;

constintN=100;

intmain(void)

(

chararray[N][N+l]={0};〃每一行的第一位存儲(chǔ)字符，后面的空間存儲(chǔ)出現(xiàn)的

位置

charcounter[N]={0};〃記錄每個(gè)字符出現(xiàn)的次數(shù)

charstr[N];〃用于存儲(chǔ)輸入的字符串

intlen;

do//保證輸入的字符串長(zhǎng)度不超過(guò)100

(

cout<<z，Inputthestring:/z<<endl;

cin?str;

len=strlen(str);

}while(len>100);

chari,j;

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

(

j=0;

while(array[j][0]&&array[j][0]!=str[i])++j;

if(!array[j][0])array[j][0]=str[i];〃如果出現(xiàn)的是新字母就填入數(shù)組

的第一位

++counter[_j];〃計(jì)時(shí)器加1

array[j][counter;〃記錄字符出現(xiàn)的位置

}

〃輸出信息

for(i=0;array[i][0];++i)

(

for(j=l;j<counter[i];++j)

cout<<array[i][0]?//：//<<int(array[i][j])?';";

cout?array[i][0"<"："<<int(array[i][j])?endl;

}

return0;

題目描述

輸入一系列整數(shù)，建立二叉排序數(shù)，并進(jìn)行前序，中序，后序遍歷。

輸入

輸入第一行包括一個(gè)整數(shù)n(l<=n<=100)o

接下來(lái)的一行包括n個(gè)整數(shù)。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，將題目所給數(shù)據(jù)建立一個(gè)二叉排序樹(shù)，并

對(duì)二叉排序樹(shù)進(jìn)行前序、中序和后序遍歷。

每種遍歷結(jié)果輸出一行。每行最后一個(gè)數(shù)據(jù)之后有一個(gè)空格。

樣例輸入

516598

樣例輸出

165981568958961

提示

輸入中可能有重復(fù)元素，但是輸出的二叉樹(shù)遍歷序列中重復(fù)元素不用輸出。

〃下面的已經(jīng)足夠?qū)Ω哆@個(gè)機(jī)試題目了，等過(guò)幾天我再寫個(gè)包含更多功能的二叉

排序樹(shù)的程序

〃這里面的遞歸實(shí)在太多了，遞歸固然簡(jiǎn)單，效率較低啊，不用遞歸的話，就擴(kuò)

展數(shù)據(jù)結(jié)構(gòu)了，線索二叉樹(shù)不錯(cuò)

#include<iostream>

usingnamespacestd;

SdefineMAX100〃二叉排序數(shù)中的元素最大數(shù)目

typedefintElemType;

〃定義二叉排序數(shù)的結(jié)點(diǎn)結(jié)構(gòu)

typedefstructNode

(

ElemTypedata;

Node*lchild;

Node*rchild;

Node(ElemTypeelem)〃結(jié)點(diǎn)帶參構(gòu)造函數(shù)

(

data=elem;

lchild=NULL;

rchild=NULL;

}Node,*BST;

voidCreateBST(BST&bst,ElemTypeelem);〃動(dòng)態(tài)創(chuàng)建二叉排序數(shù)

voidPreOrder(constBST&bst);〃前序遍歷二叉樹(shù)

voidMidOrder(constBST&bst);〃中序遍歷二叉樹(shù)

voidPostOrder(constBST&bst);〃后序遍歷二叉樹(shù)

voidRecycling(BST&bst);〃回收二叉樹(shù)的內(nèi)存空間

intmain()

intn;

do

cout?〃InputthenumberofelementsofBinary_Sort_Tree:z/;

cin>>n;

}while(n<l||n>MAX);

〃動(dòng)態(tài)創(chuàng)建二叉排序樹(shù)

cout?z，Input，，?n<<，,elementsofBinary_Sort_Tree:z/<<endl;

BSTbst=NULL;〃二叉排序樹(shù)跟結(jié)點(diǎn)初始化為NULL

ElemTypeelem;

for(inti=0;i<n;++i)

(

cin>>elem;

CreateBST(bst,elem);

〃先序遍歷二叉排序樹(shù)

cout?z，\nPreOrderBinary_Sort_Tree:z，?endl;

PreOrder(bst);

cout?endl;

〃中序遍歷二又排序樹(shù)

cout?/z\nMidOrderBinary_Sort_Tree:，，?endl;

MidOrder(bst);

cout?endl;

〃后序遍歷二叉排序樹(shù)

cout?z，\nPostOrderBinary_Sort_Tree:z，<<endl;

PostOrder(bst);

cout?endl;

return0;

voidCreateBST(BST&bst,ElemTypeelem)

(

if(bst)

(

if(elem<bst->data)〃向左子樹(shù)掃瞄

(

if(bst->lchild)CreateBST(bst->lchiId,elem);〃左子樹(shù)不為空

elsebst->lchild=newNode(elem);

)

elseif(elem>bst->data)〃向右子樹(shù)掃描

(

if(bst->rchild)CreateBST(bst->rchild,elem);〃右子樹(shù)不為空

elsebst->rchild=newNode(elem);

)

)

〃二叉排序樹(shù)的根節(jié)點(diǎn)為NULL

elsebst=newNode(elem);〃構(gòu)造新結(jié)點(diǎn)

voidPreOrder(constBST&bst)

(

if(bst)

(

cout<<bst->data?zz

PreOrder(bst->lchiId);

PreOrder(bst->rchiId);

)

)

voidMidOrder(constBST&bst)

{

if(bst)

(

MidOrder(bst->lchiId);

cout<<bst->data?zz〃；

MidOrder(bst->rchiId);

voidPostOrder(constBST&bst)

(

if(bst)

(

PostOrder(bst->lchiId);

PostOrder(bst->rchiId);

cout<<bst->data?，zz，;

)

voidRecycling(BST&bst)

(

〃采取中序方式回收內(nèi)存空間

if(bst)

(

Recycling(bst->lchild);

Recycling(bst->rchild);

deletebst;〃釋放根節(jié)點(diǎn)的內(nèi)存空間

)

題目描述

N階樓梯上樓問(wèn)題：一次可以走兩階或一階，問(wèn)有多少種上樓方式。(要求采用

非遞歸)

輸入

輸入包括一個(gè)整數(shù)N,(l<=N<90)。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

輸出當(dāng)樓梯階數(shù)是N時(shí)的上樓方式個(gè)數(shù)。

樣例輸入

4

樣例輸出

5

〃這題倒是不涉及到數(shù)據(jù)結(jié)構(gòu)方面的東西,關(guān)鍵是分析問(wèn)題

//走兩階是一步，走一階也是一步，前者和后者又不同

//所以只要在所有的步數(shù)中選擇出那兒步是可以一次走兩階的就所求的走法

//走兩階的步數(shù)i在0-N/2之間,進(jìn)行排列再求和就可以了

//測(cè)試了一下,輸入n=68時(shí),我的機(jī)器就罷工了,郁悶!

#include<iostream>

usingnamespacestd;

intCombine(intn,intm);//求排列結(jié)果

〃這是題目不允許的遞歸，遞歸關(guān)系倒是簡(jiǎn)單得很

intOtherWay(intn);

intmainO

(

intn;〃階梯的級(jí)數(shù)

cout?zzInputthenumberofstairs:z，;

cin>>n;

intsum=0;〃總的走法

inttwo=n/2;〃每次走兩階的最大步數(shù)

//每多個(gè)一步走了兩階，那么所走的步數(shù)相對(duì)上一次就少1了

for(inti=0;i<=two;++i)sum十二Combine(n-i,i);

cout?zz\nThenumberofways://<<sum?endl;

〃遞歸方式

cout<</zTheothersolutionnotallowed:/z<<0therWay(n)<<endl;

return0;

intCombine(intn,intm)〃求排列結(jié)果

(

〃按照排列組合的公式求解就可以搞定

if(n<=0)return0;

if(!m)return1;

intp=l;

for(inti=n;i!=n-m;--i)p*=i;

intq=l;

for(intj=l;j!=m+l;++j)q*=j;

returnp/q;

〃這是題目不允許的遞歸，遞歸關(guān)系倒是簡(jiǎn)單得很

intOtherWay(intn)

{

if(!n)return0;

elseif(n==l)return1;

elseif(n==2)return2;

elsereturnOtherWay(n-l)+0therWay(n-2);

)

84:二叉樹(shù)遍歷

題目描述

編一個(gè)程序，讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個(gè)二叉

樹(shù)（以指針?lè)绞酱鎯?chǔ)）。

例如如下的先序遍歷字符串：

ABC##DE#G##F###

其中表示的是空格，空格字符代表空樹(shù)。建立起此二叉樹(shù)以后，再對(duì)二叉

樹(shù)進(jìn)行中序遍歷，輸出遍歷結(jié)果。

輸入

輸入包括1行字符串，長(zhǎng)度不超過(guò)100。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，

輸出將輸入字符串建立二叉樹(shù)后中序遍歷的序列，每個(gè)字符后面都有一個(gè)空格。

每個(gè)輸出結(jié)果占一行。

樣例輸入

abc##de#g##f###

樣例輸出

cbegdfa

〃這個(gè)題目讓我機(jī)試時(shí)寫出來(lái)時(shí)間肯定不夠啊

//關(guān)鍵是當(dāng)時(shí)在解決查找插入點(diǎn)時(shí)遇到了回溯問(wèn)題

//一時(shí)沒(méi)想到引入棧，又沒(méi)找到個(gè)遞歸的規(guī)律，浪費(fèi)了不少時(shí)間

//做過(guò)一次就好了，以后遇到遞歸我就果斷引入棧

//寫完看了下，棧和二叉樹(shù)封裝成類挺合適的

#include<iostream>

usingnamespacestd;

constintMAX_LEN=100;//字符串的最大長(zhǎng)度

typedefcharElemType;

〃二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)

typedefstructNode

(

ElemTypedata;

Node*lchild;

Node*rchild;

charflag;〃標(biāo)示該結(jié)點(diǎn)的孩子結(jié)點(diǎn)數(shù)目

〃結(jié)點(diǎn)的構(gòu)造函數(shù)

Node(ElemTypeelem)

(

data=elem;

lchild=NULL;

rchild=NULL;

flag=0;〃不帶任何結(jié)點(diǎn)

}Node,*BiTree;

〃由于在查找插入點(diǎn)的過(guò)程中有回溯問(wèn)題，只好引入棧了

typedefstructStack

(

chartop;〃指向棧頂

Node*container[MAX_LEN/2];〃最多也就MAX_LEN/2個(gè)節(jié)點(diǎn)

Stack()〃默認(rèn)構(gòu)造函藪

(

top=0;

)；

〃添加棧的相關(guān)操作

//節(jié)點(diǎn)入棧

voidPush(Node*&p)

(

container[top++]=p;

}

〃獲取棧頂元素

Node*GetTop()

(

if(top>0)returncontainer[top-1];

returnNULL;

)

〃彈出所有不能再添加子節(jié)點(diǎn)的節(jié)點(diǎn)，直到遇到了可添加子節(jié)點(diǎn)的節(jié)點(diǎn)

//那么也就保證了棧頂元素始終是可添加子節(jié)點(diǎn)的

voidPop()

(

Node*p=GetTop();

while(top>0&&p->flag>=2)

(

—top;

p=GetTop();

}Stack;

Stackstack;〃全局的棧輔助查找插入點(diǎn)

〃檢查輸入的字符串是否滿足構(gòu)造二叉樹(shù)的條件

boolCheckString(ElemTypestr[]);

//創(chuàng)建二叉樹(shù)

voidCreateBiTree(BiTree&bt,ElemTypeelem);

〃中序遍歷二叉樹(shù)

voidMidOrder(constBiTree&bt);

〃回收內(nèi)存空間

voidRecycling(BiTree&bt);

intmainO

(

ElemTypestr[MAX_LEN];

cout?zzInputthestring:zz<<endl;

cin>>str;

if(CheckString(str))〃字符串通過(guò)檢查

(

BiTreebt=NULL;

intlen=strlen(str);

for(inti=0;i<len;++i)CreateBiTree(bt,strLi]);

cout<<，，\nMidOrdertheBinaryTree:/z?endl;

MidOrder(bt);

cout<<endl;

Recycling(bt);

}

elsecout<<，，Thestringisnotabletoformabinarytree!z，<<endl;

return0;

〃檢查輸入的字符串是否滿足構(gòu)造二叉樹(shù)的條件

boolCheckString(ElemTypestr[])

(

〃實(shí)際上，如果算上可以構(gòu)成一顆滿二叉樹(shù)，作為葉子結(jié)點(diǎn)的

〃所以，比其余的字符數(shù)目多1則滿足要求

intlen=strlen(str);

intcount=0;〃為'計(jì)數(shù)

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

if(str[i]==，#')++count;

if(count+count-len==l)returntrue;〃測(cè)試通過(guò)

returnfalse;

〃創(chuàng)建二叉樹(shù)

voidCreateBiTree(BiTree&bt,ElemTypeelem)

if(!bt&&elem!=，#')

(

bt=newNode(elem);〃創(chuàng)建根節(jié)點(diǎn)

stack.Push(bt);〃新節(jié)點(diǎn)入棧

}

else

(

stack.PopO;〃彈出所有不能插入子節(jié)點(diǎn)的節(jié)點(diǎn)

Node*p=stack.GetTop();〃獲取插入點(diǎn)

if(p)〃找到了插入點(diǎn)

(

if(elem!='#')

(

Node*q=newNode(elem);

if(p->flag==0)p->lchild=q;

elsep->rchild=q;

stack.Push(q);//新節(jié)點(diǎn)入棧

)

++p->flag;

)

)

)

〃中序遍歷二叉樹(shù)

voidMidOrder(constBiTree&bt)

{

if(bt)

(

MidOrder(bt->lchiId);

cout<<bt->data<<z，

MidOrder(bt->rchiId);

)

)

〃回收內(nèi)存空間

voidRecycling(BiTree&bt)

(

if(bt)

Recycling(bt->lchild);

Recycling(bt->rchiId);

deletebt;〃回收根節(jié)點(diǎn)的內(nèi)存空間

)

)

1107:搬水果

時(shí)間限制：1Sec內(nèi)存限制：32MB

提交：123解決：28

題目描述

在一個(gè)果園里，小明已經(jīng)將所有的水果打了下來(lái)，并按水果的不同種類分成了若

干堆，小明決定把所有的水果合成一堆。每一次合并，小明可以把兩堆水果合并

到一起，消耗的體力等于兩堆水果的重量之和。當(dāng)然經(jīng)過(guò)n-1次合并之后，就

變成一堆了。小明在合并水果時(shí)總共消耗的體力等于每次合并所耗體力之和。

假定每個(gè)水果重量都為1,并且已知水果的種類數(shù)和每種水果的數(shù)目，你的任務(wù)

是設(shè)計(jì)出合并的次序方案，使小明耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)

值。例如有3種水果，數(shù)目依次為1,2,90可以先將1,2堆合并，新堆數(shù)

目為3,耗費(fèi)體力為3o然后將新堆與原先的第三堆合并得到新的堆，耗費(fèi)體力

為12。所以小明總共耗費(fèi)體力=3+12=15,可以證明15為最小的體力耗費(fèi)值。

輸入

每組數(shù)據(jù)輸入包括兩行,第一行是一個(gè)整數(shù)n(l<=n<=10000),表示水果的種類

數(shù)，如果n等于0表示輸入結(jié)束，且不用處理。第二行包含n個(gè)整數(shù)，用空

格分隔，第i個(gè)整數(shù)(k=ai<=1000)是第i種水果的數(shù)目。

輸出

對(duì)于每組輸入，輸出一個(gè)整數(shù)并換行，這個(gè)值也就是最小的體力耗費(fèi)值。輸入數(shù)

據(jù)保證這個(gè)值小于2~31。

樣例輸入

39120

樣例輸出

15

//先分析問(wèn)題，運(yùn)用遞歸思想解析問(wèn)題

//1.如果只有一堆水果xl,則不用搬

//2.如果有兩堆水果xl和x2,則只需搬一次,且方法唯一

//3.如果有三堆水果xl、x2和x3,則有三種搬運(yùn)方法：

//3.1若先搬xl和x2,則體力耗費(fèi)值為Hl=2*(xl+x2)+x3;

//3.2若先搬xl和x3,則體力耗費(fèi)值為H2=2*(xl+x3)+x2;

//3.3若先搬x2和x3,則體力耗費(fèi)值為H3=xl+2*(x2+x3);

//3.4很顯然,若xl、x2都小于x3,則Hl最小；xl、x3都小于x2時(shí),H2最小;x2、

x3都小于xl時(shí),H3最小；

//3.5也就是和并三者中的較小的兩堆可是耗費(fèi)體力值最小

〃4.如果有四堆水果xl、x2、x3和x4,則必須先合并其中的兩堆，然后就成了

三堆水果

//4.1問(wèn)題就集中在先合并哪兩堆呢？

//4.2分析3.5的結(jié)論及體力耗費(fèi)值公式，不難推出：三堆中的較小兩堆之

和越小體力耗費(fèi)值越小

//4.3所以,先合并最小的兩堆，然后構(gòu)成第三堆

//5.依次這樣遞推，得出結(jié)論，每次都合并最小的兩堆可是體力耗費(fèi)值最小

//

//延伸：每次都選擇最小的兩個(gè)數(shù)組合，是否讓你想到了huffman_Tree?

//實(shí)際上，這也就是求帶權(quán)路徑長(zhǎng)度WPL的最小值問(wèn)題

//當(dāng)然，如果這題要去建立Huffman_Tree去解決問(wèn)題就太麻煩了，而且

Huffman_Tree也不是那么好構(gòu)建的

//問(wèn)題而答案就是Huffman一Tree中所有非終端節(jié)點(diǎn)的值的和，我就用結(jié)構(gòu)體數(shù)

組解決問(wèn)題算了

#include<iostream>

usingnamespacestd;

typedefstructNode

(

intdata;〃節(jié)點(diǎn)值

boolflag;〃節(jié)點(diǎn)值是否可用來(lái)合并的標(biāo)示

Node()

(

flag=false;〃結(jié)點(diǎn)的值初始化為不允許合并

data=0;

)

}Node;

#defineMAX100〃最大的水果種類數(shù)目及對(duì)應(yīng)的水果數(shù)目的最大值

〃處理數(shù)據(jù)，計(jì)算出體力耗費(fèi)最小值

intProcess(Nodenum[],intn);

〃打印每次搬運(yùn)后的水果堆的情況

voidPrint(Nodenum[],intn);

〃尋找最小的兩個(gè)節(jié)點(diǎn)的位置,放在la和1b內(nèi)

voidFindLeast(Nodenum[],int&la,int&lb,intn);

intmain()

(

intn;〃存儲(chǔ)水果種類數(shù)目

Nodenum[2*MAX-l];〃存儲(chǔ)每種水果的數(shù)目

do

(

cout<<，，Howmanykindsoffruits:";

cin?n;

cout<<z，Inputthenumberofeverykindoffruit:z，<<endl;

for(inti=0;i<n;++i)

{

cin>>num[i].data;

num[i].flag=true;〃輸入數(shù)據(jù)后允許節(jié)點(diǎn)合并

)

intresult=Process(num,n);〃獲取體力耗費(fèi)最小值

cout<<，，Theleastphysicalpowertobeconsumed:，，?result?endK<endl;

}while(n>0&&n<=MAX);

return0;

intProcess(Nodenum[],intn)

(

//最后返回所有非終端節(jié)點(diǎn)之和就可以了，非終端節(jié)點(diǎn)數(shù)目比葉子節(jié)點(diǎn)數(shù)目小

1

if(n>l)

(

intpos=MAX;//pos標(biāo)示在p數(shù)組放置非終端節(jié)點(diǎn)的位置

intla,1b;〃指示最小可用節(jié)點(diǎn)的位置

for(inti=0;i〈nT;++i)//處理過(guò)程經(jīng)歷n-1次就結(jié)束

FindLeast(num,la,lb,n);

numtpos].data=num[la].data+num[lb].data;〃水果堆合并

num[pos].flag=true;//允許節(jié)點(diǎn)在下一次合并

num[la].flag=false;//la和lb處節(jié)點(diǎn)已經(jīng)合并就不允許再合并了

num[lb].flag二false;

〃打印合并的節(jié)點(diǎn)及結(jié)果

cout<<z/Merge:(z，<<num[la].data<<，，+，，?num[lb].data?z/一一>z/<<num[pos].

data<<，z)，，?endl;

++pos;

〃打印合并后的水果堆狀態(tài)

cout?z?Statusoffruitspile:/z;

Print(num,n);

)

〃計(jì)算體力耗費(fèi)值，也就是所有的非葉子節(jié)點(diǎn)的值之和

intsum=0;

for(i=MAX;i<MAX+n-l;++i)

sum+=num[i].data;

returnsum;〃返回體力耗費(fèi)值

)

elseif(n==l)returnnum[0].data;

return0;

〃打印每次搬運(yùn)后的水果堆的情況

voidPrint(Nodenum[],intn)

(

cout?zz(〃；

〃打印葉子節(jié)點(diǎn)

for(inti=0;i<n;++i)

if(num[i].flag)cout<<num[i].data<<z，,

〃打印由上一次合并后的節(jié)點(diǎn)信息

for(intj=MAX;j<MAX+n-l;++j)

if(num[j].flag)cout?num[j].data<<〃,

。。成《〃\了;〃去掉最后一個(gè)‘，';

cout?zz)z/<<endl;

)

〃尋找最小的兩個(gè)節(jié)點(diǎn)的位置,放在la和1b內(nèi)

voidFindLeast(Nodenum[],int&la,int&lb,intn)

la=lb=-l;

〃在未經(jīng)過(guò)合并的水果堆里尋找最小的

for(inti=0;i<MAX+n-l;++i)

(

〃之所以加上這一行，是為了在i=n是將i重定向到以MAX為起始點(diǎn)的位置

〃使得與經(jīng)過(guò)合并的并且可再次用來(lái)合并的水果堆里進(jìn)行比較

i=(i==n)?MAX:i;

if(num[i].flag)

(

if(la==-l)la=i;

elseif(lb==-l)lb=i;

else

(

if.data<num[la].datal|num[i].data<num[lb].data)

(num[la].data>num[lb].data?la:lb)=i;

)

)

題目描述

對(duì)于給定的正整數(shù)n,計(jì)算其十進(jìn)制形式下所有位置數(shù)字之和，并計(jì)算其平方的

各位數(shù)字之和。

輸入

每行輸入數(shù)據(jù)包括一個(gè)正整數(shù)n(0<n<40000),如果n=0表示輸入結(jié)束，并不用

計(jì)算。

輸出

對(duì)于每個(gè)輸入數(shù)據(jù)，計(jì)算其各位數(shù)字之和，以及其平方值的數(shù)字之和，輸出在一

行中，之間用一個(gè)空格分隔，但行末不要有空格。

樣例輸入

41297399990

樣例輸出

473916223936

#include<iostream>

usingnamespacestd;

SdefineMAX40000

//int類型為4字節(jié)，足以保存小于1600000000的數(shù)

〃計(jì)算data的各位數(shù)字之和置于suml內(nèi)，平方后各位數(shù)字之和置于sum2內(nèi)

voidProcess(intdata,int&suml,int&sum2);

intmain()

(

intn,suml,sum2;

cout<<，zInputn:〃；

cin>>n;

while(n)

(

if(n>MAX)continue;

Process(n,suml,sum2);

cout<<suml<<z，，z?sum2<<endl;

cout<<z，Inputn:〃；

cin?n;

)

return0;

)

〃計(jì)算data的各位數(shù)字之和置于suml內(nèi)，平方后各位數(shù)字之和置于sum2內(nèi)

voidProcess(intdata,int&suml,int&sum2)

(

suml=sum2=0;

intsquare=data*data;

while(data)

(

suml+二data;

data/=10;

while(square)

sum2+=square;

square/=10;

題目描述

一個(gè)二進(jìn)制數(shù)，將其每一位取反，稱之為這個(gè)數(shù)的反碼。下面我們定義一個(gè)字符

的反碼。如果這是一個(gè)小寫字符，則它和字符'a'的距離與它的反碼和字符'z'

的距離相同；如果是一個(gè)大寫字符，則它和字符'A'的距離與它的反碼和字符

'Z'的距離相同；如果不是上面兩種情況，它的反碼就是它自身。

舉幾個(gè)例子，'a，的反碼是‘z'；'c'的反碼是'x'；'曠的反碼是‘D'；'『

的反碼還是‘1'；'$'的反碼還是

一個(gè)字符串的反碼定義為其所有字符的反碼。我們的任務(wù)就是計(jì)算出給定字符串

的反碼。

輸入

輸入每行都是一個(gè)字符串，字符串長(zhǎng)度不超過(guò)80個(gè)字符。如果輸入只有！，表

示輸入結(jié)束，不需要處理

輸出

對(duì)于輸入的每個(gè)字符串，輸出其反碼，每個(gè)數(shù)據(jù)占一行。

樣例輸入

HelloJLU-CCST-2011!

樣例輸出

SvoolQ0F-XXHG-2011

#include<iostream>

usingnamespacestd;

constintMAXLEN=80;

voidReverse(char*str);〃對(duì)字符串進(jìn)行反碼處理

intmain()

(

charstr[MAX_LEN];

cout<<zzInputastring:";

cin>>str;

while(str[0]!=’!')

(

Reverse(str);

cout<<z，stringreversed:zz;

cout<<str?endl;

cout<<，，Inputastring:";

cin?str;

)

return0;

〃對(duì)字符串進(jìn)行反碼處理

voidReverse(char*str)

(

for(chari=0;str[i];++i)

(

if(str[i]>=，a'&&str[i]<=，z')

str[i]=，z'a');

elseif(str[i]>=，AJ&&str[i]<=，Z')

str[i]-Z'-(str[i]~，A?);

題目描述

堆棧是一種基本的數(shù)據(jù)結(jié)構(gòu)。堆棧具有兩種基本操作方式，push和pop。Push

一個(gè)值會(huì)將其壓入棧頂，而pop則會(huì)將棧頂?shù)闹祻棾觥，F(xiàn)在我們就來(lái)驗(yàn)證一下

堆棧的使用。

輸入

對(duì)于每組測(cè)試數(shù)據(jù)，第一行是一個(gè)正整數(shù)n,0<n<=10000（n=0結(jié)束）。而后的n

行，每行的第一個(gè)字符可能是'P'或者'0'或者'A'；如果是'P’,后面還會(huì)跟

著一個(gè)整數(shù)，表示把這個(gè)數(shù)據(jù)壓入堆棧；如果是'0',表示將棧頂?shù)闹祊op出

來(lái)，如果堆棧中沒(méi)有元素時(shí)，忽略本次操作；如果是'A',表示詢問(wèn)當(dāng)前棧頂?shù)?/p>

值，如果當(dāng)時(shí)棧為空，則輸出'E'。堆棧開(kāi)始為空。

輸出

對(duì)于每組測(cè)試數(shù)據(jù)，根據(jù)其中的命令字符來(lái)處理堆棧；并對(duì)所有的'A'操作，輸

出當(dāng)時(shí)棧頂?shù)闹担總€(gè)占據(jù)一行，如果當(dāng)時(shí)棧為空，則輸出'E'。當(dāng)每組測(cè)試數(shù)

據(jù)完成后，輸出一個(gè)空行。

樣例輸入

3AP5A4P3P60A0

樣例輸出

E53

#include<iostream>

usingnamespacestd;

SdefineMAX100〃堆棧的最大容量

〃定義堆棧的數(shù)據(jù)結(jié)構(gòu)及操作

typedefstructStack

{

int*pdata;

inttop;〃棧頂指示器

Stack()〃默認(rèn)構(gòu)造函數(shù)

(

top=0;

pdata=newint[MAX];

)

voidPush(intdata)〃入棧操作

*(pdata+top)=data;

++top;

)

intPop()〃出棧操作

(

—top;

return*(pdata+top);

)

intGetTop()〃獲取棧頂數(shù)據(jù)

(

return*(pdata+top-l);

)

boolStackEmpty()〃判定棧是否為空

(

if(!top)returntrue;

returnfalse;

)

"Stack()〃析構(gòu)函數(shù)

(

top=0;

deletepdata;

pdata=NULL;

)

}Stack;

intmainO

(

intn;〃要進(jìn)行的操作數(shù)目

do

cout<<zzInputn:";

cin?n;

charch;

intdata;

for(chari=0;i<n;++i)

(

〃之所以把stack放在這，是保證其作用域在輸入的n的范圍下有效，以免

下次輸入n用的還是上次的棧

Stackstack;

cin>>ch;

switch(ch)

{

case'A':

if(stack.StackEmpty())cout〈〈〃E〃；

elsecout?stack.GetTop()?endl;

cout<</，---Operationisover---zz<<endl;

break;

case'P':

cin>>data;

stack.Push(data);

cout<</，---Operationisover—〃<<endl;

break;

case'O':

if(!stack.StackEmpty())stack.Pop();

cout<<，z---Operationisover---，z<<endl;

break;

default:

一i；〃非法操作時(shí)i必須保持不變

cout<<，z--IllegalOpration---/z<<endl;

break;

)

)

}while(n);

return0;

題目描述

給定一個(gè)無(wú)向圖和其中的所有邊，判斷這個(gè)圖是否所有頂點(diǎn)都是連通的。

輸入

每組數(shù)據(jù)的第一行是兩個(gè)整數(shù)n和m(0<=n<=1000)on表示圖的頂點(diǎn)數(shù)目，m

表示圖中邊的數(shù)目。如果n為0表示輸入結(jié)束。隨后有m行數(shù)據(jù)，每行有兩

個(gè)值X和y(0<x,y<=n),表示頂點(diǎn)x和y相連，頂點(diǎn)的編號(hào)從1開(kāi)始計(jì)

算。輸入不保證這些邊是否重復(fù)。

輸出

對(duì)于每組輸入數(shù)據(jù)，如果所有頂點(diǎn)都是連通的，輸出"YES”,否則輸出"NO"。

樣例輸入

4312233232122300

樣例輸出

NOYES

〃首先，我覺(jué)得有必要溫習(xí)一下圖的連通性的相關(guān)概念

//I無(wú)向圖G的連通性：

//若無(wú)向圖G中的任何兩個(gè)結(jié)點(diǎn)都是可達(dá)的，則稱G是連通圖(connected

graph),

//否則稱G是非連通圖(unconnectedgraph)或分離圖(separatedgraph)

//H有向圖G的連通性：

//若將有向圖G所有邊的方向略去，得無(wú)向圖G'

//若G'是連通圖則成G是連通圖或弱連通圖(weaklyconnecte