Programme C pour faire une deuxième copie d'une liste chaînée

J'ai écrit un code C pour copier le contenu d'une Liste chaînée sur une autre liste. Je veux savoir si il existe un moyen plus efficace de le faire.

Ce qui est mieux?

struct node *copy(struct node *start1)
{
struct node *start2=NULL,*previous=NULL;

while(start1!=NULL)
{
    struct node * temp = (struct node *) malloc (sizeof(struct node));
    temp->info=start1->info;
    temp->link=NULL;

    if(start2==NULL)
    {
        start2=temp;
        previous=temp;
    }
    else
    {
        previous->link=temp;
        previous=temp;          
    }
    start1=start1->link;
}
return start2;
}

OU

struct node *copy(struct node *start1)
{
    if(start1==NULL) return;
    struct node *temp=(struct node *) malloc(sizeof(struct node));
    temp->info=start1->info;
    temp->link=copy(start1->link);
    return temp;
}
Vous êtes à la recherche pour l'exécution de l'efficacité, ou d'un plus compact/moyen élégant de faire cela?
Façon plus élégante de le faire, je suppose.
Que vous devriez le faire récursive.
De manière récursive, à faire il serait très élégant, mais vous devez faire attention de peur que vous DÉBORDEMENT de la PILE. Heheehehe, les jeux de mots à écrire eux-mêmes aujourd'hui. Mais plus sérieusement, vous pouvez seulement de manière récursive jusqu'à présent, sauf si vous utilisez une queue récursive de la langue, qui C ne l'est pas.
Les vrais hommes utilisent goto pour la récursivité 😉 Même si, certains compilateur C implémentations (i.e. GCC avec les extensions?) est possible d'optimiser le TCO dans certains cas .. mais il doit être TCO'able pour commencer.

OriginalL'auteur Vivek | 2012-11-29

  1. 5

    Pour la copie d'une liste liée à une autre liste liée, vous avez pas d'autre option mais à parcourir et copie les valeurs de la seconde, dans un total de O(n)temps.
    Vous êtes déjà de le faire. Il est aucun moyen de faire mieux, sauf s'il existe une relation entre les éléments qui sont stockés.

    Une solution récursive peut-être mieux de regarder, mais il sera en fait moins efficace.

    Edit: Pour la question changé

    La version Itérative est mieux.

    Remarque : LOC n'a pas de rapport direct avec l'efficacité.

    Est-il possible de réduire le nombre de lignes de code au moins?
    Les lignes de code n'a rien à voir avec l'efficacité. Votre question portait sur l'amélioration de l'efficacité et je pense que j'ai répondu 🙂
    Merci pour ur réponses
    vous pouvez réduire le nombre de lignes. voir ma réponse
    Mais il ne sera pas nécessairement le rendre efficace. En Plus (voir mon commentaire.

    OriginalL'auteur axiom

  2. 1

    Sans aller récursive, c'est le plus compact, vous pouvez obtenir:

    struct node *copy(struct node *org)
{
struct node *new=NULL,**tail = &new;

for( ;org; org = org->link) {
    *tail = malloc (sizeof **tail );
    (*tail)->info = org->info;
    (*tail)->link = NULL;
    tail = &(*tail)->link;
    }
return new;
}

    OriginalL'auteur wildplasser

  3. 1

    Pour vitesse, il peut en effet être une meilleure façon de le faire. Comme toujours, la seule façon de le savoir est à l'indice de référence.

    • En fonction du coût relatif de la itération
      • (qui peut lui-même dépend de comment et dans quel ordre vous avez réservé vos nœuds, ainsi que de cache et de la mémoire de l'architecture)
    • contre free store allocation
      • (qui peuvent dépendre de l'état de votre tas, combien d'autres threads sont susceptibles d'être accéder, le physique, l'état de la mémoire dans l'OS hôte, etc.)

    • il peut être plus rapide:

      • passer une itération de comptage de la longueur de la liste d'origine

        int len = 0;
for (start2 = start1; start2 != NULL; start2 = start2->link)
    ++len;

      • allouer de l'espace pour tous les nœuds requis dans un seul bloc

        struct node *temp = malloc(len * sizeof(*temp));

      • et puis passer une seconde itération de lier votre tableau de nœuds

        int i = 0;
for (start2 = start1; start2 != NULL; start2 = start2->link) {
    temp[i].info = start2->info;
    temp[i].link = &temp[i+1];
}
temp[len-1].link = NULL;

    Comme je l'ai dit, je ne suis pas prometteur, il sera être plus rapide (et c'est certainement plus laid), mais il peut être sur certains systèmes, avec certains compilateurs, sous certaines conditions. Bien sûr, c'est un non-starter si le reste de votre code suppose que vous pouvez free nœuds individuels.

    Pour élégance, la récursivité naturellement gagne.

    La simple approche itérative est généralement va être un bon compromis, même si, entre élégant, mais peut exploser à moins que vous ayez une belle TCO-ing compilateur et ci-dessus, ce qui est franchement un peu moche et bénéficieraient d'un commentaire explicatif.

    Eh bien, j'étais l'écriture d'un programme, pour cette question, parce qu'il était dans l'exercice de mes Structures de Données de Livre de Texte. Merci pour l'aperçu sur l'efficacité! 🙂

    OriginalL'auteur Useless