Typedef int Item; struct unnodo { Item dato; struct



Descargar 123.45 Kb.
Fecha de conversión10.01.2017
Tamaño123.45 Kb.


Capítulo 9

Modificaciones de listas enlazadas

EJEMPLO 9.1

#include

#include
typedef int Item;

struct unnodo

{

Item dato;



struct unnodo *adelante;

struct unnodo *atras;

};
typedef struct unnodo Nodo;



int main()

{

Nodo * p = NULL;



p = (Nodo*)malloc(sizeof(Nodo));

scanf("%d",&(*p).dato);

(*p).adelante = NULL;

(*p).atras = NULL;

printf("%d\n",(*p).dato);

return 0;

}

EJEMPLO 9.2


typedef char* Item;

typedef struct Elemento

{

Item dato;



struct Elemento* siguiente;

}Nodo;
Nodo* crearNodo(Item x)

{

Nodo *a ;



a = (Nodo*)malloc(sizeof(Nodo));

a -> dato = x;

a -> siguiente = a; /* apunta así mismo, es un nodo circular */

return a;

}
void insertaCircular(Nodo** lc,Item entrada)

{

Nodo* nuevo;


nuevo = crearNodo(entrada);

if (*lc != NULL) /* lista circular no vacía */

{

nuevo -> siguiente = (*lc) -> siguiente;



(*lc) -> siguiente = nuevo;

}

*lc = nuevo;



}

Problema 9.1

Codificación

#include

#include

typedef char Telemento;

struct listaD

{

Telemento el;



struct listaD *Ant, *Sig;

};

typedef struct listaD ListaD;

typedef struct

{

ListaD *Cabecera, *Final;



} RegLD;

void EliminaLD(ListaD **Ld, Telemento el)

{

ListaD* Ptr;



int Encontrado = 0;

Ptr = *Ld; //búsqueda



while ((Ptr != NULL) && (!Encontrado))

{

Encontrado = (Ptr->el == el);



if (!Encontrado)

Ptr = Ptr -> Sig;

}

if (Ptr != NULL)

{

if (Ptr == *Ld) /* comienzo*/

{

*Ld = Ptr->Sig;



if (Ptr->Sig != NULL)

Ptr->Sig->Ant = NULL;

}

else

if (Ptr->Sig != NULL) /* centro*/

{

Ptr -> Ant ->Sig = Ptr -> Sig;



Ptr -> Sig -> Ant = Ptr -> Ant;

}

else

{

Ptr -> Ant -> Sig = NULL; /* final*/



}

free(Ptr);

}

}

void BorrarEnOrdenLD(ListaD** Ld, Telemento el)



{

ListaD *Ant, *Ptr;



int Encontrado=0;

Ant=NULL;

Ptr= *Ld;

while ((!Encontrado) && (Ptr != NULL))

{

Encontrado = (el<=(Ptr->el));



if (!Encontrado)

{

Ant = Ptr;



Ptr = Ptr->Sig;

}

}



if (Encontrado)

Encontrado= ((Ptr->el) == el);



if (Encontrado)

{

if (Ant==NULL) /* principio de lista*/



if (Ptr->Sig == NULL) /* comienzo y final*/

*Ld=NULL;



else /* comienzo y no final*/

{


Ptr->Sig->Ant = NULL;

*Ld = Ptr->Sig;

}

else /* no comienzo*/

if (Ptr->Sig == NULL) /* no comienzo y final*/

Ant->Sig = NULL;



else /* Centro*/

{

Ant->Sig = Ptr->Sig;



Ptr->Sig->Ant = Ant;

}

free(Ptr);



}

}

Problema 9.2



#include

#include

#include

#define mx 50



char maxi[mx], mini[mx];

struct pointer

{

char Nombre[mx];



struct pointer *Sig, *Ant;

};

typedef struct pointer puntero;



int Esvacialista(puntero *comienzo)

{

puntero *pa;



pa = comienzo->Sig;

if (strcmp(pa->Nombre,maxi) == 0) /*sólo tiene dos nodos*/

return 1;



else

return 0;

}

void CreaListaVacia (puntero **comienzo,puntero** final)

{

puntero *pa, *lista;



pa = (puntero*)malloc(sizeof(puntero)); /*Nodo final*/

strcpy(pa->Nombre,maxi);

pa-> Sig = NULL;

lista = (puntero*)malloc(sizeof(puntero)); /*Nodo cabecea*/

strcpy(lista->Nombre, mini);

lista-> Sig = pa;

lista->Ant = NULL;

pa->Ant = lista;

*comienzo = lista;

*final = pa;

}

void Anade (puntero *comienzo,puntero *final,char Nombre[mx],int por_delante)

{

puntero *pa, *Ant, *pa1;



pa = (puntero*)malloc(sizeof(puntero)); /*Nodo a insertar*/

strcpy(pa->Nombre, Nombre);



if (por_delante)

{ /* búsqueda por delante*/

pa1 = comienzo;

while (strcmp(pa1->Nombre,Nombre)<0)

{

Ant = pa1;



pa1 = pa1->Sig ;

}

/*inserción*/



Ant->Sig = pa;

pa->Sig = pa1;

pa->Ant = Ant;

pa1->Ant = pa;

}

else

{ /*búsqueda por detrás*/

pa1 = final;

while (strcmp(pa1->Nombre , Nombre) > 0)

{

Ant = pa1;



pa1 = pa1->Ant;

}

/*inserción*/



Ant->Ant = pa;

pa->Sig = Ant;

pa->Ant = pa1;

pa1->Sig = pa;

}

}

void sacar (puntero *comienzo,puntero *final,char Nombre[mx],int por_delante)



{

puntero *pa, *Ant;



if (por_delante)

{

pa = comienzo;



while ((strcmp(pa->Nombre,Nombre) < 0) && (pa->Sig != NULL))

{

Ant = pa;



pa = pa->Sig ;

}

if (strcmp(pa->Nombre,Nombre) == 0)

{ /*Borrado del nodo*/

strcpy(Nombre,"*");

strcat(Nombre, pa->Nombre);

Ant->Sig = pa->Sig;

pa->Sig->Ant = pa->Ant;

free(pa);

}

}

else



{

pa = final;



while ((strcmp(pa->Nombre, Nombre)>0)&&(pa->Ant !=NULL))

{

Ant = pa;



pa = pa->Ant;

}

if (strcmp(pa->Nombre,Nombre)==´0)

{ /*Borrado del nodo*/

strcpy(Nombre,"*");

strcat(Nombre, pa->Nombre);

Ant->Ant = pa->Ant;

pa->Ant->Sig = pa->Sig;

free(pa);

}

}

}



void main(void)

{

strcpy(mini,"\0");



strcpy(mini,">") ;

…………


}

Problema 9.3

#include

#include

#include

#define MAX 1000

typedef int Telemento;

typedef struct NuevoNodo

{

Telemento el;



struct NuevoNodo* sig;

}NodoLc;


NodoLc* NuevoNodoLc(Telemento el)

{

NodoLc *nn ;



nn = (NodoLc*)malloc(sizeof(NodoLc));

nn -> el = el;

nn -> sig = nn;

return nn;

}

void InsertaListaCircular(NodoLc ** Ultimo,Telemento el)

{

NodoLc* nn;



nn = NuevoNodoLc(el);

if (*Ultimo != NULL)

{

nn -> sig = (*Ultimo) -> sig;



(*Ultimo) -> sig = nn;

}

*Ultimo = nn;



}

void GeneraPorElFinalLc(NodoLc **Ultimo)

{

Telemento d;



NodoLc *p;

p = NULL;

randomize();

for (d = random(MAX); d; )

{

InsertaListaCircular(&p,d);



d = random(MAX);

}

*Ultimo=p;



}

void EliminarLc (NodoLc** Ultimo, Telemento el)

{

NodoLc* Puntero,*p;



int Encontrado = 0;

Puntero = *Ultimo;



if (Puntero == NULL)

return;

/* búsqueda mientras no encontrado y no de la vuelta*/



while ((Puntero->sig != *Ultimo) && (!Encontrado))

{

Encontrado = (Puntero->sig->el == el);



if (!Encontrado)

Puntero = Puntero -> sig;

}

Encontrado = (Puntero->sig->el == el); // aquí se debe encontrar el dato



if (Encontrado)

{

p = Puntero->sig;



if (*Ultimo == (*Ultimo)->sig) /* solo hay un dato*/

*Ultimo = NULL;



else

{

if (p == *Ultimo)

*Ultimo = Puntero;

Puntero->sig = p->sig;

}

free(p);


}

}

Problema 9.4.

#include

#include

#include

#define Max 1000



typedef int Telemento;

typedef struct NuevoNodo

{

Telemento el;



struct NuevoNodo* sig, *ant;

}NodoLDc;



void GeneraPorElFinalLDc(NodoLDc **Ultimo)

{

Telemento dato;



NodoLDc * NuevoN;

*Ultimo = NULL;

randomize();

for (dato = random(Max); dato; )

{

NuevoN = (NodoLDc*)malloc(sizeof(NodoLDc));



NuevoN -> el = dato;

if (*Ultimo != NULL)

{

NuevoN -> sig = (*Ultimo) -> sig;



NuevoN->ant = *Ultimo;

(*Ultimo)->sig->ant = NuevoN;

(*Ultimo) -> sig = NuevoN;

}

*Ultimo = NuevoN;



dato = random(Max);

}

}



void EliminarLDc (NodoLDc** Ultimo, Telemento el)

{

NodoLDc* Puntero,*paborrar;



int Encontrado = 0;

Puntero = *Ultimo;



if (Puntero==NULL)

return;

/* búsqueda mientras no encontrado y no de la vuelta*/



while ((Puntero->sig != *Ultimo) && (!Encontrado))

{

Encontrado = (Puntero->sig->el == el);



if (!Encontrado)

Puntero = Puntero -> sig;

}

Encontrado = (Puntero->sig->el == el); // aquí se debe encontrar el dato



if (Encontrado)

{

paborrar = Puntero->sig;



if (*Ultimo == (*Ultimo)->sig) /* solo hay un dato*/

*Ultimo = NULL;



else

{

if (paborrar == *Ultimo)

*Ultimo = Puntero;

Puntero->sig = paborrar->sig;

paborrar-> sig-> ant = Puntero;

}

free(paborrar);



}

}

Problema 9.5.



#include

#include



struct ListaD

{

char el;

ListaD *Ant, *Sig;

};

struct RegLD

{

ListaD *Cabecera, *Final;



} ;

void InicializarListaConCabecera(RegLD *Ld)

{

(*Ld).Final=(ListaD*)malloc(sizeof(ListaD));



(*Ld).Cabecera=(ListaD*)malloc(sizeof(ListaD));

(*Ld).Final->el= 'a'; /*las minúsculas son mayores que cualquier mayúscula*/

(*Ld).Final-> Ant = (*Ld).Cabecera;

(*Ld).Final->Sig =NULL;

(*Ld).Cabecera->el= ' '; /*el blanco es menor que las mayúscula*/

(*Ld).Cabecera-> Ant = NULL;

(*Ld).Cabecera->Sig = (*Ld).Final;

}

void RecorreHacialaDerecha(RegLD Ld)

{

ListaD *Actual;



Actual = Ld.Cabecera->Sig;

while (Actual !=Ld.Final)

{

printf("%3c",Actual->el);



Actual = Actual->Sig;

}

}



void RecorreHacialaIzquierda(RegLD Ld)

{

ListaD *Actual;



Actual = Ld.Final->Ant;

while (Actual != Ld.Cabecera)

{

printf("%3c",Actual->el);



Actual = Actual->Ant;

}

}



void BuscaEnLista(RegLD Ld, int k, char *c, int *Encontrado)

{

ListaD *Actual;



int Contador=1;

Actual = Ld.Cabecera->Sig;



while ((Contador < k) && (Actual != Ld.Final))

{

Actual = Actual->Sig;



Contador ++;

}

*Encontrado = (Contador == k) && (Actual != Ld.Final);



if (*Encontrado)

*c = Actual->el;

}

void InsertarEnListaOrdenada(RegLD Ld, char e)

{

ListaD *nuevo, *Actual;



Actual = Ld.Cabecera->Sig;

while (Actual->el < e) /*busca la posición de inserción en orden ascendente*/

Actual = Actual->Sig;

/*hay que Insertar en la lista ordenada a partir del puntero Actual*/

nuevo =(ListaD*)malloc(sizeof(ListaD));

nuevo->el = e;

nuevo->Sig = Actual;

nuevo->Ant = Actual->Ant;

Actual->Ant = nuevo;

nuevo->Ant->Sig = nuevo;

}

int EsUnaVocal (char e)

{

return(e =='A'|| e =='E'||e =='I'|| e =='O'|| e =='U');

}

void BorrarConsonantes(RegLD Ld)

{

ListaD *Actual, *Auxiliar;



Actual = Ld.Cabecera->Sig;

while (Actual != Ld.Final)

{

if (! EsUnaVocal(Actual->el))

{ /* suprime la consonante*/

Auxiliar = Actual; Actual = Actual->Sig;

Auxiliar->Ant->Sig = Auxiliar->Sig ;

Auxiliar->Sig->Ant = Auxiliar->Ant;

free(Auxiliar) ;

}

else

Actual = Actual->Sig ;

}

}



void main (void)

{

RegLD Ld;



int k, Encontrado;

char c;

InicializarListaConCabecera(&Ld);

printf("valor de k");

scanf("%d",&k);

randomize();

while (k >= 0)

{

switch (k)

{

case 0: RecorreHacialaIzquierda(Ld);

break;

case 1: RecorreHacialaDerecha(Ld);



break;

default:

BuscaEnLista(Ld, k, &c, &Encontrado);



if (! Encontrado)

{ c = 'A' + random('Z' - 'A' + 1);

InsertarEnListaOrdenada(Ld, c);

}

else

if( Encontrado && (!EsUnaVocal(c)))

BorrarConsonantes(Ld);

}

printf("\n");printf("valor dee k ");



scanf("%d",&k);

}

}



Problema 9.6

#include

#include

typedef struct listaD

{

struct listaD *Ant, *Sig;



int n;

} ListaD;



void Crearlista(ListaD **Frente, ListaD **Final, FILE *f)

{

int Numero;

ListaD *p;

*Final = NULL ;

fscanf(f,"%d",&Numero);

while (Numero != 0)

{ /*lee y crea solo los punteros de la izquierda*/

p= (ListaD*)malloc(sizeof(ListaD));

p->Ant = *Final;

p->n = Numero;

*Final = p;

fscanf(f,"%d", &Numero);

}

*Frente = *Final;



if (*Final != NULL)

{

(*Frente)->Sig = NULL;



while ((*Frente)->Ant != NULL)

{ /*crea los punteros de la derecha*/

(*Frente)->Ant->Sig = *Frente;

*Frente = (*Frente)->Ant;

}

}

}



void buscar(ListaD **Frente, ListaD **Final, int n, int *s)

{ /* La funcion transmite los punteros de Frente y Final*/

ListaD *f1;

int t;

f1 = *Frente;



if (f1 == NULL)

{

*s = 1; /* s=1 la lista está vacía*/



printf(" la lista está vacía error");

}

else

{

t = 1;


while (t)

{

if (f1->n == n)

{ /* reestructuración de la lista*/

(*Final)->Sig = *Frente; /*unir Frente y Final antíguo*/

(*Frente)->Ant = *Final;

*Frente = f1; /*nuevo Frente*/

*Final = f1->Ant; /*nuevo Final*/

(*Frente)->Ant = NULL; /*anular los punteros antíguos*/

(*Final)->Sig = NULL;

t = 0; *s =0;

}

else

{

if (f1 == *Final)

{ *s = 2; /*s= 2 elemento no encontrado*/

t = 0;


}

else

f1 = f1->Sig;

}

}

}



}

void escribelista(ListaD *Auxiliar)

{

printf("%10c", ' ');



while (Auxiliar->Sig != NULL)

{

printf("%5d",Auxiliar->n);



Auxiliar = Auxiliar->Sig;

}

printf("%5d\n", Auxiliar->n);



}

void main (void)

{

ListaD *Frente, *Final, *Auxiliar;



int ni, s;

FILE *f;

if ((f = fopen("datos.dat","wt")) == NULL)

{


printf(" error en archivo texto");

exit(1);


}

Crearlista(&Frente, &Final,f );

printf(" creada la lista cuyo orden es");

Auxiliar = Frente;

escribelista(Auxiliar);

printf("\n dato");

scanf("%d",&ni);

buscar(&Frente, &Final, ni, &s);



if (s == 1)

printf("la lista está vacía error") ;



else

{

printf(" dado el valor %d la nueva lista es", ni);



if (s == 2)

{


printf(" dato no encontrado\n");

s = 0;


}

else

{

Auxiliar = Frente;



escribelista(Auxiliar);

printf("\n");

}

}

printf("\n");



fclose (f);

}

Problema 9.7.




Codificación
#include

#include

#include

#define MaxF 4

#define MaxC 4

typedef int Telemento ;

typedef struct mat

{

Telemento Info;



int F, C;

struct mat *SigF, *SigC;

}Matriz;

Matriz* EAF(Matriz *A, int F, int C)

{ /* 1<= F <= MaxF, 1 <= C <= MaxC */

Matriz *P, *Pant, *Psig;

P = A;

while (P->F < F)

P = P->SigF; /*P apunta a la fila F*/

Pant = P;

Psig = P->SigC; /*Pant va por detrás de P, y Psig por delante*/



while ((P->C < C) && (Psig->C != 0))

{ /*Si la columna es 0, he dado la vuelta*/

Pant = P;

P = Psig;

Psig = Psig->SigC ;

}

if (P->C < C)



return P;

else

return Pant;

}

Matriz* EAC(Matriz *A, int F,int C)



{ /*Encuentra anterior en la columna 1 <= F <= MaxF, 1 <= C <= MaxC*/

Matriz *P, *Pant, *Psig;

P = A;

while (P->C < C)

P = P->SigC; /*P apunta a la columna C)*/

Pant=P;

Psig=P->SigF;



while ((P->F < F) && (Psig->F != 0))

{

Pant = P;



P = Psig;

Psig = Psig->SigF;

}

if (P->F >= F)

return Pant;

else

return P;

}

void Borrar(Matriz *P, Matriz *Q, Telemento *x)

{ /*Borra un nodo sabiendo que el anterior en la fila es P y en la columna es Q*/

Matriz *Aux;

Aux = P->SigC;

P->SigC = Aux->SigC;

Q->SigF = Aux->SigF;

*x = Aux->Info;

free(Aux);

}

void Insertar(Matriz *P,Matriz *Q, Telemento x)

{ /*Inserta un nodo dados P anterior en fila Q anterior en columna*/

Matriz *Aux;

Aux = (Matriz*)malloc(sizeof(Matriz));

Aux->Info = x;

Aux->F = P->F;

Aux->C = Q->C;

Aux->SigC = P->SigC;

Aux->SigF = Q->SigF;

P->SigC = Aux;

Q->SigF = Aux;

}

void CreaMatriz(Matriz ** A)

{ /*Crea la matriz sin ningún dato*/



int i;

Matriz *Aux, *Aux1;

Aux= (Matriz*)malloc(sizeof(Matriz));

Aux->F = 0;

Aux->C = 0;

*A = Aux; /*nodo (0,0)*/



for (i = 1; i <= MaxC; i++)

{ /*fila 0*/

Aux1= (Matriz*)malloc(sizeof(Matriz));

Aux1->F = 0;

Aux1->C = i;

Aux1->SigF = Aux1;

Aux->SigC = Aux1;

Aux = Aux1 ;

}

Aux->SigC = *A;



Aux = *A;

for (i = 1; i <= MaxF; i++)

{ /*Columna 0*/

Aux1= (Matriz*)malloc(sizeof(Matriz));

Aux1->F = i;

Aux1->C = 0;

Aux1->SigC = Aux1;

Aux->SigF = Aux1;

Aux = Aux1;

}

Aux->SigF = *A;



}

void Asignar(Matriz *A, int i, int j, Telemento x)

{ /*A[i,j]=x*/

Matriz *P, *Q;

P = EAF(A, i, j);

Q = EAC(A, i, j);

if (P->SigC == Q->SigF) /*está*/

if (x == 0)

Borrar(P, Q, &x);



else

P->SigC->Info = x ;



else

if (x != 0)

Insertar(P, Q, x);

}

Telemento Leer(Matriz *A, int i,int j)



{ /*Leer devuelve el elemento A[i,j]*/

Matriz *P, *Q;

P = EAF(A, i, j);

Q = EAC(A, i, j);



if (P->SigC == Q->SigF)

return P->SigC->Info;

else

return 0;

}

Problema 9.8

.

void MultiplicaFila(Matriz *A, int F, int Valor)

{ /*Multiplica una fila f de la matriz por un valor*/

Matriz *P, *Q, *R;

Telemento x;

P = EAF(A, F, 0);

Q = P->SigC;



if (Valor !=0)

while (Q->C > 0)

{


Q->Info = Q->Info * Valor;

Q = Q->SigC;

}

else /*f*0=Borrar fila*/

while (Q->C > 0)

{

R = EAC(A, F, Q->C);



Borrar(P, R, &x);

Q = Q->SigC;

}

}

void Suma(Matriz *A, Matriz *B , Matriz **C)



{

int i, j;

Telemento x;

CreaMatriz(C);

for (i = 1; i <= MaxF; i++)

for (j = 1; j <= MaxC;j++)

{

x = Leer(A, i, j) + Leer(B, i, j);



Asignar(*C, i, j, x);

}

}



void Multiplica (Matriz *A, Matriz *B , Matriz **C)

{

int i, j, k;

Telemento x;

CreaMatriz(C);



for (i = 1; i <= MaxF; i++)

for (j = 1;j<= MaxC;j++)

{

x=0;



for (k = 1; k <= MaxC; k++)

x+= Leer(A, i, k) * Leer(B, k, j);

Asignar(*C, i, j, x);

}

}



void IntercambiaFilas(Matriz *A, int f1, int f2)

{

int j;

Telemento x, y;

for (j = 1; j <= MaxC;j++)

{


x = Leer(A, f1, j);

y = Leer(A, f2, j);

Asignar(A, f1, j, y);

Asignar(A, f2, j, x) ;

}

}

void IntercambiaColumnas(Matriz *A, int c1, int c2)



{

int i;

Telemento x, y;



for (i = 1; i <= MaxC; i++)

{

x = Leer(A, i, c1);



y = Leer(A, i, c2);

Asignar(A, i, c1, y);

Asignar(A, i,c2, x) ;

}

}



void EscribeMatriz(Matriz *A)

{

int i, j;

Telemento x;

for (i = 1; i <= MaxF; i++)

for (j = 1;j<=MaxC;j++)

{

x = Leer(A, i, j);



printf("A[%2d,%2d]=%3d\n", i,j,x);

}

}



void LeeMatriz(Matriz **A)

{

int i, j;

Telemento x;

CreaMatriz(A);



for (i = 1; i <= MaxF; i++)

for (j = 1; j<= MaxC; j++)

{

printf("dato %d %d ", i,j);



scanf("%d",&x);

Asignar(*A,i,j,x);



}

}



La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal