精华内容
下载资源
问答
  • 线性表循环右移k位

    千次阅读 2018-04-12 19:26:59
    问题描述:线性表循环右移k位,即:1 2 3 4 5 6 7 8 9右移3位后6 7 8 9 1 2 3 4 5 #include <iostream>#include <cstdlib>using namespace std;typedef int elemtype;typedef struct{...

    问题描述:线性表循环右移k位,即:
    1 2 3 4 5 6 7 8 9
    右移3位后
    6 7 8 9 1 2 3 4 5 
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    typedef int elemtype;
    typedef struct{
     elemtype* elem;
     int listsize;
     int length;
    }sqlist;
    void create_L(sqlist& L){
     L.elem=(elemtype*)malloc(1000*sizeof(elemtype));
     L.listsize=1000;
     L.length=0;
    }
    void show(sqlist& L){
     for(int i=0;i<L.length;i++){
      cout<<L.elem[i]<<" ";
     }  
     cout<<endl;
    }
     /*先把线性表整体逆置 ,即:9 8 7 6 5 4 3 2 1
    然后再把前k+1位逆置(因为数组下标从0开始的),后面的逆置
                                              6 7 8 9,1 2 3 4 5*/
    void nixu(sqlist& L,int k){
      for(int i=0;i<L.length/2;i++){
       int t;
       t=L.elem[i];
       L.elem[i]=L.elem[L.length-1-i];
       L.elem[L.length-1-i]=t;  
         }
         for(int i=0;i<k/2;i++)
         {
          int t;
       t=L.elem[i];
       L.elem[i]=L.elem[k-i];
       L.elem[k-i]=t; 
      }
      for(int i=k+1;i<(L.length-1+k+1)/2;i++){
       int t;
       t=L.elem[i];
       L.elem[i]=L.elem[L.length-1+k+1-i];
       L.elem[L.length-1+k+1-i]=t; 
      }
        
     } 
    void fuzhi(sqlist& L,int n){
     cout<<"请输入线性表的元素";
     int m;
     for(int i=0;i<n;i++){
      cin>>m;
      L.elem[i]=m;
      L.length++;
     }
    }

    int main(){
     sqlist l;
     create_L(l);
     fuzhi(l,9); 
     show(l);
     nixu(l,3);
     show(l);
     return 0;
    }
    展开全文
  • 源码:rshift.cpp #include "stdafx.h" #include <stdio.h> /************************************************************************/ /* 数组循环右移算法 ...

    源码:rshift.cpp

    #include "stdafx.h"
    #include <stdio.h>
    
    
    /************************************************************************/
    /* 数组循环右移算法                                                     */
    /************************************************************************/
    
    /*
     * 要求:只用一个元素大小的辅助空间,且时间复杂度为O(n)
     */
    
    //************************************
    // Method:    求最大公约数(辗转相除)
    // FullName:  gcd
    // Access:    public 
    // Returns:   int
    // Qualifier:
    // Parameter: int m
    // Parameter: int n
    //************************************
    int gcd(int m, int n)
    {
        return n ? gcd(n, m % n) : m;
    }
    
    //************************************
    // Method:    循环右移解法一(通俗解法)
    // FullName:  rshift1
    // Access:    public 
    // Returns:   void
    // Qualifier:
    // Parameter: int array[]
    // Parameter: int length
    // Parameter: int shift
    //************************************
    void rshift1(int array[], int length, int shift)
    {
        //求最少循环移动链的数量
        //设length=m,shift=n
        //则[0] -> [n%m] -> [2n%m] -> ... -> [mn%m]=[0]=起始
        //假设kn%m==0,令m=gcd*X,n=gcd*Y,则X与Y互斥
        //则k*Y%X==0,Y与X互斥,故X能整除k,故k=m/gcd
        //k是一条链条的长度,故链条的数量为m/k=gcd
        int least_movement = gcd(length, shift);//最少循环移动链的数量
        int i;
        for (i = 0; i < least_movement; i++)
        {
            int swap_a = i;
            int swap_b = (i + shift) % length;
            int tmp = array[swap_a];
            while (swap_b != i)
            {
                array[swap_a] = array[swap_b];
                swap_a = swap_b;
                swap_b = (swap_b + shift) % length;
            }
            array[swap_a] = tmp;
        }
    }
    
    //************************************
    // Method:    循环右移解法二(翻转解法)
    // FullName:  rshift2
    // Access:    public 
    // Returns:   void
    // Qualifier:
    // Parameter: int array[]
    // Parameter: int length
    // Parameter: int shift
    //************************************
    void rshift2(int array[], int length, int shift)
    {
        //翻手掌算法
        //设length=m,shift=n(n=n%m)
        //方法:分割数组 => array1[0 .. n-1] | array2[ n .. m-1 ]
        //array1翻转,array2翻转,再整体翻转
        //
        //原先:     1,2,3,4,..,n-1     | n,...,m-2,m-1
        //各自翻转: n-1,n-2,...,2,1    | m-1,m-2,...,n
        //全部翻转: n,n+1,...,m-2,m-1  | 1,2,3,...,n-2,n-1
        //这就完成了右移n单位的任务
        int i;
        shift %= length;
        int tmp;
        for (i = 0; i < (shift - 1) / 2; i++)
        {
            tmp = array[i];
            array[i] = array[shift - i - 1];
            array[shift - i - 1] = tmp;
        }
        for (i = shift; i < shift + (length - shift) / 2; i++)
        {
            tmp = array[i];
            array[i] = array[length + shift - i - 1];
            array[length + shift - i - 1] = tmp;
        }
        for (i = 0; i < length / 2; i++)
        {
            tmp = array[i];
            array[i] = array[length - i - 1];
            array[length - i - 1] = tmp;
        }
    }
    
    void print_array(int array[], int length)
    {
        int i;
        for (i = 0; i < length; i++)
        {
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    int main(int argc, char* argv[])
    {
        int a[] = { 1,2,3,4,5,6 };
        printf("=====================\n");
        print_array(a, 6);
        printf("========== rshift ==========\n");
        rshift1(a, 6, 3);
        print_array(a, 6);
        printf("========== rshift ==========\n");
        rshift2(a, 6, 3);
        print_array(a, 6);
        return 0;
    }

    转载于:https://www.cnblogs.com/bajdcc/p/4768163.html

    展开全文
  • 关于最高效的循环右移算法的课程设计 题目描述:将长度为N的数组arr循环右移K位,给出最高效的算法 里面公开了相对应的课程设计和源代码
  • 有关线性表的一些算法

    千次阅读 2016-09-26 10:48:16
    1.设计一个时间复杂度为O(n)的算法,实现将数组A[n]中所有元素循环右移k个位置 举例:a[] = {1,2,3,4,5},循环右移1位后 a[] = {5,1,2,3,4}; 首先,我们可能想到的算法是,先将数组的后k个元素保存到一个临时数组中,...

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

    举例:a[] = {1,2,3,4,5},循环右移1位后 a[] = {5,1,2,3,4};

    首先,我们可能想到的算法是,先将数组的后k个元素保存到一个临时数组中,然后将前n-k个元素右移k个位置.然后将临时数组的元素复制到元素的前k个位置.

    实现:

    template <class T>
    void MoveArrayAdditional(T array[], int nLen, int k)
    {
    	// 后k个元素移到临时数组,然后将前n-k个元素循环右移k位,再将临时数组元素放到数组前面
    	int other[k];
    	int m = k;
    	for (int i = 0; i<k; i++)
    	{
    		other[i] = array[m++];
    		array[i+k] = array[i]; 
    	}
    	for (int j = 0; j<k; j++)
    	{
    		array[i] = other[i];
    	}
    }
    这个算法的时间复杂度符合要求,但是需要额外的k个存储单元.

    我们可以换个角度解决这个问题.把这个问题看作把数组ab转换为数组ba;先将a逆置得到a^b,再将b逆置得到a^b^,最后将这个a^b^逆置得到(a^b^)^ = ba.于是得到:

    template <class T>
    void MoveArray(T array[], int nStart, int nEnd)
    {
    	while (nStart < nEnd)
    	{
    		T temp = array[nStart];
    		array[nStart] = array[nEnd];
    		array[nEnd] = temp;
    		nStart++;
    		nEnd--;
    	}
    }
    emplate <class T>
    void MoveArrayK(T array[], int nLen, int k)
    {
    	MoveArray(array, 0, nLen-1);
    	MoveArray(array, 0, k-1);
    	MoveArray(array, k, nLen-1);
    }
    可以用翻转左右手来形象的形容这个问题.

    2.已知数组A[n]的元素为整型,设计算法将其调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数.

    void DevisionOddAndEven(int array[], int nLen)
    {
    	// 设置两个标志位,分别指示数组头和尾;
    	// 判断头元素是否为奇数
    	// 是:组头标记前移;
    	// 不是:将头元素与尾元素互换,尾元素前移.
    	// 当头元素和尾元素标记重合,停止
    	int nStart = 0;
    	int nEnd = nLen - 1;
    	while (nStart != nEnd)
    	{
    		if (array[nStart]%2 != 0)
    		{
    			nStart++;
    		}else
    		{
    			int temp = array[nStart];
    			array[nStart] = array[nEnd];
    			array[nEnd] = temp;
    			nEnd--;
    		}
    	}
    }
    3.给定两个链表的头结点,判断是否相交

    template <class T>
    bool TwoLinkIsIntersect(Node<T>* pHead1, Node<T>* pHead2)
    {
    	if (pHead1 == NULL || pHead2 == NULL)
    	{
    		return false;
    	}
    	// 1.两个链表相交,它们的尾结点一定相同;所以分别找到两个链表的尾结点,判断值是否相等.
    	Node* rear1 = pHead1;
    	Node* rear2 = pHead2;
    	while (rear1->pNextNode != NULL || rear2->pNextNode != NULL)
    	{
    		if (rear1->pNextNode != NULL)
    		{
    			rear1 = rear1->pNextNode;
    		}
    		if (rear2->pNextNode != NULL)
    		{
    			rear2 = rear2->pNextNode;
    		}
    	}
    	if (*rear1 == *rear2)
    	{
    		return true;
    	}
    	return false;
    }







    展开全文
  • (线性表(数组)循环右移k位 已知线性表A采用顺序存储结构。编写算法,将该表A中元素循环右移K位,要求空间复杂度为O(1) ** 例如:表中的原始数据是1,2,3,4,5,6 若k=2; 则表A的最终数据是:5,6,1,2,3,4**...

    (线性表(数组)循环右移k位

    已知线性表A采用顺序存储结构。编写算法,将该表A中元素循环右移K位,要求空间复杂度为O(1)

    如以下结果:
    表A中的原始数据是:1,2,3,4,5,6
    若k=2;
    则表A的最终数据是:5,6,1,2,3,4

    算法思想:

    线性表在处理的时候,按照数组的形式的进行处理,因此此处用数组的格式实现。首先先右移动一位,即最后一个数会被覆盖,因此先记录下最后一个数。这样循环K次就可以了,代码如下:

    #include <stdio.h>
    int main()
    {
    	int data[]={1,2,3,4,5,6};
    	int temp,i,k;
    		
    	int len= sizeof(data)/sizeof(int);//数组长度 
    	printf("请输入移动位数k=");
    	scanf("%d",&k);
    	for(int j=1;j<k+1;j++)
    	{
    		
    		temp = data[len-1];
    		for (i = len-1;i > 0 ;i--)
    	{
    		data[i] = data[i-1];
    	}
    		data[0] = temp;
    		
    	}
    
    	for(int s= 0;s<len;s++){
    	printf("%d",data[s]);
    	}
    }
    
    

    实现结果截图:在这里插入图片描述
    总结:本方法没有考虑到时间复杂度的大小,如有效率更高的解法,欢迎交流!!!

    展开全文
  • //i右移一位 } while ( i < j && L . data [ i ] < temp ) ++ i ; //i从左往右扫描,将来到第一个比temp大的元素时停止,并且每走一步都要判断i是否小于j if ( i < j ) { L . data [ j...
  • 线性表相关算法总结

    2019-10-01 21:09:09
    最近在复习考研数据结构的算法,把自己做过的觉得有意思的算法做个总结。本文均采用C语言形式的算法,并且本文算法会以考研算法的流程走,即先写算法思想,再上代码。考研算法比较偏向于算法思想,所以代码部分可能...
  • 前面了解学习了线性表的单向链表和单线循环链表和双向链表的一些知识,本篇搞几个算法题实战一下。首先,做下面准备代码: #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 // 存储空间初始分配量 #...
  • 将R中保存的序列循环左移p个位置(0 题目6 已知一个整数序列A = (a0,a1,a2,...an-1),其中(0),(0). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0,1),则称x>题目7 用单链表保存m个整数, 结点的结构为(data,link),且|data|...
  • // 这个文件主要用于实现一些线性表的功能,包括顺序线性表,静态链表,循环链表,双向链表 // 以及一个用链表实现的多项式 // 为了方便和演示算法,顺序线性表直接使用了C++ STL库中的vector #in...
  • 目录循环右移K位问题试用顺序存储结构设计一个算法,仅用一个辅助结点,实现将线性表中的结点循环右移k位的运算,并分析,算法的时间复杂度.方法一: mod移位思想方法一plus:改进方法二:倒叙移位方法三:递归调用 ...
  •   设计一个算法,对于一个存储着若干元素的顺序表,根据用户输入的移动方向和位数,实现对顺序表元素的循环移动。 2.题目分析 1.假设我们获得用户输入的方向和位数分别为左和3位,表示我们要将4号元素及其之后的...
  • 线性表的基本概念 线性表的顺序存储结构 顺序存储结构的实现 顺序存储结构的应用 线性表的链式存储结构 链式存储结构的实现 单链表的应用 线性表的基本概念 线性表:n个同类型数据元素的有限序列,记为 L=...
  • 数据结构与算法线性表(六):循序队列...循环队列: 在顺序队列基础上,对MAXSIZE总队长进行取余,使得首尾指针可以循环右移,增加了便捷性; 以下是循环队列基本操作实现(所有代码均在Embarcadero DevC++6.0和VSC
  • /*文件名称:实现线性表的插入操作*/#include &lt;iostream&gt; using namespace std; #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 ...
  • 1)个整数存放到一维数组R中,试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存的序列循环左移p(0<p<n)个位置,即把R中的数据序列由(x0,x1,…,xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…...
  • 题目:设计算法,实现一个对数组循环右移k个元素的函数,要求时间复杂度为O(n) 解答: 第一反应想到的是保存要右移的K个元素,然后将右边的N - K个元素左移,这样也可以做到O(n)的时间复杂度,但是空间复杂度是O...
  • 0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(≥0)个位置,即将A中的数据由(A​0​​A​1​​⋯A​N−1​​)变换为(A​N−M​​⋯A​N−1​​A​0​​A​1​​⋯A​N−M−1​​)(最后M个...
  • c数据结构基本算法-线性表存储的设计与测试 提供了c语言数据结构中最基本的算法--线性表存储的源码,主要包含 1. 设计源码; 2. 测试源码。 编译平台vs2015,经测试,运行正常。
  • (3)循环链表 (4)静态链表 总结 前言 大体介绍一下数据结构的知识点,便于个人复习记忆 一、线性表的定义是什么? 线性表示n个数据元素的有限序列; 在复杂的线性表(即每个数据元素都含有若干数据项...
  • 循环链表、双向链表、双向链表的操作、所有链表的时间效率比较、顺序表和链表的比较、线性表的应用、案例分析与实现。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果 可以变为 1,那么这个数就是快乐数。 如果 n 是快乐数就返回 true ;不是,则返回 false 输入:19 输出:true 解释: 12 + 92 = 82 82...
  • /*线性表的插入*/ #include using namespace std; #define LIST_INIT_SIZE 100 //线性表的初始分配量 #define LISTINCREMENT 10 //线性表分配空间的增量  struct SqList //定义线性表结构体 { i
  • 思想:可视为将ab数组转化为ba数组,a代表前p个元素,b代表后p-1个元素,再分别把a,b逆置操作;例:n[]={1,2,3,4,5,6,7,8},先转化为n[]={8,7,6,5,4,3,2,1}
  • 文章目录数据结构与算法 -- 表线性表的顺序结构与实现前提向线性表中插入元素合并两个线性表线性表的应用比较两个线性表的大小 线性表的顺序结构与实现 前提 #define TRUE 1 //正确 #define FALSE 0 //错误 #define ...
  • 线性表

    2020-03-18 11:10:34
    1.线性表的定义和基本操作 线性表:具有相同数据类型的n个数据元素的有限序列。如: L=(a1,a2,…an) 基本操作: 初始化InitList(&L)、求表长Length(L)、按值查找LocateElem(L,e)、按位查找GetElem(L,n)、插入...
  • 同理,右移过程中则会将越界部分置于原线性表的首部。以左移为例做下列分析: 1、线性表的元素循环左移,越界部分为A,为越界部分为B。原序列即为AB。 2、这样循环左移就可以视为是将原序列(AB)转换成序列(BA) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 863
精华内容 345
关键字:

线性表循环右移的算法