Quelle structure de données en C me permet de stocker des lignes et d'ajouter des lignes facilement ?

Question

J'ai une liste de données de type chaîne. 10,20,30 sont les numéros de ligne

10. string 1
20. string 2
30. string 3

et si l'utilisateur tape "23 string data". 23 est le numéro de la ligne dans laquelle l'utilisateur veut s'insérer. Les données devraient devenir comme ceci

10. string 1
20. string 2
23. string data
30. string 3

et si l'utilisateur tape "40 string data". Les données devraient devenir comme ceci

10. string 1
20. string 2
23. string data
30. string 3
40. string data

Je suis relativement nouveau dans la structure de données du C. Quelle structure de données dois-je utiliser pour stocker efficacement ce type de données ? ? Ma direction actuelle est d'implémenter un tableau dynamique ou une liste liée. Cependant, voici la liste des problèmes que j'ai rencontrés.

Problème avec le tableau dynamique :

1. En utilisant le numéro de ligne comme index et en créant un espace suffisant pour pour s'assurer que la longueur du tableau est toujours égale ou supérieure au numéro de de ligne le plus élevé. Gaspiller beaucoup de mémoire pour un index non utilisé.
2. L'impression des données serait un problème. Par exemple, l'index 0-9 n'a pas de mémoire allouée. Y accéder entraînerait une erreur. Vous devez trouver des moyens de savoir quels index sont utilisés ?

Problème avec la liste liée :

1. Je ne peux pas sauter l'index (pas sûr). Comment identifier la ligne qui vient après une autre et insérer facilement la ligne intermédiaire ?

Answer 1

Supposons que vos besoins soient les suivants :

1. Pas de temps réel fort. (C'est-à-dire qu'il n'est pas destiné au commerce à haute fréquence, ni au contrôle des machines).

2. Il fonctionne sur un PC relativement contemporain (RAM mesurée en Go, fréquence du CPU en GHz). En particulier, il ne fonctionne pas sur un système embarqué.

3. Les données sont pas plus de quelques dizaines de milliers de lignes.

Vous pouvez alors utiliser presque toutes les structures de données que vous voulez ; elles n'auront aucune importance en ce qui concerne la mémoire ou le comportement en cours d'exécution.

Par exemple, pour trouver le point d'insertion dans une liste chaînée, il suffit d'itérer cette liste. Les PC sont suffisamment rapides pour itérer des dizaines de milliers de fois avant que vous n'ayez fini de cligner des yeux.

Ou simplement allouer un tableau de 100 000 lignes de 80 caractères chacune. Aucun problème. Ou d'un million de lignes. Toujours aucun problème. Ou de 10 millions de lignes, toujours pas de problème. Vous voyez où je veux en venir ? (Dans un tableau, vous aurez besoin d'un marqueur pour marquer les lignes inutilisées. J'utiliserais un struct line { bool used; char text[80]; } ou autre. Vous pouvez également répondre à des lignes arbitrairement longues - et économiser de la mémoire - en n'ayant qu'un fichier char *text et l'allouer dynamiquement, ou définir le texte comme une liste liée de morceaux).

Le choix se résume donc à ce qui est le plus facile à utiliser pour vous. Ça pourrait être le tableau.

Answer 2

Je vais vous donner les deux solutions qui me viennent à l'esprit, mais cette question peut rester ouverte.

