[C] Tutorial Zeigerarithmetik (für Listen/Bäume)

OnkelJürgen

Moderator

Dabei seit: 30.12.2002

Beiträge: 1 719

1

Dienstag, 29. Juli 2008, 20:05

Hallo,

da ich nun etwas mehr freie Zeit habe, wollte ich mich unter anderem in Sachen C ein wenig weiterbilden und da vor allem bei der Zeigerarithmetik (Listen, Bäume, etc.), die ich bislang noch nicht vollständig durchblickt habe. Da hier auch einige Programmierer unterwegs sind, wollte ich mal fragen, ob jemand (online) ein gutes Tutorial dazu kennt. Das Grundprinzip mit Datensatz und Verweis auf das nächste Objekt ist mir klar, aber gerade beim lexikographischen Einfügen und dergleichen, habe ich noch das ein oder andere Problem.

Ich hoffe, mir kann da irgendwie in meiner Unwissenheit geholfen werden.

Viele Grüße,

OnkelJürgen

Auf jede Frage gibt es eine Antwort, man muss nur lange genug danach suchen.

z.B. auf www.netscripter.de :-P

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »OnkelJürgen« (29. Juli 2008, 20:52)

silence

König

Dabei seit: 28.02.2003

Beiträge: 981

2

Dienstag, 29. Juli 2008, 20:32

Sicher, das Zeigerarithmetik das ist, was du suchst?
Bäume un Listen gehören eher in Algorithmen bzw. Datenstrukturen. Besagte Zeigerarithmetik beschreibt lediglich das addieren und substrahieren von Zeigern (voneinander, miteinander und anderen Werten).

Zeigerarithmetik:

	Quellcode
1 2 3	int bsp[4] = { 1, 2, 3, 4 }; int pBsp = &bsp[0]; // pBsp = 1 pBsp ++; // *pBsp = 2

Oder auch

	Quellcode
1 2 3 4 5	#define PBYTE unsigned char* int bsp[4] = { 1, 2, 3, 4 }; PBYTE pPointer = (PBYTE)&bsp[0]; (int)pPointer; // = 1 (int)(pPointer + sizeof(int)); // = 2

Edit: Ups, beim Beispiel vertippt

Aktuell nutze ich: Windows, Linux, MacOS X, Solaris...weil die Welt nicht nur S/W ist!
Blog

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »silence« (29. Juli 2008, 20:49)

OnkelJürgen

Moderator

Dabei seit: 30.12.2002

Beiträge: 1 719

3

Dienstag, 29. Juli 2008, 20:52

Wie gesagt, Zeigerarithmetik auf Listen und Bäume bezogen, z.B. sowas spaßiges:

Spoiler
Quellcode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/* list_ins_sort.c
   Sortieren einer Liste mittels insertion sort */

struct knoten
{
   int element;
   struct knoten *weiter;
};

void sort(struct knoten *);

void drucken(struct knoten*);

void freigeben(struct knoten*);

main()
{
   int i, laenge;
   struct knoten *liste=NULL, *lauf;
   unsigned seed = time(NULL);
   srand(seed);
   printf("Laenge der Liste:\n");
   scanf("%d", &laenge);
   
   for (i=0; i<laenge; i++)
   {  /* neue Listenelemente werden hier am Anfang eingefuegt */
      lauf = (struct knoten *) calloc(1,sizeof(struct knoten));
      lauf->element = rand()%100;
      lauf->weiter = liste;
      liste = lauf;
   }

   printf("\nAusgabe der Liste:\n");
   drucken(liste);
   
   /* Sortieren der Liste: */
   sort(liste);
   
   printf("\nAusgabe der sortierten Liste:\n");
   drucken(liste);

   freigeben(liste);
}

void sort(struct knoten *k)
{
   int a, b;
   struct knoten *lauf1, *lauf2=k, *lauf3;
   if (k!=NULL && k->weiter!=NULL)
   { /* mindestens zwei Elemente in der Liste */
      while (lauf2->weiter != NULL)
      {
         lauf3=lauf2;
         lauf2=lauf2->weiter;
         b=lauf2->element;
         if (b < lauf3->element)
         {  /* b muss in das Anfangsstueck eingeordnet werden */
            lauf1=k;
            while (lauf1->element < b)
               lauf1=lauf1->weiter;
            if (lauf2 != lauf1)
            {/* es wurde vor dem Listenelement, auf das lauf2 zeigt,
                ein Listenelement gefunden, auf das lauf1 zeigt und das
                mindestens den Wert b hat */
                
                a=lauf1->element;
                lauf1->element=b;
                b=a;
                lauf1=lauf1->weiter;
                while (lauf2 != lauf1)
                {
                   a=lauf1->element;
                   lauf1->element=b;
                   b=a;
                   lauf1 = lauf1->weiter;
                }
                lauf2->element=b;
            }
         }          
      }
   }
}

