verkette Listen in C zum speichern von Matrizen

Neue Frage »

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.
 
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.
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.
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.
 
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.
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.
Auf diesen Beitrag antworten »
deppensido

ok, dann änder ich das besser wieder
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.
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);
}
Auf diesen Beitrag antworten »
deppensido

das funktioniert. Vielen Dank! Den Rest, sollte ich nun auch ohne große
Probleme lösen können.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »