Solución de emergencia a una pregunta sobre estructura de datos (lenguaje C)
El póster original es muy afortunado. También estoy aprendiendo la estructura de datos. Este es el código fuente proporcionado por el profesor. Espero que sea útil.
Estado MakeNode(Enlace *p. ,ElemType e)
{ /* Asigne el nodo cuyo valor es e señalado por p y devuelva OK si la asignación falla;
luego devuelve ERROR */
*p=(Link)malloc(sizeof(LNode));
if(!*p)
devuelve ERROR;
(*p)->data=e;
devolver OK;
}
anular FreeNode(Enlace *p)
{ /* Liberar el nodo señalado por p*/
free(*p);
*p=NULL;
}
Estado InitList(LinkList *L)
{ /* Construir una lista enlazada lineal vacía*/
Enlace p;
p = (Link)malloc(sizeof(LNode)); /* Generar nodo principal*/
if(p)
{
p->next= NULL;
(*L).head=(*L).tail=p;
(*L).len=0;
return OK ;
}
else
devuelve ERROR;
}
Estado ClearList(LinkList *L)
{ /* Restablece la lista enlazada lineal L a una lista vacía y libera el espacio de nodo de la lista enlazada original*/
Enlace p,q;
if( (*L).head!=(*L).tail)/* no es una tabla vacía*/
{
p=q=(*L). head->siguiente ;
(*L).head->siguiente=NULL;
while(p!=(*L).tail)
{
p=q->siguiente;
libre(q);
q=p;
}
gratis (q);
(*L).tail=(*L).head;
(*L).len=0;
}
return OK;
}
Estado DestroyList(LinkList *L)
{ /* Destruir lista lineal enlazada L , L ya no existe */
ClearList(L); /* Borrar la lista enlazada*/
FreeNode(&(*L).head);
(*L). tail=NULL;
(*L).len=0;
devuelve OK;
}
<. p> Status InsFirst(LinkList * L, Link h, Link s) /* Agregue L al parámetro formal porque L necesita ser modificado */{ /* h apunta a un nodo de L, trate h como nodo principal y cambie el punto señalado por s El nodo se inserta antes del primer nodo*/
s->next=h->next;
h- >next=s;
if(h==(*L).tail) /* h apunta al nodo de cola*/
(*L).tail=h- >siguiente; /* Modificar el puntero de cola *
/
(*L).len++;
return OK;
}
Estado DelFirst(LinkList *L,Link h, Enlace *q) /* Agregue L al parámetro formal porque L necesita ser modificado */
{ /* h apunta a un nodo de L, trata h como el nodo principal y elimina el primer nodo en la lista enlazada Haga clic y regrese con q.
*/
/* Si la lista vinculada está vacía (h apunta al nodo de cola), q=NULL, devuelve FALSE */
*q=h->next;
if(*q) /* La lista enlazada no está vacía*/
{
h->next=(*q)->next;
if(!h->next) /* Eliminar el nodo de cola*/
(*L).tail=h /* Modificar el puntero de cola*/
(*L) .len--;
devuelve OK;
}
else
devuelve FALSO /* Lista enlazada vacía*/
}
Estado Append(LinkList *L,Link s)
{ /* Apunte al puntero s (s->datos es el primer elemento de datos) (vinculados entre sí mediante punteros y terminando en NULL)*/
/* Una serie de nodos se vinculan después del último nodo de la lista lineal vinculada L y cambian la cola puntero de la lista enlazada L para apuntar a la nueva*/
/* El nodo de cola*/
int i=1;
(*L ).tail->siguiente=s;
while(s->siguiente)
{
s=s->siguiente;
i++;
}
(*L).tail=s;
(*L).len+=i;
return OK;
}
Posición PriorPos(LinkList L,Link p)
{ /* Se sabe que p apunta a un nodo en la línea lineal lista enlazada L, devuelve la posición del predecesor inmediato del nodo señalado por p*/
/* Si no hay predecesor, devuelve NULL */
Enlace q;
q=L.head->next;
if(q==p) /* Sin predecesor*/
return NULL;
else
{
while(q ->next!=p) /* q no es el predecesor directo de p*/
q=q ->siguiente;
return q;
}
}
Estado Eliminar(LinkList *L,Link *q)
{ /* Elimina el nodo de cola en la lista enlazada lineal L y lo devuelve como q, cambia El puntero de cola de la lista enlazada L apunta al nuevo nodo de cola*/
Enlace p= (*L).head;
if((*L).len==0) / *Tabla vacía*/
{
*q= NULL;
return FALSE;
}
while(p->next!=(*L).tail)
p =p->siguiente;
*q=(*L).tail;
p->siguiente=NULL;
(*L).tail =p;
(*L).len--;
return OK;
}
Estado en
sBefore(LinkList *L,Link *p,Link s)
{ /* Se sabe que p apunta a un nodo en la lista lineal enlazada L, inserte el nodo señalado por s antes del nodo señalado por p , */
/* y modifique el puntero p para que apunte al nodo recién insertado*/
Enlace q;
q=PriorPos(*L ,*p ); /* q es el predecesor de p*/
if(!q) /* p no tiene predecesor*/
q=(*L).head ;
s->siguiente=*p;
q->siguiente=s;
*p=s;
( *L).len++ ;
return OK;
}
Estado InsAfter(LinkList *L,Link *p,Link s)
{ /* Se sabe que p apunta a un nodo en la lista lineal enlazada L, inserte el nodo señalado por s después del nodo señalado por p, */
/* y modifique el puntero p para apuntar al nodo recién insertado* /
if(*p==(*L).tail) /* Modificar el puntero de cola*/
(*L).tail =s;
s->siguiente=(*p)->siguiente;
(*p)->siguiente=s;
*p= s;
(*L).len++;
return OK;
}
Estado SetCurElem(Enlace p,ElemType e)
{ / * Se sabe que p apunta a un nodo en la lista lineal enlazada, use e para actualizar el valor del elemento de datos en el nodo señalado por p */
p->data=e;
return OK;
}
ElemType GetCurElem(Enlace p)
{ /* It se sabe que p apunta a un nodo en la lista lineal enlazada, devuelve el nodo señalado por p El valor del elemento de datos en el clic*/
return p->data;
}
Status ListEmpty(LinkList L)
{ /* Si la lista lineal enlazada L es una lista vacía, devuelve VERDADERO; de lo contrario, devuelve FALSO */
if(L.len)
devuelve FALSO;
else
devuelve VERDADERO;
}
int ListLength(LinkList L)
{ /* Devuelve el número de elementos en la lista lineal enlazada L* /
return L.len;
}
Position GetHead(LinkList L)
{ /* Devuelve el encabezado de la lista lineal enlazada L La posición del nodo*/
return L.head;
}
Posición GetLast(LinkList L)
{ /* Retorno La posición del último nodo en la lista lineal enlazada L*/
return L.tail;
}
Posición NextPos(Enlace p)
{ /* Se sabe que p apunta a un nodo en el Lista lineal enlazada L, devuelve la posición del sucesor directo del nodo señalado por p */
/* Si no hay sucesor, devuelve NULL */
return p->next;
}
Estado LocatePos(LinkList L,int i,Link *p)
{ /* Devuelve p que indica lista enlazada lineal L La posición del i-ésimo nodo en y devuelve OK, devuelve ERROR cuando el valor de i es ilegal */
/* i=0 es el nodo principal*/
int j;
if(i<0||i>L.len)
devuelve ERROR;
else
{
*p=L.head;
for(j=1;j<=i;j++)
*p=(*p)-> siguiente;
return OK;
}
}
Posición LocateElem(LinkList L,ElemType e,Status (*compare)( ElemType,ElemType) )
{ /* Devuelve la posición del primer elemento en la lista lineal enlazada L que satisface la relación de juicio de la función compare() con e, */
/ * Si no existe tal elemento, entonces se devuelve NULL */
Link p=L.head;
do
p=p->next;
while (p&&!(compare(p->data,e))); /* No se llegó al final de la tabla y no se encontró ningún elemento que satisficiera la relación*/
return p;
}
Status ListTraverse(LinkList L,void(*visit)(ElemType))
{ /* Llame a la función visit() en cada elemento de datos de L por turno. Una vez que visit() falla, la operación falla*/
Link p=L.head->next;
int j;
for(j=1 ;j<=L.len;j++)
{
visitar(p->datos);
p=p->siguiente;
}
printf("\n");
return OK;
}
Estado OrderInsert(LinkList * L,ElemType e,int (*comp)(ElemType,ElemType))
{ /* Se sabe que L es una lista enlazada lineal ordenada, inserte el elemento e en L en orden no descendente.
(para polinomios de una variable) */
Link o,p,q;
q=(*L).head;
p=q- > next;
while(p!=NULL&&comp(p->data,e)<0) /* p no es el final de la tabla y el valor del elemento es menor que e */
{
q=p;
p=p->siguiente;
}
o=(Enlace) malloc(sizeof(LNode)); /* Generar nodo*/
o->data=e /* Asignar valor*/
q->next=o; Insert*/
o->next=p;
(*L).len++; /* Agrega 1 a la longitud de la tabla */
if( !p) /* Insertar al final de la tabla* /
(*L).tail=o; /* Modificar el nodo de cola*/
return OK;
}
Estado LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType))
{ /* Si hay un valor en la lista enlazada ascendente L que satisface la función de juicio compare() con e es un elemento de 0, entonces q indica la posición del primer nodo en L */
/* cuyo valor es e , y devuelve VERDADERO; de lo contrario, q indica el primer nodo que satisface la función de juicio con e*/
/* compare() toma la posición del predecesor del elemento cuyo valor es >0. y devuelve FALSO.
(para polinomios de una variable) */
Link p=L.head,pp;
do
{
pp= p ;
p=p->next;
} while(p&&(compare(p->data,e)<0)); /* El final de la tabla es no alcanzado y p- >data.expn if(!p||compare(p->data,e)>0) /* Ir al final de la tabla o comparar(p->datos,e) >0 */ { *q=pp; devolver FALSO; } else /* Encontrado*/ { *q=p; devuelve VERDADERO; } } typedef estructura LNode /* Tipo de nodo*/ { ElemType datos; struct LNode *siguiente; }LNode,*Enlace,*Posición; typedef struct LinkList /* Tipo de lista enlazada*/ { Enlace head,tail; /* Señala el nodo principal y el último nodo en la lista lineal enlazada respectivamente*/ int len /* Indica el número de elementos de datos en el enlace lineal; list*/ }LinkList ; typedef LinkList polinomio; #define DestroyPolyn DestroyList /* Sinónimo de la función en bo2-6.cpp pero con diferentes nombres*/ #define PolynLength ListLength /* Sinónimo de las funciones en bo2-6.cpp con nombres diferentes*/ Estado OrderInsertMerge(LinkList *L,ElemType e,int( * compare)(term,term)) { /* De acuerdo con la convención de la función de juicio ordenado compare(), inserte o fusione el nodo con valor e en la posición apropiada de la lista enlazada ascendente L */ Posición q,s; if(LocateElemP(*L,e,&q,compare)) /* Este elemento de índice existe en L*/ { q->data.coef+ =e.coef; /* Cambiar el valor del coeficiente del nodo actual*/ if(!q->data.coef) /* El coeficiente es 0 */ { /* Eliminar el nodo actual en el polinomio L*/ s=PriorPos(*L,q); del nodo actual*/ if(!s) / * qNo predecesor*/ s=(*L).head; DelFirst(L ,s,&q); FreeNode(&q); } devolver OK; } else /* Generar el índice El elemento se inserta en la lista enlazada*/ if(MakeNode(&s,e)) /* El nodo se genera correctamente*/ { InsFirst(L,q ,s); return OK; } else /* No se pudo generar el nodo*/ return ERROR; } int cmp(term a, term b) /* Parámetros reales de CreatPolyn()*/ { /* Según el valor del exponente de a<, = O > el valor del exponente de b, devuelve -1, 0 o +1 respectivamente */ if(a.expn==b.expn) devolver 0; else devolver (a.expn-b.expn)/abs(a.expn-b.expn); } void CreatPolyn (polinomio *P,int m) /* Algoritmo 2.22 */ { /* Ingrese los coeficientes y exponentes de m términos para establecer una lista enlazada ordenada P que represente uno -variable polinomio */ Posición q,s; término e; int i; InitList(P); printf("Ingrese en secuencia %d coeficientes, exponente:\n",m); for(i=1;i<=m;++i) { /* Ingrese m en secuencia Elementos distintos de cero (pueden estar en cualquier orden) */ scanf("%f,%d",&e.coef,&e.expn) ; if(!LocateElemP(* P,e,&q,cmp)) /* El elemento de índice no existe en la lista vinculada actual, cmp es el parámetro real*/ if(MakeNode(&s,e)) /* Genera el nodo e insértalo en la lista enlazada */ InsFirst(P,q,s); } } void PrintPolyn(polinomio P) { /* Imprime el polinomio de una variable P */ Enlace q; q=P.head->next; /* q apunta al primer nodo* / printf("Índice de coeficiente\n"); while (q) { printf("%f % d\n",q->data.coef,q->data.expn); q=q->siguiente; } } void AddPolyn(polinomio *Pa,polinomio *Pb) /* Algoritmo 2.23 */ { /* Suma polinómica: Pa=Pa+Pb, y destruye el polinomio de una variable Pb */ Posición ha,hb,qa,qb; term a,b; ha=GetHead(*Pa); hb=GetHead(*Pb); /* ha y hb apuntan a los nodos principales de Pa y Pb respectivamente. */ qa=NextPos(ha); qb= NextPos(hb); /* qa y qb apuntan a los nodos actuales en Pa y Pb respectivamente (ahora el primer nodo) */ while(!ListEmpty(*Pa)&&!ListEmpty(* Pb) &&qa) { /* Pa y Pb no están vacíos y ha no apunta al nodo de cola (qa!=0) */ a=GetCurElem(qa); b=GetCurElem(qb); /* a y b son los elementos de comparación actuales en las dos tablas*/ switch(cmp(a,b)) { case -1:ha=qa; /* El valor del exponente del nodo actual en el polinomio Pa es pequeño*/ qa=NextPos(ha); * Tanto ha como qa Mover un nodo hacia atrás*/ break; caso 0: qa->data.coef+=qb->data.coef; /* Los valores de exponente de los dos son iguales, modifica el valor del coeficiente del nodo actual de Pa*/ if(qa->data.coef==0) /* Elimina el actual nodo del polinomio Pa*/ { DelFirst(Pa,ha,&qa); FreeNode(&qa); } else ha=qa; DelFirst(Pb,hb,&qb); FreeNode(&qb); qb=NextPos(hb ); qa=NextPos(ha); break; caso 1: DelFirst(Pb,hb ,&qb); /* El valor actual en el polinomio Pb El valor del índice del nodo es pequeño*/ InsFirst(Pa,ha,qb); ha=ha-> siguiente; qb=NextPos(hb ); } } if(!ListEmpty(*Pb)) { ( *Pb).tail=hb; Append(Pa,qb /* Vincula los nodos restantes en Pb*/ } DestroyPolyn(Pb ); /* Destruir Pb */ } void AddPolyn1(polinomio *Pa,polinomio *Pb) { /* Otro método de suma de polinomios Algoritmo: Pa=Pa+Pb, y destruye el polinomio de una variable Pb */ Posición qb; término b ; qb=GetHead(*Pb); /* qb apunta al nodo principal de Pb*/ qb=qb->next; /* qb apunta al primer nodo de Pb*/ while(qb) { b=GetCurElem(qb); OrderInsertMerge(Pa,b,cmp); qb=qb->siguiente ; } DestroyPolyn(Pb); /* Destruir Pb */ } void Opuesto(polinomio Pa) { /* Invertir los coeficientes de un polinomio de una variable*/ Posición p; p=Pa.head; while (p-> siguiente) { p=p->siguiente; p->data.coef*=-1; } } void SubtractPolyn(polinomio *Pa,polinomio *Pb) { /* Resta polinómica: Pa=Pa-Pb, y destruir el polinomio de una variable Pb */ Opposite(*Pb); AddPolyn(Pa,Pb); } void MultiplyPolyn(polynomial *Pa ,polynomial *Pb) { /* Multiplicación de polinomios: Pa=PaPb, y destruye el polinomio de una variable Pb */ polinomio Pc; Posición qa,qb ; término a,b,c; InitList(&Pc); qa=GetHead(*Pa ); qa =qa->siguiente; while(qa) { a=GetCurElem(qa); qb=GetHead( *Pb); qb=qb->siguiente; while(qb) { b=GetCurElem(qb) ; c.coef=a.coef*b.coef; c.expn=a.expn+b.expn; OrderInsertMerge(&Pc, c,cmp); qb=qb->siguiente; } qa=qa->siguiente ; } DestroyPolyn(Pb); /* Destruir Pb */ ClearList(Pa); /* Restablecer Pa a una lista vacía*/ (*Pa ).head=Pc.cabeza; (*Pa).tail=Pc.tail; (*Pa).len=Pc .len; }