设置循环队列与随机链表的复制（C）

1. 设计循环队列

1.1 循环队列

循环队列是一种特殊的队列，队列的首尾相连成环
循环队列有一些特点：

1. 队头删除数据，队尾插入数据
2. 给定固定空间，使用过程中不可以扩容
3. 环形队列的内存空间满了，不能继续插入数据（即插入数据失败）

1.2 队列的结构分析

题目链接: link
题目会给定队列的长度k，下面就来具体分析，怎么来实现循环队列的底层结构：
环形队列可以使用数组实现，也可以使用循环链表实现，那么用哪个来实现循环队列更好呢？接下来一一分析：

1.2.1 链表

若用链表来实现当前的循环队列，假设开始的长度k为4，那么就得循环创建4个链表，并且将它们一一链接起来，这就是链表的初始化。

现在往链表中插入数据1，2，3，4，定义两个指针phead与ptail，它们初始的情况下都指向第一个结点，往链表中插入数据，让ptail向后移动，直到将数据都全部插入完毕：

当4插入链表中后，ptail = ptail->next，又回到了链表的头结点处，构成了循环的结构。
若要删除队列中的数据，删除数据时，队列的内存空间是不能改变的，只需要指针变换指向的位置即可，所以将phead直接往后移，即phead = phead->next即可

1.2.2 数组

若用数组来实现当前的循环队列，假设开始的长度k为4，那么只需要向操作系统申请4个int（题目明给了数组中所要存储的数据类型为int）类型大小的空间即可，这就是数组的初始化。

现在往数组中插入1，2，3，4，4个数据，定义两个变量front与rear，front始终指向队列的头，rear始终指向队列的尾，并且插入数据时，都往下标为rear的位置去插，在初始情况下，front与rear都指向数组下标为0的位置，现在往数组中插入数据，将1插入数组后，再将rear++，往后继续插入，直到数据都插入完毕：

当4插入数组中后，rear++，此时rear已经越界了，这下该怎么办？原本的队列长度为4，现在rear指向的是数组下标为4的位置，那么将rear模上4，4%4不就等于0了吗？此时rear又指向了数组下标为0的位置，也构成了循环的结构。

若要删除队列中的数据，删除数据时，队列的内存空间是不能改变的，只需要变量变换指向的位置即可，所以将front直接往后移，即front++即可。

1.2.3 总结

从以上对链表和数组的分析，若以链表来实现循环队列，那么在初始化时，不仅需要创建结点的结构，还得要创建队列的结构，需要两个结构体；而以数组来实现循环队列，只需要一个结构体，大大节省了内存。所以用数组来实现循环队列更简单，但这并不意味着链表就不可以，只不过在这里，我是用数组来实现的。

1.3 数组分析

初始情况下，我们给定队列的长度k为4，定义两个变量front与rear指向队列的头位置与尾位置，此时队列中没有数据，所以front与rear都指向数组下标为0的位置处，那么我们可以发现一种情况当队列中的数据为空时，front等于rear。

现在往数组中插入数据1，2，3，4，4个数据，且数据都是往下标为rear的位置取插入，当数据都插入完毕后，rear会越界，再让rear模上k即可。由于队列的长度为4，所以插入完毕后，队列中的数据满了，那么我们可以发现一种情况当队列中的数据满了时，front等于rear。

那么就存在一个问题，倘若当前的队列满足front等于rear，那么此时的队列是什么情况，是数据为空呢，还是数据满了呢？
那么就出现了一个值得深思的问题，如何判断队列中的数据是为空，还是满了呢？很明显不能通过front等于rear来判断。
我们可不可以在队列的结构体中额外增加一个成员变量size来统计插入了多少个数据，这样一来就能判断队列中的数据是为空，还是满了。这样也可以，但是现在再增加一个条件：要求在循环队列结构中不额外增加计数器成员变量size来保存队列中有效的数据个数，这时该怎么去解决？其实可以不增加额外的成员变量，在题目中表明了队列的长度为k，说的是循环队列中的数据个数只能是k个int类型的数据，但是并不意味着循环队列的内存空间大小必须为k个int类型大小呀？也可以为k+1个int类型呀，只不过在存储数据时存储k个int类型的数据就行了呀！
所以在这里可以为数组开辟空间时，多开辟一个int类型大小的空间，即开辟k + 1个int类型大小的空间。在初始的情况下，front指向下标为0的位置处，在插入数据后，rear不断++，如下图表示，此时的k仍然将它定义为4：

