数据结构与算法

双指针在数组中的应用。

// 双指针实现逆序
void Reverse(char arr[], int size)
{
	char * p = arr;
	char * q = arr + size - 1;
	while (p < q)
	{
		char ch = *p;
		*p = *q;
		*q = ch;
		p++;
		q--;
	}
}

int main()
{
	char arr[] = "hello world";
	cout << arr << endl;
	Reverse(arr, strlen(arr));
	cout << arr << endl;

	system("pause");
	return 0;
}

AdjustArray2 是 AdjustArray1的改进。

// AdjustArray1存在一个问题，假设当q条件不成立时，while循环每次都要再次判断p是否满足；
// 该进后，当p不成立时候，直接判断q；当p不成立，q也不成立时候，直接进行交换，就不在while开始再次判断p再判断q了。
void AdjustArray2(int arr[], int size)
{
	int *p = arr;
	int *q = arr + size - 1;
	while (p < q)
	{
		while (p < q)
		{
			if ((*p & 0b1) == 1)  // 
			{
				break;
			}
			p++;
			
		}
		while (p < q)
		{
			if ((*q & 0b1) == 0)  // 
			{
				break;
			}
			q--;
		}
		// 否则，当p和q都不满足时候，交换
		// 加一个if判断,为了防止数组中所有的数都是奇数或者偶数而导致p和q越界。
		if (p < q)
		{
			int temp = *p;
			*p = *q;
			*q = temp;
			p++;
			q--;
		}

	}

}

// 整型数组，把偶数调整到数组左边，把奇数调整到数组右边
void AdjustArray1(int arr[], int size)
{
	int *p = arr;
	int *q = arr + size - 1;
	while (p < q)
	{
		// p找奇数，找到的不是奇数就++
		if ((*p & 0b1) == 0)  // 
		{
			p++;  // 如果p是偶数，那么p++
			continue;
		}
		// q找偶数，找到的不是偶数就--
		if ((*q & 0b1) == 1)
		{
			q--;  // 如果q是奇数，q--
			continue;
		}
		// 否则，当p和q都不满足时候，交换
		int temp = *p;
		*p = *q;
		*q = temp;
		p++;
		q--;
	}

}

int main()
{
	int arr[10] = { 0 };
	srand(time(0));
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 100;
	}
	
	for (int v : arr)
	{
		cout << v << " ";
	}
	AdjustArray2(arr, 10);


	cout << endl;
	for (int v : arr)
	{
		cout << v << " ";
	}

	cout << endl;
	system("pause");
	return 0;
}