Build a linear list of the input sequence of numbers. Remove from it all the numbers except simple [closed]

This cycle is to remove nodes from the list that do not contain prime numbers.

  r=fr; rp=r; while (r->next != NULL) // Пока не дошли до последнего элемента списка. { for (int i=1;i<r->inf;i++){ if (r->inf%i==0 && i!=1 && i!=r->inf) { rp=r; r=r->next; cout<<"\n3\n"; cout<<rp; break; } else{ if (r==fr) { fr=r->next; delete rp; rp=fr; r=fr; cout<<"\n1\n"; break; } else { rp->next=r->next; delete r; r=rp->next; cout<<"\n2\n"; break; } } cout<<r; } } 

does not make sense. First, fr can be NULL , and then the calculation of the condition r->next != NULL will lead to undefined program behavior. Secondly, Fr->next in turn, can be NULL , and then you cannot check whether a single list node contains a prime number or not.

Then you incorrectly check whether the number is simple. For example, the number 2 is simple, and the number 1 is not simple.

So you better write a separate function that will check if the number is simple or not. As a result, your code will be simplified and easier to read.

The if_else conditions should be checked after the for loop has been executed, and not at each iteration.

EDIT: A function that checks whether a positive number is simple may look like this, as shown in the demo program below.

 #include <iostream> bool is_prime( int value ) { bool prime = ( value == 2 ) || ( value > 2 && value % 2 ); for ( int i = 3; prime && i <= value / i; i += 2 ) { prime = value % i; } return prime; } int main() { const int N = 100; for ( int i = 1; i < N; i++ ) { if ( is_prime( i ) ) std::cout << i << ' '; } std::cout << std::endl; return 0; } 

Its output to the console

 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

