TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Ngọc Như Loan

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách (List)" cung cấp cho người học các kiến thức: Danh sách liên kết đơn, các thao tác trên danh sách liên kết, listInsert, listwalk (duyệt ds),. . | GV: Đỗ Ngọc Như Loan Danh sách liên kết đơn Danh sách liên kết kép Danh sách liên kết vòng Danh sách liên kết đơn Danh sách liên kết đơn là một tập các nút biểu diễn cấu trúc dữ liệu gồm các đối tượng được sắp đặt theo một trật tự tuyến tính Trật tự tuyến tính trong danh sách liên kết được xác định bởi các pointer kết hợp với mỗi đối tượng Danh sách liên kết cung cấp một sự biểu diễn mềm dẻo và đơn giản cho các tập động, hỗ trợ các thao tác như tìm kiếm, chèn, xóa Ví dụ về một danh sách liên kết đơn Mỗi nút x trong DS lưu trữ một đối tượng có một khóa (có thể có thông tin khác) và một pointer next chỉ đến nút (đối tượng) kế tiếp Nếu next[x]= NULL, thì x là nút cuối cùng còn gọi là đuôi của danh sách Danh sách L là rỗng khi L = NULL Các thao tác trên danh sách liên kết ListInitialize (L) ListSearch (L, k) ListInsert (L, k) ListDelete (L, k) ListWalk (L) ĐỊNH NGHĨA DANH SÁCH LIÊN KẾT ĐƠN TRONG C++ Danh sách các đối tượng có khóa là số nguyên typedef struct CELL *LIST; struct CELL { int key; LIST next; }; LIST L; ListInitialize void ListInitialize(LIST &L) { L=NULL; } ListSearch Thao tác ListSearch(L, k) tìm một đối tượng có khóa k trong danh sách L Nếu có đối tượng có khóa k, thủ tục sẽ trả về một pointer chỉ đến đối tượng này Nếu không có đối tượng nào có khóa bằng k trong danh sách, thủ tục trả về NULL ListSearch LIST ListSearch(LIST L, int k) { LIST x; x=L; while(x!=NULL && x->key!=k) x=x->next; return x; } ListInsert Thao tác ListInsert(L, k) thực hiện đơn giản bằng cách chèn đối tượng x có khóa k vào đầu của L ListInsert void ListInsert(LIST &L, int k) { LIST x; x=new(CELL); x->key=k; x->next=L; L=x; } ListDelete Thao tác ListDelete(L, k) xóa đối tượng x có khóa k khỏi L Được thực hiện bằng cách tìm x và cập nhật lại các con trỏ nút y đi trước x để loại x ra khỏi danh sách ListDelete void ListDelete(LIST &L,int k) { LIST x, y; if(L!= NULL) { y= NULL; x =L; while(x!=NULL && x->key!=k) { y=x; x=x->next; } if(x!=NULL) //Tìm thấy { if(y==NULL) L=x->next; //nút .

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Danh sách
• Danh sách liên kết đơn
• Danh sách liên kết
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cơ sở dữ liệu
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Kiểu dữ liệu cây
• Phân loại cây
• Bài giảng Maple
• Cấu trúc dữ liệu trong maple
• Cấu trúc dữ liệu dãy
• Cấu trúc dữ liệu tập hợp
• Cấu trúc dữ liệu mảng
• Cấu trúc dữ liệu bảng
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Cấu trúc dữ liệu cây AA
• Cây AA
• Biến đổi hiệu chỉnh cây AA
• Thao tác duyệt cây
• Cấu trúc dữ liệu ngăn xếp
• Hàng đợi
• Biểu thức toán học
• Cây nhị phân
• Cấu trúc dữ liệu nâng cao
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu tuyến tính
• Cách dùng con trỏ
• Cài đặt danh sách
• Các kiểu dữ liệu cơ bản
• Giải thuật tìm tuyến tính