Sắp xếp danh sách liên kết đơn

     

Trong hướng dẫn này mình sẽ giới thiệu chúng ta cách tìm kiếm và bố trí trong danh sách links đơn.

Bạn đang xem: Sắp xếp danh sách liên kết đơn

*


*

Chúng ta sẽ với mọi người trong nhà tìm hiều lần lượt cách tìm tìm một giá trị index trong list và thực hiện sắp xếp list theo sản phẩm tự tăng dần. Bố trí và kiếm tìm kiếm là hai thuật toán không thể thiếu trong các ngôn ngữ lập trình, tị nạnh vậy chúng ta hãy luyện tập cho thuần thục nhé.

1. Search kiếm trong danh sách link đơn

Trong phần này bản thân sẽ thực hiện tìm tìm một quý giá index được nhập từ phím trong danh sách links đơn. Đây là một thao tác đơn giản, chỉ cần ta trông nom từng bộ phận trong danh sách.

Giả sử họ có cực hiếm index = 5 là giá chỉ trị đề xuất tìm vào danh sách. Từ bây giờ ta bắt buộc khai báo một Node nhất thời pTmp để sửa chữa thay thế cho pHead xem xét danh sách.

Bài viết này được đăng tại


Thực hiện vòng lặp while lặp từng thành phần trong list với đk pTmp != Null. Giả dụ pTmp -> data == index thì ra khỏi vòng lặp và thông báo đã tra cứu thấy, ngược lại thì thông báo không tìm kiếm thấy.

Xem thêm: Top 9 Máy Khuếch Tán Tinh Dầu Chính Hãng 2022, Các Thương Hiệu Máy Xông Tinh Dầu


/* search kiếm cực hiếm index trong list */Node * SearchNode(SingleList list,int d) Node *pTmp=list.pHead; // khai báo biến hóa tạm pTmp sửa chữa cho pHead nhằm duyệt danh sách //Thực hiện vòng lặp các phần tử trong list với đk pTmp != null while(pTmp!=NULL) if(pTmp->data==d) // giả dụ tìm thấy index thì thoát khỏi vòng lặp break; // chưa tìm thấy thì liên tục duyệt phần tử kết tiếp pTmp=pTmp->pNext; return pTmp;

2. Thu xếp trong danh sắp links đơn

Ở phần sắp xếp thành phần trong danh sách links đơn, bản thân sẽ thực hiện sắp xếp bằng phương pháp so sánh và thay đổi giá trị data chứ không biến đổi Node. Có nghĩa là chỉ so sánh các giá trị data rồi chuẩn bị xếp, những Node vẫn không thay đổi không dịch chuyển.

Thao tác sắp xếp trong danh sách về cơ phiên bản tương từ bỏ như các thuật toán thu xếp khác, đơn giản và dễ dàng chỉ là trông nom từng bộ phận rồi đối chiếu với nhau, kế tiếp hoán đổi địa điểm của chúng.

Đầu tiên ta bao gồm một vòng lặp For sử dụng biến pTmp để lặp từng thành phần trong danh sách, vòng lặp For thiết bị hai áp dụng biến pTmp2 để lặp từng phần tử trong danh sách.

Nếu pTmp > pTmp2 thì hoán đổi địa chỉ giữa chúng, ví như pTmp thì tiếp tục so sách các bộ phận tiếp theo, cứ như vậy cho tới hết danh sách.

Xem thêm: Cách Làm Bánh Bao Bằng Khuôn, Khuôn Bánh Bao Hoa Sen Đa Năng


/* thu xếp trong danh sách link đơn theo sản phẩm tự tăng mạnh */void SortList(SingleList &list) // for loop đầu tiên for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) //for loop vật dụng hai for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) if(pTmp->data>pTmp2->data) // nếu quý giá trước > quý giá sau thì hoán thay đổi hai địa chỉ int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp;

3. Ví dụ search kiếm và thu xếp trong danh sách links đơn

Trong phần lấy một ví dụ này họ sẽ sử dụng dữ liệu ở lấy ví dụ trước để áp dụng cho việc đào bới tìm kiếm kiếm và sắp xếp. Chúng ta lưu ý rằng ao ước sử dụng được các thao tác mình đã gợi ý thì luôn luôn luôn khái báo cấu trúc dữ liệu của DSLK solo trước nhé.


