Đồ án Cấu trúc dữ liệu và giải thuật - Sắp xếp một danh sách liên kết

Đồ án Cấu trúc dữ liệu và Giải thuật Đề tài : Sắp xếp một danh sách liên kết Giáo viên hướng dẫn : Lê Đình Sơn Sinh viên : Phạm Thành Công Lớp : Tin học 5B Nội dung 1.Đề tài và yêu cầu. 2.Danh sách liên kết và sắp xếp danh sách liên kết. 3.Xây dựng chương trình cho phép sắp xếp một danh sách liên kết. 4.Kết luận. 1.Đề tài và yêu cầu Đề tài : Sắp xếp một danh sách liên kết. Yêu cầu : Xây dựng giải thuật sắp xếp trên danh sách liên kết. Viết chương trình ứng dụng dựa trên giải thuật. 2.Danh sách liên kết và sắp xếp danh sách liên kết. Danh sách : một tập hữu hạn các phần tử có cùng một kiểu, mà tổng quát ta gọi là kiểu phần tử (Elementtype). Ta biểu diễn danh sách như là một chuỗi các phần tử của nó a1,a2…an với n >=0. Nếu n = 0 ta nói danh sách rỗng (Empty list). Nếu n > 0 ta gọi a1 là phần tử đầu tiên, an là phần tử cuối cùng của danh sách. Số phần tử của danh sách gọi là độ dài của danh sách. Danh sách liên kết : một danh sách tuyến tính mà ta sử dụng con trỏ hoặc mối nối để tổ chức danh sách tuyến tính đó. nguyên tắc :mỗi phần tử của danh sách được lưu trữ trong một phần tử nhớ mà ta gọi là nút (node) Trường INFO chứa thông tin của phần tử. Trường LINK chứa địa chỉ (mối nối) nút tiếp theo. Danh sách liên kết vòng : danh sách liên kết mà phần tử cuối cùng của danh sách trỏ tới phần tử đầu tiên của danh sách. Danh sách liên kết kép : mỗi nút có hai con trỏ. LPTR là con trỏ trái, trỏ tới nút đứng trước. INFO chứa thông tin phần tử. RPTR là con trỏ phải, trỏ tới nút đứng sau. Thuật toán sắp xếp Trong khoa học máy tính và trong toán học, một thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng theo thứ tự tăng hoặc giảm). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số. - Sắp xếp ổn định. - Sắp xếp so sánh. Một số thuật toán sắp xếp. Sắp xếp nổi bọt. Sắp xếp chèn. Sắp xếp chọn. * Sắp xếp trộn. Sắp xếp vun đống. Sắp xếp nhanh. Sắp xếp kiểu chọn. * Giải thuật:Đây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau: Đầu tiên chọn phần tử nhỏ nhất trong n phần tử từ danh sách X[1]…X[n] và hoán vị nó với phần tử X[1]. Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ danh sách X[2]… X[n] và hoán vị nó với X[2]. Tổng quát ở bước thứ i, chọn phần tử có khoá nhỏ nhất trong n-i+1 phần tử từ danh sách X(i)… X(n) và hoán vị nó với X(i). Sau n-1 bước này thì mảng đã được sắp xếp.Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp. Tư tưởng: Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2.Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy. Các bước tiến hành Bước 1: i=1 Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n] Bước 3: Hoán vị a[min] và a[i] Bước 4: Nếu i link; while ( temp2 != NULL ) { if(min -> data > temp2 -> data) { min = temp2; prev = temp1; } temp1 = temp2; temp2 = temp2-> link; } if(prev == NULL) p = min -> link; else prev -> link = min -> link; min -> link = NULL; if( q == NULL) q = min; else { temp1 = q; while( temp1 -> link != NULL) temp1 = temp1 -> link; temp1 -> link = min; } } return (q); } Giới hạn : chương trình chỉ cho phép sắp xếp một danh sách liên kết là các số. 4.Kết luận Cùng một mục đích sắp xếp như nhau mà có rất nhiều phương pháp và kỹ thuật giải quyết khác nhau. Các phương pháp sắp xếp đơn giản đã thể hiện ba kỹ thuật cơ sở của sắp xếp (dựa vào phép so sánh giá trị khóa) cấp độ lớn của thời gian thực hiện chung là O(n2) , vì vậy chỉ nên sử dụng chúng khi n nhỏ. Các giải thuật cải tiến như QUICK_SORT ,HEAP_SORT đã đạt được hiệu quả cao : thường được sử dụng khi n lớn. Việc khẳng định một kỹ thuật sắp xếp nào đó nói trên luôn luôn tốt hơn mọi kỹ thuật khác là một điều không nên. Việc chọn một phương pháp sắp xếp thích hợp thường tùy thuộc vào từng yêu cầu, từng điều kiện cụ thể. Sắp xếp một danh sách liên kết đã góp phần đơn giản hoá các công việc khác về danh sách liên kết như : tìm kiếm, khởi tạo, xoá, chèn…