Dzis wykonamy tak jak poprzednio kilka operacji na listach. I pierwsze zadanie., Załóżmy, że mamy listę kilkuelementową posortowaną. Należy napisać taką strukturę, która doda jakiś element do tej listy bez straty uporzadkowania. Jak coś takiego zrobić. Oto pseudokod:

#include <stdio.h>

struct node * AddSort(struct node *lista, int x){

struct node * pop,*nast,*e;

pop=lista;

nast=lista->next;

while (nast->val <x){

pop=pop->next;

nast=nast->next;

}

e=(struct node) malloc(sizeof(struct));

if (e!=NULL){

pop->next=e;

e->next=nast;

}

return lista;

}

I zobaczmy jeszcze, jak można rozwiązać ten problem z użyciem atrapy:

#include <stdio.h>

struct node * AddSort(struct node *lista, int x){

struct node * pop,*nast,*e, *a

struct node atrapa;

a=&atrapa;

a->next=lista;

pop=a;

nast=a->next;

while (nast!=NULL && nast->val<x){

pop=pop->next;

nast=nast->next;

}

e=(struct node) malloc(sizeof(struct));

if (e!=NULL){

pop->next=e;

e->next=nast;

}

return a->next;

}

A teraz załóżmy, że mamy dane jakieś dwie listy uporządkowane. Kolejne zadanie polegać będzie na napisaniu takiej struktury, która połączy te dwie listy i stworzy jedną listę uoprządkowaną (połączy elementy list i uporządkuje je w jednej). Oto kod:

#include <stdio.h>

struct node * merge(struct node *l1, struct node *l2){

struct node *wynik=NULL,*konw;

if (l1==NULL) return l2;

else if (l2==NULL) return l1;

else { //l1 i l2 nie są NULL

if (l1->val<l2->val){

wynik = l1;

l1=l1 -> next;

konw=wynik;

}

else

{

wynik = l2;

l2=l2->next;

konw=wynik;

}

while (l1!=NULL && l2!=NULL)

{

if(l1->val<l2->val)

{

konw->next=l1;

konw=l1;

l1=l1->next;

}

else {

konw ->next=l2;

konw=l2;

l2=l2->next;

}

}

if(l1=NULL) konw->next=l2;

else konw->next=l1;

return wynik;

}

}

I jeszcze zobaczmy, jak by to mogło wyglądać z użyciem atrapy:

#include <stdio.h>

struct node * merge(struct node *l1, struct node *l2){

struct node *wynik=NULL,*konw,*a;

struct node atrapa;

a=&atrapa;

if (l1==NULL) return l2;

else if (l2==NULL) return l1;

else { //l1 i l2 nie są NULL

konw=a;

}

while (l1!=NULL && l2!=NULL)

{

if(l1->val<l2->val)

{

konw->next=l1;

konw=l1;

l1=l1->next;

}

else {

konw ->next=l2;

konw=l2;

l2=l2->next;

}

}

if(l1=NULL) konw->next=l2;

else konw->next=l1;

return a->next;

}

}