tipos - ¿Se pueden usar cadenas como un índice de matriz?

tipos de cadenas para nieve

Question

¿Se puede usar una cadena como índice de matriz en C?

Ej: valor correspondiente a la cadena "ONE" 1 "TWO" 2 "CINCO" 5 "DIEZ" 10

Cuando se pasa una cadena en la lista anterior a la función, la función debe devolver el valor correspondiente indicado anteriormente. ¿Se puede lograr esto al declarar una matriz constante con cadena como índice?

int *x;
x["ONE"]  = 1;
x["TWO"]  = 2;
x["FIVE"] = 5;
x["TEN"]  = 5;

return x["string received by the function"];

La lógica anterior no funciona como se esperaba; ¿Hay alguna solución para implementar la lógica anterior para tener una matriz indexada por cadenas?

Answer 1

Como ya se indicó, necesita una matriz asociativa o un mapa hash o equivalente. Una posible fuente de dicho código son las " C Interfaces e Implementaciones " de Hanson (código en Google Code - verifique los términos de la licencia, etc. antes de usarlo).

Answer 2

Deberá escribir una función que asigne cadenas a enteros o, alternativamente, utilice enumeraciones en todo (y luego tal vez una función que asigne valores enumerados a cadenas).

En general, es más agradable hacer lo último: pasar enteros, de modo que la implementación no dependa de los detalles de las cadenas que podrían usarse en la representación. Por ejemplo, piense cómo manejaría la localización (traducción) si alguna vez necesita hacer que esas cadenas sean agradables para alguien que habla un idioma diferente.

Answer 3

En "C simple" puede imitar el uso de una cadena como un índice, pero no del todo como usted lo desea. Sin embargo, hacerlo rara vez es útil y, en general, es una forma excelente de hacer que su código sea ilegible. Lo que parece querer es poder usar claves de cadena en un diccionario (o "tabla de hash", si lo prefiere) y no hay una estructura de datos incorporada para eso en C. El diseño exacto dependería de lo que querer (y, de hecho, si esto es parte de la tarea, puede que ni siquiera necesite usar una implementación de tabla hash completa, pero probablemente podría salirse con la codificación estática menos eficiente).

Un ejemplo usando una cadena (OK, una matriz char) en la "posición del índice" de una construcción a [b]:

int main (void)
{
  char *str = "This is a test string";
  int x;

  for (x=0; x < 12; x += 3)
    putchar(x[str]);

  printf("/n");

  return 0;
}

Lo anterior es, hasta donde puedo decir, legal C, con un resultado bien definido (la cadena "Tss ssi"). Se basa en el hecho de que a [b] se define como igual a * (a + b).

Answer 4

Hay otras respuestas excelentes para lo que debe hacer, así que pensé en explicar lo que está haciendo y por qué se está compilando y no está funcionando.

En C, la referencia de matriz se hace teniendo una matriz o puntero y un entero de algún tipo. (en x [1], x es la matriz y 1 es el número entero). Siempre que use un tipo integral, funcionará como espera.

Supongamos que tiene algo que no es un número entero. En ese caso, la implementación C verá si puede convertirlo al tipo apropiado, por lo que terminará con una matriz y un número entero. Es en casos como este donde te metes en problemas (y versiones ligeramente más sofisticadas de esto en C ++ han confundido a personas más experimentadas que tú).

En C, una cadena literal como "uno" es de tipo const char *, lo que significa puntero a caracteres que no puede cambiar. El valor real es la dirección de memoria de donde la cadena reside realmente en la memoria. Normalmente, no prestaría atención a este valor de puntero, y miraría el valor de la cadena, pero aquí hay un problema.

En C, cualquier puntero de datos se puede convertir a algún tipo de entero, y será automáticamente. Por lo tanto, tiene una cadena como "uno", y su valor es cualquier número que represente la dirección de memoria. Úselo donde C espera algún tipo de número entero, y se convertirá a algún valor integral u otro.

Por lo tanto, esto es lo que está sucediendo con x ["ONE"]. El sistema C tiene que poner la cadena "ONE" en algún lugar de la memoria, y no importa dónde. Es probable que esté en algún lugar con una dirección de memoria bastante grande, posiblemente en miles de millones. Cuando ve x ["ONE"], intenta convertir ese valor a un entero y lo usa como un subíndice. Por lo tanto, está intentando acceder a la matriz x mucho más allá de sus límites, y eso está causando el problema. O intentas usar la memoria que no tienes permitido, y el sistema simplemente te detiene, o estás robando con un trozo de memoria que deberías estar dejando solo, y es probable que falle de alguna manera misteriosa más adelante.

Answer 5

Lo que estás buscando es probablemente el equivalente de una matriz asociativa que no se puede proporcionar con el mismo azúcar sintáctico en C, lamentablemente, sin algunos resultados tontos.

Sin embargo, lo que puede proporcionar es un hashmap si sus datos se ajustan a los pares clave -> valor. Lo que necesitará es una función hash apropiada.

Aquí hay un ejemplo simple decente de una tabla hash:

http://www.cl.cam.ac.uk/~cwc22/hashtable/

Answer 6

Puede compilar, pero no funcionará.

No está del todo claro lo que estás tratando de lograr. Creo que desea una matriz asociativa , en cuyo caso debe encontrar una implementación de biblioteca de una.

Si buscas algo más parecido a un tipo enumerado y puedes confiar en C89 , mira algo como:

enum cardsuit {
   CLUBS,
   DIAMONDS,
   HEARTS,
   SPADES
};

