La definición y el uso de tablas generalizadas

Las listas generalizadas (Lists, también conocidas como listas) son una generalización de las listas lineales. Una tabla lineal se define como una secuencia finita de n>=0 elementos a1, a2, a3,...,an. Los elementos de las tablas lineales se limitan a elementos atómicos. Los átomos son componentes estructuralmente indivisibles. Pueden ser un número o una estructura. Si se relaja esta restricción sobre los elementos de la tabla y se les permite tener su propia estructura, se producirá una forma generalizada. Concepto de mesa.

Una lista generalizada es una secuencia finita de n (n>=0) elementos a1, a2, a3,...,an, donde ai es un elemento atómico o una lista generalizada. Generalmente se escribe como LS=(a1,a2,a3,…,an). LS es el nombre de la tabla generalizada, n es su longitud. Si ai es una tabla generalizada, se denomina subtabla de LS.

La definición de tabla generalizada de tipo de datos abstractos es la siguiente:

ADT Glist

{

Objeto de datos: D={ei | i= 1,2,..,n;n>=0 ;ei?AtomSet o ei?Glist,

AtomSet es un objeto de datos}

Relación de datos: R1= {< ei-1, ei > | ei-1 , ei?D,2<=i<=n}

Operaciones básicas:

InitGList( &L);

Resultado de la operación: Crear una tabla generalizada L vacía.

CreateGList(&L,S);

Condición inicial: S es la cadena escrita de la lista generalizada.

Resultado de la operación: Crear tabla generalizada L a partir de S.

DestroyGList(&L);

Condición inicial: existe la lista generalizada L.

Resultado de la operación: Destruir la tabla generalizada L.

CopyGList( &T,L);

Condición inicial: existe la lista generalizada L.

Resultado de la operación: La tabla generalizada T se obtiene copiando la tabla generalizada L.

GListLength(L);

Condición inicial: existe la lista generalizada L.

Resultado de la operación: Encuentre la longitud de la lista generalizada L, es decir, el número de elementos.

GListDepth(L);

Condición inicial: existe la lista generalizada L.

Resultado de la operación: Encuentra la profundidad de la tabla generalizada L.

GListEmpty (L);

Condición inicial: Existe la lista generalizada L.

Resultado de la operación: Determinar si la tabla generalizada L está vacía.

GetHead(L);

Condición inicial: existe la tabla L generalizada.

Resultado de la operación: Tomar la cabecera de la tabla generalizada L.

GetTail( &T,L);

Condición inicial: existe la tabla L generalizada.

Resultado de la operación: Tomar la cola de la tabla generalizada L.

InsertFirst_GL(&L,e);

Condición inicial: existe la tabla L generalizada.

Resultado de la operación: Insertar el elemento e como primer elemento de la lista generalizada L.

DeleteFirst_GL(&L,&e);

Condición inicial: existe la tabla L generalizada.

Resultado de la operación: Elimina el primer elemento de la tabla generalizada L y devuelve su valor usando e.

Traverse_GL (L,visit());

Condición inicial: existe la tabla generalizada L.

Resultado de la operación: recorre la tabla generalizada L y utiliza la función visita para procesar cada elemento.

｝

Las tablas generalizadas suelen estar entre paréntesis y se utilizan comas para separar los elementos. Para distinguir entre átomos y tablas generalizadas, se utilizan letras mayúsculas al escribir tablas generalizadas y letras minúsculas para los átomos. Si la lista generalizada LS (n>=1) no está vacía, entonces a1 es la cabeza de LS, y la lista (a2,...an) compuesta por los elementos restantes se llama cola de LS.

Obviamente las tablas generalizadas se definen de forma recursiva, porque el concepto de tablas generalizadas se utiliza al definir tablas generalizadas. Ejemplos de listas generalizadas son los siguientes:

(1) A=() - A es una lista vacía con una longitud de cero.

(2) B= (e) - La tabla B tiene solo un átomo e, y la longitud de B es 1.

(3) C=(a,(b,c,d))——La longitud de la tabla C es 2 y los dos elementos son respectivamente

átomo a y subtabla (b,c,d).

(4) D= (A, B, C): la longitud de la tabla D es 3 y los tres elementos

son todos tablas generalizadas. Obviamente, después de sustituir los valores de la subtabla,

entonces queda D=(( ),(e),(a,(b,c,d))).

(5) E=(E)——Esta es una tabla recursiva, su longitud es 2, E es equivalente a una tabla generalizada infinita E=(a,(a,(a,( a, …)))).

Se pueden derivar tres conclusiones importantes sobre las tablas generalizadas de las definiciones y ejemplos anteriores:

(1) Los elementos de las tablas generalizadas pueden ser sublistas y elementos de una subtabla también pueden ser subtablas. Por tanto, la tabla generalizada es una estructura de varios niveles que se puede representar gráficamente. P108

(2) Las tablas generalizadas pueden ser compartidas por otras tablas. Por ejemplo, en el ejemplo anterior (4), las tablas generalizadas A, B y C son subtablas de D, por lo que no es necesario enumerar los valores de las subtablas en D, sino hacer referencia a ellas mediante los nombres de las subtablas.

(3) Recursividad de tablas generalizadas.

En resumen, las tablas generalizadas no son solo una generalización de tablas lineales, sino también una generalización de árboles.

A partir de las definiciones de encabezado y pie de página de tabla, podemos saber que el encabezado de cualquier tabla generalizada no vacía puede ser un átomo o una lista, y su pie de página debe ser una lista.

gethead(B)=egettail(B)=()

gethead(D)=Agettail(D)=(B,C)

Desde ( B, C) es una tabla generalizada no vacía, luego se puede descomponer aún más para obtener:

gethead(B,C)=Bgettail(B,C)=(C)

Tenga en cuenta que la tabla generalizada ( ) y ( ( ) ) son diferentes. La primera es una lista vacía con una longitud de 0,

no puede realizar operaciones al principio y al final de la tabla, mientras que la segunda es una lista no vacía con una longitud de 1 (es solo la lista; El único elemento de la lista es una tabla vacía). Se puede descomponer para obtener una tabla vacía () con el principio y el final de la tabla.

Estructura de almacenamiento de la tabla generalizada

Dado que los elementos de datos en la tabla generalizada (a1, a2, a3,...an) pueden tener diferentes estructuras, (ya sea tabla atómica o generalizada ), por lo tanto, es difícil expresarlo con una estructura de almacenamiento secuencial. Generalmente se usa una estructura de almacenamiento en cadena y cada elemento de datos puede representarse mediante un nodo.

Dado que hay dos tipos de elementos de datos en una tabla generalizada, átomos o tablas generalizadas, se necesitan dos estructuras de nodos: una es un nodo de tabla para representar una lista, la otra es un nodo atómico, usado; para representar átomos.

Si la lista no está vacía, se puede descomponer en un encabezado y un pie de página; de lo contrario, un par de encabezados y pies de página determinados pueden determinar de forma única la lista. Por lo tanto, un nodo de tabla puede estar compuesto por tres campos: el campo de bandera, el campo de puntero que indica el encabezado de la tabla y el campo de puntero que indica la cola de la tabla, mientras que el nodo atómico solo necesita dos campos: el campo de bandera y; el campo de valor.

1. Solo el nodo de la tabla consta de tres campos:

El campo de bandera, el campo de puntero que indica el encabezado de la tabla y el campo de puntero que indica la cola de la tabla; y el campo atómico solo necesita dos campos individuales: campo de bandera y campo de valor.

Representación de almacenamiento de lista enlazada principal y final

[cpp] ver copia simple

typedefenum{ATOM,LIST?}?ElemTag;//ATOM==0 : representación Atom, LIST==1: representa una subtabla

typedefstructGLNode?{

ElemTag?tag;// La parte pública *** se usa para distinguir la parte atómica y el nodo de la tabla

union{//La parte de unión de la parte atómica y el nodo de la tabla

AtomType?atom;//atom es el rango de valores del nodo atómico , AtomType lo define el usuario

struct{structGLNode?*hp,?*tp;}?ptr;

//ptr es el campo de puntero del nodo de la tabla, ptr .hp? y ptr.tp apuntan al principio y al final de la tabla respectivamente

};

}?*Glist;//Tipo de tabla generalizada

En la figura se muestra un ejemplo:

Tres tipos de esta estructura de almacenamiento Características:

1. Excepto por el puntero principal de una lista vacía, para cualquier lista que no esté vacía, el puntero principal apunta a un nodo de la tabla, y el campo hp en el nodo indica el encabezado de la lista, y el campo tp apunta a la cola de la lista. lista (a menos que la tabla Si la cola está vacía, el puntero está vacío; de lo contrario, debe ser un nodo de tabla);

2. Es fácil distinguir los niveles de átomos y sublistas en la lista. Por ejemplo, en la lista D, los átomos e y a están en el mismo nivel, mientras que b, c y d están en el mismo nivel y un nivel por debajo de e y a son sublistas del mismo nivel; p>

3. El número de nodos de la tabla en el nivel superior es la longitud de la lista.

2. Tanto los nodos de tabla como los nodos atómicos se componen de tres campos: campo de bandera, campo de puntero que indica el encabezado de la tabla y campo de puntero que indica la cola de los tres campos del nodo atómico; son: campos de bandera, campos de valor y campos de puntero que indican el final de la tabla.

Su tipo se define de la siguiente manera:

Representación de almacenamiento de lista enlazada lineal extendida

[cpp] ver copia simple

Typedefenum{ATOM ,LIST} ?ElemTag;

//ATOM==0: representa átomos, LIST==1: representa sublistas

TypedefstructGLNode?{

ElemTagtag;/ / Parte pública ***, utilizada para distinguir la parte atómica y el nodo de la tabla

union{// La parte de unión de la parte atómica y el nodo de la tabla

AtomTypeatom;// El valor del dominio del nodo atómico

structGLNode?*hp;//Puntero de encabezado del nodo de la tabla

};

structGLNode*tp;

//Equivalente al siguiente de una lista enlazada lineal, que apunta al siguiente nodo del elemento

}?*Glist;//El tipo de lista generalizada Glist es una lista enlazada lineal extendida

En la figura se muestra un ejemplo: