CC++基础及算法整理Word格式文档下载.docx
《CC++基础及算法整理Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《CC++基础及算法整理Word格式文档下载.docx（32页珍藏版）》请在冰点文库上搜索。
printf（"
%s\n"
str）;
free（str）;
3、Josehpus问题
structjosephus
intcode;
josephus*next;
};
voidmain（）
intnumber;
intinterval;
intstart;
cout<
Pleaseinputthenumberofchildren:
"
;
cin>
>
number;
Pleaseinputtheintervalnumber:
interval;
Pleaseinputthestartnumberofchildren:
start;
josephus*ptrJose=newjosephus[number];
josephus*ptrCurrent=ptrJose;
=number;
ptrCurrent->
next=ptrJose+i%number;
code=i;
ptrCurrent=ptrCurrent->
next;
josephus*pivot;
if（start>
0&
&
start<
=number）
if（start==1）
ptrCurrent=&
ptrJose[number-1];
else
ptrJose[start-2];
else
startnumbererror."
return;
while（ptrCurrent->
next!
=ptrCurrent）
for（inti=0;
pivot=ptrCurrent;
ptrCurrent=ptrCurrent->
No."
setw（4）<
ptrCurrent->
code<
iseliminated."
pivot->
next=ptrCurrent->
ptrCurrent=pivot;
thewinneris"
delete[]ptrJose;
4、快速排序
intdata[9]={54,38,96,23,15,72,60,45,83};
voidquick_sort（intdata[],intlow,inthigh）
inti,j,pivot;
if（low<
high）
pivot=data[low];
i=low;
j=high;
while（i<
j）
while（i<
j&
data[j]>
=pivot）
j--;
if（i<
data[i++]=data[j];
//½
«
±
È
Ê
à
Ö
á
¼
Ç
Â
Ð
¡
µ
Ä
Ò
Æ
½
Í
¶
Ë
data[i]<
i++;
j）
data[j--]=data[i];
´
ó
¸
ß
data[i]=pivot;
//Ê
×
î
Õ
Î
»
Ã
quick_sort（data,low,i-1）;
quick_sort（data,i+1,high）;
quick_sort（data,0,8）;
8;
data[i]<
下面是对这段程序的分析:
“pivot=data[low];
”表示将最低端即第一个元素作为枢轴记录，暂存到pivot中去，“while（i<
j）”表示当高低指针相遇时循环终止，否则继续。
“while（i<
=pivot）j--;
”表示从高端（即数组后面）开始搜索，直到搜索到一个比枢轴值小的某个元素，条件“data[j]>
=pivot”用的是大于或等于号，可见，在搜索过程中若遇到相等的则跳过并继续搜索，条件“i<
j”不可少，因为在搜索过程中，low与high可能相遇，此“i<
j”跟外层while的条件“i<
j”无关，作用各不相同，外层while的条件“i<
j”是判断在进行从高端向低端搜索一趟、从低端向高端搜索一趟之后高低指针是否相遇，而前者却是在单向的搜索过程中为防止高低指针相遇。
当经过“while（i<
=pivot）j--;
”的搜索之后，搜索到一个比枢轴小的元素，因为在搜索完之后i、j可能相等，若相等，就没有交换的必要，因此紧接下面设置了一个判断“if（i<
j）”，若成立，那么就要将比枢轴记录小的记录移到低端“data[i++]=data[j];
”，这里的“data[i++]”表示先使用了data[i]之后才加1，相当于“data[i]=data[j];
i++;
”两句的效果。
为什么要i++？
是因为刚交换的记录肯定比枢轴小，那么紧接下面的语句“while（i<
=pivot）”就少了一次不必要的比较（因为：
=pivot必定成立，而i<
j在前面的if语句中已成立，则“i<
=pivot”必成立，若没有i++，while中的““i<
=pivot””在肯定成立的情况下执行了一次），提高了效率。
执行“data[i++]=data[j];
”之后，高端的data[j]覆盖了data[i]的值，第一次覆盖时，覆盖的是data[low]的值，因为最开始时，“pivot=data[low];
”将最低端即第一个元素作为枢轴记录暂存到pivot中去了，所以不必担心，会丢失信息，由于data[j]的值赋给了data[i]，那么data[j]原来的位置j就可以看做一个空白，下一次覆盖时，就将低端的data[i]复制到这个位置。
紧接下来的“while（i<
=pivot）i++;
”是从低端向高端搜索，直到找到一个比枢轴大的元素，先进行判断“if（i<
j）”，若成立，如前所述，执行“data[j--]=data[i];
”就将低端的data[i]复制到上次赋值后空出的j位置。
如此反复，直到外层while的条件不成立，即i==j，即高低指针相遇，表示已经找到了枢轴记录pivot的最终位置i，执行“data[i]=pivot;
”于是，枢轴记录移到最终位置。
接下来的“quick_sort（data,low,i-1）;
quick_sort（data,i+1,high）;
”表示，对被pivot分开的左右子序列进行递归的快速排序。
Char型转换成long型
longmyatol（constchar*src）
longl=0;
constchar*p=src;
while（*p!
='
\0'
）
l=l*10+（int）（*p-'
0'
p++;
returnl;
反转字符串
//Î
ª
'
·
Å
ä
ö
¿
//char*s=src+len-1;
while（len--!
=0）
*d++=*s--;
*d='
char*test="
helloworld!
ReverseStr（test）<
Int型转char型
char*myitoa（intn,char*dest）
boolsign=（n>
0）;
if（!
sign）
n=-n;
do
*（d++）=（char）（n%10+'
）;
while（（n/=10）>
0）;
*（d++）='
-'
char*result=ReverseStr（dest）;
returnresult;
inti=-321;
char*dest=（char*）malloc（20）;
myitoa（i,dest）<
Int型转char*
char*itoh（intn）
char*buff=（char*）malloc（11）;
buff[0]='
buff[1]='
x'
buff[10]='
char*temp=buff+2;
temp[i]=（char）（n<
4*i>
28）;
temp[i]=temp[i]>
=0?
temp[i]:
temp[i]+16;
temp[i]=temp[i]<
10?
temp[i]+48:
temp[i]+55;
returnbuff;
inti=120;
itoh（i）<
递归反序输出
voidinverse（char*p）
if（*p=='
inverse（p+1）;
%c"
*p）;
inverse（test）;
求组合数：
求n个数的组合
intN,nom[100];
/*N存放在排列的数的个数，nom存要要排列的数*/
/******************************************************************************/
voidinint（）/*接收输入函数*/
{
inti;
pleaseinputthenumbern="
scanf（"
%d"
&
N）;
pleaseinput%dnumbers:
\n"
N）;
for（i=0;
N;
i++）
scanf（"
nom[i]）;
}
voidswap（int*a,int*b）/*交换函数*/
inttemp;
temp=*a;
*a=*b;
*b=temp;
voidprint（）/*打印输出函数*/
%d"
nom[i]）;
\n"
/*******************************************************************/
intsort（intk）/*回溯函数*/
if（k==N）
{
print（）;
return（0）;
}
for（i=k;
swap（&
nom[i],&
nom[k]）;
sort（k+1）;
voidmain（）/*主函数*/
inint（）;
sort（0）;
测试
pleaseinputthenumbern=3
pleaseinput3numbers:
1
3
5
135
153
315
351
531
513
求n个数（1…n）中k个数的组合
#defineMAXN100
inta[MAXN];
voidcomb（intm,intk）
inti,j;
for（i=m;
i>
=k;
i--）
a[k]=i;
if（k>
1）
comb（i-1,k-1）;
else
{
for（j=a[0];
0;
j--）
printf（"
%2d"
a[j]）;
printf（"
}
voidmain（）
intn,m;
pleaseinputtwonumber:
&
n）;
m）;
a[0]=m;
combinationresult:
comb（n,m）;
543
542
541
532
531
521
432
431
421
321
题目：
输入一个链表的头结点，从尾到头反过来输出每个结点的值。
链表结点定义如下：
structListNode
int
m_nKey;
ListNode*m_pNext;
分析：
这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。
看到这道题后，第一反应是从头到尾输出比较简单。
于是很自然地想到把链表中链接结点的指针反转过来，改变链表的方向。
然后就可以从头到尾输出了。
反转链表的算法详见本人面试题精选系列的第19题，在此不再细述。
但该方法需要额外的操作，应该还有更好的方法。
接下来的想法是从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。
当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。
该方法需要维护一个额外的栈，实现起来比较麻烦。
既然想到了栈来实现这个函数，而递归本质上就是一个栈结构。
于是很自然的又想到了用递归来实现。
要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。
基于这样的思路，不难写出如下代码：
///////////////////////////////////////////////////////////////////////
//Printalistfromendtobeginning
//Input:
pListHead-theheadoflist
voidPrintListReversely（ListNode*pListHead）
if（pListHead!
=NULL）
//Printthenextnodefirst
if（pListHead->
m_pNext!
PrintListReversely（pListHead->
m_pNext）;
//Printthisnode
pListHead->
m_nKey）;
//测试代码
structNode
intdata;
Node*next;
voidPrintLinkNode（Node*head）
if（head!
if（head->
next!
PrintLinkNode（head->
next）;
printf（"
%d\n"
head->
data）;
Node*node=newNode[10];
Node*p=node;
10;
p->
next=node+i;
data=i;
p=p->
p->
data=10;
next=NULL;
p=node;
while（p!
data<
PrintLinkNode（node）;
扩展：
该题还有两个常见的变体：
1.
从尾到头输出一个字符串；
voidPrintString（char*src）
char*p=src;
if（p!
if（*（++p）!
PrintString（++src）;
*（--p））;
PrintString（test）;
2.
定义一个函数求字符串的长度，要求该函数体内不能声明任何变量。
//不知道符不符合要求
intStringLength（char*src）
if（src==NULL）
return0;
if（*src=='
if（*src!
returnStringLength（++src）+1;
StringLength（test）<
1.用宏定义写出swap（x，y）
#defineswap（x,y）\
x=x+y;
\
y=x-y;
x=x-y;
3一语句实现x是否为2的若干次幂的判断
inti=512;
cout<
boolalpha<
（（i&
（i-1））?
false:
true）<
endl;
4.unsignedintintvert（unsignedintx,intp,intn）实现对x的进行转换,p为起始转化位,n为需要转换的长度,假设起始点在右边.如x=0b00010001,p=4,n=3转换后x=0b01100001
unsignedintintvert（unsignedintx,intp,intn）{
unsignedint_t=0;
unsignedint_a=1;
for（inti=0;
i<
n;
++i）{
_t|=_a;
_a=_a<
1;
_t=_t<
p;
x^=_t;
returnx;
2、如图：
78910
61211
54312
升级会员 