題目描述

輸入一系列整數，將其中最大的數挑出，并將剩下的數進行排序。

輸入

輸入第一行包括1個整數N,1<=N〈=1OOO,代表輸入數據的個數。

接下來的一行有N個整數。

輸出

可能有多組測試數據，對于每組數據，

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

下的數進行排序。

第二行將排序的結果輸出。

樣例輸入

41342

樣例輸出

4123

#include<iostream>

usingnamespacestd;

typedefintElemType;

^defineMAX1000〃運行輸入的數據的最大數目

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

數目

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

intmain()

(

ElemTypearray[MAX];

intn;〃數據的數目

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])〃后面的比前面的數據小就進行挪動數據

(

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,實際上最大的數據還是存在的

)

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個職工

時間限制：1Sec內存限制：32MB

提交：45解決：17

題目描述

職工有職工號，姓名，年齡.輸入n個職工的信息，找出3個年齡最小的職工打

印出來。

輸入

輸入第一?行包括1個整數N,k=N<=30,代表輸入數據的個數。

接下來的N行有N個職工的信息：

包括職工號（整數），姓名（字符串，長度不超過10）,年齡（l〈=age<=100）。

輸出

可能有多組測試數據，對于每組數據，

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

關鍵字順序：年齡》工號》姓名，從小到大。

樣例輸入

5501Jack6102Nathon100599Lily79923Lucy15814Mickle65

樣例輸出

501Jack6923Lucy15814Mickle65

#include<I0STREAM>

usingnamespacestd;

constintN=30;

typedefstructWorker

{

intNo;〃職工號

charname[30];〃姓名

intage;〃年齡

Worker()〃無參的構造函數

No=0;

memset(name,30,0);

age=0;

)

//設置參數

voidSet(intpl,char*p2,intp3)

(

No=pl;

strcpy(name,p2);

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

)

}Worker;

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

//針對數據量很大的信息，最好用堆排序

//數據量小的話，用冒泡或者簡單選擇排序就可行了

voidSortByAge(Worker*p,intn);

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

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

〃到處是指針對吧！

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

〃指針很神奇的，學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;〃輸入職工的參數

//設置職工的參數

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

)

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

〃輸出信息

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

Print(pwork,n);

deletepwork;〃釋放申請的內存空間

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);〃兩個職工交換位置

)

++count;〃計數

)

)

voidSwap(Worker*p,Worker*q)

