Bài giảng Ngôn ngữ lập trình C - Chương 8: Danh sách móc nối

Mời các bạn tham khảo "Bài giảng Ngôn ngữ lập trình C - Chương 8: Danh sách móc nối" để nắm bắt được những nội dung về danh sách liên kết đơn, stack và queue. Đây là tài liệu tham khảo hữu ích dành cho các bạn đang học và nghiên cứu về Công nghệ thông tin.
Nội dung trích xuất từ tài liệu:
Bài giảng Ngôn ngữ lập trình C - Chương 8: Danh sách móc nối CHƯƠNGVIII DANHSÁCHMÓCNỐI Ta thương sử dụng mảng cấu trúc để xử lývới nhóm dữ liệu. Đây là một cách tiếp cận đúngkhitabiếttrướcchínhxácsốcáccấutrúccầncó.Tuy nhiên, khi con số này không rõ ràng, mãng sẽtrở nên khá tốn kém vì chúng phải được cấp phátđủbộnhớđểhoạtđộng.Bốnhớnàyđượcđăngkývà sẽ không dành cho nhứng tác vụ khác ngay cảkhitachỉdùngmộtsônhỏcácphầntửmảng. Phương hướng giải quyết cho vấn đề này làchophépcấpphátbộnhớchomộtcấutrúcmớikhicầnthiết. C cho phép ta thực hiện điều này thông qua cáhc cấpphátbộnhớđộngbằng: malloc()vàcalloc() Nhưng các cấu trúc nếu được cấp pháp xong sẽ khôngcóđảmbáonàorằngcáccấutrúcsẽ được đặt liên tiếp nhau trong bộ nhớ. Do đó điều cần thiếtlàkỹthuật đểnốikếttấtcảcáccấutrúclại vớinhau. Phương cách thông dụng để kết nối các phần tử đólạilàdùngdanhsáchliênkết(Linkedlist)I. Danhsáchliênkếtđơn:1. Địnhnghĩa Cúpháp: struct { ; struct* } Vídụ:Địnhnghĩamộtdanhsáchliênkếtđể chứacácsốnguyên. structPoint { intinfo; structPoint*Next; };2. Cácphéptoántrêndanhsáchliênkếta. Cấpphátbônhớchobiếncontrỏmới Cúpháp: Point_New=(structPoint_Name*)malloc (sizeof(structPoint_Name)Vídụ: typedefstructPointPOINT; POINTHead,Last,p; CreatNode() { p=(POINT*)malloc(POINT) if(Head==(POINT*)NULL) Head=Last=p; else { Last=Head; while(Last>Next!=(POINT*)NULL) Last=Last>Next; Last>Next=p; Last=p; } printf(“ InputinformationforNode”); scanf(“%d”,p>.info); Last>Next=(POINT*)NULL; return;}b. Xoámộtcontrỏ: Cúpháp: free(Point_Variable) Giảiphóngvùngnhớđượctrỏbởi Point_Variablec. Cácphéptoánthươngdùngtrongdanhsáchliên kết  Tạomộtphầntưcủadanhsách Điềuphảilàmlàcấpphápbộnhớchocấutrúc vàtrảvềcontrỏtrỏđếnvùngnhớnày. Vídụ:POINT *CreatNode(){ POINT *p; p=(POINT*)malloc(sizeof(POINT)); if(p==NULL) { printf(“Mallocfalled. ”); exit(1); } printf(“InputdataforNodeinfo=”); scanf(“%d”,p>info); p>Next=NULL returnp;}Bổsungphầntưvàodanhsách HàmCreatNode()chỉcấpphátbộnhớnhưngnókhôngnốiphầntửnàyvàodanhsách.Đểlàmđiềunày,tacầnthêmmộthàmnữa,gọilàhàmAddNode().Đượcđịnhnghĩanhưsau:staticPOINT*Head;voidAddNode(POINT*e){ POINT*p; if(Head==NULL) { Head=e; return; } for(p=Head;p>Next!=NULL;p=p>Next); p>Next=e; }Chúý: Biến Head là con trỏ trỏ đến đầu danh sách, nên cần được khai báo đầu chương trình.(Sau phần khaiđịnhnghĩakiểucontrỏ). Chènphầntưvàodanhsách Đểchènphầntửvàodanhsáchliênkết,taphải chỉrỏphầntửmớisẽđượcchènvàovịtrínào.Sau đâylàhàmsẽthựchiệncôngviệctrên.voidInsertNode(POINT*p,POINT*q){if(p=NULL||q=NULL||p==q||q>Next==p) {printf(“CannotInsert ”); return; }p>Next=q>Next;q>Next=p;}; Xoáphầntưvàodanhsách Xoámộtphầntửkhỏidanhsáchliênkếtđơn, tacầnphảitìmphầntửtrướcphầntửcầnxoáđể nhằmmụcđíchnốilạivớiphầntửsauphầntử cầnxoá.Tadùnghàmfree()đểgiảiphốngbộnhớ chiếmbởiphầntửbịxoá.Cóthểxâydưnglà: voidDeleteNode(POINT*goner) { POINT*p; p=Head; if(goner==Head) Head=goner>Next; else {while(p!=NULL&&p>Next!=goner) p=p>Next; if(p=NULL) { printf(“CannotfindNode ”); return; } p>Next=p>Next>Next; }; free(goner)};Tìmphầntưvàodanhsách ThậtkhótạomộthàmFindNode()tổngquát,bởivìkhitìmkiếmthìtaphảidựavàomộttrongnhữngtrườngdữliệucủacấutrúc,điềunàyphụthuộc vào cấu trúc dang sử dụng. Để viết hàmFindNode()tổngquáttaphảisửdụngcontrỏtrỏđếnhàm. VớicấutrúctrêntaxâydựnghàmFindNode()nhưsau:POINT*FindNode(int*n) { POINT*p; for(p=Head;p!=NULL;p=p>Next) if(p>Info=n) returnp; returnNULL; };II. Danhsáchđaliênkết Địnhnghĩa: Cúpháp: struct { ; struct*,; }Vídụ:Địnhnghĩamộtdanhsáchliênkếtđểchứ ...