在链表中查找循环（出现分段错误）

Question

这个解决方案基于关于计算机的一个非常重要的观察。 在我的系统中，指针大小为8字节。 这个结构的大小

 struct ll1
 {  
  int data;
  struct ll1 *next;
 };

结构体指针有多个成员时，其大小为16字节。由于内存对齐的缘故，结构体指针总是带有一些尾随的零值。所以我尝试使用剩下的4个字节来存储访问标志。当我将0分配给这4个字节时，不会出现错误，但是当我分配非零值时，下面的代码会导致分段错误。请问有人可以解释为什么会出现这种情况吗？

#include<stdio.h>
#include<stdlib.h>
struct ll1
{
    int data;
    struct ll1 *next;
};
typedef struct ll1 ll;

void create(ll **root)
{

int t=1;
printf("\nEnter node value 0 if end:");
    scanf("%d",&t);
    if(t)
    {
        (*root)=(ll*)malloc(sizeof(ll))    ;
        (*root)->data=t;
        create(&(*root)->next); 
    }
    else
    (*root)=NULL;
}
int main()
{

    ll *node;
    create(&node);
    ll *temp=node,*temp2=node;
int j,size=0;

/*printing 4-4 bytes of the node */
while(temp->next)
{
    size++;
    int *p=(int *)temp;
    printf("\n%d %d %d %d",*(p),*(p+1),*(p+2),*(p+3));
    *(p+3)=0; // setting the value of last four byte zero
    temp=temp->next;

} 
printf("\n");

j=size/3;

/* making loop in the linklist */

while(j--)temp2=temp2->next;
temp=node;

while(temp->next!=NULL)temp=temp->next;
temp->next=temp2;   

/*loop created */



/* code for finding loop in the linklist */
printf("\nfinding loop in the linklist\n");
ll *root=node;  
int *pp=(int *)root;
printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3));
printf("%d \n",root->data);
while(*(pp+3)==0) 
{

    *(pp+3)=1; //when changed that line by *(pp+3)=0 it doesn't give any error 
    root=root->next; //move pointer to next
    pp=(int *)root;  // assign adress to integer pointer
    printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3));  // segmentation fault is here 
    printf("%d \n",root->data);
}
printf("%d \n",root->data);
return 0;

}

GDB中的输出

(gdb) r 
Starting program: /home/kushagra/place/linklist/a.out <ll_in

Enter node value 0 if end:1
Enter node value 0 if end:2
Enter node value 0 if end:3
Enter node value 0 if end:4
Enter node value 0 if end:5
Enter node value 0 if end:6
Enter node value 0 if end:7
Enter node value 0 if end:8
Enter node value 0 if end:8
Enter node value 0 if end:0
1 0 6299696 0
2 0 6299728 0
3 0 6299760 0
4 0 6299792 0
5 0 6299824 0
6 0 6299856 0
7 0 6299888 0
8 0 6299920 0
8 0 6299952 0

finding loop in the linklist
1 0 6299696 0
1 

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a2e in main () at P_node.c:72
72          printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3));  // segmentation fault is here 

- Kushagra Jaiswal

---

为什么要依赖字节对齐呢？只需添加另一个字段来跟踪已访问的内容即可。 - Karthik T

@Karthik T-那个可以工作，但是为什么这段代码会出错呢..?? - Kushagra Jaiswal

我不确定这个问题.. 你尝试用gdb或类似的调试器运行它了吗？ - Karthik T

我试过了，这是输出：程序收到 SIGSEGV 信号，分段错误。 0x0000000000400a2e 在 P_node.c 的 main() 函数中：第72行 printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3)); // 分段错误在这里 (gdb) - Kushagra Jaiswal

不要在C语言中强制转换malloc()的返回值。即使在C语言中也不要这么疯狂。 - unwind

Answer 1

它没有“尾随零”。在int和指针之间可能有4个未使用的字节。

这个*(pp+3)=1可能会修改指针内的四个字节。

使用：

struct ll1
 {  
  int data;
  int visited;
  struct ll1 *next;
 };

- Henrik

---

如果你检查/展示 *(pp+3)=1 是否真的改变了指针，我会给你加上 +1。 - user1944441

@Armin：Henrik 是对的。只需在结构体的单个实例上进行测试即可。(pp+3) 指向结构体开头的第三个整数，并将其放置在名为 next 的变量中... - Malkocoglu

@Malkocoglu在第二行谈到了OP的结构体示例。他说可能是这样。我只是想比那更确定一些。 - user1944441

@所有人 - Henrik是对的，当我用*(pp+1)替换了那行代码中的*(pp+3)后，这段代码就不再出现段错误了。非常感谢你，Henrik。 - Kushagra Jaiswal

@Armin 我说“可能”是为了强调依赖于精确的结构布局仅仅为了节省几个字节并不是一个好主意。 - Henrik

Answer 2

你没有检查是否到达了链表的末尾。你也应该进行检查。

while(*(pp+3)==0 && root->next) 

- Karthik T

---

链表中存在循环，因此不需要使用 root->next。 - Kushagra Jaiswal

啊，我明白了，你是故意创建一个。你检查过它是否按预期工作了吗？ - Karthik T

除了在行 *(pp+3)=1 中出现的分段错误，一切都运行良好。正如您所看到的输出。 - Kushagra Jaiswal

@user2484070 这可能有点冒险，但是你尝试过在创建循环后显示列表吗？ - Karthik T