c# - simple - ¿Ya terminé con este código de la lista enlazada?

listas simples estructura de datos

Question

Hola, estoy intentando practicar con las listas enlazadas.

Definí una clase de objeto llamada Student :

public class Student
{
protected string Student_Name;
protected int Student_ID;
protected int Student_Mark;
protected char Student_Grade;
public Student() // default Constructor
{
Student_Name = " ";
Student_ID = 0;
Student_Mark = 0;
Student_Grade = '' '';
}
public Student(string Sname, int Sid, int Smark, char Sgrade) // Constructor
{
int len = sname.Length;
Student_Name = sname.Substring(0, len);
//Student_Name = sname.Substring(0, sname.Length);
Student_ID = Sid;
Student_Mark = Smark;
Student_Grade = Sgrade;
}
}

y luego una clase Node :

public class S_Node
{
public Student Element;
public S_Node Link;
public S_Node()
{
Element = new Student();
Link = null;
}
public Node(Student theElement)
{
Element = theElement;
Link = null;
}
}

y la LinkedList :

public class S_LinkedList
{
protected S_Node header;
protected S_Node tail;
public S_LinkedList()
{
header = new S_Node();
Tail = new S_Node();
header.Link = Tail;
}
// METHODS which i don''t know how to do it (never use linkedlist before)
}

Necesito organizar estos datos usando un "tipo de estructura de datos de lista enlazada".

