iulie 22, 2020
Articles
Niciun comentariu

Tabel de căutare cu matrice fixă

Am implementat următorul exercițiu:

Implementați un tabel de căutare cu operații precum find(struct table*, const char*), insert(struct table*, const char*,int) și remove(struct table*, const char*). Reprezentarea tabelului ar putea fi o matrice a unei perechi struct sau a unei perechi de tablouri (const char*[] și int*); alegeți, alegeți și tipurile de returnare pentru funcțiile dvs. 

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define ARR_SIZE 10 struct Pair { const char* word; int val; }; struct Table { struct Pair* pairs[ARR_SIZE]; size_t sz; }; struct Pair* make_pair(const char* word, int val) { assert(word); struct Pair* pair = (struct Pair*)malloc(sizeof(struct Pair)); pair->val = val; pair->word = word; return pair; } void table_empty(struct Table* tbl) { assert(tbl); size_t i = 0; for (i = 0; i < tbl->sz; ++i) { free(tbl->pairs[i]); tbl->pairs[i] = NULL; } tbl->sz = 0; } int search_word(struct Table* tbl, const char* word) { assert(tbl); assert(word); size_t i = 0; for (i = 0; i < tbl->sz; ++i) { //printf("%s %i\n", tbl->pairs[i]->word,i); if (strcmp(tbl->pairs[i]->word, word) == 0) { return i; } } return -1; // error } void table_insert(struct Table* tbl, const char* word, int val) { assert(tbl); assert(word); int i = search_word(tbl, word); if (i != -1) { // replace val tbl->pairs[i]->val = val; } else { // add new pair struct Pair* pair = make_pair(word, val); tbl->pairs[tbl->sz] = pair; // add pair at the last position ++tbl->sz; } } int table_find(struct Table* tbl, const char* word, int* return_val) { assert(tbl); assert(word); assert(return_val); int i = search_word(tbl, word); if (i != -1) { *return_val = tbl->pairs[i]->val; return 0; } return -1; // error not found } int table_remove(struct Table* tbl, const char* word) { assert(tbl); assert(word); int i = search_word(tbl, word); if (i == -1) return -1; free(tbl->pairs[i]); // free value at current pos tbl->pairs[i] = tbl->pairs[tbl->sz - 1]; // put address of last word at the pos of the current --tbl->sz; // "erase" last word return 0; } void table_print(struct Table* tbl) { assert(tbl); printf("\n"); printf("table size = %i\n", tbl->sz); for (int i = 0; i < tbl->sz; ++i) printf("%s %i\n", tbl->pairs[i]->word, tbl->pairs[i]->val); fflush(stdout); } void print_search_result(struct Table* tbl, const char* word) { assert(tbl); assert(word); int val = 0; if (table_find(tbl, word, &val) == 0) printf("%s %i\n",word, val); else printf("%s not found in table\n", word); printf("\n"); fflush(stdout); } void print_remove_result(struct Table* tbl, const char* word) { assert(tbl); assert(word); if (table_remove(tbl, word) == -1) printf("%s not deleted\n", word); else printf("%s deleted\n", word); printf("\n"); fflush(stdout); } int main() { struct Table table = { 0 }; int val = 0; table_insert(&table, "Hello", 10); table_insert(&table, "Test", 15); table_insert(&table, "Hello", 18); // testing overrite val table_insert(&table, "What", 5); table_insert(&table, "is", 3); table_insert(&table, "going", 4); table_insert(&table, "on", 77); table_print(&table); print_search_result(&table, "Hello"); print_search_result(&table, "Test"); print_search_result(&table, "keyword"); print_remove_result(&table, "Hello"); print_remove_result(&table, "Hello"); // double delete == false print_remove_result(&table, "What"); print_remove_result(&table, "going"); print_remove_result(&table, "is"); print_remove_result(&table, "on"); print_remove_result(&table, "Test"); table_print(&table); table_insert(&table, "Hello", 10); table_insert(&table, "Test", 15); table_insert(&table, "Hello", 18); // testing overrite val table_insert(&table, "What", 5); table_insert(&table, "is", 3); table_insert(&table, "going", 4); table_insert(&table, "on", 77); table_print(&table); table_empty(&table); table_print(&table); getchar(); }

Simțiți-vă liber să comentați orice îmbunătățiri. Există o modalitate mai bună de a face acest lucru?

Am și o întrebare specifică: sunt adecvate utilizările mele de assert?

Comentarii

  • Ca titlu stilistic, ‘ recomand * într-un pointer tastați să fie adiacent cu numele variabilei (de ex. const char *word). Sintaxa de tip C a fost concepută pentru a imita utilizarea, de exemplu ‘ d tip *word pentru a accesa un const char element. Rețineți, de asemenea, că acest lucru face mai clar ce tip b este în int *a, b;.

Răspuns

Utilizarea struct

Personal, cred că ați făcut alegerea corectă utilizând un struct cu un char* și int în acesta, mai degrabă decât 2 tablouri de și respectiv int. Pair este o unitate conceptuală de date din aplicația dvs., deci are sens să le puneți împreună. Dacă ați avea 2 tablouri separate, le-ar fi ușor să iasă din sincronizare și să depaneze greu de ce s-a întâmplat asta. Bună treabă!

Prefer const și funcțiile la macro-uri

Ați definit dimensiunea matricei folosind o macro. vă aflați în dezavantaj în timpul programării. Ați eliminat informațiile de tip pentru valoare. Făcându-l: 

const int ARR_SIZE = 10;

veți obține siguranța tipului. Editați: Acel „sa C ++ – ism that doesn” Nu lucrez în C. Rău! Dar restul sfaturilor din paragraful următor sunt corecte din câte știu eu.

Cu macrocomenzile care iau parametri, riscați să fie utilizate în moduri neașteptate și să cauzeze probleme greu de depanat. Din fericire, nu ați făcut asta aici. Dar, în general, dacă vă aflați în căutarea unei macro-uri, întrebați-vă dacă ați fi mai bine cu o constantă sau o funcție. Aproape întotdeauna veți fi (presupunând că puteți utiliza constanta în modul dorit).

Erori

Există unele erori în codul dvs. În make_pair(), nu verificați pentru a vedea dacă malloc() a reușit. Dacă eșuează, nu este alocată nici o memorie și pair indică spre NULL. Când încercați să atribuiți pair->val sau pair->word vă veți bloca.

Dacă ați remediat acest lucru, table_insert() folosește rezultatul make_pair() fără a verifica dacă este primul „s NULL. A câștigat” Nu se blochează imediat, deoarece „doar atribuiți indicatorul matricei în tbl->pairs[tbl->sz] pentru a avea valoarea pair. Ce se va întâmpla mai târziu când dacă încercați să căutați sau să imprimați sau să inserați un alt element, veți primi un blocaj atunci când iterați peste acea intrare din tabel și veți încerca să faceți orice cu el.

Ați putea face aceste erori imposibile dacă nu alocarea dinamică a intrărilor matricei. Pur și simplu faceți din matrice o serie de Pair structuri, mai degrabă decât un indicator către ele.

Denumirea

Multe dintre numele dvs. sunt foarte bune . Pair și Table sunt nume decente, lizibile pentru această sarcină. make_pair(), table_insert() etc. sunt informative. Unele ar putea fi îmbunătățite, totuși. tbl nu vă economisește prea mult tastând peste table. Folosește doar cuvântul întreg. La fel cu sz vs. size. i este acceptabil ca nume de variabilă de buclă, dar ar fi și mai bine dacă ar fi mai descriptiv. De exemplu, entry_index sau pair_index. Ar trebui să descrie ceea ce „reiterați.

Comentarii

  • când schimb definiția în const int ARR_SIZE = 10; îmi dă o eroare în struct Table { struct Pair* pairs[ARR_SIZE]; size_t sz; }; că ARR_SIZE nu este const, deci cum să-l folosim în acest caz atunci?
  • Ne pare rău – că ‘ sa C ++ – ism. Am crezut că este o întrebare C ++. Rău. Mă ‘ îmi voi actualiza răspunsul.
  • Eu ‘ sunt un susținător ferm al numelor de variabile descriptive, dar cu simplitatea buclelor din acest program cred că numele variabilei i funcționează foarte bine.
  • Dacă malloc() eșuează, atribuirea către pair->val sau pair->word s-ar putea bloca, dacă aveți noroc . S-ar putea să continue și să dea rezultate greșite sau poate face ceva total neașteptat. Că ‘ este bucuria comportamentului nedefinit!

Răspuns

  • Nu aruncați rezultatul malloc.

    malloc returnează void *, iar în C este valid să se convertească void * la orice pointer. Dacă trimiteți pentru a suprima un avertisment despre conversia numărului întreg la pointer, înseamnă că un compilator nu are un prototip malloc și implicit este pentru a returna un int (este o convenție antică C). Acum, dacă int și indicatorul sunt de dimensiuni diferite, valoarea de returnare malloc ar fi trunchiată, cu toate consecințele urâte.

  • Nu este recomandat să sizeof(type). Preferați sizeof(expression). În cazul dvs., luați în considerare 

     struct Pair * pair = malloc(sizeof(*pair));

  • table_insert inserează orbește într-un tabel complet. Ar trebui să testeze pentru tbl->sz < ARR_SIZE și returnează o indicație de eroare dacă nu este.

  • Inserarea efectivă 

     struct Pair* pair = make_pair(word, val); tbl->pairs[tbl->sz] = pair; // add pair at the last position

    ar trebui să fie într-adevăr o singură linie: 

     tbl->pairs[tbl->sz] = make_pair(word, val);

Comentarii

  • de ce nu este o idee bună să aruncați malloc? În c ++ ar primi chiar o eroare de compilator?
  • @Sa ndro4912 Întrebarea este etichetată C. C ++ este un limbaj diferit, în special în acest sens. Acum, dacă compilatorul C se plânge, înseamnă că lipsește prototipul malloc, ceea ce poate duce la probleme urâtoare.
  • da, știu că este c. M-am întrebat de ce aici nu este o practică bună să indic schimbările de tip cu o distribuție
  • @ Sandro4912 Vezi editarea.
  • @ Sandro4912 pair = malloc(sizeof *pair) este mai ușor de codat corect prima dată, mai ușor de examinat și de întreținut.

Răspunde

Activează toate avertismente ale compilatorului

Cu un compilator bine activat, for (int i = 0; i < tbl->sz; ++i) ar fi trebuit să avertizeze cu privire la amestecarea semnelor i și tbl->sz, precum și intervalul. Economisiți timp și activați toate avertismentele și utilizați for (size_t i = 0; i < tbl->sz; ++i).

În general, codul este șmecher când utilizați int,size_t aproape interschimbabil . „Ar fi arhitectat și aș folosi numai size_t.

Utilizarea mixtă a copiei superficiale și profunde

make_pair(const char* word, int val) alocă și formează un struct Pair complet nou (copie profundă), dar nu copiază la ce indică word.

Poate 

// pair->word = word; pair->word = strdup(word);

Utilizați const

search_word() nu modifică *tbl, deci utilizați const to convey that. Same for table_find () , table_print () , print_search_result () `. 

// int search_word(struct Table* tbl, const char* word) int search_word(const struct Table* tbl, const char* word)

Denumire

Cod folosește const char* word; totuși nu este un „cuvânt”, ci un șir așa cum este utilizat în strcmp().

—– Adăugări

Încălcarea contractului?

Nimic din cerințele „Implementarea unui tabel de căutare cu operațiuni precum …” nu indică faptul că const char* este un pointer către un șir . Prin urmare, apelarea strcmp() este discutabil dacă nu există cerințe nedeclarate. Ca char *, codul ar putea utiliza o comparație simplă 

// if (strcmp(tbl->pairs[i]->word, word) == 0) if (tbl->pairs[i]->word == word)

Utilizarea assert()

sunt adecvate utilizările mele de afirmare?

Dacă indicatorul char * de adăugat / căutat nu este specificat ca șir , assert(word); nu este corect ca word == NULL nu este cunoscut ca fiind nevalid.

assert(return_val) din table_find(struct Table* tbl, const char* word, int* return_val) este în regulă, totuși aș reproiecta pentru a permite return_val == NULL 

if (i != -1) { // add if (return_val) { *return_val = tbl->pairs[i]->val; } return 0; }

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *