约瑟夫问题

（用new创建新的空间） 结构体（包含数据域和指针域）





#include<bits/stdc++.h>
using namespace std;
1.对于动态链表,由于是链式存储的，空间不一定是连续的，所以需要指针，定义一个动态链表的节点的一个结构体
//定义一个链表的节点：数据域data和node类型的指针next（存下一个节点的地址）


struct node{
	int data;
	node* next;
};
int main(){
	//读入人数、需要查询的人的编号
	int n,m;
	scanf("%d%d",&n,&m);
    
    
2.创建动态链表，一般常用到的三个指针：head（记录头结点的地址）、now（记录目前链表的最后一个节点的地址）、p（用于创建新的节点的指针）
	//定义指向节点的指针*head （记录头结点）*now（记录当前链表的最后一个节点）
	//*p（用于创建新的节点） *pre（用于存第m个人的前一个节点的地址）
	node* head,*now,*p,*pre;//不要忘记*
    
    
3.创建动态链表：（指定头节点的写法）
//用head节点new创建一个链表的头结点
	//将head->data=1,head->next=NULL
	//将*now指针取head的地址，表示当前链表的最后一个节点的地址
	head=new node;
	head->data =1;
	head->next =NULL;
	now=head;
	//创建链表，从第2个节点开始一直添加到第n个节点
	//用*p指针创建一个新的节点，将p->data=i,p->next=NULL
	//再将新创建的节点与前面一个节点相连接（尾插法）：now->next=p;
	//再更新now为p
	for(int i=2;i<=n;i++){
		p=new node;
		p->data =i;
		p->next =NULL;
		now->next =p;
		now=p;
	}
    
    
4.判断创建的链表是否需要首尾相连，形成循环链表
	//最后由于链表是首尾相连的，所以让now->next=head;
	now->next =head;
    
    
5.遍历整个链表，查询满足条件的节点，输出节点信息，删除节点，释放空间
由于进行增删操作，需要改变前后节点的指针的指向，所以需要一个指针*pre记录下进行修改的前一个节点的地址，由于需要输出需要查询的节点的信息，所以需要一个指针*now记录下需要进行修改的节点的地址。
再将前一个节点指向需要删除的节点的后一个节点，由于之前是用new开了新空间，所以现在由于删除了这个节点，就可以将这个节点的空间给释放掉了。

	//进行数数
	//先将now和pre取址head
	now=head;pre=head;
	//只要还有大于一个人，就继续循环
    
    while((n--)>1){
		//循环从1到m-1,每次先记录下当前的节点：pre=now
		//再将now进行移动到下一个节点：now=now->next
		//这样最后经过这个for循环之后now指向的是第m个节点，而pre是指向第m-1个节点
		for(int i=1;i<m;i++){
			pre=now;
			now=now->next ;
		}
		//输出第m个节点的对应的人的编号
		printf("%d ",now->data);
		//输出之后跳过第m个节点：pre->next=now->pre
		//第m个节点已经没用了，就可以将其delete掉了
		pre->next =now->next ;
		delete now;
		//再进行下一轮：将now更新为pre->next;
		now=pre->next ;
	}
    
    
    
6.输出最后一个节点的信息后，将空间释放，这样由于每次删除一个节点，就将对应的空间释放掉了，所以最后链表所占的空间为0
	//跳出while循环之后就只剩下一个节点，输出这个人的编号，
	//再释放最后一个节点的内存空间
	printf("%d",now->data );
	delete now;
	return 0;
}

插排

（用malloc创建动态链表）（结构体包含数据域和指针域）

题目描述 alt

AC代码:

#include<stdlib.h>


1.对于动态链表,由于是链式存储的，空间不一定是连续的，所以需要指针，定义一个动态链表的节点的一个结构体
/*由于要用创建动态的单向链表，所以需要用到指针，定义一个结构体：
用于表示链表的一个节点*/

struct node{
     int data;
     struct node *next;
};
int main(){


2.创建动态链表需要三个基本的指针：*head，*now, *p
	//对于一个动态链表来说:通常来说有至少4个节点指针：
	/* struct node *head(用来存链表的头结点的地址）,*now(用于记录当前链表的最后一个节点），*p(用于创建新的节点）,*t（获得链表的首地址，用于后期的遍历链表）*/
    
    
3.创建动态链表（用malloc开新的空间）（没有固定头结点的写法）
    struct node *head=NULL;
struct node *now,*p;
    /*这个链表需要存多少个节点就进行几次循环，每次循环创建用malloc创建一个新的节点，将节点对应的数据域存入，每个新的节点的指针指向NULL
    判断一下如果是head=NULL即表示当前新创的节点就是链表的头结点，所以将该节点的地址赋给head
    否则就将now指向刚刚新创的节点，之后由于为了进行尾插，所以更新now的值*/
    
    for(int i=1;i<=10;i++){
        int x;
        scanf("%d",&x);
        p=(struct node*)malloc(sizeof(struct node));
        p->data=x;
        p->next=NULL;
        if(head==NULL){
            head=p;
        }else{
            now->next=p;
        }
     
     //注意由于无论新创建的节点是不是新的节点，链表的最后一个节点都得到了更新，所以now要更新为新创的这个节点p,注意该语句存放的位置
        now=p;
}


  int m;
    scanf("%d",&m);
struct node *t=head;



4.遍历整个链表，找到指定位置的节点，在两个节点间插入一个新的节点
    /*注意对于在链表中的某两个节点进行插入一个节点的方法：
    1.先要遍历整个链表：1获取头结点的地址2.循环条件！=NULL 3.迭代的语句：t=t->next
    2.由于插入一个节点，需要改变的的是该节点之前的和本节点的next指针，所以先要根据查询的条件找到前一个节点的位置pre和后一节点的位置
    3.再创建一新的节点，填入节点的信息
    4.将该新节点指向pre的下一个节点，将pre指向新创建的节点*/
    
    
    while(t!=NULL){
        if(t->next->data>m){
            p=(struct node*)malloc(sizeof(struct node));
            p->data=m;
            p->next=t->next;
            t->next=p;
            break;
        }
        t=t->next;
}



**5.遍历整个链表**
	/*想要遍历整个表：
1.先获得这个表的首地址 2.在设置while循环的条件（t！=NULL），就进入循环执行循环体中的内容，不要忘记要让t一个一个不断向后一个节点移动，否则会进入死循环*/   
2.For(struct node *t=head;t!=NULL;t=t->next)
     t=head;
    while(t!=NULL){
        printf("%d ",t->data);
        t=t->next ;
    }
    return 0;
    
    
    
}