C语言链表很不明白，求详细说一下，非常感谢

Question

C语言链表很不明白，求详细说一下，非常感谢！非常感谢，越详细越好。

Answer 1

既然百度上都有了我就说说我的理解

我觉得‘’链表‘’故名思义就是将一些东西连锁起来成一个串，或者环形的，想来想去如果这些东西一一对应那就只有线和环两种形态了

而这些东西就是数据，我理解就是一个个变量，或者书中所说的节点，链接他们的东西就是指针了

传说是约瑟夫提出这么一个问题编号为1，2， 。。。，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。

这里，选择使用链表来实现，具体的使用单链表中的循环链表来实现。

首先先说下链表的实现，

1>为了创建一个链表，首先先建一个节点结构：前面说到有变量和线索链接（定义成数据域和指针）

struct Node{
   int Data;
   Node *next;
};

节点的数据域存放计算的数据，节点的next指针域存放指向下一节点的地址

2>然后创建我们的链表类List类,在List类中我们要添加实现链表操作的方法，（这些就算是基本操作了）包括:

List();
void insertNode(int val);//插入到所给值得前面
void deleteNode(int val);
bool empty();
void outputNode();

还要添加一个私有成员， Node *head; 即头指针；

构造函数:  初始化head = NULL;

插入操作：

首先新建节点并初始化，

Node *s;
s = (Node*)new(Node);
s->Data = val;

进行一下判断：

    (1).if(head==NULL)//头指针为空

    (2).Node *p = head;

         if(p->Data==val)//插入点为第一个节点

    (3).Node *q;

        while(p->Data != val)//循环寻找插入节点

     (4).if(p->next == NULL)//插入节点是尾节点

删除操作：

首先建两个指针，Node *p,*q;判断：

    (1).if(head == NULL)//链表为空

    (2).p= head;

         if(p->Data == val)//删除节点是第一个节点

    (3).while((p->Data != val)&&(p->next != NULL))//循环寻找删除节点

    (4).if(p->Data == val)找到节点

             if(p->next == NULL)//节点不存在

判空操作：

    这是一个可选的方法，return head == NULL;//判断链表是否为空

输出操作：

    定义一个指针，Node *current;

    初始化为  current = head;

    循环输出  while(current->next != NULL)

以上就是一个能实现基本操作的链表类，这里只给出了算法，希望能够理解

3>下面说下约瑟夫算法的实现，使用循环链表

    循环链表同单链表基本相似，只是循环链表尾节点的next指针始终指向链表的首地址，因此在插入删除操作时会有些不同的地方

节点结构同上，

为了实现约瑟夫算法

添加如下方法：

List();
void init(int val);//向链表中添加值
void deleteNode(int val);
bool empty();
void output();
void calculate();//计算约瑟夫算法
void setM(int val);
添加私用成员，Node *head;
int m;
int counter;//记录链表中的节点的个数

构造函数:

head= (Node*)new(Node);
counter = 0;
head->Data = counter;
head->next = NULL;

插入操作：

//这里为了具体实现约瑟夫算法，只是在链表的结尾添加数值
              Node *s,*p;
              s = (Node*)new(Node);
              s->Data = val;
              if(head->next == NULL)//首节点
                 head->next = s;
                 s->next = head->next;
                 counter++;
                 head->Data = counter;
              else 
                 p = head->next;
                 while(p->next != head->next)//找到链表尾节点
                 p = p->next;
                 p->next = s;
                 s->next = head->next;
                 counter++;
                 head->Data = counter;

删除操作：

//这里和单链表不太一样
               Node *p,*q;
              p=head->next;
              if(head->next == NULL)//空链表
                   return;
              if(p->next == head->next)//p是第一个节点，这时候要把尾节点的next指针指向第二个节点
                    q = p;
                  while(q->next != head->next)//找到尾节点
                             q = q->next;
                    head->next = p->next;
                    q->next = head->next;将新的头结点next域赋给尾节点的next域
                    delete p;
                    counter--;
                    head->Data = counter;
              while(p->Data != val)//寻找节点
                    q = p;
                    p = p->next;
              q->next = p->next; 
              delete p; 
              counter--; 
              head->Data = counter;

输出操作：

Node *current = head->next;
              while(current->next != head->next)//输出节点

判空操作：

return head->Data == 0;

计算操作：

 Node *temp;//用来存放循环的下一节点的指针
                temp = head->next;
       loop:    Node *p;//这里使用的是goto语句，当然也可以用其他的方法：）
                  p = temp;
                 int count = 1;//计数器
                 while(count != m)
                           count++;
                           p= p->next;
                 m = p->Data;
                 temp = p->next;//保护现场：赋值，存放指针
                 deleteNode(p->Data);
                 if(!empty())//判空
                       output();
                       goto loop;
                 else
                       cout<<"FINISH！"<<endl;
setM(int val): m = val ；

这里想说的是，在删除循环链表的第一个节点的时候，不要忘了给尾节点的next指针赋一个新的值！

Answer 2

自己百度，要多详细有多详细。