1.Datos

2. Elementos de datos

3. Objetos de datos

4.Tipo de datos

estructura de datos

Tres elementos

complejidad del tiempo

complejidad espacial

insertar

borrar

Buscar por valor (buscar secuencialmente)

Crear una lista enlazada individualmente

Buscar nodos por número de serie

Buscar nodo de tabla de nodos por valor

Insertar nodo

Eliminar nodo

Preguntar por el largo de la mesa

Insertar nodo

Eliminar nodo

Lista circular individualmente enlazada

Lista circular doblemente enlazada

inicialización anular InitStack(SqStack &S){ arriba = -1; }

La pila esta vacia bool PilaVacía(SqStack S){ if(S.top == -1) devuelve verdadero; de lo contrario devolverá falso; }

empujar hacia la pila bool Push(SqStack &S,ElemType x){ if(S.top == MaxSize-1) devuelve falso; S.data[ S.top] = x; //top se inicializa a -1 devolver verdadero; }

estallido bool Pop(SqStack &S,ElemType &x){ if(S.top == -1) devuelve falso; x = S.datos[S.arriba- -]; devolver verdadero; }

Leer el elemento superior de la pila. bool GetTop(SqStack S,ElemType &x){ if(S.top == -1) devuelve falso; x = S.datos[S.arriba]; devolver verdadero; }

Inicial: top0 = -1 top1 = MaxSize; pila llena: solo cuando dos punteros de pila son adyacentes top1 - top0 = 1

cola secuencial

cola circular Las operaciones de retirada de cola, unión y completa de la cola circular deben tener % y la condición vacía es solo Q.rear == Q.front;

inicialización anular InitQueue(LinkQueue &Q){ Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkQueue) //Crea el nodo principal Q.front ->siguiente = NULL; }

el equipo esta vacio bool Está vacío(LinkQueue&Q){ if(Q.front == Q.rear) return true;//Con nodo principal de lo contrario devolverá falso; }

Únete al equipo anular EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL;//Crea un nuevo nodo e insértalo al final de la cadena. Q.trasero->siguiente = s; Q.trasero = s; }

quitar la cola bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.trasero == Q.front) devuelve falso; LinkNode *p = Q.front->siguiente; x = p->datos; Q.front->siguiente = p->siguiente; if(Q.rear == p) Q.rear = Q.front;//La cola original tiene un solo nodo libre(p); devolver verdadero; }

Entrada restringida deque

Deque restringido de salida

[]()([][]()) es el formato correcto (] [) es el formato incorrecto;

Expresiones infijas: dependen de la precedencia de los operadores, pero también tratan con paréntesis Expresiones postfix: la precedencia de los operadores ya se tiene en cuenta, sin paréntesis (recorrido posterior al orden del árbol de expresiones) Convertir una expresión infija en una expresión postfija

El nodo raíz ingresa a la cola; si la cola está vacía (todos los nodos han sido procesados), el recorrido finaliza; de lo contrario, se repite el siguiente paso; el niño izquierdo se une al equipo; si tiene un niño derecho, agregue el niño derecho al equipo y regrese al paso anterior.

1. Resuelva el problema de la discrepancia de velocidad entre el host y los dispositivos externos; 2. Resolver problemas de competencia de recursos causados ​​por múltiples usuarios.

Estructura de almacenamiento de matriz fila principal; columna principal

matriz simétrica

matriz triangular

matriz tridiagonal

Utilice el método triplete (etiqueta de fila, etiqueta de columna, valor) o lista cruzada

Almacenamiento secuencial de longitud fija #definir MaxLen 255 estructura typedef { char ch[MaxLen]; longitud interna; }SSadena; Tampoco puede registrar la longitud y utilizar '\0', que no está incluido en la longitud de la cadena, para dar a entender la longitud de la cadena.

Representación de almacenamiento asignado en montón (asignación dinámica) estructura typedef { carbón*ch; longitud interna; }HString; En lenguaje C, el espacio asignado dinámicamente se almacena en el montón y se administra mediante malloc() free(). Si la asignación falla, se devuelve NULL.

Representación de almacenamiento de la cadena de bloques: cada nodo se denomina bloque, y un bloque puede almacenar uno o varios caracteres y la lista vinculada completa se denomina estructura de cadena de bloques; Cuando el último nodo ocupa menos de un bloque, normalmente se rellena con "#"

Asignación de cadenas StrAssign(&T,chars) asigna el valor de T a los caracteres

Comparación de cadenas StrCompare(S,T) si S>T,return>0;S=T,return 0;S<T,return<0

Encuentre la longitud de la cadena StrLength(S) devuelve el número de S elementos

Concatenación de series Concat(&T,S1,S2) usa T para devolver una nueva cadena formada al concatenar S1 y S2.

Encuentre la subcadena SubString(&Sub,S,pos,len) Use Sub para devolver la subcadena comenzando desde el carácter pos de la cadena S y continuando con la longitud de len

int índice(SString S,SString T){ int i=1,j=1; while(i<=S.longitud && j<=T.longitud){ si(S.ch[i] == T.ch[j]){ yo ;j ; } demás{ i = i-j 1 1;j = 1; } if(j > T.longitud) devuelve i - T.longitud; de lo contrario, devuelve 0; } Peor complejidad del tiempo O(mn)

Conceptos relacionados: Prefijo: todas las subcadenas de encabezado de la cadena excepto el último carácter; Sufijo: todas las subcadenas finales de la cadena excepto el primer carácter; Coincidencia parcial (PM): la longitud igual de prefijo y sufijo más larga de la cadena. Ejemplo: 'ababa' ¡Atención! ! A partir del primer carácter de la cadena principal, divida todas las subcadenas y luego analice la longitud del prefijo y sufijo y el sufijo y sufijo iguales más largos, respectivamente. El prefijo y sufijo 'a' es un conjunto vacío, y la longitud igual de prefijo y sufijo más larga es 0 'ab' prefijo 'a' sufijo 'b' La longitud de coincidencia igual más larga es 0 'aba' prefijo 'a' 'ab' sufijo 'a' 'ba' {'a' 'ab'} ^ {'a' 'ba'} = 'a', la longitud del sufijo igual más larga es 1 'abab' prefijo 'a' 'ab' 'aba' sufijo 'b' 'ab' 'bab', la longitud igual de prefijo y sufijo más larga es 2 'ababa' prefijo 'a' 'ab' 'aba' 'abab' sufijo 'a' 'ba' 'aba' 'baba' ,{ } ^ { } = {'a' 'aba'}, el sufijo igual más largo 3 Entonces el valor de coincidencia parcial de la cadena final es 00123

Cuando utilice el algoritmo KMP, primero escriba la tabla PM de la cadena de patrón (subcadena); cuando la subcadena no coincida con la cadena principal, busque el valor PM del último elemento coincidente de la subcadena en la tabla PM y luego deje que subcadena La distancia recorrida hacia atrás (número de caracteres coincidentes - valor PM del último carácter coincidente cuando ocurre una discrepancia en un determinado viaje, si el valor de coincidencia parcial de la parte correspondiente es 0, significa que no hay sufijos iguales y); sufijos en la secuencia coincidente El número de dígitos movidos es el mayor (longitud coincidente - 0) y se mueve directamente a la posición i señalada por la cadena principal en este momento para la siguiente comparación. Mover = (j-1) - PM[j-1];

Generación y modificación del siguiente arreglo: Para facilitar la falta de coincidencia, en lugar de esperar un carácter, verifique directamente el valor PM de la posición actual del carácter no coincidente, de modo que todos los elementos en el PM se muevan 1 posición hacia la derecha y la primera posición se llene con -1. y se ignora la última posición; Llamada siguiente matriz, Move = (j-1)-next[j] En este momento, j vuelve a j = j-Move = next[j] 1; Luego agregue 1 a todo lo siguiente y actualice la siguiente matriz para que j = next[j] (En este momento, la primera posición de la siguiente matriz es 0) El significado de la siguiente matriz final: cuando el carácter j-ésimo de la subcadena no coincide, salte a la siguiente posición [j] de la subcadena para la siguiente ronda de coincidencia. ! !

Un árbol es un conjunto finito de n (n>0) nodos. Cuando n = 0, se llama árbol vacío, tiene solo un nodo raíz y los nodos restantes se pueden dividir en conjuntos finitos disjuntos, llamados subárboles; 1. El nodo raíz del árbol no tiene predecesor, y los nodos distintos del nodo raíz tienen uno y solo un predecesor. 2. Todos los nodos del árbol pueden tener cero o más sucesores; el árbol es adecuado para representar datos con un; estructura jerarquica; 3. Terminología: 1. Ancestro-descendiente (puede abarcar varios niveles, siempre que exista una relación de arriba hacia abajo); 2. El número de hijos de un nodo en el árbol se denomina grado del nodo; el grado máximo de un nodo en el árbol es el grado del árbol; 3. Los nodos con grado> 0 se denominan nodos de rama (nodos no terminales); los nodos con grado 0 se denominan nodos hoja (nodos terminales); 4. El nivel de nodos se define a partir de la raíz del árbol, siendo el nodo raíz el primer nivel. Los nodos cuyos nodos padres están en el mismo nivel son primos entre sí; La profundidad de un nodo se acumula capa por capa comenzando desde el nodo raíz y de arriba a abajo (imagine que las raíces del árbol se vuelven más profundas hacia abajo). La altura del nodo se acumula capa por capa comenzando desde el nodo de la hoja y de abajo hacia arriba (se ve muy alto de abajo hacia arriba) La altura o profundidad de un árbol es el número máximo de niveles de nodos en el árbol; 4. Árboles ordenados y árboles desordenados, los árboles ordenados no son intercambiables 5. Ruta y longitud de la ruta: la ruta se compone de la secuencia de nodos que pasan entre los dos nodos, y la longitud de la ruta es el número de bordes pasados. 6. Bosque: una colección de m árboles separados. Siempre que se elimine el nodo raíz, el árbol se convierte en un bosque; por el contrario, siempre que se agregue un nodo raíz a m árboles, el bosque se convierte en un árbol.

naturaleza: 1. El número de nodos del árbol es igual a la suma de los grados de todos los nodos (número total de ramas) 1 (nodo raíz) 2. El i-ésimo nivel de un árbol con grado m tiene como máximo m^i-1 nodos (i>1) 3. Un árbol m-ario con altura h tiene como máximo (m^i - 1)/(m-1) nodos. 4. La altura mínima de un árbol m-ario con n nodos es

1. Almacenamiento secuencial: notación principal: una estructura grande establece una estructura pequeña, y la estructura pequeña son los datos y los punteros principales; la estructura grande es una matriz compuesta por múltiples estructuras pequeñas y el número de nodos; #definir Max_Tree_SIze 100 estructura typedef { datos de tipo elemento; padre entero; }PTNodo; estructura typedef { Nodos PTNode[Max_Tree_Size]; int n; }PTárbol; Esta estructura aprovecha el hecho de que cada nodo (excepto el nodo raíz) tiene solo un padre y puede obtener rápidamente el nodo padre de cada nodo, pero requiere atravesar todo el árbol para encontrar los hijos del nodo.

2. En la representación secundaria: conecte los nodos secundarios de cada nodo con una única lista vinculada para formar una estructura lineal. Hay n listas vinculadas para n nodos (la lista vinculada secundaria de un nodo hoja es una lista vinculada vacía); Este método es muy sencillo para encontrar hijos, pero encontrar padres requiere atravesar las n listas vinculadas de niños a las que apuntan los punteros de listas vinculadas de niños en n nodos; Similar a la tabla crítica

3. Representación de hermano menor: también conocida como representación de árbol binario. estructura typedef CSNode{ datos de tipo elemento; estructura CSNode *primerhijo,*siguientehermano; }NodoCS,*ÁrbolCS; Implemente convenientemente la operación de convertir un árbol en un árbol binario El niño izquierdo tiene un hermano.

Conversión entre árboles y árboles binarios; tanto los árboles como los árboles binarios se pueden representar mediante listas enlazadas binarias. La estructura física es la misma, pero las reglas para convertir un árbol en un árbol binario son diferentes: hijo izquierdo y hermano derecho. Dado que el nodo raíz no tiene hermanos, el nodo raíz no tiene un subárbol derecho; pasos de conversión de escritura a mano: 1. Conecte una línea entre los nodos hermanos 2. Conserve solo la conexión entre cada nodo y su primer hijo, y use otro Borre todas las conexiones de los hijos. 3. Tome la raíz del árbol como eje y gírelo 45 grados en el sentido de las agujas del reloj.

Conversión de bosque a árbol binario 1. Primero convierta cada árbol del bosque en un árbol binario. 2. La raíz de cada árbol se considera una relación entre hermanos y los árboles posteriores se consideran secuencialmente como el nodo derecho del árbol anterior. 3. Gire la raíz del primer árbol 45 grados en el sentido de las agujas del reloj.

Convierta un árbol binario en un bosque: 1. Desconecte el subárbol derecho del nodo raíz uno por uno hasta que solo quede un nodo raíz sin un subárbol derecho. 2. Convierta todos los árboles binarios desconectados en árboles para obtener el bosque original. Convertir un árbol binario en un árbol o bosque es único

Convertir árbol binario en árbol 1. Elimine todos los nodos derechos, nodos derechos y nodos derechos del subárbol izquierdo del nodo raíz. . . todos como hijos de raíz 2. Ajustar en secuencia

recorrido del árbol

Viajando por el bosque

Union-find es una representación de conjunto simple que admite 3 operaciones La definición de estructura del conjunto de búsqueda de unión: #definir TAMAÑO 100 int UFSets[TAMAÑO]; Un conjunto en la búsqueda de unión es un árbol y varios conjuntos forman un bosque.

Árbol binario de pistas (desconocido, por lo que se ha ampliado especialmente) estructura typedef TreadNode{ datos de tipo elemento; struct TreadNode *lchild,*rchild; int ltag,rtag; }Nodo de hilo,*Árbol de hilo; Una lista binaria enlazada formada con una estructura de nodos como estructura de almacenamiento del árbol binario se denomina lista enlazada de pistas; los punteros que apuntan al predecesor y al sucesor del nodo se denominan pistas. Un árbol binario con pistas se llama árbol binario de pistas.

atravesar

Árbol de clasificación binaria BST (árbol de búsqueda binaria)

árbol binario equilibrado

árbol negro rojo

Árboles de Huffman y codificación de Huffman

gráfico dirigido, gráfico no dirigido Gráfico dirigido: E es un borde dirigido (arco) y un arco es un par ordenado de vértices, denotado como <v,w> Gráfico no dirigido: E es un borde no dirigido (arista) y un borde es un par de vértices desordenados, registrados como (v, w)

Gráfico simple, gráfico múltiple Diagrama sencillo: 1. No hay aristas duplicadas (las aristas que apuntan entre sí entre dos nodos adyacentes en un gráfico dirigido no se cuentan como aristas duplicadas) 2. No hay arista desde el vértice hacia sí mismo. Múltiples tramas: 1. El número de aristas entre dos vértices es mayor que 1. 2. Permitir que los vértices se relacionen entre sí a través de una arista. Las definiciones de gráficos múltiples y gráficos simples son relativas. En la estructura de datos solo se analizan los gráficos simples.

Gráfico completo (gráfico completo simple) Para gráficos no dirigidos, el rango de valores de |E| es 0-n(n-1)/2, Un gráfico no dirigido con n (n-1)/2 aristas se llama gráfico completo y hay una arista entre dos vértices cualesquiera; Para gráficos dirigidos, el rango de valores de |E| es 0-n(n-1), Un gráfico dirigido con n (n-1) arcos se llama gráfico completo dirigido y hay un arco opuesto entre dos vértices cualesquiera.

subtrama G=(V,E),G'=(V',E'); Si V' es un subconjunto de V y E' es un subconjunto de E, entonces G' se llama subgrafo de G. Si se satisface V(G')=V(G), entonces G' se denomina subgrafo generado de G; Ningún subconjunto de V y E puede formar un subgrafo G, porque los vértices asociados con algunas aristas en el subconjunto de E pueden no estar en este subconjunto de V.

Conectividad, gráficos conectados y componentes conectados Si hay un camino desde el vértice v al vértice w, entonces se dice que v y w están conectados. Si dos vértices cualesquiera en G están conectados, se convierte en un gráfico conexo; de lo contrario, es un gráfico desconectado. El subgrafo conectado máximo en un gráfico no dirigido se llama componente conectado. Un gráfico conectado tiene al menos n-1 aristas. Si el número de aristas es menor que n-1, debe ser un gráfico no conexo; ¿Cuántas aristas puede tener como máximo un gráfico desconectado? : El estado crítico de n-1 vértices que forman un gráfico completo (agregando cualquier borde para formar un gráfico conectado)

Gráfico fuertemente conectado, componentes fuertemente conectados En un gráfico dirigido, si un par de vértices v a w y w a v tienen caminos, entonces se dice que los dos vértices están fuertemente conectados. Si cualquier par de vértices del gráfico está fuertemente conexo, el gráfico se denomina gráfico fuertemente conexo. El subgrafo máximo fuertemente conexo en un gráfico dirigido se denomina componente fuertemente conexo del gráfico dirigido; La situación con la menor cantidad de aristas cuando un gráfico dirigido está fuertemente conectado: se necesitan al menos n aristas para formar un ciclo

árbol que se extiende, bosque que se extiende El árbol de expansión de un gráfico conectado es un subgrafo conectado mínimo que contiene todos los vértices del gráfico. Si el número de vértices fijos es n, entonces el árbol de expansión tiene n-1 aristas. Si se corta un borde del árbol de expansión, se convertirá en un subgrafo no conectado; si se agrega un borde, se formará un ciclo. En un gráfico desconectado, el árbol de expansión de componentes conectados constituye el bosque de expansión del gráfico desconectado.

Grado de vértice, grado interno y grado externo Gráfico no dirigido: TD (v), la suma de los grados de todos los vértices de un gráfico no dirigido es igual a 2 veces el número de aristas Gráfico dirigido: el grado del vértice v se divide en ID de grado interno (v) y OD (v) de grado externo. El grado del vértice v es igual a la suma de grados interno y externo: TD (v). =ID(v) OD(v), el grado de entrada de todos los vértices de un gráfico dirigido es igual al grado de salida igual al número de aristas

Bian's Quanhe.com Cada borde se puede marcar con un valor numérico que tiene un cierto significado, que se llama peso del borde. El gráfico con bordes ponderados se llama gráfico ponderado, también conocido como red.

Gráfico denso, gráfico disperso Un gráfico con pocas aristas se llama gráfico disperso y lo contrario se llama gráfico denso. Generalmente, cuando G satisface |E|<|V|log|V|, G se considera un gráfico disperso.

Caminos, longitudes de caminos y bucles Ruta: una ruta desde el vértice vp a vq se refiere a la secuencia de vértices vp,vi1...vim,vq, El número de aristas en un camino se llama longitud del camino. Un camino cuyo primer y último vértice son iguales se llama ciclo o ciclo. Si un gráfico tiene n vértices y más de n-1 aristas, entonces el gráfico debe tener un ciclo.

Camino simple, bucle simple En una secuencia de caminos, un camino cuyos vértices no aparecen repetidamente se denomina camino simple; Excepto el primer vértice y el último vértice, el ciclo en el que los vértices restantes no se detienen en ese gráfico se llama ciclo simple.

distancia Si existe el camino más corto desde el vértice u al vértice v, entonces la longitud de este camino es la distancia de u a v; No hay ningún camino de u a v, entonces la distancia se registra como ∞

árbol dirigido Un gráfico dirigido en el que el grado de entrada de un vértice es 0 y el grado de salida de los vértices restantes es 1 se llama árbol dirigido.

Se refiere al uso de una matriz unidimensional para almacenar la relación entre los vértices en el gráfico y al uso de una matriz bidimensional para almacenar la información de los bordes en el gráfico (la relación de adyacencia entre los vértices La matriz bidimensional que almacena la). La relación de adyacencia entre vértices se llama matriz de adyacencia. La estructura de almacenamiento de todo el gráfico G: #definir MaxVertexNum 100 typedef char VertexType; typedef int tipo de borde; estructura typedef { VertexType Vex[MaxVertexNum]; //Tabla de vértices EdgeType Edge[MaxVertexNum][MaxVertexNum];//matriz de adyacencia, tabla de borde int vexnum, arcnum; }MGráfico;

Cuando un gráfico es un gráfico disperso, el uso del método de lista de adyacencia ahorra mucho espacio; el método de lista de adyacencia del gráfico combina métodos de almacenamiento secuencial y almacenamiento en cadena; Cree una lista enlazada individualmente para cada vértice del gráfico. El nodo en la i-ésima lista enlazada individualmente se adjunta al borde vi del vértice. Esta lista enlazada individualmente es la lista de bordes del vértice vi (un gráfico dirigido se llama. lista de bordes salientes) (la lista de bordes es "Borde" es realmente sorprendente) Cada nodo en la tabla de bordes representa un borde, pero almacena un número de vértice y omite otro número de vértice (en la tabla de vértices) El puntero principal de la tabla de bordes y la información de datos de vértice del gráfico G se almacenan secuencialmente (llamada tabla de vértices); #definir MaxVertexNum 100 typedef struct ArcNode{//nodo de tabla de borde int adjvex;// La posición del vértice señalado por el arco estructura ArcNode *siguiente; //Info Typeinfo; //El peso del borde de la red }Nodo de arco; estructura typedef VNode{ Datos VertexType;//Información de vértice struct VNode *first;//Puntero al primer arco adjunto al vértice }VNodo, AdjList[MaxVertexNum]; estructura typedef { AdjList vértices;//lista de adyacencia int vexnum, arcnum;// El número de vértices y arcos del gráfico }ALGráfico

Una lista entrecruzada es una estructura de almacenamiento vinculada de un gráfico dirigido. Cada arco del gráfico tiene un nodo. El nodo de arco tiene 5 campos: (tailvex, headvex, hlink, tlink, info) tailvex y headvex son respectivamente los vértices de origen e inserción del borde; hlink y tlink conectan respectivamente los nodos de borde de los mismos vértices de origen e inserción. El nodo de vértice tiene 3 campos: (datos, primero en entrar, primero en salir) La lista entrecruzada no es única, pero una lista entrecruzada representa un gráfico determinado. En la lista cruzada, es fácil encontrar el grado de entrada de V y el grado de salida de V.

La lista múltiple de adyacencia es una estructura de almacenamiento en cadena de gráficos no dirigidos Nodos de borde (mark,ivex,ilink,jvex,jlink,info) mark es un campo de bandera, que puede marcar si este borde ha sido buscado; ivex y jvex son las posiciones de los dos vértices adjuntos al borde en el gráfico; ilink apunta al siguiente borde adjunto a ivex; adjunto al vértice jvex info hay un campo de puntero que apunta a diversa información relacionada con el borde; vértice (datos, primer borde)

BFS resuelve el problema de la ruta más corta de fuente única void BFS_MIN_Distance(Gráfico G,int u){ para(i=0;i<G.vexnum;i) //d[i] representa el camino más corto de u a i d[i]=∞;//Inicializar longitud de ruta visitado[u]=VERDADERO; d[u]=0; En cola(Q,u); mientras (! está vacío (Q)) { DeQueue(Q,u); for(w=PrimerVecino(G,u);w>=0;w=SiguienteN vecino(G,u,w)) if(visitado[w]){ visitado[w]=TRUE; d[w]=d[u] 1;//longitud de la ruta 1 EnQueue(Q,w); } } }

árbol de expansión en anchura La matriz de adyacencia se almacena de forma única: su árbol de expansión en amplitud es único El almacenamiento de la lista de adyacencia no es único: su árbol de expansión de amplitud no es único

Similar al recorrido de preorden de un árbol bool visitado[MAX_VERTEX_NUM]; void DFSTraverse(Gráfico G){ para(v=0;v<G.vexnum;v) visitado[v] = FALSO; para(v=0,v<G.vexnum;v) si(!visitado[v]) DFS(G,v); } void DFS(Gráfico G,int v){ visita(v); visitado[v] = VERDADERO; for(w=PrimerVecino(G,v);w>=0;w=SiguienteVecino(G,v,w)) si(!visitado[w]){ DFS(G,w); } }

Se pueden utilizar algoritmos de recorrido de gráficos para determinar la conectividad del gráfico. Si un gráfico no dirigido está conectado, comenzando desde cualquier vértice, se puede acceder a todos los vértices del gráfico mediante un solo recorrido; Si un gráfico dirigido está conectado y hay una ruta desde el punto inicial hasta cada vértice del gráfico, entonces se puede acceder a todos los vértices del gráfico.

Algoritmo prim (BFS) De manera similar a Dijkstra, inicialmente seleccione un vértice del gráfico y agréguelo al árbol T, luego seleccione un vértice más cercano al conjunto actual de vértices en T y agregue el vértice y el borde al árbol T el número de vértices en T; después de cada operación, el número de aristas aumenta en 1 hasta que todos los vértices del gráfico se agreguen al árbol T, T es el árbol de expansión mínimo; Debe haber n-1 aristas en T vacíoPrim(G,T){ T=conjunto vacío; U={W}; while((V-U)!=conjunto vacío){//Si el árbol no contiene todos los vértices Sea (u, v) la arista que hace u∈U y v∈(V-U) y tiene el peso más pequeño; T=T∪{(u,v)};//Los bordes se clasifican en árboles U=U∪{v};//Los vértices se clasifican en árboles } } La complejidad temporal del algoritmo de Prim es O(|V^2|) y no depende de |E|, por lo que es adecuado para resolver el árbol de expansión mínimo de gráficos con aristas densas.

algoritmo de Kruskal A diferencia del algoritmo de Prim, que se expande desde los vértices para generar un árbol de expansión mínimo, el algoritmo de Kruskal selecciona los bordes apropiados en orden creciente de pesos para construir un árbol de expansión mínimo. Inicialmente, cada vértice forma un componente conectado. Luego, en orden de pesos de borde de pequeño a grande, el borde que aún no se ha seleccionado y tiene el peso más pequeño se selecciona continuamente si el vértice adjunto al borde cae en un conectado diferente. componente del componente T, agregue este borde a T; de lo contrario, descarte este borde hasta que todos los vértices en T estén en un componente conectado; vacío Kruskal(V,T){ T=V; //Inicializa T, solo vértices numS=n;//Número de componentes conectados while(numS>1){//Si el número de componentes conectados es mayor que 1 Tome el borde (v, u) con el peso más pequeño de E si (v y u pertenecen a diferentes componentes conectados en T) T=T∪{(v,u)}; números--; } } } El algoritmo de Kruskal utiliza un montón para almacenar el conjunto de aristas, por lo que solo toma O (log | E |) tiempo seleccionar la arista con el peso más pequeño cada vez que agregar una nueva arista es similar al proceso de resolver una equivalencia; clase y se puede utilizar el método de búsqueda de unión Estructura de datos para describir T, la complejidad temporal es O (|E|log|E|), por lo que Kruskal es adecuado para gráficos con aristas dispersas y muchos vértices.

Algoritmo de Dijkstra (BFS) Ruta más corta de fuente única; El algoritmo de Dijkstra establece un conjunto S para registrar los vértices del camino más corto que se ha obtenido. Inicialmente, el punto fuente v0 se coloca en S. Cada vez que se incorpora un nuevo vértice vi al conjunto S, se debe modificar el punto fuente v0. al vértice más corto actual en el valor de longitud de Lujin establecido no se permiten valores de peso negativos en los bordes. Configure dos matrices auxiliares: dist []: registra la longitud de la ruta más corta actual desde el punto de origen v0 a otros vértices. Estado inicial: si hay un arco de v0 a vi, entonces dist [i] es el peso del arco; ] a ∞. (dist[] solo retrocede un paso a la vez - idea BFS) ruta []: ruta [i] representa el nodo predecesor de la ruta más corta desde el punto de origen hasta el vértice i. Al final del algoritmo, se puede trazar el camino más corto desde el punto fuente v0 hasta el vértice vi. Al resolver manualmente, dibuje una matriz dict. Lo más importante es agregar el vértice al conjunto S cada vez que lo seleccione, actualizar la distancia de la ruta de cada punto y luego dar el siguiente paso comenzando desde el último vértice del conjunto. S. Complejidad del tiempo O(|V|^2)

algoritmo de floyd El camino más corto entre cada par de vértices. La recursión genera una secuencia de matriz cuadrada de orden n: A^-1,A^0,..A^N; donde A^k[i][j] representa la longitud desde el vértice i al j, y se utiliza el k-ésimo vértice; como Relajar los vértices medios La complejidad del tiempo es O(|V|^3) (equivalente a ejecutar el algoritmo de Dijkstra una vez para cada vértice O(|V^2|)*|V|), Los bordes con pesos negativos no están permitidos y pueden actuar sobre gráficos dirigidos\gráficos no dirigidos (convertidos en gráficos dirigidos con los mismos lados bilaterales)

Red AOV (Actividad en la red de vértices) Si se utiliza un DAG para representar un proyecto, sus vértices representan actividades y el borde dirigido <Vi, Vj> representa una relación en la que Vi debe preceder a Vj, entonces este tipo de gráfico se denomina red con vértices que representan actividades. Existen muchos algoritmos para la clasificación topológica de redes AOV, uno de los algoritmos más utilizados es: 1. Seleccione un vértice sin predecesor de la red AOV y envíelo 2. Elimine el vértice y todos los bordes dirigidos a partir de él de la red. 3. Repita el paso 1.2 hasta que la red AOV esté vacía o no haya vértices sin predecesores en la red actual (lo que indica que debe haber un ciclo en el gráfico) Dado que generar cada vértice requiere eliminar su borde inicial, la complejidad temporal de la clasificación topológica es O(|V| |E|) Además, la clasificación topológica también se puede implementar usando DFS (comenzando desde los vértices con un grado de entrada de 0 y un grado de salida de no 0 uno por uno, y fallará siempre que se retroceda hasta que se complete un trazo). ) clasificación topológica inversa Comience desde el vértice con grado 0 La red AOV utiliza almacenamiento de matriz de adyacencia. Si es una matriz triangular, debe haber una secuencia topológica y viceversa.

Red AOE (Actividad en la red perimetral) Los eventos se representan mediante vértices, las actividades se representan mediante aristas dirigidas y el costo de completar la actividad se representa mediante el peso en la arista (como el tiempo necesario para completar la actividad). Dos propiedades de la red AOE: 1. Solo después de que ocurre el evento representado por un vértice, pueden comenzar las actividades representadas por los bordes dirigidos a partir del vértice. 2. El evento en un vértice solo puede ocurrir después de que se completen las actividades representadas por los bordes entrantes de un vértice. Solo hay un vértice con un grado de entrada de 0 en la red AOE, llamado vértice de inicio (punto de origen), que representa el comienzo de todo el proyecto. La red AOE también tiene solo un vértice con un grado de salida de 0; , llamado vértice final (sumidero). Representa el final de todo el proyecto. Algunas actividades en la red AOE se pueden llevar a cabo en paralelo, pero todas las actividades en todas las rutas no pueden finalizar hasta que se completen. Por lo tanto, entre todas las rutas desde el origen hasta el sumidero, la ruta con la mayor longitud se denomina ruta crítica. Las actividades en el camino se denominan actividades críticas (encontrar las actividades críticas equivale a encontrar el camino crítico). El tiempo más corto para completar todo el proyecto es la longitud de la ruta crítica.

Practica ASL cuando busques el éxito y el fracaso.

Búsqueda secuencial de tablas lineales generales. typedef struct{//estructura de datos de la tabla de búsqueda ElemType *elem; //Dirección base del espacio de almacenamiento del elemento int TableLen;//La longitud de la tabla }SSTable; int Search_Seq(SSTable ST, clave ElemType){ ST.elem[0] = clave;//Centinela for(i=ST.TableLen;ST.elem[i]!=key;--i);//Mira de atrás hacia adelante devolver yo; } En el algoritmo anterior, ST.elem [0] se llama centinela, por lo que el bucle interno de Search_Seq no tiene que juzgar si la matriz se saldrá de los límites, porque el bucle definitivamente saltará cuando i == 0 sea satisfecho. La introducción de centinelas puede evitar muchos juicios innecesarios, mejorando así la eficiencia del programa.

Búsqueda secuencial en lista ordenada Si se sabe antes de la búsqueda que las palabras clave en la tabla están en orden, luego de que la comparación falle, no es necesario comparar con el otro extremo de la tabla para devolver el error de búsqueda, lo que reduce la longitud promedio de búsqueda de la fracaso de la búsqueda. Se puede utilizar un árbol de decisión para describir el proceso de búsqueda de una lista lineal ordenada. Los nodos circulares representan los elementos que existen en la lista lineal ordenada; los nodos rectangulares son nodos de falla (sus propios nodos vacíos ficticios si hay n nodos); , entonces, en consecuencia, hay n 1 nodos donde la búsqueda falló. La longitud de búsqueda promedio (ASL) de la búsqueda fallida es (1 2 .. n n)/(n 1); la probabilidad de encontrar cada 'nodo fallido' es 1/n 1;

Éxito en ASL=(n 1)/2

int Binary_Search(SeqList L, clave ElemType){ int bajo=0,alto=L.TableLen-1,medio; mientras(bajo<=alto){ medio = (bajo alto)/2; if(L.elem[mid]==key) return mid; else if(L.elem[mid]<clave){ bajo = medio 1; // medio = (bajo alto)/2; } demás{ alto = medio 1; // medio = (bajo alto)/2; } } devolver -1; }

B altura del árbol El número de accesos al disco necesarios para la mayoría de las operaciones en un árbol B es proporcional a la altura del árbol B. Cada nodo del árbol tiene como máximo m subárboles y m-1 palabras clave, y el número de palabras clave debe satisfacer n≤m^h-1; La capa h1 tiene al menos 2 (m/2 límite superior) ^ (h-1) nodos, y la capa h1 es un nodo hoja que no contiene ninguna información; Para un árbol B con n palabras clave, el nodo donde falla la búsqueda del nodo hoja es n 1, por lo que n 1>=2 (m/2 toma el límite superior)^(h-1), es decir, h≤log ( m/2 toma el límite superior)((n 1)/2 1)

Búsqueda de árbol B 1. Encuentra nodos en el árbol B 2. Encuentra palabras clave dentro del nodo. La operación de búsqueda de 1. se realiza en el disco y la operación de búsqueda de 2. se realiza en la memoria; Después de encontrar el nodo de destino, léalo en la memoria y luego use el método de búsqueda secuencial o el método de búsqueda binaria dentro del nodo.

Inserción en el árbol B Si no puede encontrar la posición e insertarla directamente, se destruirán los requisitos en la definición del árbol B. 1. Posicionamiento: busque el nodo que no es hoja en la capa más baja (busque el nodo que no sea hoja, tome el nodo que no sea hoja de la capa anterior) 2. Inserción: el número de palabras clave en cada nodo que no falla está dentro del intervalo [m/2 toma el límite superior -1, m-1] y se puede insertar directamente; Cuando el número de palabras clave de nodo insertadas es mayor que m-1, el nodo se divide. Método de división: tome el límite superior de la posición media m/2 y divida la palabra clave en dos partes. La parte izquierda se incluye en el nodo original y la parte derecha se coloca en el nuevo nodo en la posición media; m/2 toma el límite superior) para insertar el nodo padre del nodo original y así sucesivamente;

Eliminación del árbol B Cuando la palabra clave eliminada k no está en el nodo terminal (el nodo no hoja más bajo), k puede reemplazarse por el predecesor (sucesor) de k k', y luego k' se elimina en el nodo correspondiente y se convierte en una palabra clave. en el nodo terminal; Cuando la palabra clave eliminada está en el nodo terminal (el nodo no hoja más bajo), existen tres situaciones: 1. Eliminar palabras clave directamente: el número de palabras clave ≥ m/2 toma el límite superior -1 2. Los hermanos son suficientes: el número de palabras clave = m/2, tome el límite superior -1, y el número de sus palabras clave hermanas izquierda y derecha (adyacentes) es mayor o igual a m/2, tome el límite superior, luego sus hermanos, padres y él mismo utilizan el método de transposición padre-hijo para lograr el equilibrio. 3. No hay suficientes hermanos: el número de palabras clave eliminadas = m/2 y el límite superior es -1. En este momento, los nodos de sus hermanos izquierdo y derecho (adyacentes) también son = m/2 y el límite superior. es 1. Luego, las palabras clave se fusionarán con las palabras clave en el nodo hermano izquierdo (derecho) y el nodo principal después de la eliminación. El número de palabras clave en el nodo principal se reduce en uno. el nodo raíz se puede reducir directamente a 0 (eliminar el nodo raíz). El nuevo nodo se llama raíz.

Propiedades relacionadas con el árbol B Es necesario comprender la relación entre el número de palabras clave y el número de subárboles: el número de palabras clave es 1 menos que el número de subárboles. Todos los nodos no terminales, excepto el nodo raíz, tienen al menos m/2 subárboles de límite superior (m/2 límite superior - 1 palabra clave) Las palabras clave en los nodos están ordenadas en orden ascendente de izquierda a derecha. Es decir, m/2 toma el límite superior -1≤n≤m-1, es decir, [m/2 toma el límite superior -1, m-1]

B-tree es un árbol deformado de B-tree que aparece en respuesta a las necesidades de la base de datos. Un árbol B de orden m satisface las siguientes condiciones: 1. Cada nodo de rama tiene como máximo m subárboles 2. El nodo raíz no hoja tiene al menos dos subárboles. 3. La cantidad de subárboles de un nodo es igual a la cantidad de palabras clave 4. Todos los nodos hoja contienen todas las palabras clave y punteros a los registros correspondientes. Las palabras clave están organizadas en orden de tamaño en los nodos hoja, y los nodos hoja adyacentes están conectados entre sí en orden de tamaño.

Principales diferencias con los árboles B: 1. Un nodo con n palabras clave en el árbol B tiene n subárboles, y cada palabra clave corresponde a un subárbol; n nodos de palabras clave en el árbol B contienen n-1 subárboles. 2. El rango del número n de palabras clave para cada nodo en el árbol B es [m/2 toma el límite superior, m] (en relación con los límites superior e inferior del número n de palabras clave de nodos en el árbol B más 1 ); nodo raíz B: [1,m],B:[1,m-1] 3. En el árbol B, los nodos hoja contienen información (todas las palabras clave) y los nodos que no son hoja solo sirven como índices. 4. Cada búsqueda en el árbol B, exitosa o no, es una ruta desde el nodo raíz hasta el nodo hoja.

Debido a la búsqueda lineal anterior en tabla y árbol, no existe una relación definida entre la posición del registro en la tabla y la clave del registro. Por lo tanto, al buscar registros en estas tablas, es necesario comparar una serie de palabras clave. Este método de búsqueda se basa en la comparación y la eficiencia de la búsqueda depende del número de comparaciones. Función hash: la función Hash (clave) = Addr que asigna las palabras clave en la tabla de búsqueda a la dirección correspondiente a la palabra clave, es decir, utilizando las características de la palabra clave en sí y utilizando la menor búsqueda de "comparación" posible. La función hash puede asignar varias palabras clave diferentes a la misma dirección, lo que se denomina "colisión". Estas diferentes palabras clave que chocan se denominan sinónimos. Por un lado, una función hash bien diseñada minimizará los conflictos; por otro, los conflictos son inevitables y se deben diseñar métodos para abordarlos. Tabla hash: una estructura de datos a la que se accede directamente en función de palabras clave. En otras palabras, la tabla hash establece una relación de mapeo directo entre palabras clave y direcciones de almacenamiento. Idealmente, la complejidad temporal de buscar en una tabla hash es O(1), lo que significa que no tiene nada que ver con la cantidad de elementos.

1. El dominio de definición de la función hash debe incluir todas las claves de almacenamiento y el rango de valores depende del tamaño o rango de direcciones de la tabla hash. 2. Las direcciones calculadas por la función hash deben distribuirse uniformemente en todo el espacio de direcciones con la misma probabilidad, reduciendo así la aparición de conflictos. 3. La función hash debe ser lo más simple posible y poder calcular el hash correspondiente a cualquier palabra clave en poco tiempo.

Secuencia ordenada L[1..i-1]L(i) Secuencia desordenada L[i 1…n] void InsertSort(ELemType A[],int n){ int i, j; for(i=2;i<=n;i){//Inserte los siguientes n-1 números al frente si(A[i]<A[i-1]){ A[0] = A[i];//Copiar como centinela, A[0] no almacena ningún elemento for(j=i-1;A[0]<A[j];j--){//Encuentre la posición de inserción de atrás hacia adelante A[j 1] = A[j]; A[j 1] = A[0]; } } Complejidad espacial O (1), complejidad espacial O (n ^ 2) Mejor caso: los elementos de la tabla ya están ordenados, tiempo O(n) Peor de los casos: el orden de los elementos en la tabla se invierte, tiempo O(n^2) Dado que cada comparación es de atrás hacia adelante, es estable. Adecuado para listas secuenciales y listas vinculadas (puede encontrar la posición del elemento especificado de adelante hacia atrás) Adecuado para tablas de clasificación básicamente ordenadas con un volumen de datos pequeño

void InsertSort(ElemType A[],int n){ int i,j,bajo,alto,medio; para(i=2;i<=n;i){ A[0] =A[i]; bajo=1;alto=i-1; mientras(bajo<=alto){ medio = (bajo alto)/2; if(A[mid]>A[0])high=mid-1; de lo contrario, bajo = medio 1; } para(j=i-1;j>=alto 1;j--) A[j 1] = A[j]; A[alto 1]=A[0]; } } Complejidad del tiempo O (n ^ 2) El número de comparaciones no tiene nada que ver con el estado inicial de la lista a ordenar, y solo depende del número n de elementos de la lista; El número de movimientos está relacionado con el estado inicial de la lista a ordenar.

Primero divida la tabla de clasificación en varias subtablas (los registros con el mismo incremento forman una subtabla di 1 = di/2, y el último incremento es igual a 1), realice la clasificación por inserción directa en cada subtabla, cuando toda la tabla Cuando los elementos están básicamente en orden, se realiza una clasificación por inserción directa en todos los registros. void ShellSort(ELemType A[],int n){ // A [0] es una unidad de almacenamiento temporal, no un centinela. Cuando j <= 0, se alcanza la posición de inserción. for(dk=n/2;dk>=1;dk/=2)//cambio de tamaño de paso para(i=di 1;i<=n;i) if(A[i]<A[i-dk]){//A[i] debe insertarse en la subtabla incremental ordenada A[0]=A[j];//almacenado temporalmente en A[0] para(j=i-dk;j>0&&A[0]<A[j];j-=dk) A[j dk]=A[j]; } } No hay una conclusión definitiva sobre la complejidad del tiempo, pero se cree que es O(n^2) Inestabilidad de clasificación Adecuado para tablas de secuencia

Compare los valores de los elementos adyacentes de atrás hacia adelante (de adelante hacia atrás) e intercámbielos si están en orden inverso. Las palabras clave flotan gradualmente hacia la superficie como burbujas. void BubbleSort(ELemType A[],int n){ for(int i=0;i<n-1;i){//n-1 veces bandera = falso; para(j=n-1;j>i;j--) if(A[j-1]>A[j]){//Si es orden inverso intercambiar(A[j-1],A[j]); bandera = verdadero; } if(flag==false)//La bandera del fin de la clasificación de burbujas: ni un solo intercambio devolver; } } Espacio O(1), tiempo O(n^2) Estabilidad: los elementos no se intercambiarán cuando sean iguales, estables La secuencia producida por la clasificación de burbujas está ordenada globalmente, lo que no es equivalente al ordenamiento local de la clasificación por inserción.

Elija cualquier elemento de la lista para ordenarlo como pivote (generalmente el primer elemento) y divida la secuencia ordenada en dos partes independientes L[1..k-1] L(k) L[k 1, ...n] , de modo que la primera mitad sea más pequeña que el pivote y la segunda mitad sea más grande que el pivote, y el pivote se coloca en la posición final L (k). Este proceso se denomina clasificación rápida de una sola pasada (división de una sola pasada). void QuickSort(ELemType A[],int bajo,int alto){ if(low<high){//Condición para salto recursivo int pivotpos = Partición(A,baja,alta);//Partición Ordenación rápida(A,baja,pivotpos-1); QuickSort(A,puntos de pivote 1,alto); } } El rendimiento y la clave del algoritmo de clasificación rápida provienen de la operación de partición. Hay muchas versiones de la operación de partición. Aquí, el primer elemento se utiliza como pivote para la partición. int Partición(ElemType A[],int bajo,int alto){ ElemType pivote=A[bajo]; while(low<high){//Condición de interrupción del bucle while(bajo<alto && A[alto]>=pivote) --alto; A[bajo]=A[alto]; whilie(bajo<alto && A[bajo]<=pivote) bajo; A[alto] = A[bajo]; } A[bajo] = pivote; retorno bajo; } Espacio: se requiere una pila de trabajo recursiva, preferiblemente O (log2n), promedio O (log2n) (dividido por la mitad tanto como sea posible, como un árbol binario completo), En el peor de los casos, O (n) (el número de elementos en las dos áreas divididas es n-1 y 0, se requieren n-1 llamadas recursivas y la profundidad de la pila es O (n)). Tiempo: el tiempo de ejecución de la clasificación rápida está relacionado con si la división es simétrica. El peor de los casos es mitad n-1 y mitad 0. La asimetría máxima ocurre en cada nivel de recursividad, que corresponde a la secuencia ordenada inicial (secuencial o inversa). orden), es O(n^2) Estabilidad: Inestable, los mismos elementos se transferirán a diferentes partes y se cambiarán las posiciones relativas. Nota: La clasificación rápida no produce una subsecuencia ordenada, pero el elemento pivote se coloca en la posición final en cada pasada. Mejore la eficiencia: 1. Seleccione elementos pivote que puedan dividir la secuencia tanto como sea posible 2. Seleccione aleatoriamente elementos pivote La división más ideal: ambos problemas planteados son más pequeños que n/2, el tiempo es O (nlog2n) y el tiempo de ejecución de la clasificación rápida está muy cerca del mejor de los casos en promedio. Quicksort es el algoritmo de clasificación con el mejor rendimiento promedio entre todos los algoritmos de clasificación internos.

void SelectSort(ElemType A[],int n){ for(i=0;i<n-1;i)//Un total de n-1 veces min=i;//Registra la posición mínima del elemento para(j=i 1;j<n;j) si(A[j]<A[min]) mín = j; if(min!=i) swap(A[i],A[min]); } } Espacio O(1), tiempo O(n^2) Estabilidad: puede provocar que cambie la posición relativa de las palabras clave que contienen los mismos elementos, lo cual es inestable.

El montón es un objeto de matriz de un árbol. Una matriz unidimensional puede considerarse como un árbol binario completo que satisface las propiedades. 1.L(i)>=L(2i) y L(i)>=L(2i 1) o 2.L(i)<=L(2i) y L(i)<=L(2i 1) ( 1<=i<=n/2 (tomar el límite); Aquellos que satisfacen 1. se consideran montones de raíces grandes (montones superiores grandes), y aquellos que satisfacen 2. se consideran montones de raíces pequeños (montones superiores pequeños). Clasificación del montón: primero, n elementos de la matriz se integran en un montón inicial, después de generar el elemento superior del montón, el elemento inferior del montón se envía a la parte superior del montón; cumple con las propiedades de un montón raíz grande y el montón se destruye. El elemento superior del montón se mueve a la parte superior del montón. Ajústelo hacia abajo para que pueda continuar manteniendo la naturaleza de un montón superior grande. Luego genere el elemento superior de la torre y repita hasta que solo quede un elemento en el montón. Algoritmo de clasificación de montón: void HeapSort(ElemType A[],int len){ BuildMaxHeap(A,len); para(i=len;i>1;i--){ Swap(A[i],A[1]);// Genera el elemento superior del montón e intercámbialo con el elemento inferior del montón HeadAdjust(A,1,i-1);//Organiza los elementos i-1 restantes en una pila } } La clasificación del montón es adecuada para situaciones en las que hay muchas palabras clave (del orden de cientos de millones) Ejemplo: para seleccionar los 100 valores máximos principales entre 100 millones de números, primero use una matriz de 100, lea los primeros 100 números, construya un pequeño montón superior y luego lea los números restantes en secuencia si son menores que. en la parte superior del montón, deséchelos. De lo contrario, reemplace la parte superior del montón con este número y cambie el tamaño del montón. Una vez leídos los datos, los 100 números del montón son los requeridos. Eficiencia espacial O (1), eficiencia temporal O (nlog2n) inestable

Suponiendo que la tabla a ordenar contiene n registros, se puede considerar como n subtablas ordenadas, cada una con una longitud de 1, y luego fusionarlas en pares para obtener n/2 registros acotados superiores con una longitud de 2 o 1. Lista de secuencia; continúe fusionando de dos en dos hasta que se fusione en una lista ordenada de longitud n. Este método se llama clasificación por fusión bidireccional. ElemType *B=(ElemType*)malloc((n 1)*sizeof(ElemType));//Matriz auxiliar B void Merge(ElemType A[],int bajo,int medio,int alto){ //La tabla A[low..mid]A[mid 1..high] está ordenada, combínalas en una lista ordenada para(int k=bajo;k<=alto;k) B[k]=A[k]; for(i=bajo;j=medio 1;k=i,i<=medio&&j<=alto;k ){ si(B[i]<=B[j]) A[k]=B[i]; de lo contrario A[k]=B[j]; } mientras(i<=medio) A[k ]=B[i ]; mientras(j<=alto) A[k ]=B[j ]; } void MergeSort(ELemType A[],int bajo,int alto){ si(bajo<alto){ int medio=(bajo alto)/2; MergeSort(A,bajo,medio); MergeSort(A,mediados de 1,alto); Fusionar(A,bajo,medio,alto); } } Eficiencia espacial: n unidades de espacio auxiliar, complejidad espacial O (n) Eficiencia del tiempo: cada fusión es O (n), y se requieren fusiones de límite superior log2n. La complejidad del tiempo del algoritmo es O (nlog2n). Estabilidad: la operación Merge() no cambiará el orden relativo de los registros con la misma palabra clave, estable

Ordene según el tamaño de las palabras clave. La palabra clave de cada nodo aj consta de d tuplas, kd-1j es la palabra clave principal y kj0 es la palabra clave secundaria. Para lograr la clasificación de varias palabras clave, normalmente existen dos métodos: 1. Primero el bit más significativo (MSD), divida varias subsecuencias más pequeñas capa por capa de acuerdo con el peso decreciente de las palabras clave y, finalmente, todas las subsecuencias se conectan en una secuencia ordenada. 2. Primero el dígito más bajo (LSD), ordenado en orden ascendente por peso de palabra clave para formar una secuencia ordenada. funcionar: 1. Distribución: Deje vacía la cola Q0...Qr-1 y luego agréguela a la cola correspondiente según el bit correspondiente de cada nodo. 2. Colección: conecte los nodos de la cola de Q0..Qr-1 de un extremo a otro para obtener una nueva secuencia de nodos para formar una nueva tabla lineal. Ejemplo: para ordenar secuencias por debajo de 1000, primero determine la base r (puede considerarse como base r. La base de 1000 es 10, por lo que se necesitan 10 colas de cadena durante el proceso de clasificación). Los números inferiores a 1000 son tres dígitos, por lo que se requieren tres operaciones de "distribución" y "recopilación"; todos los registros con la misma palabra clave más baja (dígito de unidades) se asignan a una cola y luego se realiza la operación de "recopilación". Eficiencia del espacio: el espacio de almacenamiento auxiliar requerido para un viaje de clasificación es r (r colas: r punteros de cabecera de cola, r punteros de cola de cola), O (r) Eficiencia del tiempo: d pases de asignación y recolección, un paso de asignación requiere O (n), un paso de recolección requiere O (r), la complejidad del tiempo es O (d (n r)), independientemente del estado inicial de la secuencia . Estabilidad: la clasificación Radix en sí requiere que la clasificación bit a bit sea estable, por lo que es estable.

1. Si n es pequeño, se puede utilizar la ordenación por inserción directa o la ordenación por selección simple. Dado que la ordenación por inserción directa requiere más movimientos de registros que la ordenación por selección simple, cuando el registro en sí tiene una gran cantidad de información, la ordenación por selección simple es mejor. 2. Si el estado inicial del archivo está básicamente ordenado por palabras clave, es apropiado utilizar la inserción directa o la clasificación por burbujas. 3. Si n es grande, utilice el método de clasificación O (nlog2n): clasificación rápida, clasificación en montón o clasificación por combinación. En la actualidad, la clasificación rápida se considera el mejor método de clasificación interna basada en comparación. Cuando las palabras clave que se van a clasificar se distribuyen aleatoriamente, la clasificación rápida tiene el tiempo promedio más corto y requiere menos espacio auxiliar que la clasificación rápida. no ocurrirá. Pero ambas clasificaciones son inestables. Si se requiere un algoritmo O(nlog2n) estable, se utiliza la ordenación por fusión, pero no se recomienda fusionar pares de un solo registro. Generalmente se pueden usar en combinación con la ordenación por inserción directa: primero use la ordenación por inserción directa para obtener la subdivisión ordenada más larga. . archivos y luego fusionarlos de dos en dos. La clasificación por inserción directa es estable y la clasificación por combinación mejorada también es estable. 4. En el método de clasificación basado en comparación, después de cada comparación de dos tamaños de palabras clave, solo ocurren dos transferencias posibles. Por lo tanto, se puede usar un árbol binario para describir el proceso de decisión de comparación. Se puede demostrar que: cuando hay n archivos. Cuando las palabras clave se distribuyen aleatoriamente, cualquier algoritmo de clasificación que se base en la "comparación" requiere al menos O (nlog2n) tiempo. 5. Si n es muy grande y la cantidad de palabras clave registradas es pequeña y se puede descomponer, es mejor utilizar la clasificación por base. 6. Cuando el registro en sí tiene una gran cantidad de información, para evitar perder mucho tiempo moviendo el registro, se puede utilizar una lista vinculada como estructura de almacenamiento.

La clasificación realizada en la memoria se denomina clasificación interna. En muchas aplicaciones, es necesario ordenar archivos grandes y no se puede copiar el archivo completo en la memoria para ordenarlo. Por lo tanto, los registros que se van a clasificar deben almacenarse en una memoria externa. Durante la clasificación, los datos se transfieren a la memoria parte por parte para la clasificación. Durante el proceso de clasificación, se requieren múltiples intercambios entre la memoria y el almacenamiento externo. Esta clasificación se llama clasificación externa.

El costo de tiempo durante el proceso de clasificación externa considera principalmente la cantidad de accesos al disco, es decir, la cantidad de IO La clasificación externa generalmente utiliza clasificación por combinación: 1. Según el tamaño del búfer de memoria, divida los archivos en el almacenamiento externo en subarchivos de longitud l, léalos en la memoria en secuencia y use el método de clasificación interno para ordenarlos y escriba los subarchivos ordenados. obtenidos después de volver a clasificarlos en el almacenamiento externo, estos subarchivos ordenados se denominan segmentos fusionados o cadenas secuenciales; 2. Combine estos segmentos fusionados uno por uno, de modo que los segmentos fusionados aumenten gradualmente de pequeño a grande hasta obtener el archivo ordenado completo. La fusión de una sola pasada se refiere a fusionar todos los segmentos del mismo nivel actual en uno Tiempo total de clasificación externa = tiempo requerido para la clasificación interna, tiempo de lectura y escritura de información externa, tiempo requerido para la fusión interna El tiempo para leer y escribir información del almacenamiento externo es mucho más largo que el tiempo para la clasificación interna y la fusión interna. La lectura y escritura de información del almacenamiento externo se basa en "bloques de disco". Una combinación requiere el número total de registros/registros de uno. El bloque de disco se leerá y escribirá varias veces. Por lo tanto, el número total de lecturas y escrituras necesarias: 2*número total de registros/número de registros en un bloque de disco*n (número de veces) número total de registros/número de registros. en un bloque de disco (la clasificación interna también requiere una lectura y escritura completa) Para r segmentos de fusión iniciales, realice una fusión equilibrada de k vías. La altura del árbol (árbol k-ario invertido) = logkr y el límite superior = el número de pasadas de fusión S. Se puede ver que aumentar el número de rutas de fusión k o reducir el número de segmentos de fusión iniciales r puede reducir el número de pases de fusión S, reduciendo así el número de E/S de disco y mejorando la velocidad de clasificación externa.

Aumentar el número de rutas de fusión k puede reducir el número de pasos de fusión S, pero aumentará el tiempo de fusión interna. Al fusionar internamente, seleccionar la palabra clave más pequeña entre k elementos requiere comparaciones k-1, y cada combinación de n elementos requiere comparaciones (n-1) (k-1), S veces. El número de comparaciones necesarias para la fusión es S(n-1)(k-1)=log2r toma el límite superior (n-1)(k-1)/log2k toma el límite superior, donde (k-1)/log2k toma el límite superior y crece con el crecimiento de k. Por lo tanto, no se puede utilizar el algoritmo de ordenación por fusión interno ordinario.

Para reducir r, r=n/l toma un límite superior, por lo que necesitamos encontrar una manera de generar un segmento de fusión inicial más largo l. Supongamos que el archivo inicial a ordenar es FI, el archivo de salida del segmento de fusión inicial es FO, el área de trabajo de la memoria es WA, FO y WA están inicialmente vacíos y WA puede acomodar w registros. Los pasos del algoritmo de selección de reemplazo son los siguientes: 1. Ingrese w registros de FI al espacio de trabajo WA 2. Seleccione el registro con el valor mínimo de palabra clave de WA y regístrelo como MINIMAX. 3. Grabar MINIMAX a FO 4. Si FI no está vacío, envíe el siguiente registro de FI a WA 5. Seleccione el registro de palabra clave más pequeño de todos los registros en WA con palabras clave mayores que las palabras clave del registro MINIMAX como el nuevo registro MINIMAX. 6. Repita los pasos 3 a 5 hasta que no se pueda seleccionar ningún MINIMAX nuevo en WA, obtenga un segmento de fusión inicial y envíe una bandera de fin del segmento de fusión a FO. 7. Repita los pasos 2 a 6 hasta que WA esté vacío y se obtengan todos los segmentos fusionados iniciales. El proceso de selección de registros MINIMAX en WA requiere el uso de árboles perdedores.

Después de ordenar el archivo por selección de sustitución, se obtienen segmentos fusionados iniciales de diferentes longitudes. ¿Cómo organizar el orden de fusión de los segmentos de fusión iniciales con diferentes longitudes para minimizar la cantidad de IO? Dibuje el árbol de combinación correspondiente. La longitud de ruta ponderada WPL del árbol es el número total de registros leídos durante el proceso recursivo. Extienda la idea del árbol de Huffman al caso del árbol k-ary. En el árbol de combinación, combine primero el segmento de combinación inicial con una pequeña cantidad de registros y deje que el segmento de combinación inicial con una gran cantidad de registros. fusionado por último, se puede establecer el IO total. El mejor árbol de fusión con el menor número de veces. Método para construir el mejor árbol de fusión: si el segmento de fusión inicial no es suficiente para formar un árbol k-ario estricto, es necesario agregar un "segmento virtual" con una longitud de 0. ¿Cómo determinar la cantidad de segmentos virtuales a agregar? Un árbol k-ario estricto tiene n0=(k-1)nk 1. Si (n0-1)%(k-1)=0, entonces el libro de fusión k-fork se puede construir con nk nodos internos. Si (n0-1)%(k-1)=u!=0, entonces se pueden agregar segmentos de fusión vacíos k-u-1 para crear un árbol de fusión