Structures de données ... alors comment je les comprends?

Question

Donc, je suis un étudiant en Informatique et dans environ une semaine... je vais reprendre une des Structures de Données de cours, à l'aide de C++ pour l'application de la théorie. Oui, je dis "reprendre". J'ai pris le cours de l'Automne dernier, et j'ai l'impression qu'il est plus que j'ai besoin d'apprendre. Étant étudiant, j'ai l'impression que je DOIT connaître les bases, car il sera beaucoup plus facile à comprendre de nouveaux concepts dans les futures classes en connaissant déjà les concepts de base... de ne pas avoir à réapprendre à chaque fois.

La première fois, je n'avais aucune expérience en C++ et le cours devrait nous être codage d'ici la fin de la première semaine. J'ai eu du mal à obtenir par le biais de plusieurs des premiers devoirs de programmation (MPs). Inutile de dire que je suis habitué à elle et eu un peu de mal avec la syntaxe pour le reste du semestre. Mais ensuite, le plus difficile des Structures de Données est venu autour et la théorie (Grand O), est devenu la partie la plus difficile.

Dans l'ensemble c'était une bonne expérience, mais je sens que mon problème était que je n'ai pas de développer de bonnes habitudes d'étude. J'ai fait les Députés, et montré faire la leçon, mais il semble que mon cœur n'était pas là avec moi. Je veux changer ce la seconde fois car, en regardant en arrière au niveau de la classe, j'ai fait passer un bon moment et j'ai apprécié le matériel. Mais je me suis retrouvé à passer trop de temps à penser à/de la configuration de la structure de données(s) quand j'ai besoin de passer du temps à réfléchir à comment mettre de la structure de données pour les utiliser efficacement.

La théorie de l'apprentissage est difficile (surtout parce qu'il n'est pas si excitant) alors, comment dois-je l'appliquer moi-même pour vraiment comprendre les Structures de Données couvertes de classe? J'ai toujours été un apprenant visuel, interactif apprenant... je ne veux pas passer du temps à simplement faire mon Députés. Plutôt, j'ai envie de passer mon temps dans une telle manière que j'ai vraiment apprendre/comprendre les concepts et ensuite appliquer directement les connaissances.

Je suis à la recherche de toutes les suggestions... peut-être des conseils sur les habitudes d'étude qui ont travaillé pour vous dans le passé, l'apprentissage de ces concepts... ou des suggestions sur la bonne prise de notes techniques... tout ce que vous aimeriez partager :) ... et le plus important, comment se préparer avant le début du semestre.

N'hésitez pas à fournir des commentaires, même si une réponse a été sélectionné. Je suis à la recherche de vos conseils... c'est pourquoi j'ai posté :) Merci!

---

NOTE: Structures de Données et des Thèmes abordés dans le cours: Listes, Piles, Files, Arbres (différentes sortes), des Tables de Hachage, les Graphiques, de la Recherche/Tri/Traversée de techniques.

---

Mise à JOUR: Voici une liste de liens et de références compilées à partir des réponses à ce jour.

• Algorithmes en C++ par Robert Sedgewick
• Introduction aux Algorithmes par Cormen
• Le NIST Dictionnaire des Algorithmes et Structures de Données
• Algorithmes de tri
• Arbre traversals
• Graphique traversals
• http://www.codeproject.com/KB/cpp/linked_list.aspx
• http://www.codeproject.com/KB/architecture/treedata_class.aspx

Mise à JOUR 2: Voici une liste de quelques-uns plus de sources que j'ai trouvé:

• http://people.ksp.sk/~kuko/bak/grand/
• http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html
• http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html
• http://www.cs.duke.edu/csed/jawaa2/examples/BFS.html

Answer 1

Vous avez reçu quelques liens intéressants et des idées déjà. J'espère que je peux offrir un peu de point de vue différent:

J'ai appris à visualiser et "like" structures de données en étant enseigné que la mémoire de l'ordinateur, c'est comme une très longue liste. Les structures ont mise en page différente dans la mémoire. En visualisant les structures de la mémoire, il est devenu évident pour moi (et intéressant) comment ils fonctionnent. Sachant que la mise en page des données en mémoire est extrêmement important pour un programmeur comme aujourd'hui cesse de croître, les machines sont souvent interrompus par des accès à la mémoire. Une bonne mémoire-mise en page easen la charge de la CPU pour récupérer les données depuis la mémoire de telle sorte que le CPU n'ont pas à attendre que les données arrivent.

Des structures de données de la structure des données dans une mémoire. Considérer la mémoire comme une longue liste, comme une liste de courses, mais sans les entrées.

0...
1...
2...
3...
4...
5...
6...

Quand vous mettez les structures de la mémoire, ils ont essentiellement remplir ces emplacements dans la mémoire.

Une liste est très simple, il se remplit peu la mémoire-liste du haut et du bas:

0 Element 0
1 Element 1
2 Element 2
3 Element 3