这个额外多出来的空间不保存任何数据，也就意味着当队列的数据满了之后，队列中始终有一个内存空间是空出来的。
即便如此，仍然还是没有解决上面的问题——如何判断循环队列中的数据是空，还是满了，接下来就来解决这个问题。
当队列的数据为满了的情况下，rear的值为4，k为4，现在让rear + 1，此时rear的值为5，此时队列中的内存空间大小为5个int类型大小，我们让rear + 1模上k + 1，不就是5 % 5吗？等于0，而此时front的值为多少，为0对吧？是不是就满足（rear + 1） % （k + 1）= front这个式子呀？那么当满足（rear + 1） % （k + 1）= front 这个表达式时，就可以说明队列的数据满了。有人可会有疑问，上面的情况是否是偶然？下面就来说明这并不是偶然：

那么接下来再来回顾那个问题——如何判断队列中的数据是为空，还是满了呢？
当front == rear 时，说明队列中的数据为空；当（rear + 1） % （k + 1）== front 时，说明队列中的数据满了。

1.4 编写代码

1.4.1 分析题目

题目中给明了我们要实现的操作，接下来就来分析每个函数的作用：

//定义循环队列的结构
typedef struct
{} MyCircularQueue;//循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k)
{}//向循环队列插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{}//从循环队列中删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{}//取队头的数据
int myCircularQueueFront(MyCircularQueue* obj)
{}//取队尾的数据
int myCircularQueueRear(MyCircularQueue* obj) {}//判断循环队列中的数据是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{}//判断循环队列中的数据是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj)
{}//销毁循环队列中数据
void myCircularQueueFree(MyCircularQueue* obj)
{}

1.4.2 代码的实现

1.定义循环队列的结构
既然以数组的结构实现循环队列，那么结构体的成员变量中一定得要有数组；并且还得定义两个变量front与rear来指向队头与队尾的位置。
通过之前的分析判断队列中的数据是否为空，还是满了需要用到队列的长度k，并且之后k会在函数myCircularQueueCreate中以参数的形式来作为队列结构的初始化部分，为了将队列的长度k保存起来，在这里定义一个结构体成员变量。
分析完毕后，就可以编写代码了：

//定义循环队列的结构
typedef struct
{int* arr; int front; //表示队头int rear; //表示队尾int capacity;//记录循环队列的长度
} MyCircularQueue;

2.初始化循环队列

//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k)
{//定义一个指针，指向循环队列//为循环队列开辟MyCircularQueue大小的内存空间MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//将循环队列里的成员初始化//初始化数组 --- 为数组申请k + 1个int*大小的内存空间pq->arr = (int*)malloc(sizeof(int*) * (k + 1));//初始化指向队头和队尾的变量 --- 事先指向下标为0的位置pq->front = pq->rear = 0;//初始化capacity --- 将k直接赋值给capacitypq->capacity = k;//观察函数的返回值为MyCircularQueue*//说明要将循环队列的地址返回，直接将定义好的pq给返回return pq;
}

3.判断循环队列中的数据是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{//怎么判断队列中的数据是否为空？//当指向队头的变量front等于指向队尾的变量rear时，即可说明队列中的数据为空return obj->front == obj->rear;
}

4.判断循环队列中的数据是否为满

bool myCircularQueueIsFull(MyCircularQueue* obj)
{//怎么判断队列中的数据是否满了？//当(rear + 1） % (k + 1)等于front时，即可说明队列中的数据满了return (obj->rear + 1) % (obj->capacity + 1) == (obj->front);
}

5.向循环队列中插入数据

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{//判断队列的空间是否满了 --- 调用函数myCircularQueueIsFullif (myCircularQueueIsFull(obj)){//若队列中的数据满了，就不能再插入数据了，直接返回falsereturn false;}//代码运行到这，即可说明队列中的数据还没有满//往rear指向的位置插入数据obj->arr[obj->rear++] = value;//rear++后，需要阻止rear越界，构成循环结构obj->rear %= obj->capacity + 1;//插入成功，返回truereturn true;
}

