Mensajes

[while(num_producers_working != 0 || products.size() > 0)]

Que bueno que la gente se meta con problemas de concurrente!

He solucionado el problema de la condición de carrera, helgrind ya no se queja, la culpa la tenía el método size en la línea while(num_producers_working != 0 || products.size() > 0)...

Cuidado! Yo no tengo ni idea de helgrind, no lo había oido en mi vida, pero la depuración en concurrente es algo impracticable! Necesitas un cálculo para razonar sobre la corrección de un programa, con invariantes, etc...
Conviene tener princpios sólidos sobre los que montar tus soluciones concurrentes.
Un buen libro: "Concurrent Programming. Gregory R. Andrews".
No vas a aprender nada de C++, pero si mucho de programaci'on concurrente!

Algunas observaciones a tu programa:

• Productores consumidores se ejecutan indefinidamente. De otro modo, puedes llegar a bloqueos, (imagina 1 productor y 1000 consumidores, a 1 items cada uno... Es obvio que los consumidores se quedarán esperando indefinidamente
• El buffer, o es un escalar, o un buffer limitado. Nada se gana con los stacks... Interesa FIFO, no LIFO
• Nada se gana leyendo los manuales de la libreria <thread> o <condition variable> si no se conoce en que consisten los monitores

Código (cpp) [Seleccionar] Expandir


#include <cassert>
#include <iostream>
#include <vector> // as bounded buffer.
#include <thread>
#include <mutex>
#include <condition_variable>
#include <chrono>
#include <atomic>
#include <cassert>

#define MAX_THREADS 1000
#define SIZE_BUFFER 5
#define TIMEOUT  200

using namespace std;

// Patemeters overwritten on input.
static int P = 5; // Producers
static int C = 10; // Consumers
static int P_DELAY=1000 ; // Prod-Delay
static int C_DELAY=500;


// MONITOR VARIABLES
static mutex xmutex;                    // Our mutex, monitor methods in exclusion
static condition_variable if_full;             // to indicate that our stack is
// not full  between the thread operations
static condition_variable if_empty;            // to indicate that our stack is
// not empty between the thread operations

static int front = 0;
static int rear = 0;
static vector<int>  buf(SIZE_BUFFER);
static int holes = SIZE_BUFFER;
static int items = 0;
// Monitor invariants:
// inv. items =  (front "-" rear)
// inv. holes = SIZE_BUFFER - (front "-" rear)
// inv. 0 <= front < SIZE_BUFFER, 0 <= rear < SIZE_BUFFER

static atomic<int> m(0); // simulating a fresh message;

// MONITOR METHODS
void init()
{
 front=rear=items=0;
 holes = SIZE_BUFFER;
}

void deposit(const int id,const int msg)
{
unique_lock<mutex> lock(xmutex);

// await holes > 0
if_full.wait(lock, [] { return holes > 0; });
buf[rear] = msg; rear = ((rear+1) % SIZE_BUFFER);
cout << "p[" << id << "]\tdeposit\t:\t" << msg << endl;
holes--; items++;
if_empty.notify_all();
}

//      Consume function, consumer_id will consume a product
int fetch(const int id)
{
unique_lock<mutex> lock(xmutex);
int mess;
// await items > 0
if_empty.wait(lock, [] { return items > 0; });
mess = buf[front]; front = ((front+1) % SIZE_BUFFER);
cout << "c[" << id << "]\t\t\t\t\tfetch\t:\t" << mess << endl;
holes++;items--;
if_full.notify_all();
return mess;
}


// Real code for threads.
void producer(int id)
{
for (; 1; )
{
deposit(id, ++m);
this_thread::sleep_for(chrono::milliseconds(P_DELAY));
}
return;
}

void consumer(int id)
{
int msg;
for (; 1; )
{
msg = fetch(id);
this_thread::sleep_for(chrono::milliseconds(C_DELAY));
}
return ;
}


void simulation()
{
vector<thread> threads;

init();
// Create producers
for (int p = 0; p < P; ++p)
 threads.push_back(thread(producer, p));

// Create consumers
for (int c = 0; c < C; ++c)
 threads.push_back(thread(consumer, c));

// Wait for consumers and producers to finish
for (auto& t : threads)
t.join();
}


// IO staff.
int main(int argc, char *args[])
{
 cout << "C P P_DELAY C_DELAY " << endl;
 for( ; cin >> C >> P >> P_DELAY >> C_DELAY; )
   {
     assert((C<MAX_THREADS) && (P<MAX_THREADS) );
     assert((P_DELAY > 0) && (C_DELAY > 0) );
     simulation();
   }
 return 0;
}



Aqui un ejemplo de salida. Tu puedes experimientar variando , el numero de p/c, la velocidad relativa...

Con independencia de la velocidad relativa, dentro de un mismo grupo no está determinado el orden de acceso al monitor. Así,  es posible que el productor del mensaje 9 tenga acceso al monitor antes que el productor del mensaje 8.  Eso sí, entre dos consumidores el primero en acceder extraerá el mnesaje 9, y el segundo el 8, por ser FIFO.

Código [Seleccionar] Expandir


g++ conc.cpp -o main -lpthread && ./main
C P P_DELAY C_DELAY
5 5 500 500
p[1] deposit : 1
p[2] deposit : 2
p[0] deposit : 3
p[3] deposit : 4
c[0] fetch : 1
p[4] deposit : 5
c[1] fetch : 2
c[3] fetch : 3
c[2] fetch : 4
c[4] fetch : 5
p[1] deposit : 6
p[3] deposit : 7
p[0] deposit : 9
p[2] deposit : 8
c[0] fetch : 6
p[4] deposit : 10
c[1] fetch : 7
c[3] fetch : 9
c[2] fetch : 8
c[4] fetch : 10
p[1] deposit : 11
p[3] deposit : 12
p[0] deposit : 13
p[2] deposit : 14
c[0] fetch : 11
p[4] deposit : 15
c[1] fetch : 12
c[3] fetch : 13
c[2] fetch : 14
c[4] fetch : 15
p[1] deposit : 16
p[0] deposit : 18
p[3] deposit : 17
p[2] deposit : 19
c[0] fetch : 16
p[4] deposit : 20
c[1] fetch : 18
c[3] fetch : 17
c[2] fetch : 19
c[4] fetch : 20
p[0] deposit : 21
p[1] deposit : 22
p[3] deposit : 23
p[2] deposit : 24
p[4] deposit : 25
c[0] fetch : 21
c[1] fetch : 22
c[3] fetch : 23
c[2] fetch : 24
c[4] fetch : 25
p[0] deposit : 26
c[0] fetch : 26
p[3] deposit : 29
c[4] fetch : 29
p[4] deposit : 30
c[2] fetch : 30
p[1] deposit : 27
c[1] fetch : 27
p[2] deposit : 28
c[3] fetch : 28
p[0] deposit : 31
p[3] deposit : 32
c[4] fetch : 31
c[0] fetch : 32
p[4] deposit : 33
c[2] fetch : 33
p[1] deposit : 34
c[1] fetch : 34
p[2] deposit : 35
c[3] fetch : 35
p[4] deposit : 37
c[0] fetch : 37
p[3] deposit : 38
c[2] fetch : 38
p[2] deposit : 40
p[0] deposit : 36
p[1] deposit : 39
c[4] fetch : 40
c[1] fetch : 36
c[3] fetch : 39
p[4] deposit : 41
c[0] fetch : 41
p[3] deposit : 42
c[2] fetch : 42
p[2] deposit : 43
p[0] deposit : 44
p[1] deposit : 45
c[4] fetch : 43
c[1] fetch : 44
c[3] fetch : 45
...
C-c C-c


Como lo solucionaste, tengo un problema parecido...

Todavia no lo ha resuelto.

Lo que dice MAFUS respecto a la redireccion de la entrada estandar en shell/UNIX (tambien en COMMAND/Microsoft) es cierto, pero va a ser dificil si no elevas la abstracción, de "caracter \n" a "linea vacia". Para eso te ayuda la función

Código [Seleccionar] Expandir

#include <stdio.h>

ssize_t getline(char **lineptr, size_t *n, FILE *stream);

Aquí va una propuesta, con una "durisima" formalización, de la que no estoy seguro al 100%.
IMPORTANTE: Segun mi criterio, el ultimo parrafo acaba en EOF, no en EOL.

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h> // strlen


#define LINES_PER_FILE 1000
#define LINES_PER_PARAGRAPH 100
#define PARAGRAPH 100
#define LENGTH_LINE 250

/*
 Formal spec hard. Use line (not char) as main abstraction

 P : text[0..txtLns) of char[LENGTH_LINE];
 Q : \forall i,j : 0 <= i <= j <= N and paragraph(V,i,j,N) :
          let
            M = emptyLines(V,0,i)
          in
            isCopy(Pgrphs,M,i,j) and PgrphLns[M]=(j-i)
     txtPgrphs = min(1,N) + emptyLines(text,0,txtLns)

 where

    emptyLines(text,0,txtLns) = #i : 0 <=i <txtLns :empty(text[i])
    paragraph(V,i,j,N) =
                 i = max k : 0 <= k <=j and (k > 0 -> empty(text[k-1]) : k
                 j = min k : i <= k <= N and (k < N -> empty(text[k]) : k
    isCopy(Pgrphs,M,n,m) = \forall i : 0 <= i < m-n : Pgrphs[M][i]=text[n+i]

*/
void  text2paragraphs(const char text[][LENGTH_LINE],
     const int txtLns,
                     char pgrphs[PARAGRAPH][LINES_PER_PARAGRAPH][LENGTH_LINE],
     int *txtPgrphs,
     int pgrphLns[])
{
 int n;
 for(*txtPgrphs=(txtLns>0), n=pgrphLns[0]=0;  n<txtLns;n++)  
   if (strlen(text[n])>1)
     strncpy(pgrphs[*txtPgrphs-1][pgrphLns[(*txtPgrphs-1)]++],text[n],LENGTH_LINE);
   else
     (*txtPgrphs)++;
 return;
}

int main(int argc, char *args[])
{
 char text[LINES_PER_FILE][LENGTH_LINE];
 int txtLns,txtPgrphs;
 char paragraphs[PARAGRAPH][LINES_PER_PARAGRAPH][LENGTH_LINE];
 int pgrphLns[PARAGRAPH];
 
 char *line=NULL;
 ssize_t read;
 size_t len;

 // Input
 txtLns = 0 ;
 while ((read=getline(&line,&len,stdin))!=-1)
     strncpy(text[txtLns++],line,LENGTH_LINE);
 free(line);

 // Process
 text2paragraphs(text,txtLns,paragraphs,&txtPgrphs,pgrphLns);

 // Output
 printf("%d\n",txtPgrphs);
 for (int i=0; i< txtPgrphs ; i++)
   {
     printf("(%d,%d)\n",i,pgrphLns[i]);
     for (int j=0; j< pgrphLns[i] ; j++)
printf("%d.%d\t%s",i,j,paragraphs[i][j]);
   }
}

Ahora comprobamos con el siguiente soneto en castellano del insigne Garcilaso de la Vega (quitando acentos y usando algunas formas del siglo XVI). Fichero poema.txt

Código [Seleccionar] Expandir


bash-2.04$ cat poema.txt
A Dafne ya los brazos le crecian
y en luengos ramos vueltos se mostraban;
en verdes hojas vi que se tornaban
los cabellos qu'el oro escurecian;

de aspera corteza se cubrian
los tiernos miembros que aun bullendo 'staban;
los blancos pies en tierra se hincaban
y en torcidas raices se volvian.

Aquel que fue la causa de tal danio,
a fuerza de llorar, crecer hacia
este arbol, que con lagrimas regaba.

Oh miserable estado, oh mal tamanio,
que con llorarla crezca cada dia
la causa y la razon por que lloraba!


Veamos la salida en shell/UNIX. La primera linea marca el  número de parrafos. Despues, por cada párrafo se da el número de orden , el total de líneas por parrafo, y cada línea enumerada dentro de su párrafo.

Código [Seleccionar] Expandir


bash-2.04$ ./main < poema.txt
4
(1,4)
1.1 A Dafne ya los brazos le crecian
1.2 y en luengos ramos vueltos se mostraban;
1.3 en verdes hojas vi que se tornaban
1.4 los cabellos qu'el oro escurecian;
(2,4)
2.1 de aspera corteza se cubrian
2.2 los tiernos miembros que aun bullendo 'staban;
2.3 los blancos pies en tierra se hincaban
2.4 y en torcidas raices se volvian.
(3,3)
3.1 Aquel que fue la causa de tal danio,
3.2 a fuerza de llorar, crecer hacia
3.3 este arbol, que con lagrimas regaba.
(4,3)
4.1 Oh miserable estado, oh mal tamanio,
4.2 que con llorarla crezca cada dia
4.3 la causa y la razon por que lloraba!


Hmm...   Demasiada formalidad para un poema tan humano.

Una proposición falsa implica a todas las proposiciones, verdaderas o falsas. Que uno se encuentre con una aparente consistencia puede favorecer el entusiasmo pero no aporta prueba de nada; lamentablemente la pura lógica no se conmueve con expresiones emocionales

Pero bueno, este es tu acertijo y tus reglas. Por mí está bien, como digas.

Ejem, ejem.... Veo que has entendido parcialmente el razonamiento: de premisas falsas se llega conclusiones falsas. Es decir, el enigma podría decir que después de acabar el bucle infinito se podía llegar a cualquier cosa: que 2=2, 23=11+25, que la raíz de dos es un número racional.... Tanto verdaderas como falsas... En latín

EX IMPOSSIBILE QUOD LIBET SEQUITUR
(DE LO IMPOSIBLE SE SIGUE CUALQUIER COSA)

Pero no es de recibo desacreditar mi razonamiento por la "sorpresa", o "entusiasmo" en aras a la rigurosidad implacable de la lógica... El razonamiento es absolutamente válido y correcto. Lo que no sería es decir que se concluye que 1==0.

En ningún caso se ha probado que 1=0. Fíjate bien: En el enunciado el autor marcó on terminating the program, realzando al terminar el programa.... Cosa que no ocurre nunca, y por tanto, solo ocurre "en el infinito", lo que puede dar lugar a una contradicción, según el estándar C: 1=0. A partir de ahí, como tú dices, se puede sacar lo que quieras, en particular que assert(1) fallara.

Creo que es compatible con mostrar una reacción de asombro ante  un razonamiento riguroso y objetivo. Sin "smileys" se encuentra la prueba entre etiquetas geshi...

De todas formas, gracias loretz por tu comentario.

[terminación]

Exacto MAFUS! Lo has clavado!

Yo lo veo una proposición más filosófica que práctica.
Ya de por sí la premisa, sobre el segundo fuentes, es falsa porque ese bucle no terminan nunca, al tener en la condición un 1 y por tanto siempre será cierta. Pero en ese mismo fuente se podría considerar que 1 es falso ya que ese valor detiene el bucle y, además, hace saltar al assert. ...
En ese supuesto, imposible por otra parte, sí que se llegaría a la solución propuesta.

Bueno, creo que ya lo tengo, chicos. Me han ayudado un poco por ahí... Y cuando lo entiendes, es una pura broma....

La cuestión tiene que ver no tanto con C, como con dos aspectos de la algoritmia:

• la terminación de un programa
• la corrección parcial, que nos dice que si acaba, (notese la cursiva) entonces el programa computa lo que se espera de él.  

Las dos cuestiones son ciertas. Empiezo por la más extraña, la segunda, la del bucle infinito.

• Según el estandar ANSI-C, asssert solo falla cuando la evaluación del parámetro da 0 (false). En nuestro caso, assert(1), cuando 1==0, lo que es un absurdo  
• Según el estandar ANSI-C, el bucle acaba cuando la parte del discriminante da 0 (false) . En nuestro for( ; 1; ), caso, cuando 1==0 , (en terminos prácticos, nunca)  
• O sea, que cuando el bucle acabe, (no dice que acabe, dice que cuando acabe, esto es importante!) se cumplirá   1==0, lo que es la condición para que assert(1) falle.  

Esta bien el enigma... A nadie engaña por decir que esperando lo suficiente, el assert(1) fallará... Eso sí, tiene que esperar lo suficiente, por los siglos de los siglos...

Formalmente, pura lógica...

Código [Seleccionar] Expandir



(Short proof)
    1=0 |= 1=0  q.e.d  

(Full proof)

Let Post Q:1=0 .

Then we have to proof that

 { I } for( ; 1 ; ) { Q } (Partial correctness, no matter I)

 1. { I } skip {I}  SKIP
 2. I and 1=1 -> I (Logic, stronger antecedent )
 3. { I and 1=1 } skip { I } STREN(1,2)
 4. I and 1=0 -> 1=0 (Logic, false (or stronger) antecedent)
 5. { I } for( ; 1 ; ) { 1=0 }  WHILE(3,4)

 q.e.d

Remark: ANSI-C states
    * assert(1) call does fail when 1=0 ("never")
    * loop for( ;1;) does end when 1=0 ("never" ;-D)
    * empty loop's body is skip.

El primer problema, que todos veíamos que acababa, también es parecido...pero ahora si nos interesa demostrar que efectivamente acaba, y nos da igual lo que pase al acabar.

En los libros de algoritmia se dice que para que un bucle acabe (terminación) tenemos que idear una quota definida positiva en el punto antes de evaluar la condición de salida  (un invariante). Como no hay variables, escogemos como quota C(n)=0... Esta quota tiene que disminuir cada vuelta, es decir 0 < 0, lo que es un absurdo.
Como va a disminuir cada vuelta, si nunca entra? Bueno, seg'un el estandar ANSI entra cuando la evualuación de la guarda es  distinta de 0, nuestro caso for( ; 0 ; ) , cuando 0!=0 (o sea nunca).

El resultado es que cuando 0!=0 entonces ocurrirá que 0 < 0. No dice que 0!=0, sino que cuando 0!=0, absurdo, entonces 0<0 (otro absurdo). Genial!  Pura lógica.

Código [Seleccionar] Expandir



(Short proof)

  0!=0 |= 0 < 0   q.e.d.

(Full proof)

Let C()=0 >= 0 positively defined, i.e.

     I -> 0 >= 0  (no matter I)
     
Then we have to proof

    { I and 0!=0 and 0=0 } skip { 0 < 0} (Quota indeed decreases)

   1. { 0 < 0 } skip { 0 < 0 } (SKIP)
   2. I and 0!=0 and 0=0 -> 0 < 0  (Logic, false antecedent)
   3. { I and 0!=0 and 0=0 } skip { 0 < 0 } (STRENG(2,1))

   q.e.d

Remark :   * ANSI-C states the loop is entered
          when 0!=0, i.e. "never" ;-D
  * empty loop's body is "skip"




[bucle infinito = ((inc = 0) and (inicio <> final))]

Hola NEBIRE

...

El primer tema a considerar: Los bucles infinitos versa que si el incremento es 0 y el valor inicial es igual al valor final, no es un bucle infitio, en otro caso si:
      bucle infinito = ((inc = 0) and (inicio <> final))
...y si el cuerpo está vacío (como es el caso), o no existe dentro una sentencia de escape del bucle (si existe, deberá examinarse también). Lógicamente en tiempo de compilación...
      Por eso no se cumple en el primer caso y sí en el segundo.
...

Esta propuesta no vale. Estás describiendo un caso muy partícular de bucles "for", los que se parecen /ajustan al patrón de Pascal

Código [Seleccionar] Expandir


for < variable-name > := < initial_value > to [down to] < final_value > do
  S;


Pero en el caso de C que se da, que variables hay?, cual es el valor inicial y/o final?
En C, el bucle for es tan versátil/expresivo como el while.

EScrito de otro modo, en el primer caso hay que explicar por qué el bucle C, acaba:

Código (c) [Seleccionar] Expandir

while (0) ;

Aqui no hay duda de que no hay valores iniciales, ni finales.... Solo constantes.

Chicos, gracias por vuestras repuestas.
 Loretz, muy buena tu exhibición, pero el ejercicio que propones no cumple lo que dice, porque YA es otro fichero fuente del que se propone...

Creo que hay que hacerlo sobre el mismo contenido del original y lo que me choca más... se supone que no vale argûir "Alguien ha jugado con el assert, pues yo también...", porque el sistema ha de ser compatible ANSI-C/ISO-C, o sea, el assert tiene que hacer lo que se espera de él...

Os digo mis progresos:

• Es un absurdo esperar a que acabe un programa que no acaba. Todo el mundo está de acuerdo en que el bucle es infinito.
• Es un absurdo esperar que assert falle cuando el parámetro sea 1, ya que sólo falla cuando vale 0, según el ANSI-C/ISO-C

No hay manera de relacionar estos absurdos entre sí? Me huelo que "por aquí va la tostada", rollo lógica....

En cuanto tenga algo os lo paso...

El primer caso a mí me parece lo mismo; para el segundo lo único que se me ocurre es que alguien ha estado jugando con <assert>, así que si yo también...

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <string.h>

#define __FILENAME__ (strrchr(__FILE__, '\\') ? strrchr(__FILE__, '\\') + 1 : __FILE__)

#define assert(expression) (void)((!(expression)) || (mostrar(#expression, __FILENAME__, (unsigned)(__LINE__), __func__), 0))

#define for(a) while(0)
...


Hola!

En una facultad de Madrid me he encontrado pinchado en el panel este original reto...
Está en inglés, pero creo que se entiende...

• El primer problema pide demostrar que el programa dado acaba
• El segundo dice que cuando acabe, el sistema sacará la llamada correspondiente al assert.  

Alguna propuesta ?

No me habia dado cuenta de la fecha como salto al principio dije "a ver tiene una hermana y si lo ayudamos?"  

Bueno, vale, pues ayudémoslo! Total, quedará registrado en Internet para la posteridad para el que quiera consultarlo...

Lo que no entiendo es por qué no le dejan usar arrays ni bucles...En fin...

Código (c) [Seleccionar] Expandir


#include <stdio.h> // scanf, printf
#include <stdlib.h> // abs

/*
  Note: Arrays and loops forbidden! 8-O

  P : True
  fun min5(a0,a1,a2,a3,a4) dev <p,d>:(int,int)
  Q : p=min i : 1 <= i < 5 : |ai-a0|=d and
      d=min i : 1<=i<N : |ai-a0|

  (Not sure about legitimate use of ai at object language)

*/


void min5(const int a0,const int a1,const int a2,const int a3,const int a4,
         int *p, int *d)
{
 *p=1; *d=abs(a0-a1);
 if (*d>abs(a0-a2))
   { *p=2; *d=abs(a0-a2);}
 if (*d>abs(a0-a3))
   { *p=3; *d=abs(a0-a3);}
 if (*d>abs(a0-a3))
   { *p=3; *d=abs(a0-a3);}
 if (*d>abs(a0-a4))
   { *p=4; *d=abs(a0-a4);}
 return;
}

int main(int argc, char *args[])
{
 int a0,a1,a2,a3,a4;
 int p,d;
 for( ;scanf("%d%d%d%d%d",&a0,&a1,&a2,&a3,&a4)==5 ; )
   {
     min5(a0,a1,a2,a3,a4,&p,&d);
     printf("%d %d\n",p,d);
   }
 return 0;
}
 



EDIT Según me han hecho notar, efectivamente hay un errata: las líneas 25-26 aparecen duplicadas por error

Algunas pruebas de ejecución...

• La línea impar es la entrada de cinco variables(a0,a1,a2,a3,a4).
• La línea par saca el ordinal de la variable que esta más cerca (4 -> a4) y la distancia |a4-a0|. En caso de varías a la misma distancia, escoge la de ordinal más baja

Código [Seleccionar] Expandir


1001 1002 2 3 4
1 1
1001 2 1002 3 4
2 1
1001 2 3 1002 4
3 1
1001 2 3 4 1002
4 1
1001 1001 1001 1001 1001
1 0


Justo, mil gracias!!

Dejo el código para intercambiar iteradores y ordenar con iteradores una lista alfabeticamente por si le sirve a alguien.

Código [Seleccionar] Expandir

void Agenda::ordenaListas(){
   Contacto auxiliar;
   for(list<Contacto>::iterator it1 = listapal.begin(); it1 != --listapal.end(); it1++)
       for(list<Contacto>::iterator it2 = (++it1)--; it2 != listapal.end(); it2++)
           if(it1->comparar(it2->getNombre()))
{
               auxiliar = *it1;
               *it1 = *it2;
               *it2 = auxiliar;
           }
}
...

Más simple  (y más C++). Usa el operador ">" de strings, los operadores next(),begin() de iterator, y swap!!

Código (cpp) [Seleccionar] Expandir


#include <string>
#include <utility> //swap
#include <list> //list

using namespace std;
...
// BubleSort
// P : listapal=A[0..N) N>=0
// Q : \forall i : 0 <= i < N-1: V[i] < V[i+1] and permut(listapal,A,N)
void  Agenda::ordenaListas()
{
 list<Contacto>::iterator it1, it2;
 for( it1 = listapal.begin(); it1 != prev(listapal.end()); it1++)
   for(it2 = next(it1); it2 != listapal.end(); it2++)
     if (it1->getNombre() > it2->getNombre()) swap(*it1,*it2);
}

No puedo mandar resultados porque no tengo el resto de los componentes, (Contacto, Agenda)...
Fijaos que es una traducción del clasico en pseudocodigo.
En algún sitio he leído que hay que tener cuidado con usar el operador "<" en iteradores!. Tiene que estar definido por el programador del iterador!

Código (c) [Seleccionar] Expandir

for (i=0; i<n-1; i++)
  for (j=i+1; j<n; j++)
   if(V[i]>V[j])
      V[i],V[j]=V[j],V[i]; // Esto no existe en C


Tiene razón, me siento estupida, pero de todas formas no quiero pasar dos parametros solo el arbol  nada mas y si no se puede pues ni modo.  

Ya... Te entiendo. Para lograrlo, tienes que hacer distinguible la raiz del resto de nodos de algún modo. Y esto se hace de dos maneras:

• O planteas tu structura con un campo "padre", que apunte al nodo padre, en el caso de la raiz null (Recomendable)
• Usas un viejo truco de C, el cualificador "static", que como efecto lateral irá grabado siempre el nivel de descenso

De otro modo no se puede... Es como si, en tu solución iterativa, dijeras que no puedes porque antes del buble while solo está permitido empezar con pilas vacías. O en otra brillante metáfora, dicha por un político en otro contexto

como un hombre con los pies en un cubo tratando de levantase tirando de la asa

Espero que esto te valga   . Ahh! Y no me parece que seas "estúpida" por preguntar eso. La mayoría de los chicos y chicas de tu edad, a los 14 años,  se dedican a jugar a video juegos, sin profundizar en las cuestiones fundamentales de la computación.

Te propongo esta con el "truco" de static

Código (c) [Seleccionar] Expandir



#include <stdlib.h>
#include <stdio.h>

/*    Binary search tree

                       10
      /  \
     5   14
    /  / \
   3   13  15

  Adding non-leaf and non-root nodes, i.e. 19

  Warning: This solution may be not portable to other languages than C
*/

typedef struct nodo {
 struct nodo *izq;
 struct nodo *der;
 int dato;
}  *pnodo;

int sumar(const pnodo a)
{
 static int level = 0 ; // <== An eye to static qualifier (side effect!)
 int suma=0;

 if(a!=NULL){
   level++;  // <=== An eye.
   suma=sumar(a->izq)+sumar(a->der);
   level--; // <== An eye.
   if ((a->izq!=NULL || a->der!=NULL) && level)  //  <=== An eye
suma+=a->dato;
 }
 return suma;
}



int main(int argc, char *args[])
{
 pnodo a=NULL;

/* Raw building of tree. More abstraction might be needed here */
 if ((a = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->dato = 10;
 if ((a->izq = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->izq->dato = 5;
 if ((a->izq->izq = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->izq->izq->dato = 3;  
 if ((a->der = (pnodo )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->der->dato = 14;
 if ((a->der->der = (pnodo )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->der->der->dato = 15;
 if ((a->der->izq = (pnodo )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->der->izq->dato = 13;

 printf("Adding internal nodes %d\n",sumar(a));

}



Esta es la salida del programa

Código [Seleccionar] Expandir


Adding internal nodes 19