====== Eindimensionale Arrays ======

===== Grundlagen =====

Ein Feld ist ein strukturierter Datentyp mit einer bestimmten Anzahl von Elementen, die alle vom selben Typ sein müssen. In der %%C++%%-Literatur werden Felder auch als Vektoren bezeichnet.
Mit der Typvereinbarung werden eigene Typnamen für Felder vergeben. Diese neuen Namen können wie Standard-typenbezeichner verwendet werden.

Beispiele:

<code cpp>
#define max 7
typedef float Vektor[4]; 
typedef char Zeile[80]; 
typedef int Besetzt[max]; 
typedef int Zaehler[26];
</code>

Die Vereinbarung eines Feldtyps enthält die **Anzahl** der Elemente und den **Elementtyp**.

Die Anzahl muss eine **Konstante** sein und wird in eckige Klammern [] eingeschlossen.

Wird ein Feldtyp beispielsweise mit ''float Vektor[4];'' vereinbart, bedeutet dies, dass dieses Feld 4 Elemente (jedes vom Typ ''float'') hat.

Mit diesen Feldtypen können (wie mit jedem anderen Typ) Variablen vereinbart werden.

<code cpp>
Vektor v; 
Zeile satz; 
Besetzt besetzt; 
Zaehler anz;
</code>

Auf ein einzelnes Feldelement wird über den Namen der Variablen, die mit einem Index versehen wird, zugegriffen. Der Index kann jeder beliebige int-Ausdruck sein. Der Wert des Indexausdrucks muss innerhalb der Indexgrenzen liegen. Die Untergrenze ist immer 0, die Obergrenze ist gleich der Anzahl minus 1.

Der Index wird in eckige Klammern eingeschlossen.

**Der Index wird nicht überprüft.**

Beispiele:

<code cpp>
v[0]=25.2;
v[l]=37.1; 
v[2]=66.3; 
v[3]=97.7;

ch=satz[i*2];

if (zimmer[i])  ...;
anz[ch-'A']=anz[ch-'A']+l;
/* besser: */
anz[ch-'A']++;
</code>

Da Indizes nicht überprüft werden, kann beispielsweise die folgende Zuweisung vom Compiler nicht als fehlerhaft erkannt werden:

<code cpp>
v[4]=99.0;
</code>

Wird diese Anweisung ausgeführt, kann die Reaktion des Programms nicht vorhergesagt werden. Da die Variablenspeicherplätze nacheinander vergeben werden, //kann eine andere Variable verändert werden// - ein Fehler, der nur sehr schwer zu finden ist. Oft stürzt auch das Programm ab! Dieser Fehler kann auch bei zu klein dimensionierten Zeichenketten auftreten.

Ein expliziter Name für einen Feldtyp darf auch fehlen, das heißt, der Feldtyp kann direkt in der Variablenvereinbarung stehen.

Beispiele (diese Vereinbarungen entsprechen den schon verwendeten Vereinbarungen):

<code cpp>
#define max 7 
int main()
{float v[4];
 char satz[80];
 int zimmer[max]; 
 int anz[26];
} 
</code>

Die erste Schreibweise ist aber bei längeren Programmen übersichtlicher und daher zu bevorzugen.

===== Beispiel 1 ===== 
10 Zahlen sollen eingelesen werden. Es ist das arithmetische Mittel zu berechnen. Die Anzahl der Zahlen, die größer als das Mittel sind, ist auszugeben.

{{:inf:cpp:adim-68-1.jpg?300|}}

<code cpp>
/* Berechnet die Anzahl der Zahlen, die
   größer als das arithmetische Mittel
   der Zahlenfolge sind */

#include <iostream.h>

const int anz=10;

