insérer dans le tableau trié

Je veux insérer un élément dans le bon endroit que l'ordre maintient dans la liste triée.
J'ai attribué 2*n la taille de la matrice et rempli le reste avec 999, car ils ne sont pas utilisés actuellement.

ordered_insert(int number,int array[],int size){
 int i=0;
 int temp1,temp2,index;
 while(eleman>array[i]){
   i++;}

//push the rest to right by one
index=i;

if(i<size){
    temp1=array[i];
    temp2= array[i+1];
    array[i+1]=temp1;
    array[i+2]=temp2;
    i++;
    }

array[index]=number;

}

Je ne pouvais pas comprendre comment le remplacer 999s ou est-il une meilleure façon de faire à la place?

  • L'utilisation de la boucle de maj reste du tableau (ou memmove si ce n'est pas une école d'affectation).
  • Il y a une question similaire, here mais je ne trouve pas les réponses très satisfaisantes. Google recherche binaire position d'insertion pour trouver de meilleurs résultats, y compris rosettacode.org/wiki/Binary_search
  • En fonction de votre utilisation (par exemple, nombre d'insertions), ce type d'opération serait mieux adapté d'une liste liée au lieu d'un tableau.
InformationsquelleAutor Ege | 2013-11-26
  1. 2

    Pour déplacer tous les derniers éléments du tableau d'une étape à l'avance, vous aurez à parcourir le tableau en arrière de sorte que vous ne pas écraser les éléments.

    Une fois que vous obtenez l'indice,

    int i = size;
while ( i > index ) {
  array[i] = array[i-1];
  i--;
}
array[i] = number;
size++;
    InformationsquelleAutor Abhishek Bansal
  2. 1

    vous pouvez

    memmove(&array[i+1], &array[i], (size - i) * sizeof array[i]);

    EDIT:

    La 999 truc n'est pas nécessaire; il suffit de noter le nombre d'éléments utilisés dans size (et ajouter de limites appropriées contrôles).

    InformationsquelleAutor ensc
  3. 0

    Pour pousser le reste de la matrice de l'élément, vous devez utiliser une boucle.
    Juste être carfare vous devriez commencer à pousser à partir du dernier élément sinon vous allez affecter le reste des éléments ayant la même valeur

    int i=size-1; //Not i=size (this is the size of the array not the last index)
while (i>index){
array[i] = array[i-1];
i--;
}
array[i] = number;

    sur l'attribution d'éléments non utilisés avec 999 il n'est pas obligatoire il suffit de définir une touche pour rappeler le dernier élément et l'utiliser au lieu de la taille, puis lors de l'insertion d'un nouvel élément, il suffit de vérifier si vous avez atteint la taille de la matrice.

    • Vous devriez commencer à partir de i = taille parce que vous ajoutez un élément. Sinon, vous êtes plus que l'écriture du dernier élément.
    • Si l'aide d'une clé, vous devriez commencer à partir de la dernière utilisation de l'indice+1 mais si l'aide de la taille cela signifie que le nombre d'octets non pas le dernier indice de la matrice de sorte que vous devez soustraire 1 pour obtenir le dernier indice sinon vous allez dépasser la taille du tableau.
    InformationsquelleAutor rullof
  4. 0
    //1. initialise i (the 'hole' index) to the last element in the array
//2. if the preceeding array element is larger than the newValue
//3.   move the preceeding element into the 'hole' at i, moving the hole up a position
//4.   reverse through the array
//5. else put the newValue into the hole and we're done 

i = ARRAY_SIZE-1;  
while (i>0 && array[i-1]>newValue) {
  array[i] = array[i-1];
  i--;
}
array[i] = newValue;
    InformationsquelleAutor push2eject