• 欢迎光临~

顺序表-00016-旋转顺序表

开发技术 开发技术 2022-12-09 次浏览

 

  • 旋转顺序表:将顺序表所有元素n个整体向后移动k位。方法1
  • /**
    * @brief 功能:数组arr元素个数为n,整体向后移动k(非负数)个位置 n
    * @note 取出arr[n-1]处元素,对[0,n-1]处元素逐个右移,循环k次
    */
    void xxx_rotate_01(int arr[], int n, int k)
    {
    	if (arr == NULL || n < 1 || k < 1)
    	{
    		return;
    	}
    	k = k % n;
    	// 将表尾元素取出tmp,然后将所有元素依次向后移动1个位置
    	// 再将取出的表尾元素放置表首元素位置。
    	// 此为整体元素完成1次移动。重复上述操作,总共循环k次,即可
    	for (int j = 0; j < k; ++j)
    	{
    		int tmp = arr[n - 1];
    		for (int i = n - 1; i > 0; --i)
    		{
    			arr[i] = arr[i - 1];
    		}
    		arr[0] = tmp;
    	}
    
    }
    

      

  • 旋转顺序表:将顺序表所有元素n个整体向后移动k位。方法2
  • /**
    * @brief 功能:方法2 n
    * @note 将原数组的[0,n-k-1]的元素拷贝至新数组的[n-k,n-1]处
    * @note 将原数组的[n-k,n-1]的元素拷贝至新数组的[0,n-k-1]处
    * @note 再将处理完成的新数组元素拷贝至原数组
    */
    void xxx_rotate_02(int arr[], int n, int k)
    {
    	{
    		if (arr == NULL || k < 0)
    		{
    			return;
    		}
    		k = k % n;
    		int* p = (int*)calloc(sizeof(int), n);
    		if (p == NULL)
    		{
    			return;
    		}
    		for (int i = 0; i < k; ++i)
    		{
    			p[i] = arr[i + n - k];
    		}
    		for (int i = 0; i < n - k; ++i)
    		{
    			p[i + k] = arr[i];
    		}
    		for (int i = 0; i < n; i++)
    		{
    			arr[i] = p[i];
    		}
    		free(p);
    		p = NULL;
    	}
    }
    

      

  • 旋转顺序表:将顺序表所有元素n个整体向后移动k位。方法3
  • /**
    * @brief 功能:方法3 n
    * @note 先将数组逆置,逆置后的[0,k-1]和[k,n-1]部分分别逆转
    */
    void xxx_reverse(int arr[], int left, int right)
    {
    	if (arr == NULL)
    	{
    		return;
    	}
    	int tmp = 0;
    	while (left < right)
    	{
    		tmp = arr[left];
    		arr[left] = arr[right];
    		arr[right] = tmp;
    		left++;
    		right--;
    	}
    }
    void xxx_rotate_03(int arr[], int n, int k)
    {
    	if (arr == NULL || k < 0)
    	{
    		return;
    	}
    	k = k % n;
    	xxx_reverse(arr, 0, n - 1);
    	xxx_reverse(arr, 0, k - 1);
    	xxx_reverse(arr, k, n - 1);
    }
    

      

程序员灯塔
转载请注明原文链接:顺序表-00016-旋转顺序表
喜欢 (0)