Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) ::

C Programmierung (Teil 2)

1. Datenstrukturen

2. Aggregationen

3. Zeiger und Speichereferenzen

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Datenstrukturen

Datenstrukturen

• Wie einzelne Variablen definiert und benutzt werden wurde bereits eingeführt
• Mit Rekords werden einzelne Variablen zu benannten Datenstrukturen zusammengefasst
• Eine Definition einer Datenstruktur ist eine Typedefinition, und es können Variablen von diesem Typ erstellt werden.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Datenstrukturen

Datenstrukturen

struct <sbezeichner> { 
  <datentyp> <ebezeichner>;
  <datentyp> <ebezeichner>;
  ..
};
typedef struct <sbezeichner> <tbezeichner>;
struct <sbezeichner> ds1;
<tbezeichner> ds2;

Datenstrukturen in C. Die Deklaration eines Strukturtyps fängt immer mit dem Schlüsselwort struct an und enthält eine Liste von Elementen in geschweiften Klammern.

• sbzeichner: Name der Datenstrukur (Datentyp ist noch struct <sbezeichner>
• ebezeichner: Name eines Datenstrukturfelds (Element)
• tbezeichner: Name eines Datentyps (hier als Ersatz für struct <sbezeichner>)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Datenstrukturen

Datenstrukturen

Die Größe des Datenebereichs im Speciher für eine Datenstruktur ist die Summe alle Datenbereiche der einzelnen Strukturelemente

struct {        ┌――――――――┐  addr
  char a; ――――▶ │        │
                ├――――――――┤  addr+1
  int b;  ――――▶ │        │
                │        │
                │        │
                │        │
                ├――――――――┤  addr+5
  char c; ――――▶ │        │
                ├――――――――┤  addr+6
  float d;――――▶ │        │
                │        │
                │        │
                │        │
                │        │
                │        │
}               └――――――――┘

Lineares Speichermodell einer Datenstruktur

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Datenstrukturen

Datenstrukturen

Folgende Operationen sind mit Strukturvariablen erlaubt:

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Datenstrukturen

Datenstrukturen

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Datenstrukturen

Datenstrukturen

struct s {
  int x;
  int y;
};
struct s ds1,ds2;
// falsch: memcpy(ds2,ds1,sizeof(ds1));
// richtig mit Umwandlung in einen Pointer, als
memcpy((void*)&ds2,(void *)&ds1,sizeof(ds1));
// richtig!
int foo(struct s ds) {
  return ds.x;
}
.. foo(ds1) ..

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger

Zeiger werden auch Pointer genannt und stellen einen Verweis auf eine bestimmte Speicheradresse dar, in der z.B. ein Wert steht.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger

Es folgt ein kleiner Überblick über die wichtigsten Dinge, die man mit Zeigern realisieren kann:

• Speicherbereiche können dynamisch zur Laufzeit reserviert, verwaltet und wieder gelöscht werden.

• Mit Zeigern können Sie Datenobjekte per Referenz an Funktionen übergeben.

• Mit Zeigern lassen sich Funktionen als Argumente an andere Funktionen übergeben.

• Komplexe verkettete Datenstrukturen wie Listen und Bäume lassen sich ohne Zeiger gar nicht realisieren.

• Es lässt sich ein typenloser Zeiger (void *) definieren, mit dem Datenobjekte beliebigen Typs verarbeitet werden können, auch Funktionen!

• Achtung: Zeiger sind bei der Definition uninitialisiert! Gefahr fehlerhafter Speicherzugriffe!

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger

                              ┌―――――――――――――┐ 80000     
      ┌―――――――――――――――――┐     │             │           
      │                 │     ├―――――――――――――┤ 79010     
    ┌―┴┐                └――――▶│ var (25)    │ &var=79010
┌――▶│25│ 30  35               ├―――――――――――――┤           
│   └――┘ ▲   ▲                │             │           
│        │   │                ├―――――――――――――┤ 50000     
│        │   └―――――――――┐      │ ptr (79010) │ &ptr=50000
│        └――――――――――┐  │      ├―――――――――――――┤           
│                   │  │      │             │ 40000     
└―― int var=25;     │  │      │             │           
    int *ptr=&var;  │  │      ├―――――――――――――┤ 30000     
        *ptr=30;  ――┘  │      │ pptr (50000)│           
    int **pptr=&ptr;   │      ├―――――――――――――┤ 20000     
        **pptr=35;  ―――┘      │             │           
                              │             │ 10000     
                              │             │           
                              └―――――――――――――┘ 0

Der Zusammenhang zwischen Wert- und Zeigervariablen. Das Widersprüchliche ist: Zeiger sind auch Wertvariablen, und obwohl sie mit einen ausgwiesenen Datentyp erzeugt werden sind sie doch immer vom gleichen Datentyp (z.B. long oder int)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger

Zeiger stellen lediglich die Adresse und den Typ eines Speicherobjekts dar. Die Definition eines solchen Zeigers sieht wie folgt aus:

<Datentyp> *<pbezeichner>;
*<pbezeichner> = ε(*<pbezeichner>; // Ausdrücke mit Pointern
<pbezeichner> = &<vbezeichner>;

Definition von Zeigervariablen von einem bestimmten Zieldatentyp, Indirektionsoperationen, und Adressierung.

Am Stern * zwischen Datentyp und Bezeichner kann man den Zeiger erkennen. Der Name ist der Bezeichner und wird als Zeiger auf einem Typ Datentyp deklariert.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger als Funktionsparameter

Mit Zeigern kann man Referenzsemantik in Funktionsaufrufen simulieren:

void foo(int x, int *y) {
  *y=x*2;
}
int main() {
  int x,y;
  x=2;
  foo(x,&y);
  printf("%d %d\n",x,y);
}

Referenzsemantik für Funktionsargumente mit Pointern

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

• Sowohl Wertvariablen als auch Zeigervariablen können über Zeiger (d.h. Adressenwerte) an Funktionen übergeben werden und dort verändert werden können

www4.cs.fau.de Beispiel von Zeigern als Funktionsargumente

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger als Funktionsparameter

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeiger

Zeiger als Rückgabewert

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Dynamische Speicherallokation

Dynamische Speicherallokation

• Will man zur Laufzeit neue Speicherobjekte (vor allem Strukturen und Arrays) erzeugen, muss man dazu einen Speicherbereich auf dem Heap reserviren.

• Dazu wird die <addr>=malloc(<numbytes>) Funktion verwendet.

• Anders als Speicherobjekte die auf dem Stack reserviert wurden benötigt der Heap explizite Freigabe von nicht mehr benötigten Speicherbereichen mittels der free(<addr>) Funktion.

• Allokation und Freigabe müssen immer paarweise verwendet werden (wobei bei Beendigung eines Programms der gesamte belegte Speicher aber freigegeben wird).

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Der NULL-Zeiger

Der NULL-Zeiger

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Der NULL-Zeiger

Der NULL-Zeiger

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Der Funktionszeiger

Der Funktionszeiger

Obwohl Funktionen in C keine Werte erster Ordnung sind (also nicht an Funktionen als Argumente übergeben werden können), kann man sich wieder mit Zeigern auf Funktionen behelfen.

• Die Definition und Verwendung von Funktionszeigern ist in ihrer Schreibweise etwas verwirrend.

int foo(int x) { return x*2 };
int (*fooPtr)(int);
int main() {
  fooPtr=&foo;
  printf("%d\n",foo(2));
  printf("%d\n",(*fooPtr)(2));
}

Funktionszeiger

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Der Funktionszeiger

Zeiger können alsi auf Funktionen verweisen. Sie verweisen dann auf die Anfangsadresse des Codes in der Funktion. Es sind hierbei zusätzliche Klammern nötig. Ein solcher Zeiger kann wie folgt erstellt werden:

<Rückgabetyp> (*funktionsZeiger)(<formale Parameter>);

• Ohne die Klammerungen von (*funktionsZeiger) hätte man lediglich den Prototyp einer Funktion und keine Definition eines Zeigers erstellt.

• Der Name der Funktion wird dann implizit in einen Zeiger auf diese Funktion umgewandelt.

• Aufrufen kann man die Funktion über Zeiger mit:

( *funktionsZeiger ) (parameter);

womit der Funktionszeiger explizit dereferenziert wird.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Der Funktionszeiger

CS={"-1":"free","-2":"malloc","-3":"memcpy","-4":"printf",
    "-5":"foo","-6":"main"}
CSI={"free":-1,"malloc":-2,"memcpy":-3,"printf":-4,
     "foo":-5,"main":-6}
DS.writeInt32(CSI["foo"],fooPtr);
printf("%d\n",eval(CS[DS.readInt32(fooPtr)])(2));

JS Code vom fooPtr C Code unter Verwendung von Funktionstabellen

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Arrays

Statische Definition

<Datentyp> <Arrayname> [ <Anzahl_der_Elemente N> ];
<Datentyp> <Arrayname> [ <N> ][ <M> ] ..;

Definition einer Aggregatvariable mit Speicherallokation. Der gesamte belegte Speicherbeich ist N sizeof(elementtype), sowie mehrdimensionale Arrays.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Speicherlayout

Speicherlayout bei zweidimensionalen Matrizen

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

<Datentyp> <Arrayname> [ <Anzahl_der_Matrizen Z> ]
                       [ <Anzahl_der_Zeilen Y> ] 
                       [ <Anzahl_der_Spalten X> ];

Bei dreidimensionalen Arrays ist der Tiefenindex führend, dann folgen Zeilen- und Spaltenindex.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Arrayzugriff

• Arrayelemente (von Aggregatvariablen und Zigervariablen) werden inidiziert.
  • Um einzelnen Array-Elementen einen Wert zu übergeben oder Werte daraus zu lesen, wird der Indizierungsoperator [] (auch Subskript-Operator genannt) verwendet, bei mehreren Dimensionen je ein Indizierungsoperator pro Dimension.

Arrayzugriffe über den Index werden nicht geprüft. Ein zu großer Index führt beim Lesen zu fehlerhaften Werten, beim Schreiben zu einer Kollision mit einer anderen Variable, und ggfs. zu einem Speicherschutzfehler (z.B. Lesen/Schreiben über Segmentgrenzen hinaus).

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Initialisierung mit einer Initialisierungsliste

• Ein Array (vor allem kleine Arrays) kann bereits bei der Definition mit einer Initialisierungsliste initialisiert werden. Hierbei wird bei der Definition eine Liste von Werten in geschweiften Klammern, getrennt durch Kommata, angegeben.

<Datentyp> <Arrayname> [ <Anzahl_der_Elemente N> ] = 
  { <Wert El1>, <Wert El2> , .. , <Wert ElN> };

Initialisierung von Arrays. Die Angabe der Anzahl der Elemente kann auch weggelassen werden, ergibt sich aus der Werteliste. Die Anzahl der Elemente in der Werteliste darf aber kleiner als ein explizit angegebenes N sein.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Dynamische Arrayvariablen

• Anstelle einer Aggregatvariable type name[N] kann auch eine Zeigervariable type *name definiert werden.
  • Hier muss dann explizit Speicher reserviert werden.

<Datentyp> *<Arrayname>;
..
  <Arrayname>=(<Datentyp> *)malloc(N*sizeof(<Datentyp>));
..

Definition einer Zeigervariable für Arrays mit Speicherallokation. Ein Array wird daraus erst durch die Speicherbelegung.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Adressrechnung

1. Eindimensionale Arrays [i] mit Definition <eltype> x[I]:

$${A}={i}\cdot\text{sizeof}{\left(\text{eltype}\right)}$$

2. Zweidimensionale Arrays [i][j] mit Definition <eltype> x[I][J]:

$${A}={\left({i}{J}+{j}\right)}\cdot\text{sizeof}{\left(\text{eltype}\right)}$$

3. Multidimensionale Arrays [i1][i2].. mit Definition <eltype> x[I1][I2].. und Dimension d:

$${A}={\sum_{{{l}={1}}}^{{d}}}{\left({i}_{{l}}\cdot{\prod_{{{k}={l}}}^{{{d}}}}{I}_{{k}}\right)}\cdot\text{sizeof}{\left(\text{eltype}\right)}\\ {\prod_{{u}}^{{u}}}={1}$$

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Zeigerarrays

• Wir haben festgestellt dass mehrdimensionale Arrays nicht dynamisch linear erzeugt werden können bzw. man selber explizit die Indexberechnung gemäß vorheriger Gleichungen (ohne Datentypmultiplikation) durchführen.

• Eine Möglichkeit multidimensionale Arrays zu erstellen und zu nutzen sind Zeigerarrays, d.h. die Partitionierung einer lineare Tabelle in einzelnen verkettete Tabellen.

• Bei Zeigerarrays kann man dann wieder multidimensionale Indizierung durchführen!

• Es werden als Zeigertabellen verwendet um weitere Zeigertabellen oder die Wertarrays zu referenzieren.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Arrays

Zeigerarrays

int **xp;
int main() {
  xp=(int **)malloc(10*sizeof(int *));
  for(int i=0;i<10;i++) {
   xp[i]=(int *)malloc(10*sizeof(int));
  }
  for(int i=0;i<10;i++)  { 
    for(int j=0;j<10;j++) { 
      xp[i][j]=i+j; 
    } 
  }
}

Zeigerarrays von Arrays, so z.B. auch main(char **argv)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeigerarithmetik

Zeigerarithmetik

int x=1;
x=x+1;
x++;
print(x) // x==3;

int *x=1
x=x+1;
x++;
print(x) // x==9 !!!!;

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeigerarithmetik

Zeigerarithmetik

int *xp;
..
  int *xpp;
  xp=(int *)malloc(100*sizeof(int));
  xpp=xp;
  printf("%d==%d\n",xpp,xp);
  for(int i=0;i<100;i++) {
   *xpp=i;
   xpp++;
  }
  printf("%d!=%d\n",xpp,xp);
  xpp=xp;
..

Arrayzugriff über dynamische Zeiger

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeigerarithmetik

+

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zeichenketten

Zeichenketten

• Zeichenketten (Strings) sind in C utf8 oder ASCII kodierte char Arrays.
  • Da keine Länge gespeichert wird muss eine Zeichenkette immer mit einem NULL Zeichen (Ganzzahlwert 0) abgeschlossen werden.
  • Ansonsten übliche Arrays

char message[]="Hello World";
char *m;
int main() {
  m=(char *)malloc(100);
  memcpy(m,message,strlen(message)+1)
  pritnf("%s %s\n",message,m);
}

Zeichenketten in C

Stefan Bosse - Grundlagen der Betriebssysteme - Modul C2 C Programmierung (Teil 2) :: Zusammenfassung

Zusammenfassung