【算法】—— 链表类问题

1. 三种常见考点

单链表进行排序时，一定用冒泡排序。只交换两个节点的data就行了，不用发生指针的移动。

2. 链表类的都需要定义结构体

2）在二叉树中 

这里结合二叉树学习的，再来复习一下结构体的规则：

typedef struct node{
	char data;
	struct node *lchild,*rchild;
}*BitTree;  //和【int *p】一样，*在指针变量p的前面 
			//同理，node和BitTree尽量不要重名，和【int】与【p】的关系是一样的

3. 创建链表

1）节点

在C++中创建一个节点用new 结构体名()或者new 结构体名。

struct node*head;
head=new node();  //或者head=new node;

在C语言中

struct node *head;
head=(struct node*)malloc(sizeof(node);

这里的“head=”是指向的意思，不要认为此时head就是头结点，它只是头结点的指针，但是它可以操纵头结点。对于其他指针也一样，比如now指针，它并不是当前节点，只是指向当前节点，但是它可以操纵当前节点。

 2）在二叉树中

        复习了链表以后，才理解了创建二叉树时的new node操作—— 创建一个新结点，让结构体指针指向这个新结点

3）尾插法创建链表

struct node *head,*tail,*now;

head=new node(); //创建头结点
head->next=null; // 避免野指针

tail=head; //此时头结点就是尾结点


for(int i=1;i<=一共有多少个;i++){
    now=new node();
    tail->next=now;
    tail=tail->next;
    tail->next=null;
}

4)头插法

我不喜欢用头插法 

输入
10
2 5
输出
6,1，7,3，10,9，2,5，8,4

# include
using namespace std;

struct node{
	int num;
	struct node *next;
};

int main(){
	int totalMonkey; //猴子总数 
	int start;  //从第几只猴子开始 
	int number;  //报的数
	struct node *head,*tail,*now,*pre;
	
	cin>>totalMonkey;
	cin>>start;
	cin>>number;
	 
	head=new node();  //创建头结点 
	head->num=1;
	head->next=NULL;
	tail=head;
	for(int i=2;i<=totalMonkey;i++){ //尾插法创建链表 
		now=new node();
		now->num=i; 
		tail->next=now;
		tail=now;
		tail->next=NULL; 
	}
	tail->next=head;//连成一个环
	 
//	
//	for(int i=1;i<=totalMonkey;i++){
//		cout<num<<" ";
//		head=head->next;
//	} 

    
    //先找到最开始报数的猴子，用now标注
	now=head;
	pre=tail; //pre在now前面一个 
	for(int i=1;i<=start-1;i++){
		now=now->next;
		pre=pre->next;
	} 
	while(now->next!=now){
		//报数ing
		for(int i=1;i<=number-1;i++){
			now=now->next;
			pre=pre->next;
		} 
		//此时now指向的猴子结点退出
		cout<num<<",";
		pre->next=now->next;
		now->next=NULL;
		now=pre->next; 
	}
	cout<num; //最后一只猴子 
    return 0;
}

 发现自己深入理解一下结点指针和结点的关系后，写起代码来比以前简洁多了！