Galleria mappe mentale struttura dati
Struttura dei dati, che organizza il contenuto principale e la struttura logica dei concetti di base della struttura dei dati, aiuta a comprendere e ricordare i punti di conoscenza ed è adatto per la revisione dell'esame!
Modificato alle 2024-03-27 14:56:11Questa è una mappa mentale su una breve storia del tempo. "Una breve storia del tempo" è un'opera scientifica popolare con un'influenza di vasta portata. Non solo introduce i concetti di base della cosmologia e della relatività, ma discute anche dei buchi neri e dell'espansione dell'universo. questioni scientifiche all’avanguardia come l’inflazione e la teoria delle stringhe.
Dopo aver letto "Il coraggio di essere antipatico", "Il coraggio di essere antipatico" è un libro filosofico che vale la pena leggere. Può aiutare le persone a comprendere meglio se stesse, a comprendere gli altri e a trovare modi per ottenere la vera felicità.
"Il coraggio di essere antipatico" non solo analizza le cause profonde di vari problemi nella vita, ma fornisce anche contromisure corrispondenti per aiutare i lettori a comprendere meglio se stessi e le relazioni interpersonali e come applicare la teoria psicologica di Adler nella vita quotidiana.
Questa è una mappa mentale su una breve storia del tempo. "Una breve storia del tempo" è un'opera scientifica popolare con un'influenza di vasta portata. Non solo introduce i concetti di base della cosmologia e della relatività, ma discute anche dei buchi neri e dell'espansione dell'universo. questioni scientifiche all’avanguardia come l’inflazione e la teoria delle stringhe.
Dopo aver letto "Il coraggio di essere antipatico", "Il coraggio di essere antipatico" è un libro filosofico che vale la pena leggere. Può aiutare le persone a comprendere meglio se stesse, a comprendere gli altri e a trovare modi per ottenere la vera felicità.
"Il coraggio di essere antipatico" non solo analizza le cause profonde di vari problemi nella vita, ma fornisce anche contromisure corrispondenti per aiutare i lettori a comprendere meglio se stessi e le relazioni interpersonali e come applicare la teoria psicologica di Adler nella vita quotidiana.
struttura dati
introduzione
Concetti base di struttura dei dati
dati
elemento di dati, elemento di dati
Riassumi con esempi
oggetti dati, strutture dati
Tipi di dati, tipi di dati astratti
Tre elementi
struttura logica
struttura lineare
raccogliere
struttura ad albero
Struttura del grafico (struttura mesh)
struttura non lineare
Struttura fisica (struttura di stoccaggio)
memorizzazione sequenziale
stoccaggio a catena
Archiviazione dell'indice
Archiviazione hash
memorizzazione non sequenziale
Operazioni sui dati
algoritmo
concetto di base
cos'è l'algoritmo
Programma = struttura dati + algoritmo
Le strutture dati sono le informazioni da elaborare
Gli algoritmi sono passaggi per l'elaborazione delle informazioni
Cinque caratteristiche degli algoritmi
Finitezza
Può essere eseguito entro un tempo limitato
Gli algoritmi sono finiti
I programmi possono essere infiniti
certezza
Lo stesso input produrrà solo lo stesso output
fattibilità
Gli algoritmi possono essere implementati utilizzando le operazioni di base esistenti
accedere
Dati inviati all'algoritmo per l'elaborazione
produzione
Il risultato dell'elaborazione dell'algoritmo
Caratteristiche di un algoritmo “buono”.
correttezza
In grado di risolvere i problemi correttamente
leggibilità
Descrivi l'algoritmo in modo che gli altri possano capirlo
Robustezza
Gli algoritmi possono gestire alcune situazioni anomale
Alta efficienza e bassi requisiti di stoccaggio
Cioè, l'esecuzione dell'algoritmo consente di risparmiare tempo e memoria.
Bassa complessità temporale e bassa complessità spaziale
Una misura dell'efficienza dell'algoritmo
complessità temporale
Come calcolare
① Trova un'operazione di base (il loop più profondo)
② Analizzare la relazione tra il numero di tempi di esecuzione x dell'operazione di base e la dimensione del problema n x = f (n)
③L'ordine di grandezza O(x) di x è la complessità temporale dell'algoritmo T(n)
Tecniche comunemente usate
Regola dell'addizione: O( f( n)) × O( g( n)) = O( max( f( n), g( n)))
Regola di moltiplicazione: O( f( n)) × O( g( n)) = O( ( f( n) × g( n)))
"Fare sempre riferimento all'ordine del potere"
Tre livelli di complessità
Complessità temporale nel caso peggiore: considerare il caso "peggiore" dei dati di input
Complessità temporale media: considera la situazione in cui tutti i dati di input appaiono ugualmente probabili
Migliore complessità temporale: considerare il "caso migliore" per i dati di input
complessità spaziale
sovraccarico della memoria
①Variabili di archiviazione
②Chiamata ricorsiva
Come calcolare
Programma ordinario
①Trova le variabili relative allo spazio occupato e alla dimensione del problema
②Analizza la relazione tra lo spazio occupato x e la dimensione del problema n x = f (n)
③L'ordine di grandezza O(x) di x è la complessità spaziale dell'algoritmo S(n)
programma ricorsivo
① Trova la relazione tra la profondità della chiamata ricorsiva x e la dimensione del problema n x = f(n)
②L'ordine di grandezza O(x) di x è la complessità spaziale dell'algoritmo
Nota: alcuni algoritmi richiedono uno spazio di archiviazione diverso per ciascun livello di funzioni e i metodi di analisi sono leggermente diversi.
Tecniche comunemente usate
Regola dell'addizione: complessità temporale simultanea
Regola di moltiplicazione: complessità temporale simultanea
"Fare sempre riferimento all'ordine del potere"
Capitolo primo
tavola lineare
Definizione e operazioni base delle tavole lineari
definizione
Una tabella lineare ha una sequenza finita di n (n>=0) elementi di dati dello stesso tipo di dati, dove n è la lunghezza della tabella quando n=0 Una lista lineare è una lista vuota.
ordine
L'ordine dei bit inizia da 1 e l'indice dell'array inizia da 0
Lunghezza tabella, tabella vuota
Elementi di intestazione e piè di pagina
diretto predecessore e diretto successore
Ad eccezione del primo elemento, ogni elemento ha uno ed un solo predecessore diretto; Ogni elemento tranne l'ultimo ha esattamente un successore diretto.
Caratteristiche degne di nota
Gli elementi dei dati sono dello stesso tipo, limitati e ordinati
Operazioni di base
Crea vendite, aggiungi, elimina, modifica e controlla
Giudicare vuoto, giudicare lungo, output di stampa (funzione funzione personalizzata)
Altri punti degni di nota
Comprendere quando passare i riferimenti ai parametri "&"
La denominazione delle funzioni dovrebbe essere leggibile
Tabella sequenziale (memorizzazione sequenziale)
Definizione (struttura di stoccaggio)
Gli elementi di dati che sono logicamente adiacenti sono anche fisicamente adiacenti
Metodo per realizzare
allocare staticamente la memoria
Utilizzare l'implementazione "array statico" per definire il numero massimo di spazio di archiviazione
Una volta determinata la dimensione, non è possibile modificarla
Allocare dinamicamente la memoria
Utilizzando "array dinamico", il puntatore dati definito nella struttura alloca dinamicamente la memoria tramite malloc (c'è un'area heap)
L.data=(ElemType *)malloc(sizeof(ElemType)*size)
Quando la tabella di sequenza è piena, è possibile utilizzare malloc per espandere dinamicamente la capacità massima della tabella di sequenza.
È necessario copiare gli elementi dei dati in una nuova area di archiviazione e utilizzare la funzione gratuita per liberare l'area originale.
Le intestazioni utilizzate #include <stdlib.h>
Caratteristiche
accesso casuale
Può trovare l'i-esimo elemento nel tempo O(1).
Alta densità di stoccaggio
Aumentare la capacità è scomodo
L'inserimento e l'eliminazione di elementi di dati è scomodo
Funzione operativa
inserire
Complessità temporale: Migliore O(1) Peggiore O(n) Media O(n)
eliminare
Complessità temporale: Migliore O(1) Peggiore O(n) Media O(n)
Punti di codice
Il codice dovrebbe prestare attenzione alla differenza tra ordine di bit i e pedice
L'algoritmo deve essere robusto e prestare attenzione alla legalità di i
Uso delle virgolette
Trovare
Ricerca bit a bit
Nel caso della memoria allocata dinamicamente, la complessità temporale è O(1)
Trova per valore
Complessità temporale di allocazione statica: migliore O(1) peggiore O(n) media O(n)
Statico e dinamico sono la stessa cosa
lista collegata
puntatore della testa
coda
1. È possibile utilizzare array ed elenchi collegati
Elenchi concatenati circolari e array circolari
Puntatori di testa e coda, pedici
Capitolo due