Bien que parfois vous voulez changer l'élément 2 à autre chose, peut-être zéro. C'est la façon dont les listes de travail. Vous pouvez accéder aux données dans la structure par la connaissance de leur indice (dans ce cas, 0 .. 3).

Les piles sont différents. Vous ne pourrez accéder au "top" d'une pile en "poussant" un élément vers le haut, ou de la "poping" un élément à partir du haut de il. Poussant signifie l'ajout d'un autre élément et le vieux devient invisible. Poping implique la suppression de l'élément supérieur et celui-ci devient visible.

0   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
n   [ Hidden data ]
n+1 Element 4

Les listes chaînées sont différents. Une liste contient un pointeur (indice dans la mémoire de liste) pour les données, et un pointeur vers l'élément suivant:

0 Data: Memory index 0x00000100
1 Next: Memory index 6
2 
3 
4 
5 
6 Data: Memory index 104
7 Next: Memory index 8
...
100 Data pointed to from first member
101
102
103
104 Data pointed to from second member

La file d'attente est comme un plus puissant de la pile, vous avez accès à la fois la base et le sommet. Vous ne pouvez pousser les articles au top et vous ne pouvez pop des éléments à partir du bas.

0 (bottom) Element (ready to be popped)
1 [ Hidden data ]
2 [ Hidden data ]
3 [ Hidden data ]
.
.
.
n (top) (empty, ready to be pushed / be given data)

Par la visualisation de la mise en page de chaque structure de données, ils sont devenus beaucoup plus évident pour moi dans la façon dont ils nécessitent de la mémoire et comment ils fonctionnent vraiment ( également dans la mémoire). J'espère que mes exemples vous ont donné quelques brèves de départ de la connaissance pour vous à la base de vos futures études sur la. Un dernier exemple sur les structures de données, je vais vous donner un déséquilibré arbre binaire qui ont eu l'ordre suivant de l'élément d'insertion: 3, 2, 1, 10, 9, 8, 6, 5, 4, 7

L'arbre commence à l'adresse de mémoire de 100, depuis la mémoire de l'adresse 0 n'est pas valide et je vais donc l'utiliser comme une "pointeur".

100 Value: "3"
101 Left ptr: 103
102 Right ptr: 109

103 Value: "2"
104 Left ptr: 106
105 Right ptr: 0

106 Value: "1"
107 Left ptr: 0
108 Right ptr: 0

109 Value: "10"
110 Left ptr: 112
111 Right ptr: 0

112 Value: "9"
113 Left ptr: 115
114 Right ptr: 0

115 Value: "8"
116 Left ptr: 118
117 Right ptr: 0

118 Value: "6"
119 Left ptr: 121
120 Right ptr: 127

121 Value: "5"
122 Left ptr: 124
123 Right ptr: 0

124 Value: "4"
125 Left ptr: 0
126 Right ptr: 0

127 Value: "7"
128 Left ptr: 0
129 Right ptr: 0

Espérons que ça aide!

Answer 2

Voici ce qui m'a le plus aidé... Puisque vous êtes une personne visuelle, Google certains visualisé algorithmes de tri, d'arbre en arbre traversals, le hachage et la suite afin d'obtenir une idée générale de ce qu'il se passe. Après cela, essayez de faire un programme simple à l'aide de différentes structures et d'expérimenter avec différentes combinaisons d'entre eux-peut-être pour un exemple, vous pouvez faire une liste chaînée pour commencer, puis en faire une liste chaînée circulaire, puis en faire une liste doublement chaînée, puis en faire une circulaire doublement lié liste, et ainsi de suite...

Vous avez juste à expérimenter avec les structures, et comme vous le faites, vous allez commencer à voir ce que les structures de données sont appropriées pour les applications que vous serez en développement.

Voici quelques belles références pour vous.. Algorithmes de tri: http://www.sorting-algorithms.com/ Arbre traversals: http://nova.umuc.edu/~jarc/idsv/lesson1.html Graphique traversals: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html

---

Comme pour l'efficacité (Big O analyse), il viendra à vous plus ou moins naturellement, une fois que vous comprenez ce qui se passe à l'algorithmique niveau de chaque opération de la structure de données.

Une chose que mon université contraintes est le développement de notre propre mise en œuvre de structures de données (ce qui est en bas d'apprentissage) sans plonger dans le pré-établi des modèles C++ (de haut en bas de l'apprentissage). En le faisant à partir de zéro, vous avez vraiment compris les frais généraux inhérents à l'insertion, la suppression, la recherche (traversant), et l'accès aux données à partir d'une certaine structure, et qui contribuera à votre intuition lors de la conception d'un système à l'avenir.

Answer 3

Pratique, pratique, pratique.

Le premier conseil que j'ai pour vous est d'être le plus efficace possible en C++.

