软考程序员算法实例.docx

1、软考程序员算法实例软考程序员算法实例：二叉树的中序输出问题这个程序的思路是自己输入数字，在输入的同时，已经帮你左右顺序排好了，即左子树的数字比右子树小，是个顺序二叉树，以输入0为结素，而后一中序遍历输出，但不知道为什么，在屏幕上打引的却是左子树最小的数字，而且一直输出，请看下面程序：#include #include typedef struct noint key;struct no *left,*right;node,*PNOD;void inster(PNOD *p,int k)PNOD ppre,pre,temp;ppre=*p;printf(“current number ppre

2、% 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(k key)temp=ppre;ppre=ppre-left;printf(“leftn”);else if(k = ppre-key)printf(“has n”);return;else if(k ppre-key)temp=ppre;ppre=ppre-right;printf(“rightn”);/*printf(“aaaaa

3、aaaaaaaaaaaaa”);*/pre=(node *)malloc(sizeof(node);pre-key=k;pre-left=NULL;pre-right=NULL;if(temp-key k)temp-left=pre;elsetemp-right=pre;PNOD creat()PNOD T=NULL;int k;printf(“please input number =”);scanf(“%d”,&k);while(k)inster(&T,k);printf(“nagain =”);scanf(“%d”,&k);return T;void found(PNOD t)PNOD

4、pp;pp=t;while(pp)printf(“pp-key=%d pp-left=%d pp-right=%d”,pp-key,pp-left-key,pp-right-key);printf(“n”);found(pp-left);printf(“”,pp-key);/*printf(“pp-left=%d and pp=%d”,pp-left,pp);*/getchar();found(pp-right);main()PNOD T=NULL;printf(“*n”);T=creat();found(T);软考程序员算法实例：全排列的递归算法using System;namespace

5、TotalSort/*/ / 全排列的递归算法/ class Class1/*/ / 应用程序的主入口点。/ STAThreadstatic void Main(string args)/char s = abcdefghijklmnopqrstuvwxyz.ToCharArray();char s = abcde.ToCharArray();TotalSort(s, 0);Console.WriteLine(nn总数：0, resultCount);Console.ReadLine();static int resultCount = 0;public static void TotalSo

6、rt(char list, int start) int end = list.Length - 1;if (start = end) resultCount+;Console.WriteLine(list);else for (int i = start; i temp&low寻找小于temp的数high-;if(low=high)break;elsearraylow=arrayhigh;low+;while(arraylow寻找大于temp的数low+;if(low=high)break;elsearrayhigh=arraylow;high-;arraylow=temp; /最终low=

7、high作为划分点,并将划分数存于arraylowreturn low;思想：就是你从数组中任取一个元素p(可随机取,现在以取第一个为例);以P作为主元,对数组 进行划分 ,前一部分小于 P,后一部分大于p;最后划分处存储 p;然后分别对划分后的前一部分和后一部分递归调用;算法平均时间复杂度: O(nlogn)。软考程序员算法实例：C语言二路归并排序lovethea 8585人关注 Thea 更新：2011/4/9查看评论(0)给我发信息免费做试题学习交流写了个二路归并的归并排序小代码，直接贴上来：/* file:quick.cpp author: */ #include using name

8、space std; void Merge(int a,int low,int mid,int high,int b); void MSort(int a,int low,int high,int b); void main() int a=4,5,9,10,51,6,46,36,6,56,67,45,36; int b13; MSort(a,0,12,b); for(int i=0;i13;i+) coutbi ; coutendl; for(int j=0;j13;j+) coutaj ; coutendl; void Merge(int a,int low,int mid,int hig

9、h,int b) int i=low,j=mid+1,k=low; while(i=mid)&(j=high) if(ai=aj) bk=ai; i+; else bk=aj; j+; k+; while(i=mid) ak=ai; k+; i+; while(j=high) ak=aj; k+;j+; void MSort(int a,int low,int high,int b) if(low=high) blow=alow; else int mid=(low+high)/2; MSort(a,low,mid,b); MSort(a,mid+1,high,b); Merge(a,low,

10、mid,high,b); 软考程序员算法实例：朴素字符串匹配算法lovethea 8585人关注 Thea 更新：2011/4/9查看评论(0)给我发信息免费做试题学习交流作为最原始的字符串匹配算法，它的时间复杂度是O(n-m+1)m)#include stdio.h/计算字符串的长度int Length(char *s)int count=0;while(*s+!=0)count+;return count;/字符串匹配void NaiveStringMatching(char *t,char *p)int n=Length(t);int m=Length(p);if(nM) printf(

11、Error:The P is longer than T!n);return;bool find=true;printf(The string T is %sn,t);printf(The string P is %sn,p);for(int s=0;s=n-m;s+)find=true;for(int i=0;iM;I+) if(ts+i!=pi)find=false;break;if(find)printf(Pattern occurs with shift:%dn,s+1);int main()char t=abcdebcg;char p=bcdebcg;NaiveStringMatch

12、ing(t,p);return 0;软考程序员算法实例：二路归并排序算法lovethea 8585人关注 Thea 更新：2011/4/9查看评论(0)给我发信息免费做试题学习交流写了个二路归并的归并排序小代码，直接贴上来/*file:quick.cppauthor:*/#includeusing namespace std;void Merge(int a,int low,int mid,int high,int b);void MSort(int a,int low,int high,int b);void main()int a=4,5,9,10,51,6,46,36,6,56,67,4

13、5,36;int b13;MSort(a,0,12,b);for(int i=0;i13;i+)coutbi ;coutendl;for(int j=0;j13;j+)coutaj ;coutendl;void Merge(int a,int low,int mid,int high,int b)int i=low,j=mid+1,k=low;while(i=mid)&(j=high)if(ai=aj)bk=ai;i+;elsebk=aj;j+;k+;while(i=mid)ak=ai;k+;i+;while(j=high)ak=aj;k+;j+;void MSort(int a,int lo

14、w,int high,int b)if(low=high)blow=alow;elseint mid=(low+high)/2;MSort(a,low,mid,b);MSort(a,mid+1,high,b);Merge(a,low,mid,high,b); 软考程序员算法实例：矩阵求逆算法/* 求矩阵A的逆矩阵Ai*param A 源矩阵*param Ai 逆矩阵*param size 矩阵的大小*return 求解成功返回非零值，失败返回零*/int InverseMatrix(double *Ai, double *A, int size)int i, j;double *b, *x;b = (double*)malloc(sizeof(double)*size);x = (double*)malloc(sizeof(double)*size);for (i = 0; i size; i+)memset(b, 0, sizeof(double)*size);bi = 1;if (!LinearEquation(A, x, b, size)free(b);free(x);return 0;for (j = 0; j size; j+)Aiji = xj;free(b);free(x);return 1;