When using this function, the while may look like

 while ( r != NULL ) { if ( not is_prime( r->inf ) ) { // удаляем узел // ... } else { // просто переходим к следующему узлу rp = r; r = r->next; } } 

Identifiers should be given meaningful names so that your code reader understands what they mean. Identifiers such as fr or er that you use are difficult to understand.

You should also declare variables in the smallest scope. Otherwise, declarations of multiple variables can only confuse the reader of your code.

If you use your approach, the program may look like this, Only in it I enter the data in the list not from a file, but simply use a natural series of numbers.

 #include <iostream> bool is_prime( int value ) { bool prime = ( value == 2 ) || ( value > 2 && value % 2 ); for ( int i = 3; prime && i <= value / i; i += 2 ) { prime = value % i; } return prime; } struct node { int inf; node *next; }; int main() { node *head = nullptr, *tail = nullptr; const int N = 100; int i = 1; do { node *current = new node { i, nullptr }; if ( head == nullptr ) head = current; else tail->next = current; tail = current; } while ( i++ != N ); for ( node *current = head; current != nullptr; current = current->next ) { std::cout << current->inf << ' '; } std::cout << std::endl; node *previous = head, *current = head; while ( current != nullptr ) { if ( not is_prime( current->inf ) ) { if ( current == head ) { head = current->next; delete current; current = head; previous = head; } else { previous->next = current->next; delete current; current = previous->next; } } else { previous = current; current = current->next; } } std::cout << std::endl; for ( node *current = head; current != nullptr; current = current->next ) { std::cout << current->inf << ' '; } std::cout << std::endl; while ( head != nullptr ) { node *current = head; head = head->next; delete current; } return 0; } 

The output of the program to the console is as follows.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

However, this approach to remove nodes from the list can not be called successful. Why? Because in the general algorithm special cases are considered: is the deleted node the head node of the list.

Programming is the art of generalization. The more special cases are considered in the program, the more susceptible such a program is, and it is also difficult for the general idea to read the program code. He will also have to spend his time digging into these particulars in order to understand what is being done there. And such programs are harder to maintain and modify.

Therefore, programs should be written in such a way as to avoid particulars when they are not really necessary. It is necessary to choose a more generalized algorithm that is not overloaded with all sorts of particular cases, in other words, in which there are fewer different if-else sentences.

In your program, you can use a different approach to removing nodes from a single-linked list. Below is a demonstration program.

 #include <iostream> bool is_prime( int value ) { bool prime = ( value == 2 ) || ( value > 2 && value % 2 ); for ( int i = 3; prime && i <= value / i; i += 2 ) { prime = value % i; } return prime; } struct node { int inf; node *next; }; int main() { node *head = nullptr; node *tail = nullptr; const int N = 100; for ( int i = 1; i <= N; i++ ) { node *current = new node { i, nullptr }; if ( head == nullptr ) head = current; else tail->next = current; tail = current; } for ( node *current = head; current != nullptr; current = current->next ) { std::cout << current->inf << ' '; } std::cout << std::endl; for ( node **current = &head; *current != nullptr; ) { if ( not is_prime( ( *current )->inf ) ) { node *tmp = *current; *current = ( *current )->next; delete tmp; } else { current = &( *current )->next; } } std::cout << std::endl; for ( node *current = head; current != nullptr; current = current->next ) { std::cout << current->inf << ' '; } std::cout << std::endl; while ( head != nullptr ) { node *current = head; head = head->next; delete current; } return 0; } 

As you can see, when deleting nodes, no particular case of whether a node is a head node is considered, since the removal algorithm is the same for all nodes.

In connection with all of the above, it will be interesting to read the discussion on one site in the topic What is good and what is bad There is a link to the speech of the author of the Linux operating system Linus Torvalds, where he, in particular, expressed his opinion on two fragments of a certain conditional code, also associated with the list.

So, here, the participants of this forum, who consider themselves professionals, first of all, did not even realize that this example code is conditional and is intended to demonstrate the idea. And also, secondly, they did not understand this idea, that is, what Linus means when one code fragment considers better than another.

And Linus means exactly what I wrote here: try to write generalized code, avoiding unnecessary particulars that will only overload the program and thereby blur the main and secondary, making it more difficult to see the main essence of the algorithm. :)

Here is a function to determine if a number is simple:

 #include <math.h> bool IsPrime (int In){ if(In==1) return false; if(In==2) return true; if(In%2==0) //проверяем четное ли число return false; //если да то оно не простое //если нет, продолжим проверку int test=3; int stop=(int)sqrt(In)/2;//добудем корень //К примеру число 121 (это 11*11) надо поделить на 11 и узнаем что 121 не простое //А еще раз разделить на 2 потому как будем проверять //делением только на нечетные (ведь если число нечетное, то оно не поделится на четное) for(int i=0;i<stop;i++){ if(In%test==0) return false; test+=2;//идем по нечетным числам начиная с 3 } terurn true } 

So what is next:

 while (r != NULL){ if(IsPrime(r->inf)){ //что делать если число простое } else{ //что делать если число не простое //учтите, что у вас может быть всего один узел списка //или простым окажется только один узел списка //или простых чисел не окажется в списке вообще } r = r->next; } 

A singly-linked list is a simple data structure in which you can easily insert new items at the top of the list (or after a given item) and process them in an obvious way.

Often, working with a single-linked list does not even require writing helper functions (especially if these are not repetitive actions); simple list manipulations are easily written directly in the code that implements the logic of the program.

For example, inserting a new item into the list after the item pointed to by cur :

 newnode->next = cur->next; cur->next = newnode; 

Multiple code samples for working with single-linked lists.

Here is a very simple loop for building a simply linked list (assuming that the order is not important, we build the list in the reverse order (like the stack)).

  node *list = 0; int n; while (cout << "Enter N: ", cin >> n) { node *p = new node; p->next = list; p->inf = n; list = p; } 

If the order is important, then you can either reverse the entire list built earlier.

  for (node *p = list, *t = list = 0; t = p;) { p = p->next; t->next = list; list = t; } 

or get another pointer that will always look at the last element in the list and build the list like this:

  node *list = 0, *tail; int n; while (cout << "Enter NUM: ", cin >> n) { node *p = new node; p->inf = n; p->next = 0; if (list) tail->next = p; else list = p; tail = p; } 

By the way, it is sometimes convenient to represent a simply-connected list as a structure that contains pointers to the first and last list elements.

 struct s_list { s_list *list, *tail; }; 

You just need to remember to correctly modify both of these pointers when deleting items and inserting new ones.

Here is the print list cycle

  for (node *c = list; c; c = c->next) cout << c->inf << '\n'; 

And here is a simple loop to remove selectable items from a single-linked list.
(usually the greatest difficulties arise precisely with the removal in the process of iterations on the list)

  for (node **p = &list, *c = *p; c;) if (deleit(c)) { *p = c->next; delete c; c = *p; } else { p = &c->next; c = c->next; } 

In it, node **p always addresses a pointer that refers to the element of the list being checked (and potentially deleted).

Instead of deleit() write your function, for example, determining whether the number is simple.

And finally, the code to delete all nodes in the list and reset the pointer to it

  while (list) { node *t = list->next; delete list; list = t; } 

Naturally, if such fragments occur many times in the code, then it makes sense to design them as functions.