插入数据后，rear会++，这个时候为什么rear可能会越界呢？接下来画图分析：

6.删除循环队列中的数据

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{//要删除数据总得有数据可删吧？即队列中的数据不能为空//判断队列中的数据是否为空 --- 调用函数myCircularQueueIsFullif (myCircularQueueIsEmpty(obj)){//若队列中的数据为空，则返回falsereturn false;}//代码运行到这，即可说明队列中的数据不为空//删除数据直接将front++即可obj->front++;//那么就要分析front直接++，可不可能越界呢？//可能会越界，所以需要向rear那样来组织front越界，构成循环结构obj->front %= obj->capacity + 1;//删除成功，返回truereturn true;
}

删除数据后，front会++，这个时候为什么front可能会越界呢？接下来画图分析：

7.取循环队列队头的数据

int myCircularQueueFront(MyCircularQueue* obj)
{//要获取到数据，首先队列中的数据不能为空//所以要先判断队列是否为空 --- 调用函数myCircularQueueIsEmptyif (myCircularQueueIsEmpty(obj)){//若队列中的数据为空，则返回-1return -1;}//代码运行到这，说明队列中的数据不为空//直接将下标为front的数据给返回return obj->arr[obj->front];
}

8.取循环队列队尾的数据

int myCircularQueueRear(MyCircularQueue* obj)
{//要获取到数据，首先队列中的数据不能为空//所以要先判断队列是否为空 --- 调用函数myCircularQueueIsEmptyif (myCircularQueueIsEmpty(obj)){//若队列中的数据为空，则返回-1return -1;}//定义一个变量保存rear前的下标int prev = obj->rear - 1;//若rear指向的下标为0，这就意味着rear-1后，prev会越界,所以需要特殊处理if (obj->rear == 0){prev = obj->capacity + 1;}//此时prev指向的位置就为队尾的数据，直接将下标为prev的数据返回return obj->arr[prev];
}

为什么需要定义一个变量prev来保存rear前的下标呢？且还得要对prev特殊处理？接下来画图分析：

9.销毁循环队列中的数据

void myCircularQueueFree(MyCircularQueue* obj)
{//将为数组开辟的内存空间给free掉if (obj->arr){free(obj->arr);}//将为循环队列开辟的内存空间给free掉，并且手动置空free(obj);obj = NULL;
}

10.分析代码运行后的结果

题目给了我们这样的一个输入实例，那这些代表着什么呢？

第一行是调用的函数，第二行是函数调用的参数。再次说明，循环队列中插入数据是从队头插入的，删除数据是从队尾删除的。
MyCircularQueue表示初始化，而初始化的参数为多少？第二行中已经给明了，是3，说明队列的长度为3；
接下来调用函数enQueue，往队列中插入数据，首先判断队列中的数据是否满了，在一开始队列中的没有数据，所以可以插入数据，插入数据成功后返回true，且插入的数据为1；
接下来继续调用函数enQueue，此时的队列中只有一个数据，还可以再插入两个数据，插入成功后，再次返回true；
接下来继续调用函数enQueue，此时队列中只有一个数据，还可以再插入最后一个数据，插入成功后，返回true；
接下来继续调用函数enQueue，判断队列中的数据是否满了，由于之前的三次插入数据，队列中的数据已经满了，所以插入数据失败，返回false；
接下来调用函数Rear，取队尾数据，但是并不删除这个数据，此时队尾的数据为3（这个是之前插入的），取出来后，返回该值，故返回了3；
接下来调用函数isFull，判断队列中的数据是否满了，此时队列中的数据已经满了，所以返回true；
接下来调用函数deQueue，删除队头的数据，判断队列中的数据是否为空，不为空，此时队头的数据为1，删除成功后，返回true；
接下调用函数enQueue，往队列中插入数据，首先判断队列中的数据是否满了，由于之前调用了函数deQueue，将1删除了，所以此时的队列中的数据并不是满的，所以可以插入数据，插入的数据为4，插入成功返回true；
接下来调用函数rear，取队尾的数据，判断队列是否为空，发现并不为空，可以取队尾的数据，此时队尾的数据为4，取出来后，返回该值，故返回4.

2. 随机链表的复制

2.1 题目分析

题目链接: link
题目提供了函数

