Circular linked list
To join the two ends of a linked list to form a circular list, usually called a circular list.
As its name suggests, a linked list can be looped by simply pointing the pointer to the last node in the table to the head node, as shown below.
It is important to note that although circular lists are circular, they are essentially linked lists, so you can still find header Pointers and header nodes in circular lists. The only difference between a circular list and a regular list is that the circular list is connected end to end, and everything else is exactly the same.
Cyclic linked lists implement Joseph rings
Joseph’s ring problem is a classical circular linked list problem, which means: given n people (numbered 1,2,3 respectively… , n is for) Sit around a round table and count clockwise from person k to person M. The next person starts at 1 again, again clockwise, and the person who counts to M gets out again; Repeat until there is one person left at the table.
As shown in the figure below, suppose there are 5 people around the circle at this time, and ask to count clockwise from the person numbered 3 to the person who counts to 2:
The order of emergence is as follows:
3 starts counting 1, then 4 counts 2, so 4 goes first;
When 4 gets out of the column, you start at 5 and you count 1, 1, 2, so 1 gets out of the column;
When 1 gets out of the column, we start at 2 and we count 1, 3 and we count 2, so 3 gets out of the column;
When 3 gets out of the column, you start at 5 and you count 1,2 and 2, so 2 gets out of the column;
At the end of the day, there’s only 5 left, so 5 wins.
Joseph’s ring problem has many variations, such as turning clockwise to turning counterclockwise, etc. Although the details of the problem have many variations, the central idea of solving the problem is the same, that is, using circular linked lists.
Through the above analysis, we can try to write C language code, the complete code is as follows:
— — — — — —
typedefstruct node{int number; structnode * next; }person; person * initLink(int n){person * head=(person*)malloc(sizeof(person)); head->number=1; head->next=NULL; person * cyclic=head; for(inti=2; i<=n; i++) {person * body=(person*)malloc(sizeof(person)); body->number=i; body->next=NULL; cyclic->next=body; cyclic=cyclic->next; }cyclic->next=head; // return head; }voidfindAndKillK(person * head,intk,int m){person * tail=head; While (tail->next!) (tail->next!) =head) {tail=tail->next; }person * p=head; While (p->number! =k) {tail=p; p=p->next; } p->next==p;} p->next==p; =p) {// end (tail) {end (tail) {end (tail); for(inti=1; itail=p; p=p->next; }tail->next=p->next; Printf (" %d\n",p->number); free(p); p=tail->next; }printf(" printf number :%d\n",p->number); free(p); }int main() {printf(" Enter the number of people in the round table n:"); int n; scanf("%d",&n); person * head=initLink(n); Printf (" count from KTH (k>1 and k<%d) : ",n); int k; scanf("%d",&k); Printf (" count to m: "); int m; scanf("%d",&m); findAndKillK(head, k, m); return0; }Copy the code— — — — — —
See here you are not to C language and have a little new cognition ~
If you like this article, give it a thumbs-up
If you want to learn programming, xiaobian recommend a **C language /C++ programming learning base [click to enter]! **
An active, high-powered, high-level programming learning hall; The introduction of programming is only a side, the improvement of thinking is valuable!
Introduction to Programming, game programming, network programming, Windows programming, Linux programming, Qt interface development, hacking and so on…