Varias operaciones básicas de la tabla lineal de estructura de datos no se pueden implementar. Deje que los expertos ayuden a resolver el problema.

1 Método de aprendizaje

Como tengo que prepararme para este tema, he pensado seriamente en mi método de aprendizaje, pero creo que básicamente leo el libro antes de clase y escucho atentamente durante clase, repasar después de clase y, por supuesto, hacer los deberes muy en serio. No existe ningún buen método, pero todavía tengo algunas palabras que darte.

¡Puedo hacerlo!

Personalmente, creo que esta frase es muy importante. No sé qué piensan todos del curso de estructura de datos. ¿Cuántas personas piensan que la estructura de datos es difícil? A veces hablé con mi amigo sobre cómo aprender. Después de hablar mucho, se quejó: no aprendí bien C ++ antes y no pude aprender bien las estructuras de datos. ¿Qué tiene que ver con C ++? Creo que si tienes esa mentalidad y no crees en ti mismo, es imposible aprender bien. Y aquellos estudiantes que encuentran difíciles las estructuras de datos, creo que deberían darle gran importancia a las estructuras de datos. Y luego solo un día, ¿no sería agotador tener un libro de estructuras de datos en la mano toda la noche? Y debido a que le resulta difícil, no creerá en usted mismo y su eficiencia de aprendizaje no será muy buena. Personalmente, creo que las estructuras de datos son fáciles de aprender y son fáciles de aprender. Quizás esto me esté subestimando un poco, pero como creo que es fácil, naturalmente siento que no tengo ningún problema y que puedo aprenderlo fácilmente. y los resultados son aceptables. Todos han aprobado el examen de ingreso a la universidad, por lo que deben conocer la importancia de la mentalidad. Dos mentalidades diferentes tienen efectos completamente diferentes. Después de aprender estructuras de datos durante tanto tiempo, ¿qué estamos aprendiendo exactamente? No sé si lo ha pensado. Ahora resumamos lo que hemos aprendido hasta ahora. como árboles binarios, árboles, gráficos y problemas de clasificación. Las tablas lineales y cadenas anteriores son solo algunos conceptos. Por supuesto, también hay un algoritmo KMP muy importante. Luego, en cada estructura de datos, hemos aprendido varios algoritmos. Creo que el número real es sólo docenas de algoritmos. Aprender estructuras de datos significa dominar estas docenas de algoritmos, qué simple es. En cuanto a cómo dominar cada algoritmo, creo que solo necesitas leer más libros. Lo importante es poder comprenderlo.

¡Puedo hacer mis deberes solo!

Mi definición aquí es diferente de la del profesor. El profesor anima a todos a discutir, pero descubrí que algunos estudiantes todavía preguntan sobre los algoritmos de otras personas primero y luego escriben los suyos propios. pero básicamente no existe un proceso para pensar en el problema. Aunque es necesario pensar mucho para comprender el algoritmo, debido a que no tiene su propio proceso de pensamiento independiente, no puede escribir programas o algoritmos usted mismo, por lo que. Creo que si realmente quieres aprenderlo bien, cuando se trata de estructuras de datos, es mejor poder pensar en el problema tú mismo, no pensar en ello por un tiempo y luego sentir que no puedes hacerlo. y luego preguntar a otras personas. De hecho, la tarea que nos da el profesor se basa en nuestro nivel. Creo absolutamente que podemos descubrir el algoritmo por nuestra cuenta. Aunque puede llevar mucho tiempo, definitivamente aprenderemos más que preguntándole a otras personas. Por supuesto, no estoy diciendo que no debas preguntarles a tus compañeros de clase. A veces simplemente no puedes entenderlo y lo entenderás tan pronto como les preguntes a los demás. Por supuesto, preguntar a los demás no debería significar solo eso. Conozco el algoritmo. También deberías pensar en cómo pensar para obtener el algoritmo. De esta manera, tu nivel mejorará mucho.

¡Experimenta más!

No hay muchas razones para esto. Siempre he sentido que la programación es una ciencia especializada. Cuanto más programes, el nivel definitivamente mejorará. Lo más importante es desarrollar un sentimiento por el programa. el algoritmo Sensible, ¿por qué esas personas talentosas entienden un algoritmo de una vez pero a mí me lleva mucho tiempo entenderlo, y después de entenderlo, me olvido de leerlo después de un tiempo? Las personas con talento han visto muchos programas antes y los han programado. También hay muchos, por lo que tienen ese sentimiento, así que creo que todos deberían leer más programas, escribir más programas y cultivar sus propios sentimientos.

