Faire pivoter une chaîne de caractères en c++?

Je suis à la recherche d'un moyen pour faire pivoter une chaîne de caractères en c++. Je passe tout mon temps en python, donc mon c++ est très rouillé.

Voici ce que je veux faire: si j'ai une chaîne de caractères 'abcde' je le veux changé pour "bcdea' (premier caractère déplacé à la fin).
Voici comment je l'ai fait en python:

def rotate(s):
    return s[1:] + s[:1]

Je ne suis pas sûr de savoir comment faire en rpc. Peut-être utiliser un tableau de caractères?

InformationsquelleAutor Jeremy | 2009-04-25

c++string

29

Je recommande std::rotate:
```
std::rotate(s.begin(), s.begin() + 1, s.end());
```
- disponible uniquement pour les sig stl
- section 25.2.10 dans la Norme C++ indique std::rotate
- Par ailleurs, si vous avez besoin d'un droit de rotation, l'utilisation d'inverser les itérateurs: std::rotate(s).rbegin(), s.rbegin() + 1, s.rené()); et le String devient "eabcd"
- aussi pour info std::rotate peut être nettement plus rapide que sur un rouleau de votre propre mise en œuvre. donc, si vous voulez vous assurer à la fois la justesse et de la performance, alors il est également bon d'utiliser std::rotate. voir stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast
InformationsquelleAutor Johannes Schaub - litb
11

Voici une solution qui "flotte" le premier caractère de la fin de la chaîne, un peu comme une seule itération de tri à bulles.
```
#include <algorithm>

string rotate(string s) {
  for (int i = 1; i < s.size(); i++)
    swap(s[i-1], s[i]);
  return s;
}
```
si vous souhaitez que la fonction de rotation de la chaîne en place:
```
#include <algorithm>

void rotate(string &s) {
  for (int i = 1; i < s.size(); i++)
    swap(s[i-1], s[i]);
}
```
- Nice rare solution
- Solution élégante!
- Attention à une chose: s'.size() == 0, alors s.size()-1 deviendra 4294...... depuis s.size() n'est pas signé.
- Bonne prise, mis à jour à aller de 1 à s.taille().
- connexes: stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast
InformationsquelleAutor marcog
5

Voici un moyen relativement simple:
```
void RotateStringInPlace(char buffer[])
{
    //Get the length of the string.

    int len  = strlen(buffer);
    if (len == 0) {
        return;
    }

    //Save the first character, it's going to be overwritten.

    char tmp = buffer[0];

    // Slide the rest of the string over by one position.

    memmove(&buffer[0], &buffer[1], len - 1);

    //Put the character we saved from the front of the string in place.

    buffer[len - 1] = tmp;
    return;
}
```
Noter que ceci va modifier le tampon en place.
- Je dirais que c'est plus C qu'en C++, n'est-ce pas?
- +1 pour l'utilisation de memmove au lieu de memcpy (qui n'est pas sécuritaire lorsque les chaînes peuvent se chevaucher).
- Je suppose que vous pourriez dire que c'est plus C qu'en C++, mais il est encore valide en C++, et c'est probablement plus efficace que std::rotation, qui est O(n) dans le nombre de caractères dans la chaîne, alors que cette approche est probablement plus comme O(m) où m est n/(de la taille d'un mot sur votre plate-forme).
- Melski: Votre "O(m)" est la même chose que O(n), juste plus rapide. Big O notation seule mesure comment l'algorithme échelles, non pas à quelle vitesse la mise en œuvre est.
InformationsquelleAutor Eric Melski
5

Il y a une norme faites tourner fonction trouvée dans l'algorithme d'en-tête.

Si vous voulez le faire vous-même, vous pouvez essayer ce qui suit:
```
#include <iostream>
#include <string>

std::string rotate_string( std::string s ) {
    if (s.empty()) return s;

    char first = s[0];

    s.assign(s, 1, s.size() - 1);
    s.append(1, first);

    return s;
}

int main() {
    std::string foo("abcde");

    std::cout << foo << "\t" << rotate_string(foo) <<  std::endl;

    return 0;
}
```
Mais bien sûr, à l'aide de la bibliothèque standard est préférable ici, et dans la plupart des cas.

EDIT #1 j'ai juste vu litb de réponse. Battre à nouveau!

EDIT #2 je veux juste mentionner que le rotate_string fonction échoue sur les chaînes de longueur 0. Vous recevrez un std::out_of_range erreur. Vous pouvez remédier à cela avec un simple bloc try/catch, ou d'utiliser std::rotation 🙂

EDIT #3 Retour sur la même chaîne si la longueur de la chaîne est de 0.

InformationsquelleAutor Nick Presta
1

Est de le faire en place une exigence?

Si non, vous êtes probablement mieux de prendre une sous-chaîne de tous, mais le premier char, et en ajoutant que le premier char à la fin.

InformationsquelleAutor patros
1