Contiene todos los métodos de lista enlazada como Agregar nodos a la lista como he aprendido -> (Insertar), Eliminando nodos de la lista, como he aprendido -> ((Eliminar), Atravesando las listas que he aprendido - -> ((PrintList), Encontrando un nodo en la lista como he aprendido -> ((Find, FindPrevious) el problema que soy autoaprendizaje y he intentado buscar en la red y leer más del estúpido C # que fue un desastre. He hecho demasiado que estoy tan triste que no sé cómo completarlo.

Estoy intentando usar estas clases para escribir un programa ejecutable y probarlo.

Si no quieres ayudar a completar este programa (espero que no), al menos muéstrame algunos ejemplos o ideas reales, después de todo soy un geek autodidacta :-)

Answer 1

¡Haré uno para ti! Debe dibujar diagramas con cada nodo como un cuadro y determinar qué código debe usar para cambiar la lista de cada operación. Mira esto para inspirarte:

http://en.wikipedia.org/wiki/Linked_list

Los diagramas allí no muestran la clase de lista principal como un cuadro, que debería tener, con dos flechas que salen de él para el encabezado y la cola.

Dibuja algunos diagramas para los dos casos en el método Insert para averiguar qué está pasando. Un diagrama para cuando no hay nada en la lista y el encabezado es nulo, y otro diagrama para cuando ya hay algo en la lista. Luego, desde allí, resuelve las otras operaciones.

public class S_LinkedList {
protected S_Node header = null;
protected S_Node tail = null;
public S_LinkedList()
{
}
// METHODS which i don''t know how to do it (never use linkedlist before)
void Insert(Student s)
{
if( header == null )
{
header = new S_Node(s);
tail = header;
}
else
{
tail.Link = new S_Node(s);
tail = tail.Link;
}
}
}

Answer 2

El concepto de listas vinculadas no es muy difícil de entender. Implementación por otro lado ... puede ser un poco complicado.

También puedo entender su frustración de tratar de encontrar información en la web al respecto. He estado en su barco antes y todo varía de un sitio a otro. Es posible que desee invertir en un libro de estructuras de datos ya que creo que la información que encuentre será mucho más clara y útil que la mayoría de la información que encuentre en la naturaleza.

Implementar una lista enlazada en Java / C # será mucho más fácil si nunca antes ha utilizado ll''s. Sin embargo, una vez que lo sientas mejor obtendrás una mejor comprensión de los lls al crearlos en C / C ++.

A partir de su código anterior, será mejor que piense en cada S_Node como un nodo regular que contiene un objeto de Estudiante en lugar de pensarlo como un nodo de Estudiante (la esperanza tiene sentido). Se aplican las mismas reglas para su clase S_LinkedList. Una lista vinculada es un modo de lista de nodos. Estos nodos contienen objetos Student.

Espero que esto ayude.

Answer 3

En realidad, no veo una razón para escribir su propia lista vinculada en C # (aparte de aprender cómo funciona) ya que .NET ya contiene la clase genérica LinkedList.

Answer 4

Las operaciones que te faltan son:

Añadir:

establece el enlace del nodo de la cola para que sea el nodo agregado y configura la cola para que sea el nuevo nodo.

Eliminar / Eliminar:

es un poco complicado si no tienes una lista doblemente vinculada, pero con una lista individualmente enlazada ve a través de la lista desde la cabeza hasta que encuentres el nodo que necesitas manteniendo el nodo anterior en una variable separada. Cuando encuentre el nodo que está eliminando, establezca el enlace del nodo anterior a ese enlace de nodos. Una optimización podría ser verificar que no sea el enlace que está buscando. Alternativamente, conviértalo en una lista doblemente enlazada y no necesita hacer un seguimiento del nodo anterior.

Encontrar:

Recorre la lista de nodo a nodo hasta que encuentres la que estás buscando.

lea este artículo de Wikipedia para más información.

Answer 5

Mira esto ...

Aunque si realmente quieres aprender a hacer esto, debes escribirlo en c o c ++ al menos entonces estarías haciendo algo útil ...

Answer 6

Tu pregunta, mientras la leo, es demasiado vaga. Comenzaría buscando en Google ''listas enlazadas'' o leyendo un libro sobre ''estructuras de datos''. Cuando te encuentres con un problema específico, pregúntalo aquí, y estoy seguro de que alguien te ayudará.

Answer 7

Pruebe esto como su clase de Estudiante.

public class Student
{
protected string Name;
protected int ID;
protected int Mark;
protected char Grade;
public Student() // default Constructor
{
Name = "";
ID = 0;
Mark = 0;
Grade = '''';
}
public Student(string Name, int ID, int Mark, char Grade) // Constructor
{
this.Name = Name;
this.ID = ID;
this.Mark = Mark;
this.Grade = Grade;
}
}

Answer 8

the head of the list. ( item1 Element: student1 Next ------------> ( item2 ) Element: student2 Next ------------> ( item3 ) Element: student3 Next: null ) the tail of the list.

En primer lugar, para que pueda escribir la clase StudentList, primero debe escribir el código del cliente. El código del cliente es el código que usa su lista de estudiantes. Además, no solo escriba una cosa a la vez y tírela. En su lugar, escriba un montón de casos [de prueba] que ejerciten las diferentes formas en que necesita interactuar con la Lista de Estudiantes. Escribe casos excepcionales también. Pero no tengas la tentación de escribir una navaja suiza de una clase que hace todo solo porque puede. Escriba la cantidad mínima de código que hace el trabajo.

La forma en que necesite usar la clase dictará en gran medida cómo se construye la clase. Esta es la esencia de TDD o Test Driven Design.

El mayor problema que puedo ver es que no tienes idea de cómo quieres usar la clase. Así que vamos a hacer eso primero.

// create a list of students and print them back out.
StudentList list = new StudentList();
list.Add( new Student("Bob", 1234, 2, ''A'') );
list.Add( new Student("Mary", 2345, 4, ''C'') );
foreach( Student student in list)
{
Console.WriteLine(student.Name);
}

Agrego a los estudiantes a la lista, y luego los imprimo.

No necesito que mi código de cliente aparezca dentro de StudentList. Por lo tanto, StudentList oculta cómo implementa la lista vinculada. Vamos a escribir los conceptos básicos de StudentList.

public class StudentList
{
private ListNode _firstElement; // always need to keep track of the head.
private class ListNode
{
public Student Element { get; set; }
public ListNode Next { get; set; }
}
public void Add(Student student) { /* TODO */ }
}

StudentList es bastante básico. Internamente realiza un seguimiento de los nodos primero o principal. Sin embargo, siempre se requiere hacer un seguimiento del primer nodo.

También podría preguntarse por qué se declara ListNode dentro de StudentList. Lo que sucede es que la clase ListNode solo es accesible para la clase StudentList. Esto se hace porque StudentList no quiere dar los detalles a su implementación interna porque controla todos los accesos a la lista. StudentList nunca revela cómo se implementa la lista. El ocultamiento de la implementación es un concepto importante de OO.

Si permitimos que el código del cliente manipule directamente la lista, no tendría sentido que StudentList sea el primer lugar.

Avancemos e implementemos la operación Add ().

public void Add(Student student)
{
if (student == null)
throw new ArgumentNullException("student");
// create the new element
ListNode insert = new ListNode() { Element = student };
if( _firstElement == null )
{
_firstElement = insert;
return;
}
ListNode current = _firstElement;
while (current.Next != null)
{
current = current.Next;
}
current.Next = insert;
}

La operación Agregar tiene que encontrar el último elemento en la lista y luego coloca el nuevo ListNode al final. Aunque no es terriblemente eficiente. Actualmente es O (N) y Adding se volverá más lento a medida que la lista se alargue.

Permite optimizar esto un poco para inserciones y reescribir el método Add. Para hacer que Add sea más rápido, todo lo que necesitamos hacer es que StudentList haga un seguimiento del último elemento de la lista.

private ListNode _lastElement; // keep track of the last element: Adding is O(1) instead of O(n)
public void Add(Student student)
{
if( student == null )
throw new ArgumentNullException("student");
// create the new element
ListNode insert = new ListNode() { Element = student };
if (_firstElement == null)
{
_firstElement = insert;
_lastElement = insert;
return;
}
// fix up Next reference
ListNode last = _lastElement;
last.Next = insert;
_lastElement = insert;
}

Ahora, cuando agregamos, no iteramos. Solo necesitamos hacer un seguimiento de las referencias de cabeza y cola.

Siguiente: el ciclo foreach. StudentList es una colección, y al ser una colección, queremos enumerarla y usar el foreach C #. El compilador de C # no puede iterar mágicamente. Para usar el ciclo foreach Necesitamos proporcionarle al compilador un enumerador para que lo use, incluso si el código que escribimos no aparece explícitamente para usar el enumerador.

Antes que nada, revisemos cómo iteramos sobre una lista enlazada.

// don''t add this to StudentList
void IterateOverList( ListNode current )
{
while (current != null)
{
current = current.Next;
}
}

Bueno. así que enganchémonos en el ciclo foreach de C # y devolvamos un enumerador. Para hacerlo, modificamos StudentList para implementar IEnumerable. Esto se está haciendo un poco más avanzado, pero deberías ser capaz de descubrir qué está pasando.

// StudentList now implements IEnumerable<Student>
public class StudentList : IEnumerable<Student>
{
// previous code omitted
#region IEnumerable<Student> Members
public IEnumerator<Student> GetEnumerator()
{
ListNode current = _firstElement;
while (current != null)
{
yield return current.Element;
current = current.Next;
}
}
#endregion
#region IEnumerable Members
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
}

Debería poder detectar la iteración de la lista enlazada allí. No te dejes caer por la palabra clave yield . Todo lo que se está haciendo es devolver al alumno actual al ciclo foreach. El enumarator deja de devolver alumnos cuando llega al final de la lista vinculada.

¡Y eso es! El código funciona de la manera que queremos.

* Esta no es, de ninguna manera, la única forma de implementar la lista. Opté por poner la lógica de la lista en la Lista del alumno y mantener ListNode muy básico. Pero el código solo hace lo que necesita mi primera prueba unitaria y nada más. Hay más optimizaciones que podría hacer, y hay otras formas de construir la lista.

En el futuro: lo que debe hacer primero es crear pruebas [unit] para lo que su código necesita hacer, luego agregue la implementación que necesita.

* fyi También reescribí la clase de Estudiante. El mal nombre y la carcasa extraña de un perseguidor de C #, sin mencionar el código que proporcionó, no se compila. Prefiero el _ como líder a las variables de miembros privados. A algunas personas no les gusta eso, sin embargo eres nuevo en esto, así que los dejaré porque son fáciles de detectar.

public class Student
{
private string _name;
private int _id;
private int _mark;
private char _letterGrade;
private Student() // hide default Constructor
{ }
public Student(string name, int id, int mark, char letterGrade) // Constructor
{
if( string.IsNullOrEmpty(name) )
throw new ArgumentNullException("name");
if( id <= 0 )
throw new ArgumentOutOfRangeException("id");
_name = name;
_id = id;
_mark = mark;
_letterGrade = letterGrade;
}
// read-only properties - compressed to 1 line for SO answer.
public string Name { get { return _name; } }
public int Id { get { return _id; } }
public int Mark { get { return _mark; } }
public char LetterGrade { get { return _letterGrade; } }
}

• verificar parámetros
• preste atención a la diferente carcasa de propiedades, clases y variables.
• ocultar el constructor predeterminado. ¿Por qué quiero crear estudiantes sin datos reales?
• proporcionar algunas propiedades de solo lectura.
  • Esta clase es inmutable como está escrita (es decir, una vez que creas un alumno, no puedes cambiarlo).