Informatiker Board | Algorithmen | verkette Listen in C zum speichern von Matrizen

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » verkette Listen in C zum speichern von Matrizen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

verkette Listen in C zum speichern von Matrizen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

verkette Listen in C zum speichern von Matrizen

Zitatantwort auf diesen Beitrag erstellen

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.

deppensido hat dieses Bild (verkleinerte Version) angehängt:

29.04.2015 03:08

Nehmen Sie deppensido in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

29.04.2015 16:08

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

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:07

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

29.04.2015 17:16

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

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:07

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

29.04.2015 19:14

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

ok, dann änder ich das besser wieder

29.04.2015 19:22

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

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 20:32

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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);
}

__________________
Syntax Highlighting fürs Board (Link)

29.04.2015 21:03

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

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

29.04.2015 21:24

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » verkette Listen in C zum speichern von Matrizen