想用memset对结构中的动态数组进行初始化

18222936370

1. #include<iostream>
   
2. #include<memory>
   
3. using namespace std;
   
4. struct DAG
   
5. {
   
6.         int depth;
   
7.         int *next;
   
8. };
   
9. int main()
   
10. {
    
11.         int m,n,M,N;
    
12.         cin>>m>>n;
    
13.         DAG *point=new DAG[m];
    
14.         for(int i=0;i<m;i++)
    
15.         {
    
16.                 point[i].depth =0;
    
17.                 point[i].next =new int[m+1];
    
18.                 memset(point[i].next,-1,sizeof(point[i].next));
    
19.         }
    
20.         for(int i=0;i<n;i++)
    
21.         {
    
22.                 cin>>M>>N;
    
23.                 M--;N--;
    
24.                 int x=0;
    
25.                 while(point[M].next[x]!=-1 )x++;
    
26.                 point[M].next[x]=N;
    
27.                 point[N].depth ++;
    
28.         }
    
29. }

复制代码

我想用memset函数将结构中的point.next指向的数组进行初始化，使数组的每一项都初始化为-1.
可是现在遇到的问题是只有point.next[0]是-1，其他的项并未被初始化，请问该怎么办。

weishuo1999

memset(point[i].next,-1,sizeof(point[i].next));
改成
memset(point[i].next,-1,m+1);

18222936370

回复 2# weishuo1999


    试了一下，可是还是不可以，不知道问题出在哪里了。memset可以这么用吗？还是说这种情况下只能用for循环啦？

sanagi1987

memset(point[i].next,-1, sizeof(int) * (m+1));
或者
memset(point[i].next,0xff, sizeof(int) * (m+1));

weishuo1999

memset可以这么用，不知道你怎么验证得出还是不行的，可以把完整代码贴一些回复 3# 18222936370


   

weishuo1999

sorry， 刚man了一下memset的函数说明，如下
The memset() function writes len bytes of value c (converted to an unsigned char) to the string b.

可以看到的是这种情况下，size是按照char的字节赋值的，所以前面的格式就变成了
一个int被分割为4个char字节，每个字节的值是-1（而且是unsigned的）

18222936370

回复 5# weishuo1999

1. /*算法原理是：
   
2. 每次找到第一个结点，将其提取出来并消掉其后的边，之后再找下一个节点。
   
3. 若在所有节点并未被提取出时出现找不到当前第一个结点的情况，则存在圈。
   
4. 此时任意一个节点沿其后的边进行查找，直至回到该节点，都是这个图中的一个圈。
   
5. 若能顺利查找完所有结点并不存在圈，则是DAG。
   
6. */
   
7. /*实现方法：
   
8. 将图想象成一个树，用depth表示某节点的深度，则所找的第一个节点应为depth为0的节点
   
9. 当找出第一个点之后，该点的所有孩子的depth减一
   
10. 此时再将这一点的depth变为-1，定义其为已查找过
    
11. 某一时刻遍历时不存在depth为0的点则说明已查找完或存在圈
    
12. 时间复杂度为O(n^2)*/
    
13. #include<iostream>
    
14. #include<memory>
    
15. using namespace std;
    
16. struct DAG
    
17. {
    
18.         int depth;
    
19.         int *next;
    
20. };
    
21. int main()
    
22. {
    
23.         int m,n,M,N;
    
24.         cin>>m>>n;
    
25.         DAG *point=new DAG[m];
    
26.         for(int i=0;i<m;i++)
    
27.         {
    
28.                 point[i].depth =0;
    
29.                 point[i].next =new int[m+1];
    
30.                 memset(point[i].next,-1,m+1);
    
31.                 /*for(int j=0;j<m+1;j++)
    
32.                 {
    
33.                         point[i].next[j]=-1;
    
34.                 }*/
    
35.         }
    
36.         for(int i=0;i<n;i++)
    
37.         {
    
38.                 cin>>M>>N;
    
39.                 M--;N--;
    
40.                 int x=0;
    
41.                 while(point[M].next[x]!=-1 )x++;
    
42.                 point[M].next[x]=N;
    
43.                 point[N].depth ++;
    
44.         }
    
45.         for(int i=0;i<m;i++)
    
46.         {
    
47.                 int y=0,j=0,x=0,k=0;
    
48.                 for(j=0;j<m;j++)
    
49.                 {
    
50.                         if(point[j].depth ==0)y++;
    
51.                         break;
    
52.                 }
    
53.                 if(y==1)
    
54.                 {
    
55.                         while(point[j].next[x]!=-1)
    
56.                         {
    
57.                                 point[point[j].next[x]].depth --;
    
58.                         };
    
59.                         point[j].depth =-1;
    
60.                 }
    
61.                 if(y==0)
    
62.                 {
    
63.                         cout<<"No"<<endl;
    
64.                         break;
    
65.                 }
    
66.                 if(y==1&&i==(m-1))cout<<"Yes"<<endl;
    
67.         }
    
68.         return 0;
    
69. }

复制代码

题目就是判断一个图是否是有向无圈图，这是我写的代码。
给的样例输入是

5 7(第一个为结点数 第二个为边数)
1 2(第一个是根结点，第二个是指向的结点)
1 3
2 1
2 5
3 4
4 2
4 5
输出是 No
如果换成注释的for的那一段就可以执行。

18222936370

回复 4# sanagi1987


    这种方法可以，多谢。已牢记在心

18222936370

回复 6# weishuo1999


    原来是这个原理，我刚才按4楼说的将它的类型强制转换为int，就实现了，多谢啦。

socay2

               
point.next =new int[m+1];
memset(point.next,-1,sizeof(point.next));

memset 第三个参数表示要格式化的字节数(Bytes)
sizeof(point.next) 明显等于4 (32位下)

答案在四楼