软考程序员算法实例.docx
《软考程序员算法实例.docx》由会员分享，可在线阅读，更多相关《软考程序员算法实例.docx（18页珍藏版）》请在冰点文库上搜索。
软考程序员算法实例
软考程序员算法实例：
二叉树的中序输出问题
这个程序的思路是自己输入数字，在输入的同时，已经帮你左右顺序排好了，即左子树的数字比右子树小，是个顺序二叉树，以输入0为结素，而后一中序遍历输出，但不知道为什么，在屏幕上打引的却是左子树最小的数字，而且一直输出，请看下面程序：
#include
#include
typedefstructno
{
intkey;
structno*left,*right;
}node,*PNOD;
voidinster（PNOD*p,intk）
{
PNODppre,pre,temp;
ppre=*p;
printf（“currentnumberppre%d”,ppre->key）;
if（ppre==NULL）
{
ppre=（node*）malloc（sizeof（node））;
ppre->key=k;
ppre->left=NULL;
ppre->right=NULL;
*p=ppre;
return;
}
while（ppre）
{
if（kkey）
{
temp=ppre;
ppre=ppre->left;
printf（“left\n”）;
}
elseif（k==ppre->key）
{
printf（“has…\n”）;
return;
}
elseif（k>ppre->key）
{
temp=ppre;
ppre=ppre->right;
printf（“right\n”）;
}
/*printf（“aaaaaaaaaaaaaaaaaa”）;*/
}
pre=（node*）malloc（sizeof（node））;
pre->key=k;
pre->left=NULL;
pre->right=NULL;
if（temp->key>k）
{
temp->left=pre;
}
else
{
temp->right=pre;
}
}
PNODcreat（）
{
PNODT=NULL;
intk;
printf（“pleaseinputnumber=”）;
scanf（“%d”,&k）;
while（k）
{
inster（&T,k）;
printf（“\nagain=”）;
scanf（“%d”,&k）;
}
returnT;
}
voidfound（PNODt）
{
PNODpp;
pp=t;
while（pp）
{
printf（“pp->key=%dpp->left=%dpp->right=%d”,pp->key,pp->left->key,pp->right->key）;
printf（“\n”）;
found（pp->left）;
printf（“]”,pp->key）;
/*printf（“pp->left=%dandpp=%d”,pp->left,pp）;*/
getchar（）;
found（pp->right）;
}
}
main（）
{
PNODT=NULL;
printf（“***************\n”）;
T=creat（）;
found（T）;
}
软考程序员算法实例：
全排列的递归算法
usingSystem;
namespaceTotalSort
{
/**////
///全排列的递归算法
///
classClass1
{
/**////
///应用程序的主入口点。
///
[STAThread]
staticvoidMain（string[]args）
{
//char[]s="abcdefghijklmnopqrstuvwxyz".ToCharArray（）;
char[]s="abcde".ToCharArray（）;
TotalSort（s,0）;
Console.WriteLine（"\n\n总数：
{0}",resultCount）;
Console.ReadLine（）;
}
staticintresultCount=0;
publicstaticvoidTotalSort（char[]list,intstart）{
intend=list.Length-1;
if（start==end）{
resultCount++;
Console.WriteLine（list）;
}
else{
for（inti=start;i<=end;i++）{
char[]temp=newchar[list.Length];
list.CopyTo（temp,0）;
chartempc=temp[start];
temp[start]=temp[i];
temp[i]=tempc;
TotalSort（temp,start+1）;
}
}
}
}
}
软考程序员算法实例：
C语言中trim的实现
用ATL写了个COM，不支持MFC，所以无法用CString，但支持C编码，遇到字符串（字符数组），想去掉字符串中的空格，C下没有TRIM函数，找又没找到，几行代码自己写吧。
往后大家万一遇到用着也方便。
说明：
1.seps是需要去除的字符数组，可以有几个字符，也可以一个。
这里是空格，最常用的。
2.参数也很简单，第一个是结果数组指针，第二个是原字符数组指针，第三个是需要去掉的字符数组指针。
返回的是结果数组指针。
源代码：
#include“stdafx.h”
#include
#include
charseps[] =“”;
char*trim（char*desc,char*src,char*seps）;
intmain（intargc,char*argv[]）
{
charszResult[1024]=“”;
memset（szResult,0,1024）;
charstrtemp[]=“abcdef”;
printf（“%s
Tokens:
”,strtemp）;
trim（szResult,strtemp,seps）;
printf（“result:
%s（ok!
）
”,szResult）;
return0;
}
char*trim（char*desc,char*src,char*seps）
{
char*token=NULL;
/*Establishstringandgetthefirsttoken:
*/
token=strtok（src,seps）;
while（token!
=NULL）
{
/*Whiletherearetokensin“string”*/
printf（“%s
”,token）;
strcat（desc,token）;
/*Getnexttoken:
*/
token=strtok（NULL,seps）;
}
returndesc;
}
软考程序员算法实例：
快速排序算法
lovethea8585人关注Thea更新：
2011/4/9查看评论（0）
给我发信息免费做试题学习交流
代码：
voidQuickSort（intlow,inthigh,int*array）
{
intpos;
if（low{
pos=SPLIT（low,high,array）;//以array[low]进行划分,pos最为划分点
//前一部分后一部分,反之
QuickSort（low,pos-1,array）;//对划分后的前一部分递归处理
QuickSort（pos+1,high,array）;//对划分后的后一部分递归处理
}
}
intSPLIT（intlow,inthigh,int*array）
{
inttemp=array[low];//用temp来记录划分数
while（low{
while（array[high]>temp&&low寻找小于temp的数
high--;
if（low==high）
break;
else
{
array[low]=array[high];
low++;
}
while（array[low]寻找大于temp的数
low++;
if（low==high）
break;
else
{
array[high]=array[low];
high--;
}
}
array[low]=temp;//最终low=high作为划分点,并将划分数存于array[low]
returnlow;
}
思想：
就是你从数组中任取一个元素p（可随机取,现在以取第一个为例）;
以P作为主元,对数组进行划分,前一部分小于P,后一部分大于p;
最后划分处存储p;
然后分别对划分后的前一部分和后一部分递归调用;
算法平均时间复杂度:
O（nlogn）。
软考程序员算法实例：
C语言二路归并排序
lovethea8585人关注Thea更新：
2011/4/9查看评论（0）
给我发信息免费做试题学习交流
写了个二路归并的归并排序小代码，直接贴上来：
/*
file:
quick.cpp
author:
*/
#include
usingnamespacestd;
voidMerge（inta[],intlow,intmid,inthigh,intb[]）;
voidMSort（inta[],intlow,inthigh,intb[]）;
voidmain（）
{
inta[]={4,5,9,10,51,6,46,36,6,56,67,45,36};
intb[13];
MSort（a,0,12,b）;
for（inti=0;i<13;i++）
cout< cout< for（intj=0;j<13;j++）
cout< cout< }
voidMerge（inta[],intlow,intmid,inthigh,intb[]）
{
inti=low,j=mid+1,k=low;
while（（i<=mid）&&（j<=high））
{
if（a[i]<=a[j]）
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
while（i<=mid）
{
a[k]=a[i];
k++;
i++;
}
while（j<=high）
{
a[k]=a[j];
k++;j++;
}
}
voidMSort（inta[],intlow,inthigh,intb[]）
{
if（low==high）
b[low]=a[low];
else
{
intmid=（low+high）/2;
MSort（a,low,mid,b）;
MSort（a,mid+1,high,b）;
Merge（a,low,mid,high,b）;
}
}
软考程序员算法实例：
朴素字符串匹配算法
lovethea8585人关注Thea更新：
2011/4/9查看评论（0）
给我发信息免费做试题学习交流
作为最原始的字符串匹配算法，它的时间复杂度是O（（n-m+1）m）
#include\"stdio.h\"
//计算字符串的长度
intLength（char*s）
{
intcount=0;
while（*s++!
=\\\0\）
count++;
returncount;
}
//字符串匹配
voidNaiveStringMatching（char*t,char*p）
{
intn=Length（t）;
intm=Length（p）;
if（n {
printf（\"Error:
ThePislongerthanT!
\\n\"）;
return;
}
boolfind=true;
printf（\"ThestringTis%s\\n\",t）;
printf（\"ThestringPis%s\\n\",p）;
for（ints=0;s<=n-m;s++）
{
find=true;
for（inti=0;i {
if（t[s+i]!
=p[i]）
{
find=false;
break;
}
}
if（find）
printf（\"Patternoccurswithshift:
%d\\n\",s+1）;
}
}
intmain（）
{
chart[]=\"abcdebcg\";
charp[]=\"bcdebcg\";
NaiveStringMatching（t,p）;
return0;
}
软考程序员算法实例：
二路归并排序算法
lovethea8585人关注Thea更新：
2011/4/9查看评论（0）
给我发信息免费做试题学习交流
写了个二路归并的归并排序小代码，直接贴上来
/*
file:
quick.cpp
author:
*/
#include
usingnamespacestd;
voidMerge（inta[],intlow,intmid,inthigh,intb[]）;
voidMSort（inta[],intlow,inthigh,intb[]）;
voidmain（）
{
inta[]={4,5,9,10,51,6,46,36,6,56,67,45,36};
intb[13];
MSort（a,0,12,b）;
for（inti=0;i<13;i++）
cout< cout< for（intj=0;j<13;j++）
cout< cout< }
voidMerge（inta[],intlow,intmid,inthigh,intb[]）
{
inti=low,j=mid+1,k=low;
while（（i<=mid）&&（j<=high））
{
if（a[i]<=a[j]）
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
while（i<=mid）
{
a[k]=a[i];
k++;
i++;
}
while（j<=high）
{
a[k]=a[j];
k++;j++;
}
}
voidMSort（inta[],intlow,inthigh,intb[]）
{
if（low==high）
b[low]=a[low];
else
{
intmid=（low+high）/2;
MSort（a,low,mid,b）;
MSort（a,mid+1,high,b）;
Merge（a,low,mid,high,b）;
}
}
软考程序员算法实例：
矩阵求逆算法
/**
*求矩阵A的逆矩阵Ai
*@paramA源矩阵
*@paramAi逆矩阵
*@paramsize矩阵的大小
*@return求解成功返回非零值，失败返回零
*/
intInverseMatrix（double**Ai,double**A,intsize）
{
inti,j;
double*b,*x;
b=（double*）malloc（sizeof（double）*size）;
x=（double*）malloc（sizeof（double）*size）;
for（i=0;i {
memset（b,0,sizeof（double）*size）;
b[i]=1;
if（!
LinearEquation（A,x,b,size））
{
free（b）;
free（x）;
return0;
}
for（j=0;j Ai[j][i]=x[j];
}
free（b）;
free（x）;
return1;
}
升级会员 