C# · 12月 19, 2021

数据结构测试代码

1.二进制转化非递归

2.二进制转化递归

3.斐波那契递归

4.斐波那契非递归

5.大数加法

6.直接插入排序

7.快速排序

8.简单选择排序

1.二进制转化非递归

#include

int main()

{

int j,i = 0;

int m,a[100];

scanf(“%d”,&m);

while (m)

{

i++;

a[i] = m % 2;

m /= 2;

}

for (j=i;j>=1;j–)

printf(“%d”,a[j]);

printf(“n”);

return 0;

}

2.二进制转化递归 

#include

void fun(int a)

{

int b = a % 2;

if (a<2)

printf(“%d”,a);

else

{

a /= 2;

fun(a);

printf(“%d”,b);

}

}

int main()

{

int m;

scanf(“%d”,&m);

fun(m);

printf(“n”);

return 0;

}

3.斐波那契递归 

#include

int fun(int m)

{

if (m==1 || m==2) return 1;

else return fun(m-1) + fun(m-2);

}

int main()

{

int f;

scanf(“%d”,&f);

int ans = fun(f);

printf(“%dn”,ans);

return 0;

}

4.斐波那契非递归 

#include

int main()

{

int ans,i,k;

int t1 = 1,t2 = 1;

scanf(“%d”,&k);

if (k==1 || k==2)

ans = 1;

else

{

for (i=3;i<=k;i++)

{

ans = t1 + t2;

t1 = t2;

t2 = ans;

}

}

printf(“%dn”,ans);

return 0;

}

 5.大数加法

#include

#include

char s1[100],s2[100];

int a[100],b[100];

int main()

{

int i,j,l,l1,l2;

scanf(“%s %s”,s1,s2);

l1 = strlen(s1);

l2 = strlen(s2);

if (s1[0]==’0′ && s2[0]==’0′)

printf(“0n”);

else

{

for (i=l1-1,j=0;i>=0;i–,j++)

a[j] = s1[i] – ‘0’;

for (i=l2-1,j++)

b[j] = s2[i] – ‘0’;

l = l1 > l2 ? l1 : l2;

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

{

a[i] += b[i];

if (a[i]>9)

{

a[i] -= 10;

a[i+1]++;

}

}

while (!a[l]) l–;

for (;l>=0;l–)

printf(“%d”,a[l]);

printf(“n”);

}

return 0;

}

6.直接插入排序 

#include

int n,a[1000];

void SORT()

{

int i,j;

for (i=2;i<=n;i++)

if (a[i]

{

a[0] = a[i];

a[i] = a[i-1];

for (j=i-2;a[0]

a[j+1] = a[j];

a[j+1] = a[0];

}

}

int main()

{

scanf(“%d”,&n);

for (int i=1;i<=n;i++)

scanf(“%d”,&a[i]);

SORT();

for (int i=1;i<=n;i++)

printf(“%d “,a[i]);

printf(“n”);

return 0;

}

7.快速排序 

#include

int a[1000];

int partsort(int low,int high)

{

a[0] = a[low];

int t = a[0];

while (low<high)

{

while (low=t) high–;

a[low] = a[high];

while (low<high && a[low]<=t) low++;

a[high] = a[low];

}

a[low] = a[0];

return low;

}

void qsort(int low,int high)

{

if (low<high)

{

int t = partsort(low,high);

qsort(low,t-1);

qsort(t+1,high);

}

}

int main()

{

int n,i;

scanf(“%d”,&n);

for (i=1;i<=n;i++)

scanf(“%d”,&a[i]);

qsort(1,n);

for (i=1;i<=n;i++)

printf(“%d “,a[i]);

printf(“n”);

return 0;

}

8.简单选择排序 

#include

int a[1000];

void SORT(int n)

{

int i,j;

for (i=1;i<=n-1;i++)

{

int k = i;

for (j=i+1;j<=n;j++)

if (a[j]

k = j;

if (k!=j) swap(a[i],a[k]);

}

}

int main()

{

int n,&a[i]);

SORT(n);

for (i=1;i<=n;i++)

printf(“%d “,a[i]);

printf(“n”);

return 0;

}