29.04.2015, 03:08 |
Auf diesen Beitrag antworten » |
deppensido |
verkette Listen in C zum speichern von Matrizen
hallo,
meine Aufgabe ist es eine verkette Liste in C zu implementieren, die eine Matrix beliebiger Größe speichern soll. Konkret soll man eine Funktion schreiben, die so eine Matrix erzeugt und eine die diese Ausgibt. Von C habe ich ehrlich gesagt nicht viel Ahnung und glaube, dass die Funktionsrümpfe
auch nicht ganz richtig sind. Bis lang habe ich nur folgendes:
code: |
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:
|
#include <stdlib.h>
#include <stdio.h>
struct cell {
int num_columns;
int num_rows;
struct cell* next;
};
int main() {
struct cell* c;
c = malloc(sizeof(struct cell));
c->num_columns = 4;
c->num_rows = 4;
c->next = NULL;
grid_init(c->num_columns, c->num_rows);
grid_print(c);
grid_print_dot(c);
return 0;
}
void grid_init(struct cell* num_columns,struct cell* num_rows) {
}
void grid_print(struct cell* grid) {
}
void grid_print_dot(struct cell* grid) {
}
|
|
Jedenfalls komme ich überhaupt nicht weiter. Daher wäre es toll, wenn mir jemand ein paar Tipps und oder eine grobe Vorgehensweise beschreiben könnte.
Vielen Dank im voraus. |
|
|
|
29.04.2015, 16:08 |
Auf diesen Beitrag antworten » |
eulerscheZahl |
Hallo,
bevor wir uns an die Implementierung machen, sollten wir uns eine Struktur überlegen, wie die Daten überhaupt abgespeichert werden sollen. Wenn deine Zelle nur einen Nachfolger hat, wirst du damit keine zweidimensionale Struktur erzeugen können. Zumindest für die erste Zeile (oder Spalte) brauchen die Zellen 2 Nachfolger, einen in Zeilenrichtung und einen in Spaltenrichtung.
Du kannst jetzt entweder jeder Zelle 2 Nachfolger geben (wobei die meisten ungenutzt wären, folglich Speicherverschwendung), oder du definierst dir eine Liste von Listen. |
29.04.2015, 17:07 |
Auf diesen Beitrag antworten » |
deppensido |
Danke für die Antwort.
Also mach ich am Besten einen zweiten Zeiger in Cell,
Z.B. struct cell *next2? Dann hätte jedes Element 2 Zeiger?
Wie würde eine Liste von Listen funktionieren? Das kann ich mir
nur schwer vorstellen. Dies wäre wohl wegen dem geringeren Speicherverbrauch die bessere Lösung.
Vielen Dank im voraus. |
29.04.2015, 17:16 |
Auf diesen Beitrag antworten » |
eulerscheZahl |
Ja, bzw. struct cell *nextRow und struct cell *nextColumn.
So wäre ich die Sache angegangen:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
|
struct cell {
int value;
struct cell* next;
};
struct line {
struct cell* first; //Verweis auf erstes Element, die folgenden dann über cell->next
struct line* nextLine; //Verweis auf nächste Zeile
};
struct matrix {
struct line* firstLine; //folgende Zeilen dann über die erste Zeile
}; |
|
Das Einfügen neuer Zeilen ist ohne großen Aufwand möglich. Wenn du eine Spalte ergänzen willst, wird es schon aufwändiger, da du dann jede Zeile bearbeiten musst. |
Anzeige |
|
|
29.04.2015, 19:07 |
Auf diesen Beitrag antworten » |
deppensido |
würde ich dann folgendermaßen auch einfach neue Spalten eingeben können?
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
|
struct cell {
int value;
struct cell* next;
};
struct line {
struct cell* first; //Verweis auf erstes Element, die folgenden dann über cell->next
struct line* nextLine; //Verweis auf nächste Zeile
};
struct column {
struct cell* first;
struct column* nextColumn;
};
struct matrix {
struct line* firstLine; //folgende Zeilen dann über die erste Zeile
struct column* firstColumn;
};
|
|
oder sollte ich es der Einfachheit lieber so übernehmen, wie von dir vorgeschlagen?
Vielen dank im voraus. |
29.04.2015, 19:14 |
Auf diesen Beitrag antworten » |
eulerscheZahl |
Da sehe ich keinen Vorteil drin, die Referenzen der einzelnen Zeilen müssen ja trotzdem angepasst werden. Da machst du dir zusätzliche Arbeit, ohne einen Nutzen. |
29.04.2015, 19:22 |
Auf diesen Beitrag antworten » |
deppensido |
ok, dann änder ich das besser wieder |
29.04.2015, 20:32 |
Auf diesen Beitrag antworten » |
deppensido |
ich habe jetzt mal die Funktion zum erstellen der Matrix geschrieben. Könntest du bitte
schauen, ob das richtig ist? Ich kann das noch nicht testen, da ich die Funktion zur Ausgabe noch schreiben muss. Wie die Werte der Matrix belegt werden, ist laut Aufgabenstellung egal.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
|
void grid_init(int num_columns, int num_rows) {
struct matrix *start = 0; //start initial mit 0
struct line *l;
struct cell *c;
c = malloc(sizeof(struct cell)); //Speicher reservieren
l = malloc(sizeof(struct line));
l->nextLine = start; //Auf erste Zeile verweisen
c->next = l->first; //Auf erstes Element verweisen
for(int i = 0; i < num_rows; i++) {
for(int j = 0; j < num_columns; j++) {
c->value = i + 10; //Matrix mit Werten füllen
c = c->next; //auf nächstes Element verweisen
}
l = l->nextLine; //auf nächste Zeile verweisen
}
}
|
|
vielen Dank im voraus. |
29.04.2015, 21:03 |
Auf diesen Beitrag antworten » |
eulerscheZahl |
So einfach geht es dann doch nicht.
Hier etwas Code:
code: |
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:
|
#include <stdlib.h>
#include <stdio.h>
struct cell {
int value;
struct cell* next;
};
struct line {
struct cell* first; //Verweis auf erstes Element, die folgenden dann über cell->next
struct line* nextLine; //Verweis auf nächste Zeile
};
struct matrix {
struct line* firstLine; //folgende Zeilen dann über die erste Zeile
};
struct line* createLine(int columns, int val) {
struct line* l = malloc(sizeof(struct line));
struct cell* currentCell = malloc(sizeof(struct cell));
currentCell->value = val;
l->first = currentCell;
for(int i = 1; i < columns; i++) {
struct cell* c = malloc(sizeof(struct cell));
c->value = currentCell->value + 1;
currentCell->next = c;
currentCell = c;
}
return l;
}
struct matrix* grid_init(int num_columns, int num_rows) {
struct matrix* mat = malloc(sizeof(struct matrix));
struct line* currentLine = createLine(num_columns, 0);
mat->firstLine = currentLine;
for (int i = 1; i < num_rows; i++) {
struct line* l = createLine(num_columns, i*num_columns);
currentLine->nextLine = l;
currentLine = l;
}
return mat;
}
void printLine(struct line* l) {
struct cell* c = l->first;
while (c) {
printf("%d\t", c->value);
c = c->next;
}
printf("\n");
}
void printMatrix(struct matrix* mat) {
struct line* l = mat->firstLine;
while (l) {
printLine(l);
l = l->nextLine;
}
}
int main() {
struct matrix* mat = grid_init(4,3);
printMatrix(mat);
} |
|
|
29.04.2015, 21:24 |
Auf diesen Beitrag antworten » |
deppensido |
das funktioniert. Vielen Dank! Den Rest, sollte ich nun auch ohne große
Probleme lösen können. |