1.3.23 # 解答 # 由于先后问题，y 在第一句代码执行完毕之后无法访问，t 的 next 会指向自己。 代码 # // x.next = t x 的下一个是 t // t.next = x.next t 的下一个和 x 的下一个相同（也就是 t） // 于是 t.next = t, 遍历会出现死循环。 var first = new Node<string>(); var second = new Node<string>(); var third = new Node<string>(); var fourth = new Node<string>(); first.Item = "first"; second.Item = "second"; third.Item = "third"; fourth.Item = "fourth"; first.Next = second; second.Next = third; third. ...
1.3.24 # 解答 # 直接把该节点的 next 域设为 null，后续元素就会因无法访问而被清理掉。 代码 # var first = new Node<string>(); var second = new Node<string>(); var third = new Node<string>(); var fourth = new Node<string>(); first.Item = "first"; second.Item = "second"; third.Item = "third"; fourth.Item = "fourth"; first.Next = second; second.Next = third; third.Next = fourth; fourth.Next = null; var current = first; while (current != null) { Console.Write(current.Item + " "); current = current. ...
1.3.25 # 解答 # 见练习 1.3.22，加入一些对边界情况的处理即可。 代码 # var first = new Node<string>(); var second = new Node<string>(); var third = new Node<string>(); first.Item = "first"; second.Item = "second"; third.Item = "third"; first.Next = second; second.Next = null; var current = first; while (current != null) { Console.Write(current.Item + " "); current = current.Next; } InsertAfter(second, third); Console.WriteLine(); current = first; while (current != null) { Console.Write(current.Item + " "); current = current. ...
1.3.26 # 解答 # 之前已经写过了删除指定结点（习题 1.3.20）和查找指定结点（习题 1.3.21），结合使用即可。 代码 # var link = new LinkedList<string>(); link.Insert("first", 0); link.Insert("second", 1); link.Insert("third", 2); link.Insert("third", 3); link.Insert("third", 4); Console.WriteLine(link); Remove(link, "third"); Console.WriteLine(link); static void Remove(LinkedList<string> link, string key) { for (var i = 0; i < link.Size(); i++) { if (link.Find(i) == key) { link.Delete(i); i--; } } } 另请参阅 # Generics 库
1.3.27 # 解答 # 遍历一遍即可。 代码 # var first = new Node<int>(); var second = new Node<int>(); var third = new Node<int>(); var fourth = new Node<int>(); first.Item = 1; second.Item = 2; third.Item = 3; fourth.Item = 4; first.Next = second; second.Next = third; third.Next = fourth; fourth.Next = null; Console.WriteLine("Max:" + Max(first)); static int Max(Node<int> first) { var max = 0; var current = first; while (current ! ...
1.3.28 # 解答 # 其实链表本身就是一个递归结构，链表的定义可以用递归的方式表示： 链表 = 头结点A + 链表B = 头结点A + 头结点B + 链表C…… 所以 Max() 可以这么写： Max(Node<Item> Cur, int nowmax) 如果 Cur 为空，则直接返回 nowmax。 否则检查 Cur 结点的值是否大于目前找到的最大值 nowmax。 如果不大于，继续查找下一个结点，返回 Max(Cur.next, nowmax) 否则，把 nowmax 修改为当前结点的值，继续查找，返回 Max(Cur.next, Cur.item) 代码 # var first = new Node<int>(); var second = new Node<int>(); var third = new Node<int>(); var fourth = new Node<int>(); first.Item = 1; second.Item = 2; third.Item = 3; fourth. ...
1.3.29 # 解答 # 其实就是一个长这样的链表： 显然说 first 和最后一个节点的指针重复了，所以我们只需要保留 last 的指针就行了。 入队（注意顺序） 出队 代码 # Queue.cs # /// <summary> /// 队列类。 /// </summary> /// <typeparam name="TItem">队列中存放的元素。</typeparam> public class Queue<TItem> : IEnumerable<TItem> { private Node<TItem> _last; private int _count; /// <summary> /// 默认构造函数。 /// </summary> public Queue() { _last = null; _count = 0; } /// <summary> /// 检查队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _last == null; } /// <summary> /// 返回队列中元素的数量。 /// </summary> /// <returns></returns> public int Size() { return _count; } /// <summary> /// 返回队列中的第一个元素（但不让它出队）。 /// </summary> /// <returns></returns> public TItem Peek() { if (IsEmpty()) throw new InvalidOperationException("Queue underflow"); return _last. ...
1.3.30 # 解答 # 书中给出了代码，这里说一下递归的实现。 如果说一个链表除了第一个结点剩下的都已经反转了，那么我们就只要把该结点插入到最后就行了（也就是原先的第二个结点之后）。 像这样： 代码 # var first = new Node<string>(); var second = new Node<string>(); var third = new Node<string>(); var fourth = new Node<string>(); first.Item = "first"; second.Item = "second"; third.Item = "third"; fourth.Item = "fourth"; first.Next = second; second.Next = third; third.Next = fourth; fourth.Next = null; var current = first; while (current != null) { Console.Write(current.Item + " "); current = current.Next; } first = Reverse(first); Console. ...
1.3.31 # 解答 # 双向链表的插入有顺序，务必当心。 双向链表长这样（似乎有一种画法是把空指针画成“接地”的样子）： 删除中间那个： 再插回去： 原则是不要让有用的结点变得无法访问。 代码 # DoubleNode<> # /// <summary> /// 双向链表。 /// </summary> /// <typeparam name="TItem">链表中要存放的元素。</typeparam> public class DoubleLinkList<TItem> : IEnumerable<TItem> { private class DoubleNode<T> { public T Item; public DoubleNode<T> Prev; public DoubleNode<T> Next; } private DoubleNode<TItem> _first; private DoubleNode<TItem> _last; private int _count; /// <summary> /// 建立一条双向链表。 /// </summary> public DoubleLinkList() { _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 InsertFront(TItem item) { var node = new DoubleNode<TItem> { Item = item, Next = _first, Prev = null }; if (_first ! ...
1.3.32 # 解答 # 在队列的基础上增加一个在队首插入元素的方法即可。 代码 # Steque.cs # /// <summary> /// Steque。 /// </summary> /// <typeparam name="TItem">Steque 中要存放的元素。</typeparam> public class Steque<TItem> : IEnumerable<TItem> { private Node<TItem> _first; private Node<TItem> _last; private int _count; private class Node<T> { public T Item; public Node<T> Next; } /// <summary> /// 默认构造函数。 /// </summary> public Steque() { _first = 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 Push(TItem item) { var oldFirst = _first; _first = new Node<TItem>(); _first. ...