Structures de données et Programmation sont deux choses très différentes rubriques. Si vous vous trouvez aux prises avec la programmation, il est peu probable que vous serez en mesure de comprendre les structures de données.

Comment voulez-vous devenir compétent en C++? Pratique, pratique, pratique. Programme tout. Apprenez tout ce que vous pouvez sur le sujet. Écrire des dizaines de petits programmes. Tout ce que vous pouvez faire pour devenir à l'aise avec le C++.

Si vous maîtriser le C++, alors je vous assure que les structures de données va devenir plus facile. (Notez que je n'ai pas dis facile, je l'ai dit plus facile :) )

Answer 4

La clé de l'apprentissage des structures de données est de commencer avec quelque chose de petit, et de mettre à profit. Nous allons commencer avec un simple C struct:

struct Person {
  char name[100];
  int age;
};

Cette structure de données représente une personne. Vous devez assurez-vous de comprendre la structure simple des concepts tels que ceux-ci, et vous pouvez alors passer à des choses plus grandes.

Lorsque vous commencez à parler de structures de données comme les piles et les files d'attente, par exemple, essayez d'abord de comprendre conceptuellement ce que la structure de données est en train de faire. Par exemple, avec une pile, nous utilisons le principe, c'est-à-dire, Last In First Out. Avec une file d'attente, nous utilisons le principe FIFO (premier entré, premier sorti).

Et puis il y a celui qui voyages beaucoup de gens, la liste chaînée. Vous avez besoin de comprendre les pointeurs bien pour celui-ci, donc avant d'essayer de s'attaquer à des listes liées, commencer avec quelque chose de simple:

int* x;
int y = 10;
x = &y;

Vous devriez être en mesure de regarder le code et immédiatement savoir ce qu'elle fait. Si vous ne pouvez pas, alors vous n'êtes pas prêt à passer à plus avancée structures de données comme les listes chaînées.

Le point sur lequel je suis en train de faire est vous avez besoin pour obtenir les bases de froid, puis de construire sur ceux-ci. Il est également important de garder en place avec la classe avec beaucoup de soin, demandez à votre professeur ou tuteur si vous rencontrez des problèmes, et assurez-vous que vous êtes sur la bonne voie, chaque semaine, et ne pas rester à la traîne.

Des cours d'informatique sont un peu comme les classes de Mathématiques, chaque semaine, généralement s'appuie sur tout ce que vous avez appris de la précédente N semaines. Donc, si vous n'êtes pas la compréhension d'un concept clé, comme les pointeurs par exemple, alors vous allez avoir de grandes luttes pour le reste du semestre.

Answer 5

J'aime dcp réponse.

Le meilleur moyen pour envelopper votre tête autour de structures de données est d'écrire des mini-exemples. Même si vous copiez-les à partir de votre livre, si vous pouvez les obtenir à travailler et à compiler, et vous les avez tapés avec vos doigts, vous allez apprendre beaucoup de choses.

Comme vous l'avez lu votre livre, et après chaque cours, écrire la plus courte des programmes que vous pouvez créer et travailler avec (affichage, l'utilisation, etc.) la structure de données que vous venez d'apprendre sur.

Puis, quand vous avez à faire votre missions, vous vous en apprendrez encore plus que vous essayez et prenez votre mini exemples et branchez-le dans la résolution de la cession des problèmes.

Je pense que l'écriture le plus court / plus petit morceau de code de travail individuel pour les structures de données est très utile. Aussi, n'hésitez pas à copier le code (pour votre propre édification, et non pour votre tourné dans assignations).... Si vous copiez en tapant et de ne pas copier-coller, vous ne finissent par apprendre beaucoup, car il vous oblige à regarder chaque caractère du code.

---

Si l'ensemble des structures de données sembler "trop" pour envelopper votre tête autour de, alors commencez par écrire mini voici quelques exemples de composants de structures de Données. Rangez donc un titre de livre avec un pointeur. Ensuite stocker de nombreux titres de livres avec des pointeurs de pointeurs. Lire un titre de livre avec crochet de la notation et de l'arithmétique des pointeurs. Utiliser la récursivité dans les fonctions simples où il est clairement ce qui se passe..... Par exemple, la récursivité pour montrer la factorielle d'un nombre est plus simple pour vous envelopper la tête autour de la récursivité pour afficher un arbre binaire (à mon avis).....

Vous verrez ce que vos zones à problèmes sont, et d'essayer de les isoler pour que les petites et spécifique d'une chose que vous pouvez, puis d'écrire un programme qui traite de la problématique..... et puis construire.

Vos cours sont sur ensemble de structures de données... géant Cummulus cloud banques de la théorie.... donc, essentiellement, ils sont de haut en bas. Isoler les petits problèmes de la syntaxe et l'utilisation de mini-problèmes est de bas en haut. Si votre professeur vous aide à attaquer depuis le sommet, on attaque par le bas, par la pratique, et assez rapidement, il n'y a rien dans le milieu!