【数组＆＆字符串＆＆宏练习题】

今天向大家分享的是一些最近整理出来的一些基础练习题，希望能对你有所帮助。

 

 

目录

1 模拟实现atoi

2 寻找单身狗

3 用宏将一个二进制位的奇数位与偶数位交换

4 用宏模拟实现offsetof

 4 序列中整数去重

5 有序序列合并

---

 

1 模拟实现atoi

我们知道：atoi是将字符串中的数字转化成整形数字，但是有以下的情况需要特殊考虑：

1空指针

2空字符串

3遇到了非数字字符

4超出了范围

 所以我们不妨用一种枚举类型state来判断当前的输入是否合法，符号的正负可以定义一个flag.

enum state
{
	VALID,
	UNVALID,
};
enum state s = VALID;
int MyAtoi(const char* ps)
{
	if (NULL == ps)
	{
		s = UNVALID;
	    return 0;
    }
	int flag = 1;
    if (*ps == '+')
	{
		ps++;
	}
	else if (*ps == '-')
	{
	     flag = -1;
         ps++;
    }
	while (isspace(*ps))
	{
		ps++;
	}
	long long n = 0;
	while (isdigit(*ps))
	{
		n = n * 10 + flag*(*ps - '0');
		if (n > INT_MAX || n < INT_MIN)
		{
			s = UNVALID;
		    return 0;
		}
		ps++;
	}
	if (*ps == '\0')
		return (int)n;
	else
	{
		s = UNVALID;
		return 0;
    }


}
int main()
{
	const char* pc = "- a123456";
	int ret = MyAtoi(pc);
	if (s == VALID)
    {
		printf("%d\n", ret);
	}
	else
		printf("格式错误，无法打印\n");
	return 0;
}

---

 

2 寻找单身狗

题目要求：一个整形数组中只有两个元素是单身的（只出现了一次），其他元素均出现了两次，请找出这两个单身元素。

我们知道：如果只有一个单身元素的话，只需要将数组中每一个元素互相^就能解决问题。那么有两个单身元素又该怎么办呢？

我i们不妨假设一个整形数组{1,1,2,2,3,3,4,4,5,6}，如果将数组中每个元素^就相当于5^6，得到的结果是3，解决该问题的关键在于如何将5和6分到不同的小组？

我们发现：将5^6的结果(3)二进制的每一位都&1(从右向左)，如果&1的结果==1，就记住第一次==1的位置，假设该位置记做pos，然后让数组中每一个元素都向右移动pos位，得到的结果如果==1，就分到一个数组，不为1就分到另外一个数组，这样就将5和6分到了不同的小组了。

 

//求一个数组中哪两个是单身元素（其余重复元素只有两个）
void GudgSgle(int arr[], int len,int*p1,int*p2)
{
	int ret = 0;
	int i = 0;
	int pos = 0;
	for (i = 0; i < len; i++)
	{
		ret ^= arr[i];
	}
	for (i = 0; i < 32; i++)
	{
		if ((ret >> i & 1) == 1)
		{
			pos = i;
			break;
		}
	}
	for (i = 0; i <len; i++)
	{
		if ((arr[i] >> pos & 1) == 1)
			*p1 ^= arr[i];
		else
			*p2 ^= arr[i];
	}
}
int main()
{
	int arr[12] = { 1,2,3,4,5,6,1,2,3,4 };
	int len = sizeof(arr) / sizeof(int);
	int single1 = 0;
	int single2 = 0;
	GudgSgle(arr, len,&single1,&single2);
	printf("%d %d\n", single1, single2);
	return 0;
}

---

 

3 用宏将一个二进制位的奇数位与偶数位交换

首先来看：如何将一个二进制位奇数位与偶数位交换？如果能拿到所有奇数位以及所有偶数位，再将所有奇数位向左移动一位，所有偶数位向右移动一位，然后再相加就能解决问题。关键在于如何拿到所有的奇数位和所有的偶数位：给定一个二进制数1111 1111 1111 1111 1111 1111 1111 1111，如果要得到奇数位就将该二进制数&0101 0101 0101 0101 0101 0101 0101 0101（0x55555555)