#include using namespace std;/* Khai báo giá trị data và nhỏ trỏ pNext trỏ tới phần tử kế tiếp */struct Node int data;// quý hiếm data của node Node *pNext;// con trỏ pNext; /* Khai báo Node đầu pHead với Node cuối pTail*/struct SingleList Node *pHead; //Node đầu pHead Node *pTail; // Node cuối pTail; /* khởi sinh sản giá trị mang lại Node đầu với Node cuối */void Initialize(SingleList &list) list.pHead=list.pTail=NULL;// khởi tạo ra giá trị cho Node đầu cùng Node cuối là Null /* Đếm số bộ phận trong danh sách */ int SizeOfList(SingleList list) Node *pTmp=list.pHead; int nSize=0; while(pTmp!=NULL) pTmp=pTmp->pNext; nSize++; return nSize; /* tạo nên Node vào danh sách link đơn */Node *CreateNode(int d) Node *pNode=new Node; //sử dụng pNode để sinh sản một Node bắt đầu if(pNode!=NULL) // giả dụ pNode != Null, có nghĩa là pNode có mức giá trị thì pNode->data=d; // gán quý hiếm data đến d pNode->pNext=NULL;// cùng cho nhỏ trỏ pNext trỏ tới quý hiếm Null else // nếu như pNode == Null, tức là pNode không có giá trị thì xuất tin tức coutpNext=list.pHead; list.pHead=pNode; /* chèn node vào thời gian cuối danh sách */void InsertLast(SingleList &list,int d) Node *pNode=CreateNode(d); if(list.pTail==NULL) list.pHead=list.pTail=pNode; else list.pTail->pNext=pNode; list.pTail=pNode; /* chèn node vào giữa danh sách */void InsertMid(SingleList &list, int pos, int d) // nếu như pos = SizeOfList(list)) coutpNext; i++; //sau khi kiếm được thì chuyển đổi con trỏ pNext pPre ->pNext=pNode; pNode->pNext=pIns; }/* tìm kiếm kiếm giá trị index trong list */Node * SearchNode(SingleList list,int d) Node *pTmp=list.pHead; // khai báo biến đổi tạm pTmp sửa chữa thay thế cho pHead để duyệt danh sách //Thực hiện vòng lặp các phần tử trong danh sách với đk pTmp != null while(pTmp!=NULL) if(pTmp->data==d) // nếu tìm thấy index thì thoát ra khỏi vòng lặp break; // chưa tìm thấy thì tiếp tục duyệt thành phần kết tiếp pTmp=pTmp->pNext; return pTmp;/* thu xếp trong danh sách link đơn theo thiết bị tự tăng nhiều */void SortList(SingleList &list) // for loop trước tiên for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) //for loop thiết bị hai for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) if(pTmp->data>pTmp2->data) // nếu quý hiếm trước > giá trị sau thì hoán đổi hai vị trí int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp; /* hàm xuất tài liệu */void PrintList(SingleList list) Node *pTmp=list.pHead; if(pTmp==NULL) coutdatapNext; int main() { SingleList list; Initialize(list); //Thêm node đầu danh sách InsertFirst(list, 5); InsertFirst(list, 7); InsertFirst(list, 3); cout>index; Node *pFound = SearchNode(list, index); if(pFound == NULL){ cout
Kết quả:

Như vậy là chúng ta đã thực hiện kết thúc chương trình tìm kiếm và bố trí các bộ phận trong danh sách liên kết đơn. Cũng như hoàn thành hướng dẫn làm việc tìm kiếm và sắp tới xếp. Chúc các bạn thực hiện thành công !!!



Tìm những số chẵn lẻ bởi Queue với Stack

Để làm cho được bài xích này chúng ta cần có kỹ năng và kiến thức về cấu trúc Queue…



cài đặt hàng chờ Queue bởi mảng một chiều

bọn họ sẽ thuộc nhau mày mò về cách setup hàng ngóng Queue bằng…



thiết lập hàng đợi Queue bằng danh sách link

họ sẽ thuộc nhau khám phá về giải pháp khởi tạo cấu tạo dữ liệu…



Hàng hóng Queue là gì? cấu tạo dữ liệu và các cách cài đặt Queue

Trong lý giải này mình đang giới thiệu các bạn một cấu tạo lưu trữ…


bài tập kiểm tra số nguyên tố bằng Stack

họ sẽ cùng cả nhà tạo một cấu trúc Stack với danh sách liên kết…


bài bác tập đổi khác cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài xích toán biến hóa cơ…


thiết đặt Stack bởi mảng một chiều

bọn họ sẽ lần lượt thực hiện tạo những hàm cơ bản cho Stack như:…


cài đặt Stack bởi danh sách links

chúng ta sẽ triển khai lần lượt các thao tác làm việc trong Stack thực hiện danh…


ngăn xếp Stack là gì? cấu tạo và cơ chế chuyển động ra sao?

Trong khuyên bảo này mình vẫn giới thiệu các bạn một kết cấu lưu trữ…


Cây đỏ đen là gì? cấu tạo của Red-Black Tree

Trong lí giải này mình vẫn giới thiệu các bạn một cấu tạo dữ liệu…


Xóa Node khỏi cây nhị phân tìm kiếm kiếm

chúng ta sẽ cùng nhau thực hiện xóa Node có một con, Node tất cả 2…


search Node MAX và MIN trong cây nhị phân search kiếm

bọn họ sẽ triển khai một vài giải pháp tìm ra cực hiếm MAX với MIN…


Xuất Node bé và lá vào cây nhị phân tìm kiếm kiếm

Trong lí giải này mình vẫn giới thiệu các bạn cách xuất những Node con…


kiếm tìm kiếm Node trên cây nhị phân tìm kiếm

Trong lý giải này mình sẽ giới thiệu các bạn cách search kiếm một Node…


Thêm Node vào cây nhị phân kiếm tìm kiếm

Trong gợi ý này mình đang giới thiệu chúng ta về cấu tạo dữ liệu…


cấu trúc cây nhị phân là gì? vận động ra sao?

Trong bài bác này mình sẽ giới thiệu chúng ta một vào các cấu tạo dữ…


Gộp hai danh sách liên kết đôi

bọn họ sẽ cùng nhau mày mò về cách nối hai danh sách liên kết…