Si vous ne voulez pas de ces en place des solutions, puis votre code python peuvent être directement convertis en C++, avec un peu de code supplémentaire pour composer avec le fait que l'indice hors limites est de mauvaises nouvelles en C++.
```
s[1:] --> s.substr(1);
s[:1] --> s[0]; //s[0] is a char not a string, but that's good enough
```
Donc,
```
std::string rotate(const std::string &s) {
    if (s.size() > 0) return s.substr(1) + s[0];
    return s;
}
```
Ce n'est pas le plus efficace: il sera presque certainement faire plus de la chaîne de création que le minimum possible. Mais vous n'avez généralement pas besoin de le plus efficace, et vous avez reserve et append si vous voulez faire la concaténation inutile sans affectation.

InformationsquelleAutor Steve Jessop

À un certain point, j'ai été obsédé par diviser et conquérir, et utilisé les méthodes suivantes

car il "Divise" le problème pour les petits problèmes, ma conjecture est que cela fonctionne mieux.
Commentaires des experts sur la complexité et l'accès à la mémoire de comportement sont les bienvenues :).

Initial Call:
rotate_about(rots_g, 0, i, j - 2);


void rotate_about(char *str, int start, int pivot, int end)
{
    if(pivot == start)
    {
        return ;
    }
    else if((pivot - start) <= (end - pivot))
    {
        int move_bytes = pivot-start;
        swap_bytes(&str[start], &str[pivot],move_bytes);
        rotate_about(str,pivot,pivot+move_bytes,end);
    }
    else
    {
        int move_bytes = end - pivot + 1;
        swap_bytes(&str[start], &str[pivot],move_bytes);
        rotate_about(str, start+move_bytes ,pivot,end);
    }
}

InformationsquelleAutor Meneheune

1

Voici le code en C qui n'utilise pas de fonctions externes:
Elle tourne de la chaîne en place à la fois en avant et en arrière par une valeur de n'importe quelle taille.
```
int stringRotate(int value)
  {
  unsigned long   I,J,K;
  unsigned long   index0;
  unsigned long   temp1,temp2;
  unsigned long   length;

  length = stringLength;

  if (value < 0)
    value = length - ((0 - value) % length);

  if (value > length)
    value = value % length;

  J = 0;
  index0 = J;
  temp1 = stringData[J];

  for (I = 0;I < length;I++)
    {
    K = (J + value) % length;
    temp2 = stringData[K];
    stringData[K] = temp1;

    J = K;

    temp1 = temp2;

    if (J == index0)
      {
      J++;
      index0 = J;
      temp1 = stringData[J];
      }
    }

  return 1;
  }
```
Pour faire tourner la chaîne à la fois en avant et en arrière serait un peu fastidieux de sorte qu'il est mieux de ne faire avant de tourner et de calculer la valeur correcte pour l'arrière.Aussi, si la valeur de rotation est plus que la longueur de la chaîne, puis il nous suffit de le couper, car le résultat serait le même de toute façon.

valeur = longueur - ((0 - valeur) % de la longueur) : signifie que si la valeur de rotation est négatif, puis définissez la valeur de la longueur de la chaîne, moins le résultat positif de la le reste de la division de la valeur par la longueur de la chaîne. Par exemple: la rotation d'une chaîne de caractères de longueur par 10 -9 postes serait la même que la rotation de +1. La rotation de la même chaîne par -19 positions également être la même que la rotation par plus un.
valeur = valeur % de la longueur : signifie que si la valeur positive est plus que la longueur de la corde, puis diviser par la longueur de la chaîne et de prendre le reste. Le résultat serait le même que si nous avons fait le chemin le plus long.

À faire la rotation en place, nous allons avoir besoin de sauter par la valeur de la rotation d'échanger des personnages qui sont loin d'intervalle. Nous commençons à la position zéro, aller de l'avant par la rotation de la valeur et de continuer à sauter de ce montant. si nous allons passé la fin de la chaîne, nous enroulez simplement le début. Le problème est que si la valeur est un nombre pair, nous serons là où nous avons commencé et il va rater tous les caractères illisibles. La variable index0 est là pour indiquer où nous avons commencé à partir. Si nous retrouver à cet indice, alors nous avons besoin de passer par une position d'index et de continuer à sauter. Nous continuons à le faire jusqu'à ce que tous les personnages sont inversés
À ce stade, nous avons besoin de deux variables temporaires pour faire l'échange en place. J est la position de départ. Nous déplacer le personnage à l'indice J de la première variable temporaire. Maintenant, nous I de la boucle de la longueur de la chaîne. K est l'index de destination, J plus la valeur de rotation Enroulé autour de la fin si nécessaire. Déplacer le personnage à l'indice K de la deuxième variable temporaire. Mettre le personnage à partir de l'index J en indice K à l'aide de la première variable temporaire. Par la voie de la raison pour laquelle nous ne déplace pas seulement le caractère directement à partir de l'indice J dans l'indice K est à cause de la dernière partie de la boucle, les indices peuvent changer entre les deux boucles, mais les personnages dans temp1 ne devrait pas.
Maintenant que l'on échange les temp1 avec temp2.
Cette dernière partie est pour le cas où la valeur est un nombre pair et nous sommes de retour là où nous avons commencé. Cela arrive par fois la valeur de rotation moins un. incrément d'indice J par un et réinitialiser les valeurs de départ. Boucle jusqu'à ce que fait.

Une vidéo de démonstration peut être trouvé ici: https://www.youtube.com/watch?v=TMzaO2WzR24

InformationsquelleAutor Guraku

Vous devez vous connecter pour publier un commentaire.