Mảng là một Cấu trúc dữ liệu tuyến tính, là tập hợp các loại đối tượng tương tự [số nguyên, ký tự, chuỗi, v.v. ] được lưu trữ trong các vị trí bộ nhớ liền kề và liền kề. Một mảng dựa trên hệ thống chỉ mục, giúp dễ dàng truy cập vào các phần tử của mảng. Giá trị của chỉ mục bắt đầu từ '0' và đi đến 'n-1', trong đó n là số phần tử có trong mảng
Sợi dây
Chuỗi là một loại mảng đặc biệt, nó được gọi là một mảng các ký tự. Nó được thực hiện tương tự như một mảng. Nó cũng tuân theo hệ thống chỉ số. Sự khác biệt giữa một mảng ký tự và một chuỗi là chuỗi được kết thúc bởi một ký tự đặc biệt được gọi là ký tự null '\0'
Danh sách liên kết
Danh sách liên kết là một cấu trúc dữ liệu tuyến tính là tập hợp các nút. Mỗi nút bao gồm hai trường i. e. một là trường dữ liệu và một là con trỏ tới nút tiếp theo của danh sách được liên kết. Địa chỉ của các nút trong danh sách liên kết không liên tục nên việc thêm hoặc xóa nút dễ dàng hơn nhưng việc tìm kiếm trở nên tốn kém hơn
thuật toán tìm kiếm
Thuật toán tìm kiếm là một trong những thuật toán quan trọng nhất được áp dụng cho cấu trúc dữ liệu để giải bài toán. Tìm kiếm được định nghĩa là quá trình tìm kiếm hoặc truy cập dữ liệu cần thiết từ tập hợp các mục được lưu trữ dưới dạng phần tử bên trong cấu trúc dữ liệu. Có hai loại thuật toán tìm kiếm chủ yếu được sử dụng
- Tìm kiếm tuyến tính. Tìm kiếm tuyến tính là một thuật toán tìm kiếm tuần tự trong đó chúng ta bắt đầu tìm kiếm một phần tử từ đầu danh sách và đi đến cuối danh sách hoặc cho đến khi không tìm thấy phần tử cần thiết. Đây là thuật toán tìm kiếm dễ dàng và đơn giản nhất. Độ phức tạp về thời gian của thuật toán tìm kiếm tuyến tính là O[N] trong trường hợp xấu nhất, O[1] trong trường hợp tốt nhất và O[N] trong trường hợp trung bình, trong đó N là số phần tử trong mảng
- Tìm kiếm nhị phân. Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng để tìm dữ liệu hoặc phần tử bên trong danh sách [hoặc mảng] được sắp xếp bằng cách chia đôi không gian tìm kiếm mỗi khi chúng tôi không tìm thấy phần tử. Động cơ chính của việc sử dụng tìm kiếm nhị phân là để giảm độ phức tạp về thời gian của việc tìm kiếm một phần tử bên trong một mảng được sắp xếp vì độ phức tạp về thời gian của thuật toán tìm kiếm nhị phân là O[NlogN] trong trường hợp xấu nhất
Thuật toán chia để trị
Phương pháp chia để trị này là một cách tiếp cận chia một bài toán lớn hơn thành các bài toán con nhỏ hơn tương tự như bài toán ban đầu và nó giải đệ quy các bài toán con để cuối cùng kết hợp các nghiệm của các bài toán con và giải bài toán lớn hơn ban đầu. Chủ yếu có hai thuật toán quan trọng nhất dựa trên phương pháp chia để trị, đó là. e. Hợp nhất Sắp xếp và Sắp xếp Nhanh
thuật toán sắp xếp
Sắp xếp là kỹ thuật sắp xếp dữ liệu trong danh sách theo thứ tự ưu tiên. Thứ tự thường là thứ tự tăng hoặc giảm. Nhiều thuật toán khác nhau được sử dụng để sắp xếp một mảng, các thuật toán được sử dụng nhiều nhất được đề cập bên dưới
- Sắp xếp bong bóng
- Sắp xếp chèn
- Sắp xếp lựa chọn
- Hợp nhất Sắp xếp
- Sắp xếp nhanh chóng
- Sắp xếp đống
Xếp hàng
Hàng đợi là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Nhập trước xuất trước [nguyên tắc FIFO]. Điều đó có nghĩa là phần tử nào vào trong hàng đợi trước sẽ là phần tử đầu tiên được đưa ra khỏi hàng đợi. Đúng như tên gọi, nó giống như hàng đợi ngoài đời thực, người đứng đầu hàng sẽ là người đầu tiên được giải trí. Hàng đợi bao gồm hai thao tác i. e. 'enqueue' có nghĩa là đẩy một phần tử vào cuối hàng đợi và 'dequeue' có nghĩa là lấy phần tử ra khỏi đầu hàng đợi
Cây rơm
Ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Nhập sau xuất trước [nguyên tắc LIFO]. Điều đó có nghĩa là phần tử vào cuối cùng trong ngăn xếp sẽ là phần tử đầu tiên bị xóa khỏi ngăn xếp. Ngăn xếp bao gồm hai thao tác i. e. 'push' nghĩa là đẩy phần tử lên đỉnh ngăn xếp và 'pop' nghĩa là lấy phần tử ra khỏi đỉnh ngăn xếp
Cấu trúc dữ liệu cây
Cây là Cấu trúc dữ liệu phi tuyến tính bao gồm một tập hợp nhiều nút. Nút bao gồm trường dữ liệu và các con trỏ tới con của nút. Cấu trúc dữ liệu cây được sử dụng để thể hiện cấu trúc phân cấp. Cây nhị phân là Cây được sử dụng nhiều nhất, trong đó mỗi nút bao gồm ba trường, trường đầu tiên là trường dữ liệu, trường thứ hai là con trỏ tới nút con bên trái của nút và trường thứ ba là con trỏ tới nút con bên phải của nút. . Nếu không có phần tử con nào thì các con trỏ sẽ được gán giá trị NULL
Cấu trúc dữ liệu đồ thị
Biểu đồ là một cấu trúc dữ liệu phi tuyến tính. Nó được biểu diễn dưới dạng đỉnh và cạnh. Các đỉnh còn được gọi là các nút và các cạnh còn được gọi là các đường hoặc cung. Các cạnh chịu trách nhiệm kết nối một nút với một nút khác. Biểu đồ là một trong những thứ quan trọng nhất vì nó có nhiều ứng dụng thực tế mà chúng ta có thể gặp trong cuộc sống hàng ngày. Biểu đồ chủ yếu được sử dụng để mô tả mối quan hệ giữa hai nút và các nút này có thể biểu thị bất kỳ đối tượng thực tế nào
đệ quy
Nói một cách đơn giản, chúng ta có thể định nghĩa Đệ quy là “Một hàm gọi chính nó trực tiếp hoặc gián tiếp”, và hàm gọi chính nó [thực hiện đệ quy] được gọi là hàm đệ quy. Trong thế giới của Khoa học Máy tính, có nhiều vấn đề mà phép lặp không thành công hoặc độ phức tạp của các giải pháp lặp tăng lên, vì vậy các loại vấn đề này phù hợp nhất để giải quyết bằng đệ quy. Ví dụ về một số bài toán nổi tiếng là Merge Sort, Tower of Hanoi, DFS traversal, v.v.
phương pháp tham lam
Thuật toán tham lam là một cách tiếp cận được sử dụng để giải quyết vấn đề một cách tối ưu và hiệu quả. Ở mỗi bước, lựa chọn có chi phí thấp nhất và lợi nhuận cao nhất được chọn, như tên gọi của chính nó, lựa chọn mang lại lợi ích ngay lập tức được xem xét
Thuật toán quay lui
Nói một cách đơn giản, chúng ta có thể định nghĩa Backtracking là 'Một thuật toán sử dụng kỹ thuật brute force để thử tất cả các giải pháp khả thi và cuối cùng chọn ra giải pháp tốt nhất'. Trong một số vấn đề, chúng tôi có nhiều lựa chọn nhưng chúng tôi không biết giải pháp tốt nhất, vì vậy trong những trường hợp này, chúng tôi thích sử dụng Quay lui để chúng tôi có thể tìm thấy mọi giải pháp khả thi và cuối cùng chọn giải pháp tốt nhất có thể
Lập trình năng động
Quy hoạch động là một cách tiếp cận giải quyết các bài toán có cấu trúc con chồng chéo một cách tối ưu và hiệu quả. Nó còn được gọi là 'tối ưu hóa qua đệ quy đơn giản' vì trong đệ quy, chúng ta có nhiều vấn đề chồng chéo có thể giải quyết dễ dàng bằng cách sử dụng khái niệm Quy hoạch động. Đệ quy tìm mọi giải pháp có thể và Lập trình động lưu trữ giải pháp này để các vấn đề đã được giải quyết không được giải quyết lặp đi lặp lại, thay vào đó, chúng ta phải sử dụng giải pháp đã lưu trữ sẽ giảm độ phức tạp thời gian từ hàm mũ sang tuyến tính hoặc bậc hai