Ciao non ho guardato il tuo codice , ma la soluzione mi sembra intuitiva ...

tu hai un array citta[] e un array temperature[] , la posizione i nome città è uguale alla posizione i
temperatura , allora con un unica funzione se scambi citta scambi temperatura

Come salvi le temperature ???? se hai 5 nomi citta[5][15] , ti serve un array di 5 elementi temperature[5] , cosa ti serve una matrice di interi ???????
Ma forse ho capito male


codice:
void scambio(char citta[][15],int temperatura[],int i , int j){
char string[20];
     int temp;
          strcpy(string,citta[i]);
          temp=temperatura[i];
          strcpy( citta[i],citta[j]);
          temperatura[i]=temperatura[j];
          strcpy(citta[j], string);
          temperatura[j]=temp;

return;
}