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;
}
}