2 Habilidades de revisión y examen

Creo que todos deberían tener este sentimiento, es decir, sienten que han dominado todo, pero se sentirán mareados durante el examen. Cuando salí de la sala de examen, supe dónde cometí el error. Luego, después de mirar las respuestas, descubrí que el examen era en realidad muy simple. Esto está relacionado con mi revisión. y habilidades de examen.

La primera es la revisión. Como se mencionó anteriormente, en realidad hay docenas de algoritmos que aprendemos, por lo que nuestra tarea es comprender estas docenas de algoritmos, y la revisión es profundizar su comprensión. ¿Cómo entender el algoritmo y luego hasta qué punto se puede entender todo el algoritmo? Parece que ese no es el caso. Después de aprobar el examen de mitad de período, todos deberían haber descubierto que la estructura de datos sí. En realidad, no es necesario que comprenda el algoritmo. Memorice todo el algoritmo. Se centra en probar su comprensión. Entonces, ¿cómo comprobarlo? En realidad, hay dos formas: darle un ejemplo y pedirle que lo ejecute. un cierto algoritmo para obtener el resultado. Creo que todavía habrá muchas preguntas de este tipo durante el examen final. Por ejemplo, la clasificación es una muy buena pregunta. Creo que es muy sencillo revisar este tipo de preguntas. Practique cada algoritmo con ejemplos para poder adaptarme a él, Wan Chang, esto es lo que hice durante mi revisión de mitad de período. Y antes del examen, sentí que era muy probable que las preguntas que se combinaron y verificaron fueran probadas. así que se me ocurrieron algunos ejemplos y lo hice. Otra forma de examinar es el algoritmo para completar los espacios en blanco y la corrección de errores del algoritmo. A algunos estudiantes les puede resultar difícil este tipo de preguntas. De hecho, primero podemos determinar que estas dos preguntas definitivamente están relacionadas con los algoritmos del libro. comprender los algoritmos del libro Eso es todo. Algunas personas piensan que entienden todo después de leer el libro y pueden resolverlo en silencio. De hecho, este no es el caso. La corrección de algoritmos y el llenado de espacios en blanco son principalmente los detalles de la inspección. Incluso si cree que puede resolverlo en silencio, ese no es el caso. Si puede comprender tácitamente la parte principal del algoritmo, fácilmente pasará por alto muchas sutilezas. Creo que todos deberían sentirse así después de aprobar el examen de mitad de período. Entonces, ¿cómo deberíamos resolver este problema? Creo que hay dos métodos: este método es más significativo y también puede mejorar el nivel de programación. Es utilizar ejemplos para analizar cada oración del algoritmo. Creo que este método es el más efectivo.

Luego hay otro tipo de pregunta, que es la última pregunta sobre escribir algoritmos. Creo que este tipo de pregunta es fácil de resolver, siempre que puedas hacer la tarea tú mismo, básicamente será fácil. Esta es también la razón por la que pensé que deberías pensar de forma independiente al hacer la tarea. Al mismo tiempo, debes tener cuidado al hacer este tipo de preguntas, especialmente cuando las preguntas son simples, definitivamente habrá algunas cosas pequeñas. Eso debe considerarse cuidadosamente. Si no tiene cuidado, se le descontarán muchos puntos.

No creo que haya mucho de qué hablar durante el examen. Siempre que revises bien y tengas más cuidado durante el examen, entonces debes intentar asegurarte de que sea correcto al principio. de una pregunta. Si crees que debes quedarte allí, lo comprobaré nuevamente después de haberlo terminado, por lo que aún es posible que los errores no se detecten. Básicamente, no revisé durante el examen de mitad de período. Me aseguré de que todas las preguntas fueran correctas, y me llevó mucho tiempo, y luego sentí que ya no era necesario comprobarlo.

La experiencia de un estudiante aprendiendo la estructura de datos (republicada)

Lea "Estructura de datos (edición en lenguaje C)" (1)