int main ()
{ float zahl[anz],summe=0,mittel;
  int i,groesser=0;
  cout << "Bestimmt die Anzahl der Zahlen > arithm. Mittel\n";
  cout << anz << " Zahlen:\n";

  for (i=0;i<anz;++i)
  { cout << i+1 << ". Zahl ? ";
    cin >> zahl[i];
  }
  for (i=0;i<anz;++i)
    summe+=zahl[i];
  mittel=summe/anz;

  for (i=0;i<anz;++i)
    if (zahl[i]>mittel) ++groesser;
  cout << groesser << " Zahlen sind größer als das arithmetische Mittel(" <<  mittel << ")\n";
    
  system("PAUSE");
  return EXIT_SUCCESS;   
}
</code>


===== Beispiel 2 =====

Ein beliebiger Text soll eingelesen und die absolute und relative Häufigkeit der einzelnen Großbuchstaben in Tabellenform ausgegeben werden. Der Text wird durch einen Punkt abgeschlossen.


{{:inf:cpp:adim-68-2.jpg?300|}}

<code cpp>
/* Absolute und relative Häufigkeit der Buchstaben
   in einem beliebigen Text bestimmen */
   
#include <iostream.h>
#include <conio.h>
#include <ctype.h>
using namespace std;

int main ()
{ char i,j,zeichen;
  int anz=0,zaehler[26];
  for (i='A';i<='Z';++i) zaehler[i-'A']=0;
  printf("Häufigkeit von Großbuchstaben.\n"
	 "Text ? ('.' = Abbruch)\n");

  while ((zeichen=getche())!='.')
  { ++anz;
    if (isupper(zeichen))
      ++zaehler[zeichen-'A'];
  }

  if (anz==0) anz=1;
  printf
    ("\nBuchstabe   Abs.H.     Rel.H.     "
    "Buchstabe   Abs.H.     Rel.H.\n"
    "=============================     "
    "=============================\n");
  for (i='A';i<='M';++i)
  { if (anz==0) anz++;
    printf("%4c: %10d %10.1f%%      ",
      i,zaehler[i-'A'],
      zaehler[i-'A']*100.0/anz);
    j=i+13;
    printf("%4c: %10d %10.1f%%\n",
      j,zaehler[j-'A'],
      zaehler[j-'A']*100.0/anz);
  }
  system("PAUSE");
  return EXIT_SUCCESS; 

</code>

===== Übergabe von eindimensionalen Feldern an Unterprogramme =====

Die Übergabe von Feldern an Unterprogramme erfolgt 
  * über Typdefinition (''typdef'') oder
  * über Angabe der Adresse auf das betreffende Feld oder
  * über allgemeine Typangabe.


Programmbeispiel 1 sieht mit Unterprogrammen so aus:

<code cpp>
/* Berechnet die Anzahl der Zahlen, die
   größer als das arithmetische Mittel
   der Zahlenfolge sind */

#include <iostream.h>

const int anz=10;
typedef float Feld[anz]; // nur bei erster Variante notwendig

void lesen(Feld z)
{ int i;
  for (i=0;i<anz;++i)
  { cout << i+1 << ". Zahl ? ";
    cin >> z[i];
  }
} 

float mittel(Feld z)
{ int i;
  float summe=0;
  for (i=0;i<anz;++i)
    summe+=z[i];
  return summe/anz;
} 

int zaehlen(Feld z,float m)
{ int i,groesser=0;
  for (i=0;i<anz;++i)
    if (z[i]>m) ++groesser;
  return groesser;
}


/* Alternative Variante der Parametervereinbarung: mit Hilfe von Zeigern
void lesen(float *z)
{ int i;
  for (i=0;i<anz;++i)
  { cout << i+1 << ". Zahl ? ";
    cin >> *(z+i);
  }
} 

float mittel(float *z)
{ int i;
  float summe=0;
  for (i=0;i<anz;++i)
    summe+=*(z+i);
  return summe/anz;
} 

int zaehlen(float *z,float m)
{ int i,groesser=0;
  for (i=0;i<anz;++i)
    if (*(z+i)>m) ++groesser;
  return groesser;
} 
*/


/* Alternative Variante der Parametervereinbarung: Angabe, dass z ein eindimensionales Array von float-Werten ist
void lesen(float z[])
{ int i;
  for (i=0;i<anz;++i)
  { cout << i+1 << ". Zahl ? ";
    cin >> z[i];
  }
} 

float mittel(float z[])
{ int i;
  float summe=0;
  for (i=0;i<anz;++i)
    summe+=z[i];
  return summe/anz;
} 

int zaehlen(float z[],float m)
{ int i,groesser=0;
  for (i=0;i<anz;++i)
    if (z[i]>m) ++groesser;
  return groesser;
}
*/

int main ()
{ float zahl[anz];
  float m;
  cout << "Bestimmt die Anzahl der Zahlen > arithm. Mittel\n";
  cout << anz << " Zahlen:\n";

  lesen(zahl);
  m=mittel(zahl);
  cout << zaehlen(zahl,m) << " Zahlen sind groesser als das arithmetische Mittel(" << m << ")\n";

  system("PAUSE");
  return EXIT_SUCCESS;    
} 
</code>

===== Übungsaufgaben =====

Schreibe ein Programm, dass

<box 100% |<fc #0000ff>Ex 1</fc>>
...das eine Folge von n ganzen Zahlen einliest und jene Zahlen aus der Folge löscht, die mehrmals vorkommen. Anschließend soll die Folge ausgegeben werden.
</box>

++++ Lösung|
<code cpp delmultiple.cpp>
#include <iostream>
using namespace std;

main(){
int n;
cout<<"Anzahl Zahlen: "; cin>>n; cout<<endl;

int zahl[n];
cout<<"\nZahlen: \n";
for(int i=0;i<n;i++)cin>>zahl[i];

sort(zahl,zahl+n);

cout<<"\nSortiert ohne Wiederholung: \n";
cout<<zahl[0] <<" ";
for(int i=1;i<n;i++)
   if(zahl[i]!=zahl[i-1]) cout<<zahl[i]<<" "; 

cout<<endl<<endl;
system("PAUSE");       
</code>
++++


<box 100% |<fc #0000ff>Ex 2</fc>>
...das eine Folge von n ganzen Zahlen einliest und jene Zahlen aus der Folge löscht, die größer als eine vorgegebene Zahl sind. Anschließend soll die Folge ausgegeben werden.
</box>

++++ Lösung|
<code cpp delgreater.cpp>
#include <iostream>
using namespace std;

main(){
int *zf, max,anz;
cout<<"Anzahl der Zahlen: ";cin>>anz;
zf=new int[anz];
cout<<"\nMaxiaml hoechste Zahl: ";cin>>max; 
cout<<"\nZahlen:\n";
for(int i=0;i<anz;i++)cin>>zf[i];
for(int j=0;j<anz;j++){if(zf[j]>max){zf[j]=max+1;}}
cout<<"\nSortierte, begrenzte Folge: \n";
sort(zf,zf+anz);
for(int l=0;l<anz;l++){if(zf[l]!=max+1){cout<<zf[l] <<" ";}}   
delete[] zf;

cout<<endl<<endl;       
system("PAUSE");
</code>
}
++++

<box 100% |<fc #0000ff>Ex 3</fc>>
...das eine maximal 80 Zeichen lange Zeichenfolge umdreht.
</box>

++++ Lösung|
<code cpp revers.cpp>
#include <iostream>
#include <conio.h>
using namespace std;

const char ENTER=13;

int main(){
 int i=0;
 char zeichen, zkette[80];
 cout<<"Zeichenfolge eingeben:\n";
 do {
   zeichen = getche(); 
   zkette[i]=zeichen;
   i++;
 } while (zeichen!=ENTER && i<80);
 cout<<endl<<endl;
 reverse(zkette,zkette+i);
 for(int j=0;j<i;j++)cout<<zkette[j];   

 cout<<endl;
 system("PAUSE");       
}
</code>
++++


<box 100% |<fc #0000ff>Ex 3a</fc>>
...das an einer maximal 40 Zeichen langen Zeichenfolge überprüft, ob es sich um ein Palindrom handelt.

Hinweis: Von einem Palindrom spricht man dann, wenn ein Wort von vorne und hinten gelesen gleich aussieht, z.B. LAGERREGAL
</box>

++++ Lösung|
<code cpp palindrom.cpp>
#include <iostream>
#include <conio.h>
using namespace std;
const char CR=13;

main()
{char zeichen; char zkette[100];
 cout<<"Geben Sie Ihre Zeichenkette ein (max. 100): \n";
 // Eingabe der Zeichenkette
 int i=0; 
 do {
   zeichen = getche(); 
   zkette[i]=zeichen;
   i++;
 } while (zeichen!=CR);
 int laenge=i-1;
 // Ausgabe verkehrt
 cout<<"\nRueckwaerts gelesen:\n ";
 for(i=laenge-1;i>=0;i--) cout<<zkette[i];
 // Vergleich auf Palindrom-Eigenschaft
 i=0; while(zkette[i]==zkette[laenge-i-1]) i++;
 if (i==laenge) cout<<"\nEs handelt sich um ein Palindrom.";         
 else cout<<"\nEs ist kein Palindrom."; 
 
 cout<<"\n\n"; system("PAUSE");
}
</code> 
++++

<box 100% |<fc #0000ff>Ex 4</fc>>
...das zwei steigend sortierte Buchstabenfolgen zu einer sortierten Folge zusammenfasse In der Ergebnisfolge dürfen keine gleichen Buchstaben vorkommen. Bei der Eingabe soll überprüft werden, ob die Buchstabenfolgen steigend sortiert sind.
</box>

<box 100% |<fc #0000ff>Ex 5</fc>>
...das zwei monoton steigende Zahlenfolgen zu einer monoton steigenden Zahlenfolge zusammenfasst und ausgibt.
</box>

<box 100% |<fc #0000ff>Ex 6</fc>>
...das zwei gleichlange Wörter einliest und den HAMMING-Abstand berechnet: Als HAMMING-Ab-stand zweier Wörter mit gleichlangen Binärcodes wird die Anzahl jener Stellen bezeichnet, in denen sich die beiden Wörter unterscheiden.

Beispiel: \\ 001010110 101000110\\ HAMMING-Abstand:2
</box>

<box 100% |<fc #0000ff>Ex 7</fc>>
...das Vektoren verknüpft. Folgende Operationen sollen durchführbar sein:
   * Addition zweier Vektoren,
   * Subtraktion zweier Vektoren,
   * Multiplikation von Vektor und Skalar,
   * skalares Produkt zweier Vektoren.

Die Vektoren sollen maximal sechs Komponenten enthalten.
</box>

<box 100% |<fc #0000ff>Ex 8</fc>>
...das wie ein Auszählreim arbeitet: n Kinder sind im Kreis aufgestellt. Nach Aufsagen eines Auszählreimes mit m Silben wird das jeweils m-te Kind im Kreis ausgeschieden. Auszugeben ist die Reihenfolge, in der die Kinder ausscheiden.

Anleitung:
Jedem Kind ist ein Element eines Arrays zugeordnet. Zu Beginn werden sämtliche Elemente des Arrays gleich 1 gesetzt. Danach werden die Elemente zyklisch durchlaufen und das jeweils m-te Element gleich 0 gesetzt. Die Indizes der 0 gesetzten Elemente entsprechen den Nummern der ausgeschiedenen Kinder.
</box>

++++ Lösung|
<code cpp auszaehlreim.cpp>
// Auszählreim
#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;

int main()
{int n,m;
 cout << "\nBitte Anzahl der Kinder und Anzahl der Silben eingeben:\n"; 
 cin >> n >> m;
 int kind[n];
 // Initialierung des Feldes
 for (int i=0;i<n;i++) kind[i]=1;
 // Ausgabe
 // for (int i=0;i<n;i++) cout << "(" << i <<"|" << kind[i] <<")";
 cout << endl;

 clock_t sz,ez;
 sz = clock(); 

 // Auszählreim
 int pos=-1;
 for (int i=0;i<n;i++) {  
    int z=1; 
    while (z<=m){
       pos=(pos+1)%n;   
       if (kind[pos]) z++;
    }      
    kind[pos]=0;z=0;         
    cout <<  pos  << ' ';
 }    
 ez = clock(); 
 cout << "\nGesamtzeit: " << (ez-sz)/(double)CLOCKS_PER_SEC << "\n\n";
 
 
 system("PAUSE");
 return 0;
}
</code>
++++

<box 100% |<fc #0000ff>Ex 9</fc>>
...das alle Primzahlen, die kleiner oder gleich der natürlichen Zahl n sind, ausgibt.

Anleitung (Siebverfahren des ERATOSTHENES):
Verwende ein Array mit dem Index 0..n-2, dessen Elemente gleich 1 (wahr) gesetzt werden. Danach betrachtet man mit dem Index 0 beginnend der Reihe nach sämtliche Elemente mit dem Wert wahr und setzt jene Elemente gleich 0 (falsch), deren Indizes Vielfache des gerade betrachteten Indexwertes+2 sind. Die  Indizes jener  Elemente,  die den Wert wahr beinhalten, sind Primzahlen.
</box>

++++ Lösung|
<code cpp siebdeseratosthenes.cpp>
#include <iostream>
using namespace std;

main(){ 
 int n;
 cout <<"Geben Sie eine natuerliche Zahl ein: "; cin >>n; int z[n+1];
 z[1]=0; for(int i=2;i<=n;i++) z[i]=1;
 for(int i=3;i<=n;i++) 
   for(int j=2;j<i;j++) if(i%j==0) z[i]=0;
 cout<<"\nAlle Primzahlen, die kleiner oder gleich der natuerlichen Zahl "<<n<<" sind:\n\n";
 for(int i=1;i<=n;i++)if(z[i]==1) cout<<i<<' ';
 cout << "\n\n"; system("PAUSE");
}
</code>
++++

<box 100% |<fc #0000ff>Ex 10</fc>>
...das ein Kartenspiel von 52 Karten an beliebig viele Spieler austeilt und das Blatt jedes Spielers sortiert ausgibt. Die Anzahl der Spieler soll eingegeben werden.
Beispiel:

{{:inf:cpp:adim-70-1.jpg?300|}}
</box>

<box 100% |<fc #0000ff>Ex 11</fc>>
... das einen Text gemäß der Cäsar-Verschlüsselung codiert.
Dabei wird jeder Buchstabe eines Textes durch seinen m-ten Nachfolger erstetzt.

z.B. Hallo Welt, m=3\\
wird zu Kdoor Zhow
</box>

++++ Lösung|
<code cpp caesarverschluesselung.cpp>
// Cäsar-Verschlüsselung
#include <iostream>
#include <conio.h>
using namespace std;

int main()
{int m,i=0;
 char text[100], vtext[100], zeichen;
 cout << "Cäsar-Vershluesselung\n\n";
 cout << "Bitte Verschiebung m angeben: "; cin >> m;
 // Eingabe des Textes
 cout << "\nBitte zu verschluesselnden Text eingeben ('.' fuer Ende) \n"; 
 do {
   zeichen = getche(); // cout << '*';
   text[i]=zeichen;
   i++;
 }
 while (zeichen!='.');
 // Ausgabe des Textes
 cout << endl;
 for (int j=0;j<(i-1);j++) cout << text[j];
 cout << endl;

 // Verschluesselung     
 for (int j=0;j<(i-1);j++) {
   // Großbuchstaben verschlüsseln  
   if (text[j]>= 65 && text[j] <=90) vtext[j]=(text[j]-65+m)%26+65;
   // Großbuchstaben verschlüsseln
   if (text[j]>= 97 && text[j] <=122) vtext[j]=(text[j]-97+m)%26+97;
 }
 
 // Ausgabe des codierten Textes
 cout << endl;
 for (int j=0;j<(i-1);j++) cout << vtext[j];
 cout << endl;

     
 system("PAUSE");
 return 0;
}

</code>
++++