void drucken(struct knoten *start)
{
   while (start != NULL)
   {
      printf("%d  ", start->element);
      start=start->weiter;
   }
   printf("\n");
}
 
void freigeben(struct knoten * a)
{
   struct knoten * lauf;
   while (a!=NULL)
  {
      lauf=a->weiter;
      free(a);
      a=lauf;
   }
}

/* Beispiel:
Laenge der Liste:
10

Ausgabe der Liste:
19  21  18  59  63  94  90  99  52  23  

Ausgabe der sortierten Liste:
18  19  21  23  52  59  63  90  94  99  


*/

Halt ein Tutorial, dass genauer auf Listen anlegen, verwalten usw. eingeht.

Auf jede Frage gibt es eine Antwort, man muss nur lange genug danach suchen.

z.B. auf www.netscripter.de :-P

silence

König

Dabei seit: 28.02.2003

Beiträge: 981

4

Dienstag, 29. Juli 2008, 22:12

Ok, ich glaube wir reden immernoch einander vorbei:
Dein Bespiel hat nichts direkt mit Zeigerarithmetik zu tun, es ist einfach nur eine Form der implementierung von in der Informatik vertretenen Datenstrukturen, und darüber gibt es recht viel Materiel (d.h. wie Listen, Bäume etc arbeiten und aufgebaut sind). Das ganze hat dann erstmal nichts mit C zu tun.
Ob dir Seiten über spezielle Implementierungen (dein Beispiel) helfen, wage ich zu bezweifeln: Das untere Beispiel verwendet soweit ich sehen konnte gar keine Zeigerarithmetik, implementiert jedliglich eine einfach verkettete Liste.
Informationen über die theo. Grundlagen hätte ich welche, sind aber alle recht trocken.

Aktuell nutze ich: Windows, Linux, MacOS X, Solaris...weil die Welt nicht nur S/W ist!
Blog

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »silence« (29. Juli 2008, 22:13)

OnkelJürgen

Moderator

Dabei seit: 30.12.2002

Beiträge: 1 719

5

Dienstag, 29. Juli 2008, 22:28

Dass wir aneinander vorbeireden scheint mir auch so ... Tatsächlich geht es mir um eine didaktisch gut verständliche Erklärung zur Implementierung von Zeigern und Bäumen in C. Wie man es nun benennt ist doch Wurst, oder? Mir wurde es im Zusammenhang mit der Zeigerarithmetik erklärt, nur habe ich des öfteren noch Probleme mit eben genau dieser Implementierung und brauche quasi etwas "Nachhilfe".

Gern beschäftige ich mich auch theoretische Grundlagen, aber es irgendwann völlig durchblicken würde ich es schon gern.

Du musst mich hier auch nicht als völliger Neuling in der Materie abstempeln, aber da ich mich, Studienbedingt, nun einmal damit erst seit einem Jahr beschäftige, wollte ich eben die freie Zeit gerne zum ausmisten von Defiziten nutzen.

Mit C an sich komme ich, unabhängig von eben diesem Punkt, schon recht gut zurecht, nur war gerade dieser Punkt eben bisher etwas völlig Neues, das ich in keiner bisher (in der Freizeit) erlernten Sprache gebraucht habe.

Ich hoffe jetzt kommen wir langsam auf einen gemeinsamen Nenner und du kannst mir hoffentlich weiterhelfen.

Auf jede Frage gibt es eine Antwort, man muss nur lange genug danach suchen.

z.B. auf www.netscripter.de :-P

ospx

Kaiser

Dabei seit: 11.11.2006

Beiträge: 1 131

6

Donnerstag, 31. Juli 2008, 10:55