如果要得到偶数位就将该二进制数&1010 1010 1010 1010 1010 1010 1010 1010 (0xaaaaaaaa)

//写一个宏：将一个整数的二进制位奇数与偶数交换
#define SWAP(num) (((num&0x55555555)<<1)+((num&0xaaaaaaaa)>>1))
int main()
{
	int num = 10;
	printf("%d\n", SWAP(num));
	return 0;
}

 得到的结果是5 符合要求。

---

4 用宏模拟实现offsetof

offsetof是计算结构体中某变量相对于首地址的偏移量。为了计算的简便，我们不妨将0强转成一种结构体指针，再通过该指针引用结构体中的变量，取出它的地址，该地址再数值上就等于所求结构体变量的偏移量。

//写一个宏，自己实现offsetof
struct state
{
	char a;
	char b;
	short c;
	int d;
};

#define OFFSETOF(stuname,memname) (int)&(((struct state*)0)->memname)
int main()
{
	printf("%d\n", OFFSETOF(struct state, a));
	printf("%d\n", OFFSETOF(struct state, b));
	printf("%d\n", OFFSETOF(struct state, c));
	printf("%d\n", OFFSETOF(struct state, d));
	return 0;
}

得到的结果：

 这里值得注意的是：将0强转成一种结构体指针并不是真正使用了0地址处的空间，只是模拟实现了计算偏移量而已，这里也可以将其他数字强转，只不过后面要再减去该数字。

下面这种写法也是正确的：

---

 

 4 序列中整数去重

给定一个整形数组，去除其中重复出现的数字：例如{1,2,2,2,5,5,3,9},去重后变为{1,2,5,3,9},

解题的思路是：遍历数组中每一个元素，将该元素与后面其他所有数字比较，如果相等，就将该元素被后面一个元素覆盖（该元素其后的元素均向前移动一位）

#include<stdio.h>
int main()
{
    int n=0;
    scanf("%d",&n);
    int i=0;
    int arr[1000]={0};
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    int j=0;
    int k=0;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(arr[j]==arr[i])
            {
                for(k=j+1;k<n;k++)
                    arr[k-1]=arr[k];
                n--;
                j--;
            }
        }
    }
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

 

其中容易出错的是当覆盖了一个元素后j--,就拿{1,2,2,2,5,5,3,9}来说，当拿第二个元素与第3个元素相比时，就会把第二个元素覆盖，此时数组变为{1,2,2,5,5,3,9},j如果不--的话会直接跳到现在的第3位元素，会让第3位元素与后面的进行比较，也就忽略了覆盖元素，就会出错。

---

5 有序序列合并

题目要求：将两个按升序排列的整形数组合并成一个按升序排列的整形数组。

解题思路：可以创建一个整形数组，一个一个比较另外两个数组，将其中的较小值放在创建的数组中。

#include<stdio.h>
int main()
{
    int m=0;
    int n=0;
    int arr1[1000]={0};
    int arr2[1000]={0};
    int arr3[3000]={0};
    scanf("%d%d",&m,&n);
    int i=0;
    for(i=0;i<m;i++)
    {
        scanf("%d",&arr1[i]);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr2[i]);
    }
    i=0;
    int j=0;
    int k=0;
    while(i<m && j<n)
    {
        if(arr1[i]>arr2[j])
        {
            arr3[k++]=arr2[j];
            j++;
        }
        else
        {
            arr3[k++]=arr1[i];
            i++;
        }
    }
    if(i==m)
        for(;j<n;j++)
            arr3[k++]=arr2[j];
    else
        for(;i<m;i++)
            arr3[k++]=arr1[i];
    for(i=0;i<k;i++)
        printf("%d ",arr3[i]);
    return 0;
}

如果其中一个数组遍历完了但是另一个数组还没有遍历完，就把没有遍历完的元素一 一赋给创建的数组。