[教程]掌握C#数据结构，挑战50道实战练习题

1. 线性表

题目描述： 实现一个线性表，支持插入、删除、查找等基本操作。

代码示例：

public class LinearList
{ private int[] array; private int size; public LinearList(int capacity) { array = new int[capacity]; size = 0; } public void Insert(int index, int value) { if (index < 0 || index > size) { throw new IndexOutOfRangeException("Index out of range."); } for (int i = size; i > index; i--) { array[i] = array[i - 1]; } array[index] = value; size++; } public void Delete(int index) { if (index < 0 || index >= size) { throw new IndexOutOfRangeException("Index out of range."); } for (int i = index; i < size - 1; i++) { array[i] = array[i + 1]; } size--; } public int Find(int value) { for (int i = 0; i < size; i++) { if (array[i] == value) { return i; } } return -1; }
}

2. 链表

题目描述： 实现一个单链表，支持插入、删除、查找等基本操作。

代码示例：

public class ListNode
{ public int Val { get; set; } public ListNode Next { get; set; } public ListNode(int val = 0, ListNode next = null) { Val = val; Next = next; }
}
public class LinkedList
{ private ListNode head; public LinkedList() { head = null; } public void Insert(int index, int value) { ListNode newNode = new ListNode(value); if (index == 0) { newNode.Next = head; head = newNode; } else { ListNode current = head; for (int i = 0; i < index - 1 && current != null; i++) { current = current.Next; } if (current == null) { throw new IndexOutOfRangeException("Index out of range."); } newNode.Next = current.Next; current.Next = newNode; } } public void Delete(int index) { if (head == null) { throw new InvalidOperationException("List is empty."); } if (index == 0) { head = head.Next; } else { ListNode current = head; for (int i = 0; i < index - 1 && current != null; i++) { current = current.Next; } if (current == null || current.Next == null) { throw new IndexOutOfRangeException("Index out of range."); } current.Next = current.Next.Next; } } public int Find(int value) { ListNode current = head; while (current != null) { if (current.Val == value) { return current.Val; } current = current.Next; } return -1; }
}

3. 栈

题目描述： 实现一个栈，支持入栈、出栈、判断是否为空等操作。

代码示例：

public class Stack
{ private T[] array; private int size; public Stack(int capacity) { array = new T[capacity]; size = 0; } public void Push(T value) { if (size == array.Length) { throw new InvalidOperationException("Stack is full."); } array[size++] = value; } public T Pop() { if (size == 0) { throw new InvalidOperationException("Stack is empty."); } T value = array[--size]; array[size] = default(T); return value; } public bool IsEmpty() { return size == 0; }
}

4. 队列

题目描述： 实现一个队列，支持入队、出队、判断是否为空等操作。

代码示例：

public class Queue
{ private T[] array; private int front; private int rear; private int size; public Queue(int capacity) { array = new T[capacity]; front = 0; rear = 0; size = 0; } public void Enqueue(T value) { if (size == array.Length) { throw new InvalidOperationException("Queue is full."); } array[rear] = value; rear = (rear + 1) % array.Length; size++; } public T Dequeue() { if (size == 0) { throw new InvalidOperationException("Queue is empty."); } T value = array[front]; array[front] = default(T); front = (front + 1) % array.Length; size--; return value; } public bool IsEmpty() { return size == 0; }
}

5. 链队列

题目描述： 实现一个链队列，支持入队、出队、判断是否为空等操作。

代码示例：

public class LinkedListQueue
{ private ListNode head; private ListNode tail; public LinkedListQueue() { head = null; tail = null; } public void Enqueue(T value) { ListNode newNode = new ListNode(value); if (tail == null) { head = newNode; tail = newNode; } else { tail.Next = newNode; tail = newNode; } } public T Dequeue() { if (head == null) { throw new InvalidOperationException("Queue is empty."); } T value = head.Val; head = head.Next; if (head == null) { tail = null; } return value; } public bool IsEmpty() { return head == null; }
}

6. 双端队列

题目描述： 实现一个双端队列，支持在两端入队、出队等操作。

代码示例：

public class Deque
{ private T[] array; private int front; private int rear; private int size; public Deque(int capacity) { array = new T[capacity]; front = 0; rear = 0; size = 0; } public void EnqueueFront(T value) { if (size == array.Length) { throw new InvalidOperationException("Deque is full."); } array[front] = value; front = (front - 1 + array.Length) % array.Length; size++; } public void EnqueueRear(T value) { if (size == array.Length) { throw new InvalidOperationException("Deque is full."); } array[rear] = value; rear = (rear + 1) % array.Length; size++; } public T DequeueFront() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = array[front]; array[front] = default(T); front = (front + 1) % array.Length; size--; return value; } public T DequeueRear() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = array[rear]; array[rear] = default(T); rear = (rear - 1 + array.Length) % array.Length; size--; return value; } public bool IsEmpty() { return size == 0; }
}

7. 顺序栈

题目描述： 实现一个顺序栈，支持入栈、出栈、判断是否为空等操作。

代码示例：

public class SequentialStack
{ private T[] array; private int top; public SequentialStack(int capacity) { array = new T[capacity]; top = -1; } public void Push(T value) { if (top == array.Length - 1) { throw new InvalidOperationException("Stack is full."); } array[++top] = value; } public T Pop() { if (top == -1) { throw new InvalidOperationException("Stack is empty."); } T value = array[top--]; array[top] = default(T); return value; } public bool IsEmpty() { return top == -1; }
}

8. 顺序队列

题目描述： 实现一个顺序队列，支持入队、出队、判断是否为空等操作。

代码示例：