Empiece a leer este libro en serio hoy Edición Tsinghua de Estructuras de datos, editada por Yan Weimin y Wu Weimin. Tal vez se pregunte por qué elegí este libro sobre estructuras de datos descritas en lenguaje C. ¿No están todas las estructuras de datos actuales descritas en lenguajes orientados a objetos? De hecho, este libro no fue elegido por mí, sino que fue una referencia especificada por mí. la prueba de computadora que tomé Libro. Sin embargo, tengo mis propias opiniones sobre el lenguaje elegido para este libro. Obviamente, existen muchos inconvenientes al usar el lenguaje C para describir estructuras de datos, pero en un mundo lleno de estructuras de datos descritas en OO, puede ser más fácil ver la esencia de la estructura de datos con mayor claridad al retirarse de OO y usar C para Mire la estructura de datos.

Bien, pongámonos manos a la obra. En este primer artículo de hoy, discutiré los conceptos básicos de las estructuras de datos. El autor resume los pasos generales para la resolución de problemas informáticos al principio: primero, debemos abstraer un modelo matemático apropiado del problema específico, luego diseñar un algoritmo para resolver el modelo matemático y finalmente compilar el programa, probarlo y depurarlo hasta que se obtiene la solución final.

Permítanme resumirlo más: modelo matemático abstracto - algoritmo de diseño - programa de escritura. Esta idea es muy importante, salvo algunos problemas muy simples, toda programación debe seguir estos tres pasos básicos. Un error común que cometemos a menudo al escribir programas es ignorar el primer o segundo paso, o peor aún, ignorar los dos primeros.

En el proceso de diseño de modelos matemáticos, en realidad se introduce el concepto de estructura de datos. La definición dada por el autor en este libro es: En pocas palabras, la estructura de datos es una disciplina que estudia los objetos operativos de la computadora y las relaciones y operaciones entre ellos en problemas de programación no numérica. Para ser rigurosos en el lenguaje, los libros de texto locales a menudo hacen que las palabras sean difíciles de entender. Preste atención a estas palabras clave en esta oración: 1) Cálculos no numéricos, que ilustran el alcance de la aplicación de la disciplina de estructura de datos. Si desea resolver un sistema de ecuaciones lineales, puede resultar difícil encontrar directamente una estructura de datos adecuada. 2) Objeto de operación, que son los datos en la pregunta y su forma de representación; 3) Relación, que es la relación entre datos; 4) Operación, que es la operación sobre los datos;

Escribe la definición anterior como una fórmula, que es

Estructura_de_datos = (D, S)

donde D es un conjunto finito de elementos de datos y S es D Un conjunto finito de relaciones. Por lo tanto, al diseñar una estructura de datos, la primera tarea es descubrir los datos que se van a manipular y la segunda es descubrir la relación entre los datos. Una vez completados estos dos pasos, se determina la estructura lógica de los datos. Las estructuras entre datos incluyen las siguientes:

Conjunto, que es consistente con el concepto de conjunto en matemáticas

Estructura lineal, es decir, la relación uno a uno entre datos; elementos

Estructura de árbol, es decir, una relación de uno a muchos entre elementos de datos

Estructura gráfica o estructura de red, es decir, una relación de muchos a muchos; elementos de datos.

Sin embargo, solo la estructura lógica no es suficiente para que el programa pueda ejecutarse, se debe expresar la estructura lógica de los datos en la computadora, es decir, se diseña la estructura física. La mayoría de los lenguajes de alto nivel tienen un buen soporte para la estructura física de los datos, como varios tipos de datos. Al explicar el concepto de tipos de datos, el autor dijo: El propósito de introducir tipos de datos, desde una perspectiva de hardware, es como un medio para interpretar el significado de la información en la memoria de la computadora, para que los usuarios que usan tipos de datos se den cuenta del significado de. La ocultación de información significa que todos los detalles que los usuarios no necesitan saber están encapsulados en tipos. Este resumen es muy revelador y se puede ver que la programación orientada a objetos en el futuro solo encapsulará y ocultará información a un nivel superior.

Para ampliar aún más los tipos de datos, el autor introduce el concepto de tipos de datos abstractos. Un tipo de datos abstracto (ADT) se refiere a un modelo matemático y un conjunto de operaciones definidas en el modelo. Después de la introducción de tipos de datos abstractos, la estructura lógica se vuelve más independiente, lo que permite a los programadores centrarse más en el diseño de la estructura lógica. El tipo de datos abstracto está representado por una fórmula, que es (D, S, P), donde D es el objeto de datos, S es el conjunto de relaciones en D y P es el conjunto de operaciones básicas en D. Si las computadoras deben seguir un patrón general al resolver problemas, la fórmula anterior da la respuesta.

