Zaimplementowałem następujące ćwiczenie:
Zaimplementuj tabela przeglądowa z operacjami takimi jak
find(struct table*, const char*),insert(struct table*, const char*,int)iremove(struct table*, const char*). Tabela może być tablicą składającą się zstructpary lub par tablic (const char*[]iint*); wybierz, wybierz także typy zwracania dla swoich funkcji.
#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(); } Zapraszam do komentowania wszelkich ulepszeń. Czy jest lepszy sposób na zrobienie tego?
Mam również jedno konkretne pytanie: czy moje zastosowania assert są odpowiednie?
Komentarze
Odpowiedz
Używając struct
Osobiście uważam, że dokonałeś właściwego wyboru, używając struct z char* i int zamiast 2 tablicami char* i int. Pair to pojęciowa jednostka danych w Twojej aplikacji, więc warto je połączyć. Gdybyś miał 2 oddzielne tablice, łatwo byłoby im stracić synchronizację i trudno byłoby ustalić, dlaczego tak się stało. Dobra robota!
Preferuj const i funkcje zamiast makr
Zdefiniowałeś rozmiar tablicy za pomocą makra. W ten sposób w niekorzystnej sytuacji podczas programowania. Usunąłeś informacje o typie dla wartości. Robiąc to:
const int ARR_SIZE = 10; uzyskujesz bezpieczeństwo typów. Edycja: To jest „C ++ – ism that doesn” t pracować w C. Moja wina! Ale reszta porady w następnym akapicie jest poprawna, o ile wiem.
W przypadku makr, które pobierają parametry, istnieje ryzyko, że zostaną użyte w nieoczekiwany sposób i spowodują trudne do debugowania problemy. Na szczęście nie zrobiłeś tego tutaj. Ale ogólnie, jeśli zdarzy ci się sięgnąć po makro, zadaj sobie pytanie, czy lepiej byłoby, gdybyś miał stałą lub funkcję. Prawie zawsze tak będzie (zakładając, że możesz użyć stałej w żądany sposób).
Błędy
W Twoim kodzie są błędy. W make_pair() nie sprawdzasz, czy jeśli malloc() powiodło się. Jeśli to się nie powiedzie, żadna pamięć nie zostanie przydzielona, a pair wskazuje na NULL. Przy próbie przypisania pair->val lub pair->word nastąpi awaria.
Jeśli to naprawiłeś, table_insert() używa wyniku make_pair() bez sprawdzania, czy najpierw jest to „s NULL. Ten wygrał” t awarii natychmiast, ponieważ „przypisujesz po prostu wskaźnik tablicy w tbl->pairs[tbl->sz], aby uzyskać wartość pair. Co się stanie później, gdy jeśli spróbujesz wyszukać, wydrukować lub wstawić inny element, wystąpi awaria podczas iteracji tego wpisu w tabeli i próby zrobienia z nim czegokolwiek.
Możesz uniemożliwić te błędy, jeśli nie dynamiczne przydzielanie wpisów tablicy. Po prostu utwórz tablicę jako tablicę struktur Pair zamiast wskaźnika do nich.
Nazewnictwo
Wiele z twoich nazw jest naprawdę dobrych . Pair i Table to przyzwoite, czytelne nazwy tego zadania. make_pair(), table_insert() itp. mają charakter informacyjny. Jednak niektóre można by ulepszyć. tbl nie oszczędza dużo pisania w table. Po prostu użyj całego słowa. To samo dotyczy sz i size. i jest akceptowalna jako nazwa zmiennej pętli, ale byłoby jeszcze lepiej, gdyby była bardziej opisowa. Na przykład entry_index lub pair_index. Powinien opisywać, nad czym „powtarzasz iterację”.
Komentarze
- po zmianie definicji na
const int ARR_SIZE = 10;wyświetla mi się błąd wstruct Table { struct Pair* pairs[ARR_SIZE]; size_t sz; };, że ARR_SIZE nie jest stałą, więc jak w takim razie użyć go w takim przypadku? - Przepraszam – że ' w języku C ++. Myślałem, że to pytanie w C ++. Mój błąd. ' zaktualizuję swoją odpowiedź.
- I ' Jestem zagorzałym zwolennikiem opisowych nazw zmiennych, ale dzięki prostocie pętli w tym programie myślę, że nazwa zmiennej
idziała dobrze. - Jeśli
malloc()nie powiedzie się, przypisywanie dopair->vallub może zawiesić się, jeśli masz szczęście . Może po prostu trwać i dawać złe wyniki lub może spowodować coś zupełnie nieoczekiwanego. To ' to radość z niezdefiniowanego zachowania!
Odpowiedź
-
Nie rzutuj wyniku
malloc.malloczwracavoid *, aw C można przekonwertowaćvoid *na dowolny wskaźnik. Jeśli rzutujesz w celu pominięcia ostrzeżenia o konwersji liczby całkowitej na wskaźnik, oznacza to, że kompilator nie ma prototypumalloci domyślnie zwracaint(to starożytna konwencja języka C). Teraz, jeśliinti wskaźnik mają inny rozmiar, wartość zwracana przez malloc zostanie obcięta, ze wszystkimi nieprzyjemnymi konsekwencjami. -
Nie zaleca się
sizeof(type). Preferujsizeof(expression). W Twoim przypadku rozważstruct Pair * pair = malloc(sizeof(*pair)); -
table_insertślepo wstawia do pełnej tabeli. Powinien sprawdzać, czytbl->sz < ARR_SIZEi zwróć informację o błędzie, jeśli tak nie jest. -
Rzeczywiste wstawienie
struct Pair* pair = make_pair(word, val); tbl->pairs[tbl->sz] = pair; // add pair at the last positionpowinno być naprawdę jedną linią:
tbl->pairs[tbl->sz] = make_pair(word, val);
Komentarze
- dlaczego rzutowanie malloc nie jest dobrym pomysłem? W C ++ nawet wystąpiłby błąd kompilatora?
- @Sa ndro4912 Pytanie jest oznaczone C. C ++ to inny język, szczególnie w tym zakresie. Jeśli kompilator C narzeka, oznacza to, że brakuje prototypu
malloc, co może prowadzić do nieprzyjemnych problemów. - tak, wiem, że to c. Zastanawiałem się tylko, dlaczego tutaj nie jest dobrą praktyką wskazywanie zmian typu za pomocą rzutowania
- @ Sandro4912 Zobacz edycję.
- @ Sandro4912
pair = malloc(sizeof *pair)jest łatwiejszy do poprawnego zakodowania za pierwszym razem, łatwiejszy do przejrzenia i utrzymania.
Odpowiedź
Włącz wszystkie ostrzeżenia kompilatora
Przy dobrze włączonym kompilatorze for (int i = 0; i < tbl->sz; ++i) powinien był ostrzec o mieszaniu oznaczeń i i tbl->sz oraz range. Oszczędzaj czas i włącz wszystkie ostrzeżenia i używaj for (size_t i = 0; i < tbl->sz; ++i).
Ogólnie kod jest mało skomplikowany przy używaniu int,size_t prawie zamiennie . Przebudowuję architekturę i używam tylko size_t.
Mieszane użycie płytkiej i głębokiej kopii
make_pair(const char* word, int val) przydziela i tworzy zupełnie nowy struct Pair (głęboka kopia), ale nie kopiuje tego, na co word wskazuje.
Być może
// pair->word = word; pair->word = strdup(word); Użyj const
search_word() nie modyfikuje *tbl, więc użyj 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) Nazewnictwo
Kod używa const char* word;, ale nie jest to „słowo”, ale ciąg używany w strcmp().
—– Dodatki
Naruszenie umowy?
Nic w wymaganiach „Zaimplementuj tabelę przeglądową z operacjami takimi jak …” nie wskazuje, że const char* jest wskaźnikiem do ciągu znaków . Wywołanie strcmp() jest wątpliwa, chyba że istnieją nieokreślone wymagania. Jako char * kod może używać prostego porównania
// if (strcmp(tbl->pairs[i]->word, word) == 0) if (tbl->pairs[i]->word == word) Zastosowanie assert()
Czy moje zastosowania assert są właściwe?
Jeśli char * wskaźnik dodawania / wyszukiwania nie jest określony jako ciąg , assert(word); nie jest prawidłowy, ponieważ word == NULL nie jest nieprawidłowy.
assert(return_val) w table_find(struct Table* tbl, const char* word, int* return_val) jest w porządku, ale przeprojektowałbym, aby zezwolić na return_val == NULL
if (i != -1) { // add if (return_val) { *return_val = tbl->pairs[i]->val; } return 0; }
*we wskaźniku wpisz obok nazwy zmiennej (np.const char *word). Składnia typu C została zaprojektowana tak, aby naśladować użycie, gdzie na przykład ' d wpisz*word, aby uzyskać dostęp doconst charelement. Zwróć również uwagę, że dzięki temu jest bardziej jasne, jaki typbznajduje się wint *a, b;.