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),... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Ngọc Như LoanGV:ĐỗNgọcNhưLoanDanhsáchliênkếtđơnDanhsáchliênkếtképDanhsáchliênkếtDanhsáchliênkếtđơn Danhsáchliênkếtđơnlàmộttậpcácnút biểudiễncấutrúcdữliệugồmcácđốitượng đượcsắpđặttheomộttrậttựtuyếntính Trậttựtuyếntínhtrongdanhsáchliênkết đượcxácđịnhbởicácpointerkếthợpvớimỗi đốitượng Danhsáchliênkếtcungcấpmộtsựbiểu diễnmềmdẻovàđơngiảnchocáctậpđộng, hỗtrợcácthaotácnhưtìmkiếm,chèn,xóa v.v Vídụvềmộtdanhsáchliênkếtđơn MỗinútxtrongDSlưutrữmộtđốitượngcó mộtkhóa(cóthểcóthôngtinkhác)vàmột pointernextchỉđếnnút(đốitượng)kếtiếp Nếunext[x]=NULL,thìxlànútcuốicùngcòn gọilàđuôicủadanhsách DanhsáchLlàrỗngkhiL=NULLCácthaotáctrêndanhsáchliênkết ListInitialize(L) ListSearch(L,k) ListInsert(L,k) ListDelete(L,k) ListWalk(L)ĐỊNHNGHĨADANHSÁCHLIÊNKẾTĐƠNTRONGC++ Danhsáchcácđốitượngcókhóalàsố nguyêntypedefstructCELL*LIST;structCELL{ intkey; LISTnext; };LISTL;ListInitializevoid ListInitialize(LIST &L){ L=NULL;}ListSearch ThaotácListSearch(L,k)tìmmộtđốitượng cókhóaktrongdanhsáchL Nếucóđốitượngcókhóak,thủtụcsẽtrảvề mộtpointerchỉđếnđốitượngnày Nếukhôngcóđốitượngnàocókhóabằngk trongdanhsách,thủtụctrảvềNULLListSearchLIST ListSearch(LIST L, int k){ LIST x; x=L; while(x!=NULL && x->key!=k) x=x->next; return x;}ListInsert ThaotácListInsert(L,k)thựchiệnđơngiản bằngcáchchènđốitượngxcókhóakvào đầucủaLListInsertvoid ListInsert(LIST &L, int k){ LIST x; x=new(CELL); x->key=k; x->next=L; L=x;}ListDelete ThaotácListDelete(L,k)xóađốitượngxcó khóakkhỏiL Đượcthựchiệnbằngcáchtìmxvàcậpnhật lạicáccontrỏnútyđitrướcxđểloạixra khỏidanhsáchListDeletevoid 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 {ListWalk(DuyệtDS)void ListWalk(LIST L){ if(L!=NULL) { coutĐỘPHỨCTẠPCÁCTHAOTÁC ListSearch(L,k)cóđộphứctạptrungbình T(n)=O(n) ListInsert(L,k)cóđộphứctạpT(n)=O(1) ListDelete(L,k)cóđộphứctạptrungbình T(n)=O(n)DANHSÁCHLIÊNKẾTKÉP Danhsáchliênkếtképlàcấutrúcdữliệu trongđócácđốitượngđượcsắpđặttheo mộttrậttựtuyếntính Trậttựtuyếntínhtrongdanhsáchliênkết képđượcxácđịnhbởimộtcặppointertrong mỗiđốitượngĐỊNHNGHĨADANHSÁCHLIÊNKẾTKÉPTRONGC++ Danhsáchcácđốitượngcókhóalàsố nguyêntypedef struct CELL *LIST;struct CELL { int key; LIST prev, next; };LIST L;ListInitializevoid ListInitialize(LIST &L){ L=NULL;}ListSearch ThaotácListSearch(L,k)tìmmộtphầntửcó khóaktrongdanhsáchL Nếucóphầntửcókhóak,thủtụcsẽtrảvề mộtpointerchỉđếnphầntửnày Nếukhôngcóđốitượngnàocókhóabằngk trongdanhsách,thủtụctrảvềNULLListSearchLIST ListSearch(LIST L, int k){ LIST x; x=L; while(x!=NULL && x->key!=k) x=x->next; return x;}