Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize the sorting algorithm of linked list in C++", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "how to achieve the sorting algorithm of linked lists in C++"!

I. sorting by linked list

The simplest and direct way (directly using bubbling or selective sorting, and not exchanging nodes, only exchanging data fields)

/ / sort the linear list, using bubble sort, directly traverse the linked list void Listsort (Node* & head) {int I = 0; int j = 0; / / for variable linked list Node* L = head; / / as a temporary quantity Node* p; Node* p1; / / if the linked list is empty, directly return if (head- > value = = 0) return; for (I = 0; I

Value-1; iTunes +) {L = head- > next; for (j = 0; j

Value-I-1; value; +) {/ / get two values p = L; p1 = L-> next; / / if the former one is larger than the latter one, the data field if (p-> value > p1-> value) {Elemtype temp = p-> value; p-> value = p1-> value is exchanged between them. P1-> value = temp;} L = L-> next;}

Because the faster sorting, such as quick sorting requires that the addresses of their data fields are connected, it is more suitable for the sequential structure, while when the chain structure, we can only use two more sorting algorithms, such as bubbling sorting and so on. We are here to sort without swapping nodes, which is simple and clear, so that array sorting is the same. Later I will write the sort by exchanging nodes.

Next, we will discuss the time complexity of this sorting algorithm, because it uses bubble sorting, as long as its time is spent in those two loops, so the time complexity is: O (nymn), this efficiency is too low, let's think about this (bubble sorting) to achieve the sorting of the linked list in another way.

2. Another sorting method of linked list

When we discuss the sorting algorithm, we always store the data in the array for discussion. Under the sequential structure, we can adopt many efficient sorting algorithms, so this is another way for us to sort the linked list. First, we store the contents of the linked list in the array (time is O (n)), and then we sort that array (the fastest is nlog (n)). Finally, we sort that array. Store in the linked list (time is O (n)). Through the calculation, we can get that its time complexity is (O (nlogn)), which is almost the same as under the sequential structure, and it is acceptable.

Void Listsort_1 (Node* & head) {int I = 0; int j = 0; / / for variable linked list Node* L = head; / / if the linked list is empty, return if directly (head- > value = = 0) return; Elemtype * copy = new Elemtype [head-> value]; / / variable linked list, storing array for (I = 0; I)

Value; iTunes +) {L = L-> next; copy [I] = L-> value;} / / call the sort function sort in STL (copy, copy + head- > value); L = head; / / back to for in the linked list (I = 0; I

Value; iTunes +) {L = L-> next; L-> value= copy [I];}} III. Compare the efficiency of the two kinds of sorting

As shown in the figure, when the amount of data is 10000, it is obvious that the second sorting algorithm takes about 28 times faster than the first.

4. the following is to sort the linked list by exchanging nodes.

First of all, we write the function of the exchange node, the exchange of the node is mainly to consider the problem of the pointer domain of the node, in which the two adjacent nodes are a special case, which should be taken into special consideration. Let's first draw the idea diagram of node exchange, as shown in the following figure

First of all, we give the idea of the exchange of two adjacent nodes:

The following is the following figure for the exchange under normal circumstances

/ / Parameter is the position of the header node and the two nodes to be exchanged (starting point is 1) void swap_node (Node * & head,int iReint j) {/ / invalid if (ivalue | | j > head- > value) {cout next; / / change the value of the next node pre- > next = b of the pre / / you must first give the value of the next node of b to a first a-> next = b-> next; / / so that the next node of b equals a b-> next = a; return;} / / the first node before the first node Node * a = getitem (head, I); / / the previous node of the second node Node * b = getitem (head, j) / / first node Node * p = a-> next; / / second node Node * Q = b-> next; / / the next node of the first node Node * p_next = p-> next; / / the next node of the second node Node * q_next = Q-> next; / / a points to the second node Q a-> next = Q / / the next node of the second node points to the next node of the first node; / / the next node of / b points to the first node p b-> next = p; / / the next node of the first node points to the next node of the second node, p-> next = qroomnext;}

When sorting the code, keep in mind that the exchange nodes are exchanged before and after the exchange, so after the exchange is completed, L has been moved to the next node, so do not execute: next L-> exchange

/ / sort of linear table, exchange node void Listsort_Node (Node* & head) {int I = 0; int j = 0; / / for variable linked list Node* L = head; / / as a temporary quantity Node* p; Node* p1; / / if the linked list is empty, directly return if (head- > value = = 0) return; int flag = 0; cout value value-1 ITunes +) {L = head- > next; for (j = 0; j

Value-1-I; next- +) {/ / if we have exchanged nodes, then we have already moved L to the next node when switching nodes, so do not / / execute: l = L-> next;, otherwise if (L-> value > L-> next- > value) {flag = 1 Swap_node (head, j + 1, j + 2);} if (flag = = 1) {flag = 0;} else {L = L-> next;}}

Well, that's all for today. Today, by writing the exchange node, I found that the linked list was really easy to fool people. I was fooled for an hour before I knew that the node had been moved to the next node.

Finally, add a good way to reverse the linked list (it seems that calculating the length of the linked list in the header file can bring a lot of traversal)

Void rollback (Node * & head) {/ / first knows the location of the last element and the first element int end = head- > value; int start = 1; / / both sides start / / switch while (1) {if (end = = start) return; swap_node (head, end, start);-- end; + + start;}}

I hope you will make some comments on the code I wrote. I think I'd better paste a completed code directly. The transfer code is also in it.

Include#include#include#include#includeusing namespace std;typedef int Elemtype;// chain structure, we intend to add a / / save length header node to the linked list. Adding this node can facilitate us to do some / / basic operations on the node. The node saves the value of the linear table length struct Node {/ / node. If it is a header node, it saves the length Elemtype value of the linked list. / / the address of the next node Node * next;}; / / create an empty linked list where each header node represents a linked list void InitList (Node * & head) {head = new Node (); head- > value = 0; head- > next = NULL;} / / destroy a linked list void DestroyList (Node * & head) {delete head; head = NULL } / / clear the entire list void ClearList (Node * & head) {head- > value = 0; head- > next = NULL;} / / insert the function bool Listinsert (Node * & head, int I, Elemtype value) {/ / insert the previous method int j = 0; Node * L = head; / / return the error message if (ihead- > value + 1) return false directly if the insertion position is invalid / / get the previous node while (j) of the insertion position

Next; + + j;} / s is a temporary node Node * s = new Node (); s-> value = value; / / first assign a value to the temporary node s-> next = L-> next; / / Let the next location of the temporary node point to the next location of the previous node that currently needs to be inserted L-> next = s / / Let the next location of the previous node point to the temporary node, and / / add + + head- > value; return true to the length of the linear table. } / / get the value at a certain location Node * getitem (Node * & head, int I) {/ / We ask the program to return the value at a specific location / / We also look for the location from the header node int j = 0; Node * L = head; / / whether the desired location is legal if (ihead- > value) return NULL; / / also get the previous node while (j

Next; + + j;} / value = L-> next- > value; return L;} / / the sort of linear table, using bubble sort, directly traverses the linked list void Listsort (Node* & head) {int I = 0; int j = 0; / / for variable linked list Node* L = head; / / as a temporary quantity Node* p; Node* p1 / / return if (head- > value = = 0) return; for (I = 0; I) directly if the linked list is empty

Value-1; iTunes +) {L = head- > next; for (j = 0; j

Value-I-1; value; +) {/ / get two values p = L; p1 = L-> next; / / if the former one is larger than the latter one, the data field if (p-> value > p1-> value) {Elemtype temp = p-> value; p-> value = p1-> value is exchanged between them. P1-> value = temp;} L = L-> next;}} / / complete my sorting through the array void Listsort_by_array (Node* & head) {int I = 0; int j = 0; / / for variable linked list Node* L = head; / / return if (head- > value = = 0) return directly if the linked list is empty Elemtype * copy = new Elemtype [head-> value]; / / variable linked list, holding the array for (I = 0; I)

Value; iTunes +) {L = L-> next; copy [I] = L-> value;} / / call the sort function sort in STL (copy, copy + head- > value); L = head; / / back to for in the linked list (I = 0; I

Value; iNode +) {L = L-> next; L-> value = copy [I];}} / / Parameter is the position of the header node and the two nodes to be exchanged (starting point is 1) void swap_node (Node * & head,int iMint j) {/ / invalid if (ivalue | | j > head- > value) {cout next / / change the value of the next node of pre pre- > next = b; / / you must first give the value of the next node of b to a first a-> next = b-> next; / / so that the next node of b equals a b-> next = a; return;} / / the node before the first node Node * a = getitem (head, I) / / the first node of the second node Node * b = getitem (head, j); / / the first node Node * p = a-> next; / / the second node Node * Q = b-> next; / / the next node of the first node Node * p_next = p-> next; / / the next node of the second node Node * q_next = Q-> next / / the next node of / a points to the second node Q a-> next = Q; / / the next node of the second node points to the next node of the first node Q-> next = pextt; the next node of / b points to the first node p b-> next = p; / / the next node of the first node points to the next node of the second node p-> next = q_next } / / reverse void rollback (Node * & head) {/ / first know the position of the last element and the first element int end = head- > value; int start = 1; / / both sides start / / switch while (1) {if (end value = = 0) return; int flag = 0; for (I = 0; I)

Value-1; iTunes +) {L = head- > next; for (j = 0; j

Value-1-I; next- +) {/ / if we have exchanged nodes, then we have already moved L to the next node when switching nodes, so do not / / execute: l = L-> next;, otherwise if (L-> value > L-> next- > value) {flag = 1 Swap_node (head, j + 1, j + 2);} if (flag = = 1) {flag = 0;} else {L = L-> next }} void print (Node * & head) {/ / output We just need to pass in the header node, and then loop to determine whether the next node of the current node is empty, / / so that we can output all the content Node * L = head; while (L-> next) {L = L-> next; cout value

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.