JASON HIRSCHHORN: Benvenuti a tutti alla sezione Seven. Siamo nella settimana di sette del corso. E questo prossimo Giovedi Halloween è così io sono vestita come una zucca. Non riuscivo a piegarmi e mettere su le mie scarpe, ecco perché io sono solo indossando calzini. Non sto anche indossare nulla sotto questo, quindi non posso toglierlo se è distrazione a voi. Mi scuso in anticipo per questo. Non c'è bisogno di immaginare cosa sta succedendo. Sto indossando boxer. Quindi va tutto bene. Ho una storia più lunga sul perché io sono vestita come una zucca, ma ho intenzione di salvo che per avanti in questa sezione perché io voglio iniziare. Abbiamo un sacco di cose interessanti di andare oltre questa settimana. La maggior parte riguarda direttamente a questo set problema della settimana, errori ortografici. Stiamo per andare oltre collegate elenchi e tabelle hash per l'intera sezione. Ho messo questa lista ogni settimana, una lista di risorse per voi per aiutarvi con il materiale in questo corso. Se in perdita o se cerca di qualche ulteriori informazioni, controllare uno dei queste risorse. Anche in questo caso, è pset6 errori di ortografia, pset di questa settimana. E ti incoraggia, e mi incoraggiare, usare qualche altro risorse specificamente per questo pset. In particolare, i tre che ho elencati sullo schermo - gdb, che siamo stati a conoscenza ed è stato usato per un po 'di tempo, è sarà molto utile questa settimana. Così ho messo che fino qui. Ma ogni volta che si lavora con C, si dovrebbe sempre utilizzare gdb eseguire il debug dei programmi. Questa settimana anche valgrind. Qualcuno sa che cosa valgrind fa? AUDIENCE: Verifica le perdite di memoria? JASON HIRSCHHORN: Valgrind i controlli per le perdite di memoria. Quindi, se si malloc qualcosa nella vostra programma, si sta chiedendo per la memoria. Alla fine del programma, è necessario scrivere libera su tutto ciò che hai malloced per dare la memoria indietro. Se non si scrive libero alla fine e il programma arriva ad una conclusione, tutto automaticamente essere liberato. E per i piccoli programmi, è Non un grosso problema. Ma se si sta scrivendo una corsa più lunga programma che non smettere, necessariamente, in un paio di minuti o un paio di secondi, poi perdite di memoria può diventare un affare enorme. Così per pset6, l'aspettativa è che si avrà perdite di memoria a zero con il vostro programma. Per verificare la presenza di perdite di memoria, valgrind eseguire e vi darà qualche bella Uscita ti permette di sapere se o non tutto era gratuito. Ti pratica in un secondo momento oggi, si spera. Infine, il comando diff. Hai usato qualcosa di simile ad esso in pset5 con lo strumento peek. Permesso di guardare dentro. Hai usato anche diff, troppo, per il problema set spec. Ma in voi permesso di confrontare due file. Si potrebbe paragonare il file bitmap e Informazioni intestazioni di una soluzione personale e la soluzione in pset5 se si è scelto di utilizzare. Diff vi permetterà di farlo, pure. È possibile confrontare la risposta corretta per Il problema di questa settimana impostato per la tua risposta e vedere se si allinei o vedere dove gli errori sono. Quindi questi sono tre ottimi strumenti che si consiglia di utilizzare per questa settimana, e controllare definitivamente il programma con questi tre strumenti Prima di accendere dentro Ancora una volta, come ho già detto ogni settimana, se avete tutte le risposte per me - sia positivo e costruttivo - sentitevi liberi di andare al sito nella parte inferiore di questa diapositiva e ingresso lì. Ho davvero apprezzato ogni e tutti i feedback. E se mi dai le cose specifiche che Posso fare per migliorare o che sono facendo bene che mi volete Continuo, mi prendo a cuore e davvero cercare difficile da ascoltare per le vostre risposte. Non posso promettere che ho intenzione di fare tutto, anche se, come indossare un zucca costume ogni settimana. Così ci accingiamo a trascorrere la maggior parte del sezione, come ho detto, parlando liste concatenate e tabelle hash, che saranno direttamente applicabile alla problema impostare questa settimana. Liste concatenate andremo oltre relativamente rapidamente perché abbiamo passato un bel po ' di tempo che va su di esso in sezione. E così ci arriveremo direttamente nel problemi di codifica per le liste collegate. E poi alla fine ne parleremo hash tabelle e come si applicano a questo problema della settimana impostato. Hai visto questo codice prima. Questa è una struttura, e sta definendo qualcosa di nuovo chiamato un nodo. E all'interno di un nodo è un numero intero qui e là è un puntatore a un altro nodo. Abbiamo visto prima. Questo è stato in arrivo per un paio di settimane ormai. Esso combina puntatori, che siamo stati lavorare con, e le strutture, che permettono di combinare due diversi cose in un tipo di dati. Ci sono un sacco di cose su schermo. Ma tutto questo dovrebbe essere relativamente familiarità con voi. Nella prima riga, abbiamo dichiarare un nuovo nodo. E poi all'interno di tale nuovo nodo, ho impostato il numero intero in quel nodo per uno. Vediamo sulla riga successiva sto facendo un printf comando, ma ho visualizzati in grigio il comando printf, perché la realtà parte importante è questa linea qui - new_node.n. Cosa fa il punto significa? PUBBLICO: Andare al nodo e valutare il valore di n per esso. JASON HIRSCHHORN: Ecco esattamente a destra. Dot significa accedere alla parte n di questo nuovo nodo. Questa riga successiva fa che cosa? Michael. AUDIENCE: Crea un altro nodo che punterà al nuovo nodo. JASON HIRSCHHORN: Quindi non lo fa creare un nuovo nodo. Si crea una cosa? PUBBLICO: Un puntatore. JASON HIRSCHHORN: Un puntatore a un nodo, come indicato da questo nodo * qui. Così crea un puntatore a un nodo. E quale nodo si è rivolta a, Michael? AUDIENCE: Nuovo nodo? JASON HIRSCHHORN: Nuovo nodo. Ed è lì che punta perché abbiamo dato l'indirizzo del nuovo nodo. E ora in questa linea vediamo due modi diversi di esprimendo la stessa cosa. E volevo sottolineare come questi due cose sono le stesse. Nella prima riga, abbiamo dereferenziare il puntatore. Così andiamo al nodo. Questo è ciò che significa questa stella. Abbiamo visto che prima con i puntatori. Vai a quel nodo. Questo è tra parentesi. E poi accedere tramite l'operatore punto l'elemento n di tale nodo. Così che sta prendendo la sintassi abbiamo visto proprio qui e ora utilizzarlo con un puntatore. Naturalmente, diventa un po 'affollato, se si sta scrivendo queste parentesi - quella stella e quel puntino. Si diventa un po 'affollato. Così abbiamo un po 'di zucchero sintattico. E questa linea qui - ptr_node-> n. Che fa la stessa cosa esatta. Così, queste due linee di codice sono equivalenti e farà la stessa identica cosa. Ma ho voluto segnalare quelli fuori prima di andare avanti in modo da capire che in realtà questa cosa qui è solo zucchero sintattico per dereferencing il puntatore e poi andare a la parte n di tale struttura. Avete domande su questa diapositiva? OK. Quindi stiamo andando a passare attraverso una coppia di operazioni che si possono fare su liste collegate. Una lista concatenata, di richiamo, è una serie di nodi che puntano l'uno all'altro. E noi di solito cominciamo con un puntatore chiamato testa, in generale, che punta a la prima cosa nella lista. Così, sulla prima riga qui, avere prima il nostro L originale. Quindi, che cosa si può pensare - questo testo proprio qui si può pensare come solo il puntatore che abbiamo memorizzato che da qualche parte i punti al primo elemento. E in questa lista collegata abbiamo quattro nodi. Ogni nodo è una grande scatola. La casella più grande all'interno del grande scatola è la parte intera. E poi abbiamo una parte puntatore. Queste scatole non sono attratti scala perché come è grande un numero intero in byte? Quanto è grande ora? Quattro. E quanto grande è un puntatore? Quattro. Quindi, in realtà, se dovessimo disegnare questo per scalare entrambe le caselle sarebbe la stessa dimensione. In questo caso, vogliamo inserire qualcosa nella lista collegata. Così si può vedere qui stiamo inserendo cinque attraversiamo attraverso l' lista collegata, trovare dove cinque va, quindi inserirla. Rompiamo che verso il basso e andare un po 'più lentamente. Ho intenzione di puntare alla scheda. Così abbiamo la nostra nodo cinque che abbiamo creato in mallocs. Perché tutti ridono? Sto scherzando. OK. Così abbiamo malloced cinque. Abbiamo creato questo nodo da qualche altra parte. Dobbiamo pronto ad andare. Partiamo nella parte anteriore del la nostra lista con due. E vogliamo inserire in modo ordinato. Quindi, se vediamo due e vogliamo mettere in cinque, cosa facciamo quando vediamo qualcosa meno di noi? Cosa? Vogliamo inserire cinque in questo lista collegata, mantenendolo ordinato. Vediamo numero due. Allora cosa facciamo? Marcus? AUDIENCE: Chiamare il puntatore al nodo successivo. JASON HIRSCHHORN: E perché andiamo al prossimo? AUDIENCE: Perché è l' nodo successivo nella lista. E sappiamo solo che altra posizione. JASON HIRSCHHORN: E cinque è maggiore di due, in particolare. Perché vogliamo tenerlo ordinato. Così cinque è maggiore di due. Quindi si passa a quello successivo. Ed ora arriviamo a quattro. E cosa succede quando arriviamo a quattro? Cinque è maggiore di quattro. Quindi noi continuiamo. E ora siamo a sei. E che cosa vediamo alle sei? Sì, Carlos? AUDIENCE: Six è maggiore di cinque. JASON HIRSCHHORN: Six è maggiore di cinque. Ecco, questo è dove vogliamo inserire cinque. Tuttavia, tenere presente che se si hanno un solo puntatore qui - questo è il nostro puntatore in più che è attraversando l'elenco. E stiamo puntando a sei. Abbiamo perso traccia di ciò che viene prima delle sei. Quindi, se vogliamo inserire un elemento in questa lista mantenendolo ordinato, abbiamo probabilmente bisogno di quanti puntatori? AUDIENCE: Two. JASON Hirschorn: Two. Uno per tenere traccia della corrente uno e uno per tenere traccia di quello precedente. Questa è solo una lista concatenata. Va sola direzione. Se avessimo una lista doppiamente concatenata, dove tutto era rivolta verso la cosa dopo di essa e la cosa prima, poi non avremmo bisogno di farlo. Ma in questo caso non vogliamo perdere traccia di ciò che è venuto prima di noi in caso abbiamo bisogno di inserire cinque da qualche parte nel mezzo. Dire che siamo rimasti inseriamo nove. Che cosa accadrebbe se siamo arrivati ​​a otto? PUBBLICO: Dovreste ottenere che il punto zero. Invece di avere punto zero si avrebbe aggiungere un elemento e quindi avere puntare a nove. JASON Hirschorn: Esattamente. Così otteniamo otto. Arriviamo alla fine della lista, perché questo sta puntando a null. E adesso, invece di puntare a nullo dobbiamo puntare al nostro nuovo nodo. E abbiamo impostato il puntatore il nostro nuovo nodo a null. Qualcuno ha domande sull'inserimento? Cosa succede se non mi preoccupo mantenere la lista ordinata? AUDIENCE: Bastone alla inizio o fine. JASON Hirschorn: Bastone a l'inizio o la fine. Quale dovremmo fare? Bobby? Perché alla fine? AUDIENCE: perché l'inizio è già riempito. JASON Hirschorn: OK. L'inizio è già piena. Chi vuole argomentare contro Bobby. Marcus. AUDIENCE: Beh, probabilmente si desidera bastone all'inizio perché altrimenti se lo metti a Alla fine dovreste attraversare l'intero elenco. JASON Hirschorn: Esattamente. Quindi, se stiamo pensando di runtime, l' runtime di inserimento alla fine sarebbe n, la dimensione di questo. Qual è la grande O runtime di inserimento all'inizio? Costante di tempo. Quindi, se non si cura di tenere qualcosa di ordinato, molto meglio solo inserire all'inizio di questa lista. E questo può essere fatto in tempo costante. OK. Operazione successiva è trovare, che altro - abbiamo formulato questo come ricerca. Ma stiamo andando a guardare attraverso il lista collegata per qualche oggetto. Voi ragazzi avete visto il codice per verificare prima in conferenza. Ma abbiamo una sorta di appena fatto con inserire, o almeno inserimento qualcosa ordinati. Si guarda attraverso, andando nodo per nodo, fino a trovare il numero che si sta cercando. Cosa succede se si raggiunge la fine della lista? Dire che sto cercando nove e io raggiungere la fine dell'elenco. Che cosa facciamo? AUDIENCE: Ritorno falso? JASON Hirschorn: Ritorno false. Non abbiamo trovato. Se si raggiunge la fine della lista e Non avete trovato il numero sei cercando, non è lì. Hai domande su trovare? Se questo fosse un elenco ordinato, cosa sarebbe essere diverso per la nostra ricerca? Già. AUDIENCE: Sarebbe trovare il primo valore che è maggiore di quello stai cercando e poi tornare false. JASON Hirschorn: Esattamente. Quindi, se si tratta di un elenco ordinato, se si arriva a qualcosa che è più grande di quello stiamo cercando, non abbiamo bisogno di proseguire fino alla fine della lista. A quel punto possiamo tornare falso perché non stiamo andando a trovarlo. La domanda è ora, abbiamo parlato mantenendo liste collegate ordinati, tenerli indifferenziati. Che sta per essere qualcosa che ti probabilmente andando ad avere per pensare quando la codifica problema impostato cinque se si scegliere una tabella hash con separata approccio concatenamento, che parleremo più avanti. Ma ne vale la pena di tenere aggiornato l'elenco ordinato e quindi essere in grado di avere forse ricerche più rapide? O è meglio per inserire rapidamente qualcosa in runtime costante ma poi avere più la ricerca? Questo è un compromesso proprio lì che si arrivare a decidere che cosa è più appropriato per il problema specifico. E non c'è necessariamente una risposta assolutamente ragione. Ma è certamente una decisione che si ottiene per fare, e probabilmente buona per difendere che, per esempio, un commento o due perché si è scelto uno sopra l'altro. Infine, l'eliminazione. Abbiamo visto l'eliminazione. E 'simile alla ricerca. Cerchiamo l'elemento. Dire che stiamo cercando di eliminare sei. Così troviamo sei proprio qui. La cosa che dobbiamo fare in modo che fare è che tutto ciò che sta puntando sei - come si vede nel passaggio due quaggiù - tutto ciò che sta indicando sei esigenze di saltare sei adesso e essere cambiato qualunque cosa sei sta indicando. Noi non vogliamo orfano sempre il resto della la nostra lista dimenticando di set che puntatore precedente. E poi a volte, a seconda sul programma, faranno solo eliminare del tutto questo nodo. A volte si desidera restituire il valore che è in questo nodo. Ecco come funziona l'eliminazione. Tutte le domande di eliminare? AUDIENCE: Quindi, se avete intenzione di eliminare si, ti basta usare gratuitamente perché presumibilmente fu malloced? JASON Hirschorn: Se si desidera liberare qualcosa che è esattamente a destra e si malloced esso. Dire abbiamo voluto restituire questo valore. Potremmo tornare a sei e poi libero questo nodo e chiamata gratis su di esso. Oppure avremmo probabilmente chiamiamo libero prima e poi tornare a sei. OK. Quindi passiamo alla pratica di codifica. Stiamo andando a codificare tre funzioni. Il primo si chiama insert_node. Così avete il codice che ti ho mandato, e se stai guardando questo più avanti è possibile accedere al codice linked.c sul sito CS50. Ma in linked.c, c'è qualche codice scheletro che è già stato scritto per voi. E poi ci sono un paio di funzioni è necessario scrivere. In primo luogo stiamo andando a scrivere insert_node. E cosa insert_node fa IS inserisce un numero intero. E si sta dando il numero intero in una lista collegata. E in particolare, è necessario per mantenere la lista ordinata dal più piccolo al più grande. Inoltre, non si vuole inserire eventuali duplicati. Infine, come si può vedere insert_node restituisce un bool. Quindi si suppone di consentire all'utente di sapere se l'inserto era di successo, restituendo vero o falso. Alla fine di questo programma - e per questa fase non è necessario preoccuparsi di liberare nulla. Quindi tutto quello che stai facendo è prendere un intero e inserendolo in un elenco. Questo è quello che ti sto chiedendo di fare adesso. Ancora una volta, nel linked.c, che si hanno tutti, è il codice scheletro. E si dovrebbe vedere verso il basso la dichiarazione di funzione di esempio. Tuttavia, prima di andare in codificarlo in C, vivamente vi incoraggio ad andare attraverso le fasi siamo stati praticare ogni settimana. Abbiamo già passati attraverso una foto di questo. Quindi, si dovrebbe avere una certa comprensione di come funziona. Ma vorrei incoraggiarvi a scrivere alcuni pseudocodice prima di tuffarsi dentro E stiamo per andare oltre pseudocodice come gruppo. E poi una volta che hai scritto la tua pseudocodice, e una volta abbiamo scritto il nostro pseudocodice come gruppo, è possibile andare in codifica in C. Come un testa a testa, la funzione insert_node è probabilmente il più difficile di tre stiamo andando a scrivere perché io aggiunto alcuni vincoli aggiuntivi per la programmazione, in particolare, che non avete intenzione di inserire qualsiasi duplicati e che l'elenco dovrebbe rimanere ordinato. Quindi questo è un programma non banale che è necessario codificare. E perché non ti prendi 5-7 minuti solo per ottenere lavorando sulla pseudocodice e il codice. E poi inizieremo andando come un gruppo. Anche in questo caso, se avete appena tutte le domande alzare la mano e vengo in giro. . Abbiamo anche generalmente facciamo questi - o io non esplicitamente dici in grado di lavorare con le persone. Ma, ovviamente, altamente vi incoraggio, se avete domande, chiedere al vicino seduto accanto a te o anche lavorare con qualcuno altrimenti se si vuole. Ciò non deve essere un individuo attività di silenzio. Cominciamo con la scrittura di alcuni pseudocodice sulla scheda. Chi mi può dare la prima linea di pseudocodice per questo programma? Per questa funzione, piuttosto - insert_node. Alden? AUDIENCE: Quindi la prima cosa che ho fatto è stato creare un nuovo puntatore al nodo e inizializzato si punta alla stessa cosa che la lista sta puntando. JASON Hirschorn: OK. Quindi, si sta creando un nuovo puntatore all'elenco, non al nodo. AUDIENCE: Giusto. Già. JASON Hirschorn: OK. E allora cosa vogliamo fare? Cosa c'è dopo? Che dire del nodo? Non abbiamo un nodo. Abbiamo solo un valore. Se vogliamo inserire un nodo, cosa facciamo bisogno di fare prima che possiamo ancora pensare di inserirlo? PUBBLICO: Oh, mi dispiace. abbiamo bisogno di malloc spazio per un nodo. JASON Hirschorn: Excellent. Facciamo - OK. Non possono raggiungere così in alto. OK. Stiamo per scendere, e poi stiamo usando due colonne. Non posso andare che - OK. Creare un nuovo nodo. È possibile creare un altro puntatore alla lista o si può semplicemente utilizzare l'elenco come esiste. Non c'è davvero bisogno di farlo. Quindi creiamo un nuovo nodo. Grande. Questo è quello che facciamo prima. Quali sono le prospettive? AUDIENCE: Aspetta. Dovremmo creare un nuovo nodo adesso o dovremmo aspettare per fare in modo che non ci sono duplicati del nodo sulla lista, prima creiamo? JASON Hirschorn: Bella domanda. Facciamo ritengono che per più tardi perché l' maggior parte del tempo saremo creando un nuovo nodo. Quindi noi terremo qui. Ma questa è una buona domanda. Se creiamo e troviamo un duplicato, quello che dovrebbe facciamo prima di tornare? AUDIENCE: liberarlo. JASON Hirschorn: Già. Probabilmente liberarlo. OK. Che cosa facciamo dopo che abbiamo creare un nuovo nodo? Annie? AUDIENCE: Abbiamo messo la numero nel nodo? JASON Hirschorn: Esattamente. Abbiamo messo il numero - abbiamo malloc spazio. Ho intenzione di lasciare che tutti come una riga. Ma hai ragione. Noi malloc spazio e quindi abbiamo messo il numero dentro Possiamo anche impostare il puntatore parte di esso a null. Questo è esattamente vero. E poi che dire dopo? Abbiamo disegnato questa immagine sul tabellone. Allora cosa facciamo? AUDIENCE: Andiamo attraverso la lista. JASON Hirschorn: Passare attraverso la lista. OK. E che cosa controlliamo per ogni nodo. Kurt, che cosa controlliamo per ogni nodo? AUDIENCE: Vedere se il valore di n tale nodo è maggiore del valore n del nostro nodo. JASON Hirschorn: OK. Ho intenzione di fare - sì, OK. Quindi è n - Sto per dire se il valore è maggiore di questo nodo, allora cosa facciamo? PUBBLICO: Bene, allora inseriamo la cosa giusta prima. JASON Hirschorn: OK. Quindi, se è maggiore di questa, poi vogliamo inserire. Ma vogliamo inserirlo destra prima perché anche noi avremmo bisogno di essere tenere traccia, quindi, di ciò che era prima. Quindi inserire prima. Quindi probabilmente abbiamo perso qualcosa precedenza. Probabilmente abbiamo bisogno di essere tenuta traccia di quello che sta succedendo. Ma ci arriveremo laggiù. Quindi, quale valore è inferiore? Kurt, cosa facciamo se valore è inferiore? AUDIENCE: Poi basta andare avanti meno che non sia l'ultimo. JASON Hirschorn: questo mi piace. Quindi, andare al nodo successivo. Meno che non sia l'ultima - probabilmente stiamo controllando che nei termini di una condizione. Ma sì, il prossimo nodo. E questo è sempre troppo basso, così ci sposteremo qui. Ma se - possono tutti vedere questo? Se siamo uguali cosa facciamo? Se il valore stiamo cercando di inserire è uguale al valore di questo nodo? Sì? AUDIENCE: [incomprensibile]. JASON Hirschorn: Già. Dato questo - Marcus è giusto. Avremmo potuto forse fare qualcosa di diverso. Ma dato che abbiamo creato, ecco dobbiamo liberare e poi tornare. Oh boy. Va meglio? Come sarebbe? OK. Libero e allora cosa facciamo ritorno, [incomprensibile]? OK. Ci manca qualcosa? Allora, dove stiamo tenendo traccia del nodo precedente? PUBBLICO: Penso che sarebbe andare dopo creare un nuovo nodo. JASON Hirschorn: OK. Quindi all'inizio faremo probabilmente - sì, possiamo creare un puntatore a una nuova nodo, come un puntatore nodo precedente e un puntatore nodo corrente. Quindi cerchiamo di inserire qui. Creare attuale e precedente puntatori ai nodi. Ma quando facciamo registriamo tali puntatori? Dove lo facciamo nel codice? Jeff? AUDIENCE: - condizioni di valore? JASON Hirschorn: Quale uno in particolare? PUBBLICO: Sto solo confuso. Se il valore è maggiore di questo nodo, Non vuol dire che si vuole andare al nodo successivo? JASON HIRSCHHORN: Quindi, se il nostro valore è maggiore del valore di questo nodo. PUBBLICO: Sì, allora che ci si vuole andare più giù la linea, giusto? JASON HIRSCHHORN: Giusto. Quindi non inseriamo qui. Se il valore è inferiore a questo nodo, quindi andiamo al nodo successivo - e poi noi inserire prima. PUBBLICO: Aspetta, che è questo nodo e che è il valore? JASON HIRSCHHORN: Bella domanda. Valore per questa definizione di funzione è quello che ci è dato. Così valore è il numero che stiamo dato. Quindi, se il valore è inferiore a questo nodo, abbiamo bisogno di tempo per inserire. Se il valore è maggiore di questo nodo, andiamo al nodo successivo. E torniamo alla domanda iniziale, però, dove - AUDIENCE: Se il valore è maggiore di questo nodo. JASON HIRSCHHORN: E così cosa facciamo qui? Dolce. Questo è corretto. Sto solo andando a scrivere aggiornamento puntatori. Ma sì, con quella attuale si dovrebbe aggiornarlo alla puntare a quello successivo. Tutto il resto stiamo manca? Quindi ho intenzione di scrivere questo codice in gedit. E mentre faccio questo, si può avere un paio di minuti per lavorare sulla codifica questo in C. Così ho ingresso pseudocodice. Una breve nota prima di iniziare. Potremmo non essere in grado di completamente finire questo in tutti i tre di queste funzioni. Ci sono soluzioni corrette a loro che io con la posta elettronica a voi ragazzi dopo la sezione, e sarà essere pubblicato su CS50.net. Quindi io non ti incoraggio a andare a vedere le sezioni. Vi incoraggio a provare questi sul possedere, e quindi utilizzare la pratica problemi per controllare le tue risposte. Essi sono stati progettati per strettamente riguardare e aderire a quello devi fare sul problema set. Quindi vi incoraggio a praticare questo per conto proprio e quindi utilizzare il codice per controllare le vostre risposte. Perché io voglio passare a hash Tavoli a un certo punto nella sezione. Così potremmo non ottenere attraverso di essa tutti. Ma faremo quanto possiamo ora. OK. Cominciamo. Asam, come possiamo creare un nuovo nodo? AUDIENCE: Non struct *. JASON HIRSCHHORN: Quindi noi avere che fino qui. Oh, mi dispiace. Dicevi struct *. PUBBLICO: E poi [? tipo?] nodo o nodo c. JASON HIRSCHHORN: OK. Ho intenzione di chiamarlo new_node così possiamo rimanere coerenti. PUBBLICO: E si desidera impostare tale a testa, il primo nodo. JASON HIRSCHHORN: OK. Così ora questo punta a - quindi questo non ha ancora creato un nuovo nodo. Questo è solo rivolta alla primo nodo nell'elenco. Come faccio a creare un nuovo nodo? Se devo spazio per creare un nuovo nodo. Malloc. E quanto è grande? PUBBLICO: La dimensione della struttura. JASON HIRSCHHORN: L' dimensione della struttura. E qual è la struttura chiama? AUDIENCE: Nodo? JASON HIRSCHHORN: Node. Così malloc (sizeof (nodo)); ci dà lo spazio. Ed è questa linea - una cosa è errato su questa linea. È new_node un puntatore ad una struct? Questo è un nome generico. Che cosa è - nodo, esattamente. Si tratta di un nodo *. E cosa facciamo subito dopo abbiamo malloc qualcosa, Asan? Qual è la prima cosa che facciamo? E se non funziona? PUBBLICO: Oh, verificare se punti al nodo? JASON HIRSCHHORN: Esattamente. Quindi, se si new_node uguale uguale null, cosa facciamo? Questo restituisce un bool, questa funzione. Esattamente. Sembra buono. Qualcosa da aggiungere lì? Aggiungeremo le cose alla fine. Ma che finora sembra buono. Creare puntatori attuali e precedenti. Michael, come faccio a fare questo? AUDIENCE: Avreste fare un nodo *. Dovreste fare uno non per new_node ma per il nodi che già hanno. JASON HIRSCHHORN: OK. Quindi il nodo corrente siamo su. Chiamerò che curr. Bene. Abbiamo deciso che vogliamo mantenere due perché abbiamo bisogno di sapere cosa c'è prima. Che cosa vengono inizializzati? PUBBLICO: Il loro valore nella nostra lista. JASON HIRSCHHORN: Allora, qual è il prima cosa sulla nostra lista? Oppure, come facciamo a sapere dove il inizio della nostra lista è? AUDIENCE: Non è forse passato nella funzione? JASON HIRSCHHORN: Giusto. E 'stata approvata nel proprio qui. Quindi, se è passato nella funzione, il inizio della lista, quello che dovremmo set corrente pari a? AUDIENCE: List. JASON HIRSCHHORN: List. Questo è esattamente vero. Ora ha l'indirizzo l'inizio della nostra lista. E per quanto riguarda precedente? AUDIENCE: Lista meno uno? JASON HIRSCHHORN: Non c'è niente prima. Che cosa possiamo fare per significare nulla? AUDIENCE: Null. JASON HIRSCHHORN: Già. Sembra una buona idea. Perfetto. Grazie. Passare attraverso la lista. Costantino, da quanto tempo stiamo andando per scorrere l'elenco? AUDIENCE: fino a raggiungere nulla. JASON HIRSCHHORN: OK. Quindi, se, mentre, per il ciclo. Cosa stiamo facendo? AUDIENCE: Forse un ciclo for? JASON HIRSCHHORN: Facciamo un ciclo for. OK. PUBBLICO: E diciamo per - fino a quando il puntatore corrente non è uguale a zero. JASON HIRSCHHORN: Quindi, se conosciamo il condizioni, come possiamo scrivere un ciclo Basato questa condizione. Che tipo di un ciclo dovremmo usare? AUDIENCE: While. JASON HIRSCHHORN: Già. Questo rende più senso in base fuori di quello che hai detto. Se vogliamo solo andare in noi sarebbe è sufficiente sapere che cosa, farebbe senso fare un ciclo while. Mentre la corrente non è uguale a null, se il valore è inferiore a questo nodo. Akshar, dammi questa linea. AUDIENCE: Se la corrente-> n n meno di valore. O invertire tale. Passare quella fascia. JASON HIRSCHHORN: Mi dispiace. AUDIENCE: Modificare la staffa. JASON HIRSCHHORN: Quindi, se è maggiore del valore. Perché questo è confusa con l' commento di cui sopra, ho intenzione di farlo. Ma sì. Se il nostro valore è inferiore a questo nodo, cosa facciamo? Oh. Ce l'ho proprio qui. Inserisci prima. OK. Come lo facciamo? PUBBLICO: E 'ancora di me? JASON HIRSCHHORN: Già. AUDIENCE: You - new_node-> next. JASON HIRSCHHORN: Allora, qual è che andare a pari? AUDIENCE: Sta andando a corrente pari. JASON HIRSCHHORN: Esattamente. E così l'altro - cos'altro abbiamo bisogno di aggiornare? AUDIENCE: Controllare se passato è uguale a null. JASON HIRSCHHORN: Se prev - quindi se prev uguale a null. AUDIENCE: Ciò significa che sta andando per diventare il capo. JASON HIRSCHHORN: Ciò significa che è diventato il capo. Allora cosa facciamo? AUDIENCE: Facciamo testa uguale new_node. JASON HIRSCHHORN: Testa uguale new_node. E perché la testa qui, non elencare? AUDIENCE: perché la testa è un globale variabile, che è il punto di partenza. JASON HIRSCHHORN: Sweet. OK. E - AUDIENCE: Allora non altro Prec.-> successiva è uguale new_node. E poi si torna vero. JASON HIRSCHHORN: Dove fare noi mettemmo fine new_node? PUBBLICO: Vorrei - Ho impostato che alla partenza. JASON HIRSCHHORN: Cosa line? PUBBLICO: Dopo il if controllando se è noto. JASON HIRSCHHORN: Proprio qui? PUBBLICO: Farei new_node-> n uguale valore. JASON HIRSCHHORN: Suona bene. Probabilmente ha senso - non lo facciamo bisogno di sapere che siamo sulla lista perché stiamo solo fare con una lista. Così una dichiarazione di funzione migliore per questo è solo per sbarazzarsi di questo tutto e basta inserire un valore in testa. Non abbiamo nemmeno bisogno di sapere quale lista siamo dentro Ma terrò per ora e poi cambiare su di aggiornamento le diapositive e il codice. In modo che sembra buono per ora. Se il valore - che può fare questa linea? Se - cosa facciamo qui, Noah. AUDIENCE: Se il valore è maggiore di curr-> n - JASON HIRSCHHORN: come fare andiamo al nodo successivo? AUDIENCE: Curr-> n è pari a new_node. JASON HIRSCHHORN: Allora n è quale parte della struttura? Il numero intero. E new_node è un puntatore a un nodo. Quindi, quale parte del curr dovremmo aggiornare? Se no n, allora qual è l'altra parte? Noè, cosa c'è dall'altra parte. PUBBLICO: Oh, la prossima. JASON HIRSCHHORN: Avanti, esattamente. Esattamente. La prossima è quella giusta. E cos'altro abbiamo bisogno aggiornare, Noah? PUBBLICO: I puntatori. JASON HIRSCHHORN: So abbiamo corrente aggiornato. AUDIENCE: Prec.-> next. JASON HIRSCHHORN: Già. OK, ci fermiamo. Chi ci può aiutare qui? Manu, che cosa dobbiamo fare? AUDIENCE: Hai avuto modo di impostare uguale a curr-> next. Ma fare prima riga precedente. JASON HIRSCHHORN: OK. Qualcos'altro? Akshar. PUBBLICO: Io non penso che tu sia destinato a cambiare curr-> next. Penso che sei destinato a fare eguali curr curr-> next per andare al nodo successivo. JASON HIRSCHHORN: Mi spiace, dove? Su quale linea? Questa linea? AUDIENCE: Già. Fai curr uguale curr-> next. JASON HIRSCHHORN: Quindi è corretto perché la corrente è un puntatore a un nodo. E vogliamo che puntare alla prossima nodo di ciò che sta facendo attualmente indicato. Curr stessa ha un successivo. Ma se dovessimo aggiornare curr.next, abbiamo sarebbe l'aggiornamento della nota reale sé, non dove questa puntatore stava indicando. Che dire di questa linea, però. Avi? AUDIENCE: Prec.-> uguale prossimo curr. JASON HIRSCHHORN: Quindi, di nuovo, se prev è un puntatore a un nodo, prev-> successivo è l' puntatore effettivo nel nodo. Quindi questo sarebbe un aggiornamento puntatore in un nodo a curr. Non vogliamo aggiornare un puntatore in un nodo. Vogliamo aggiornare precedente. Quindi, come possiamo farlo? AUDIENCE: sarebbe solo prev. JASON HIRSCHHORN: Giusto. Prev è un puntatore a un nodo. Ora stiamo cambiando ad una nuovo puntatore a un nodo. OK Passiamo giù. Infine, questa ultima condizione. Jeff, cosa facciamo qui? AUDIENCE: Se il valore è pari al curr-> n. JASON HIRSCHHORN: Mi dispiace. Oh mio Dio. Cosa? Valore == curr-> n. Che cosa facciamo? AUDIENCE: Faresti liberare la nostra new_node, e poi ci si torna false. JASON HIRSCHHORN: Questo è ciò che abbiamo scritto finora. Qualcuno ha nulla aggiungere prima che facciamo? OK. Proviamo. Il controllo può raggiungere la fine di una funzione non nullo. Avi, cosa sta succedendo? AUDIENCE: dovresti mettere ritorno vero al di fuori del ciclo while? JASON HIRSCHHORN: Non lo so. Sei tu mi vuoi? AUDIENCE: Non importa. No. JASON HIRSCHHORN: Akshar? PUBBLICO: Penso che intendevi mettere return false alla fine del ciclo while. JASON HIRSCHHORN: Allora, dove vuoi che vada? AUDIENCE: Come al di fuori del ciclo while. Quindi, se si esce dal ciclo while che i mezzi di che hai raggiunto alla fine e è successo niente. JASON HIRSCHHORN: OK. Allora cosa facciamo qui? PUBBLICO: Si ritorna falso lì. JASON HIRSCHHORN: Oh, abbiamo farlo in entrambi i luoghi? AUDIENCE: Già. JASON HIRSCHHORN: OK. Dovremmo andare? Oh mio Dio. Mi dispiace. Mi scuso per lo schermo. È un po 'andando fuori di testa su di noi. Quindi scegliere un'opzione. Zero, per il codice, si chiude il programma. Un inserisce qualcosa. Inseriamo tre. L'inserto non ha avuto successo. Io vado a stampare. Io non ho nulla. OK. Forse era solo un colpo di fortuna. Inserire uno. Non è successo. OK. Corriamo attraverso la GDB molto velocemente verificare che cosa sta succedendo. Ricorda gdb. / Il nome del programma ci mette in GDB. È che un sacco di gestire? Il lampeggiante? Probabilmente. Chiudete gli occhi e prendere un po 'profonda respiri se vi stancate di vedere la cosa. Sono in GDB. Qual è la prima cosa che faccio in GDB? Dobbiamo capire cosa sta succedendo qui. Vediamo. Abbiamo sei minuti per capire cosa sta succedendo. Rompere principale. E allora cosa faccio? Carlos? Esegui. OK. Scegliamo un'opzione. E cosa significa N fare? Avanti. Già. AUDIENCE: Non si parla - Non hai detto che la testa, era inizializzato per nulla all'inizio. Ma non avevi detto che era OK. JASON HIRSCHHORN: Andiamo - diamo un'occhiata in GDB, e poi ci torneremo. Ma suona come avete già alcune idee su quello che sta succedendo. Quindi vogliamo inserire qualcosa. OK. Abbiamo inserire. Si prega di inserire un int. Ci inseriamo tre. E poi io sono su questa linea. Come posso fare avviare il debug l'inserto nota funzione? Oh mio Dio. Questo è un sacco. È che andando fuori di testa un sacco? PUBBLICO: Oh, è morto. JASON HIRSCHHORN: Ho appena tirato fuori. OK. AUDIENCE: Forse è il altra estremità del filo. JASON HIRSCHHORN: Wow. Così la linea di fondo - che cosa hai detto? PUBBLICO: Ho detto l'ironia del tecnico difficoltà di questa classe. JASON HIRSCHHORN: Lo so. Se solo avessi avuto il controllo su quella parte. [Incomprensibile] Sembra fantastico. Perché non cominciare a pensare ragazzi quello che avremmo potuto fare di sbagliato, e saremo di nuovo in 90 secondi. Avica, ho intenzione di chiedere a voi come fare all'interno insert_node di debug. Quindi questo è dove abbiamo l'ultima lasciato. Come faccio ad andare dentro insert_node, Avica, per esaminare cosa sta succedendo? Quale comando GDB? Rottura non mi avrebbe portato dentro. Lo sa Marquise? AUDIENCE: Cosa? JASON HIRSCHHORN: Quale comando GDB Io uso per andare all'interno di questa funzione? AUDIENCE: Passo? JASON HIRSCHHORN: Step via S. Questo mi porta dentro. OK. New_node mallocing po 'di spazio. Che tutto sembra proprio andare. Esaminiamo new_node. Ha ottenuto un certo indirizzo di memoria. Diamo un'occhiata - che è tutto corretto. Quindi tutto qui sembra funzionare correttamente. AUDIENCE: Qual è la differenza tra P e display? JASON HIRSCHHORN: P sta per la stampa. E così stai chiedendo qual è la differenza tra questo e questo? In questo caso, nulla. Ma in generale ci sono alcune differenze. E si dovrebbe guardare nel manuale GDB. Ma in questo caso, nulla. Noi tendiamo a usare la stampa, però, perché non abbiamo bisogno di fare molto di più stampare un singolo valore. OK. Quindi siamo sulla linea 80 del nostro codice, Impostazione nodo * curr uguale alla lista. Cerchiamo di stampiamo curr. E 'uguale lista. Dolce. Aspetta. E 'uguale a qualcosa. Non mi sembra giusto. Ci andiamo. È perché in GDB, a destra, se è la linea sei su di esso non ancora eseguita. Quindi è necessario digitare realtà successivo per eseguire la riga prima di vedere i risultati. Così eccoci qui. Abbiamo appena eseguita questa linea, precedente è uguale a null. Quindi, di nuovo, se stampiamo precedente non vedremo nulla di strano. Ma se abbiamo effettivamente eseguiamo che linea, poi vedremo che quella linea ha funzionato. Così abbiamo curr. Quelli sono entrambi buoni. Giusto? Ora siamo su questa linea qui. Mentre curr non è uguale null. Ebbene, che cosa fa curr uguali? Abbiamo appena visto pari a null. Abbiamo stampato fuori. Io stamparlo di nuovo. Così è che il ciclo while andando da eseguire? PUBBLICO: No. JASON HIRSCHHORN: Così, quando ho scritto che linea, vedete abbiamo saltato tutta la strada fino in fondo, restituire false. E poi andremo a restituire false e tornare al nostro programma e eventualmente stampare, come abbiamo visto, l'inserto non ha avuto successo. Così, qualcuno ha qualche idea su cosa dobbiamo fare per risolvere questo problema? Ho intenzione di aspettare fino a quando vedo un paio di mani salire. Noi non eseguiamo questo. Tenete a mente, questa era la prima cosa stavamo facendo. Non ho intenzione di fare una coppia. Io vado a fare un paio. Perché un paio significa due. Ti aspetto per più di due. Il primo inserimento, curr, per default è uguale a null. E questo ciclo viene eseguito solo se curr non è nullo. Così come posso ottenere intorno a questo? Vedo tre mani. Ti aspetto per più di tre. Marcus, cosa ne pensi? PUBBLICO: Beh, se avete bisogno di eseguire più di una volta, basta cambiarlo in un ciclo do-while. JASON HIRSCHHORN: OK. Sarà che risolvere il nostro problema, però? AUDIENCE: In questo caso no, perché di il fatto che l'elenco è vuoto. Allora probabilmente solo bisogno di aggiungere una dichiarazione che, se il ciclo termina allora devi essere alla fine del l'elenco, a quel punto si può semplicemente inserirlo. JASON HIRSCHHORN: questo mi piace. Questo ha un senso. Se il ciclo termina - perché tornerà falso qui. Quindi, se l'uscita dal ciclo, quindi siamo in la fine della lista, o forse l' avviare di una lista se non c'è niente esso, che è la stessa come la fine. Così ora vogliamo inserire qualcosa qui. Così come fa quel codice guarda, Marcus? AUDIENCE: Se hai già ottenuto il nodo malloced, si può solo dire new_node-> next uguale nullo perché deve essere alla fine. Oppure new_node-> equivale prossimo null. JASON HIRSCHHORN: OK. Scusi. New_node-> next uguale nullo perché siamo alla fine. Questo non metterla dentro Come la mettiamo nella lista? Giusto. Questo è solo l'impostazione è uguale a. No come possiamo effettivamente metterlo nella lista? Che cosa sta indicando la fine della lista? AUDIENCE: Head. JASON HIRSCHHORN: Sorry? AUDIENCE: Testa punta alla fine della lista. JASON HIRSCHHORN: Se non c'è nulla in la lista, la testa è rivolta al fine dell'elenco. Così che lavorerà per il primo inserimento. Che dire se ci sono un paio le cose nella lista? Che noi non vogliamo impostare testa pari a new_node. Che cosa vogliamo fare? Sì? Probabilmente precedente. Sarà che lavorare? Ricordiamo che precedente è solo un puntatore a un nodo. Ed precedente è una variabile locale. Quindi questa linea imposterà una variabile locale, precedente, pari o indicando questo nuovo nodo. Che non sarà effettivamente messo nella nostra lista, però. Come abbiamo messo nella nostra lista? Akchar? PUBBLICO: penso che tu fare corrente-> next. JASON HIRSCHHORN: OK. curr-> next. Così ancora una volta, l'unica ragione per cui siamo giù ecco, quello che fa corrente uguale? AUDIENCE: Equals nullo. JASON HIRSCHHORN: E allora cosa succede se facciamo nulla-> next? Cosa si vuole ottenere? Avremo un segmentation fault. AUDIENCE: Do curr uguale a null. JASON HIRSCHHORN: Che è la stessa cosa come precedente, però, perché c'è una variabile locale stiamo impostando uguale a questo nuovo nodo. Torniamo alla nostra immagine di inserire qualcosa. Dire che stiamo inserendo alla fine della lista, quindi proprio qui. Abbiamo un puntatore corrente che è che punta a null e un punto precedente che sta puntando a 8. Quindi cosa abbiamo bisogno di aggiornare, Avi? AUDIENCE: precedente-> next? JASON HIRSCHHORN: precedente-> successivo è quello vogliamo aggiornare perché effettivamente inserirla in la fine dell'elenco. Abbiamo ancora un bug, però, che stiamo andando a correre in. Qual è il bug? Sì? PUBBLICO: E 'intenzione di tornare falso in questo caso? JASON HIRSCHHORN: Oh, è sta andando a restituire false. Ma c'è un altro bug. Quindi abbiamo bisogno di mettere in cambio vero. AUDIENCE: Fa precedente ancora pari nulla in cima alla lista? JASON HIRSCHHORN: ancora So precedente pari nullo all'inizio. Quindi, come possiamo ottenere oltre che? Sì? PUBBLICO: Penso che si possa fare un controllo prima che il ciclo while per vedere se è una lista vuota. JASON HIRSCHHORN: OK. Quindi cerchiamo di andare qui. Fare un controllo. Se - AUDIENCE: Quindi se la testa uguale uguale a null. JASON HIRSCHHORN: Se la testa uguale uguale null - che ci ti dirò se si tratta di un elenco vuoto. PUBBLICO: E poi si fare di testa equivale a nuovo. JASON HIRSCHHORN: Testa uguale new_node? E che altro dobbiamo fare? PUBBLICO: E poi si torna vero. JASON HIRSCHHORN: Non proprio. Ci manca un solo passo. AUDIENCE: New_node prossimo deve puntare a null. JASON HIRSCHHORN: Esattamente, Alden. E allora possiamo restituire true. OK. Ma è ancora una buona idea per fare le cose alla fine della lista, giusto? Bene. Abbiamo ancora potrebbe effettivamente ottenere alla fine della lista. Quindi questo è il codice bene se siamo al fine dell'elenco e ci sono alcuni le cose nella lista? Giusto? Perché abbiamo ancora idea di Marcus. Potremmo uscire da questo ciclo perché siamo alla fine della lista. Quindi cosa vogliamo ancora questo codice qui? PUBBLICO: Sì. JASON HIRSCHHORN: Già. E che cosa dobbiamo cambiare questo? Vero. Fa che il buon suono a tutti fino ad ora? Qualcuno ha - Avi, hai qualcosa da aggiungere? PUBBLICO: No. JASON HIRSCHHORN: OK. Così abbiamo fatto un paio di modifiche. Abbiamo fatto questo controllo prima di siamo andati in un elenco vuoto. Così abbiamo preso cura di una lista vuota. E qui abbiamo preso cura di inserimento qualcosa alla fine dell'elenco. Così sembra che questa presa ciclo while cura delle cose in mezzo, qualche parte nella lista se sono cose nella lista. OK. Corriamo ancora questo programma. Non è successo. AUDIENCE: Non hai fatto esso. JASON HIRSCHHORN: Oh, Non ce l'ho fatta. Buon punto, Michael. Aggiungiamo un make collegato. Linea 87 c'è un errore. Linea 87. Alden, questa era la linea che mi hai dato. Cosa c'è di sbagliato? AUDIENCE: Deve essere null. JASON HIRSCHHORN: Excellent. Esattamente. Dovrebbe essere nullo. Facciamo di nuovo. Compilare. OK. Inseriamo tre. L'inserto ha avuto successo. Diciamo stamparlo. Oh, se solo potessimo controllare. Ma non abbiamo fatto il stampare ancora la funzione. Entriamo qualcos'altro. Che cosa dovremmo entrare? AUDIENCE: Seven. JASON HIRSCHHORN: Seven? PUBBLICO: Sì. JASON HIRSCHHORN: Abbiamo un guasto seg. Così abbiamo trovato uno, ma abbiamo chiaramente non è possibile ottenere due. E '5:07. Così abbiamo potuto eseguire il debug di questo per tre minuti. Ma ho intenzione di lasciarci qui e passare a tabelle hash. Ma ancora una volta, le risposte di questo codice Io con la posta elettronica a voi in un po '. Siamo molto vicini ad esso. I consigliamo vivamente di capire cosa sta succedendo qui e risolverlo. Quindi ti email È questo codice come ben oltre la soluzione - probabilmente la soluzione più tardi. Prima di questo codice. L'altra cosa che voglio fare prima di finale è che non abbiamo liberato nulla. Quindi voglio mostrarvi che cosa valgrind assomiglia. Se corriamo confini valgrind sul nostro programma,. / collegato. Sempre secondo questa diapositiva, abbiamo dovrebbe funzionare valgrind con un certo tipo di opzione, in questo caso - Perdita-check = pieno. Quindi cerchiamo di scrivere valgrind - Perdita-check = pieno. Quindi, questo verrà eseguito valgrind sul nostro programma. Ed ora il programma effettivamente eseguito. Quindi stiamo andando a correre proprio come prima, mettere qualcosa dentro Ho intenzione di mettere in tre. Che funziona. Non ho intenzione di provare a mettere in qualcosa altro, perché stiamo andando a ottenere un falso segmento in quel caso. Così sto solo andando a smettere. E ora vedete qui perdite e sintesi heap. Queste sono le cose buone che che si desidera controllare. Così la sintesi heap - dice, in uso all'uscita - otto byte in un blocco. Che un blocco è l' nodo che malloced. Michael, hai detto prima che un nodo è di otto punture perché ha il numero intero e il puntatore. Ecco, questo è il nostro nodo. E poi si dice che abbiamo utilizzato malloc sette volte e abbiamo liberato qualcosa sei volte. Ma non abbiamo mai chiamato libero, quindi non ho idea di cosa sta parlando. Ma basti dire che quando il programma viene eseguito, malloc viene chiamato in alcuni altri luoghi che non c'è bisogno di preoccuparsi. Così malloc fu probabilmente chiamato in alcuni luoghi. Non abbiamo bisogno di preoccuparsi dove. Ma questo è davvero noi. Questa prima linea è noi. Abbiamo lasciato quel blocco. E si può vedere che qui nel riassunto perdita. Ancora raggiungibile - otto byte in un blocco. Ciò significa che la memoria - abbiamo trapelato che la memoria. Definitivamente perso - qualcosa si perde per sempre. In genere, non sarà vedi nulla. Ancora raggiungibile è generalmente dove vedrai cose, dove si vuole guardare per vedere quale codice si dovrebbe hanno liberato ma si è dimenticato di liberare. E poi se questo non era il caso, se abbiamo fatto tutto gratuito, possiamo controllare quello. Diciamo solo eseguire il programma non mettere in nulla. Vedrete qui in uso in uscita - zero byte in blocchi zero. Ciò significa che non avevamo niente di sinistra quando questo programma terminato. Quindi, prima di girare in pset6, eseguire valgrind e assicurarsi che non si dispone di eventuali perdite di memoria nel vostro programma. Se avete qualunque domande con valgrind, sentitevi liberi di raggiungere. Ma questo è come lo si utilizza. Molto semplice - vedere se si avere in uso all'uscita - tutti i byte in tutti i blocchi. Così stavamo lavorando sul nodo di inserimento. Ho avuto altre due funzioni qui - stampare i nodi e nodi liberi. Anche queste sono funzioni che sono sarà un bene per voi di praticare perché vi aiuterà non solo con questi esercizi di esempio, ma anche sul problema posto. Hanno una mappa su praticamente vicino alle cose si sta andando ad avere a che fare in problema set. Ma io voglio fare in modo Tocchiamo tutto. E le tabelle hash sono essenziali anche per quello che stiamo facendo in questa sezione settimana - o nel problema proposto. Quindi stiamo andando a finire la sezione parlando di tabelle hash. Se notate ho fatto un piccola tabella hash. Non è questo che stiamo parlando in merito, tuttavia. Stiamo parlando di un diverso tipo di tabelle hash. E al suo interno, una tabella hash non è altro che un matrice più una funzione di hash. Stiamo andando a parlare per un po 'solo per assicurarsi che tutti capiscono quello che un funzione hash è. E io ti sto dicendo ora che è niente di più di due cose - una matrice e una funzione hash. E qui sono i passi attraverso che tale opera. Ecco il nostro array. C'è la nostra funzione. In particolare, le funzioni di hash devono fare un paio di cose con questo. Io vado a parlare specificamente su questo problema impostato. E 'probabilmente andando a prendere in una stringa. E che cosa sta andando a tornare? Che tipo di dati? Alden? Ritorno, la vostra funzione di hash? Un numero intero. Quindi questo è ciò che l'hash tabella consiste di - una tabella in forma di matrice e una funzione hash. Come funziona? Funziona in tre fasi. Diamo un tasto. In questo caso, daremo una stringa. Chiamiamo la funzione di hash per passo uno sulla chiave e otteniamo un valore. In particolare, diremo otteniamo un numero intero. Tale numero intero, ci sono molto specifici limiti a ciò che può essere intero. In questo esempio, la serie è di dimensione tre. Quindi, quali numeri può che essere intero. Qual è il range di valori validi per che integer, il tipo restituito di questo hash funzione? Zero, uno e due. Il punto della funzione di hash è quello capire il posto nella matrice dove la nostra chiave sta andando. Ci sono solo tre possibili posti qui - zero, uno, o due. Quindi questa funzione meglio di restituzione zero, uno, o due. Alcuni indice valido in questo array. E poi, a seconda di dove ritorna, potete vedere ci open array inquadrare il valore. Ecco dove abbiamo messo la chiave. Così ci buttiamo nella zucca, usciamo zero. A supporto di matrice 0, abbiamo messo la zucca. Gettiamo nei gatti, usciamo uno. Abbiamo messo gatto in uno. Abbiamo messo in ragno. Scendiamo due. Abbiamo messo ragno a staffa due array. Sarebbe così bello se ha funzionato così. Ma purtroppo, come vedremo, è un po 'più complicato. Prima di arrivare lì, tutte le domande su questa base set-up di una tabella di hash? Questa è l'immagine di esattamente quello che abbiamo disegnato sul tabellone. Ma poiché abbiamo disegnato sulla lavagna, mi Non ho intenzione di andare in ulteriormente. Essenzialmente chiavi, la scatola nera magica - o in questo caso, scatola verde acqua - di un funzione di hash li mette in secchi. E in questo esempio siamo non mettere il nome. Stiamo mettendo il telefono associato numero del nome nel secchio. Ma si potrebbe benissimo solo mettere il nome nel secchio. Questo è solo un quadro di ciò che abbiamo disegnato sulla scheda. Abbiamo potenziali insidie, però. E ci sono due in particolare diapositive che voglio andare oltre. Il primo è di circa una funzione hash. Così ho fatto la domanda, che cosa fa una buona funzione di hash? Io do due risposte. Il primo è che è deterministico. Nel contesto di funzioni hash, cosa significa questo? Sì? PUBBLICO: Si può trovare l' indice in tempo costante? JASON HIRSCHHORN: Che Non è ciò che significa. Ma questa è una buona congettura. Chiunque altro ha una supposizione a cosa significa questo? Che una buona funzione di hash è deterministico? Annie? AUDIENCE: che una chiave può essere mappato solo ad un posto nella tabella hash. JASON HIRSCHHORN: Ecco esattamente a destra. Ogni volta che si mette in zucca, restituisce sempre zero. Se si mette in zucca e il vostro hash funzione restituisce zero, ma ha un probabilità di ritorno qualcosa altro maggiore di zero - così forse si può tornare a volte si o altre due volte - che non è una buona funzione hash. Hai perfettamente ragione. La vostra funzione hash dovrebbe restituire l' stesso intero esatto, in questo caso, per la stessa stringa esatta. Forse restituisce lo stesso intero esatto per la stessa stringa esatta indipendentemente dalla capitalizzazione. Ma in questo caso è ancora deterministica perché le cose più sono mappati sullo stesso valore. Va bene. Finché vi è un solo uscita per un dato ingresso. OK. La seconda cosa è che restituisce indici validi. Abbiamo portato up che in precedenza. Questa funzione hash - oh boy - una funzione di hash deve ritorno indici validi. Così dicono - torniamo a questo esempio. La mia funzione hash conta up le lettere della parola. Questa è la funzione hash. E che restituisce intero. Quindi, se ho la parola A, è andando a tornare uno. E sta andando a mettere un proprio qui. Cosa succede se metto nella parola pipistrello? E 'intenzione di tornare tre. Dov'è bat va? E non va bene. Ma ha bisogno di andare da qualche parte. Questa è la mia tabella di hash, dopo tutto, e tutto deve andare da qualche parte. Allora, dove dovrebbe andare pipistrello? Qualche idea? Indovina? Buone ipotesi? AUDIENCE: Zero. JASON HIRSCHHORN: Perché lo zero? AUDIENCE: Perché tre modulo a tre è pari a zero? JASON HIRSCHHORN: Three modulo tre è zero. Questa è una grande congettura, e questo è corretto. Quindi in questo caso dovrebbe probabilmente andare a zero. Quindi un buon modo per garantire che questo hash funzione restituisce solo gli indici validi è a con modulo per la dimensione della tabella. Se si MODULO qualunque cosa rendimenti tre, si sta andando sempre di ottenere qualcosa tra zero, uno e due. E se questo ritorna sempre sette, e sempre Modulo per tre, sei sempre andando ad ottenere la stessa cosa. Quindi è ancora deterministica se MODULO. Ma che farà in modo che si mai ottenere qualcosa - un settore non valida. In generale, tale modulo dovrebbe accadere all'interno della vostra funzione di hash. Quindi non c'è bisogno di preoccuparsi di questo. È solo possibile garantire che questo è un indice valido. Tutte le domande su questo potenziale problema? OK. E ci andiamo. Avanti potenziale insidia, e questo è quello grande. Che cosa succede se due tasti mappa allo stesso valore? Quindi ci sono due modi per gestire questo. Il primo si chiama lineare sondaggio, che sono non intenzione di andare oltre. Ma è necessario avere familiarità con il modo che funziona e di cosa si tratta. La seconda ho intenzione di andare oltre perché è quello che molti persone probabilmente finirà per decidere da utilizzare nel loro insieme problema. Naturalmente, non è necessario. Ma per il set problema, molte persone tendono a scegliere di creare una tabella hash con concatenazioni separate da implementare loro vocabolario. Quindi stiamo intenzione di andare oltre ciò che significa per creare una tabella hash con concatenazioni separate. Così ho messo in zucca. Esso restituisce zero. E ho messo la zucca qui. Poi ho messo in - che cosa è un'altra cosa Halloween a tema? AUDIENCE: Candy. JASON HIRSCHHORN: Candy! Questo è un grande. Ho messo in caramelle e caramelle Mi dà anche zero. Cosa faccio? Tutte le idee? Perché tutti voi sapete sorta di ciò concatenazioni separate è. Quindi, tutte le idee che cosa fare? Già. AUDIENCE: Mettere la stringa effettivamente nella tabella hash. JASON HIRSCHHORN: Così stiamo andando a disegnare la buona idea qui. OK. AUDIENCE: Avere la hashtable [Incomprensibile] il puntatore che punta a l'inizio di un elenco. E poi hanno la zucca essere il primo valore in tale lista collegata e caramelle essere il secondo valore in quella lista collegata. JASON HIRSCHHORN: OK. Marcus, che era eccezionale. Io vado a rompere che verso il basso. Marcus sta dicendo di non sovrascrivere zucca. Che sarebbe male. Non mettere caramelle da qualche altra parte. Stiamo andando a metterli entrambi a zero. Ma stiamo andando ad affrontare mettendoli a zero creazione di un elenco a zero. E stiamo andando a creare un elenco di tutto ciò che mappato a zero. E il modo migliore che abbiamo imparato a creare una lista che può crescere e ridursi non è dinamicamente all'interno un altro array. Quindi non un array multi-dimensionale. Ma per creare solo una lista collegata. Così che cosa ha proposto - Ho intenzione di ottenere un nuovo - è creare un array con i puntatori, un array di puntatori. OK. Qualsiasi idea o suggerimento che tipo di questi puntatori dovrebbe essere? Marcus? AUDIENCE: Puntatori a - JASON HIRSCHHORN: Perché ha detto una lista collegata, così - AUDIENCE: puntatori nodo? JASON HIRSCHHORN: puntatori nodo. Se le cose nel nostro collegati elenco sono nodi poi dovrebbe essere puntatori nodi. E cosa uguali inizialmente? AUDIENCE: Null. JASON HIRSCHHORN: Null. Quindi c'è la cosa vuota. Ritorna zucca zero. Che cosa facciamo? Camminare me attraverso di essa? In realtà, Marcus già mi ha dato. Qualcun altro me a piedi attraverso di essa. Cosa facciamo quando - questo sembra molto simile a quello che stavamo solo facendo. Avi. PUBBLICO: Vado a prendere una congettura. Così, quando si arriva caramelle. JASON HIRSCHHORN: Già. Beh, abbiamo ottenuto la zucca. Prendiamo il nostro primo. Abbiamo ottenuto zucca. AUDIENCE: OK. Ritorna zucca zero. Così si mette in questo. O addirittura, lo metti nella lista collegata. JASON HIRSCHHORN: Come facciamo a metterlo nella lista collegata? PUBBLICO: Oh, la sintassi? JASON HIRSCHHORN: Solo a piedi - dire di più. Che cosa facciamo? AUDIENCE: Devi solo inserire come primo nodo. JASON HIRSCHHORN: OK. Così abbiamo il nostro nodo, zucca. E ora come faccio inserisco? PUBBLICO: È possibile assegnare al puntatore. JASON HIRSCHHORN: Quale puntatore? PUBBLICO: Il puntatore a zero. JASON HIRSCHHORN: Allora, dove fa questo punto? PUBBLICO: A nulla adesso. JASON HIRSCHHORN: Beh, è rivolto a null. Ma sto mettendo in zucca. Allora, dove dovrebbe puntare? PUBBLICO: Per zucca. JASON HIRSCHHORN: Per zucca. Esattamente. Quindi questo indica zucca. E da dove viene questo puntatore al punto di zucca? A AUDIENCE: Null. JASON HIRSCHHORN: NULL. Esattamente. Così abbiamo appena inserito qualcosa nella lista collegata. Abbiamo appena scritto questo codice per fare questo. Quasi abbiamo quasi ottenuto completamente incrinato. Ora inseriamo caramelle. La nostra caramella va anche a zero. Allora cosa facciamo con la caramella? AUDIENCE: Dipende se o Non stiamo cercando di risolvere. JASON HIRSCHHORN: Ecco esattamente a destra. Dipende se o non stiamo cercando di risolvere. Supponiamo che non siamo andando a risolverlo. PUBBLICO: E allora, come abbiamo discusso prima, è semplice basta metterlo proprio all'inizio in modo che il puntatore da zero punti a caramella. JASON HIRSCHHORN: OK. Aspetta. Permettetemi di creare caramelle proprio qui. Quindi questo puntatore - PUBBLICO: Sì, ora dovrebbe si punta a caramelle. Poi hanno il puntatore da Punto di caramelle per la zucca. JASON HIRSCHHORN: Ti piace questo? E dire che abbiamo ottenuto un altro cosa per mappare a zero? PUBBLICO: Beh, basta fare la stessa cosa? JASON HIRSCHHORN: Fate la stessa cosa. Quindi, in questo caso, se non lo facciamo desidera mantenere ordinati esso suoni piuttosto semplice. Prendiamo il puntatore Indice dato dalla nostra funzione di hash. Dobbiamo quel punto il nostro nuovo nodo. E poi qualunque cosa puntava precedentemente - in questo caso nulla, nella secondo caso pumpkin - che, qualunque cosa sta puntando a precedenza, si aggiunge nella successiva il nuovo nodo. Stiamo inserendo qualcosa all'inizio. In realtà questo è molto più semplice di cercando di mantenere la lista ordinata. Ma ancora una volta, la ricerca sarà più complicato qui. Avremo sempre di andare fino alla fine. OK. Avete domande su concatenazioni separate? Come funziona? Si prega di chiedere adesso. Ho molta voglia di assicurarsi che tutti i capire questo prima di testa fuori. AUDIENCE: Perché metti la zucca e caramelle nella stessa parte della tabella hash? JASON HIRSCHHORN: Bella domanda. Perché li mettiamo nella stessa parte della tabella hash? Beh, in questo caso la nostra funzione di hash restituisce zero per entrambi. Quindi hanno bisogno di andare a zero indice perché è lì che stiamo andando a cercarli, se mai voglia di guardare in su. Anche in questo caso, con un approccio scansione lineare noi non li avremmo messi entrambi a zero. Ma nell'approccio catena separata, stiamo andando a metterli entrambi a zero e quindi creare un elenco off pari a zero. E noi non vogliamo sovrascrivere zucca solo per questo, perché allora faremo per scontato che la zucca era mai inserito. Se ci limitiamo a tenere una cosa in posizione che sarebbe male. Allora non ci sarebbe possibilità di noi ha mai - se abbiamo mai avuto un duplicato, poi abbiamo sarebbe solo cancellare il nostro valore iniziale. Ecco perché facciamo questo approccio. O è per questo che abbiamo scelto - ma ancora una volta, abbiamo ha scelto l'approccio concatenazioni separate, che ci sono molti altri approcci si può scegliere. Questo risponde alla tua domanda? OK. Carlos. Scansione lineare comporterebbe - se abbiamo trovato una collisione a zero, abbiamo apparirebbe nel punto successivo per vedere se era aperto e messo lì. E poi guardiamo nel prossimo sport e vedere se era aperto e metterlo lì. Così troviamo il successivo luogo aperto e messo lì. Tutte le altre domande? Sì, Avi. AUDIENCE: Come un follow-up a ciò, cosa si intende per il prossimo posto? Nella tabella hash o in una lista collegata. JASON HIRSCHHORN: Per lineari programmazione, liste collegate. Il punto successivo sulla tabella hash. AUDIENCE: OK. Quindi la tabella di hash sarebbe inizializzato alla dimensione - come il numero di stringhe che si stava inserendo? JASON HIRSCHHORN: Lo faresti voglio che sia davvero grande. Sì. Ecco una foto di quello che abbiamo appena richiamato sulla scheda. Ancora una volta, abbiamo una collisione proprio qui. a 152. E vedrete che abbiamo creato una lista collegata fuori di esso. Anche in questo caso, la tabella hash concatenazioni separate approccio non è quello che si prendere per impostare i problemi sei, ma è uno che un sacco di gli studenti tendono a prendere. Quindi, su questa nota, parliamo brevemente prima di testa fuori per il problema sei, e poi io condividere una storia con te. Abbiamo tre minuti. Problema set di sei. Avete quattro funzioni - carico, controllare, le dimensioni e scarico. Load - bene, stiamo andando sopra il carico solo ora. Abbiamo disegnato il carico sul bordo. E abbiamo anche iniziato la codifica di un sacco di inserimento in una lista collegata. Così carico non è molto più di quello che abbiamo fatto appena. Arrivo è una volta che avete qualcosa caricato. E 'lo stesso processo come questo. Le stesse prime due parti in cui si passi qualcosa nella funzione di hash e ottenere il suo valore. Ma ora non stiamo inserirla. Ora stiamo cercando. Ho scritto il codice di esempio per la ricerca qualcosa in una lista collegata. Vi incoraggio a praticare questo. Ma intuitivamente trovare qualcosa sta molto simile a inserire qualcosa. Infatti, abbiamo disegnato un quadro di trovare qualcosa in una lista collegata, spostando attraverso finché si è giunti alla fine. E se avete ottenuto alla fine e non poteva lo trova, allora non c'è. Ecco, questo è il check, in sostanza. Avanti è la dimensione. Saltiamo dimensioni. Finalmente hai scarico. Scaricamento è uno che non abbiamo disegnato sul bordo o ancora codificate. Ma vi incoraggio a provare la codifica è nel nostro campione lista d'esempio. Ma scarico intuitivamente è simile a gratis - o che voglio dire è simile a controllare. Tranne che per ora ogni volta che si sta andando attraverso, non stai semplicemente controllando vedere se avete il vostro valore lì. Ma stai prendendo quel nodo e liberandola, essenzialmente. Questo è quello che scarico si chiede di fare. Tutto libero che hai malloced. Quindi stai passando l'intera lista nuovamente, passando attraverso l'intero hash Tavolo di nuovo. Questa volta non controlla per vedere cosa c'è. Basta liberare cosa c'è. E infine le dimensioni. Dimensione dovrebbe essere attuato. Se non si implementa dimensioni - Dirò come questo. Se non si implementa dimensioni esattamente una riga di codice compresa la ritorno economico, si è facendo formato errato. Quindi assicuratevi dimensioni, per la progettazione completa punti, si sta facendo esattamente quello riga di codice, compreso l'istruzione return. E non le valigie ancora, Akchar. Castoro Eager. Volevo dire grazie ragazzi per venire a sezione. Avere un Happy Halloween. Questo è il mio costume. Sarò indossare questo il Giovedi se ti vedo in orario di ufficio. E se siete curiosi di sapere un po 'di più come sfondo a questo costume, si sentono libero di controllare 2011 sezione per una storia sul perché io sono indossare il costume da zucca. Ed è una storia triste. Quindi assicuratevi di avere alcuni tessuti vicini. Ma su questo, se avete qualche domande che ti attaccano intorno fuori dopo la sezione. Buona fortuna per il problema definito sei. E come sempre, se avete qualche domande, fammi sapere.