Cấu trúc dữ liệu và giải thuật trong C# – ChienTX

Hôm nay, tất cả chúng ta sẽ cùng nhau tìm hiểu và khám phá về hai kiểu dữ liệu thông dụng và tương đối giống nhau được trình làng trong. NET Framework, đó là kiểu Array và kiểu List .

Array

Mảng là một tập hợp những kiểu dữ liệu giống nhau và được xác lập tại những vị trí liều kề nhau trong bộ nhớ. Các thành phần của mảng hoàn toàn có thể được truy vấn trực tiếp qua chỉ số của thành phần đó trong mảng. Trong C #, khi một mảng được tạo ra, chúng sẽ có giá trị null. Đoạn code sau khởi tạo một mảng kiểu bool :

bool [] booleanArray;

Bạn đang đọc: Cấu trúc dữ liệu và giải thuật trong C# – ChienTX

Trước khi có thể thao tác với mảng thì tất cả chúng ta phải tạo một biểu lộ của mảng mà để lưu những thành phần. Cú pháp như sau :
booleanArray = new bool [ 10 ] ;
hoặc tất cả chúng ta hoàn toàn có thể vừa khởi tạo, vừa tạo bộc lộ của mảng :
bool [ ] booleanArray = new bool [ 10 ] ;
Mọi mảng trong. NET được cho phép những thành phần hoàn toàn có thể đọc và viết giá trị vào đó. Cú pháp như sau :

1 : / / Read an array element

2 : bool b = booleanArray[7];

3 :  

4 : / / Write an array element

5 : booleanArray[2] = false;

Trong managed code, CLR sẽ kiểm tra để bảo vệ là những thành phần truy nhập nằm trong số lượng giới hạn của mảng, nếu không thì một ngoại lệ sẽ được ném ra : IndexOutOfRangeException .
Khi thao tác với mảng, nhiều lúc tất cả chúng ta cần đổi khác kích cỡ của mảng. Để làm được điều này, tất cả chúng ta phải tạo một biểu lộ mới của mảng với kích cỡ mới, sao chép nội dung mảng cũ sang mảng mới. Đoạn code sau miêu tả quy trình đó :

1 : / / Create an integer array with three elements

2 : int [] fib = new int[3];

3 : fib[0] = 1;

4 : fib[1] = 1;

5 : fib[2] = 2;

6 :       

7 : / / Redimension message to a 10 element array

8 : int [] temp = new int[10];

9 :  

10 : / / Copy the fib array to temp

11 : fib.CopyTo(temp, 0);

12 :       

13 : / / Assign temp to fib

14 : fib = temp;   

Sau dòng code cuối thì mảng fib hoàn toàn có thể tham chiếu được tới 10 thành phần. Giá trị từ 3 – 9 sẽ mang giá trị mặc định của kiểu Int32 là 0

Tạo Cấu trúc dữ liệu thực thi an toàn, có thể tái sử dụng

Khi tạo một cấu trúc dữ liệu cho một yếu tố nào đó, thường thì cấu trúc đó được tùy chỉnh theo nhu yếu của việc làm. Ví dụ, để quản lí bảng lương nhân viên cấp dưới, những giá trị nguồn vào là những nhân viên cấp dưới, tất cả chúng ta hoàn toàn có thể tạo một lớp Employee với những phương pháp và thuộc tính tương thích. Và để màn biểu diễn một tập hợp những nhân viên cấp dưới, tất cả chúng ta hoàn toàn có thể sử dụng một mảng Employee, nhưng bạn lại cần có thêm những tính năng bổ trợ mà không muốn chăm sóc đến việc biến hóa kích cỡ mảng khi thiết yếu. Một tùy chọn đó là tự tạo một cấu trúc dữ liệu riêng cho kiểu Employee, thêm vào đó những công dụng thiết yếu như tìm kiếm, tăng size … .
Cấu trúc này tỏ ra hữu dụng trong ứng dụng của bạn nhưng khi đem sử dụng cho những ứng dụng khác thì lại không được vì nó chỉ tàng trữ những thành phần là kiểu Employee. Để tạo cấu trúc dữ liệu thêm linh động, ta hoàn toàn có thể tạo một mảng của những biểu lộ Object. Bởi vì tổng thể những kiểu dữ liệu đều là dẫn xuất từ kiểu Object nên nó hoàn toàn có thể lưu bất kỳ giá trị nào. . NET Framework cung ứng một cấu trúc cho việc này : lớp System. Collections. ArrayList. ArrayList chứa một mảng những thành phần có kiểu là Object nên nó hoàn toàn có thể lưu bất kể kiểu giá trị nào : strings, integers, đối tượng người tiêu dùng FileInfo, những bộc lộ của Form … .
Mặc dù ArrayList tỏ ra khá hữu hiệu và linh động nhưng lại phải đổi lại bằng hiệu năng của ứng dụng. Vì ArrayList lưu mảng những object, và khi đọc giá trị thì phải ép kiểu giá trị. Một mảng ArrayList thì dù cho bạn không có tàng trữ bất kỳ thành phần nào thì mỗi thành phần là một tham chiếu tới một kiểu giá trị được boxed ( boxed value type ) => tốn bộ nhớ .

