精华内容
下载资源
问答
  • 数组循环左移 c++实现

    2018-06-20 11:06:28
    请编写程序将一个大小为n的整数数组循环左移m位。如:1,2,3,4,5,6,7,8循环左移三位后结果是:4,5,6,7,8,1,2,3.
  • 数组循环左移问题

    2021-02-27 21:17:51
    数组循环左移问题的三种解法问题/题干 描述解法1解法2解法3 问题/题干 描述 将一个具有n个元素的数组向左循环移动i个位置。 这只一个很实用的问题,很多应用程序会调用这个问题的算法,例如在文本编辑器中移动行的...

    数组循环左移问题的三种解法

    问题/题干 描述

    将一个具有n个元素的数组向左循环移动i个位置。
    这只一个很实用的问题,很多应用程序会调用这个问题的算法,例如在文本编辑器中移动行的操作,磁盘整理时交换两个不同大小的相邻内存块等。所有解决这个问题的算法要求有较高的时间性能和空间性能。

    解法1

    先将数组前i个元素存放于另一个临时数组,再将余下的n-i个元素左移i个位置,最后将前i个元素从临时数组复制会原数组后面i个位置。
    总共需要移动i+(n-i)+i=i+n次数组元素,使用了i个额外的存储单元。

    解法2

    设计一个函数,将数组向左循环1个位置,循环i次。
    移动i*n次数组元素,使用了1个额外数组单元。

    解法3

    换个角度看:
    把这个问题看做数组AB转换为数组BA的问题(A代表数组前i个元素,B代表余下n-i个元素)。
    先将A取逆得A-1B,再将B取逆得A-1B-1, 最后将整个A-1B-1取逆得BA
    下面通过reverse函数演示一下,对abcdefgh左移3个元素位置:
    reverse(0, i-1); cbadefgh
    reverse(i, n-1); cbahgfed
    reverse(0,n-1); defghabc

    该算法总共交换i/2 + (n-i)/2 + n/2 = n次数组元素,使用了1个用来交换的数组单元。
    Brian Kernighan 在Software Tools in Pascal中使用了这个算法在文本编辑器中移动各行。

    展开全文
  • 将一维数组(x0,x1,…,xn-1)循环左移p位(0<p<n),变为(xp,xp+1,…,xn-1,x0,x1,…,xp-1) 例如: 一维数组: (1,2,3,4,5,6,7,8,9,10),令p=4 最终得到一维数组:(5,6,7,8,9,10,1,2,3,4) ...

    问题描述:
    将一维数组(x0,x1,…,xn-1)循环左移p位(0<p<n),变为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)
    例如:
    一维数组: (1,2,3,4,5,6,7,8,9,10),令p=4
    最终得到一维数组:(5,6,7,8,9,10,1,2,3,4)
    算法思想:
    先整体逆置为(10,9,8,7,6,5,4,3,2,1),
    再将前n-p个逆置为(5,6,7,8,9,10,4,3,2,1),
    再将后p个逆置为(5,6,7,8,9,10,1,2,3,4)
    代码实现:

    typedef int DataType;
    void Reverse(DataType A[],int left,int right){
    	if(left>right)
    		return;
    	int mid=(left+right)/2;
    	for(int i=0;i<=mid-left;i++){
    		DataType t=A[left+i];
    		A[left+i]=A[right-i];
    		A[right-i]=t;
    	}
    }
    void LeftMove_p(DataType A[],int p){
    	Reverse(A,0,n-1);
    	Reverse(A,0,n-1-p);
    	Reverse(A,n-p,n-1);
    }
    
    展开全文
  • 课程设计题目:用 Reverse 实现时间复杂度为 O(n)O(n)O(n) 数组循环左移算法 一、问题描述 设计一个时间复杂度为 O(n)O(n)O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 kkk 个位置。 详见王红梅等编著的《数据...

    课程设计题目:用 Reverse 实现时间复杂度为 O ( n ) O(n) O(n) 数组循环左移算法

    一、问题描述

    设计一个时间复杂度为 O ( n ) O(n) O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 k k k 个位置。

    详见王红梅等编著的《数据结构(C++版)(第2版)》P53页习题5(1)。

    二、基本要求

    1. 实现将数组 A[n] 中所有元素循环左移 k k k 个位置。

    2. 时间复杂度为 O ( n ) O(n) O(n)

    三、概要设计

    1. 算法的设计

    算法思路参考王红梅等编著的《数据结构(C++版)(第2版)》P16页思想火花,出自BW Kernighan和PJ Plauger于1981年发表的著作Software tools in Pascal

    1. 设计reverse(first, last)函数,用于实现反转从firstlast(不含)之间的元素;

    2. 通过3次reverse实现将数组 A[n] 中所有元素循环左移 k k k 个位置:

      reverse(a, a + k)

      reverse(a + k, a + n)

      reverse(a, a + n)

    四、详细设计

    1. 设计每个函数

    void Reverse(int *first, int *last)
    {
        last--;
        for (int temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    

    2. 设计主函数

    int main()
    {
        reverse(a, a + k);
        reverse(a + k, a + n);
        reverse(a, a + n);
    }
    

    五、运行与测试

    1. 测试环境

    运行环境:Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

    编译器:gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

    编译命令:-g

    运行终端:cmd

    2. 在调试程序的过程中遇到的问题与解决方案

    暂未发现异常。

    3. 设计的测试数据与测试结果

    测试3次。输入k,然后生成一个随机数组并输出,数组所有元素循环左移 k k k 个位置后再输出。

    4. 程序清单及运行结果

    4.1 A[n] 为整型数组

    程序清单如下。

    // ex1_2.cpp
    
    /*
     * 1. 编写程序:课本p53页习题5(1),先做整数,然后改用模板函数做并测试。
     * 课本p53页习题5(1):设计一个时间复杂度为 O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 k 个位置。
     * 模板
     */
    
    #include <iostream>
    #include <ctime>
    using namespace std;
    
    template <typename T>
    void Reverse(T *first, T *last)
    {
        last--;
        for (T temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    
    int main()
    {
        srand(time(NULL));
    
        int n = 10, k;
        cout << "Please input k(0 < k < 10): ";
        cin >> k;
    
        int A[n];
        for (int i = 0; i < n; i++)
            cout << (A[i] = rand()) << " ";
        cout << endl;
    
        Reverse(A, A + k);
        Reverse(A + k, A + n);
        Reverse(A, A + n);
    
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    
        double B[n];
        for (int i = 0; i < n; i++)
            cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
        cout << endl;
    
        Reverse(B, B + k);
        Reverse(B + k, B + n);
        Reverse(B, B + n);
    
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
        cout << endl;
    
        return 0;
    }
    

    第1次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 3
    31255 22925 30731 23452 21176 11048 16126 26806 17875 16867
    23452 21176 11048 16126 26806 17875 16867 31255 22925 30731

    第2次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 4
    31297 31583 821 8595 24193 29328 23820 21519 3149 2478
    24193 29328 23820 21519 3149 2478 31297 31583 821 8595

    第3次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 5
    31310 9040 6742 6545 32684 12267 3502 9810 3660 10654
    12267 3502 9810 3660 10654 31310 9040 6742 6545 32684

    4.2 模板

    #include <iostream>
    #include <ctime>
    using namespace std;
    
    template <typename T>
    void Reverse(T *first, T *last)
    {
        last--;
        for (T temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    
    int main()
    {
        srand(time(NULL));
    
        int n = 10, k;
        cout << "Please input k(0 < k < 10): ";
        cin >> k;
    
        int A[n];
        for (int i = 0; i < n; i++)
            cout << (A[i] = rand()) << " ";
        cout << endl;
    
        Reverse(A, A + k);
        Reverse(A + k, A + n);
        Reverse(A, A + n);
    
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    
        double B[n];
        for (int i = 0; i < n; i++)
            cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
        cout << endl;
    
        Reverse(B, B + k);
        Reverse(B + k, B + n);
        Reverse(B, B + n);
    
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
        cout << endl;
    
        return 0;
    }
    

    第1次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 3
    31607 4105 26750 850 21038 9151 24591 5572 31655 8236
    850 21038 9151 24591 5572 31655 8236 31607 4105 26750
    0.551057 2.53344 0.209033 6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277
    6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277 0.551057 2.53344 0.209033

    第2次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 4
    31624 25079 17767 22863 7075 28785 7385 23704 15909 10263
    7075 28785 7385 23704 15909 10263 31624 25079 17767 22863
    0.511611 0.172095 1.52812 1.01504 0.720147 9.04 10.3216 0.00956241 2.05172 0.394671
    0.720147 9.04 10.3216 0.00956241 2.05172 0.394671 0.511611 0.172095 1.52812 1.01504

    第3次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 5
    31653 23511 14704 10057 1602 31357 2629 30126 673 20467
    31357 2629 30126 673 20467 31653 23511 14704 10057 1602
    0.4426 0.60074 5.66135 0.316398 0.906047 2.21183 135.865 0.0243682 0.37898 0.211203
    2.21183 135.865 0.0243682 0.37898 0.211203 0.4426 0.60074 5.66135 0.316398 0.906047

    六、总结与心得

    算法之美,妙不可言!

    七、参考资料

    1. 王红梅, 胡明, 王涛. 数据结构 (C++ 版)[M]. 清华大学出版社, 2005.

    2. Kernighan B W, Plauger P J. Software tools in Pascal[J]. 1981.

    展开全文
  • C++实验02(04)数组循环左移

    千次阅读 2020-05-02 15:04:24
    题目描述 (要求通过下标和指针访问...最后输出循环左移后的A数组循环左移方法如下所示。在这个实例中k=3。 (本题中n为5) 如果循环左移前,A中存放的内容是: 11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 41 ...

    题目描述
    (要求通过下标和指针访问数组元素)从键盘输入n* n个整数,将它们存放在二维数组A中;然后将A中整数循环左移k次(1<k<n);最后输出循环左移后的A数组。
    循环左移方法如下所示。在这个实例中k=3。 (本题中n为5)
    如果循环左移前,A中存放的内容是:
    11 12 13 14 15
    21 22 23 24 25
    31 32 33 34 35
    41 42 43 44 45
    51 52 53 54 55
    则循环左移后,A中存放的内容变成:
    14 15 21 22 23
    24 25 31 32 33
    34 35 41 42 43
    44 45 51 52 53
    54 55 11 12 13
    输入描述
    两批数据:第一批:左移的次数k
    第二批:5 * 5个整数
    输出描述
    左移k位后的数组,按行输出,数据间用"\t"分隔
    输入样例
    3
    11 12 13 14 15
    21 22 23 24 25
    31 32 33 34 35
    41 42 43 44 45
    51 52 53 54 55
    输出样例
    左移3位后的数组为:
    14 15 21 22 23
    24 25 31 32 33
    34 35 41 42 43
    44 45 51 52 53
    54 55 11 12 13

    #include <iostream>
    using namespace std;
    int main()
    {
    	int a[5][5],i,j,k,t,s;
    	cin>>k;
    	for(i=0;i<5;i++)
    		for(j=0;j<5;j++)
    		   cin>>*(*(a+i)+j);
    	if(k>1&&k<5)
    	{
    		for(s=1;s<=k;s++)
    		{
    			t=a[0][0];
    			for(i=0;i<5;i++)
    				for(j=0;j<5;j++)
    				{
    					if(j!=4)
    						*(*(a+i)+j)=*(*(a+i)+j+1);
    					else
    						*(*(a+i)+j)=*(*(a+i+1)+0);
    				}
    			a[4][4]=t;
    		}
    	}
    	cout<<"左移"<<k<<"位后的数组为:"<<endl;
    	for(i=0;i<5;i++)
    		for(j=0;j<5;j++)
    		{
    			cout<<a[i][j]<<'\t';
    			if(j==4)
    				cout<<endl;
    		}
    		return 0;
    }
    
    展开全文
  • 7-2 数组循环左移(20分)(顺序表实现)

    千次阅读 2019-08-03 10:23:53
    本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a0 a1 … an-1)变换为(am…an-1 a0 a1...
  • 试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0, x1…, xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。 输入 多组数据,每组数据...
  • 数组循环左移 本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a​0​​ a​1​​ ⋯a​n...
  • 将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据(x0,x1,x2,…x(n-1))变换为(xp,x(p+1),…,x(n-1),x0,x1,…,x(p-1)) 示例: [1, 2, 3, 4, 5, 6, 7, 8, 9] 左移4位 [5, 6, 7, 8, 9, 1, 2, 3, 4] ....
  • 习题2.2 数组循环左移 颠倒交换法 算法描述:循环左移k位, 把前面 0 到 k-1位置的数字首尾交换, 把 k 到 len-1位置首尾交换, 再把 0 到 len-1下标位置首位交换
  • 数组循环左移和右移

    2021-09-06 10:30:23
    [在这里插入图片描述](https://img-blog.csdnimg.cn/588247dfb7c8436c977e5ed372a08fba.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qS_Jua5qw==,size_20,color_...
  • 对于一个任意长度为len的数组A,使其循环左移P个元素。如数组{1,2,3,4,5,6,7},左移3个元素即变为{4,5,6,7,1,2,3}。 实现算法 方法一 对前3个元素完全转置,变为{3,2,1,4,5,6,7} 对后4个元素完全转置,变为{3,2,1,7,6...
  • 数组循环左移

    2020-02-18 10:55:13
    试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0, x1…, xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。 输入 多组数据,每组数据...
  • 数组循环移动问题

    2021-07-26 16:21:24
    问题描述:将一个具有N个元素的数组循环左移或右移。 分析如下(以循环左移为例) 解法一: ​ 先将数组中的前 i 个元素存放在一个临时数组中,再将余下的 N - i 个元素左移 i 个位置,最后将前 i 个元素从临时数组...
  • 数组循环左移

    千次阅读 2017-07-12 13:49:57
    本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a0a1⋯a(n−1))变换为(am⋯a(n−1)a0a1⋯a...
  • 对于一个任意长度为len的数组A,使其循环左移P个元素。如数组{1,2,3,4,5,6,7},左移3个元素即变为{4,5,6,7,1,2,3}。 实现算法 方法一 对前3个元素完全转置,变为{3,2,1,4,5,6,7} 对后4个元素完全转置,变为{3,2...
  • 0)个整数,在不允许使用另外数组的前提下,将每个整数循环左移m(≥0)个位置,即将a中的数据由(a0​a1​⋯an−1​)变换为(am​⋯an−1​a0​a1​⋯am−1​)(最前面的m个数循环移至最后面的m个位置)。...
  • 本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a​0​​ a​1​​ ⋯a​n−1​​ )变换...
  • 习题2.2 数组循环左移

    2021-02-16 18:29:59
    习题2.2 数组循环左移 题目描述 浙大版《数据结构(第2版)》题目集 本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥...
  • 数组循环向左移动k位的算法

    千次阅读 2018-08-17 00:18:46
    算法描述:循环左移k位, 先把前面 0 到 k-1位置的数字首尾交换, 然后再把 k 到 len-1位置首尾交换, 最后再把 0 到 len-1下标位置首位交换即可实现, 这里的原理你可以画个例子就懂了 代码: int a[100]; //数组是全.....
  • 数组循环左移 题目描述: 本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a​0​a​1​...
  • 数组元素循环左移

    千次阅读 2017-07-03 21:26:46
    设将n(n>1)个整数存放到一维数组R中,设计一个算法,将R中的序列循环左移P(0 分析: 要实现R中序列循环左移P个位置,只需先将R中前P个元素逆置,再将剩下的元素逆置,最后将R中所有元素再整体做一次逆置操作...
  • 将R中保存的序列循环左移p个位置,即将R中的数据由(X0,X1,…Xn-1)变换为Xp,Xp-1,…Xn-1,X0,X1,…Xp-1 2.代码描述 #include<iostream> #include<algorithm> #define InitSize 12 void Reverse01(int...
  • 问题描述】设将n(n>1)个整数存放在一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移P(P>0)个位置。 例如,假设P<n,将R中的数据(X0,X1……Xn-1)循环左移P个...
  • 试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0, x1…, xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。 输入 多组数据,每组数据有...
  • 一、问题描述 二、思路分析 根据这几天做题,我发现考研题难度确实大,而且这尼玛题目总是搞得让你看不懂,总体来说思路不是很好想。那么这种情况下该如何准备代码题呢?我认为还是得多练,多见,见得多了也就有点...
  • 数据结构习题(数组循环左移

    千次阅读 2019-04-11 23:58:15
    将R中保存的序列循环左移p(0 < p < n)个位置,即将R中的数据由(X0,X1,…,Xn-1`)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求: 1)给出算法的基本设计思想 2)根据设计思想,采用C或++或Java语言描述算法,...
  • 本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(&gt;0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(m≥0)个位置,即将a中的数据由(​​​​⋯)变换为(⋯​​​​⋯...
  • 问题描述:对于给定的数组循环左移p个元素 说明:对于这个问题,我想了有三种方法。(当然,还参考了资料),把它们简要的实现出 来了。现简要叙述如下: MoveLeft1:这种算法的思路是,将第一个元素暂时...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,923
精华内容 4,369
关键字:

数组的循环左移问题描述