Lea "Estructura de datos (edición en lenguaje C)" (2)

Esta sección habla sobre el análisis de algoritmos y el método de estimación de O grande (notación de O grande). La medición de la eficiencia del algoritmo generalmente adopta el método de análisis y estimación ex ante. El método habitual es seleccionar una operación original del algoritmo que sea una operación básica para el problema (o tipo de algoritmo) en estudio y ejecutarla repetidamente. tiempos de operación como medida del tiempo del algoritmo. Al hablar de esto, el autor introdujo el método de estimación Big O.

En este libro, la introducción del autor al método de estimación Big O parece un poco apresurada. Al principio apareció una fórmula T(n) = O(n3), y luego se introdujo la definición de la forma llamada "O" en letra pequeña al final de esta página: Si f(n) es una función de la entero positivo n , entonces xn=O(f(n)) significa que hay una constante positiva M, tal que cuando n≥n0, |xn|≤M|f(n)| se satisface. Quizás mi base matemática sea demasiado pobre, pero me confundí cuando vi esta definición. No sé por qué el autor no dedicó un poco de espacio a presentar el origen y la definición del método de estimación Big O.

Busqué en Google y encontré esta introducción:

Definición: una medida teórica de la ejecución de un algoritmo, generalmente el tiempo o la memoria necesaria, dado el tamaño del problema n, que suele ser el número de elementos. alguna ecuación f(n) = O(g(n)) significa que es menor que algún múltiplo constante de g(n). La notación se lee, "f de n es grande oh de g de n".

Definición formal: f(n) = O(g(n)) significa que hay constantes positivas cyk, tales que 0 ≤ f(n) ≤ cg(n) para todo n ≥ k. de cyk debe ser fijo para la función f y no debe depender de n

Nota: Como ejemplo, n2 + 3n + 4 es O(n2), ya que n2 + 3n + 4 < 2n2. para todo n > 10. Estrictamente hablando, 3n + 4 también es O(n2), pero la notación O grande a menudo se utiliza incorrectamente para significar igual a en lugar de menor que. La noción de "igual a" se expresa por Θ (n).

La importancia de esta medida se puede ver al intentar decidir si un algoritmo es adecuado, pero puede que simplemente necesite una mejor implementación, o el algoritmo siempre será demasiado lento con una entrada lo suficientemente grande. Por ejemplo, la clasificación rápida, que es O(n log n) en promedio, ejecutándose en una pequeña computadora de escritorio puede superar la clasificación de burbujas, que es O(n2), ejecutándose en una supercomputadora si hay muchos números para ordenar. números, la clasificación rápida toma 20.000.000 de pasos en promedio, mientras que la clasificación de burbujas toma 1.000.000.000.000 de pasos.

Cualquier medida de ejecución debe referirse implícita o explícitamente a algún modelo de cálculo. Generalmente se trata de alguna noción del factor limitante.

Para un problema o máquina, el número de multiplicaciones de punto flotante puede ser el factor limitante, mientras que para otro, puede ser el número de mensajes pasados ​​a través de una red. Otras medidas que pueden ser importantes son las comparaciones, los movimientos de elementos, los accesos al disco y la memoria. tiempo usado o transcurrido ("reloj de pared")

(La introducción anterior proviene de: Paul E. Black, "big-O notation", del Dictionary of Algorithms and Data Structures, Paul E. Black. , ed., NIST.)

Además, esta publicación también analiza la estimación de la complejidad temporal del algoritmo, que es muy fácil de entender.

Lea "Estructura de datos (edición en lenguaje C)" (3)

Descripción del problema

Diseñe un programa de demostración que pueda realizar operaciones con números complejos.

Requisitos básicos

Realizar las siguientes seis operaciones básicas:

Generar un número complejo a partir de la parte real y la parte imaginaria de entrada.

Dos Suma de dos números complejos;

Encuentra la diferencia de dos números complejos;

Encuentra el producto de dos números complejos

Separa la parte real de la; número complejo conocido;

p>

Separar la parte imaginaria de un número complejo conocido.

El resultado de la operación se muestra en la representación del número complejo o número real correspondiente.

(Ver adjunto para el texto completo)