C++单向链表（数组）遍历出现死循环

Question

n次操作，1 x说明x出现1次，2查询当前出现次数最多次数

不知道哪里有问题，程序会死循环。感谢指导。

输入样例
6
1 1
2
1 2
2
1 2
2
输出样例
1
1
2

#include<iostream>
using namespace std;

template <class T>

struct node{//单向链表模板类 
    T next,val,cnt;
};

struct node<int> a[1001];

int main(){
    int n;
    cin>>n;
    a[0].val=0;a[0].cnt=0;a[0].next=1;
    for(int i=1;i<n;i++){//初始化 
        a[i].val=0;a[i].next=-1;a[i].cnt=0;
    }
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x==1){
            int y,p=a[0].next;
            cin>>y;
            while(1){
                if(a[p].val==y){
                    a[p].cnt++;
                    break;
                }
                if(a[p].next==-1)break;
                p=a[p].next;
            }
            if(a[p].next==-1&&a[p].val!=y){//第一次添加 
                a[p].next=y;
                a[y].val=y;
                a[y].cnt=1;
            }
        }else if(x==2){
            int ans=0,num=0,p=a[0].next;
            while(1){
                if(a[p].cnt>ans){
                    ans=a[p].cnt;
                    num=a[p].val;
                }
                if(a[p].next==-1)break;
                p=a[p].next;
            }
            cout<<num<<endl;
        }
    }
    return 0;
}

Answer 1

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7488576
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：C++奇偶排序，从键盘输入n(n＜100)个整数（以0结束），存放在一个一维数组中，将它们按奇数在前、偶数在后，同为奇数或偶数的按从小到大的顺序排序，并输出排序后的结果。
• 除此之外, 这篇博客: 网球循环赛 算法分析与设计(C++)中的 3）当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 书中对于2k2^k2k 的运动员的赛程安排在这里便行不通了，所以需要考虑新的办法。

  如果当n为奇数时，可以考虑补充一个虚拟对手，即让n+1为偶数，多出的虚拟对手，代表轮空。

  接下来考虑如果n/2为偶数，则可以同2k2^k2k一样的方法来进行填充，而如果n/2为奇数的话，需要进行新的处理。

  综上，下面以n=6为例说明算法：

  #define rep(i,s,n) for(int i=s;i<n;i++) //循环
  void tournament(int n)
  {
  	if (n == 1)
  	{
  		a[n][n] = 1;
  		return;
  	}
  	if (n % 2 == 1)//奇数
  	{
  		tournament(n + 1);
  		return;
  	}
  	tournament(n / 2);
  	match_copy(n);
  
  }
  

  主递归函数，先判断n是否为奇数，如果为奇数，则转换为求解n+1的问题

  void match_copy(int n)
  {
  	if (n / 2 > 1 && odd(n / 2))
  		copyodd(n);
  	else
  		copy(n);
  
  }
  
  

  考虑n/2的奇偶性，分别做出处理

  void copy(int n)
  {
  	int m = n / 2;
  	for (int i = 1; i <= m; i++)
  	{
  
  		for (int j = 1; j <= m; j++)
  		{
  			a[i][j + m] = a[i][j] + m;
  			a[i + m][j] = a[i][j + m];
  			a[i + m][j + m] = a[i][j];
  			
              /*
  			rep(i, 1, 9) {
  				rep(j, 1, 9)
  				{
  					cout << a[i][j] << " ";
  				}
  				cout << endl;
  
  			}
  			*/
  			
  		}
  
  	}
  
  }
  
  

  该函数对n/2为偶数的情况进行处理。类似于书中的2k2^k2k的处理方式

  具体操作过程是将n一分为2，通过一个正方形中左上角的值来得到其他三个角的值。

  右上角的值=左上角值+m，右下角值=左上角值，左下角值=右上角值

  以n=2为例：初始仅有一个1，但经过操作后可得到如下结果

  1	2
  2	1

  又如n=4:初始时仅有4个值，但是通过左右两次循环，上下两次循环 可以得到如下结果

  1	2	1+2=3	2+2=4
  2	1	2+2=4	1+2=3
  3	4	1	2
  4	3	2	1

  经过这样是可以解决n/2 为偶数的情况，现在再回到主递归函数，来从n=4生成n=6

  void copyodd(int n)
  {
  	int m = n / 2;
  	rep(i, 1, m + 1) {
  		b[i] = m + i;
  		b[m + i] = b[i];
  	}
  	rep(i, 1, m + 1)
  	{
  		rep(j, 1, m + 2)
  		{
  			if (a[i][j] > m)
  			{
  				a[i][j] = b[i];
  				a[m + i][j] = (b[i] + m) % n;
  			}
  			else
  				a[m + i][j] = a[i][j] + m;
  		}
  		rep(j, 2, m + 1)
  		{
  
  			a[i][m + j] = b[i + j - 1];
  			a[b[i + j - 1]][m + j] = i;
  
  		}
  
  
  	}
  } 
  

  首先我们需要一个循环数组b，他是为了保证我们生成的后两列不会出现重复

  比如我们这里的b为 4，5，6，4，5，6 很明显 第一行可以取4，5 第二行 取5，6 第三行取6，5，这样就正好补齐了前三行的后两列

  接着我们通过以现有值叠加m的方式来得到后几行的结果，以第一行的值来确定第四行的值，第二行的值来确定第五行的值，第三行的值来确定第六行的值。

  第一次循环：i=1 时，我们依次判断，通过第一个j循环可以得到以下结果

  1	2	3	4
  2	1	4	3
  3	4	1	2
  1+3=4	2+3=5	3+3=6	（4+3）%6=1

  接下来进行下一个j循环，可以得到如下结果

  1	2	3	4	5	6
  2	1	4	3
  3	4	1	2
  4	5	6	1
  				1
  					1

  第二次循环：i=2时

  1	2	3	4	5	6
  2	1	4$\to$5	3
  3	4	1	2
  4	5	6	1
  2+3=5	1+3=4	(5+3)%6=2	3+3=6	1
  					1

  接下来进行下一个j循环，可以得到如下结果

  1	2	3	4	5	6
  2	1	5	3	6	4
  3	4	1	2
  4	5	6	1		2
  5	4	2	6	1
  				2	1

  第三次循环:i=3时

  1	2	3	4	5	6
  2	1	5	3	6	4
  3	4→64\to64→6	1	2
  4	5	6	1		2
  5	4	2	6	1
  3+3=6	(6+3)%6=3	1+3=4	2+3=5	2	1

  接下来进行下一个j循环，可以得到如下结果

  1	2	3	4	5	6
  2	1	5	3	6	4
  3	666	1	2	4	5
  4	5	6	1	3	2
  5	4	2	6	1	3
  6	3	4	5	2	1

  综上我们就得到了n=6的情况，其具有一般代表性 如果n为奇数则加1，多出的一个选手代表轮空即可

  算法分析：

  T(n)=T(n/2)+O(n2)T(n)=T(n/2)+O(n^2)T(n)=T(n/2)+O(n2)

  根据主定理可知T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)