Я закончил работу с этим кодом связанного списка?
https://stackoverflow.com/questions/248031
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Привет, я пытаюсь попрактиковаться в использовании связанных списков.
Я определил класс объекта под названием 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;
}
}
а затем 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;
}
}
и 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)
}
Мне нужно организовать эти данные, используя «тип структуры данных связанного списка».
Содержит все методы связанного списка, такие как Добавление узлов в список, как я узнал --> (Вставить), Удаление узлов из списка, как я узнал --> ((Удалить), Обход списков, которые я узнал - ->((PrintList),Нахождение узла в списке, как я узнал -->((Find , FindPrevious) проблема, которую я решаю самостоятельно, и я пытался искать в сети и читать больше из глупого C#, который была катастрофа.Я сделал слишком много, и мне так грустно, что я не знаю, как это завершить.
Я изо всех сил стараюсь использовать эти классы для написания исполняемой программы и ее тестирования.
Если вы не хотите помогать в завершении этой программы (надеюсь, что нет), по крайней мере, покажите мне несколько реальных примеров или идей, в конце концов, я компьютерный самообучающийся :-)
Решение
the head of the list.
( item1
Element: student1
Next ------------> ( item2
) Element: student2
Next ------------> ( item3
) Element: student3
Next: null
)
the tail of the list.
Прежде всего, чтобы вы могли написать класс StudentList, вам необходимо сначала написать клиентский код.Клиентский код — это код, который использует ваш список учащихся.Кроме того, не пишите по одной вещи и выбрасывайте ее.Вместо этого напишите целую кучу [тестовых] случаев, которые проверят разные способы, с помощью которых вы нуждаться для взаимодействия со StudentList.Напишите и исключительные случаи.Но не поддавайтесь искушению написать швейцарский нож такого класса, который делает все только потому, что может.Напишите минимальное количество кода, позволяющее выполнить работу.
То, как вам нужно использовать класс, во многом будет определять, как он будет построен.В этом суть TDD или Test Driven Design.
Ваша самая большая проблема, которую я вижу, заключается в том, что вы понятия не имеете, как вы хотите использовать этот класс.Итак, давайте сделаем это в первую очередь.
// 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);
}
Я добавляю студентов в список, а затем распечатываю их.
Мне не нужно, чтобы мой клиентский код мог видеть содержимое StudentList.Поэтому StudentList скрывает способ реализации связанного списка.Давайте напишем основы 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 довольно простой.Внутри он отслеживает первые или головные узлы.Очевидно, что отслеживание первого узла необходимо всегда.
Вы также можете задаться вопросом, почему ListNode объявлен внутри StudentList.Происходит следующее: класс ListNode доступен только классу StudentList.Это сделано потому, что StudentList не хочет раскрывать подробности своей внутренней реализации, поскольку он контролирует весь доступ к списку.StudentList никогда не раскрывает, как реализован список.Сокрытие реализации — важная концепция объектно-ориентированного программирования.
Если бы мы разрешили клиентскому коду напрямую манипулировать списком, не было бы смысла ставить StudentList на первое место.
Давайте продолжим и реализуем операцию 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;
}
Операция Add должна найти последний элемент в списке, а затем поместить в конец новый ListNode.Хоть и не очень эффективно.В настоящее время это O(N), и добавление будет замедляться по мере увеличения длины списка.
Давайте немного оптимизируем это для вставок и перепишем метод Add.Чтобы ускорить процесс добавления, все, что нам нужно сделать, это заставить StudentList отслеживать последний элемент в списке.
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;
}
Теперь, когда мы добавляем, мы не повторяем.Нам просто нужно отслеживать ссылки на голову и хвост.
Следующий:цикл foreach.StudentList — это коллекция, и, поскольку она является коллекцией, мы хотим выполнить ее перечисление и использовать методы C#. foreach.Компилятор C# не может выполнять итерации волшебным образом.Чтобы использовать цикл foreach, нам необходимо предоставить компилятору перечислитель, который он будет использовать, даже если код, который мы пишем, явно не использует перечислитель.
Однако сначала давайте еще раз вернемся к тому, как мы перебираем связанный список.
// don't add this to StudentList
void IterateOverList( ListNode current )
{
while (current != null)
{
current = current.Next;
}
}
Хорошо.Итак, давайте подключимся к циклу foreach C# и вернем перечислитель.Для этого мы изменим StudentList, чтобы реализовать IEnumerable.Это уже немного продвинуто, но вы сможете понять, что происходит.
// 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
}
Вы сможете обнаружить там итерацию связанного списка.Не поддавайтесь yield ключевое слово.Все, что делает выход, — это возвращает текущего студента обратно в цикл foreach.Счетчик перестает возвращать студентов, когда достигает конца связанного списка.
Вот и все!Код работает так, как мы хотим.
* Это далеко не единственный способ реализации списка.Я решил поместить логику списка в StudentList и оставить ListNode очень простым.Но код делает только то, что нужно моему самому первому модульному тесту, и не более того.Вы можете сделать больше оптимизаций и есть другие способы построения списка.
Идти вперед:Что вам нужно сделать, так это сначала создать [юнит] тесты для того, что должен делать ваш код, а затем добавить необходимую реализацию.
* к вашему сведению, я также переписал класс Student.Плохое имя и странный регистр с точки зрения C#, не говоря уже о том, что предоставленный вами код не компилируется.Я предпочитаю _ в качестве лидера для частных переменных-членов.Некоторым людям это не нравится, однако вы новичок в этом, поэтому я оставлю их здесь, потому что их легко заметить.
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; } }
}
- проверить параметры
- обратите внимание на различный регистр свойств, классов и переменных.
- скрыть конструктор по умолчанию.Почему я хочу создавать учеников без реальных данных?
- предоставить некоторые свойства, доступные только для чтения.
- Этот класс является неизменяемым, как написано (т.е.как только вы создадите ученика, вы не сможете его изменить).
Другие советы
Я сделаю один для тебя! Вам нужно нарисовать диаграммы с каждым узлом в виде блока и выяснить, какой код нужно использовать для изменения списка для каждой операции. Посмотрите это для вдохновения:
http://en.wikipedia.org/wiki/Linked_list
Диаграммы там не показывают класс основного списка в виде поля, которое вы должны иметь, с двумя выходящими из него стрелками для заголовка и хвоста.
Нарисуйте несколько диаграмм для двух случаев в методе Insert, чтобы понять, что происходит. Одна диаграмма для случая, когда в списке ничего нет и заголовок равен нулю, а другая диаграмма для случая, когда в списке уже что-то есть. Затем отработать другие операции.
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;
}
}
}
Вам не хватает следующих операций:
Добавлять:
установите ссылку хвостового узла в качестве добавленного узла, а хвост — в качестве нового узла.
Удалить/Удалить:
немного сложно, если у вас нет двусвязного списка, но с односвязным списком пройдите по списку от головы, пока не найдете нужный узел, сохраняя предыдущий узел в отдельной переменной.Когда вы найдете удаляемый узел, установите ссылку предыдущего узла на ссылку этого узла.Оптимизация может заключаться в проверке того, что это не та ссылка, которую вы ищете.В качестве альтернативы сделайте его двусвязным списком, и вам не нужно будет отслеживать предыдущий узел.
Находить:
Перемещайтесь по списку от узла к узлу, пока не найдете тот, который ищете.
прочитай это статья в Википедии для получения дополнительной информации.
Посмотрите это ...
Хотя, если вы действительно хотите научиться делать это, вы должны написать это по крайней мере на c или c ++, тогда вы будете делать что-то полезное ...
На самом деле я не вижу причины писать свой собственный связанный список в C # (кроме изучения того, как он работает), поскольку .NET уже содержит универсальный класс LinkedList.
Понятие связанных списков не очень сложно для понимания. Реализация с другой стороны ... может быть немного сложнее.
Я также понимаю ваше разочарование в связи с попытками найти в Интернете информацию об этом. Я был в вашей лодке раньше, и все меняется от сайта к сайту. Возможно, вы действительно захотите инвестировать в книгу по структурам данных, так как я думаю, что информация, которую вы найдете, будет намного более понятной и полезной, чем большая часть информации, которую вы найдете в дикой природе.
Реализация связанного списка в Java / C # будет намного проще, если вы никогда раньше не использовали ll. Однако, как только вы почувствуете это лучше, вы получите гораздо лучшее понимание для всех, создав их на C / C ++.
Из приведенного выше кода вам будет лучше думать о каждом S_Node как о обычном узле, который содержит объект Student, а не думать о нем как об узле Student (надеюсь, это имеет смысл). Те же правила применяются для вашего класса S_LinkedList. Связанный список - это режим списка узлов. Эти узлы содержат объекты Student.
Надеюсь, это поможет.
Попробуйте это в классе ученика.
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;
}
}
Ваш вопрос, насколько я понимаю, слишком расплывчатый. Я бы начал с поиска в «связанных списках» или поиска книги о «структурах данных». Когда вы столкнетесь с конкретной проблемой, задайте ее здесь, и я уверен, что кто-то вам поможет.
