Giáo trình cấu trúc dữ liệu part 5

Tham khảo tài liệu giáo trình cấu trúc dữ liệu part 5, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình cấu trúc dữ liệu part 5Cấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản void Delete_List (Position p, DoubleList *DL){ if (*DL == NULL) printf(”Danh sach rong”); else{ if (p==*DL) (*DL)=(*DL)->Next; //Xóa phần tử đầu tiên của danh sách nên phải thay đổi DL p->Previous->Next=p->Next; else if (p->Next!=NULL) p->Next->Previous=p->Previous; free(p); } }Thêm phần tử vào danh sách liên kết kép Để thêm một phần tử x vào vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta cũngcần phân biệt mấy trường hợp sau: Danh sách rỗng, tức là DL = NULL: trong trường hợp này ta không quan tâm đến giá trịcủa p. Để thêm một phần tử, ta chỉ cần cấp phát ô nhớ cho nó, gán giá trị x vào trườngElement của ô nhớ này và cho hai con trỏ previous, next trỏ tới NULL còn DL trỏ vào ô nhớnày, các thao tác trên có thể viết như sau: DL=(Node*)malloc(sizeof(Node)); DL->Element = x; DL->Previous=NULL; DL->Next =NULL; Nếu DL!=NULL, sau khi thêm phần tử x vào vị trí p ta có kết quả như hình II.18 p->Previous p p->Next Hình II.17: Danh sách trước khi thêm phần tử x 65 TrangCấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản p->Previous p p->Next Hình II.18: Danh sách sau khi thêm phần tử x vào tại vị trí p (phần tử tại vị trí p cũ trở thành phần tử sau của x) Lưu ý: các kí hiệu p, p->Next, p->Previous trong hình II.18 để chỉ các ô trước khi thêmphần tử x, tức là nó chỉ các ô trong hình II.17. Trong trường hợp p=DL, ta có thể cập nhật lại DL để DL trỏ tới ô mới thêm vào hoặc đểnó trỏ đến ô tại vị trí p cũ như nó đang trỏ cũng chỉ là sự lựa chọn trong chi tiết cài đặt. void Insert_List (ElementType X,Position p, DoubleList *DL){ if (*DL == NULL){ (*DL)=(Node*)malloc(sizeof(Node)); (*DL)->Element = X; (*DL)->Previous =NULL; (*DL)->Next =NULL; } else{ Position temp; temp=(Node*)malloc(sizeof(Node)); temp->Element=X; temp->Next=p; temp->Previous=p->Previous; if (p->Previous!=NULL) p->Previous->Next=temp; p->Previous=temp; } } 66 TrangCấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bảnTỔNG KẾT CHƯƠNG Chương mô tả các cấu trúc dữ liệu trừu tượng và các giải thuật cài đặt các phép toán này.Tuy nhiên, tùy theo bài toán cụ thể và mức độ thay đổi của dữ liệu cũng mà ta lựa chọn cáccấu trúc dữ liệu cho phù hợp. Trong chương này, phần cơ bản nhất là danh sách đặc và liênkết, còn các cấu trúc khác chỉ là sự biến tấu của cấu trúc này. Trong chương này cũng đề cậpđến các ứng dụng cụ thể của từng cấu trúc dữ liệu trừu tượng bên ngoài thực tế. Cách cài đặtcác cấu trúc dữ liệu trừu tượng khác nhau và có vận dụng cấu trúc đã có để mô tả cho mộtcấu trúc dữ liệu trừu tượng mới. 67 TrangCấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản BÀI TẬP1. Viết khai báo và các chương trình con cài đặt danh sách bằng mảng. Dùng cácchương trình con này để viết:a. Chương trình con nhận một dãy các số nguyên nhập từ bàn phím, lưu trữ nó trongdanh sách theo thứ tự nhập vào.b. Chương trình con nhận một dãy các số nguyên nhập từ bàn phím, lưu trữ nó trongdanh sách theo thứ tự ngược với thứ tự nhập vào.c. Viết chương trình con in ra màn hình các phần tử trong danh sách theo thứ tự của nótrong danh sách.2. Tương tự như bài tập 1. nhưng cài đặt bằng con trỏ.3. Viết chương trình con sắp xếp một danh sách chứa các số nguyên, trong các trườnghợp:a. Danh sách được cài đặt bằng mảng (danh sách đặc).b. Danh sách được cài đặt bằng con trỏ (danh sách liên kết).4. Viết chương trình con thêm một phần tử trong danh sách đã có thứ tự sao cho ta vẫncó một danh sách có thứ tự bằng cách vận dụng các phép toán cơ bản trên danh sách5. Viết chương trình con tìm kiếm và xóa một phần tử trong danh sách có thứ tự. ...