Sử dụng ArrayList với số lượng thành phần lớn hoàn toàn có thể làm chậm việc thực thi chương trình. Ngoài ra, vì ArrayList được cho phép bất kể kiểu giá trị nào cũng hoàn toàn có thể được thêm vào nên sẽ không có lỗi xảy ra khi thêm một kiểu không hợp lệ. Các lỗi này sẽ không Open đến khi kiểm tra hoặc đem ra sử dụng .
Tuy nhiên, trong. NET Framework 2.0, tất cả chúng ta có Generics để xử lý yếu tố của ArrayList. Generics là một namespace được cho phép tạo một cấu trúc dữ liệu theo một cách khác. Developer hoàn toàn có thể tùy chọn kiểu dữ liệu sử dụng. Để hiểu rõ hơn thì tất cả chúng ta xét một ví dụ :

public class TypeSafeList
{
    T[] innerArray = new T[0];
    int currentSize = 0;
    int capacity = 0;

    public void Add(T item)
    {
        / / see if array needs to be resized
        if (currentSize == capacity)
        {
            / / resize array
            capacity = capacity == 0 ? 4 : capacity * 2;  
// double capacity 
Xem thêm: 5 dấu hiệu thai phát triển tốt và 10 dấu hiệu thai yếu bạn cần biết 

            T[] copy = new T[capacity];    / / create newly sized array
            Array.Copy(innerArray, copy, currentSize);  / / copy over the array
            innerArray = copy;    / / assign innerArray to the new, larger array
        }

        innerArray[currentSize] = item;
        currentSize++;
    }

    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= currentSize)
                throw new IndexOutOfRangeException();
            return innerArray[index];
        }
        set
        {
            if (index < 0 || index >= currentSize)
                throw new IndexOutOfRangeException();
            innerArray[index] = value;
        }
    }

    public override string ToString()
    {
        string output = string.Empty;
        for (int i = 0; i < currentSize - 1; i++)
            output += innerArray[i] + ", ";

        return output + innerArray[currentSize - 1];
    }
}

Tại dòng tiên phong, tất cả chúng ta có thành phần định nghĩa kiểu T. Developer sẽ dùng nó để chỉ định một kiểu, mà ở đây tất cả chúng ta định danh là T. Chúng ta trọn vẹn hoàn toàn có thể dùng những tên khác thay cho T, và biến này hoàn toàn có thể được sử dụng trong những phương pháp và thuộc tính .
Để khai báo biến cho class này, developer cần chỉ định kiểu T, như :

TypeSafeList varibaleName;

Đoạn code sau diễn đạt việc tạo một bộc lộ của TypeSafeList tàng trữ số nguyên và đưa giá trị là 25 số Fibonacci vào :

TypeSafeList fib = new TypeSafeList();
fib.Add(1);
fib.Add(1);
for (int i=2; i<25; i++)
    fib.Add(fib[i-1] + fib[i-2]);
Console.WriteLine(fib.ToString());

Lợi ích của việc sử dụng Generics là :

-An toàn kiểu: developer chỉ có thể thêm vào một kiểu được chỉ định.
-Performance: chương trình thực thi nhanh hơn và hiệu quả hơn
-Có thể tái sử dụng

Rất nhiều cấu trúc dữ liệu, ví dụ như cây nhị phân, tất cả chúng ta sẽ dùng tới Generics

List: Mảng đồng nhất, tự thay đổi số chiều.

Trong phần trước, tất cả chúng ta đã tạo ra một lớp TypeSafeList, tuy nhiên ,. NET Framework phân phối sẵn một lớp tựa như như vậy cho tất cả chúng ta mà tất cả chúng ta không cần chăm sóc nhiều đến việc viết code. Đó là lớp List, được chứa trong namespace System. Collections. Generics
Để tạo một bộc lộ của List, ta làm giống như ví dụ ở phần trước :

/ / Tạo một list những số nguyên
List myFavouriteIntegers = new List();

/ / Tạo một list chuỗi
List friendsNames = new List();

Khi khởi tạo, tất cả chúng ta không cần chỉ ra kích cỡ của List ( mặc dầu tất cả chúng ta hoàn toàn có thể chỉ định một kích cỡ mặc định trước qua constructor hoặc qua thuộc tính List’s Capacity ). Để thêm vào một thành phần, ta dùng phương pháp Add ( ), và tất cả chúng ta hoàn toàn có thể truy vấn trực tiếp và những thành phần trải qua chỉ số của thành phần đó. Sau đây là một đoạn code miêu tả việc tạo một List những số nguyên, và sau đó là thêm, đọc, ghi giá trị :

/ / Create a List of integers
List powersOf2 = new List();

/ / Add 6 integers to the List
powersOf2.Add(1);
powersOf2.Add(2);
powersOf2.Add(4);
powersOf2.Add(8);
powersOf2.Add(16);
powersOf2.Add(32);

/ / Change the 2 nd List item to 10
powersOf2[1] = 10;

// Compute 2^3 + 2^4
Xem thêm: Lịch sử Internet – Wikipedia tiếng Việt

int sum = powersOf2[2] + powersOf2[3];

List cung ứng cho ta nhiều phương pháp tương hỗ cho những việc làm thường làm. Ví dụ, muốn tìm một thành phần trong một mảng, bạn cần viết một vòng lặp for để thực thi. Trong List, bạn chỉ cần đơn thuần gọi thủ tục Contains ( ) để xem có thành phần nào đó trong mảng không, hay IndexOf ( ) để tìm vị trí của thành phần. Lớp List cũng có phương pháp BinarySearch ( ) để tìm một thành phần trong mảng đã được sắp xếp, và những phương pháp Find ( ), FindAll ( ), Sort ( ), ConvertAll ( ) .

Source: https://thomaygiat.com
Category : Kỹ Thuật Số