Danh Sách Liên Kết đơn - Lập Trình 321

• Home

• 

Lập Trình 321

Tổng Hợp Kiến Thức Lập Trình

SLIDE1

• Home

Sunday, April 26, 2015

Home » danh sach lien ket , giai thuat » danh sách liên kết đơn

danh sách liên kết đơn

Unknown 10:06 PM danh sach lien ket, giai thuat Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần Thành phần dữ liệu: Lưu trữ thông tin về bản thân phần tử Thành phần liên kết: Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách. Cấu trúc dữ liệu của 1 nút trong List đơn typedef struct tagNode { Data Info; // Lưu thông tin bản thân struct tagNode *pNext; //Lưu địa chỉ của Node đứng sau }Node; Cấu trúc dữ liệu của DSLK đơn typedef struct tagList { Node *pHead;//Lưu địa chỉ Node đầu tiên trong List Node *pTail; //Lưu địa chỉ của Node cuối cùng trong List }LIST; // kiểu danh sách liên kết đơn *các thao tác cơ bản trên danh sách liên kết Tạo 1 danh sách liên kết đơn rỗng Tạo 1 nút có trường Infor bằng x Tìm một phần tử có Info bằng x Thêm một phần tử có khóa x vào danh sách Hủy một phần tử trong danh sách Duyệt danh sách Sắp xếp danh sách liên kết đơn *khởi tạo danh ách liên kết Địa chỉ của nút đầu tiên, địa chỉ của nút cuối cùng đều không có void CreateList(List &l) { l.pHead=NULL; l.pTail=NULL; } *tạo 1 phần tử mới Hàm trả về địa chỉ phần tử mới tạo Node* CreateNode(Data x) // trong bài học là int { Node *p; p = new Node;//Cấp phát vùng nhớ cho phần tử if ( p==NULL) exit(1); p ->Info = x; //gán dữa liệu cho nút p->pNext = NULL; return p; } *thêm 1 phần tử vào sánh sách liên kết Nguyên tắc thêm: Khi thêm 1 phần tử vào List thì có làm cho pHead, pTail thay đổi? Các vị trí cần thêm 1 phần tử vào List: +)Thêm vào đầu List đơn Thêm nút p vào đầu danh sách liên kết đơn Bắt đầu: Nếu List rỗng thì + pHead = p; + pTail = pHead; Ngược lại + p->pNext = pHead; + pHead = p void AddHead(LIST &l, Node* p) { if (l.pHead==NULL) { l.pHead = p; l.pTail = l.pHead; } else { p->pNext = l.pHead; l.pHead = p; } } +)Thêm vào cuối List Ta cần thêm nút p vào cuối list đơn Bắt đầu: Nếu List rỗng thì + pHead = p; + pTail = pHead; Ngược lại + pTail->pNext=p; + pTail=p void AddTail(LIST &l, Node *p) { if (l.pHead==NULL) { l.pHead = p; l.pTail = l.pHead; } else { l.pTail->Next = p; l.pTail = p; } } +)Thêm vào sau 1 phần tử q trong list Ta cần thêm nút p vào sau nút q trong list đơn Bắt đầu: Nếu (q!=NULL) thì B1: p->pNext = q->pNext B2: + q->pNext = p + nếu q = pTail thì pTail=p void InsertAfterQ(List &l, Node *p, Node *q) { if(q!=NULL) { p->pNext=q->Next; q->pNext=p; if(l.pTail==q) l.Tail=p; } else AddHead(l,p);// thêm q vào đầu list } *hủy phần tử trong sanh sách liên kết Nguyên tắc: Phải cô lập phần tử cần hủy trước hủy. Các vị trị cần hủy Hủy phần tử đứng đầu List Hủy phần tử có khoá bằng x Huỷ phần tử đứng sau q trong danh sách liên kết đơn Ở phần trên, các phần tử trong DSLK đơn được cấp phát vùng nhớ động bằng hàm new, thì sẽ được giải phóng vùng nhớ bằng hàm delete. Bắt đầu: Nếu (pHead!=NULL) thì B1: p=pHead B2: + pHead = pHead->pNext + delete (p) B3: Nếu pHead==NULL thì pTail=NULL Hủy được hàm trả về 1, ngược lại hàm trả về 0 int RemoveHead(List &l, int &x) { Node *p; if(l.pHead!=NULL) { p=l.pHead; x=p->Info; //lưu Data của nút cần hủy l.pHead=l.pHead->pNext; delete p; if(l.pHead==NULL) l.pTail=NULL; return 1; } return 0; } Hủy phần tử sau phần tử q trong List Bắt đầu Nếu (q!=NULL) thì //q tồn tại trong List B1: p=q->pNext;// p là phần tử cần hủy B2: Nếu (p!=NULL) thì // q không phải là phần tử cuối + q->pNext=p->pNext;// tách p ra khỏi xâu + nếu (p== pTail) // nút cần hủy là nút cuối pTail=q; + delete p;// hủy p int RemoveAfterQ(List &l, Node *q, int &x) { Node *p; if(q!=NULL) { p=q->pNext; //p là nút cần xoá if(p!=NULL) // q không phài là nút cuối { if(p==l.pTail) //nút cần xoá là nút cuối cùng l.pTail=q;// cập nhật lạ pTail q->pNext=p->pNext; x=p->Info; delete p; } return 1; } else return 0; } Thuật toán hủy phần tử có khoá x Bước 1: Tìm phần tử p có khoá bằng x, và q đứng trước p Bước 2: Nếu (p!=NULL) thì //tìm thấy phần tử có khoá bằng x Hủy p ra khỏi List bằng cách hủy phần tử đứng sau q Ngược lại Báo không tìm thấy phần tử có khoá int RemoveX(List &l, int x) { Node *p,*q = NULL; p=l.Head; while((p!=NULL)&&(p->Info!=x)) //tìm { q=p; p=p->Next; } if(p==NULL) //không tìm thấy phần tử có khoá bằng x return 0; if(q!=NULL)//tìm thấy phần tử có khoá bằng x DeleteAfterQ(l,q,x); else //phần tử cần xoá nằm đầu List RemoveHead(l,x); return 1; } Hàm tìm 1 phần tử trong DSLK đơn Hàm tìm phần tử có Info = x, hàm trả về địa chỉ của nút có Info = x, ngược lại hàm trả về NULL Node *Search(LIST l, Data x) { Node *p; p = l.pHead; while((p!= NULL)&&(p->Info != x)) p = p->pNext; return p; } Duyệt danh sách Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu cần xử lý các phần tử trong danh sách như: Đếm các phần tử trong danh sách Tìm tất cả các phần tử trong danh sách thảo điều kiện Hủy toàn bộ danh sách Bước 1: p = pHead;// p lưu địa chỉ của phần tử đầu trong List Bước 2: Trong khi (danh sách chưa hết) thực hiện + xử lý phần tử p + p=p->pNext;// qua phần tử kế void PrintList(List l) { Node *p; p=l.pHead; while(p!=NULL) { printf(“%d ”, p->Info); p=p->pNext; } } Hủy danh sách liên kết đơn Bước 1: Trong khi (danh sách chưa hết) thực hiện B11: p = pHead; pHead = pHead->pNext;// cập nhật pHead B12: Hủy p Bước 2: pTail = NULL;// bảo toàn tính nhất quán khi xâu rỗng void RemoveList(List &l) { Node *p; while(l.pHead!=NULL)//còn phần tử trong List { p = l.pHead; l.pHead = p->pNext; delete p; } } Sắp xếp danh sách Có hai cách tiếp cận Cách 1: Thay đổi thành phần Info Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn) Thay đổi thành phần Info (dữ liệu) Ưu: Cài đặt đơn giản, tương tự như sắp xếp mảng Nhược: Đòi hỏi thêm vùng nhớ khi hoán vị nội dung của 2 phần tử -> chỉ phù hợp với những xâu có kích thước Info nhỏ Khi kích thước Info (dữ liệu) lớn chi phí cho việc hoán vị thành phần Info lớn Làm cho thao tác sắp xếp chậm Thay đổi thành phần pNext Ưu: Kích thước của trường này không thay đổi, do đó không phụ thuộc vào kích thước bản chất dữ liệu lưu tại mỗi nút. Thao tác sắp xếp nhanh Nhược: Cài đặt phức tạp void SelectionSort(LIST &l) { Node *p,*q,*min; p=l.pHead; while(p!=l.pTail) { min=p; q=p->pNext; -------------------------------------- while(q!=NULL) { if(q->Info<p->Info) min=q; q=q->pNext; } HV(min->Info,p->Info); p=p->pNext; } } Các thuật toán sắp xếp hiệu quả trên List Các thuật toán sắp xếp xâu (List) bằng các thay đổi thành phần pNext (thành phần liên kết) có hiệu quả cao như: Thuật toán sắp xếp Quick Sort Thuật toán sắp xếp Merge Sort Thuật toán sắp xếp Radix Sort Thuật toán sắp xếp Quick Sort Bước 1: Chọn X là phần tử đầu xâu L làm phần tử cầm canh Loại X ra khỏi L Bước 2: Tách xâu L ra làm 2 xâu L1(gồm các phần tử nhỏ hơn hoặc bằng x) và L2 (gồm các phần tử lớn hơn X) Bước 3: Nếu (L1 !=NULL) thì QuickSort(L1) Bước 4: Nếu (L2!=NULL) thì QuickSort(L2) Bước 5: Nối L1, X, L2 lại theo thứ tự ta có xâu L đã được sắp xếp Sắp xếp L1 Sắp xếp L2 Chọn x=6 cầm canh, và tách L2 thành L21 và L22 void QuickSort(List &l) { Node *p,*X;//X lưu địa chỉ của phần tử cầm canh List l1,l2; if(l.pHead==l.pTail) return;//đã có thứ tự CreateList(l1); CreateList(l2); X=l.pHead; l.pHead=X->pNext; while(l.pHead!=NULL)//tách L = L1 va L2 { p=l.pHead; l.pHead=p->pNext; p->pNext=NULL; if(p->Info<=X->Info) AddHead(l1,p); else AddHead(l2,p); } QuickSort(l1);//Gọi đệ quy sắp xếp L1 QuickSort(l2);//Gọi đệ quy sắp xếp L2 if(l1.pHead!=NULL)//nối l1, l2 va X vao l { l.pHead=l1.pHead; l1.pTail->pNext=X;//nối X vào } else l.pHead=X; X->pNext=l2.pHead; if(l2.pHead!=NULL) //l2 có trên một phần tử l.pTail=l2.pTail; else //l2 không có phần tử nào l.pTail=X; } Thuật tốn sắp xếp Merge Sort Bước 1: Phân phối luân phiên từng đường chạy của xâu L vào 2 xâu con L1 và L2. Bước 2: Nếu L1 != NULL thì Merge Sort (L1). Bước 3: Nếu L2 != NULL thì Merge Sort (L2). Bước 4: Trộn L1 và L2 đã sắp xếp lại ta có xâu L đã được sắp xếp. Không tốn thêm không gian lưu trữ cho các dãy phụ Cài đặt hàm main() Yêu cầu: Viết chương trình thành lập 1 xâu đơn, trong đó thành phần dữ liệu của mỗi nút là 1 số nguyên dương. Liệt kê tất thành phần dữ liệu của tất cả các nút trong xâu Tìm 1 phần tử có khoá bằng x trong xâu. Xoá 1 phần tử đầu xâu Xoá 1 phần tử có khoá bằng x trong xâu Sắp xếp xâu tăng dần theo thành phần dữ liệu (Info) Chèn 1 phần tử vào xâu, sao cho sau khi chèn xâu vẫn tăng dần theo trường dữ liệu ..vv void main() { LIST l1; Node *p; int x; CreateList(l1); do{ printf(“nhap x=”); scanf(“%d”,&x); if(x>0) { p = CreateNode(x); AddHead(l1,x); } }while(x>0); printf(“Danh sách mới thành lập là\n”); PrintList(l1); printf(“nhập x cần tìm x=”); scanf(“%d”,&x); p = Search(l1,x); if(p==NULL) printf(“không tìm thấy”); else printf(“tìm thấy”); RemoveHead(l1,x); printf(“danh sách sau khi xóa\n”); PrintList(l1); printf(“nhập khoá cần xoá\n”); scanf(“%d”,&x); RemoveX(l1,x); printf(“danh sách sau khi xoá”); PrintfList(l1); SelectionSort(l1); printf(“Danh sách sau khi sắp xếp”); PrintfList(l1); RemoveList(l1); } Email ThisBlogThis!Share to XShare to Facebook ← Newer Post Older Post → Home

Find us on facebook

Trần Khánh Toànemail: [email protected]://www.laptrinh321.net FaceBook Google Plus

• Popular
• Tags
• Blog Archives

• hệ đếm nhị phân, thập phân và thập lục phân 1. hệ đếm nhị phân: dùng 2 kí số cơ bản là 0 và 1 đổi hệ 10 sang hệ 2 thì chia liên tiếp cho 2 đến khi bằng 0, số dư được viết theo c...
• các hệ thống số cơ bản, nhị phân, bát phân, thập lục phân, thập phân các hệ thống số cơ bản thập phân: gồm các chữ số 0,1,2,3,4,5,6,7,8,9 ví dụ: 576.348 = 5*10^2 + 7*10^1 + 6*10^0 + 3*10^-1 + 4*10^-2 ...
• lập trình tìm các bộ số pitago | lập trình c/c++ lập trình tìm các bộ số pitago | lập trình c/c++.   Một tam giác vuông có thể có tất cả các cạnh là các số nguyên. Tập của ba số nguyên của...
• xung đột? pipelined và kỹ thuật forwarding, non-forwarding  Pipeline là một kỹ thuật mà trong đó các lệnh được thực thi theo kiểu chồng lắp lên nhau. - Cách tiếp cận dùng kỹ thuật pipeline tiêu tố...
• viết chương trình c chuyển đổi hệ đếm nhị phân, bát phân, thập lục phân viết chương trình c chuyển đổi hệ đếm nhị phân, bát phân, thập lục phân .  DEC,BIN,HEX,OCT.   Viết chương trình in bảng của các số từ 1 đế...
• [C/C++] nhập vào họ và tên, in ra tên viết chương trình [C/C++] nhập vào họ và tên , sau đó xử lý chuỗi và in ra tên của người đó. #include<stdio.h> #include<string.h...
• OOP C++ cộng trừ nhân chia số phức Làm lại bài số phức với một phương thức thiết lập duy nhất cho phép quan điểm một số thực như một số phức đặc biệt (phần ảo bằng 0). Định ng...
• cách XĐ tín hiệu điều khiển từ khối "Control" - Datapath (KTMT) ** Tổng quan các lệnh cần xem xét: (8 lệnh trong 3 nhóm chính của tập lệnh MIPS)   §  Nhóm lệnh tham khảo bộ nhớ (lw và sw): Nạp...
• 5. Viết chương trình nhập họ tên, điểm toán, điểm văn của một học sinh. Tính điểm trung bình và xuất kết quả. 5. Viết chương trình nhập họ tên, điểm toán, điểm văn của một học sinh. Tính điểm trung bình và xuất kết quả. #include<iostream> us...
• [OOP C++] quản lý nhân viên và tính lương cho từng nhân viên bài tập OOP C++. Giả sử Công ty có hai loại nhân viên: Nhân viên văn phòng và Nhân viên sản xuất. Viết chương trình quản lý và tính lương ch...

Labels

• bai tap c
• bai tap oop
• cau truc cay
• danh sach lien ket
• giai thuat
• giao trinh hoc c
• giao trinh oop
• html
• kien truc may tinh
• lap trinh c
• lap trinh web
• linh tinh
• linux
• mang may tinh
• may tinh
• PHP
• sap xep
• SQL
• tim kiem

Blog Archive

• ►  2016 (6)
  • ►  March (4)
  • ►  January (2)

• ▼  2015 (173)
  • ►  October (22)
  • ►  September (11)
  • ►  June (17)
  • ►  May (29)
  • ▼  April (25)
    • code c++ phần mềm split and join file part,001,002
    • danh sách liên kết kép
    • danh sách liên kết đơn
    • sắp xếp trộn run sắp xếp ngoại
    • thư viện vector STL C++
    • cơ bản thư viện vector STL C++
    • cơ bản về thư viện string - STL C++
    • tính giá trị biểu thức toán học bất kỳ, giống máy ...
    • tạo lập đối tượng trong c++
    • lớp class trong lập trình c++
    • [C++] điều khiển robot trong bản đồ Oxy U-D-L-R-T-B
    • Viết định nghĩa lớp TamGiac ,quay, tịnh tiến, phón...
    • Tra Cứu điểm chuẩn đại học cao đẳng 2015
    • thuật toán sắp xếp radix sort
    • thuật toán merge sort - sắp xếp trộn
    • thuật toán quick sort - sắp xếp nhanh
    • thuật toán heap sort - sắp xếp vun đống, (cây)
    • thuật toán shell sort - cải tiến của chèn trực tiếp
    • thuật toán binary insertion sort - chèn nhị phân
    • thuật toán insertion sort - chèn trực tiếp
    • [đệ quy c/c++] kiểm tra các phần tử của mảng
    • [đệ quy c/c++] đếm số phần tử phân biệt trong mảng
    • [đệ quy c/c++] tìm UCLN tất cả các phần tử trong mảng
    • [Đệ Quy C++] viết hàm xuất các số nguyên tố có tro...
    • [Đệ Quy C/C++] tìm min và max các phần tử của mảng.
  • ►  March (15)
  • ►  February (11)
  • ►  January (43)

• ►  2014 (66)
  • ►  December (9)
  • ►  October (28)
  • ►  September (29)

Categories

• bai tap c
• bai tap oop
• cau truc cay
• danh sach lien ket
• giai thuat
• giao trinh hoc c
• giao trinh oop
• html
• kien truc may tinh
• lap trinh c
• lap trinh web
• linh tinh
• linux
• mang may tinh
• may tinh
• PHP
• sap xep
• SQL
• tim kiem

BTemplates.com

Đồng Hồ Gỗ, Tượng Gỗ Di Lặc, Phúc Lộc Thọ Dịch Vụ Kế Toán Tại Nhà Kế Toán  

• Labels

  • bai tap c
  • bai tap oop
  • cau truc cay
  • danh sach lien ket
  • giai thuat
  • giao trinh hoc c
  • giao trinh oop
  • html
  • kien truc may tinh
  • lap trinh c
  • lap trinh web
  • linh tinh
  • linux
  • mang may tinh
  • may tinh
  • PHP
  • sap xep
  • SQL
  • tim kiem

• Blogroll

  

• About

Copyright © Lập Trình 321 | Powered by Blogger Design by FThemes | Blogger Theme by Lasantha - Premium Blogger Templates | NewBloggerThemes.com