Triển khai mảng của danh sách ADT trong Python
|
Chúng ta đã thảo luận về các định nghĩa cơ bản của Cấu trúc dữ liệu và giải thuật trong bài viết trước. trong bài viết này, chúng ta hãy tìm hiểu sâu hơn về thế giới Cấu trúc dữ liệu, và đặc biệt, hãy bắt tay vào viết mã một chút Show Mục tiêu của bài viết này
Giới thiệu về kiểu dữ liệuCấu trúc dữ liệu được tạo từ một hoặc nhiều đối tượng Dữ liệu. các đối tượng dữ liệu đại diện cho dữ liệu mà chúng tôi sẽ lưu trữ bằng các cấu trúc dữ liệu được thiết kế cẩn thận. Các kiểu dữ liệu được xác định là cách chính để phân loại một số loại dữ liệu trong cấu trúc dữ liệu, chẳng hạn như chuỗi, ký tự, số nguyên, v.v. Có hai loại dữ liệu chính trong thế giới lập trình, đó là kiểu dữ liệu tích hợp và kiểu dữ liệu có nguồn gốc Kiểu dữ liệu tích hợpĐây là những kiểu dữ liệu cơ bản mà các ngôn ngữ lập trình đang hỗ trợ. Chủ yếu được gọi là các loại dữ liệu chính trong một ngôn ngữ lập trình cụ thể Loại dữ liệu dẫn xuấtCác kiểu dữ liệu này được triển khai bằng cách sử dụng một hoặc nhiều kiểu dữ liệu (chính) tích hợp sẵn. Tất cả các cấu trúc dữ liệu được phát triển dựa trên loại dữ liệu dẫn xuất như vậy. Trong bài viết này, chúng ta sẽ thảo luận về cấu trúc dữ liệu của Stack’s an Array với các ví dụ triển khai Cấu trúc dữ liệu ngăn xếpNgăn xếp là một kiểu dữ liệu Trừu tượng (ADT là kiểu dành cho các đối tượng có hành vi được xác định bởi một tập giá trị và một tập hoạt động) là một trong những cấu trúc Dữ liệu chính trong ngôn ngữ lập trình và đối với người mới bắt đầu, đây là một cấu trúc dữ liệu dễ hiểu. . LIFO (Last In First Out) là đặc điểm chính của ngăn xếp Giống như hầu hết các cấu trúc dữ liệu, ngăn xếp cũng đại diện cho các đối tượng trong thế giới thực. Ví dụ: một chồng tiền xu, một chồng hộp, v.v. Một ngăn xếp có thể được thực hiện bằng cách sử dụng một mảng, một danh sách, một con trỏ, v.v. Khi nói đến ngăn xếp, có một tập hợp các hàm được xác định để sử dụng ngăn xếp một cách hiệu quả trong ngữ cảnh lập trình Triển khai Python Trong python, chúng ta có thể sử dụng kiểu dữ liệu danh sách làm kiểu dữ liệu tích hợp để triển khai cấu trúc dữ liệu ngăn xếp {code}Vui lòng tìm cơ sở mã đính kèm trong liên kết Github này triển khai NodeJ Trong NodeJs, chúng ta có thể triển khai cấu trúc dữ liệu ngăn xếp bằng kiểu dữ liệu Array {code} Vui lòng tìm cơ sở mã đính kèm trong liên kết Github này Thao tác đẩyKhi bạn đã xác định lớp ngăn xếp, một trong những chức năng chính là chức năng đẩy. Tại đây bạn sẽ nhập một mục vào đầu mảng Thuật toán để thực hiện Chúng ta có thể định nghĩa một thuật toán để thực hiện thao tác đẩy trong lớp ngăn xếp Step 1 − Checks if the stack is full(assume that the list is implemented based on a dynamic array) for the given size or not.Step 2 − If the stack is full, print an errorStep 3 − If the stack is not full for the given maximum size, increase the top by one and point the pointer to the next empty space.Step 4 − Add a new element to the new empty space which is in the top of the stackStep 5 − Return success.Hoạt động nhạc pop Hàm pop sẽ xóa phần tử trên cùng khỏi ngăn xếp và số lượng mục trong ngăn xếp sẽ giảm đi một. Mặc dù có vẻ như phần tử trên cùng đã bị xóa khỏi ngăn xếp, nhưng phần tử đó sẽ không bị xóa hoàn toàn, chỉ con trỏ sẽ di chuyển đến vị trí bên dưới Thuật toán để thực hiện Chúng ta có thể định nghĩa một thuật toán để thực hiện thao tác pop trong lớp ngăn xếp Step 1 − Checks if the stack is empty by looking at the array lengthStep 2 − If the stack is empty, print an error, exitStep 3 − If the stack is not empty, get the element which is pointing at the top of the stack.Step 4 − Decreases the size of the stack by 1, automatically the pointer of the top most item will changed to the below item.Step 5 − Returns success.Hoạt động lén lút Hàm peek sẽ hiển thị phần tử trên cùng của ngăn xếp và thao tác này sẽ không xóa phần tử khỏi ngăn xếp như trong thao tác pop Thuật toán để thực hiện Chúng ta có thể định nghĩa một thuật toán để thực hiện thao tác nhìn lén trong lớp ngăn xếp. thao tác nhìn trộm chỉ trả về giá trị ở đầu ngăn xếp Step 1 − Checks if the stack is empty by looking at the array lengthStep 2 − If the stack is empty, print an error, exitStep 3 − If the stack is not empty, get the element which is pointing at the top of the stack.Step 4 − Returns success. Có các hàm khác như isEmpty(), isFull() và printStackItems() có thể được sử dụng như các hàm hỗ trợ giúp bạn sử dụng ngăn xếp hiệu quả Triển khai ngăn xếp và tất cả các triển khai chức năng hỗ trợ sẽ được tìm thấy trong cơ sở mã này. cấu trúc dữ liệu ngăn xếp Làm bẩn tay bạn với cấu trúc dữ liệu ngăn xếp vì chúng tôi sẽ sử dụng các cấu trúc dữ liệu này trong tương lai khi chúng tôi giải quyết các vấn đề thực tế trong phần thuật toán Cấu trúc dữ liệu mảngMảng là một trong những cấu trúc dữ liệu được sử dụng nhiều nhất khi các lập trình viên triển khai thuật toán của mình. Một điểm đặc biệt của mảng là vùng chứa mảng phải có kích thước cố định và tất cả các phần tử phải cùng loại Ngoài việc tất cả các phần tử trong mảng phải có cùng kiểu dữ liệu, mảng luôn bắt đầu từ phần tử thứ 0 (không được lập chỉ mục) và kích thước của mảng có nghĩa là có thể lưu trữ bao nhiêu phần tử trong chính nó Trong nhiều loại dữ liệu, có các hoạt động (chức năng) chính tồn tại để sử dụng hiệu quả và hiệu quả loại dữ liệu đó. Trong kiểu dữ liệu mảng tồn tại 5 thao tác chính Chèn mảngThêm một phần tử mới vào chỉ số đã cho được gọi là chèn mảng. Chúng tôi đã có thể thực hiện việc chèn một phần tử vào chỉ mục đã cho thông qua ngôn ngữ lập trình python và nodejs Thực hiện thao tác chèn mảng trong nodejs Thực hiện thao tác chèn mảng trong python Tìm kiếm mảngChúng ta có thể thực hiện các thao tác tìm kiếm trên một phần tử mảng dựa trên giá trị hoặc chỉ mục Tìm kiếm theo chỉ số có nghĩa là trả về phần tử mảng tương ứng với chỉ số đã cho và tìm kiếm theo giá trị có nghĩa là trả về giá trị tương ứng của chỉ số đã cho trong mảng Thực hiện thao tác chèn mảng trong nodejs Thực hiện thao tác chèn mảng trong python Xóa mảngVì mảng là một cấu trúc dữ liệu có kích thước cố định nên việc xóa một phần tử khỏi vị trí đã cho trong một mảng hơi phức tạp một chút. Bạn nên điều chỉnh mảng mới bằng cách giảm kích thước của mảng trong khi bạn đang xóa phần tử đã cho. Vui lòng tham khảo các mẫu mã sau giải thích cách xóa một phần tử đã cho khỏi một mảng bằng các kỹ thuật lập trình cơ bản Thực hiện thao tác chèn mảng trong python Thực hiện thao tác chèn mảng trong Nodejs Cập nhật mảngCập nhật mảng là một thao tác khá dễ dàng, bạn chỉ cần duyệt qua mảng đã cho cho đến khi tìm thấy phần tử cần cập nhật. Vui lòng làm theo các mẫu mã sau để làm quen với chức năng cập nhật mảng Triển khai thao tác cập nhật mảng trong nodejs — code Triển khai thao tác cập nhật mảng trong python — code Truyền tải mảngTruyền mảng không là gì ngoài việc in tất cả các phần tử của mảng theo một trình tự. Vì mảng là kiểu dữ liệu có chỉ mục bằng 0, nên chúng ta có thể bắt đầu in các phần tử mảng bằng cách duyệt qua cấu trúc mảng từ vị trí 0 Triển khai hoạt động truyền tải mảng trong nodejs — code Triển khai thao tác duyệt mảng trong python — code Tóm lại, chúng ta đã học cách sử dụng Stack và Array một cách hiệu quả. Vui lòng tìm các đoạn mã sau để xem cách chúng tôi có thể triển khai ngăn xếp và mảng trong python và nodejs Bạn sẽ chỉ cần cài đặt nút trong máy của mình và bạn đã sẵn sàng để sử dụng. (liên kết cài đặt nút) Bắt đầu viết mã để làm bẩn tay cho các bài học sau FYI: when you trying to implement data structure operations, always remember on “Algorithm to implement” and think in that direction. This approach will help you to get a deep understanding of the entire workflow of data structure usage.Trong bài học tiếp theo, chúng ta sẽ triển khai các cấu trúc dữ liệu dẫn xuất khác như hàng đợi, danh sách được liên kết, danh sách liên kết kép và danh sách liên kết vòng được coi là cấu trúc dữ liệu cực kỳ quan trọng để nắm bắt trước khi đi sâu vào sử dụng thuật toán Triển khai mảng của danh sách ADT là gì?Đó là một dãy gồm n phần tử trong đó các phần tử trong mảng được lưu trữ với chỉ số của mảng liên quan đến vị trí của phần tử trong danh sách. In array implementation,elements are stored in contiguous array positions (Figure 3.1).
ADT viết ADT cho mảng là gì?Mảng là một kiểu dữ liệu trừu tượng (ADT) chứa một tập hợp các phần tử có thể truy cập bằng một chỉ mục. Các phần tử được lưu trữ trong một mảng có thể là bất kỳ thứ gì từ các kiểu nguyên thủy như số nguyên đến các kiểu phức tạp hơn như các thể hiện của các lớp.
Danh sách ADT trong Python là gì?Ví dụ: danh sách ADT có thể được sử dụng cho danh sách số nguyên, danh sách ký tự, danh sách bản ghi bảng lương, thậm chí danh sách danh sách . Một danh sách được gọi là rỗng khi nó không chứa phần tử nào. Số phần tử đang được lưu trữ gọi là độ dài của danh sách.
Hai cách thực hiện danh sách ADT là gì?Có thể có nhiều cách khác nhau để triển khai ADT, ví dụ: Danh sách ADT có thể được triển khai bằng cách sử dụng mảng hoặc danh sách liên kết đơn hoặc danh sách liên kết đôi. |