(

charbuf[30];

inttmp;

〃交換姓名

strcpy(buf,p->name);

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

strcpy(q->name,buf);

〃交換職工號

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:矩陣最大值

時間限制：1Sec內存限制：32MB

提交：51解決：24

題目描述

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

總和。

要求把每行總和放入每行最大值的位置，如果有多個最大值，取下標值最小的那

一個作為最大值。

最后將結果矩陣輸出。

輸入

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

數。

接下來的m行每行有n個數，代表矩陣的元素。

輸出

可能有多組測試數據，對于每組數據，輸出按題目要求執行后的矩陣。

樣例輸入

3311111111133323232323

樣例輸出

311311311823272823

#include<iostream>

usingnamespacestd;

typedefintElemType;

constintMAX=10;〃設置矩陣的最大行、列數

constintN=2;〃測試的組數

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

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

intmain()

(

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

(

ElemTypeMatrix[MAX][MAX];

introw,col;

cout<<，zInputtherowandcolofMatrix:z，;

cin>>row>>col;

〃輸入矩陣數據

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標示每行的最大元素位置，默認為第一個

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:遍歷鏈表

時間限制：1Sec內存限制：32MB

提交:88解決：31

題目描述

建立一個升序鏈表并遍歷輸出。

輸入

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

個整數。

輸出

可能有多組測試數據，對于每組數據，

將n個整數建立升序鏈表，之后遍歷鏈表并輸出。

樣例輸入

43579

樣例輸出

3579

#include<iostream>

usingnamespacestd;

typedefintElemType;

typedefstructNode

(

ElemTypedata;

Node*next;

}Node,*List;

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

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

voidRecycling(List&L);〃負責回收內存

intmain()

(

intn;

cout?zzInputN:〃；

cin>>n;

ListL=newNode;

L->next=NULL;

if(L)〃申請內存成功

(

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的后續結點指針

Node*q=L;〃獲取p的前面一個結點的指針

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

(

q=P；〃q指向P

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

)

〃新建結點

Node*s=newNode;

s->data=t;

〃在q的后面插入結點

s->next=q->next;

q->next=s;

)

〃遍歷鏈表數據

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的后續結點指針

while(p)

(

L->next=p->next;

deletep;〃刪除L的所有后續結點

p=L->next;

deleteL;〃刪除頭結點

L=NULL;//L歸為NULL

1195:最長&最短文本

時間限制：1Sec內存限制：32MB

提交：32解決：19

題目描述

輸入多行字符串，請按照原文本中的順序輸出其中最短和最長的字符串，如果最

短和最長的字符串不止一個，請全部輸出。

輸入

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

輸出

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

止一個，請全部輸出。

樣例輸入

helloshesorryhe

樣例輸出

hehellosorry

#include<iostream>

usingnamespacestd;

#defineN1000〃字符串的最大長度

SdefineMAXLINE30〃最多可輸入的字符串

intmain()

(

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

串的長度

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

后位存儲有效位置的數目

charmaxline[MAXLINE+l]={0};〃用于存儲最長字符串在數組中的位置，最后

一位存儲有效位置的數目

〃設定輸入字符串"EOF”時表示輸入結束

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

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

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

(

cin?txt[i];

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

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

++count;

〃整理出最短和最長的字符串在數組中的位置

intmax=txt[0][N];〃最大和最小長度都初始化為第一個字符串的長度

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;〃最短字符串的數目修改為1

)

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

{

〃出現多個最短字符串，插入到后面,minline的最后一位也指示了插入的位

置

miniine[miniine[MAXLINE]]=i;

++minline[MAXLINE];〃最短字符串數目加1

)

〃處理最長的字符串

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

(

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

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

maxiine[MAXLINE]=1;〃最長字符串的數目修改為1

)

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

maxiine[maxiine[MAXLINE]]=i;〃出現多個最長字符串，插入到后面

++maxline[MAXLINE];〃最長字符串數目加1

〃輸出最短的和最長的字符串

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

(

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

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

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

cout〈〈endl<〈”最長的字符串〃<<endl;

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

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

return0;

題目描述

輸入一個四行五列的矩陣，找出每列最大的兩個數。

輸入

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

表一個四行五列的矩陣，矩陣元素全部是整數。

輸出

可能有多組測試數據，對于每組數據，按照樣例輸出的格式將每列最大的兩個數

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

小的那一個。

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

依然小。

樣例輸入

112498-1498812987078970

樣例輸出

12999878988

提示

每個數字后面都要輸出一個空格

#include<iostream>

usingnamespacestd;

constintR0W=4;

constintC0L=5;

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

果放在data中

intmainO

(

intn;

intarray[ROW][COL]；〃存儲矩陣信息

intdata[2][C0L]={0};〃存儲處理結果

〃輸入矩陣的數據

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)〃尋找每一列中的最大的兩個數

(

〃初始化為該列的最下面的兩個數，并與中上下位置對應

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];〃較大或者相同但是小標較小的數放在上面

)

)

題目描述

不借用任何字符串庫函數實現無冗余地接受兩個字符串，然后把它們無冗余的連

接起來。

輸入

每一行包括兩個字符串，長度不超過100。

輸出

可能有多組測試數據，對于每組數據，

不借用任何字符串庫函數實現無冗余地接受兩個字符串，然后把它們無冗余的連

接起來。

輸出連接后的字符串。

樣例輸入

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)

(

〃利用鏈表存儲字符串

cout<<，zInputtwostrings:";

charch;

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

(

do

(

ch=getchar();

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

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();

〃進行字符串連接，將鏈表的首尾相接即完成

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

〃輸出連接后的字符串

Node*q=head[0];

while(q)

(

cout?q->ch;

q=q->next;

)

cout<<endl;

〃清空申請的內存空間

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:找位置

題目描述

對給定的一個字符串，找出有重復的字符，并給出其位置，如：

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

輸入

輸入包括一個由字母和數字組成的字符串，其長度不超過100o

輸出

可能有多組測試數據，對于每組數據，

按照樣例輸出的格式將字符出現的位置標出。

樣例輸入

abcaaAB12abl2

樣例輸出

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

提示

1、下標從o開始。

2、相同的字母在一行表示出其出現過的位置。

#include<iostream>

usingnamespacestd;

constintN=100;

intmain(void)

(

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

位置

charcounter[N]={0};〃記錄每個字符出現的次數

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

intlen;

do//保證輸入的字符串長度不超過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];〃如果出現的是新字母就填入數組

的第一位

++counter[_j];〃計時器加1

array[j][counter;〃記錄字符出現的位置

}

〃輸出信息

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;

題目描述

輸入一系列整數，建立二叉排序數，并進行前序，中序，后序遍歷。

輸入

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

接下來的一行包括n個整數。

輸出

可能有多組測試數據，對于每組數據，將題目所給數據建立一個二叉排序樹，并

對二叉排序樹進行前序、中序和后序遍歷。

每種遍歷結果輸出一行。每行最后一個數據之后有一個空格。

樣例輸入

516598

樣例輸出

165981568958961

提示

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

〃下面的已經足夠對付這個機試題目了，等過幾天我再寫個包含更多功能的二叉

排序樹的程序

〃這里面的遞歸實在太多了，遞歸固然簡單，效率較低啊，不用遞歸的話，就擴

展數據結構了，線索二叉樹不錯

#include<iostream>

usingnamespacestd;

SdefineMAX100〃二叉排序數中的元素最大數目

typedefintElemType;

〃定義二叉排序數的結點結構

typedefstructNode

(

ElemTypedata;

Node*lchild;

Node*rchild;

Node(ElemTypeelem)〃結點帶參構造函數

(

data=elem;

lchild=NULL;

rchild=NULL;

}Node,*BST;

voidCreateBST(BST&bst,ElemTypeelem);〃動態創建二叉排序數

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

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

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

voidRecycling(BST&bst);〃回收二叉樹的內存空間

intmain()

intn;

do

cout?〃InputthenumberofelementsofBinary_Sort_Tree:z/;

cin>>n;

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

〃動態創建二叉排序樹

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

BSTbst=NULL;〃二叉排序樹跟結點初始化為NULL

ElemTypeelem;

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

(

cin>>elem;

CreateBST(bst,elem);

〃先序遍歷二叉排序樹

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

PreOrder(bst);

cout?endl;

〃中序遍歷二又排序樹

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

MidOrder(bst);

cout?endl;

〃后序遍歷二叉排序樹

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

PostOrder(bst);

cout?endl;

return0;

voidCreateBST(BST&bst,ElemTypeelem)

(

if(bst)

(

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

(

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

elsebst->lchild=newNode(elem);

)

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

(

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

elsebst->rchild=newNode(elem);

)

)

〃二叉排序樹的根節點為NULL

elsebst=newNode(elem);〃構造新結點

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)

(

〃采取中序方式回收內存空間

if(bst)

(

Recycling(bst->lchild);

Recycling(bst->rchild);

deletebst;〃釋放根節點的內存空間

)

題目描述

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

非遞歸)

輸入

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

輸出

可能有多組測試數據，對于每組數據，

輸出當樓梯階數是N時的上樓方式個數。

樣例輸入

4

樣例輸出

5

〃這題倒是不涉及到數據結構方面的東西,關鍵是分析問題

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

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

//走兩階的步數i在0-N/2之間,進行排列再求和就可以了

//測試了一下,輸入n=68時,我的機器就罷工了,郁悶!

#include<iostream>

usingnamespacestd;

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

〃這是題目不允許的遞歸，遞歸關系倒是簡單得很

intOtherWay(intn);

intmainO

(

intn;〃階梯的級數

cout?zzInputthenumberofstairs:z，;

cin>>n;

intsum=0;〃總的走法

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

//每多個一步走了兩階，那么所走的步數相對上一次就少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)〃求排列結果

(

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

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;

〃這是題目不允許的遞歸，遞歸關系倒是簡單得很

intOtherWay(intn)

{

if(!n)return0;

elseif(n==l)return1;

elseif(n==2)return2;

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

)

84:二叉樹遍歷

題目描述

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

樹（以指針方式存儲）。

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

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

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

樹進行中序遍歷，輸出遍歷結果。

輸入

輸入包括1行字符串，長度不超過100。

輸出

可能有多組測試數據，對于每組數據，

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

每個輸出結果占一行。

樣例輸入

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

樣例輸出

cbegdfa

〃這個題目讓我機試時寫出來時間肯定不夠啊

//關鍵是當時在解決查找插入點時遇到了回溯問題

//一時沒想到引入棧，又沒找到個遞歸的規律，浪費了不少時間

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

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

#include<iostream>

usingnamespacestd;

constintMAX_LEN=100;//字符串的最大長度

typedefcharElemType;

〃二叉樹的結點結構

typedefstructNode

(

ElemTypedata;

Node*lchild;

Node*rchild;

charflag;〃標示該結點的孩子結點數目

〃結點的構造函數

Node(ElemTypeelem)

(

data=elem;

lchild=NULL;

rchild=NULL;

flag=0;〃不帶任何結點

}Node,*BiTree;

〃由于在查找插入點的過程中有回溯問題，只好引入棧了

typedefstructStack

(

chartop;〃指向棧頂

Node*container[MAX_LEN/2];〃最多也就MAX_LEN/2個節點

Stack()〃默認構造函藪

(

top=0;

)；

〃添加棧的相關操作

//節點入棧

voidPush(Node*&p)

(

container[top++]=p;

}

〃獲取棧頂元素

Node*GetTop()

(

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

returnNULL;

)

〃彈出所有不能再添加子節點的節點，直到遇到了可添加子節點的節點

//那么也就保證了棧頂元素始終是可添加子節點的

voidPop()

(

Node*p=GetTop();

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

(

—top;

p=GetTop();

}Stack;

Stackstack;〃全局的棧輔助查找插入點

〃檢查輸入的字符串是否滿足構造二叉樹的條件

boolCheckString(ElemTypestr[]);

//創建二叉樹

voidCreateBiTree(BiTree&bt,ElemTypeelem);

〃中序遍歷二叉樹

voidMidOrder(constBiTree&bt);

〃回收內存空間

voidRecycling(BiTree&bt);

intmainO

(

ElemTypestr[MAX_LEN];

cout?zzInputthestring:zz<<endl;

cin>>str;

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

(

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;

〃檢查輸入的字符串是否滿足構造二叉樹的條件

boolCheckString(ElemTypestr[])

(

〃實際上，如果算上可以構成一顆滿二叉樹，作為葉子結點的

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

intlen=strlen(str);

intcount=0;〃為'計數

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

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

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

returnfalse;

〃創建二叉樹

voidCreateBiTree(BiTree&bt,ElemTypeelem)

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

(

bt=newNode(elem);〃創建根節點

stack.Push(bt);〃新節點入棧

}

else

(

stack.PopO;〃彈出所有不能插入子節點的節點

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

if(p)〃找到了插入點

(

if(elem!='#')

(

Node*q=newNode(elem);

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

elsep->rchild=q;

stack.Push(q);//新節點入棧

)

++p->flag;

)

)

)

〃中序遍歷二叉樹

voidMidOrder(constBiTree&bt)

{

if(bt)

(

MidOrder(bt->lchiId);

cout<<bt->data<<z，

MidOrder(bt->rchiId);

)

)

〃回收內存空間

voidRecycling(BiTree&bt)

(

if(bt)

Recycling(bt->lchild);

Recycling(bt->rchiId);

deletebt;〃回收根節點的內存空間

)

)

1107:搬水果

時間限制：1Sec內存限制：32MB

提交：123解決：28

題目描述

在一個果園里，小明已經將所有的水果打了下來，并按水果的不同種類分成了若

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

到一起，消耗的體力等于兩堆水果的重量之和。當然經過n-1次合并之后，就

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

假定每個水果重量都為1,并且已知水果的種類數和每種水果的數目，你的任務

是設計出合并的次序方案，使小明耗費的體力最少，并輸出這個最小的體力耗費

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

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

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

輸入

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

數，如果n等于0表示輸入結束，且不用處理。第二行包含n個整數，用空

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

輸出

對于每組輸入，輸出一個整數并換行，這個值也就是最小的體力耗費值。輸入數

據保證這個值小于2~31。

樣例輸入

39120

樣例輸出

15

//先分析問題，運用遞歸思想解析問題

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

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

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

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

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

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

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

x3都小于xl時,H3最小；

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

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

三堆水果

//4.1問題就集中在先合并哪兩堆呢？

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

和越小體力耗費值越小

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

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

//

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

//實際上，這也就是求帶權路徑長度WPL的最小值問題

//當然，如果這題要去建立Huffman_Tree去解決問題就太麻煩了，而且

Huffman_Tree也不是那么好構建的

//問題而答案就是Huffman一Tree中所有非終端節點的值的和，我就用結構體數

組解決問題算了

#include<iostream>

usingnamespacestd;

typedefstructNode

(

intdata;〃節點值

boolflag;〃節點值是否可用來合并的標示

Node()

(

flag=false;〃結點的值初始化為不允許合并

data=0;

)

}Node;

#defineMAX100〃最大的水果種類數目及對應的水果數目的最大值

〃處理數據，計算出體力耗費最小值

intProcess(Nodenum[],intn);

〃打印每次搬運后的水果堆的情況

voidPrint(Nodenum[],intn);

〃尋找最小的兩個節點的位置,放在la和1b內

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

intmain()

(

intn;〃存儲水果種類數目

Nodenum[2*MAX-l];〃存儲每種水果的數目

do

(

cout<<，，Howmanykindsoffruits:";

cin?n;

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

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

{

cin>>num[i].data;

num[i].flag=true;〃輸入數據后允許節點合并

)

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

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

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

return0;

intProcess(Nodenum[],intn)

(

//最后返回所有非終端節點之和就可以了，非終端節點數目比葉子節點數目小

1

if(n>l)

(

intpos=MAX;//pos標示在p數組放置非終端節點的位置

intla,1b;〃指示最小可用節點的位置

for(inti=0;i〈nT;++i)//處理過程經歷n-1次就結束

FindLeast(num,la,lb,n);

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

num[pos].flag=true;//允許節點在下一次合并

num[la].flag=false;//la和lb處節點已經合并就不允許再合并了

num[lb].flag二false;

〃打印合并的節點及結果

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

data<<，z)，，?endl;

++pos;

〃打印合并后的水果堆狀態

cout?z?Statusoffruitspile:/z;

Print(num,n);

)

〃計算體力耗費值，也就是所有的非葉子節點的值之和

intsum=0;

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

sum+=num[i].data;

returnsum;〃返回體力耗費值

)

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

return0;

〃打印每次搬運后的水果堆的情況

voidPrint(Nodenum[],intn)

(

cout?zz(〃；

〃打印葉子節點

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

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

〃打印由上一次合并后的節點信息

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

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

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

cout?zz)z/<<endl;

)

〃尋找最小的兩個節點的位置,放在la和1b內

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

la=lb=-l;

〃在未經過合并的水果堆里尋找最小的

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

(

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

〃使得與經過合并的并且可再次用來合并的水果堆里進行比較

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;

)

)

題目描述

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

各位數字之和。

輸入

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

計算。

輸出

對于每個輸入數據，計算其各位數字之和，以及其平方值的數字之和，輸出在一

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

樣例輸入

41297399990

樣例輸出

473916223936

#include<iostream>

usingnamespacestd;

SdefineMAX40000

//int類型為4字節，足以保存小于1600000000的數

〃計算data的各位數字之和置于suml內，平方后各位數字之和置于sum2內

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;

)

〃計算data的各位數字之和置于suml內，平方后各位數字之和置于sum2內

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

(

suml=sum2=0;

intsquare=data*data;

while(data)

(

suml+二data;

data/=10;

while(square)

sum2+=square;

square/=10;

題目描述

一個二進制數，將其每一位取反，稱之為這個數的反碼。下面我們定義一個字符

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

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

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

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

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

一個字符串的反碼定義為其所有字符的反碼。我們的任務就是計算出給定字符串

的反碼。

輸入

輸入每行都是一個字符串，字符串長度不超過80個字符。如果輸入只有！，表

示輸入結束，不需要處理

輸出

對于輸入的每個字符串，輸出其反碼，每個數據占一行。

樣例輸入

HelloJLU-CCST-2011!

樣例輸出

SvoolQ0F-XXHG-2011

#include<iostream>

usingnamespacestd;

constintMAXLEN=80;

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

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;

〃對字符串進行反碼處理

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?);

題目描述

堆棧是一種基本的數據結構。堆棧具有兩種基本操作方式，push和pop。Push

一個值會將其壓入棧頂，而pop則會將棧頂的值彈出。現在我們就來驗證一下

堆棧的使用。

輸入

對于每組測試數據，第一行是一個正整數n,0<n<=10000（n=0結束）。而后的n

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

著一個整數，表示把這個數據壓入堆棧；如果是'0',表示將棧頂的值pop出

來，如果堆棧中沒有元素時，忽略本次操作；如果是'A',表示詢問當前棧頂的

值，如果當時棧為空，則輸出'E'。堆棧開始為空。

輸出

對于每組測試數據，根據其中的命令字符來處理堆棧；并對所有的'A'操作，輸

出當時棧頂的值，每個占據一行，如果當時棧為空，則輸出'E'。當每組測試數

據完成后，輸出一個空行。

樣例輸入

3AP5A4P3P60A0

樣例輸出

E53

#include<iostream>

usingnamespacestd;

SdefineMAX100〃堆棧的最大容量

〃定義堆棧的數據結構及操作

typedefstructStack

{

int*pdata;

inttop;〃棧頂指示器

Stack()〃默認構造函數

(

top=0;

pdata=newint[MAX];

)

voidPush(intdata)〃入棧操作

*(pdata+top)=data;

++top;

)

intPop()〃出棧操作

(

—top;

return*(pdata+top);

)

intGetTop()〃獲取棧頂數據

(

return*(pdata+top-l);

)

boolStackEmpty()〃判定棧是否為空

(

if(!top)returntrue;

returnfalse;

)

"Stack()〃析構函數

(

top=0;

deletepdata;

pdata=NULL;

)

}Stack;

intmainO

(

intn;〃要進行的操作數目

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；〃非法操作時i必須保持不變

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

break;

)

)

}while(n);

return0;

題目描述

給定一個無向圖和其中的所有邊，判斷這個圖是否所有頂點都是連通的。

輸入

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

表示圖中邊的數目。如果n為0表示輸入結束。隨后有m行數據，每行有兩

個值X和y(0<x,y<=n),表示頂點x和y相連，頂點的編號從1開始計

算。輸入不保證這些邊是否重復。

輸出

對于每組輸入數據，如果所有頂點都是連通的，輸出"YES”,否則輸出"NO"。

樣例輸入

4312233232122300

樣例輸出

NOYES

〃首先，我覺得有必要溫習一下圖的連通性的相關概念

//I無向圖G的連通性：

//若無向圖G中的任何兩個結點都是可達的，則稱G是連通圖(connected

graph),

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

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

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

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