Si no puedes confiar en C89, entonces deberías probar algunos trucos typedef .

Answer 7

Puede crear fácilmente tablas de búsqueda con la función bsearch() proporcionada por stdlib.h . Un ejemplo de trabajo es esto:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define count(ARRAY) (sizeof(ARRAY)/sizeof(*ARRAY))

struct item
{
    const char * name;
    int value;
};

static _Bool sorted;

static struct item items[] =
{
    { "one", 1 },
    { "two", 2 },
    { "three", 3 },
    { "ten", 10 }
};

static int compare(const void * p1, const void * p2)
{
    return strcmp(*((const char **)p1), *((const char **)p2));
}

int get(const char * name)
{
    if(!sorted)
    {
        qsort(items, count(items), sizeof(*items), compare);
        sorted = 1;
    }

    struct item * item = bsearch(&name, items, count(items), sizeof(*items),
        compare);

    return item ? item->value : 0;
}

int main(int argc, char ** argv)
{
    int i;
    for(i = 1; i < argc; ++i)
        printf("%i/n", get(argv[i]));

    return 0;
}

Answer 8

Este es un hilo viejo, pero pensé que esto aún podría ser útil para cualquiera que busque una implementación. No requiere demasiado código; Hice la mía en ~ 100 líneas sin ninguna biblioteca adicional como sugirió Hank Gay. Lo llamé un diccionario porque es paralelo (tipo de) el tipo de datos python. Aquí está el código:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct hollow_list hollow_list;

struct hollow_list{
    unsigned int size;
    void *value;
    bool *written;
    hollow_list *children;
};

//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
    hollow_list output;
    output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
    return output;
}

//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
    int i;
    for(i = 0; i < l->size; i++){
        hollow_list_free(l->children + i, free_values);
    }
    if(free_values){
        free(l->value);
    }
    free(l);
}

//Reads from the hollow list and returns a pointer to the item''s data
void *hollow_list_read(hollow_list *l, unsigned int index){
    if(index == 0){
        return l->value;
    }
    unsigned int bit_checker;
    bit_checker = 1<<(l->size - 1);
    int i;
    for(i = 0; i < l->size; i++){
        if(bit_checker & index){
            if(l->written[i] == true){
                return hollow_list_read(l->children + i, bit_checker ^ index);
            } else {
                return (void *) 0;
            }
        }
        bit_checker >>= 1;
    }
}

//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
    if(index == 0){
        l->value = value;
    } else {
        unsigned int bit_checker;
        bit_checker = 1<<(l->size - 1);
        int i;
        for(i = 0; i < l->size; i++){
            if(bit_checker & index){
                if(!l->written[i]){
                    l->children[i] = hollow_list_create(l->size - i - 1);
                    l->written[i] = true;
                }
                hollow_list_write(l->children + i, bit_checker ^ index, value);
                break;
            }
            bit_checker >>= 1;
        }
    }
}

typedef struct dictionary dictionary;

struct dictionary{
    void *value;
    hollow_list *child;
};

dictionary dictionary_create(){
    dictionary output;
    output.child = malloc(sizeof(hollow_list));
    *output.child = hollow_list_create(8);
    output.value = (void *) 0;
    return output;
}

void dictionary_write(dictionary *dict, char *index, unsigned int strlen, void *value){
    void *hollow_list_value;
    dictionary *new_dict;
    int i;
    for(i = 0; i < strlen; i++){
        hollow_list_value = hollow_list_read(dict->child, (int) index[i]);
        if(hollow_list_value == (void *) 0){
            new_dict = malloc(sizeof(dictionary));
            *new_dict = dictionary_create();
            hollow_list_write(dict->child, (int) index[i], new_dict);
            dict = new_dict;
        } else {
            dict = (dictionary *) hollow_list_value;
        }
    }
    dict->value = value;
}

void *dictionary_read(dictionary *dict, char *index, unsigned int strlen){
    void *hollow_list_value;
    dictionary *new_dict;
    int i;
    for(i = 0; i < strlen; i++){
        hollow_list_value = hollow_list_read(dict->child, (int) index[i]);
        if(hollow_list_value == (void *) 0){
            return hollow_list_value;
        } else {
            dict = (dictionary *) hollow_list_value;
        }
    }
    return dict->value;
}

int main(){
    char index0[] = "hello, this is a test";
    char index1[] = "hello, this is also a test";
    char index2[] = "hello world";
    char index3[] = "hi there!";
    char index4[] = "this is something";
    char index5[] = "hi there";

    int item0 = 0;
    int item1 = 1;
    int item2 = 2;
    int item3 = 3;
    int item4 = 4;

    dictionary d;
    d = dictionary_create();
    dictionary_write(&d, index0, 21, &item0);
    dictionary_write(&d, index1, 26, &item1);
    dictionary_write(&d, index2, 11, &item2);
    dictionary_write(&d, index3, 13, &item3);
    dictionary_write(&d, index4, 17, &item4);

    printf("%d/n", *((int *) dictionary_read(&d, index0, 21)));
    printf("%d/n", *((int *) dictionary_read(&d, index1, 26)));
    printf("%d/n", *((int *) dictionary_read(&d, index2, 11)));
    printf("%d/n", *((int *) dictionary_read(&d, index3, 13)));
    printf("%d/n", *((int *) dictionary_read(&d, index4, 17)));
    printf("%d/n", ((int) dictionary_read(&d, index5, 8)));
}

Desafortunadamente no se puede replicar la sintaxis de la lista [x], pero esta es la mejor alternativa que se me ocurrió.