Wondershare EdrawMind
MindMap Gallery 01Struttura dei dati
- 12
01Struttura dei dati
Questa è una mappa mentale sulla struttura dei dati 01, inclusa la struttura logica, il numero Cattleya, la struttura fisica, Operazioni sui dati, ecc.
Edited at 2023-12-08 15:46:58
- 暗黑模板-個人求職簡歷模板
個人求職簡歷模板的暗黑配色方案，包括個人簡介、職業規劃、行業經驗、自我評價等多個部分，讓你的簡歷更出彩。使用模板可以極大地提高效率，用戶不需要從頭開始設計結構和內容，只需在模板的基礎上填寫或添加自己的信息即可，這樣可以節省大量的時間和精力，歡迎參考使用!持續分享給大家……
- Strategia di saggio sulla gestione del rischio di progetto
Se non sai come scrivere un articolo, sarai nei guai come manager dei sistemi informativi. Una guida passo passo su come scrivere un documento sulla gestione del rischio. Se ne hai bisogno, ritiralo velocemente!
- piano pasto
Il programma dietetico formula un programma dietetico scientifico e ragionevole per soddisfare i nutrienti e l'energia richiesti dal corpo, mantenendo così una buona salute e una buona postura.
01Struttura dei dati
- 暗黑模板-個人求職簡歷模板
個人求職簡歷模板的暗黑配色方案，包括個人簡介、職業規劃、行業經驗、自我評價等多個部分，讓你的簡歷更出彩。使用模板可以極大地提高效率，用戶不需要從頭開始設計結構和內容，只需在模板的基礎上填寫或添加自己的信息即可，這樣可以節省大量的時間和精力，歡迎參考使用!持續分享給大家……
- Strategia di saggio sulla gestione del rischio di progetto
Se non sai come scrivere un articolo, sarai nei guai come manager dei sistemi informativi. Una guida passo passo su come scrivere un documento sulla gestione del rischio. Se ne hai bisogno, ritiralo velocemente!
- piano pasto
Il programma dietetico formula un programma dietetico scientifico e ragionevole per soddisfare i nutrienti e l'energia richiesti dal corpo, mantenendo così una buona salute e una buona postura.
- Recommended to you
- Outline
struttura dati (una raccolta di elementi di dati che hanno una relazione)
struttura logica
struttura lineare
Tavola lineare generale
rappresentazione sequenziale
Tabella di sequenza
Utilizzare unità di archiviazione con indirizzi consecutivi per memorizzare gli elementi nella tabella
Caratteristiche
L’ordine logico è coerente con l’ordine fisico
Gli inserimenti e le cancellazioni sono estremamente costosi
accesso casuale
inserire
Caso migliore: inserimento alla fine della tabella O(n) Scenario peggiore: inserimento dell'intestazione, tutti gli elementi devono essere spostati indietro O(n)
for(int j=L. length; j>=i; j--)//Sposta indietro il primo elemento e gli elementi successivi L. dati[j]=L. dati[j-1]; L. data[i-1]=e;//Metti e nella posizione i L.length;//Aggiungi 1 alla lunghezza della tabella lineare
eliminare
Caso migliore, O(1) Nel caso peggiore, O(n)
e=L data[i-1];//Assegna l'elemento eliminato a e for(int j=i; j<L. length;j);//Sposta l'elemento dopo la i-esima posizione in avanti L. dati[j-1]=L.dati[j]; L. length--;//La lunghezza della tavola lineare viene ridotta di 1
Trova per valore
Nel migliore dei casi, O(1) Caso peggiore, O(n)
for(i=0; i<L. lunghezza;i) if(L.dati[i]==e) return i 1;//Poiché il pedice della tabella è memorizzato a partire da 0, il valore dell'elemento con pedice i è uguale a e, restituisce il suo ordine di bit i 1 return 0;//Esce dal ciclo, indicando che la ricerca è fallita
rappresentazione della catena
Logicamente adiacenti, non fisicamente adiacenti, stabilendo relazioni logiche attraverso catene
vantaggio
L'inserimento e l'eliminazione non richiedono lo spostamento di elementi, basta modificare il puntatore.
discordanza
Impossibile accedere in modo casuale
Categorie principali
Elenco unico
L'unità di memorizzazione memorizza le informazioni sull'elemento e un puntatore al successivo
Metodo di definizione
digitare la struttura LNoed{ Dati ElemType; Struct LNoed *next; üLNodo,*Llinklist;
inserire
Metodo di inserimento della testa
S->dati=x; S->successivo=L->successivo; //L è il puntatore della testa L->successivo=S;
L è il puntatore della testa
metodo di inserimento della coda
S->dati=x; r->next=S;. //r è il puntatore finale della tabella r=S; //Sposta r sul nuovo nodo di coda per prepararsi al successivo inserimento della coda
eliminare
pqx Cancella q
q=p->successivo; p->successivo=q->successivo; libero(q);
Trova per valore
lnode *p=l->next; //Il puntatore p punta al nodo successivo del nodo head while (p!=null&&p!=valore da verificare) p=p->successivo; restituire p;
Doppia lista concatenata
Rispetto ad una lista concatenata singolarmente, c'è un prepuntatore in più che punta al nodo precedente.
Definizione
digitare la struttura LNoed{ Dati ElemType; Struct LNoed *pre,*next; üLNodo,*Llinklist;
inserire
① s->successivo=p->successivo; ② p->successivo->pre=s; ③ s->pre=p; ④ p->successivo=s;
①② deve precedere ④
eliminare
p→successivo=q→successivo; q→successivo→pre=p; libero(q);
elenco collegato circolare
Elenco circolare collegato singolarmente
Elenco circolare doppiamente concatenato
elenco collegato statico
Il puntatore qui si riferisce all'indice dell'array dell'elemento successivo
tabella generalizzata
Testa
Rimuovi l'elemento all'inizio della tabella o della sottotabella
coda
Rimuovi gli elementi alla fine della tabella
tavola lineare ristretta
pila
Caratteristiche
ultimo ad entrare, primo ad uscire
È consentito solo l'inserimento o l'eliminazione in cima allo stack
Non puoi leggere a piacimento un elemento nel mezzo
Classificazione
pila di sequenze
Operazioni di base
La pila è vuota boolStackVuoto(SqStack S){ if(S.top==-1) //La pila è vuota restituisce vero; altrimenti //non vuoto restituire falso; ｝
spingere nella pila boolPush(SqStack &S,ElemType x){ if(S.top==MaxSize-1) //Lo stack è pieno e verrà segnalato un errore restituire falso; S. data[ S. top]=x; //Il puntatore viene prima incrementato di 1, quindi inserito nello stack restituisce vero; ｝
pop bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) //Lo stack è vuoto e viene segnalato un errore restituire falso; x=S. data[S. top--]; //Prima tira lo stack, quindi decrementa il puntatore di 1 restituisce vero; }
Leggi l'elemento in cima allo stack bool GetTop(SqStack S,ElemType &x) { if(S.top==-1)//Lo stack è vuoto e viene segnalato un errore restituire falso; x=S. data[S. top]; //x registra l'elemento superiore dello stack restituisce vero; ｝
pila condivisa
Due stack sequenziali condividono uno spazio di stack per risparmiare spazio di archiviazione.
Il puntatore top0 dello stack A punta alla cima dello stack e il puntatore top1 dello stack B punta alla cima dello stack. Gli elementi vengono inseriti nello stack A: top0 viene aggiunto prima e poi inserito nello stack. L'elemento viene inserito nello stack B: top1 viene prima decrementato di uno e poi inserito nello stack Lo stack è pieno quando top1-top0=1 lo stack A è vuoto quando top0==-1 Lo stack B è vuoto quando top1==Maxsize
pila di catene
Nessun nodo di testa Lhead punta all'elemento in cima allo stack Lo stack a catena facilita l'inserimento e l'eliminazione
applicazione dello stack
corrispondenza delle parentesi
Valutazione dell'espressione
chiamata ricorsiva
coda
Caratteristiche
il primo che entra è il primo ad uscire
Non consentire la lettura arbitraria di un elemento nel mezzo
Classificazione
Memorizzazione degli ordini in coda
coda sequenziale
Unisciti alla squadra
posteriore 1, quindi assegnare il valore
Decoda
Lascia prima la squadra, poi l'attaccante 1
coda circolare
La squadra è vuota
anteriore==posteriore
La squadra è piena
(posteriore 1)%Maxsize==anteriore
Numero attuale di elementi
(dimensione massima posteriore-anteriore)% dimensione massima
Unisciti alla squadra
Unisciti alla squadra bool EnQueue(SqQueue &Q, ElemType x){ if((Q. posteriore 1)Dimensione massima==Q. anteriore) return false; //Se la coda è piena, verrà segnalato un errore Q. data[Q. posteriore]=x; //Se non c'è spazio, inserirlo nella parte posteriore Q. posteriore=(Q. posteriore 1)MaxSize; //Aggiungi 1 al modulo del puntatore di coda restituisce vero; ｝
Decoda
Decoda bool DeQueue(SqQueue &Q, ElemType &x){ if(Q. posteriore==Q. anteriore) return false; //Se la coda è vuota, verrà segnalato un errore x=Q.dati[Q.front]; Q. front=(Q. front 1)%MaxSize; //Aggiungi 1 al modulo del puntatore della testa della squadra restituisce vero; }
Archiviazione della catena di code
L'essenza è una lista collegata singolarmente con un puntatore head e un puntatore tail.
coda dentro e testa fuori
La squadra è vuota bool ÈVuoto(LinkQueue Q){ if(Q.front==Q.retro) restituisce vero; altrimenti restituisce false; ｝
Unisciti alla squadra void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->dati=x; s->next=NULL; //Crea un nuovo nodo e inseriscilo alla fine della catena Q. posteriore->successivo=s; Q. posteriore=s; ｝
Decoda bool DeQueue(LinkQueue &Q, ElemType &x){ if(Q.front==Q.retro) return false;//Squadra vuota LinkNodo *p=Q.anteriore->successivo; x=p->dati; Q.anteriore->successivo=p->successivo; if(Q.posteriore==p) Q. posteriore=Q. anteriore; //Se c'è un solo nodo nella coda originale, diventerà vuoto dopo l'eliminazione. libero(p); restituisce vero; ｝
deque
Uscita limitata
È consentita l'uscita solo da un'estremità
Ingresso limitato
È consentito un solo input
Applicazioni in coda
Attraversamento di livello
respingente
corda
corrispondenza dei modelli
corrispondenza semplice
Algoritmo kmp
Metodo di calcolo del valore successivo
① I primi due valori successivi sono 0 e 1
② Il valore successivo viene abbinato al prefisso e al suffisso e la lunghezza della stringa più lunga abbinata con successo viene presa come 1
Ottimizzazione dell'algoritmo kmp
metodo di calcolo del valore nextval
Cerca in avanti in base al valore successivo con lo stesso numero. Il valore successivo è il valore nextval da trovare. Se esiste già un valore nextval, aggiornalo.
Generalizzazione delle tavole lineari
vettore
Metodo di archiviazione
precedenza di riga
Prima la colonna
Archiviazione compressa di matrici speciali
matrice triangolare superiore matrice triangolare inferiore
Matrice simmetrica
matrice tridiagonale
precedenza di riga
Memorizzato in un array unidimensionale k=2i j-3
matrice sparsa
metodo di tripla archiviazione
(riga, colonna, dati)
Metodo di archiviazione dell'elenco con collegamenti incrociati
struttura non lineare
raccogliere
Gli elementi appartengono allo stesso insieme
struttura ad albero
Albero
natura dell'albero
è una struttura dati ricorsiva
è una struttura gerarchica
① Il numero di nodi nell'albero = la somma dei gradi di tutti i nodi 1
② Un albero di grado m ha al più mⁱ⁻¹ nodi al livello i-esimo.
③ Un albero m-ario di altezza h ha al massimo (mʰ -1) / (m-1) nodi.
④ L'altezza minima di un x-albero con n nodi ┍ logₓ (n(m-1) 1)┒
Albero binario
natura
n₀=n₂ 1
n=n₀ n₁ n₂
n=1 n₁ 2n₂
Un albero binario di altezza h ha al massimo 2ʰ-1 nodi.
Classificazione
Albero binario vuoto
albero binario completo
albero binario completo
Corrispondenza biunivoca tra nodi e numeri
Può esserci solo uno o nessun nodo di grado 1
Questo nodo determina la parità del numero totale di nodi nell'albero binario completo
L'altezza dell'albero di un albero binario completo con n nodi
┍ log₂(n 1)┒ arrotonda per eccesso
┕ log₂n┙ 1 arrotondamento per difetto
Albero di ordinamento binario
Piccolo a sinistra e grande a destra
albero binario bilanciato
La differenza di altezza tra i sottoalberi sinistro e destro non supera 1
Struttura di archiviazione ad albero binario
memorizzazione sequenziale
albero binario completo
albero binario completo
stoccaggio a catena
Lista concatenata binaria con n nodi Contiene n 1 dominio a catena vuota
albero binario indizio
Clue L'albero binario è una struttura fisica
Il campo di collegamento vuoto viene utilizzato per memorizzare indizi che puntano alla sequenza precedente o successiva.
Classificazione
Albero binario degli indizi in ordine
albero binario dell'indizio di preordine
albero binario indizio postorder
Attraversamento dell'albero binario
attraversamento del preordine
Intorno alla radice
attraversamento in ordine
radice sinistra destra
Attraversamento postordine
radici sinistra e destra
struttura di stoccaggio dell'albero
rappresentanza dei genitori
rappresentazione infantile
rappresentanza del fratello minore
rappresentazione ad albero binario
Nodi facili da trovare per i bambini
Trovare i genitori è più difficile
digita struct csnode{ dati di tipo elem; struct csnode *liftchild, *rightbro; //Definisce i puntatori del figlio e del fratello destro ｝csnode, *cstree;
Conversione di alberi, foreste, alberi binari
Bambino a sinistra, fratello a destra
Il nodo figlio sinistro della radice viene utilizzato come nodo figlio della radice nel nuovo albero. Il fratello giusto della radice diventa figlio della radice nel nuovo albero
Applicazioni degli alberi e degli alberi binari
Albero di Huffman/Albero di Huffman
Albero binario con lunghezza del percorso ponderata minima WPL
Caratteristiche
① Piccolo a sinistra e grande a destra o Grande a sinistra e piccolo a destra
② Seleziona ogni volta due fusioni con il peso più piccolo e la loro somma viene utilizzata come peso della nuova radice.
③ La forma dell'albero Ha non è unica, ma il valore WPL è sempre il più piccolo.
④ Non esiste alcun nodo di grado 1 nell'hash tree.
Perché gli alberi sono fusi in due.
Codifica di Huffman
lunghezza variabile
Variabile di lunghezza carattere binario
lunghezza fissa
La lunghezza dei caratteri binari è fissa
E cerca nella collezione
è un insieme (struttura logica)
Albero memorizzato in sequenza nella rappresentazione principale
E
controllo
Applicazione della ricerca sindacale
Determinare la connettività di un grafico
Attraversa tutti i bordi di un grafico non orientato, Ogni volta che viene attraversato un bordo, i suoi due vertici vengono uniti in un insieme. In questo modo, tutti i vertici connessi saranno in un insieme, mentre i vertici non connessi non saranno in questo insieme.
struttura del grafico
Definizione di grafico
L'insieme dei vertici V e l'insieme degli spigoli E costituiscono
Classificazione delle immagini
Grafico non orientato
La somma dei gradi di tutti i vertici di un grafo non orientato = numero di bordi × 2
grafico diretto
coda dell'arco → testa dell'arco
La somma dei gradi entranti di tutti i vertici di un grafo diretto = la somma dei gradi uscenti
diagramma semplice
Non sono presenti bordi duplicati Non c'è alcun bordo dal vertice a se stesso
grafico completo
grafo completo non orientato
n(n-1)/2 archi
Grafico completo diretto
Ci sono due archi in direzioni opposte tra due vertici
sottotrama
collegato
in grafo non orientato
Due vertici qualsiasi sono collegati
I sottografi massimamente connessi sono detti componenti connessi
Connettività forte
nel grafico diretto
Due punti qualsiasi sono fortemente connessi
Percorsi semplici e circuiti semplici
I vertici non appaiono ripetutamente → percorso semplice
Ad eccezione del primo e dell'ultimo punto, gli altri punti non compaiono ripetutamente → circuito semplice
albero di copertura
Sottografo connesso minimo contenente tutti i vertici
Il grafico deve essere connesso e avere il numero minimo di spigoli.
Avviso
Il maggior numero di spigoli nel caso non connesso:
Un grafico completo è composto da n-vertici. In questo momento, l'aggiunta di un altro punto è un grafico non connesso.
Il grafo orientato ha il minor numero di archi quando è fortemente connesso:
Almeno n archi formano un ciclo
Altre immagini
grafico sparso
|E| = |V|*log|V|
grafico denso
Memorizzazione dei grafici
metodo della matrice di adiacenza
magazzinaggio
Grafico non orientato
grafico diretto
Complessità spaziale O(n²) → n è il numero di vertici
Più adatto per la memorizzazione di grafici densi
metodo della lista di adiacenza
magazzinaggio
Grafico non orientato
Complessità spaziale (V 2E)
Perché il bordo apparirà due volte
grafico diretto
Complessità spaziale (V E)
metodo degli elenchi incrociati
Archiviazione concatenata di grafi diretti
metodo di tabelle multiple
Archiviazione concatenata di grafi non orientati
Attraversamento del grafico
prima l'ampiezza
Simile all'attraversamento del livello
prima la profondità
Continua a scavare in profondità in un punto
Per i grafici non orientati, il numero di chiamate a DFS o BFS = il numero di componenti connessi di questo grafico
Applicazione dei diagrammi
① Albero di copertura minimo
① Contiene tutti i vertici
② Contenere il minor numero possibile di bordi
③ Peso e unicità
④ Numero di bordi = numero di vertici-1
⑤ La forma dell'albero non è unica
② Algoritmo primitivo
processo dell'algoritmo
① Scegline uno qualsiasi
② Trova il peso più piccolo
③ Collega in sequenza, compresi tutti i punti, con il minor numero di bordi possibile
Adatto per risolvere alberi di copertura minimi di grafi ad alta densità di spigoli
complessità temporale
O(V²)
③ Algoritmo di Kruskal
Trova il bordo più piccolo nell'intero grafico, selezionalo prima e richiedi che tutti i vertici siano inclusi
Usa e cerca
Adatto per grafici con pochi spigoli e molti vertici
complessità temporale
Elog₂E
④ Problema del percorso più breve
① Algoritmo di Dijkstra
processo dell'algoritmo
Registra ogni round
① Il percorso di ogni passaggio e il peso totale del percorso
② Percorso più breve impostato
Risolvere il problema del percorso di origine singolo
Immagini senza autorità o immagini con autorità vanno bene.
complessità temporale
matrice di adiacenza
O(V²)
lista di adiacenze
O(V²)
②Algoritmo di Floyd
grafico ponderato
processo dell'algoritmo
Aggiorna continuamente la matrice
Ad esempio: A, A², A³……
Il pedice di A rappresenta il nodo relè
complessità temporale
O(V³)
⑤ Problema del percorso critico
processo di calcolo manuale
① Trova il primo momento in cui si è verificato l'evento Vk
Contare direttamente da davanti a dietro
② Trova l'ora in cui si è verificato l'ultimo evento Vl
Calcola da dietro in avanti, sottrai il peso più piccolo
③ Trova il primo momento in cui si è verificato l'attività
Il primo momento in cui si è verificato l'evento alla fine dell'arco
④ Trova l'ultima ora in cui si è verificata l'attività
L'ora dell'ultimo verificarsi dell'evento all'inizio dell'arco: il peso di questa attività
⑤ Sottrarre la prima attività e dall'ultima attività l. L'attività uguale a 0 è l'attività chiave, e i vertici ad essa collegati sono quelli richiesti.
Numero di Cattleya
Si applica a:
pila
n elementi vengono inseriti nello stack e viene trovato il numero di sequenze pop-up.
Albero binario
Quante forme diverse di alberi binari possono essere formate da n nodi?
corrispondenza delle parentesi
n coppie di parentesi, quante sequenze di corrispondenza delle parentesi ci sono?
Prerequisiti per l'utilizzo dei numeri Cattelan
Stack e alberi binari non possono avere altre restrizioni
Ad esempio, il requisito è: il primo numero uscito dallo stack è 1. In questo momento, il numero di Cattelan non può essere utilizzato per calcolarlo.
Due metodi principali
Trovare
ricerca sequenziale
Applicabile a
Tabella di sequenza
lista collegata
mezza ricerca
Applicabile a
elenco di sequenze ordinate
metodo di confronto
Unilaterale
È necessario che la tabella lineare possa essere memorizzata in modo casuale Pertanto, funziona solo con strutture di archiviazione sequenziali
Complessità temporale O(log₂n)
Cerca in blocchi
Non ordinato all'interno dei blocchi, ordinato tra i blocchi
Una tabella di lunghezza n è divisa in b blocchi, ogni blocco ha s record. s=√n, la lunghezza media della ricerca assume il valore minimo √n 1
Durata media della ricerca ASL = (S² 2S n)/2S
ordine
ricerca degli alberi
Albero di ordinamento binario
Piccolo a sinistra e grande a destra
struttura
inserire
eliminare
albero binario bilanciato
La differenza di altezza tra i sottoalberi sinistro e destro non supera 1 O un albero vuoto
Regolazione
Tipo LL
Girare a destra una volta
Tipo RR
Girare a sinistra una volta
Tipo LR
Girare prima a sinistra e poi a destra
tipo RL
Girare prima a destra e poi a sinistra
operare
inserire
eliminare
Trovare
albero rosso nero
definizione
① Radice sinistra destra
② Radici e foglie nere
③ Non rosso
④ Pinza per la strada nera
Prima aggiusta e poi colora
Trova lungo
Successo ASL = (ΣNumero layer×Numero di nodi)/Numero totale
Guasto ASL = (ΣQuale livello × numero di domini di collegamento vuoti del nodo)/numero totale
B-Tree&B-Tree
B-albero
m-ario B-albero
Supporta la ricerca casuale
Caratteristiche
① Ogni nodo ha al più m sottoalberi, Al massimo m-1 parole chiave
③ Ad eccezione del nodo radice, tutti i nodi non foglia hanno almeno ┍ m/2 ┒ sottoalberi Sono presenti almeno ┍ m/2 ┒-1 parole chiave
④ I nodi foglia si trovano sullo stesso livello, ovvero sul livello del dominio di collegamento vuoto
② Se il nodo radice non è una foglia, ci sono almeno 2 sottoalberi
altezza dell'albero
Trovare
Utilizzare la ricerca sequenziale e la ricerca parziale all'interno del nodo.
inserire
eliminare
① Elimina direttamente
② I fratelli possono prendere in prestito abbastanza
① Il fratello Zuo può prenderlo in prestito
Sostituisci te stesso con il nodo più a destra del tuo fratello sinistro e colma tu stesso il vuoto.
② Il fratello giusto può prenderlo in prestito
Sostituisci te stesso con il nodo più a sinistra del tuo fratello destro e colma tu stesso il vuoto.
③ Non ci sono abbastanza fratelli da prendere in prestito
unire
B-albero
Caratteristiche dell'albero B con forcella m
① Ogni parola chiave corrisponde a un sottoalbero
② ┍ m/2 ┒ ≤ n ≤ m
③ I nodi foglia contengono tutte le parole chiave e contengono informazioni
④ Il non foglio serve solo come indice
⑤ Supporta la ricerca sequenziale e la ricerca casuale
tabella hash
L'efficienza della ricerca dipende dal numero di confronti
funzione hash
①Metodo di indirizzamento diretto
②Metodo della divisione con resto
H (tasto) = tasto%P
P: il numero primo più grande non maggiore della lunghezza della tabella
③Metodo di analisi digitale
④Metodo medio dei quadrati
Ricerca hash
Fattore di caricamento α = numero di record/lunghezza della tabella
Come gestire i conflitti
metodo di indirizzamento aperto
① Rilevamento lineare
Torna indietro e compila
Rilevamento lineare calcolato manualmente
Guasto ASL = numeratore/denominatore
Numeratore: sposta indietro il numero di serie della tabella finché non incontra uno spazio vuoto, registra il numero di volte in cui viene spostato indietro, quindi 1 Tutti i record all'interno di P elementi (il numero di spostamenti all'indietro è 1) e il numero di spazi vuoti (se gli spazi vuoti sono all'interno di P)
Denominatore: p
② Rilevamento quadrato
risolvere i conflitti
(resto d¡)% lunghezza della tabella
D = 0², 1², -1², 2², -2²…
③Doppio hashing
④Pseudo-casuale
metodo della cerniera
ordinare
La maggior parte degli ordinamenti funziona solo su tabelle lineari archiviate in sequenza
Ordinamento interno
ordinamento di inserimento
ordinamento per inserzione diretta
Tavoli lineari adatti allo stoccaggio sequenziale e concatenato
Scegline uno come sentinella
Gli elementi grandi sono posti dietro la sentinella, mentre gli elementi piccoli sono posti davanti alla sentinella.
Dopo il completamento, seleziona l'elemento che hai appena organizzato come nuova sentinella.
complessità temporale
O(n²)
Stabilizzare
ordinamento a metà inserimento
Tavoli lineari adatti allo stoccaggio sequenziale
complessità temporale
O(n²)
Ordinamento collinare
Tavoli lineari adatti allo stoccaggio sequenziale
complessità temporale
O(n²)
instabile
Ordinamento dello scambio
Ordinamento a bolle
complessità temporale
O(n²)
Stabilizzare
Ordinamento rapido
Selezionare il benchmark, ① confrontare con il benchmark da dietro in avanti, ② confrontare con il benchmark da davanti a dietro, ① e ② alternativamente
complessità temporale
Miglior O(nlog₂n)
Peggiore O(n²)
O medio(nlog₂n)
instabile
ordinamento della selezione
Ordinamento di selezione semplice
Complessità temporale O(n²)
instabile
Ordinamento dell'heap
Adatto a situazioni con molte parole chiave
Un heap può essere visto come un albero binario completo
processo di impostazione
A partire dall'ultimo nodo non foglia, determinare se soddisfa i requisiti dell'heap.
Complessità temporale O(nlog₂n)
instabile
Ordinamento radicale
L'efficienza temporale è indipendente dalla sequenza iniziale
Prima il bit più alto/prima il bit più basso
Ordina anno mese giorno
Complessità temporale O(d(n r))
Stabilizzare
unisci ordinamento
Complessità temporale O(nlog₂n)
Stabilizzare
ordinamento esterno
Tempo totale di ordinamento esterno = tempo di ordinamento interno, tempo di lettura e scrittura dell'archiviazione esterna, tempo di unione interna
Per r segmenti di unione iniziali, eseguire x unioni
Altezza dell'albero h - 1 = ┍ logₓr ┒= numero di passaggi di unione
albero perdente
Può essere considerato come un albero binario completo
In ogni round di confronto, il vincitore continua verso l'alto, fino al nodo radice
La profondità dell'albero del perdente per la fusione k-way è: ┍ log₂k ┒
Ordinamento della selezione dello spostamento
processo dell'algoritmo
①Seleziona un certo numero di elementi dalla sequenza da ordinare e inseriscili nell'area di lavoro
②Seleziona il numero minimo nell'area di lavoro e inseriscilo nel segmento di unione e modifica miniMax con questo numero.
③ Assicurati che il numero inserito nel segmento di unione la prossima volta sia maggiore del valore miniMax.
④Quando non è presente alcun numero maggiore di miniMax nell'area di lavoro, viene generato il primo segmento di unione
La migliore fusione
Operazioni sui dati
Aritmetica
aggiungere
ridurre -
Prendere *
rimuovere /
Operazione (a è un dato)
XOR ^ Lo stesso è 0, la differenza è 1
AND logico && È uguale a 1 è 1, altrimenti è 0
OR logico || Tutti gli 0 sono 0, altrimenti 1
Prima incrementa e poi assegna a
Assegnare prima il valore e poi incrementare a
Prima decrementa e poi assegna --a
Assegna prima e poi decrementa a...
Prendi il resto %a
Negare !a
struttura fisica
Archiviazione dell'indice
Non solo memorizza gli elementi, ma crea anche una tabella di indice per essi. La tabella di indice contiene più voci di indice. Quando si modificano i dati, è necessario modificare anche la tabella dell'indice
stoccaggio a catena
Gli elementi sono logicamente adiacenti, ma non necessariamente fisicamente adiacenti
memorizzazione sequenziale
Gli elementi logicamente adiacenti vengono memorizzati anche fisicamente adiacenti.
Archiviazione hash (hash)
Calcola l'indirizzo di archiviazione direttamente in base alle parole chiave