复盘理解/实验报告梳理 数据结构PTA实验一

新系列！！！

由于要写数据结构实验，所以我需要重新梳理一下我前面写过的实验题，顺便写一个综合性较强的博文，针对实验报告中的“调试过程”内容进行复盘，方便复习。

一、约瑟夫环

????????此题内容是对于循环链表的创建，以及遍历，从链表中删除结点，然后再注意剩下最后一个结点的问题即可。

????????首先先简单做一个链表，然后将最后一个结点的next指向头结点，这样就创建好了头节点为空循环链表。

????????进入打印环节，将给的p传入打印函数，循环判断空头节点的next是否为空，将每次循环p次循环到的元素输出，并删除这个结点（将其前面那个结点的next置为该结点的下一个元素），第一次写这里的时候，输出到最后会一直输出最后一个元素，原因是循环检测的是head的next是否为空，然而，该链表里到最后也会剩下最后一个元素，因为这个结点的next->next和该节点的next和它本身是相同一个结点，所以会一直打印这个结点，之后，我们在下面做一个if，会检测是不是只剩下这个结点了，如果if成立，就直接输出break即可（没有人会为你一直停留在原地的）。

二、重排链表

????????首先分析了一下输入内容，可以采取数组依次储存的方法，或者取数组下标作为地址，两者我都尝试了一下，发现前者会在最大输出的时候超时，所以需要采用后者，数组下标作为该元素地址，然后结构体存下一个地址和val。

????????由于题目要求，可以考虑将这个问题分为两部分，即存入链表，和重排链表。

????????存入链表先根据上面的内容，存到线性表里，然后进入到创建双向链表的函数，设置双向是因为方便重排，进行一下读取存入，具体的操作就是进行循环，从输入的起始地址开始，直到找到下一个地址为-1的，break循环。每次元素的下一个地址和val通过尾插法进入链表。这样，就可以构成一个很棒的存有输入内容的链表。

????????下一步就是重排链表。这里我们用两个指针，一个指针指向头节点，一个指向最尾的结点，之后根据题意，头一个尾一个进行重构，这里我新创建了一个链表，来接收构建的内容，在原链表上直接改觉得太麻烦。这里要注意的就是当两个指针碰到一块要怎么处理。这里我考虑了一下，发现结点当为偶数时，就不会正好碰上，而是擦肩而过，而奇数就能正好碰上（希望大家的爱情也会像奇数的情形一样）。这里可以做个结点数判断，但是我选择的是：发现重排后，奇数位是后往前读，偶数位是前往后读，所以在构建链表中设置if，检测这个点位是奇数还是偶数，奇数就读取尾的指针指向的内容，然后尾指针前移一下，偶数同理。这样就组装好了重排的链表。

????????然后就是执行打印，这里就将重排好的链表扔进打印的函数，一个一个按照输出格式要求打印即可。打印时候会发现，由于起初要进入数组，我们输入的时候地址按照int型输入的，打印也势必输出int型，即缺少前面补位的0，我们这里只需要在写一个函数，例如当999=>address>=100，就要补充两个0，进行if，补充即可。完成这一步，大功告成。

?

希望不要白嫖↓↓↓