1. Utilisez une table de hachage. Les clés sont des numéros de ligne. Les valeurs sont (string, pointer to next line's value) . Cela rend l'accès aléatoire et linéaire rapide. Editar: L'insertion est toujours O(n) avec ça. Ça ne fera qu'aider le temps d'accès, qui sera O(1) . La deuxième solution a O(1) l'insertion.

2. En supposant que vous n'ayez pas des numéros de ligne très espacés : Utilisez une liste singulièrement liée L pour stocker des chaînes de caractères. Créez également un tableau séparé P contenant un pointeur sur chaque k -ème nœud de la liste. Pour accéder à la ligne i , vérifier P[floor(i/k)] et passer au nœud qu'il désigne dans L et sauter en avant i mod k fois pour atteindre votre chaîne. Le temps d'accès est donc O(k) . Le temps d'insertion est O(1) . Utilisation de l'espace pour n Les cordes sont O(n + max{i}/k) .

La seule chose qui rend cela pertinent pour le C... est qu'il n'y a pas de table de hachage intégrée, bien sûr ! Donc, #2 peut être plus facile à mettre en œuvre.

Answer 3

Je sais que vous recherchez une structure de données spécialisée, mais que diriez-vous d'utiliser plutôt une simple structure de données mais en la triant paresseusement ? Vous pourriez ajouter de nouvelles lignes à un tableau dynamique, puis trier le tableau (avec la commande qsort ) lorsque vous devez les imprimer.

Je pense que ce serait mieux car l'impression de toutes les lignes est probablement faite beaucoup moins fréquemment que l'ajout/insertion de lignes. Par conséquent, vous devriez faire en sorte que l'ajout de lignes soit bon marché (dans ce cas, O(1) amorti), et que l'impression soit plus coûteuse (dans ce cas, O( n journal n )). Cela permet également de conserver des structures de données simples et de laisser la bibliothèque standard C gérer les parties compliquées.

Vous pourriez encore améliorer la situation en conservant un drapeau qui indique si toutes les données sont déjà triées ; de cette façon, l'impression répétée (ou, en supposant que vous essayez d'écrire un interpréteur BASIC, l'exécution répétée) sera également bon marché. Un tel indicateur peut également être utile si vous pensez que les lignes sont généralement saisie dans l'ordre ; puis au fur et à mesure que chaque ligne est ajoutée :

alreadySorted = alreadySorted && (new_line_number > last_line_number)

Je note que vous n'avez pas précisé ce qui se passe si une ligne est ajoutée qui réutilise un numéro de ligne existant. Si vous souhaitez remplacer l'ancienne ligne, vous pouvez modifier cette approche en utilisant une balise tri stable puis en itérant sur les lignes pour supprimer les lignes avec des numéros en double, en ne gardant que le dernier.

(Si vous voulez faire qsort stable pour ce cas, au lieu de stocker simplement une chaîne pour chaque ligne, vous pourriez stocker des métadonnées supplémentaires avec elle (n'importe quel compteur à croissance monotone ferait l'affaire, comme l'heure actuelle, ou simplement le nombre total de lignes au moment où la ligne a été ajoutée). Ensuite, la fonction de comparaison que vous donnez à qsort aurait juste besoin d'utiliser ces données supplémentaires pour résoudre les liens provenant de numéros de ligne en double).

L'inconvénient de cette approche est que enlever ne seront pas rapides ou ne récupéreront pas immédiatement la mémoire. Cependant, vous n'avez pas précisé si la suppression des lignes est une exigence ; même si c'est le cas, il est probable que ce soit une opération rare (donc être un peu plus efficace en termes de temps ou d'espace pourrait être acceptable).

Answer 4

La meilleure solution pour cette tâche est d'utiliser le type de données dictionnaire. Bien sûr, en fonction de la nature des clés (nombre de lignes), vous pouvez effectuer une optimisation via une table de hachage appropriée.

Bien sûr, la bibliothèque C n'a pas d'implémentation de dictionnaire. Mais vous pouvez créer la vôtre, basée sur l'arbre rouge noir. Cormen a expliqué cette structure de données facilement https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

Remarque : si votre collection est de petite taille ou si vous modifiez rarement la structure, vous pouvez utiliser la liste liée.

Answer 5

Ma suggestion est d'utiliser une liste liée et un tri par insertion pour insérer chaque fois que nécessaire,

Voici le code modifié sur la base d'un extrait de geeksforgeeks.org,

Je n'ai pas testé le code, c'est juste un code modifié tel que pris sur le site.

`/ C program for insertion sort on a linked list /

include<stdio.h>

#include<stdlib.h>

/* Link list node */
struct node
{
    int lineNumber;
    char *str;
    struct node* next;
}node;

// Function to insert a given node in a sorted linked list
void sortedInsert(struct node**, struct node*);

// function to sort a singly linked list using insertion sort
void insertionSort(struct node **head_ref)
{
    // Initialize sorted linked list
    struct node *sorted = NULL;

    // Traverse the given linked list and insert every
    // node to sorted
    struct node *current = *head_ref;
    while (current != NULL)
    {
        // Store next for next iteration
        struct node *next = current->next;

        // insert current in sorted linked list
        sortedInsert(&sorted, current);

        // Update current
        current = next;
    }

    // Update head_ref to point to sorted linked list
    *head_ref = sorted;
}

/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(struct node** head_ref, struct node* new_node)
{
    struct node* current;
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->lineNumber >= new_node->lineNumber)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current->next!=NULL &&
            current->next->lineNumber < new_node->lineNumber)
        {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */

/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while(temp != NULL)
    {
        printf("%d  %s \n", temp->lineNumber,temp->str);

        temp = temp->next;
    }
}

/* A utility function to insert a node at the beginning of linked list */
void push(struct node** head_ref, int new_data, char *line)
{
    /* allocate node */
    struct node* new_node = (struct node *)malloc(sizeof(struct node));
    int len = strlen(line)+1;
    /* put in the data */
    new_node->lineNumber = new_data;

    new_node->str = malloc(len);
    strcpy(new_node->str,line);
    new_node->str[len]  = '\0';

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

// Driver program to test above functions
int main(int argc,char *argv[])
{
    struct node *a = NULL;
    push(&a, 5 , "TestLine");
    push(&a, 1 , "SecondTest");
    push(&a, 1 , "SecondTest");
    push(&a, 3 , "SecondTest");
    insertionSort(&a);

    printf("\nLinked List after sorting \n");
    printList(a);

    return 0;
}`