Hier is hoe om datastrukture op die prettige manier met Flutter te leer

Bou speletjies en leer Rekenaarwetenskap.

Datastrukture vorm die grondslag van doeltreffende sagteware-ontwikkeling, maar tradisionele leermetodes laat hulle dikwels abstrak voel en losgekoppel van werklike toepassings. Hierdie artikel volg 'n ander benadering – kombineer teorie met praktiese implementering in Flutter om leer beide boeiend en prakties te maak.

Geïnspireer deur Google se Toegepaste CS met Android , bied hierdie aanpassing vir Flutter 'n interaktiewe manier om Arrays, HashSets en HashMaps te verstaan. In net 3–4 uur sal jy 'n dieper begrip van hierdie fundamentele datastrukture kry terwyl jy dit in 'n sinvolle konteks toepas.

Of jy nou 'n beginner is wat jou CS-grondbeginsels wil versterk of 'n ervare ontwikkelaar wat daarop gemik is om jou vaardighede te verfyn, hierdie gids bied 'n doeltreffende en genotvolle manier om noodsaaklike datastrukture te bemeester. Kom ons begin.

Die doelwitte van hierdie artikel:

1. Vergewis uself van hoe woordeboeke gebruik kan word om data (in hierdie geval woorde) te stoor.
2. Gebruik hash-kaarte om groeperings van woorde, wat anagramme is, te stoor.
3. Die beperkings wat sommige datastrukture ondervind wanneer daar met groot datastelle gewerk word, kan verduidelik.

Voorbereiding:

Ons sal 'n paar datastrukture in die werkswinkelaktiwiteit gebruik, so hersien asseblief Lists , HashSets , en HashMaps . Jy behoort met selfvertroue in staat te wees om elemente in te voeg, uit te vee, toegang te verkry en die bestaan daarvan na te gaan deur hierdie datastrukture in Dart te gebruik.

Dit is 'n klein inleiding tot die datastrukture, HashSets en HashMap.

'n Klein opwarmingsoefening vir beginners:

As 'n voorbeeldaktiwiteit wat HashMaps gebruik, skep 'n program (nie noodwendig 'n Flutter-toepassing nie - opdragreël is goed) wat 'n drieletter-landkode sal inneem (sien ISO-3166 ) en die volle naam van die land waaraan dit behoort terugstuur.

Byvoorbeeld:

 Input | Output ----- | ---------------------------------------------------- GBR | United Kingdom of Great Britain and Northern Ireland IDN | Indonesia IND | India

As 'n uitbreiding, as die invoer groter as 3 letters is, beskou dit as die naam van 'n land en stuur die drieletterkode daarvoor terug. Skryf 'n nuttige foutboodskap as die invoer nie 'n geldige kode of 'n landnaam is nie.

Kom ons begin.

Anagramme

'n Anagram is 'n woord wat gevorm word deur die letters van 'n ander woord te herrangskik. Byvoorbeeld, teater is 'n anagram van iceman .

Die meganika van die spel is soos volg:

1. Die speletjie voorsien die gebruiker van 'n woord uit die woordeboek.

   
   

2. Die gebruiker probeer om soveel woorde as moontlik te skep wat al die letters van die gegewe woord plus een bykomende letter bevat. Let daarop dat dit ongeldig is om die ekstra letter aan die begin of einde by te voeg sonder om die ander letters te herrangskik. Byvoorbeeld, as die speletjie die woord 'erts' as 'n voorgereg kies, kan die gebruiker 'roos' of 'nul' raai, maar nie 'seer' nie.

   
   

3. Die gebruiker kan opgee en die woorde sien wat hulle nie geraai het nie.

Ons het vir jou 'n voorgeregskode verskaf wat 'n woordeboek van 10 000 woorde bevat en die UI-gedeeltes van hierdie speletjie hanteer en jy sal verantwoordelik wees vir die skryf van die AnagramBlocclass wat alle woordmanipulasies hanteer.

Toer deur die Kode

Die aanvangskode bestaan uit drie hoofpyltjieklasse:

anagrams_page.dart

Dit is 'n eenvoudige kode wat die skerm verteenwoordig wat ons hierbo sien. Ons sal 'n blok vir staatsbestuur vir die skerm gebruik. Ons sal begin deur die speletjie op te stel deur 'n gebeurtenis na die blok te stuur en te definieer wat sal gebeur wanneer die skerm op verskillende speletjietoestande reageer.

 import 'package:anagrams/anagrams/bloc/anagram_bloc.dart'; import 'package:anagrams/anagrams/domain/word.dart'; import 'package:anagrams/l10n/l10n.dart'; import 'package:bloc_presentation/bloc_presentation.dart'; import 'package:flutter/material.dart'; import 'package:flutter_bloc/flutter_bloc.dart'; class AnagramsPage extends StatelessWidget { const AnagramsPage({super.key}); @override Widget build(BuildContext context) { return BlocProvider( create: (_) => AnagramBloc() ..add( SetupAnagrams( DefaultAssetBundle.of(context), ), ), child: const AnagramsView(), ); } } class AnagramsView extends StatelessWidget { const AnagramsView({super.key}); @override Widget build(BuildContext context) { final l10n = context.l10n; return Scaffold( appBar: AppBar(title: Text(l10n.anagramAppBarTitle)), body: BlocBuilder<AnagramBloc, AnagramState>( builder: (context, state) { switch (state.status) { case AnagramGameStatus.gameError: return const Center( child: Text('An error occurred'), ); case AnagramGameStatus.loaded: return Padding( padding: const EdgeInsets.all(20), child: ListView( children: const [ _SelectedWord(), SizedBox(height: 20), _AnagramsTextField(), SizedBox(height: 10), _GuessListView(), ], ), ); case AnagramGameStatus.initial: return const Center( child: CircularProgressIndicator(), ); } }, ), floatingActionButton: const _NextWordButton(), ); } } class _SelectedWord extends StatelessWidget { const _SelectedWord(); @override Widget build(BuildContext context) { return BlocSelector<AnagramBloc, AnagramState, String>( selector: (state) => state.currentWord, builder: (context, currentWord) { return Text.rich( TextSpan( text: 'Find as many words as possible that can be ' 'formed by adding one letter to ', children: [ TextSpan( text: currentWord.toUpperCase(), style: const TextStyle(fontWeight: FontWeight.bold), ), TextSpan( text: ' (but that do not contain the substring' ' ${currentWord.toUpperCase()}).', ), ], ), ); }, ); } } class _AnagramsTextField extends StatelessWidget { const _AnagramsTextField(); @override Widget build(BuildContext context) { final controller = TextEditingController(); return TextField( controller: controller, decoration: const InputDecoration( hintText: 'Enter an anagram', border: OutlineInputBorder(), ), keyboardType: TextInputType.text, textInputAction: TextInputAction.done, onSubmitted: (value) { controller.clear(); context.read<AnagramBloc>().add(ProcessWord(value)); }, ); } } class _GuessListView extends StatelessWidget { const _GuessListView(); @override Widget build(BuildContext context) { return BlocSelector<AnagramBloc, AnagramState, List<Word>>( selector: (state) => state.guesses, builder: (context, guesses) { return Column( children: guesses.map((word) { return ListTile( minTileHeight: 0, contentPadding: EdgeInsets.zero, visualDensity: VisualDensity.compact, title: Text(word.value), leading: Icon( word.isAnagram ? Icons.check : Icons.close, color: word.isAnagram ? Colors.green : Colors.red, ), ); }).toList(), ); }, ); } } class _GameResult extends StatelessWidget { const _GameResult(this.currentWord, this.result); final List<Word> result; final String currentWord; @override Widget build(BuildContext context) { return ListView( shrinkWrap: true, children: [ const SizedBox(height: 20), Padding( padding: const EdgeInsets.symmetric( horizontal: 20, ), child: Text( 'Game Result for $currentWord', style: const TextStyle(fontSize: 20), ), ), Padding( padding: const EdgeInsets.all(20), child: SizedBox( width: double.infinity, child: DataTable( decoration: BoxDecoration( border: Border.all( color: Colors.grey.shade400, ), borderRadius: BorderRadius.circular(10), ), columns: const [ DataColumn(label: Text('Possible Anagrams')), DataColumn(label: Text('Your Guesses')), ], rows: result.map((word) { return DataRow( cells: [ DataCell(Text(word.value)), DataCell( Center( child: Icon( word.isAnagram ? Icons.check : Icons.close, color: word.isAnagram ? Colors.green : Colors.red, ), ), ), ], ); }).toList(), ), ), ), ], ); } } class _NextWordButton extends StatelessWidget { const _NextWordButton(); @override Widget build(BuildContext context) { final l10n = context.l10n; return BlocPresentationListener<AnagramBloc, AnagramPresenterEvent>( listener: (context, event) { if (event is FinishGuess) { // show a bottom sheet with the anagrams that were not guessed showModalBottomSheet<void>( context: context, useSafeArea: true, builder: (context) { return _GameResult(event.currentWord, event.result); }, ); } }, child: FloatingActionButton.extended( onPressed: () async { context.read<AnagramBloc>().add(ResetGame()); }, label: Text(l10n.nextWordButton), ), ); } }

• _SelectWord : wys die gekose woord vir die speletjie om anagramme van te vorm.

• _AnagramsTextField : neem die woord in en vuur 'n gebeurtenis af om die woord wat die gebruiker getik het, te verwerk.

• _GuessListView : wys die raaiskote wat die gebruiker ingevoer het en of dit korrek is of nie.

• _NextWordButton : stel die speletjie terug en bied aan die gebruiker al die anagramme van die huidige woord en watter een die gebruiker geraai het.

anagram_states.dart

 enum AnagramGameStatus { initial, loaded, gameError } const minNumAnagrams = 5; const defaultWordLength = 3; const maxDefaultWordLength = 7; @immutable final class AnagramState extends Equatable { factory AnagramState({ AnagramGameStatus status = AnagramGameStatus.initial, List<String> words = const [], String currentWord = '', List<String> anagrams = const [], List<Word> guesses = const [], HashSet<String>? wordSet, HashMap<String, List<String>>? anagramMap, HashMap<int, List<String>>? sizeToWords, int wordLength = defaultWordLength, }) { return AnagramState._( status: status, words: words, currentWord: currentWord, anagrams: anagrams, guesses: guesses, wordSet: wordSet ?? HashSet<String>(), anagramMap: anagramMap ?? HashMap<String, List<String>>(), sizeToWords: sizeToWords ?? HashMap<int, List<String>>(), wordLength: wordLength, ); } const AnagramState._({ required this.status, required this.words, required this.currentWord, required this.anagrams, required this.guesses, required this.wordSet, required this.anagramMap, required this.sizeToWords, this.wordLength = defaultWordLength, }); // The current status of the game final AnagramGameStatus status; // All the words in the game final List<String> words; // Currently chosen word of the game to form anagrams final String currentWord; // All the anagrams for the current word final List<String> anagrams; // All the guesses user has made final List<Word> guesses; // A set of all the words in the game final HashSet<String> wordSet; // A map of anagrams for each word final HashMap<String, List<String>> anagramMap; // Stores the words in increasing order of their length final HashMap<int, List<String>> sizeToWords; final int wordLength; AnagramState copyWith({ AnagramGameStatus? status, List<String>? words, String? currentWord, List<String>? anagrams, List<Word>? guesses, HashSet<String>? wordSet, HashMap<String, List<String>>? anagramMap, HashMap<int, List<String>>? sizeToWords, int? wordLength, }) { return AnagramState( status: status ?? this.status, words: words ?? this.words, currentWord: currentWord ?? this.currentWord, anagrams: anagrams ?? this.anagrams, guesses: guesses ?? this.guesses, wordSet: wordSet ?? this.wordSet, anagramMap: anagramMap ?? this.anagramMap, sizeToWords: sizeToWords ?? this.sizeToWords, wordLength: wordLength ?? this.wordLength, ); } @override List<Object?> get props => [ status, words, currentWord, anagrams, guesses, wordSet, anagramMap, sizeToWords, wordLength, ]; }

AnagramState bevat al die toestandsveranderlikes wat nodig is om die speletjie te laat loop.

• status : hou vas of die speletjie besig is om te laai (aanvanklik), gelaai of een of ander fout gegooi word.
• words : Lys al die woorde uit die lêer word.txt wat vanaf die lêer gelaai is.
• anagrams : hou al die anagramme vir die gekose woord.
• currentword : gekose woord uit 'n woordelys en woord om anagramme van te vorm.
• guesses : Al die keuses wat die gebruiker invoer en of dit reg of verkeerd is.

Ons sal later in die artikel by die res van die besonderhede uitkom.

anagram_bloc.dart

 import 'dart:async'; import 'dart:collection'; import 'dart:convert'; import 'package:anagrams/anagrams/domain/word.dart'; import 'package:bloc_presentation/bloc_presentation.dart'; import 'package:equatable/equatable.dart'; import 'package:flutter/widgets.dart'; import 'package:flutter_bloc/flutter_bloc.dart'; part 'anagram_events.dart'; part 'anagram_states.dart'; class AnagramBloc extends Bloc<AnagramEvent, AnagramState> with BlocPresentationMixin<AnagramState, AnagramPresenterEvent> { AnagramBloc() : super(AnagramState()) { on<SetupAnagrams>(_onSetupAnagrams); on<ProcessWord>(_onProcessWord); on<ResetGame>(_onResetGame); } Future<void> _onSetupAnagrams( SetupAnagrams event, Emitter<AnagramState> emit, ) async { try { // this should not be done here, // but for the sake of simplicity, we will do it here final wordsFile = await event.defaultAssetBundle.loadString('assets/words.txt'); // read each line in the file final words = const LineSplitter().convert(wordsFile); // change the state of the game emit( state.copyWith( status: AnagramGameStatus.loaded, words: words, ), ); // reset the game _onRestartGame(emit); } catch (e) { emit( state.copyWith( status: AnagramGameStatus.gameError, ), ); } } Future<void> _onProcessWord( ProcessWord event, Emitter<AnagramState> emit, ) async { try { final word = event.word.trim().toLowerCase(); if (word.isEmpty) { return; } if (_isGoodWord(word) && state.anagrams.contains(word)) { // remove the word from the list of anagrams // add the word to the list of guesses emit( state.copyWith( anagrams: state.anagrams..remove(word), guesses: [...state.guesses, Word(word, isAnagram: true)], ), ); // if there are no more anagrams, the game is over // call _onResetGame to reset the game if (state.anagrams.isEmpty) { add(ResetGame()); } } else { emit( state.copyWith( guesses: [...state.guesses, Word(word)], ), ); } } catch (e) { // show an error message } } FutureOr<void> _onResetGame(ResetGame event, Emitter<AnagramState> emit) { _onGameFinished(); _onRestartGame(emit); } void _onRestartGame(Emitter<AnagramState> emit) { final starterWord = _pickGoodStarterWord(emit); emit( state.copyWith( status: AnagramGameStatus.loaded, currentWord: starterWord, anagrams: _getAnagrams(starterWord), guesses: [], ), ); } void _onGameFinished() { emitPresentation(FinishGuess(_result, state.currentWord)); } List<Word> get _result { // All the anagrams that were not guessed final notGuessedAnagrams = state.anagrams.map(Word.new).toList(); // All the guesses that were made final guesses = state.guesses.where((word) => word.isAnagram).toList(); // return the list of anagrams that were not guessed return [...guesses, ...notGuessedAnagrams]; } /// create a function to find all the anagrams of the target word List<String> _getAnagrams(String targetWord) { // find all the anagrams of the target word final anagrams = <String>[]; // return the list of anagrams return anagrams; } // ignore: unused_element List<String> _getAnagramsWithOneMoreLetter(String targetWord) { final anagrams = HashSet<String>(); // return the list of anagrams return anagrams.toList(); } /// Picks a good starter word for the game. String _pickGoodStarterWord(Emitter<AnagramState> emit) { const word = 'skate'; return word; } /// Checks if the word is a good word. bool _isGoodWord(String word) { return true; } }

• onSetupAnagrams : Lees die lêer, verdeel die woorde en voeg dit by die lys. Dit vind ook die huidige woord, vind anagramme vir daardie gekose woord en werk die toestand op.

• onProcessWord : Dit is die hanteerder wat geroep word wanneer die gebruiker 'n raaiskoot invoer en die toestand opdateer.
• onReset : Opgeroep om op die volgende woordknoppie te klik en die speletjie terug te stel.
• isGoodWord : Bevestig dat die gegewe woord in die woordeboek is en nie gevorm word deur 'n letter aan die begin of einde van die basiswoord by te voeg nie.
• getAnagrams : Skep 'n lys van alle moontlike anagramme van 'n gegewe woord.
• getAnagramsWithOneMoreLetter : Skep 'n lys van alle moontlike woorde wat gevorm kan word deur een letter by die gegewe woord te voeg.
• pickGoodStarterWord : Kies lukraak 'n woord met ten minste die verlangde aantal anagramme.

Mylpaal 1: Noodsaaklikhede

Die eerste mylpaal fokus op die skep van 'n baie eenvoudige werkprogram. Jy gaan die fondamente implementeer waarop in Mylpale 2 en 3 gebou sal word.

Ons sal aan die anagram_bloc.dart werk.

kry Anagrams

Implementeer getAnagrams wat 'n string neem en al die anagramme van daardie string in ons invoer vind. Ons strategie vir nou sal eenvoudig wees: vergelyk net elke string in words Lys met die invoerwoord om te bepaal of dit anagramme is. Maar hoe sal ons dit doen?

Daar is verskillende strategieë wat jy kan gebruik om te bepaal of twee stringe anagramme van mekaar is (soos om die aantal voorkoms van elke letter te tel), maar vir ons doel sal jy 'n helperfunksie skep (noem dit sortLetters ) wat 'n String neem en nog 'n String met dieselfde letters in alfabetiese volgorde terugstuur (bv. "pos" -> "pos").

Om te bepaal of twee stringe anagramme is, is dan 'n eenvoudige saak om te kontroleer dat hulle dieselfde lengte is (ter wille van spoed) en om te kontroleer dat die gesorteerde weergawes van hul letters gelyk is.

wordSet en anagramMap

Ongelukkig sal die eenvoudige strategie te stadig wees vir ons om die res van hierdie speletjie te implementeer. Dus, ons sal ons onSetupAnagrams moet herbesoek en 'n paar datastrukture vind wat die woorde stoor op maniere wat gerieflik is vir ons doeleindes. Ons sal twee nuwe datastrukture skep (bykomend tot words ):

• 'n HashSet (genoem wordSet ) wat ons sal toelaat om vinnig (in O(1)) te verifieer of 'n woord geldig is.

• 'n HashMap (genoem anagramMap ) wat ons sal toelaat om anagramme te groepeer. Ons sal dit doen deur die sortLetters -weergawe van 'n string as die sleutel te gebruik en 'n Lys van die woorde wat ooreenstem met daardie sleutel as ons waarde te stoor. Byvoorbeeld, ons kan 'n inskrywing van die vorm hê: sleutel: "opst" waarde: ["post", "spot", "potte", "tops", ...].

Terwyl jy die invoerwoorde verwerk, roep sortLetters op elkeen van hulle en kyk dan of anagramMap reeds 'n inskrywing vir daardie sleutel bevat. Indien wel, voeg die huidige woord by List by daardie sleutel. Andersins, skep 'n nuwe een, voeg die woord daarby en stoor dit in die HashMap met die ooreenstemmende sleutel.

Sodra jy dit voltooi het, het jy die einde van Mylpaal 1 bereik! Jy is nou gereed om aan te beweeg na die tweede mylpaal, waar jy meer kompleksiteit by jou program sal voeg.

Oplossing vir mylpaal 1

Mylpaal 2: Voeg kwaliteit by

Mylpaal 2 gaan alles daaroor om te verseker dat die woorde wat gekies is, geskik is vir die anagramspeletjie. Anders as. Die vorige mylpaal, hierdie een word in drie afdelings opgedeel.

isGoodWord

Jou volgende taak is om isGoodWord te implementeer wat kontroleer:

• die verskafde woord is 'n geldige woordeboekwoord (dws in wordSet ), en
• die woord bevat nie die basiswoord as 'n substring nie.

Om te kontroleer of 'n woord 'n geldige woordeboekwoord is, kan bewerkstellig word deur na wordSet te kyk om te sien of dit die woord bevat. Om te kontroleer dat die woord nie die basiswoord as 'n substring bevat nie, word as 'n uitdaging gelaat!

getAnagramsWithOneMoreLetter

Laastens, implementeer getAnagramsWithOneMoreLetter wat 'n string neem en alle anagramme vind wat gevorm kan word deur een letter by daardie woord te voeg.

Maak seker dat jy 'n nuwe List as jou terugkeerwaarde instansieer en kontroleer dan die gegewe woord + elke letter van die alfabet een vir een teen die inskrywings in anagramMap .

Dateer ook die onRestartGame op om getAnagramsWithOneMoreLetter in plaas van getAnagrams op te roep.

pickGoodStarterWord

As jou speletjie werk, gaan voort om pickGoodStarterWord te implementeer om die speletjie interessanter te maak. Kies 'n ewekansige beginpunt in die woordlys en kontroleer elke woord in die skikking totdat jy een kry wat ten minste minNumAnagrams het. Maak seker dat jy omdraai tot aan die begin van die skikking hanteer indien nodig.

Twee-derdes van die pad deur! Net een mylpaal en die uitbreiding voor jy klaar is.

Oplossing vir mylpaal 2

Mylpaal 3: Refaktorering

Op hierdie stadium is die speletjie funksioneel, maar dit kan nogal moeilik wees om te speel as jy met 'n lang basiswoord begin. Om dit te vermy, kom ons herfaktor onSetupGame om woorde van toenemende lengte te gee.

Hierdie refactor begin in die onSetupGame waar jy benewens die invul word ook elke woord in 'n HashMap (kom ons noem dit sizeToWords ) moet stoor wat woordlengte na 'n List van alle woorde van daardie lengte karteer. Dit beteken, byvoorbeeld, jy behoort alle vierletterwoorde in die woordeboek te kan kry deur sizeToWords.get(4) te roep.

In pickGoodStarterWord , beperk jou soektog tot die woorde van lengte wordLength , en sodra jy klaar is, verhoog wordLength (tensy dit reeds by axWordLength is) sodat die volgende aanroep 'n groter woord sal terugstuur.

Oplossing vir mylpaal 3

Uitbreidings

Hierdie aktiwiteit (soos alle toekomstige aktiwiteite) bevat 'n paar opsionele uitbreidings. As die tyd dit toelaat, probeer ten minste een uitbreiding uit die lys hieronder of een wat jy self uitgevind het.

• Tweelettermodus: skakel oor om die gebruiker toe te laat om twee letters by te voeg om anagramme te vorm.

• Optimaliseer woordkeuse deur woorde wat nie genoeg anagramme het nie uit die poel moontlike beginwoorde te verwyder. Let daarop dat daardie woorde in wordSet moet bly, aangesien hulle steeds as anagramme met ander woorde gebruik kan word.

• Tweewoordmodus: Laat die gebruiker toe om een letter by 'n paar woorde te voeg om twee nuwe geldige woorde te vorm.

Baie geluk dat jy dit tot die einde gemaak het! Jy het verken hoe Lists, HashSets en HashMaps kragdoeltreffende datahantering in Flutter doen, net soos in enige goed geoptimaliseerde toepassing. Om hierdie strukture te verstaan, gee jou 'n voorsprong in die skryf van skaalbare en presterende kode. So gaan voort, en gee jouself 'n welverdiende klop op die skouer! Sit nou hierdie kennis in aksie en bou aan wonderlike dinge!