关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
(c语言)浙大数据结构Mooc作者答案集
原题谷歌翻译
AC运行结果截图
闲谈
终于这道题做了 今天下午就到了 最后的散列表了
回想起这一个多月的数据结构的学习 也快进入尾声了
我去看看我学了多久了
我是从 2020/11/15 09:50:14开始进入PTA做题
差不多快30多天一点了 可能最多还有1天多也就结束课程了
陈越姥姥确实讲的很好
但是我觉得还是 个人的领悟和理解是最重要的吧
毕竟课程都在那里 但是你学到的 终究是你学到的
不会的 或者 模模糊糊的 也终究不是自己的
就这样叭
视频讲解链接（姥姥思路）
主要还是看一下 陈越姥姥对于这道题的讲解吧
我认为只是看讲解 觉得并没有那么困难
下面先给出视频链接 先看一下陈越姥姥这道题是怎么说的
Sort with Swap(0,i)姥姥之习题选讲
个人思路+代码实现
还是按照姥姥的思路来进行做
但是可以发现 自己实现代码的时候也并非那么容易
因为设计两个数组的套着用的
而且对个别数字的处理要非常注意
所以下面我就直接给出全部代码
然后在代码旁边直接给注释
#include <stdio.h>
#include <stdlib.h>
#include <string.h>int main()
{
//先对变量注释一下// i 就是计数的 N是数字的总量 temp是需要临时用的变量 //position 是用来记录当前在数组走到什么位置的int i,N,temp,number,position;//tempposition是为了给数组的一些地方赋值用的 后面会讲到//totalsteps是记录总交换数的 tempsteps是记录对于一个环交换次数的记录//flag主要是判断这个环中是否含有0int tempposition,totalsteps = 0,tempsteps,flag;//下面我就用的动态分配 主要是想尝试一下 嘻嘻int *Array,*T,*Visit;scanf("%d",&N);Array = (int*)malloc(N * sizeof(int));T = (int*)malloc(N * sizeof(int));Visit = (int*)malloc(N * sizeof(int));//这里就是初始化数组//但是注意 初始化数组如果为0可以这样用 如果是 1 或者其他数//用循环体来初始化 用memeset是赋值不了的memset(Array,0,sizeof(int) * N);memset(T,0,sizeof(int) * N);memset(Visit,0,sizeof(int) * N);//这里是存储数组的 看过视频的应该知道什么意思for(i=0;i<N;i++){
scanf("%d",&number);Array[i] = number;T[number] = i;}//下面就是核心算法了for(i=0;i<N;i++){
//每次先把flag tempsteps初始化flag = 0;tempsteps = 0;//visit是看是否我们访问过 没访问过就进入 访问过就直接跳过if(!Visit[i]){
//记录当前环中数组的数字temp = Array[i];//position是当前数组下标position = i;Visit[i] = 1;while(position != temp){
//如果当前环中含有0 则flag为1 为了后面交换次数的累加if(!position)flag = 1;//这里具体什么意思//就是当我们取出第一个数时//我们也需要对T数组中的那个数下标进行改动//不然闭环时就少一个数//如果还不清楚的话 可以动手画一下交换图//或者测试一下没有这步骤的 T数组中交换完是什么样子的if(!tempsteps)T[Array[position]] = temp;//tempposition主要用来改变T数组下标//当交换赋值完时 我们同时需要改变T数组的下标//但是position已经改变后无法做出这样的操作//就只能记录之前position的位置来这样做tempposition = position;Visit[position] = 1;//更改原先数组的值 对于环数值的改变Array[position] = Array[T[position]];//当前位置的移动position = T[position];//改变已经赋值过了的T数组下标T[tempposition] = tempposition;//每当进入一次循坏 交换次数就+1tempsteps++;}//这里就是对 最后环的末值进行处理了Array[position] = temp;T[position] = temp;totalsteps += tempsteps;//如果当环中没有0的话 需要加的数就是比环中有0的数多2//并且在对于环中只有1个元素时//是不进入while循坏的 所以每次tempsteps都是0if(!flag && tempsteps)totalsteps += 2;}}printf("%d",totalsteps);free(Array);free(T);free(Visit);return 0;
}
结束语
我认为这道题光看代码可能是看不懂的
要结合自己手画一下操作流程 并对一些细节的处理再多思考一下
可能这道题才能实现出来
与大家一起共勉！：）
（小声BB 待会还要去上C语言课 这学期才学到数组 真的是麻了）
（下学期还要再学一学期C才学的完 无奈~）
