Shulou(Shulou.com)05/31 Report--

This article Xiaobian introduces in detail for you "C# data type how to achieve knapsack, queue and stack", the content is detailed, the steps are clear, and the details are handled properly. I hope this "C# data type how to achieve knapsack, queue and stack" article can help you solve your doubts, following the editor's ideas slowly in-depth, together to learn new knowledge.

Basic programming model and data abstraction

The language features, software libraries and operating system features used to describe and implement the algorithm are collectively called the basic programming model.

Points to note when writing recursive code:

1. There is always the simplest case of recursion-the first statement of a method always contains a conditional statement of return.

two。 Recursive calls always try to solve a smaller sub-problem so that recursion converges to the simplest case.

3. There should be no intersection between the parent problem of the recursive call and the child problem you are trying to solve.

A data type refers to a set of values and a set of operations on those values. Abstract data type (ADT) is a data type that can hide data representation from consumers. Implementing abstract data types with classes in a high-level language is no different from implementing a library with a set of static methods. The main difference of an abstract data type is that it associates the data with the implementation of the function and hides the representation of the data. When using abstract data types, we focus on the operations described by API rather than the representation of the data; when implementing abstract data types, we focus on the data itself and will implement various operations on that data.

Abstract data is important because it supports encapsulation in programming.

The main reason why we study different algorithms for the same problem is that they have different performance characteristics. Abstract data types can replace one algorithm with another without modifying the test code.

A basic concept in data abstraction: an object is an entity that can carry values of a data type. All objects have three characteristics: status, identity, and behavior. The state of the object is the value in the data type. The identity of the object is its location in memory. The behavior of an object is the operation of a data type.

Many basic data types are related to collections of objects. The value of a data type is a collection of objects, and all operations are about adding, deleting, or accessing objects in the collection. Backpacks (Bag), queues (Quene), and stacks (Stack) differ in the order in which objects are deleted or accessed.

1. API

Both Stack and Quene contain a method that can delete specific elements in the collection.

The implementation of the above API requires high-level language features: generics, boxing and unboxing, iterability (implementing the IEnumerable interface).

1. knapsack

A backpack is a collection type that does not support removing elements from it-its purpose is to help use cases collect elements and iterate through all elements. Use cases can also use stacks or queues, but using Bag shows that the order in which the elements are processed is not important.

two。 FIFO queue

Queues are collection types based on first-in, first-out (FIFO) policies.

3. Lower stack

Stack down (stack for short) is a type of collection based on last-in, first-out (LIFO) strategy.

