一道C数据结构试题2

发布网友发布时间：2023-10-23 20:03

共2个回答

热心网友时间：2023-11-19 15:32

这是我们数据结构考试的最后一题呵呵,比较简单的说.
我大概说一下当时我的解法.
记得要设两个指针同时从数组的头和尾进行遍历,
从尾部开始,如果是偶数就向前移,直到遇到一个奇数为止.再从头部判断如果是奇数就往后移,直到遇到一个偶数为止.这时交换两个指针的值.直到两个指针指向一起.
空间复杂度为O(1),时间复杂度在O(n)级.
程序如下:

#include<stdio.h>
int main()
{
int a[]={2,33,24,54,56,34,76,76,78,67,65,34,34,23};
int i,j;
for(i=0,j=sizeof(a)/sizeof(int); i != j; )
{
if( a[j] % 2 == 0 && a[i] % 2 == 0 )
{
j--;
continue;
}
else if( a[j] % 2 !=0 && a[i] % 2 != 0 )
{
i++;
continue;
}

else if( a[j] % 2 == 0 && a[i] % 2 != 0 )
{
j--;
i++;
continue;
}
else
{
int tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
for(i = 0; i < sizeof(a)/sizeof(int); i++ )
{
printf("%d\t", a[i]);
}
}

热心网友时间：2023-11-19 15:32

void fun(int A[],int n)//n为A中元素个数
{
int i=0,j=n-1,t;
while(i<j)
{
if(A[i]%2==0&&A[j]%2!=0)
{
t=A[i];
A[i]=A[j];
A[j]=t;
}
if(A[i]%2!=0)i++;
if(A[j]%2==0)j--;
}
}
时间复杂度为o(n)