struct Node* copyRandomList(struct Node* head) {
}

那么我们要对这个函数做些什么呢？接下来观察题目：
题目中所给的链表的结点的结构中有三个成员变量：val，next，random；分别是所存储的数据，指向下一个结点的指针；指向随机的结点。题目中的深拷贝又是什么意思呢？既然有深拷贝，是不是还有浅拷贝呀？对的，确实有：

浅拷贝：直接按位复制内存内容，包括指针的值（地址），而不复制指针指向的实际数据
深拷贝：不仅复制对象本身，还复制所有指针成员指向的实际数据

题目要求构造这个链表的深拷贝，并且拷贝的新结点中的val值，next指针的指向，random指针的指向都与原链表的一致；复制链表中的指针都不应指向原链表中的结点 是什么意思呢？
拿题目所给的数据来分析，复制链表中的指针都不应指向原链表中的结点的意思是，复制的结点的random指针或next指针不能指向原链表的结点：

上图的新链表中的其中一个结点的random指针就指向了原链表的结点，这样是不行的。

2.2 解决问题的思路

既然要拷贝新的结点，可以定义两个指针phead与pcur，这两个指针都指向原链表，其中phead指向原链表的头结点，pcur从原链表的头结点开始，往后遍历原链表，只要pcur指向的结点不为空，就复制该结点，直到pcur指向NULL。
再定义两个指针copyhead与copytail，这两个指针都指向新链表，其中copyhead指向新链表的头结点，copytail指向新链表的尾结点，在一开始只有一个结点的时候，这两个指针指向的是同一个结点，当结点增加时，copytail指针要向后移动，指向新的尾结点：

但是到现在仍然还是不知道怎么取出处理新链表结点的random指针的指向，那怎么设置random指向的指向呢？接下来来画图分析：新结点已经复制成功

既然上面的方法太麻烦，那有没有什么简单的方法，不用多次重复遍历就能找到每个结点的random指针指向的结点呢？
我们将一切都推倒从来，下面我来给出具体的方法：

1. 在原链表的基础上拷贝结点

定义一个指针pcur指向原链表的头结点，从原链表的头结点开始遍历，只要遍历到的结点不是NULL，就向操作系统申请结点大小的空间，该空间中的值都和pcur指向的结点中的值一模一样，并将其插入原链表中，我们将新插入的这个结点取名为newnode，定义一个指针next指向pcur指针指向的结点的下一个结点。
接下来开始链接pcur与newnode，让pcur的next指针指向newnode，让newnode的next指针指向next，最后将next赋值给pcur，让pucr继续往后遍历。最后就反复执行上面的操作，直到pcur指向NULL。

2. 设置复制结点的random指针的指向

观察原链表的random指针的指向，val值为7的结点的random指针指向的是NULL，所以复制结点的val值为7的random指针指向的也是NULL。
定义两个指针pcur与copy，pcur遍历原链表，copy遍历复制的结点。如下图所示：

接下来pcur指针指向的结点的random指针指向的是val值为7的结点；
那么copy指针指向的结点的random指针指向的也是val值为7的结点，这个结点不能是原链表的结点，而是复制的结点，那么怎么找到这个val值为7的复制的结点呢？
观察上图，该结点的地址就是pcur->random->next。那么也就是说，copy->random = pcur->random->next.

接下来pcur继续向下遍历原链表pcur = copy->next，copy也继续向下遍历复制的结点copy = pucr->next。如下图所示：

现在pcur指针指向的结点的random指针指向的是val值为1的结点；
那么copy指针指向的结点的random指针指向的也是val值为1的结点，这个结点不能是原链表的结点，而是复制的结点，那么怎么找到这个val值为7的复制的结点呢？
观察上图，该结点的地址就是pcur->random->next。那么也就是说，copy->random = pcur->random->next。

通过上面的分析，我们可以知道如何去处理复制结点的random指针，因为copy->random = pcur->random->next。这也就是为什么要在原链表的基础上去插入复制的结点。复制结点的random设置的总结果如下图所示：

3. 断开新链表与原链表

