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