C语言链表很不明白,求详细说一下,非常感谢
发布网友
发布时间：2022-05-27 04:01
共2个回答
热心网友
时间：2022-05-24 04:06
既然百度上都有了我就说说我的理解
我觉得‘’链表‘’故名思义就是将一些东西连锁起来成一个串，或者环形的，想来想去如果这些东西一一对应那就只有线和环两种形态了
而这些东西就是数据，我理解就是一个个变量，或者书中所说的节点，链接他们的东西就是指针了
传说是约瑟夫提出这么一个问题编号为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指针赋一个新的值！
热心网友
时间：2022-05-24 05:24
