Cola de pila de lista de diccionario
Capítulo 1 Estructura de datos y algoritmo
1.1 Algoritmo
Algoritmo: se refiere a una descripción precisa y completa de la solución.
Los algoritmos no son iguales a los programas, ni tampoco a los métodos informáticos, por lo que la programación no puede ser mejor que el diseño de algoritmos.
Características básicas de un algoritmo: Es un conjunto de reglas que define estrictamente la secuencia de operaciones, y cada regla es válida y clara, y esta secuencia terminará en un número limitado de veces. Las funciones incluyen:
(1) Viabilidad;
(2) Determinismo, cada paso del algoritmo debe estar claramente definido y no se permiten interpretaciones ambiguas ni ambigüedades;
p>
(3) Tiene una naturaleza finita y el algoritmo debe completarse en un tiempo limitado, es decir, puede finalizarse después de ejecutar un número limitado de pasos, incluido el significado de un tiempo de ejecución razonable. ;
(4) Dominar suficiente información.
Los elementos básicos del algoritmo: primero, el cálculo y operación de los objetos de datos; el segundo es la estructura de control del algoritmo.
Conjunto de instrucciones: Colección de todas las instrucciones que un sistema informático puede ejecutar.
Las operaciones y operaciones básicas incluyen: operaciones aritméticas, operaciones lógicas, operaciones relacionales y transmisión de datos.
Estructuras de control de algoritmos: estructura secuencial, estructura de selección y estructura de bucle.
Los métodos básicos de diseño de algoritmos incluyen enumeración, inducción, recursividad, recursividad, tecnología de recursividad de reducción de depósitos y retroceso.
Complejidad algorítmica: complejidad temporal del algoritmo y complejidad espacial del algoritmo.
La complejidad temporal de un algoritmo se refiere al esfuerzo computacional requerido para ejecutar el algoritmo.
La complejidad del espacio del algoritmo se refiere al espacio de memoria necesario para ejecutar el algoritmo.
1.2 Conceptos básicos de estructura de datos
Tres aspectos de la investigación de la estructura de datos:
(1) La relación lógica interna entre los elementos de datos en el conjunto de datos, que es, la estructura lógica de los datos;
(2) Al procesar datos, la relación de almacenamiento de cada elemento de datos en la computadora, es decir, la estructura de almacenamiento de los datos;
(3) Operaciones de varias estructuras de datos.
Una estructura de datos se refiere a una colección de elementos de datos interrelacionados.
La estructura lógica de los datos incluye:
(1) Representa la información de los elementos de datos
② Representa la relación entre los elementos de datos.
La estructura de almacenamiento de datos incluye orden, enlace, índice, etc.
Condiciones de estructura lineal:
(1) Hay y solo hay un nodo raíz;
(2) Cada nodo tiene como máximo una pieza frontal y una pieza trasera.
Estructura no lineal: estructura de datos que no cumple las condiciones de una estructura lineal.
1.3 Tabla lineal y su estructura de almacenamiento secuencial
Una tabla lineal consta de un conjunto de elementos de datos. La posición de los elementos de datos sólo depende de sus propios números de serie y de las posiciones relativas. entre los elementos es lineal.
En una tabla lineal compleja, un elemento de datos compuesto por múltiples elementos de datos se llama registro, y una tabla lineal compuesta por múltiples registros también se llama archivo.
Características estructurales de listas lineales no vacías;
(1) Y solo hay un nodo raíz a1, que no tiene antecedente;
(2) Sólo hay un Nodo terminal y no tiene posparte;
(3) Excepto el nodo raíz y el nodo terminal, todos los demás nodos tienen un solo antecedente y un consecuente. El número de nodos n se denomina longitud de la lista lineal, y cuando n = 0 se denomina lista vacía.
La estructura de almacenamiento secuencial de una mesa lineal tiene las siguientes dos características básicas:
El espacio de almacenamiento que ocupan todos los elementos de la mesa lineal es continuo;
(2) Los elementos de datos de una tabla lineal se almacenan en el espacio de almacenamiento en un orden lógico.
La dirección de almacenamiento de ai es: ADR (AI) = ADR (a 1) (I-1) k, donde ADR (a 1) es la dirección del primer elemento, y k significa que cada El elemento ocupa un número de bytes.
Operaciones de lista de secuencias: inserción y eliminación.
(Consulte las páginas 14-16 para obtener más detalles)
1.4 Pila y cola
La pila es una lista lineal con un solo extremo utilizado para la inserción y eliminación. El extremo donde se permiten las inserciones y eliminaciones se denomina parte superior de la pila, y el otro extremo donde no se permiten las inserciones y eliminaciones se denomina parte inferior de la pila.
La pila organiza los datos según "FILO" o "LIFO", y la pila tiene una función de memoria. Utilice top para representar la posición en la parte superior de la pila y use bottom para representar la posición en la parte inferior de la pila.
Operaciones básicas de la pila: (1) Insertar un elemento se llama operación de pila; (2) Eliminar un elemento se llama operación de pila (3) Leer el elemento superior de la pila es asignar; el elemento superior de la pila a una variable especificada, el puntero permanece sin cambios en este momento.
Cola se refiere a una lista lineal que permite la inserción en un extremo (el final de la cola) y la eliminación en el otro extremo (el encabezado de la cola). El puntero posterior apunta al final de la línea y el puntero frontal apunta al comienzo de la línea.
Una cola es una lista lineal de FIFO o LILO.
Las operaciones de cola incluyen (1) operación de puesta en cola: insertar un elemento desde el final de la cola; (2) operación de salida: eliminar un elemento del encabezado de la cola.
Cola circular: s=0 significa que la cola está vacía, s=1, front=rear significa que la cola está llena.
1.5 Lista Enlazada Lineal
Cada nodo en la estructura de datos corresponde a una unidad de almacenamiento, llamada nodo de almacenamiento.
Un nodo consta de dos partes: (1) se utiliza para almacenar valores de elementos de datos, llamados campos de datos; (2) se usa para almacenar punteros, llamados campos de puntero, que se usan para apuntar al nodo anterior o al siguiente. nodo.
En la estructura de almacenamiento en cadena, el espacio de almacenamiento utilizado para almacenar la estructura de datos puede ser discontinuo y el orden de almacenamiento de cada nodo de datos puede ser inconsistente con la relación lógica entre los elementos de datos. por el campo del puntero.
El almacenamiento en cadena se puede utilizar para representar estructuras lineales y no lineales.
Para listas enlazadas lineales, HEAD se denomina puntero principal y HEAD=NULL (o 0) se denomina lista vacía. Si hay dos punteros, el puntero izquierdo (Llink) apunta al nodo anterior y el puntero derecho (Rlink) apunta al siguiente nodo.
Operaciones básicas de listas enlazadas lineales: búsqueda, inserción y borrado.
1.6 Árboles y árboles binarios
Un árbol es una estructura no lineal simple y todos los elementos tienen características jerárquicas obvias.
En la estructura de árbol, cada nodo tiene un solo antecedente, llamado nodo padre, y un solo nodo sin antecedentes, llamado nodo raíz del árbol. Cada nodo puede tener múltiples nodos sucesores, que se denominan hijos del nodo. Los nodos sin nodos sucesores se denominan nodos hoja.
En la estructura de árbol, el número de secuelas que posee un nodo se denomina grado del nodo, y el grado máximo entre todos los nodos se denomina grado del árbol. El nivel más alto de un árbol se llama profundidad del árbol.
Características de los árboles binarios: (1) Un árbol binario no vacío tiene solo un nodo raíz (2) Cada nodo tiene como máximo dos subárboles, que se denominan subárbol izquierdo y subárbol derecho del nodo; .
Propiedades básicas de los árboles binarios:
(1) El k-ésimo nivel de un árbol binario tiene como máximo 2k-1 (k≥1) nodos;
(2) Un árbol binario con profundidad m tiene como máximo 2m-1 nodos;
(3) Siempre hay un nodo más con grado 0 (es decir, nodo hoja) que nodo con grado 2;
(4) La profundidad de un árbol binario con n nodos es al menos [log2n] 1, donde [log2n] representa la parte entera de log2n;
(5) La profundidad de un árbol binario completo un árbol binario con n nodos es [log2n] 1;
(6) Supongamos que un árbol binario completo * * * tiene n nodos.
Si a partir del nodo raíz, los números de nodo son números naturales 1, 2,...n en orden (de izquierda a derecha para cada capa) (k = 1, 2...n), se llega a la siguiente conclusión:
(1) Si k=1, entonces el nodo es el nodo raíz y no tiene nodo padre; si k gt1, el número de nodo padre del nodo es int (k/2);
(2 ) Si 2k ≤ n, el número de nodo secundario izquierdo del nodo numerado k es 2k; de lo contrario, el nodo no tiene nodo secundario izquierdo (ni nodo secundario derecho
(3) Si 2k 1 ≤ n, entonces el número de nodo secundario derecho del nodo numerado k es 2k 1; de lo contrario, el nodo no tiene ningún nodo secundario derecho;
Un árbol binario completo significa que todos los nodos de cada nivel excepto el último nivel tienen dos hijos, por lo que un árbol binario completo de profundidad m en el nivel K tiene 2k-1 nodos y 2m-1 nodo.
Un árbol binario completo significa que el número de nodos en cada capa alcanza el máximo excepto la última capa, a la que solo le faltan unos pocos nodos a la derecha.
La estructura de almacenamiento del árbol binario adopta una estructura de almacenamiento en cadena, y los árboles binarios completos y los árboles binarios completos se pueden almacenar en orden.
Recorrido del árbol binario:
(1) Recorrido del prefacio (DLR): primero visite el nodo raíz, luego atraviese el subárbol izquierdo y finalmente atraviese el subárbol derecho;
(2) Recorrido de orden intermedio (LDR), primero atraviesa el subárbol izquierdo, luego visita el nodo raíz y finalmente atraviesa el subárbol derecho;
(3) Recorrido de postorden (LRD) primero atraviesa el subárbol izquierdo, luego se visita el subárbol derecho y finalmente se visita el nodo raíz.
1.7 Tecnología de búsqueda
Uso de búsqueda secuencial:
(1) Las tablas lineales están desordenadas;
(2) Las tablas adoptan la cadena estructura de almacenamiento.
La búsqueda binaria sólo funciona en listas ordenadas y almacenadas en secuencia. Para una lista lineal ordenada de longitud n, en el peor de los casos, solo requiere comparaciones log2n.
1.8 Tecnología de clasificación
La clasificación se refiere a clasificar una secuencia desordenada en una secuencia ordenada en orden no descendente de valores.
Método de clasificación de intercambio: (1) Método de clasificación de burbujas, el número de comparaciones es n (n-1)/2 (2) Método de clasificación rápida.
Método de clasificación por inserción: (1) Método de clasificación por inserción simple, que requiere n (n-1)/2 comparaciones en el peor de los casos (2) Método de clasificación Hill, que requiere n (n-1) /2 comparaciones en el peor de los casos O(n 1,5) comparaciones.
Método de clasificación por selección: (1) Método de clasificación por selección simple,
El peor de los casos requiere n (n-1)/2 comparaciones (2) Método de clasificación en montón, en En el; En el peor de los casos, se requieren comparaciones O(nlog2n).
-
Capítulo 2 Conceptos básicos de programación
2.1 Métodos y estilos de diseño de programación
Cómo formar un buen estilo de programación
1. Documentación del programa fuente; 2. Método de interpretación de datos;
3.
Los comentarios se dividen en comentarios de prefacio y comentarios funcionales. El primero es la estructura clara de la oración y el segundo es la eficiencia.
2.2 Programación Estructurada
Los cuatro principios del método de programación estructurada son: 1. De arriba hacia abajo; 2. Mejora gradual; 3. Modularización 4. Limitar el uso de declaraciones goto.
La estructura básica y las características de los programas estructurados;
(1) Estructura de secuencia: programación simple, la estructura más básica y comúnmente utilizada;
(2) Estructura de selección: también conocida como estructura de rama, que incluye selección simple y estructura de selección de múltiples ramas, qué rama se selecciona para ejecutar la secuencia de oraciones correspondiente de acuerdo con las condiciones;
(3) Estructura de repetición: también conocida como bucle estructura, puede determinar si el mismo segmento de programa debe ejecutarse repetidamente en función de determinadas condiciones.
2.3 Programación orientada a objetos
Programación orientada a objetos: marcada por el lenguaje SIMULA desarrollado por la Universidad de Oslo y el Centro Noruego de Computación a finales de los años 1960.
Ventajas del método orientado a objetos:
(1) Consistente con el método de pensamiento utilizado por los humanos;
②Buena estabilidad;
(3) Buena reutilización;
④ Fácil de desarrollar productos de software a gran escala
(5) Buena capacidad de mantenimiento.
Objeto es el concepto más básico en el método orientado a objetos y puede usarse para representar cualquier entidad en el mundo objetivo. El objeto es la abstracción de la entidad.
Los objetos en los métodos de programación orientada a objetos son entidades utilizadas para describir cosas objetivas en el sistema y son las unidades básicas del sistema. Consta de un conjunto de propiedades que representan sus características estáticas y un conjunto de operaciones que se pueden realizar.
Los atributos son información contenida en un objeto y las operaciones describen las funciones realizadas por el objeto. Las operaciones también se denominan métodos o servicios.
Características básicas de los objetos:
(1) Unicidad de identificación
(2) Clasificación;
③Polimorfismo; >
④Encapsulación;
(5) El módulo tiene buena independencia.
Una clase se refiere a una colección de objetos con * * * las mismas propiedades y * * * los mismos métodos. Por lo tanto, una clase es una abstracción de un objeto y un objeto es una instancia de la clase correspondiente.
Los mensajes son información que se pasa entre una instancia y otra instancia.
La composición del mensaje incluye (1) el nombre del objeto que recibe el mensaje; (2) el identificador del mensaje, también llamado nombre del mensaje; ③ cero o más parámetros.
La herencia es la capacidad de obtener directamente propiedades y características existentes sin tener que definirlas repetidamente.
La herencia se divide en herencia única y herencia múltiple. La herencia única significa que una clase puede tener solo una clase principal, mientras que la herencia múltiple significa que una clase puede tener varias clases principales.
El polimorfismo se refiere al fenómeno de que un mismo mensaje conducirá a acciones completamente diferentes cuando lo reciban diferentes objetos.
-
Capítulo 3 Conceptos básicos de la ingeniería de software
3.1 Conceptos básicos de la ingeniería de software
El software informático son programas, datos y documentos relacionados La colección completa de.
Las funciones de este software incluyen:
(1) El software es una entidad lógica;
(2) La producción de software es diferente de la producción de hardware proceso de producción obvio;
(3) El software no tiene problemas de desgaste y envejecimiento durante la operación y el uso;
(4) El desarrollo y el funcionamiento del software dependen y son. afectado por las restricciones del sistema informático, lo que conduce a problemas de trasplante de software;
(5) El software es complejo y costoso;
(6) El desarrollo de software involucra muchos factores sociales.
El software se divide en software de aplicación, software de sistema y software de soporte (o software de herramienta) según sus funciones.
La crisis del software se manifiesta principalmente en cuestiones como el coste, la calidad y la productividad.
La ingeniería de software es un conjunto de métodos, herramientas, documentación, estándares de práctica y procedimientos para definir, desarrollar y mantener software informático.
La ingeniería del software incluye tres elementos: métodos, herramientas y procesos.
El proceso de ingeniería de software es un conjunto de recursos y actividades interrelacionados que transforman el software en resultados, incluidas cuatro actividades básicas:
(1) especificación de p-software;
②d-Desarrollo de software;
(3) Verificación de software;
(4) Evolución del software.
Ciclo del software: El proceso de los productos de software desde la propuesta, implementación, uso y mantenimiento hasta la discontinuación y el retiro.
El ciclo de vida del software tiene tres etapas: definición del software, desarrollo del software y operación y mantenimiento. Las principales etapas de la actividad incluyen:
(1) Estudio y planificación de viabilidad;
②Análisis de requisitos;
③Diseño de software;
(4 ) Implementación de software;
⑤ Pruebas de software
(6) Operación y mantenimiento.
Objetivos y principios de la ingeniería de software;
Objetivo: Bajo la premisa de un costo y cronograma dado, desarrollar productos con efectividad, confiabilidad, comprensibilidad, mantenibilidad y confiabilidad. , adaptable, portátil, rastreable e interoperable y que satisfaga las necesidades de los usuarios.
Objetivos básicos: pagar menores costos de desarrollo; cumplir con los requisitos funcionales del software; obtener un mejor rendimiento del software; desarrollar software que sea fácil de portar; ser capaz de completar el desarrollo a tiempo y entregarlo a tiempo.
Principios básicos: abstracción, ocultación de información, modularidad, localización, determinismo, coherencia, exhaustividad y verificabilidad.
Los contenidos de investigación teórica y técnica de la ingeniería de software incluyen principalmente: tecnología de desarrollo de software y gestión de ingeniería de software.
La tecnología de desarrollo de software incluye: metodología de desarrollo de software, proceso de desarrollo, herramientas de desarrollo y entorno de ingeniería de software.
La gestión de la ingeniería de software incluye: gestión de software, economía de la ingeniería de software, psicología del software, etc.
La gestión del software incluye organización del personal, cronograma, control de calidad, gestión de la configuración, planificación de proyectos, etc.
Los principios de la ingeniería de software incluyen abstracción, ocultación de información, modularidad, localización, determinismo, coherencia, integridad y verificabilidad.
3.2 Método Estructurado
El núcleo y fundamento del método estructurado es la teoría de la programación estructurada.
Los métodos de análisis de requisitos incluyen (1) método de análisis de requisitos estructurado; (2) método de análisis orientado a objetos.
A partir de las características del modelo establecido por el análisis de la demanda, se divide en análisis estático y análisis dinámico.
La esencia del método estructurado es tomar el flujo de datos como centro, descomponerlo de arriba a abajo, establecer el flujo de procesamiento del sistema y utilizar el diagrama de flujo de datos y el diccionario de datos como herramientas principales para Establecer el modelo lógico del sistema.
Herramientas comunes para análisis estructurado
(1) Diagrama de flujo de datos (2) Diccionario de datos (3) Árbol de decisiones;
Diagrama de flujo de datos: una herramienta para describir el proceso de procesamiento de datos. Es una representación gráfica de los requisitos que comprenden el modelo lógico y apoya directamente el modelado de funciones del sistema.
Diccionario de datos: una lista organizada y definiciones precisas y rigurosas de todos los elementos de datos relevantes para un sistema para que los usuarios y analistas del sistema tengan la misma comprensión de las entradas, salidas, componentes de almacenamiento y resultados de cálculos intermedios.
Árbol de decisión: distinga qué condiciones juzgar y qué conclusiones juzgar a partir de la descripción textual de la definición del problema, descubra la relación subordinada, la relación paralela y la relación de selección entre las condiciones de juicio de acuerdo con los conectivos en el material de descripción y construir un árbol de decisiones basado en ellos.
Tabla de decisiones: similar a un árbol de decisiones, cuando el procesamiento en el diagrama de flujo de datos depende de los valores de múltiples condiciones lógicas, es decir, se provoca un conjunto de acciones para completar el procesamiento. por la combinación de los valores de un conjunto de condiciones Cuando, es más apropiado describirlo con una tabla de decisiones.
El diccionario de datos es el núcleo del análisis estructurado.
Características de las especificaciones de requisitos de software:
(1) Corrección;
(2) Sin ambigüedad;
(3) Integridad;
⑷Verificabilidad;
⑤Consistencia;
(6) Comprensibilidad;
(7) Trazabilidad.
3.3 Método de diseño estructurado
El objetivo básico del diseño de software es determinar cómo el sistema objetivo completa las tareas predeterminadas de una manera más abstracta y general. modelo del sistema.
El diseño de software es el paso más importante en la fase de desarrollo y la única forma de convertir con precisión los requisitos en un producto o sistema de software completo.
Desde una perspectiva técnica, el diseño de software incluye el diseño de la estructura del software, el diseño de datos, el diseño de interfaces y el diseño de procesos.
Diseño estructural: Define la relación entre los principales componentes del sistema software.
Diseño de datos: Convertir el modelo creado durante el proceso de análisis en la definición de estructuras de datos.
Diseño de interfaz: describe cómo el software se comunica internamente, entre el software y los sistemas colaboradores, y entre el software y las personas.
Diseño de proceso: Descripción del proceso que convierte los componentes estructurales del sistema en software.
Desde la perspectiva de la gestión de proyectos: diseño general y diseño de detalle.
El proceso general de diseño de software: el diseño de software es un proceso iterativo; primero, el diseño estructural de alto nivel; luego, el diseño de procesos de bajo nivel se intercala con el diseño de datos y el diseño de la interfaz.
Para medir la independencia de los módulos de software se utilizan dos medidas cualitativas: acoplamiento y cohesión.
Cuanto más fuerte sea la cohesión de cada módulo en la estructura del programa, más débil será el acoplamiento. Un buen software debe tener alta cohesión y bajo acoplamiento.
Las tareas básicas del diseño del esquema de software son:
(1) Diseñar la estructura del sistema de software (2) Estructura de datos y diseño de la base de datos;
③Escribir un breves documentos de diseño; (4) Revisar los documentos de diseño del esquema.
Los módulos están representados por rectángulos y las flechas representan las relaciones de llamada entre módulos.
En los diagramas de estructura, también puede utilizar flechas anotadas para representar la información que se transmite de un lado a otro durante las llamadas al módulo. También puede utilizar una flecha circular sólida para indicar que se ha transferido la información de control y una flecha circular abierta en el centro para indicar que se han transferido los datos.
Las formas básicas de los diagramas de estructura: forma básica, forma secuencial, forma repetitiva y forma de selección.
Hay cuatro tipos de módulos en el diagrama de estructura: módulo de entrada, módulo de salida, módulo de conversión y módulo de coordinación.
Existen dos tipos de flujo de datos típicos: tipo de transformación y tipo de transacción.
El diagrama de estructura del sistema de transformación consta de tres partes: entrada, transformación central y salida.
Las características del flujo de datos transaccionales son: aceptar una transacción, seleccionar y programar las unidades de procesamiento apropiadas de acuerdo con las características y la naturaleza del procesamiento de la transacción, y luego dar los resultados.
Diseño detallado: consiste en determinar el algoritmo de implementación y la estructura de datos local para cada módulo en el diagrama de estructura del software, y utilizar algunas herramientas de expresión seleccionadas para expresar los detalles del algoritmo y la estructura de datos.
Las herramientas de diseño de procesos más utilizadas incluyen: herramientas gráficas (diagramas de flujo de programas), herramientas de tablas (tablas de juicio) y herramientas de lenguaje (PDL).
3.4 Pruebas de software
La definición de pruebas de software: el proceso de ejecutar o probar el sistema de forma manual o automática, cuyo propósito es verificar si el sistema cumple con los requisitos especificados o para averiguar si los resultados esperados son consistentes con las diferencias entre los resultados reales.
El propósito de las pruebas de software: el proceso de descubrir errores y ejecutar programas.
Métodos de prueba de software: pruebas estáticas y pruebas dinámicas.
Las pruebas estáticas incluyen inspección de código, análisis de estructura estática y medición de la calidad del código. No hay ejecución real del software, principalmente trabajo manual.
Pruebas dinámicas: es una prueba de conceptos básicos de informática, que incluye principalmente pruebas de caja blanca y pruebas de caja negra.
Pruebas de caja blanca: realizadas dentro del programa, utilizadas principalmente para verificar el funcionamiento interno del software. Los métodos principales son la cobertura lógica y las pruebas de ruta base básica.
Prueba de caja negra: diagnostica principalmente funciones incorrectas u omitidas, errores de interfaz, estructura de datos o errores de acceso a bases de datos externas, errores de rendimiento, errores de condiciones de inicialización y terminación, y se utiliza para la verificación del software. Los métodos principales incluyen división de clases de equivalencia, análisis de valores límite, especulación de errores, diagramas de causa y efecto, etc.
El proceso de prueba de software generalmente se divide en cuatro pasos: prueba unitaria, prueba de integración, prueba de aceptación (prueba de confirmación) y prueba del sistema.
3.5 Depuración del programa
La tarea de la depuración del programa es diagnosticar y corregir errores en el programa, principalmente durante la fase de desarrollo.
Pasos básicos para la depuración del programa:
(1) Localice el error
② Modifique el diseño y el código para eliminar el error
<; p>( 3) Realizar pruebas de regresión para evitar la introducción de nuevos errores.La depuración de software se puede dividir en depuración estática y depuración dinámica. La depuración estática se refiere principalmente al análisis del código fuente y la depuración a través del pensamiento humano, que es el método de diseño principal, mientras que la depuración dinámica es una depuración estática auxiliar. Los principales métodos de depuración son:
(1) Método de depuración forzada;
(2) Método de retroceso
(3) Método de eliminación de causas.
-
4.1 Conceptos básicos de los sistemas de bases de datos
Datos: En realidad es un registro simbólico que describe cosas.
Características de los datos: Tienen una determinada estructura, tipos y valores, como números enteros, reales y caracteres. Al valor de los datos se le asigna un valor que se ajusta al prototipo, por ejemplo el valor entero 15.
Base de datos: Es una colección de datos con una estructura unificada y almacenados en un medio de almacenamiento unificado. Es una integración de varios datos de aplicaciones y puede ser utilizado por todas las aplicaciones.
Los datos almacenados en la base de datos se almacenan de acuerdo con el esquema de datos proporcionado por los datos y tienen las características de integración y uso compartido.
Sistema de gestión de bases de datos: software del sistema responsable de la organización de los datos, las operaciones de los datos, el mantenimiento, el control y la protección de los datos y los servicios de los datos en la base de datos.
Funciones del sistema de gestión de bases de datos:
(1) Definición del esquema de datos: es decir, el marco de datos para construir la base de datos
(2) Construcción física de la base de datos; acceso a datos: el acceso físico y la construcción de esquemas de datos proporcionan métodos y medios de acceso efectivos;
(3) Operaciones de datos: brindan comodidad a los usuarios para usar datos en la base de datos, como consulta, inserción, modificación y eliminación. y operaciones aritméticas simples y estadísticas;
Definición e inspección de la integridad y seguridad de los datos;
(5) Control de concurrencia de bases de datos y recuperación de fallas;
(6) Servicios de Datos: tales como replicación, transferencia, reorganización, seguimiento y análisis del desempeño.
Para completar las seis funciones anteriores, el sistema de gestión de bases de datos proporciona los siguientes lenguajes de datos:
(1) Lenguaje de definición de datos: responsable de la definición del esquema de datos y la construcción del acceso físico a los datos. ;
(2) Lenguaje de operación de datos: responsable de las operaciones de datos, como consultar, agregar, eliminar y modificar;
(3) Lenguaje de control de datos: responsable de la definición e inspección de integridad y seguridad de datos, control de concurrencia, recuperación de fallos, etc.
Los lenguajes de datos se presentan en dos formas estructurales dependiendo de su uso: comandos interactivos (también llamados lenguajes independientes o autónomos) lenguajes anfitriones (generalmente integrados en algún lenguaje anfitrión).
Administrador de Bases de Datos: Administrador profesional responsable de planificar, diseñar, mantener y monitorear bases de datos.
Sistema de base de datos: entidad operativa compuesta por cinco partes: base de datos (datos), sistema de gestión de bases de datos (software), administrador de bases de datos (personal), plataforma hardware (hardware) y plataforma software (software).
Sistema de aplicación de base de datos: consta de un sistema de base de datos, un software de aplicación y una interfaz de aplicación.
Etapa del sistema de archivos: proporciona funciones simples de administración e intercambio de datos, pero no puede proporcionar funciones completas y unificadas de administración e intercambio de datos.
Las etapas del sistema de base de datos jerárquica y de base de datos en red: brindan un fuerte soporte para la unificación y el intercambio de datos.
Etapa del sistema de base de datos relacional
Las características básicas del sistema de base de datos son: integración de datos, alto disfrute de datos y baja redundancia, independencia de datos (independencia física e independencia lógica) y datos unificados. gestión y control.
Modelo de sistema de base de datos de tres niveles:
(1) Modelo conceptual: descripción de la estructura lógica de datos globales en el sistema de base de datos, vista de datos públicos para todos los usuarios;
(2) Modo externo: también llamado submodo y modo usuario. Es la vista de datos del usuario, es decir, el modelo de datos visto por el usuario;
(3) Modelo interno: también llamado modelo físico, proporciona la estructura de almacenamiento físico y el método de acceso físico a la base de datos. .
Mapeo de dos niveles del sistema de base de datos;
(1) Mapeo del esquema conceptual al esquema interno
(2) Mapeo del esquema externo al esquema conceptual; cartografía.
4.2 Modelo de datos
El concepto de modelo de datos es la abstracción de las características de los datos. Describe las características estáticas, el comportamiento dinámico y las restricciones del sistema desde un nivel abstracto y proporciona información. Las tablas y restricciones para el sistema de base de datos proporcionan un marco abstracto. Se describen las estructuras de datos, las operaciones de datos y las restricciones de datos.
Conceptos básicos del modelo E-R
(1) Entidad: cosas del mundo real;
(2) Atributos: características de las cosas;
(3) Conexión: la relación entre cosas en el mundo real. Las relaciones de conjuntos de entidades incluyen relaciones uno a uno, uno a muchos y muchos a muchos.
La conexión entre los tres conceptos básicos del modelo E-R: la entidad es la unidad básica en el mundo conceptual, los atributos tienen dominios de atributos y cada entidad puede tomar valores en el dominio de atributos. Todos los valores de atributos de una entidad se denominan tuplas.
Representación gráfica del modelo E-R: (1) Representación del conjunto de entidades; (2) Método de tabla de atributos; (3) Representación de contactos.
La estructura básica del modelo jerárquico es una estructura de árbol, que tiene las siguientes características:
(1) Cada árbol tiene uno y sólo un nodo sin padres, llamado raíz <; /p >
(2) Todos los nodos del árbol, excepto la raíz, tienen un solo nodo principal.
Desde la perspectiva de la teoría de grafos, el modelo de cuadrícula es un gráfico no dirigido sin condiciones.
El modelo relacional está representado por una tabla bidimensional, denominada tabla, que consta de un marco de tabla y una tupla de tabla. Una tabla bidimensional es una relación.
El atributo más pequeño que puede identificar de forma única una tupla en una tabla bidimensional se llama clave o código. Seleccione una clave de todos los candidatos para que sea la clave principal del usuario. Si un atributo de la tabla A es una clave para la tabla B, el conjunto de atributos se denomina clave externa o código de clave externa para A.
Restricciones de datos en las relaciones:
( 1 ) Restricción de integridad de la entidad: el valor del atributo en la clave principal de la relación de restricción no puede estar vacío;
(2) Restricción de integridad de referencia: es la restricción básica entre relaciones;
(3) Restricciones de integridad personalizadas: refleja los requisitos semánticos de los datos en una aplicación específica.
4.3 Álgebra Relacional
Una de las características del sistema de base de datos relacional es que se basa en la teoría de datos. Existen muchas teorías de datos que pueden representar las operaciones de datos del modelo relacional. , el más famoso de los cuales es el álgebra relacional y el cálculo relacional.
Operaciones básicas del modelo relacional:
(1) Inserción (2) Eliminación (3) Modificación (4) Consulta (incluidas operaciones de proyección, selección y producto cartesiano)
4.4 Diseño y gestión de bases de datos
El diseño de bases de datos es el núcleo de la aplicación de datos.
Dos métodos de diseño de bases de datos:
(1) Orientado a datos: dar prioridad a las necesidades de información y tener en cuenta las necesidades de procesamiento;
(2) Proceso Orientado: dar prioridad a las necesidades de Procesamiento, teniendo en cuenta las necesidades de información.
El ciclo de vida de la base de datos: fase de análisis de requisitos, fase de diseño conceptual, fase de diseño lógico, fase de diseño físico, fase de codificación, fase de prueba, fase de operación y fase de modificación posterior.
Los métodos comúnmente utilizados para el análisis de requisitos incluyen el análisis estructural y los métodos orientados a objetos. Los métodos de análisis estructural (SA) analizan sistemas mediante descomposición de arriba hacia abajo y capa por capa. Utilice diagramas de flujo de datos para expresar la relación entre datos y procesamiento. Para el diseño de bases de datos, el diccionario de datos es el resultado principal de la recopilación y el análisis de datos detallados.
El diccionario de datos es una colección de varias descripciones de datos, que incluyen cinco partes: elementos de datos, estructuras de datos, flujos de datos (elementos de datos o estructuras de datos), almacenamiento y procesamiento de datos.
El propósito del diseño conceptual de una base de datos es analizar las relaciones semánticas inherentes a los datos. Hay dos formas de diseñar.
(1) Método de diseño de patrones centralizado (aplicable a unidades o departamentos pequeños o poco complejos);
(2) Método de diseño de integración de vistas.
Método de diseño: modelo E-R e integración de vistas.
El diseño de vista suele tener tres órdenes de diseño: de arriba hacia abajo, de abajo hacia arriba y de adentro hacia afuera.
Varios tipos de conflictos en la integración de vistas: conflictos de nombres, conflictos de conceptos, conflictos de dominio y conflictos de restricciones.
Diseño de vista relacional: El diseño de vista relacional también se denomina diseño de esquema externo.
Las funciones principales de la vista relacional:
(1) Proporcionar independencia lógica de los datos;
(2) Capaz de satisfacer las diferentes necesidades de datos de los usuarios;
p>
(3) Tiene ciertas funciones de seguridad de datos.
El objetivo principal del diseño físico de la base de datos es ajustar la estructura física interna de los datos y seleccionar una ruta de acceso razonable, aumentando así la velocidad de acceso a la base de datos y utilizando eficazmente el espacio de almacenamiento. En términos generales, el contenido que se deja a los usuarios para participar en el diseño físico en RDBMS es el diseño de índices, el diseño de clústeres integrados y el diseño de particiones.
Contenido de la gestión de la base de datos:
(1) Establecimiento de la base de datos
②Ajuste de la base de datos;
③Reorganización de la base de datos
p>
④Control de integridad y seguridad de la base de datos;
(5) Recuperación de fallas de la base de datos;
6.