Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Preface:
Today in class our teacher reviewed the single linked list of the head plug method and tail plug method, insert and delete, this few do not understand the children’s shoes concern my last article (juejin.cn/post/702278…) “, then the teacher explained the Joseph ring, Joseph ring is a circular linked list, today we review the Algorithm of Joseph ring, by the way, advance preview of bidirectional linked list and cyclic bidirectional linked list.
Once a day to prevent decadence
Your roommate may be paddling, but he definitely hasn’t stopped learning
1.1 Joseph’s ring
We first look at Joseph ring, Joseph ring is a sad story after the Roman occupation of Joe tower pat, 39 jews and Josephus and his friend hiding in a hole, 39 decided jews would rather die don’t was caught by the enemy, then made a suicide, 41 people arranged in a circle, start from 1 individual number off, Every time you get to the third person you have to kill yourself, and then you have to count again from the next person, until all of them have killed themselves, so let’s use a simpler number, N people in a circle, start counting from the first person, and the MTH person will be out. For example, N=6, M=5, the order is: 5, 4, 6, 2, 3**, **1
Here’s a graph:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
struct Node *next;
}link;
link * creattail(int * arc, int length) {// Here we use the tail insertion method to create the linked list
int i;
link * q ; //q is used to mark the position of the last node, and then q is connected to the next new node
link * H =(link*)malloc(sizeof(link));// create the first node
H->data = arc[0];
H->next = NULL;
q = H; // remember the first node
for (i = 1; i<length; i++) {
link * a = (link*)malloc(sizeof(link));// Create new node
q->next = a; // The last node is connected to the new node, so that each new node is created at the last
a->data = arc[i]; // Assign a value to the newly created node
a->next = NULL; // Since the newly created node is the last one, its pointer field is NULL
q = a; //q now marks the newly created node as the last node, so that the newly created node can join q
}
return H;Return the first node
}
link * creatcycle (int * arc, int length) {// Here we use the tail insertion method to create the linked list
int i;
link * q ; //q is used to mark the position of the last node, and then q is connected to the next new node
link * H =(link*)malloc(sizeof(link));// create the first node
H->data = arc[0];
H->next = NULL;
q = H; // remember the first node
for (i = 1; i<length; i++) {
link * a = (link*)malloc(sizeof(link));// Create new node
q->next = a; // The last node is connected to the new node, so that each new node is created at the last
a->data = arc[i]; // Assign a value to the newly created node
a->next = H; // Since the newly created node is the last, we point to the head to form a circular list
q = a; //q now marks the newly created node as the last node, so that the newly created node can join q
}
return H;Return the first node
}
void yuesefu(link *p,int n,int m)
{ int i=1;
link * q;
q = p;
int j=1;
while(j<n&&p! =NULL) {if(i==m)// Check if I is equal to m. If m is equal to q, the pointer should exit
{
i=1;
j++; // Count nodes
printf("%d,",p->data);
q->next = p->next; // The last node is connected to the current next node
free(p); // Release the node
p=q->next; Since I assign I to 1, I point p to the next q
}
else
{
i++;// Count +1 without reaching position
q =p; // mark the current location, because P is going to the next location
p=p->next;// to the next node
}
}
printf("%d",p->data);// Outputs the last node
free(p);
}
void display(link *p) { // The output function of the list, traversing the list
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void displaycycle(link *p,int a) { // Because it is a circular list, no matter which node it is, it can traverse the entire list
int i=0;
while (i<a) {
i++;
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int a[6] = { 1.2.3.4.5.6};
link * cycle = creatcycle(a, 6); // Create a circular list by using the tail insertion method
displaycycle(cycle,6); // Output
yuesefu(cycle,6.5); // Joseph loop implementation, cycle represents the list of cycles, 6 represents the sum of points, 5 is the number of positions output
free(cycle);
return 0;
}
Copy the codeEffect display:
2. Bidirectional linked lists
The girl’s face a breeze through the window, she seemed to be watching what, downstairs the crowd of people crossing the street, there is a boy, she watched, until the boy watched her, their eyes in communication, a girl with filar silk ruddy face, like the peach blossom, just opened slightly red, also like peach, sweet, the boy’s eyes, such as general electric, sharp, Charming, they look relatively, escape from each other, and pulling each other, the girl quickly go out, come, stairwells, she hesitated, he will go there, this way also can up and down, there can also be there, and the boy also hesitated, bad weather, between them, a downstairs and one upstairs, miss each other, the boy shook her head and said: “Next time you see her, you must ask her to pay the rent.” The girl sighed. “Thanks to run of quick, or you will pay the rent in the”, ha, ha, ha, girl downstairs is to list down the traverse the next, and the boy upstairs is upwards through the port, between them is the equivalent of two linked list, but have the students ask, if I were the boy went up to half, I found her not, and then to the other side, can meet her, It means that our classmates are still very smart, which is equivalent to me going down half of the way, and then going up and back to the starting point, which can be done in a two-way list, two-way list is like an elevator can go up and down, the floor is our data.
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
struct Node *port,*next;
}link;
link * creat(int * arc, int length) {// Use the tail insertion method to create
int i=0;
link * q,* p,*head;
head = q = p=(link*)malloc(sizeof(link));// create the first node
q->data = arc[0];
q->next = NULL;// The first node is followed by NULL
q->port = NULL;// The first node is preceded by NULL
for (i = 1; i<length; i++) {
p = (link*)malloc(sizeof(link));// Create new node
p ->data =arc[i];
p ->port = q; // The new node precursor connects to a node
q ->next = p;// The successor of the previous node joins the current node
q =p; // Add the previous node's flag q to the new node
p->next =NULL; // The new node's pointer field points to NULL
}
return head;
}
void displayport(link *p) { // The output function of the list, traversing the list using precursors
while (p) {
printf("%d ", p->data);
p = p->port;
}
printf("\n");
}
void displaynext(link *p) { // The output function of the linked list, using the successor to traverse the list
printf("%d ", p->data);
while (p->next) {
p = p->next;
printf("%d ", p->data);
}
printf("\n");
displayport(p);// Pass the last node with a subsequent output
}
int main(int argc, char *argv[]) {
int a[6] = { 1.2.3.4.5.6};
link * list = creat(a, 6);
displaynext(list);// Use subsequent output
}
Copy the codeThe blogger uses the tail insertion method to create a new effect to show:
Insert and delete:
3.1 Insertion of bidirectional linked list, insertion needs two nodes, note: it is ok to maintain the successor of P is the last break, that is, the position of the other steps in the fourth step is not required.
void insert(link *p,int n,int m)// Insert data m after position NTH
{
int i= 1;
while(i<n)
{
p =p->next;
i++;
}
link * q=(link*)malloc(sizeof(link));// Create a node
q->data = m;// add m to q
p->next->port = q;//2. P ->next connects to the new node
q->next = p->next;//1. Connect p->next
q->port = p;//3 The precursor of the newly inserted node points to p
p->next = q;//4 p; Note The first three positions can be moved freely
}
Copy the codeEffect display:
3.2 Delete bidirectional linked list, only need one node, can be completed
void deletelist(link *p,int n)
{
int i=1;
while(i<n)
{
p =p->next;
i++;
}
p->port->next = p->next;/ / the first step
p->next->port = p->port;/ / the second step
free(p);/ / the third step
}
Copy the codeEffect: I deleted the data for the 3 position in the linked list
3. Circular bidirectional linked lists
3.1 Circular bidirectional linked lists and circular single linked lists are similar, but there are more precursor nodes, can be executed forward.
3.2 Creating a circular bidirectional linked list, let’s roll it up, you guys
link * creatcycle(int * arc, int length) {// Use the tail insertion method to create
int i=0;
link * q,* p,*head;
head = q = p=(link*)malloc(sizeof(link));// Create the first node
p->data = arc[0];
p->next = p;// The first node is followed by NULL
p->port = p;// The first node is preceded by NULL
for (i = 1; i<length; i++) {
p = (link*)malloc(sizeof(link));// Create a new node
p ->data =arc[i];
p ->port = q; // Step 3: connect the new node to a node
q ->next = p;// The last node joins the current node
p->next =head;// Step 5: The last node points to head
head->port = p;//head precursors point to p
q =p; // Add the previous node's flag q to the new node
}
return head;
}
void displaycycle(link *p) { // The output function of the linked list, using the successor to traverse the list
link * head=p;
printf("%d ", p->data);
p = p->next;
while(p! =head) { printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
Copy the codeEffect display:
Conclusion:
Data structure, the operation of the linear chain table we basically operation, circulation of two-way chain table insertion and deletion and two-way table inserted delete is the same, we didn’t do more for the operation, if you have any questions, comments can ask me, we can discuss together, learning or knock it yourself, blogger provide code can be directly built projects run, You can also follow the steps of the blogger summary, step by step. Well, creation is not easy, I hope you like, like, pay attention to, comment, favorites, bloggers will follow the data structure to the following update, there are like you can collect oh. I’ll put up a picture for you to roll up.
