Sistema de conocimiento del examen de ingreso de posgrado de estructura de datos 2022: tabla lineal: definición y operaciones básicas de tabla lineal

1. Definición

Una tabla lineal es una secuencia finita de n (n? 0) elementos de datos. Donde n es la longitud de la tabla. Cuando n = 0, la tabla lineal es una tabla vacía. Si l se usa para nombrar una tabla lineal, generalmente se expresa como

L=(a1, a2? ai? An)

tipo, a1 es el único primer elemento de datos, y Llamado elemento de encabezado; es el último elemento de datos, también llamado elemento de pie de página.

2. Características lógicas

A excepción del primer elemento, cada elemento tiene y tiene un solo antecesor directo. Cada elemento excepto el último elemento tiene exactamente un sucesor directo.

3. Características de las tablas lineales

(1) El número de elementos de la tabla es limitado

(2) Los elementos de la tabla son lógicas; Secuencial, el orden de cada elemento en la secuencia tiene su propio orden;

(3) Todos los elementos de la tabla son elementos de datos y cada elemento es un elemento único (elemento de datos único);

(3) Todos los elementos de la tabla son elementos de datos y cada elemento es un elemento único (elemento de datos único);

(3) p>

(4) Los tipos de datos de los elementos de la tabla son todos iguales, es decir, cada elemento ocupa el mismo espacio de almacenamiento

(5) Los elementos de la tabla son abstractos y solo se analizan las relaciones lógicas entre los elementos; relación, independientemente de lo que representen los elementos.

Nota: Una lista lineal es una estructura lógica que representa una relación adyacente uno a uno entre elementos. Las listas de secuencias y las listas enlazadas son estructuras de almacenamiento, ¡no son el mismo concepto! ! ! ! !

2. Operaciones básicas de tablas lineales

Las operaciones más básicas: añadir, eliminar y cambiar consultas.

InitList(& amp;l): Inicializa la tabla. Construya una tabla lineal vacía;

Longitud (L): encuentre la longitud de la tabla. Devuelve la longitud de la tabla lineal L, es decir, el número de elementos de datos en L;

Locatelem (l, e): operación de búsqueda por valor. Encuentra elementos con un valor de palabra clave determinado en la tabla L;

GetElem(L, I): operación de búsqueda bit a bit. Inserte el elemento especificado e en la posición I-ésima de la tabla L;

list insert(&l,I,e): operación de inserción. Inserte el elemento e especificado en la posición I-ésima de la tabla L;

lista eliminar(&l,I,e): operación de eliminación. Elimine el elemento en la posición I en la tabla L y use e para devolver el valor del elemento eliminado;

PrintList(L): operación de salida. Genere todos los valores de los elementos de la tabla lineal L en secuencia;

Vacío (L): sin operación. Si l es una tabla vacía, devuelve verdadero; de lo contrario, devuelve falso

Lista de destrucción (& ampl): operación de destrucción. Destruya la tabla lineal y libere el espacio de memoria ocupado por la tabla lineal l.

Nota: La implementación de operaciones básicas depende de qué estructura de almacenamiento se utilice. ¿en? y amplificador? Representa una referencia en C++.