关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
(c语言)浙大数据结构Mooc作者答案集
下面是关于这道题的图片
关于这道题的闲谈
关于这道题第一次我看到的时候，一点点思路都没有，甚至连题意都没会出来，我还以为是中间的数字进行翻转，旁边的地址都是不依次连接的，所以就做了很久，终于把我错误的题意做出来了，还说哇 这都做出来了，一提交，再次看题才发现自己是错的。这道题确实不是很容易理解。
（其实是疯了）
关于这道题的思路
其实如果让我再做这道题 可能难度还是很大的 因为自己思路也没有那么清晰 并且也还借鉴了他人的做法 理解别人的做法都理解了很久 这道题我自己看我自己写的代码 根本不像其他题我一看我就知道我在干什么 但还是就着当复习和温习的作用 我尽力把我写的代码每个步骤在干什么注释一下吧 大家可以手写一下怎么实现的 再结合一下代码应该就能看懂了
下面是我这道题的代码实现
#include <stdio.h>
#include <stdlib.h>//这里就是定义元素为int型
typedef int ElementType;
typedef struct list{
ElementType Data;ElementType Next;
} List;#define max 100000//输出函数
void Print(List Node[],int head);//这里是借鉴了他人的代码 我自己想是没想到的
//这个就是检查有效结点 有些结点并不是有效的 不是输入N就是N 把有效的给剔出来
int Check(List Node[],int Firaddr);//反转函数
int ReverseK(List Node[],int K,int Checknum,int Firaddr);int main()
{
//这里看英文就知道变量是干嘛的int Firaddr,Num,K;int Address,Data,Next;int Checknum,i,head;scanf("%d%d%d",&Firaddr,&Num,&K);//建立一个结构体数组List Node[max];//读入数据for(i=0;i<Num;i++){
scanf("%d%d%d",&Address,&Data,&Next);Node[Address].Data = Data;Node[Address].Next = Next;}//检查有效节点个数Checknum = Check(Node,Firaddr);//这个head就是我们输出的第一个地址 也就是第一次反转的最上面的数head = ReverseK(Node,K,Checknum,Firaddr);Print(Node,head);return 0;
}int Check(List Node[],int Firaddr)//筛查无效结点
{
int Checknum=1;int address = Firaddr;//当最后的地址的下一个Next等于-1时停止//推一下还是挺好推的while((address = Node[address].Next) != -1)Checknum++;return Checknum;
}int ReverseK(List Node[],int K,int Checknum,int Firaddr)//扭转次序
{
int i,j;//变量名字有点多 解释一下attach变量 lasthead firsthead//attach就是负责连接反转后的链表和还没反转的链表//唯一修改值的只有prevaddr和curraddr起作用//nextaddr的目的其实就是先提前准备好位置让curraddr落位int prevaddr,curraddr,nextaddr,head,attach,lasthead,firsthead;curraddr = Firaddr;nextaddr = Node[curraddr].Next;//始终都要将反转链表第一个的prevaddr赋值为-1//结合上面我手写的图片思考一哈prevaddr = -1;head = curraddr;for(i=0;i<Checknum/K;i++){
lasthead = firsthead;firsthead = curraddr;//就比如例子中需要反转数为4 那么先把1的地址记录下来//连接的时候直接连到1的下一个位置值就ok了attach = curraddr;for(j=0;j<K;j++){
//起到修改值的语句Node[curraddr].Next = prevaddr;//这些都是让prevaddr curraddr nextaddr落位的语句prevaddr = curraddr;curraddr = nextaddr;nextaddr = Node[nextaddr].Next;}if(i == 0)//这里就是记录第一次反转的我们需要输出要的首地址//因为反转第一次i还没有+1head = prevaddr;//将处理过的反转链表末尾相连//如果反转数为3 那么这里就是1的下一个地址和6的首地址相连elseNode[lasthead].Next = prevaddr;}//连接反转链表和未反转的链表 如果没有未反转链表//这里将会是赋值 -1 = -1hhhNode[attach].Next = curraddr;return head;
}//输出函数 注意最后那个是-1 而不是补充了0的-1
void Print(List Node[],int head)
{
int i;while((Node[head].Next) != -1){
printf("%05d %d %05d\n",head,Node[head].Data,Node[head].Next);head = Node[head].Next;}printf("%05d %d %d\n",head,Node[head].Data,Node[head].Next);
}
这个就是我整体的思路了 现在发现思路还是蛮清晰的 一点一点理解 理解不了的时候在纸上比划一下 这道题我的注释都打了半个小时 也是希望这个博客有更多后面的同学看到吧 反正当时我去看人家的思路 没怎么加注释我也不怎么看得懂 qwq 关于数据结构的每一道题我做了都是这样解析了 … 所以也是希望能够帮到各位 respect