Application example: evaluate the value of the input string (1 + ((2 + 3) * (4 # 5) expression.

Use dual stack solution:

1. Push the Operand into the Operand stack

two。 Push the operator into the operator stack

3. Ignore making parentheses

4. When you encounter the right parenthesis, pop up an operator, pop up the desired number of operands, and press the results of the operators and operands into the Operand stack.

two。 Implemented with an array

Push down the stack:

/ / if you want the data type to be iterative, you need to implement IEnumerable public class ResizingStack: IEnumerable {private Item [] a = new Item [1]; private int N = 0; public bool IsEmpty {get {return N = = 0;}} public int Size {get {return N;}} public int Count {get; set } / private void Resize (int max) {Count = 0; Item [] temp = new Item [max]; for (var I = 0 a.Length/ I 0 & N = = a.Length/ 4) Resize (a.Length/2) Return item;} IEnumerator IEnumerable.GetEnumerator () {return new ResizingStackEnumerator (a);} public IEnumerator GetEnumerator () {return new ResizingStackEnumerator (a);}} class ResizingStackEnumerator: IEnumerator {private Item [] a; private int N = 0 Public ResizingStackEnumerator (Item [] _ a) {a = _ a; N = a.Lengthmurl;} public object Current = > a [Nmuri -]; Item IEnumerator.Current = > a [Nmura -]; public void Dispose () {throw new NotImplementedException () } public bool MoveNext () {return N > 0;} public void Reset () {throw new NotImplementedException ();}} 3. Linked list

A linked list is another basic data structure that represents data in the abstract data type implementation of a collection class.

Definition: a linked list is a recursive data structure that points either to an empty or to another node that contains a generic element and a reference to another linked list.

Class Node {public Item item {get; set;} public Node Next {get; set;}} 1. Construct linked list

The linked list represents a list of elements.

According to the recursive definition, only a variable of type Node is needed to represent a linked list, as long as its Next value is null or points to another Node object, and the Next of that object points to another linked list.

two。 Insert a node in the header

The easiest place to insert a new node in the linked list is to start. To insert the string not at the beginning of a given linked list with the first node first, save the first in oldfirst, then assign a new node to first, and set the item of first to not and Next to oldfirst.

The time it takes to insert a node at the beginning of the linked list is independent of the length of the linked list.

3. Delete a node from the header

Simply point the first to first.next. The object that first originally points to becomes an orphan, and the garbage collection mechanism reclaims it.

Again, the time required for this operation is independent of the length of the linked list.

4. Insert a node at the end of the table

When the linked list has more than one node, you need a link oldlast that points to the last node of the linked list. Create a new node, and last points to the new last node. Then oldlast.next points to last.

When there is only one node in the linked list, the first node is the tail node. Just point the last to the new node, and then the first.next to last.

5. Insert and delete operations in other locations

The above operations can be easily implemented, but the following operations are more complex:

1. Delete the specified node

two。 Insert a new node before the specified node

These operations require us to traverse the linked list, and the time it takes is proportional to the length of the linked list. To achieve arbitrary insertion and deletion of nodes, you need to use a two-way linked list, where each node contains two links to the previous and next nodes, respectively.

6. Ergodic

Simple implementation:

Public class Bag {private Node first; public void Add (Item item) {Node oldFirst = first; first = new Node () {item = item, Next = oldFirst};}} Bag bags = new Bag (); for (var I = 0; I

< 10; i++) { bags.Add(i); } for (var x = bags.first; x != null; x = x.Next) { Console.WriteLine(x.item); } 实现 IEnumerable 接口 实现遍历： public class Bag: IEnumerable { public Node first; public void Add(Item item) { Node oldFirst = first; first = new Node() { item = item, Next = oldFirst }; } public IEnumerator GetEnumerator() { return new LineEnumerator(first); } IEnumerator IEnumerable.GetEnumerator() { return new LineEnumerator(first); } } public class LineEnumerator : IEnumerator { public Node first; public LineEnumerator(Node _first) { first = _first; } public Item Current { get { var oldfirst = first; first = first.Next; return oldfirst.item; } } object IEnumerator.Current =>

First; public void Dispose () {return;} public bool MoveNext () {if (first! = null) return true; return false;} public void Reset () {throw new NotImplementedException () }} public static void LineTest () {Bag bags = new Bag (); for (var I = 0; I

< 10; i++) { bags.Add(i); } foreach(var bag in bags) { Console.WriteLine(bag); } }4. 用链表实现背包 见上述代码。 5. 用链表实现栈 Stack API 中 Pop() 删除一个元素，按照前面的从表头删除结点实现，Push() 添加一个元素，按照前面在表头插入结点。 public class Stack : IEnumerable { public Node first; private int N; public bool IsEmpty() { return first == null; //或 N == 0 } public int Size() { return N; } public void Push(Item item) { Node oldfirst = first; first = new Node() { item = item, Next = oldfirst }; N++; } public Item Pop() { Item item = first.item; first = first.Next; N--; return item; } public IEnumerator GetEnumerator() { return new StackLineIEnumerator(first); } IEnumerator IEnumerable.GetEnumerator() { return new StackLineIEnumerator(first); } } public class StackLineIEnumerator : IEnumerator { private Node first; public StackLineIEnumerator(Node _first) { first = _first; } public Item Current { get { var oldfirst = first; first = first.Next; return oldfirst.item; } } object IEnumerator.Current =>

Throw new NotImplementedException (); public void Dispose () {return;} public bool MoveNext () {return first! = null;} public void Reset () {throw new NotImplementedException ();}

The use of linked lists achieves the optimal design goal:

1. Can handle any type of data

two。 The space required is always proportional to the size of the collection

3. The time required for the operation is always independent of the size of the collection

6. Implementing queues with linked lists

Two instance variables are required, first pointing to the beginning of the queue and last pointing to the footer of the queue. Add an element Enquene () to add the node to the end of the list (when the linked list is empty, both first and last point to the new node). Delete an element Dequene (), delete the node in the header (after deletion, update last to null when the queue column is empty).

Public class Quene: IEnumerable {public Node first; public Node last; private int N; public bool IsEmpty () {return first = = null;} public int Size () {return N;} public void Enquene (Item item) {var oldlast = last Last = new Node () {item = item, Next = null}; if (IsEmpty ()) first = last; else oldlast.Next = last; Nissan + } public Item Dequene () {if (IsEmpty ()) throw new Exception (); Item item = first.item; first = first.Next; if (IsEmpty ()) last = null; N Murray; return item } public IEnumerator GetEnumerator () {return new QueneLineEnumerator (first);} IEnumerator IEnumerable.GetEnumerator () {return new QueneLineEnumerator (first);}} public class QueneLineEnumerator: IEnumerator {private Node first; public QueneLineEnumerator (Node _ first) {first = _ first } public Item Current {get {var oldfirst = first; first = first.Next; return oldfirst.item;}} object IEnumerator.Current = > throw new NotImplementedException (); public void Dispose () {return;} public bool MoveNext () {return first! = null } public void Reset () {throw new NotImplementedException ();}} 7. Summary

Linked lists are an important alternative to arrays when structurally storing datasets.

The two data types, array and linked list, lay the foundation for the study of algorithms and more advanced data structures.

Basic data structure:

The advantages and disadvantages of the data structure the array can directly access any element through the index, and when initializing, you need to know the number of elements, the space size used by the linked list is proportional to the number of elements, and you need to access any element through reference.

When studying a new application area, you can follow these steps to identify goals, define problems, and solve problems using data abstraction:

1. Define API

two。 Develop use case code according to specific application scenarios

3. Describes a data structure (that is, the representation of a set of values) and defines instance variables of the class based on it in the implementation of API.

4. Describe the algorithm, that is, implement API, and apply it to use cases according to it

5. Analyze the performance of the algorithm

After reading this, the article "how to implement backpacks, queues and stacks of C# data types" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself. If you want to know more about related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.