Nhập xuất danh sách liên kết đơn c++
Show
nut *p = (nut *)malloc(sizeof(nut)); //1. Khai báo và cấp phát vùng nhớ cho p Giả sử danh sách ban đầu có 3 nút có giá trị lần lượt là 5, 3 và 6. Để thêm nút có giá trị 4 vào đầu danh sách ta cần thực hiện lần lượt 4 bước sau:
Code: void ThemDau(int giatri){ nut *p; p=(nut* )malloc(sizeof(nut)); // 1.Cấp phát ô nhớ cho p p->data=giatri; // 2.Gán giá trị cho p p->next=dau; // 3.Gán p vào đầu con trỏ dau=p; // 4.Cập nhật con trỏ } Có nhiều cách để thêm một nút mới vào cuối danh sách. Dưới đây là cách có sử dụng thêm con trỏ cuoi (luôn trỏ đến phần tử cuối cùng của danh sách). Nếu không có con trỏ này, trước mỗi lần thêm nút mới ta phải "duyệt" toàn bộ danh sách để tìm được con trỏ trỏ đến phần tử cuối cùng (chính là con trỏ cuoi). Khi đã có được con trỏ cuoi, để gắn nút mới vào danh sách ta chỉ việc gắn nút này vào ngay sau nút được trỏ bởi cuoi.
code: void ThemCuoi(int giatri) { nut *p = (nut *)malloc(sizeof(nut)); //1.Khai báo và cấp phát ô nhớ cho p p->data = giatri; //2. Gán giá trị cho p p->next = NULL; if (dau == NULL) //3.Gắn p vào danh sách dau = p; else cuoi->next = p; cuoi = p; //4.Cập nhật con trỏ cuối } Muốn hiển thị ta cần phải duyệt danh sách. Để duyệt danh sách, ta cần thêm một con trỏ p. Ban đầu p trỏ đến nút đầu tiên (p=dau). Ta sẽ "lặp" việc di chuyển p cho đến khi hết danh sách (p=NULL). Đoạn mã cho việc duyệt danh sách có thể viết như sau: Code: void HienThi(){ nut *p; //1.Khai báo p p=dau; //2.Gán p vào đầu để quản lí DS while(p != NULL){ //3.Nếu danh sách rỗng printf("%d",p->data); p=p->next; //4.Duyệt p } } #include <stdio.h> #include <stdlib.h> typedef struct SV{ int data; struct SV* next; } nut; nut* dau,* cuoi; void ThemDau(int giatri){ nut *p; p=(nut* )malloc(sizeof(nut)); p->data=giatri; p->next=dau; dau=p; } void ThemCuoi(int giatri) { nut *p = (nut *)malloc(sizeof(nut)); p->data = giatri; p->next = NULL; if (dau == NULL) dau = p; else cuoi->next = p; cuoi = p; } void HienThi(){ nut *p; p=dau; while(p != NULL){ printf("%d",p->data); p=p->next; } } int main(int argc, char *argv[]) { int n,i,s; printf("Nhap vao tong so: "); scanf("%d",&n); for(i=0;i
Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là cực kỳ quan trọng để hiểu cách danh sách liên kết hoạt động, vì vậy nếu bạn chưa có kiến thức về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một chút về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần nội dung cài đặt danh sách liên kết của bài viết này sẽ chỉ trình bày về danh sách liên kết đơn. I. Danh Sách Liên Kết Đơn C++Danh sách liên kết đơn (Single Linked List) là một cấu trúc dữ liệu động, nó là một danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách. Mỗi phần tử (được gọi là một node hay nút) trong danh sách liên kết đơn là một cấu trúc có hai thành phần:
Đặc điểm của danh sách liên kết đơn Do danh sách liên kết đơn là 1 cấu trúc dữ liệu động, được tạo nên nhờ việc cấp phát động nên nó có một số đặc điểm sau đây:
Và do tính liên kết của phần tử đầu và phần tử đứng sau nó trong danh sách liên kết đơn, nó mang những đặc điểm sau:
II. Nối 2 Danh Sách Liên Kết Đơn C++Bài tập C: Nối hai danh sách liên kết đơn Bài tập C này giúp bạn làm quen dần với cách tạo danh sách liên kết đơn và cách nối hai danh sách liên kết đơn trong C. Để giải bài tập này, mình sử dụng cấu trúc struct trong C. Chương trình C Dưới đây là chương trình C để giải bài tập nối hai danh sách liên kết đơn trong C: #includeBiên dịch chương trình C trên sẽ cho kết quả: III. Đảo Ngược Danh Sách Liên Kết Đơn C++Đảo ngược Danh sách liên kết Với hoạt động này, bạn cần phải cẩn thận. Chúng ta cần làm cho nút đầu (head) trỏ tới nút cuối cùng và đảo ngược toàn bộ danh sách liên kết. Đầu tiên, chúng ta duyệt tới phần cuối của danh sách. Nút này sẽ trỏ tới NULL. Bây giờ điều cần làm là làm cho nút cuối này trỏ tới nút phía trước của nó. Chúng ta phải đảm bảo rằng nút cuối cùng này sẽ không bị thất lạc, do đó chúng ta sẽ sử dụng một số nút tạm (temp node – giống như các biến tạm trung gian để lưu giữ giá trị). Tiếp theo, chúng ta sẽ làm cho từng nút bên trái sẽ trỏ tới nút trái của chúng. Sau đó, nút đầu tiên sau nút head sẽ trỏ tới NULL. Chúng ta sẽ làm cho nút head trỏ tới nút đầu tiên mới bởi sử dụng các nút tạm. Bây giờ Danh sách liên kết đã bị đảo ngược. Chương trình minh họa Danh sách liên kết (Linked List) trong C #includeKết quả Biên dịch và chạy chương trình C trên sẽ cho kết quả: IV. Nhập Xuất Danh Sách Liên Kết Đơn C++Tùy theo kiểu danh sách bạn là gì mà cách nhập xuất khác nhau. Bài viết này mình nhập xuất số nguyên nên có phần đơn giản hơn Mình sẽ nhập vào phần tử cho danh sách liên kết đơn bằng con trỏ. Nếu nhập vào bằng 0 thì sẽ dừng nhập. Thêm phần tử vào danh sách mình sử dụng hàm chèn cuối Insert_Last // Hàm nhập danh sách số nguyên từ bàn phím void Input(List &L){ Init(L); item x; int i=1; do{ cout<<"\nNhap phan tu thu "<>x; if (x!=0){ Insert_Last(L,x); i++; } } while (x!=0); // Nếu nhập x = 0 thì dừng nhập //Ban co the dung cach khacV. Sắp Xếp Danh Sách Liên Kết Đơn C++Ở phần sắp xếp phần tử trong danh sách liên kết đơn, mình sẽ thực hiện sắp xếp bằng cách so sánh và đổi thay giá trị data chứ không thay đổi Node. Tức là chỉ so sánh các giá trị data rồi sắp xếp, các Node vẫn giữ nguyên không dịch chuyển. Thao tác sắp xếp trong danh sách về căn bản tương tự như những thuật toán sắp xếp khác, đơn giản chỉ là duyệt từng phần tử rồi so sánh với nhau, sau ấy hoán đổi vị trí của chúng. Đầu tiên ta có một vòng lặp For sử dụng biến pTmp để lặp từng phần tử trong danh sách, vòng lặp For thứ hai sử dụng biến pTmp2 để lặp từng phần tử trong danh sách. Nếu pTmp > pTmp2 thì hoán đổi vị trí giữa chúng, nếu pTmp < pTmp2 thì tiếp tục so sách những phần tử tiếp theo, cứ như vậy cho tới hết danh sách. /* sắp xếp trong danh sách liên kết đơn theo thứ tự tăng dần */ void SortList(SingleList &list) { // for loop thứ nhất for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) { //for loop thứ hai for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { if(pTmp->data>pTmp2->data) // nếu giá trị trước > giá trị sau thì hoán đổi hai vị trí { int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp; } } } }VI. Cài Đặt Danh Sách Liên Kết Đơn C++Trước lúc đi vào cài đặt danh sách liên kết đơn, hãy chắc chắn rằng bạn đã nắm vững phần con trỏ và cấp phát động trong C++. Do danh sách liên kết đơn là một cấu trúc dữ liệu động, nếu bạn không nắm vững con trỏ và cấp phát động sẽ rất khó để bạn hiểu được bài viết này. Nếu bạn cảm thấy chưa tự tin, hãy dành ít thời gian để xem bài viết này của mình. Còn bây giờ thì bắt đầu thôi! Tạo nodeDanh sách liên kết đơn được tạo thành từ nhiều node, do đó, chúng ta sẽ cùng đi từ node trước. Một node gồm hai thành phần là thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu có thể là kiểu dữ liệu có sẵn hoặc bạn tự định nghĩa (struct hay class…), trong bài viết này để đơn giản mình sẽ dùng kiểu int cho phần dữ liệu. Thành phần liên kết là địa chỉ đương nhiên sẽ là con trỏ, con trỏ này trỏ đến node tiếp theo, do đó, con trỏ này là con trỏ trỏ vào 1 node. struct Node { int data; Node* next; };Để tạo một node mới, ta thực hiện cấp phát động cho node mới, khởi tạo giá trị ban đầu và trả về địa chỉ của node mới được cấp phát. Tạo danh sách liên kết đơnTa đã có được thành phần tạo nên danh sách liên kết đơn là node, tiếp theo chúng ta cần quản lý chúng bằng phương pháp biết được phần tử đầu và cuối. Vì mỗi phần tử đều liên kết với phần tử kế vậy nên tả chỉ cần biết phần tử đầu và cuối là có thể quản lý được danh sách này. Vậy đơn giản ta cần tạo 1 cấu trúc lưu trữ địa chỉ phần tử đầu (head) và phần tử cuối (hay phần tử đuôi tail). struct LinkedList { Node* head; Node* tail; };Khi mới tạo danh sách, danh sách sẽ không có phần tử nào, do đó head và tail không trỏ vào đâu cả, ta sẽ gán chúng bằng NULL. Ta xây dựng hàm tạo danh sách như sau: void CreateList(LinkedList& l) { l.head = NULL; l.tail = NULL; }Bây giờ để tạo một danh sách, ta làm như sau: LinkedList list; CreateList(list); // Gán head và tail bằng NULLThêm phần tử vào danh sáchThêm vào đầu Để thêm node vào đầu danh sách, trước tiên ta cần kiếm tra xem danh sách đó có rỗng hay không, nếu danh sách rỗng, ta chỉ cần gán head và tail của danh sách bằng node đó. Ngược lại nếu danh sách không rỗng, ta thực hiện trỏ thành phần liên kết vào head, sau đó gán lại head bằng node mới. Như trong hình trên, chúng ta thêm node có data bằng 0 vào danh sách. Ta thực hiện trỏ next của node đó vào head của danh sách (chính là node đầu tiên của danh sách có data bằng 1), sau đó ta trỏ head vào node có data 0 vừa được thêm. Vậy là phần tử đó đã nằm ở đầu danh sách rồi. Thêm vào cuối Tương tự, để thêm node vào cuối danh sách, đầu tiên ta đánh giá xem danh sách rỗng hay không, rỗng thì gán head và tail đều bằng node mới. Nếu không rỗng, ta thực hiện trỏ tail->next vào node mới, sau đó gán lại tail bằng node mới (vì bây giờ node mới thêm chính là tail). Trong hình trên, chúng ta thực hiện thêm node có data bằng 6 vào danh sách. Tail hiện tại là node có data 5, thực hiện gán tail->next bằng node mới để nối thêm nó vào đuôi danh sách, lúc này node mới trở thành phần tử cuối danh sách nên ta gán tail lại bằng node mới. Thêm vào sau node bất kỳ Để thêm một node p vào sau node q bất kỳ, đầu tiên ta cần kiếm tra xem node q có NULL hay không, nếu node q là NULL tức là danh sách rỗng, vậy thì ta sẽ thêm vào đầu danh sách. Nếu node q không NULL, tức là tồn tại trong danh sách, ta thực hiện trỏ p->next = q->next, sau đó q->next = p. Tiếp theo chúng ta kiểm tra xem node q trước đó có phải là node cuối hay không, nếu node q là node cuối thì thêm p vào, p sẽ thành node cuối nên ta gán lại tail = p. Trong hình trên, ta thêm node có data bằng 4 (node p) vào sau node có data bằng 3 (node q). Ta trỏ next của node p vào next của node q tức là node có data bằng 5, sau đó trỏ next của node q vào node p vậy là node p đã được thêm vào danh sách. Xóa phần tử khỏi danh sáchXóa ở đầu Để xóa phần tử ở đầu danh sách, ta kiểm tra xem danh sách đó có rỗng hay không, nếu rỗng, ta không cần xóa, trả về kết quả là 0. Nếu danh sách không rỗng, ta thực hiện lưu node head lại, sau đó gán head bằng next của node head, sau đó xóa node head đi. Tiếp theo ta cần kiểm tra xem danh sách vừa bị xóa đi node head có rỗng hay không, nếu rỗng ta gán lại tail bằng NULL luôn sau đó trả về kết quả 1. Lưu ý trước khi xóa node head đi, ta dùng biến tham chiếu x để lưu trữ lại giá trị của node bị hủy để sử dụng. Trong hình trên, mình thực hiện xóa node đầu tiên có data bằng 0. Mình trỏ head đến next của node 0 (hiện đang là head), thì head lúc này sẽ là node 1, sau đó mình hủy đi node 0 là được. Xóa ở sau node bất kỳ Để xóa một node p sau node q bất kỳ, ta kiểm tra xem node q có NULL hay không, nếu node q NULL thì không tồn tại trong danh sách, do đó trả về 0, không xóa. Nếu node q khác NULL nhưng next của q là NULL, tức là p bằng NULL thì không xóa, trả về 0 (do sau q không có node nào cả, q là tail). Nếu node p tồn tại, ta thực hiện kiểm tra xem node p có phải là tail hay không, nếu node p là tail thì gán lại tail là q, tức là node trước đó để xóa node p đi. Trong hình trên, ta thực hiện xóa node có data 3 (node p) sau node có data 2 (node q). Ta trỏ next của node q vào next của node p tức là node có data 4, sau đó xóa node p đi là xong. Duyệt danh sách và in Sau khi có các thao tác thêm, xóa, chúng ta có thể in ra danh sách để kiểm tra xem có hoạt động đúng hay không. Để in danh sách, ta duyệt từ đầu đến cuối danh sách và in ra trong lúc duyệt. Ta gán một node bằng head, sau đó kiểm tra xem node đó có NULL hay không, không thì in ra data của node đó, sau đó gán tiếp node đó bằng next của chính nó tức node đó bây giờ là node tiếp theo, cứ như vậy cho đến hết. Lấy giá trị node bất kỳ Để lấy giá trị phần tử trong danh sách, ta thực hiện duyệt tương tự như khi in phần tử. Ta sẽ tạo một biến đếm để biết vị trí hiện tại, duyệt qua các node cho đến khi node bằng NULL hoặc biến đếm bằng với vị trí node cần lấy. Kiểm tra xem nếu node khác NULL và biến đếm bằng vị trí cần lấy, ta sẽ trả về địa chỉ của node đó, ngược lại trả về NULL (danh sách rỗng hoặc là vị trí cần lấy nằm ngoài phạm vi của danh sách). Tìm kiếm phần tử trong danh sách Ý tưởng tìm kiếm phần tử cũng là duyệt danh sách, nếu như chưa tìm thấy thì tiếp tục duyệt. Sau khi kết thúc duyệt, ta chỉ cần kiểm tra xem node duyệt có bằng NULL hay không, nếu không tức là đã tìm thấy, ta sẽ trả về địa chỉ của node đó. Đếm số phần tử của danh sách Đếm số phần tử thì cũng tương tự, ta áp dụng duyệt từ đầu đếm cuối và đếm số node. Xóa danh sách Để xóa danh sách, ta cần hủy tất cả các node tức là duyệt và hủy từng node. Ở đây mình sẽ dùng lại hàm RemoveHead. Đầu tiên, ta gán một node bằng head, kiểm tra nếu node đó khác NULL thì gọi RemoveHead và gán lại node bằng head tiếp, cứ lặp như vậy cho đến khi node đó NULL thì thôi. Sau khi xóa hết tất cả phần tử thì gán lại tail bằng NULL. VII. Code Danh Sách Liên Kết Đơn Sinh Viên C++Đề bài: Xây dựng chương trình quản lý sinh viên bằng DSLK đơnCho 1 sinh viên có cấu trúc: mã (int), tên (char *). Dùng danh sách liên kết đơn với con trỏ phead để thao tác:
Chương trình quản lý sinh viên sử dụng DSLK đơnChúng ta sẽ lần lượt tạo cấu trúc sinh viên, cấu trúc danh sách liên kết đơn và các thao tác liên quan. Đầu tiên chúng ta buộc phải tạo một cấu trúc sinh viên với mã số sinh viên ma và tên sinh viên ten. //tao cau truc sinh vien struct SinhVien { int ma; char ten[150]; };Tiếp đến tạo cấu trúc dữ liệu của danh sách liên kết đơn với giá trị data và con trỏ pNext. Khởi tạo giá trị cho pHead và pTail bằng NULL. //tao cau truc danh sach lien ket don struct Node { SinhVien *data; Node *pNext; }; struct SingleList { Node *pHead; }; //khoi tao danh sach lien ket don void Initialize(SingleList *&list) { list=new SingleList; list->pHead=NULL; }Tạo 1 hàm NhapSinhVien() dùng cấu trúc SinhVien để nhập những thông tin của sinh viên như: MSSV và tên sinh viên SinhVien *NhapSinhVien() { SinhVien *sv=new SinhVien; cout<<"Nhap MSSV:"; cin>>sv->ma; cin.ignore(); cout<<"Nhap ho va ten:"; gets(sv->ten); return sv; }Bây giờ chúng ta bắt đầu tạo Node với các thông tin của cấu trúc SinhVien, sau đó thêm Node vào cuối danh sách. //tao node sinh vien Node *CreateNode(SinhVien *sv) { Node *pNode=new Node; if(pNode!=NULL) { pNode->data=sv; pNode->pNext=NULL; } else { cout<<"cap phat bo nho that bai!!!"; } return pNode; } //them node vao cuoi danh sach void InsertLast(SingleList *&list,SinhVien *sv) { Node *pNode=CreateNode(sv); if(list->pHead==NULL) { list->pHead=pNode; } else { Node *pTmp=list->pHead; while(pTmp->pNext!=NULL) { pTmp=pTmp->pNext; } pTmp->pNext=pNode; } }Sau lúc thêm Node vào danh sách ta thực hiện những thao tác theo đề nghị của đề bài. Đầu tiên là việc sắp xếp các sinh viên theo MSSV. Ở bài tìm kiếm và sắp xếp trong danh sách liên kết đơn mình đã giới thiệu các bạn thao tác sắp xếp. Dựa vào đó ta chỉ cần biến đổi một chút sẽ có ngay hàm sắp xếp SortList() theo MSSV. void SortList(SingleList *&list) { for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) { for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { SinhVien *svTmp=pTmp->data; SinhVien *svTmp2=pTmp2->data; if(svTmp2->maTương tự như hàm sắp xếp, để xóa một sinh viên dựa vào tên ta thực hiện vòng lặp while lặp từng phần tử trong danh sách. Nếu phần tử đó trùng với phần tử được nhập vào từ bàn phím ta thực hiện delete phần tử đó ra khỏi danh sách. void RemoveNode(SingleList *&list,int ma) { Node *pDel=list->pHead; if(pDel==NULL) { cout<<"Danh sach rong!"; } else { Node *pPre=NULL; while(pDel!=NULL) { SinhVien *sv=pDel->data; if(sv->ma==ma) break; pPre=pDel; pDel=pDel->pNext; } if(pDel==NULL) { cout<<"khong tim thay MSSV: "<Sau khi thực hiện tạo các thao tác, ta chỉ cần tạo hàm main() và gọi các thao tác đó ra để sử dụng. int main(int argc, char** argv) { SingleList *list; Initialize(list); SinhVien *teo=NhapSinhVien(); InsertLast(list,teo); SinhVien *ty=NhapSinhVien(); InsertLast(list,ty); SinhVien *bin=NhapSinhVien(); InsertLast(list,bin); PrintList(list); SortList(list); cout<<"\nSau khi sap xep:\n"; PrintList(list); cout<<"\Ban muon xoa sinh vien co MSSV: "; int ma; cin>>ma; RemoveNode(list,ma); cout<<"\nSau khi xoa:\n"; PrintList(list); }Full code: #includeKết quả: VIII. Xóa Phần Tử Trong Danh Sách Liên Kết Đơn C++Trong chỉ dẫn này mình sẽ giới thiệu tới các bạn cách xóa Node trong danh sách liên kết đơn. Chúng ta sẽ cùng nhau tìm hiểu 3 ví dụ lúc xóa 1 Node khỏi danh sách liên kết đơn:
+ Xóa Node ở đầu danh sách liên kết đơnTrong trường hợp chúng ta muốn xóa một Node, mà Node đó lại nằm ở đầu danh sách. Đây là một trường hợp đặc biệt, các bạn hãy xem các bước thực hiện sau đây: Giả sử chúng ta có một Node pDel là Node cần xóa và một danh sách liên kết đơn. Bước 1: Vì Node cần xóa ở đầu danh sách, tức là ngay node pHead. Vì vậy chúng ta cần di chuyển pHead từ pDel sang Node kế tiếp: list.pHead = list.pHead -> pNext Bước 2: Sau khi di chuyển pHead sang Node kế tiếp, chúng ta sẽ ngắt mối liên kết giữa pDel với Node phía sau nó: pDel -> pNext = Null. Bước 3: Bây giờ pDel không còn liên kết với bất kì Node nào trong danh sách nữa, chúng ta đã có thể xóa Node này. delete pDel + Xóa Node ở cuối danh sách liên kết đơn.Trong trường hợp Node muốn xóa lại nằm ở cuối danh sách, tương tự như việc xóa ở đầu danh sách. Ta chỉ cần di chuyển pTail về Node trước đó (pPre) và thay đổi pNext = NULL. Sau khi di chuyển pTail về Node trước đó và ngắt mối liên kết giữa pPre với pDel, ta thực hiện xóa Node pDel: delete pDel //Nếu pDel == list.pTail, tức là số cần xóa ở cuối danh sách if(pDel -> pNext == NULL){ list.pTail = pPre; pPre -> pNext = NULL; delete pDel; pDel = NULL; }+ Xóa Node ở giữa danh sách liên kết đơn.Và trường hợp cuối cùng, khi xóa Node mà Node đó không nằm đầu cũng không nằm cuối danh sách, ta thực hiện các bước như sau: Khi ta muốn xóa một Node ở giữa danh sách, đầu tiên ta cần xác định Node cần xóa pDel và Node đứng trước nó pPre. Sau khi xác định được pDel và pPre, ta thay đổi mối liên kết giữa pPre đến pTail (pPre -> pNext = pDel -> pNext) và cho pDel -> pNext == NULL. Các bạn có thể xem hướng mũi tên để biết được các bước thực hiện của nó. Ta có thể xóa Node pDel khi đã ngắt mối liên kết giữa nó với các Node khác: delete pDel // và trường hợp cuối cùng số muốn xóa nằm ở giữa danh sách else{ pPre -> pNext = pDel -> pNext; pDel -> pNext = NULL; delete pDel; pDel = NULL; }+ Ví dụ xóa Node trong danh sách liên kết đơnChúng ta sẽ sử dụng dữ liệu ở ví dụ trước để thực hiện xóa cho ví dụ này, vừa có thể ôn lại kiến thức cũ vừa áp dụng kiến thức mới. Kết quả: IX. Bài Tập Danh Sách Liên Kết Đơn C++Bài tập danh sách liên kết đơn dưới đây là 1 dạng bài tập tổng hợp giúp những bạn ôn luyện lại kiến thức về danh sách liên kết đơn cũng như các kiến thức khác về lập trình C. Sau bài học này, bên cạnh kiến thức về danh sách liên kết đơn, bạn cũng sẽ nắm được:
Đề bài tập danh sách liên kết đơnViết chương trình trong ngôn ngữ C thực hiện các bắt buộc sau:
Yêu cầu:
Lời giải bài tập danh sách liên kết đơn+ Xây dựng các kiểu dữ liệu cần thiết
+ Xây dựng các hàm khởi tạo
Lưu ý: Ta cần cho con trỏ next của Node được khởi tạo bằng NULL, tức là chưa trỏ tới đâu. Tránh trường hợp nó trỏ lung tung trong bộ nhớ.
Lưu ý:
+ Các hàm thao tác với danh sách liên kết Trong bài toán này, chúng ta có các hành động thêm, sửa, xóa Node. Do đó, chúng ta cần xây dựng các hàm sau:
Các hàm này đều là hàm cơ bản của DSLK đã được mình trình bày chi tiết tại bài danh sách liên kết đơn. Do vậy, bạn nào chưa hiểu thì có thể quay lại đọc bài đó trước nha.
# Hàm duyệt danh sách void traverser(Node head){ printf("Danh sach hien tai:\n"); printf("------------------------------------------------------------------------------------------------------------\n"); printf("%10s%50s%20s%20s\n", "Ma Tinh/TP", "Tinh thanh", "Dien tich", "Dan so"); for(Node p = head; p != NULL; p = p->next){ printf("%10d%50s%20f%20d\n", p->city.code, p->city.name, p->city.area, p->city.population); } printf("------------------------------------------------------------------------------------------------------------\n"); }
# Các hàm phục vụ thêm Node // Thêm vào cuối Node addTail(Node head, City value){ Node temp,p;// Khai báo 2 Node tạm temp và p temp = createNode(value);//Gọi hàm createNode để khởi tạo Node temp có next trỏ tới NULL và giá trị là value if(head == NULL){ head = temp; //Nếu linked list đang trống thì Node temp là head luôn } else{ p = head;// Khởi tạo p trỏ tới head while(p->next != NULL){ p = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là Node có next = NULL } p->next = temp;//Gán next của thằng cuối = temp. Khi đó temp sẽ là thằng cuối(temp->next = NULL mà) } return head; } // Thêm vào đầu Node addHead(Node head, City value){ Node temp = createNode(value); // Khởi tạo Node temp với data = value if(head == NULL){ head = temp; // //Nếu linked list đang trống thì Node temp là head luôn }else{ temp->next = head; // Trỏ next của temp = head hiện tại head = temp; // Đổi head hiện tại = temp(Vì temp bây giờ là head mới mà) } return head; } // Thêm vào ở "chỉ số" (bắt đầu từ 0) bất kỳ, nếu muốn thêm theo "vị trí" (bắt đầu từ 1) thì giảm position đi 1 đơn vị Node addAt(Node head, City value, int position){ position = position - 1; // Thêm theo vị trí if(position == 0 || head == NULL){ head = addHead(head, value); // Nếu vị trí chèn là 0, tức là thêm vào đầu }else{ // Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí int k = 1; Node p = head; while(p != NULL && k != position){ p = p->next; ++k; } if(k != position){ // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định chèn cuối // Nếu bạn không muốn chèn, hãy thông báo vị trí chèn không hợp lệ head = addTail(head, value); // printf("Vi tri chen vuot qua vi tri cuoi cung!\n"); }else{ Node temp = createNode(value); temp->next = p->next; p->next = temp; } } return head; }Kết hợp với hàm khởi tạo City (createCity) phía trên, chúng ta có thể hoàn chỉnh thao tác thêm Node vào danh sách với hàm dưới đây: Node delHead(Node head){ if(head == NULL){ printf("\nCha co gi de xoa het!"); }else{ head = head->next; } return head; } Node delTail(Node head){ if (head == NULL || head->next == NULL){ return delHead(head); } Node p = head; while(p->next->next != NULL){ p = p->next; } p->next = p->next->next; // Cho next bằng NULL return head; } // Xóa Node ở "chỉ số" (bắt đầu từ 0) bất kỳ Node delAt(Node head, int position){ if(position == 0 || head == NULL || head->next == NULL){ head = delHead(head); // Nếu vị trí xóa là 0, tức là thêm vào đầu }else{ // Bắt đầu tìm vị trí cần xóa. Ta sẽ dùng k để đếm cho vị trí int k = 1; Node p = head; while(p->next->next != NULL && k != position){ p = p->next; ++k; } if(k != position){ // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định xóa cuối // Nếu bạn không muốn xóa, hãy thông báo vị trí xóa không hợp lệ head = delTail(head); // printf("Vi tri xoa vuot qua vi tri cuoi cung!\n"); }else{ p->next = p->next->next; } } return head; }Ở trên, chúng ta đã có hàm xóa ở chỉ số bất kỳ, vậy để xóa Node theo mã (code) cung cấp. Ta cần viết thêm 1 hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code trùng với giá trị được cung cấp: // Hàm tìm chỉ số của Node có dữ liệu thành phố mà mã code của nó trùng với giá trị cần tìm int findIndexByCode(Node head, int code){ int index = -1; for(Node p = head; p != NULL; p = p->next){ index++; if (p->city.code == code){ return index; } } return -1; // Không tìm thấy }Như vậy, để hoàn chỉnh thao tác xóa Node theo mã tỉnh/thành phố. Ta sẽ thêm 1 hàm sau: Node removeNode(Node head){ int code; char option; while (TRUE) { printf("========== Chon Node muon xoa ===============\n"); printf("Nhap ma tinh/thanh pho can xoa: "); scanf("%d", &code); int position = findIndexByCode(head, code); if (position < 0){ printf("Khong tim thay du lieu can xoa! Xoa tiep (Y/n)? "); }else { head = delAt(head, position); printf("Xoa thanh cong? Xoa tiep (Y/n)? "); } getchar(); // Bỏ qua '\n' trong bộ đệm scanf("%c", &option); if (option == 'N' || option == 'n'){ break; } } return head; }Các chức năng thêm, xóa Node của danh sách đều có thể thay đổi Node head (Ex: xóa Node head). Do đó, các hàm này đều cần trả về giá trị là Node head mới sau khi thay đổi (có thể vẫn giữ nguyên). # Hàm sửa giá trị Node trong DSLK
# Hàm sắp xếp danh sách void swapCityData(City *a, City *b){ City tmp = *a; *a = *b; *b = tmp; } // Hàm sắp xếp // Nếu sort theo code, thì byCode = 1, byArea = 0 // Nếu sort theo area, thì byCode = 0, byArea = 1 // Nếu sắp xếp tăng dần thì desc = 0, giảm dần thì desc = 1 void sortCities(Node head, int byCode, int byArea, int desc){ for(Node p = head; p != NULL; p = p->next){ for(Node q = p->next; q != NULL; q = q->next){ if (desc){ if (byCode && p->city.code < q->city.code){ swapCityData(&p->city, &q->city); }else if (byArea && p->city.area < q->city.area){ swapCityData(&p->city, &q->city); } }else { if (byCode && p->city.code > q->city.code){ swapCityData(&p->city, &q->city); }else if (byArea && p->city.area > q->city.area){ swapCityData(&p->city, &q->city); } } } } }
# Các hàm chức năng khác Ngoài các hàm thêm, sửa, xóa trên, đề bài còn yêu cầu một số hàm tính tổng diện tích, tìm tỉnh/thành phố có diện tích/dân số lớn nhất, và cả sắp xếp danh sách. Về cơ bản, các hàm này chỉ cần dựa trên thao tác duyệt danh sách (traveser) là có thể hoàn thành rồi. // Hàm tính tổng diện tích các thành phố trong DSLK float sumArea(Node head){ float sum = 0; for(Node p = head; p != NULL; p = p->next){ sum += p->city.area; } return sum; } // Hàm tìm chỉ số của Node có diện tích lớn nhất (giả sử chỉ có 1) // Nếu dữ liệu có nhiều hơn 1, chúng ta tìm max rồi duyệt lại 1 lần nữa để tìm ra các Node có giá trị = max đó int indexOfMaxArea(Node head){ int maxIndex = 0, index = 0; int maxArea = head->city.area; for(Node p = head; p != NULL; p = p->next){ if (p->city.area > maxArea){ maxArea = p->city.area; maxIndex = index; } index++; } return maxIndex; } // Hàm tìm Node có dân số lớn nhất City maxByPopulation(Node head){ City city = head->city; for(Node p = head; p != NULL; p = p->next){ if (p->city.population > city.population){ city = p->city; } } return city; }Thao tác đọc dữ liệu từ tệp Đề bài yêu cầu chúng ta cần khởi tạo danh sách ban đầu bằng cách đọc dữ liệu từ tệp. Do đó, chúng ta cần thêm 1 số hàm con nữa. – Do dữ liệu tên tỉnh/thành phố có dấu cách nên mình chỉ biết cách đọc từng dòng vào xử lý. Do vậy, mình cần:
Như vậy là hoàn thiện, việc còn lại chỉ là đưa chúng vào hàm main theo 1 trật tự do chúng ta quy định. X. Danh Sách Liên Kết Đơn Quản Lý Sinh Viên C++Hôm nay mình định viết về phần tiếp theo của opencv xử lý ảnh nhưng còn bài tập môn cấu trúc dữ liệu chưa hoàn thành , sẵn tiện mình vừa làm vừa ra bài này luôn . Đề bài Code #include"iostream" #include"string" #include"stdlib.h" using namespace std; struct SinhVien { int mssv; string name; string diachi; string ngaysinh; string lop; }; typedef struct SinhVien sinhvien; struct node { sinhvien *data; struct node* link; }; typedef struct node Node; struct list { Node* pHead; Node* pTail; }; typedef struct list List; void KhoiTaoList(List &l) { l.pHead = l.pTail = NULL; } void Input_ThongTin(sinhvien *sv) { cin.ignore(); cout << "Nhap Ten sinh vien: \n"; fflush(stdin); getline(cin,sv->name); cout << "Nhap Ma so sinh vien : "; cin >> sv->mssv; cin.ignore(); cout << "Nhap dia chi sinh vien :\n"; getline(cin,sv->diachi); fflush(stdin); cout << "Nhap ngay sinh cua sinh vien:\n"; getline(cin, sv->ngaysinh); fflush(stdin); cout << "Nhap lop cua sinh vien : "; getline(cin, sv->lop); } Node *KhoiTaoNode() { sinhvien* sv = new sinhvien; Input_ThongTin(sv); Node* p = new Node; if (p == NULL) { cout << "full ram ko thể tao thêm\n"; return 0; } p->data = sv; p->link = NULL; return p; } void ThemVaoDauMotSinhVien(List &l, Node *p) { if (l.pHead == NULL) { l.pHead = l.pTail= p; } else { p->link = l.pHead; l.pHead = p; } } void Show(List l) { for (Node* k = l.pHead; k != NULL; k = k->link) { cout << "MSSV : " << k->data->mssv< |