Создание циркулярного связанного списка в C#?
Я дам вам несколько советов, которые должны привести вас к решению:
- Рассчитать общую сумму в массиве за один проход. Давайте назовем это totalSum .
- Сделайте второй проход и вычислите partSum , до позиции, которую вы обработали (, но не включили ). Скажите, что это i со значением a [i] . Если
totalSum - partialSum - a[i] = partialSum, то позиция i является вашим ответом, а a [i] является его значением.
8 ответов
Поскольку большинство из этих ответов на самом деле не раскрывают сути вопроса, а лишь намерения, возможно, это поможет:
Что касается Я могу сказать, что единственная разница между связанным списком и круговым связным списком - это поведение итераторов при достижении конца или начала списка. Очень простой способ поддержать поведение кругового связного списка - написать метод расширения для LinkedListNode, который возвращает следующий узел в списке или первый, если такой узел не существует, и аналогично для получения предыдущего узла или последнего. один, если такой узел не существует. Для этого должен использоваться следующий код, хотя я его не тестировал:
static class CircularLinkedList {
public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
{
return current.Next ?? current.List.First;
}
public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current)
{
return current.Previous ?? current.List.Last;
}
}
Теперь вы можете просто вызвать myNode.NextOrFirst () вместо myNode.Next, и у вас будет все поведение кругового связанного списка. Вы по-прежнему можете выполнять удаление с постоянным временем и вставлять до и после всех узлов в списке и тому подобное.Если мне не хватает какого-то другого ключевого фрагмента кругового связного списка, дайте мне знать.
Вероятно, было бы плохой идеей наследовать класс BCL LinkedList. Этот класс предназначен для некруглого списка. Попытка сделать это круглым только вызовет у вас проблемы.
Тебе, вероятно, гораздо лучше писать свои собственные.
Я не думаю, что круговой связанный список является правильной структурой данных для списка контактов. Простой Список <> или Набор <> должен быть достаточным.
Есть ли у вас особые требования к использованию циклически связанного списка (т. Е. Домашней работы)? Если нет, я бы предложил использовать простой класс List<T> для хранения ваших контактов.
Циркулярные связанные списки часто реализуются с помощью массивов, который делает их очень быстро, и по их характеру не требуют динамического изменения размеров. Вам просто нужна быстрая проверка на чтении и индексах записи, чтобы видеть, упали ли они с конца и если так, обнулили его (или один, безотносительно).
Однако они обычно используются для вещей как входные буферы, где данные не имеют никакого действительного значения однажды чтение. Списки контактов имеют длительное значение, и новые контакты перезапишут более старые контакты, после того как список заполняется, который мог бы быть в порядке, если Вы не перезаписываете свою бабушку, которая оставляет Вас набором наличных в ее желании.
Я не думаю, что связанный список является самым эффективным способом пойти для кольцевого буфера (исходный вопрос).
Целью кольцевого буфера является скорость, и массив просто не может быть разбит для скорости в контексте кольцевого буфера. Даже если Вы сохраните указатель на свой последний объект связанного списка, к которому получают доступ, то массив все еще будет более эффективным. Списки имеют динамические возможности изменения размеров (наверху), которые являются ненужными для кольцевых буферов. Однако я думаю, что кольцевой буфер является, вероятно, не правильной структурой для приложения (список контактов), Вы упоминаете.
class CircularArray<T> : IEnumerator<T>
{
private readonly T[] array;
private int index = -1;
public T Current { get; private set; }
public CircularArray(T[] array)
{
Current = default(T);
this.array = array;
}
object IEnumerator.Current
{
get { return Current; }
}
public bool MoveNext()
{
if (++index >= array.Length)
index = 0;
Current = array[index];
return true;
}
public void Reset()
{
index = -1;
}
public void Dispose() { }
}
class Program
{
static void Main(string[] args)
{
int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };
IEnumerable<int> circularNumbers = numbers.AsCircular();
IEnumerable<int> firstFourNumbers = circularNumbers.Take(4); // 1 2 3 4
IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers
.Skip(4).Take(7); // 4 5 6 7 1 2 3
}
}
public static class CircularEnumerable
{
public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source)
{
if (source == null)
yield break; // be a gentleman
IEnumerator<T> enumerator = source.GetEnumerator();
iterateAllAndBackToStart:
while (enumerator.MoveNext())
yield return enumerator.Current;
enumerator.Reset();
if(!enumerator.MoveNext())
yield break;
else
yield return enumerator.Current;
goto iterateAllAndBackToStart;
}
}
Если вы хотите пойти дальше, сделайте CircularList и удерживайте тот же счетчик, чтобы пропустить Skip() при вращении, как в вашем примере.