Ich weiß, dass du weißt, was Zeiger sind und vermutl besser damit umgehen kannst, als ich. Ist schon eine Weile her, dass ich mich intensiver mit cpp beschäftigte. Ich sehe, welchen unterschied silence meint, glaube aber auch zu wissen, was dir eventuell weiterhelfen könnte (kann natürlich auch sein, dass das für dich kicki ist und nicht dem entspr.
Das Tutorial ist schon etwas älter und leider wird es offensichtlich nicht mehr gepflegt.
Trotzdem haben sie zum Thema Zeigerarithmetik ein paar sehr schöne anschauliche Beispiele und abstruse Experimente in Verbindung mit Arrays drin, die mir diese Thematik verständlich gemacht haben:

Inhaltsübersicht gesamt cpp
Inhaltsübersicht Pointer --> hier gibt es das Kapitel "Arrays und Pointer - Allokation -
Pointerarithmetik "
mit mehreren sehr interessanten Unterseiten. Leider ist die Website total veraltet und basiert auf sehr unhandlich zu steuernden Frames. Links in der Menueleiste gibt es den Link "nächste Seite". Die Steuerung ist hierrüber am besten machbar, um die Unter- und Folgeseiten lesen zu können.

Die Website ist halt grottig ( nicht mehr zeitgemäß und nicht funktional) aber der Inhalt gut.

Ebenfalls im Kapitel Pointer gibt es ein Unterkapitel "Verkettete Listen" (in Verbindung mit Pointern), was ja so in etwa das sein dürfte, was du ungefähr meinen wirst.

Vielleicht ist ja was für dich dabei ...
Gruß

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »ospx« (31. Juli 2008, 10:57)

OnkelJürgen

Moderator

Dabei seit: 30.12.2002

Beiträge: 1 719

7

Donnerstag, 31. Juli 2008, 18:59

Danke sehr, das mit den Pointern und Listen sieht auf jeden Fall so aus, als ob es mir helfen könnte. Ist zwar alles C++, aber müsste sich ja analog auch in C umsetzen lassen.

Auf jede Frage gibt es eine Antwort, man muss nur lange genug danach suchen.

z.B. auf www.netscripter.de :-P

ospx

Kaiser

Dabei seit: 11.11.2006

Beiträge: 1 131

8

Donnerstag, 31. Juli 2008, 20:22

im Großen und Ganzen schon... mit Abstrichen. C++ ist halt eine Erweiterung von C. Soweit ich weiß, geht mit c++ alles, was mit c geht jedoch nicht anders herum. Weiß nicht so genau, inwieweit c die oop-Konzepte, die im Tutorial verwendet werden, unterstützt. Denn das ist ja die wichtigste Erweiterung von c++ im Vergleich zu c als prozeduraler Sprache. Der ganze Spaß mit cout, cin funktioniert so unter c auch nicht, läßt sich aber einfach ersetzen. Der eigentliche Zeigerkrempel müßte identisch sein, aber das wissen silence oder andere sicher genauer.

Elektrofreak

Grünschnabel

Dabei seit: 12.07.2008

Beiträge: 9

9

Donnerstag, 31. Juli 2008, 21:52

Hallo

Als kleine Übung, würd ich dir ganz klassisch mal den Huffmann-Code empfehlen. Schau mal hier , auf S.64. Hier ist alles in C, nicht in C++. Nur mit dem 'didaktisch geschickten beibringen' ist es hier nicht ganz so prickelnd. :whistling:

Gruß

silence

König

Dabei seit: 28.02.2003

Beiträge: 981

10

Donnerstag, 31. Juli 2008, 22:07

Ich glaub der Huffman Code ist nicht das richtige...
Wenn schon Algorithmen an Bäumen, dann vielleicht lieber mit Traversierung anfangen

Bäume und verkettete Listen sind in ihrer Implementierung doch relativ ähnlich, ich hab allerdings von meiner Uni entweder nur Pseudocode, oder welchen in Java, und zum C schreiben bin ich jetzt zu faul :w00t:

Aber ich suche weiter, bin mir eigentlich sicher das ich ein paar PDFs zu dem Thema aus meiner Schulzeit hatte, dort haben wir nämlich etwas ähnliches gemacht.

btw, schon interessant wie sich die Fragestellungen bei den Aufgaben im Dokument der FH von dennen auf der Uni unterscheiden :evil:

Aktuell nutze ich: Windows, Linux, MacOS X, Solaris...weil die Welt nicht nur S/W ist!
Blog

OnkelJürgen

Moderator

Dabei seit: 30.12.2002

Beiträge: 1 719

11

Donnerstag, 31. Juli 2008, 22:37

Hehe, stimmt, so nen Codec wollt ich zum Einarbeiten eigentlcih nicht durchgehen bzw. erstmal nichts so komplexes.

@silence
Naja, von den Algorithemn und Datenstrukturen hätte ich auch noch viel Pseudocode, aber leider oft eher schlecht umzusetzen, da er sich wenn, dann eher an Java orientiert (was ja Grundsätzlich auch okay ist). Leider lag aber auch hier mehr die Konzentration auf dem theoretischen Verstehen, als der Implementierung.

Also wie so ein Liste durchwandern, Element suchen, Zeiger auf neues Element setzen und dessen Zeiger auf das alte Folgeelement setzen klappt ist mir schon klar, sobald ich im Code so Zig Hilfsstrukturen und Schleifen für den Zweck hab, hapert es dann immer mehr, vor allem beim allein-implementieren, ohne Codefragmente.