2018-5-18
1.3.33 # 解答 # 动态数组这里要注意 first 不要小于零。
代码 # Deque 类 # /// <summary> /// 双端队列。 /// </summary> /// <typeparam name="TItem">队列中要存放的元素。</typeparam> public class Deque<TItem> : IEnumerable<TItem> { private class DoubleNode<T> { public T Item; public DoubleNode<T> Next; public DoubleNode<T> Prev; } private DoubleNode<TItem> _first; private DoubleNode<TItem> _last; private int _count; /// <summary> /// 默认构造函数，建立一个双端队列。 /// </summary> public Deque() { _first = null; _last = null; _count = 0; } /// <summary> /// 检查队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 返回队列中元素的数量。 /// </summary> /// <returns></returns> public int Size() { return _count; } /// <summary> /// 向左端添加一个元素。 /// </summary> /// <param name="item">要添加的元素。</param> public void PushLeft(TItem item) { var oldFirst = _first; _first = new DoubleNode<TItem> { Item = item, Prev = null, Next = oldFirst }; if (oldFirst == null) { _last = _first; } else { oldFirst.
...
2018-5-18
1.3.34 # 解答 # 在初始化迭代器的时候随机生成一个访问序列，
之后按照这个访问序列进行迭代即可。
代码 # RandomBag.cs # /// <summary> /// 随机背包。 /// </summary> /// <typeparam name="TItem">背包中要存放的元素。</typeparam> public class RandomBag<TItem> : IEnumerable<TItem> { private TItem[] _bag; private int _count; /// <summary> /// 建立一个随机背包。 /// </summary> public RandomBag() { _bag = new TItem[2]; _count = 0; } /// <summary> /// 检查背包是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 返回背包中元素的数量。 /// </summary> /// <returns></returns> public int Size() { return _count; } /// <summary> /// 向背包中添加一个元素。 /// </summary> /// <param name="item">要向背包中添加的元素。</param> public void Add(TItem item) { if (_count == _bag.
...
2018-5-18
1.3.35 # 解答 # 事实上只需要在普通队列的基础上稍作修改就可以了。
出队时先随机选择一个元素，之后让它和最开始的元素做交换，之后正常出队即可。
代码 # RandomQueue.cs # /// <summary> /// 随机队列。 /// </summary> /// <typeparam name="TItem">队列中要存放的元素。</typeparam> public class RandomQueue<TItem> { private TItem[] _queue; private int _count; /// <summary> /// 新建一个随机队列。 /// </summary> public RandomQueue() { _queue = new TItem[2]; _count = 0; } /// <summary> /// 判断队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 为队列重新分配内存空间。 /// </summary> /// <param name="capacity"></param> private void Resize(int capacity) { if (capacity <= 0) { throw new ArgumentException(); } var temp = new TItem[capacity]; for (var i = 0; i < _count; i++) { temp[i] = _queue[i]; } _queue = temp; } /// <summary> /// 向队列中添加一个元素。 /// </summary> /// <param name="item">要向队列中添加的元素。</param> public void Enqueue(TItem item) { if (_queue.
...
2018-5-18
1.3.36 # 解答 # 实现方法和 1.3.34 类似，初始化迭代器的时候同时初始化一个随机访问序列。
代码 # RandomQueue.cs # /// <summary> /// 随机队列。 /// </summary> /// <typeparam name="TItem">队列中要保存的元素。</typeparam> public class RandomQueue<TItem> : IEnumerable<TItem> { private TItem[] _queue; private int _count; /// <summary> /// 新建一个随机队列。 /// </summary> public RandomQueue() { _queue = new TItem[2]; _count = 0; } /// <summary> /// 判断队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 为队列重新分配内存空间。 /// </summary> /// <param name="capacity"></param> private void Resize(int capacity) { if (capacity <= 0) { throw new ArgumentException(); } var temp = new TItem[capacity]; for (var i = 0; i < _count; i++) { temp[i] = _queue[i]; } _queue = temp; } /// <summary> /// 向队列中添加一个元素。 /// </summary> /// <param name="item">要向队列中添加的元素。</param> public void Enqueue(TItem item) { if (_queue.
...
2018-5-18
1.3.37 # 解答 # 也就是约瑟夫问题，官方给出的 JAVA 版答案：Josephus.java。
报数时将一个人出队然后入队来模拟一个环。
报到 M 个后将那个人出队但不入队（删除）
随后继续循环。
代码 # var numOfPeople = 7; var callForDeath = 2; var queue = new Queue<int>(); for (var i = 0; i < numOfPeople; i++) { queue.Enqueue(i); } while (!queue.IsEmpty()) { for (var i = 0; i < callForDeath - 1; i++) { queue.Enqueue(queue.Dequeue()); } Console.Write(queue.Dequeue() + " "); } Console.WriteLine(); 另请参阅 # Generics 库
约瑟夫问题-维基百科——给出了约瑟夫问题的数学通解
2018-5-18
1.3.38 # 解答 # 这里采用“假删除”的方式，对要删除的元素不直接删除而是打上标记，这样就可以维持插入的顺序。
代码 # 数组实现 # /// <summary> /// 以一维数组为基础的队列。 /// </summary> /// <typeparam name="TItem">队列中要保存的元素。</typeparam> internal class ArrayBasedGeneralizeQueue<TItem> { private TItem[] _queue; private bool[] _isVisited; private int _count; private int _last; /// <summary> /// 建立一个队列。 /// </summary> public ArrayBasedGeneralizeQueue() { _queue = new TItem[2]; _isVisited = new bool[2]; _last = 0; _count = 0; } /// <summary> /// 检查队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 为队列重新分配空间。 /// </summary> /// <param name="capacity"></param> private void Resize(int capacity) { var temp = new TItem[capacity]; for (var i = 0; i < _count; i++) { temp[i] = _queue[i]; } _queue = temp; var t = new bool[capacity]; for (var i = 0; i < _count; i++) { t[i] = _isVisited[i]; } _isVisited = t; } /// <summary> /// 向队列中插入一个元素。 /// </summary> /// <param name="item">要插入队列的元素。</param> public void Insert(TItem item) { if (_count == _queue.
...
2018-5-18
1.3.39 # 解答 # 可以直接套用队列的实现方式，在满或空时抛出相应异常。
代码 # /// <summary> /// 环形缓冲区。 /// </summary> /// <typeparam name="TItem">缓冲区包含的元素类型。</typeparam> internal class RingBuffer<TItem> { private readonly TItem[] _buffer; private int _count; private int _first; // 读指针 private int _last; // 写指针 /// <summary> /// 建立一个缓冲区。 /// </summary> /// <param name="n">缓冲区的大小。</param> public RingBuffer(int n) { _buffer = new TItem[n]; _count = 0; _first = 0; _last = 0; } /// <summary> /// 检查缓冲区是否已满。 /// </summary> /// <returns></returns> public bool IsFull() { return _count == _buffer.
...
2018-5-18
1.3.40 # 解答 # 每次插入时都先搜索一遍链表，再判定相应动作。
代码 # /// <summary> /// 前移编码队列。 /// </summary> /// <typeparam name="TItem">需要前移编码的元素类型。</typeparam> internal class MoveToFront<TItem> { private class Node<T> { public T Item; public Node<T> Next; } private Node<TItem> _first; private int _count; /// <summary> /// 检查编码组是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _first == null; } /// <summary> /// 建立一个前移编码组。 /// </summary> public MoveToFront() { _first = null; _count = 0; } /// <summary> /// 找到相应元素的前驱结点。 /// </summary> /// <param name="item">要寻找的元素。</param> /// <returns></returns> private Node<TItem> Find(TItem item) { if (IsEmpty()) { return null; } var current = _first; while (current.
...
2018-5-21
1.3.41 # 解答 # 可以按照书上的提示出队再入队，也可以直接用迭代器访问一遍进行复制。
代码 # /// <summary> /// 复制构造函数。 /// </summary> /// <param name="r"></param> public Queue(Queue<Item> r) { foreach (Item i in r) { Enqueue(i); } }
2018-5-21
1.3.42 # 解答 # 直接把链栈的整个链表复制一份即可。
代码 # /// <summary> /// 复制构造函数。 /// </summary> /// <param name="s"></param> public Stack(Stack<Item> s) { if (s.first != null) { this.first = new Node<Item>(s.first); for (Node<Item> x = this.first; x.next != null; x = x.next) { x.next = new Node<Item>(x.next); } } this.count = s.count; }