既然要返回的是新链表的头结点的地址，那么得要将新链表与原链表的结点之间的联系断开，也就是将新链表中的结点的next指针不再指向原链表的结点，而是新链表的结点；而原链表中的结点的next指针不再指向新链表的结点，而是原链表的结点。
要断开它们二者的联系，需要定义两个指针pcur和prev，pcur去遍历原链表，prev负责恢复原链表的next指针的指向；
并且要定义两个指针copyhead与copytail，分别指向新链表的头结点和尾结点，且让copytail去遍历新链表。
copyhead与copytail等于pcur->next，只要copytail指针指向的结点的下一个结点不为空，就让pcur指向该结点，再将prev->next = pcur，prev = pcur；然后再将copytail指向的结点的next指针不再指向原链表，而是指向copytail指向的结点的下一个结点，也就是pcur->next。
然后反复执行上述操作，直到copytail指针指向的结点的next指针指向NULL。
断开新链表与原链表的结果如下图所示：

2.3 编写代码

题目与思路都分析完毕后，接下来开始编写代码:

typedef struct Node Node;//为新的结点开辟内存空间
Node* BuyNode(int x)
{//为新结点申请结点大小的内存空间Node* newnode = (Node*)malloc(sizeof(Node));//初始化新结点newnode->val = x;newnode->next = newnode->random = NULL;//返回新结点return newnode;
}//增加新的结点
//将原链表的头结点的地址作为参数，因为需要拷贝原链表中的结点
void AddNode(Node* head)
{//定义一个指针pcur去遍历原链表Node* pcur = head;//循环遍历原链表，只要pcur为空，就停止循环while (pcur){//复制结点，为新的结点开辟内存空间//新结点中保存的val值与pcur的val一样Node* newnode = BuyNode(pcur->val);//将newnode插入原链表中//定义一个指针next保存pcur的下一个结点的地址Node* next = pcur->next;pcur->next = newnode;newnode->next = next;//pcur继续往下去遍历pcur = next;}
}//设置拷贝结点的random指针的指向
//将原链表的头结点的地址作为参数，因为拷贝的结点在原链表中
void SetRandom(Node* head)
{//定义一个指针pucr指向原链表的头结点Node* pcur = head;//让pcur遍历原链表，去设置拷贝结点的random指针的指向//循环执行，直到pcur指向NULLwhile (pcur){//定义一个指针copy指向拷贝结点的第一个结点,即pcur的下一个结点//copy指针指向的始终是pucr的下一个结点Node* copy = pcur->next;//设置拷贝结点的random指针的指向//只要pcur的random指针指向的不是NULL//就执行copy->random = pcur->random->nextif (pcur->random){copy->random = pcur->random->next;}//设置完random指针后，pcur需要继续往下遍历pcur = copy->next;}	
}struct Node* copyRandomList(struct Node* head)
{//链表不能为空if (head == NULL){return head;}//在原链表的基础上拷贝结点，并将新结点插入原链表中//调用函数AddNodeAddNode(head);//设置拷贝结点的random指针的指向//调用函数SetRandomSetRandom(head);//将新链表从原链表中断开//定义指针pcur去遍历原链表Node* pcur = head;//定义指针prev开始是指向原链表的头结点//为了恢复原链表的next指针的指向Node* prev = head;//定义两个指针copyhead与copytail，开始都指向复制结点的第一个结点//copyhead始终指向新链表的头结点//copytail去遍历新链表，去处理新链表中结点的next指针的指向Node* copyhead = pcur->next;Node* copytail = pcur->next;while (copytail->next){//让pcur指针指向copytail的下一个结点//使得pcur继续向下遍历原链表pcur = copytail->next;//恢复原链表next指针的指向prev->next = pcur;prev = pcur;//处理新链表中next指针的指向copytail->next = pcur->next;//copytail继续往下遍历新链表copytail = copytail->next;}//将新链表的头结点返回return copyhead;
}

接下来来分析题目所给的测试用例：

看输入：有两层中括号，里面的中括号括起来的是结点的val值与random指针的指向，
如 [7，null] 意思就是该结点的val值为7，且其random指针指向的是null；
那么 [13，0] 中的0又是什么意思呢？这指的是下标为0的结点，结点的下标是从零开始的，而下标为0的结点就是 [7，null] ，所以 [13，0] 的意思是该结点的val值为13，random指针的指向是下标为0的结点，即val值为7，random指向null的结点。
其它数据也是如此分析。