public class SequentialQueue
{ private T[] array; private int front; private int rear; private int size; public SequentialQueue(int capacity) { array = new T[capacity]; front = 0; rear = 0; size = 0; } public void Enqueue(T value) { if (size == array.Length) { throw new InvalidOperationException("Queue is full."); } array[rear] = value; rear = (rear + 1) % array.Length; size++; } public T Dequeue() { if (size == 0) { throw new InvalidOperationException("Queue is empty."); } T value = array[front]; array[front] = default(T); front = (front + 1) % array.Length; size--; return value; } public bool IsEmpty() { return size == 0; }
}

9. 顺序双端队列

题目描述： 实现一个顺序双端队列，支持在两端入队、出队等操作。

代码示例：

public class SequentialDeque
{ private T[] array; private int front; private int rear; private int size; public SequentialDeque(int capacity) { array = new T[capacity]; front = 0; rear = 0; size = 0; } public void EnqueueFront(T value) { if (size == array.Length) { throw new InvalidOperationException("Deque is full."); } array[front] = value; front = (front - 1 + array.Length) % array.Length; size++; } public void EnqueueRear(T value) { if (size == array.Length) { throw new InvalidOperationException("Deque is full."); } array[rear] = value; rear = (rear + 1) % array.Length; size++; } public T DequeueFront() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = array[front]; array[front] = default(T); front = (front + 1) % array.Length; size--; return value; } public T DequeueRear() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = array[rear]; array[rear] = default(T); rear = (rear - 1 + array.Length) % array.Length; size--; return value; } public bool IsEmpty() { return size == 0; }
}

10. 循环队列

题目描述： 实现一个循环队列，支持入队、出队、判断是否为空等操作。

代码示例：

public class CircularQueue
{ private T[] array; private int front; private int rear; private int size; public CircularQueue(int capacity) { array = new T[capacity]; front = 0; rear = 0; size = 0; } public void Enqueue(T value) { if (size == array.Length) { throw new InvalidOperationException("Queue is full."); } array[rear] = value; rear = (rear + 1) % array.Length; size++; } public T Dequeue() { if (size == 0) { throw new InvalidOperationException("Queue is empty."); } T value = array[front]; array[front] = default(T); front = (front + 1) % array.Length; size--; return value; } public bool IsEmpty() { return size == 0; }
}

11. 双端循环队列

题目描述： 实现一个双端循环队列，支持在两端入队、出队等操作。

代码示例：

public class CircularDeque
{ private T[] array; private int front; private int rear; private int size; public CircularDeque(int capacity) { array = new T[capacity]; front = 0; rear = 0; size = 0; } public void EnqueueFront(T value) { if (size == array.Length) { throw new InvalidOperationException("Deque is full."); } array[front] = value; front = (front - 1 + array.Length) % array.Length; size++; } public void EnqueueRear(T value) { if (size == array.Length) { throw new InvalidOperationException("Deque is full."); } array[rear] = value; rear = (rear + 1) % array.Length; size++; } public T DequeueFront() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = array[front]; array[front] = default(T); front = (front + 1) % array.Length; size--; return value; } public T DequeueRear() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = array[rear]; array[rear] = default(T); rear = (rear - 1 + array.Length) % array.Length; size--; return value; } public bool IsEmpty() { return size == 0; }
}

12. 双端循环队列（链表实现）

题目描述： 使用链表实现一个双端循环队列，支持在两端入队、出队等操作。

代码示例：

public class CircularDequeLinkedList
{ private ListNode head; private ListNode tail; private int size; public CircularDequeLinkedList() { head = null; tail = null; size = 0; } public void EnqueueFront(T value) { ListNode newNode = new ListNode(value); if (tail == null) { head = newNode; tail = newNode; newNode.Next = newNode; } else { newNode.Next = tail.Next; tail.Next = newNode; if (head == tail) { head = newNode; } } tail = newNode; size++; } public void EnqueueRear(T value) { ListNode newNode = new ListNode(value); if (tail == null) { head = newNode; tail = newNode; newNode.Next = newNode; } else { newNode.Next = tail.Next; tail.Next = newNode; tail = newNode; } size++; } public T DequeueFront() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = head.Val; head = head.Next; if (head == tail) { tail = null; head = null; } size--; return value; } public T DequeueRear() { if (size == 0) { throw new InvalidOperationException("Deque is empty."); } T value = tail.Val; ListNode current = head; while (current.Next != tail) { current = current.Next; } current.Next = tail.Next; tail = current; size--; return value; } public bool IsEmpty() { return size == 0; }
}

13. 二叉树

题目描述： 实现一个二叉树，支持插入、查找、遍历等操作。

代码示例：“`csharp public class TreeNode{

public T Val { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode(T val)
{ Val = val; Left = null; Right = null;
}

}

public class BinaryTree{

private TreeNode root;
public BinaryTree()
{ root = null;
}
public void Insert(T value)
{ root = InsertRecursive(root, value);
}
private TreeNode InsertRecursive(TreeNode current, T value)
{ if (current == null) { return new TreeNode(value); } if (value.CompareTo(current.Val) < 0) { current.Left = InsertRecursive(current.Left, value); } else if (value.CompareTo(current.Val) > 0) { current.Right = InsertRecursive(current.Right, value); } return current;
}
public bool Find(T value)
{ return FindRecursive(root, value);
}
private bool FindRecursive(TreeNode current, T value)
{ if (current == null) { return false; } if (value.CompareTo(current.Val) == 0) { return true; } return value.CompareTo(current.Val) < 0 ? FindRecursive(current.Left, value) : FindRecursive(current.Right, value);
}
public void InOrderTraversal()
{ InOrderTraversalRecursive(root);
}
private void InOrderTraversalRecursive(TreeNode