标题: [其他] [已解决]批处理可以建立链表吗? [打印本页]
作者: dengyuli 时间: 2015-5-22 17:30 标题: [已解决]批处理可以建立链表吗?
本帖最后由 dengyuli 于 2015-5-26 18:01 编辑
链表的优势是:插入、删除元素比较方便
下面给出我做的单向链表:- @echo off
- setlocal enabledelayedexpansion
- :head
- cls
- set /p n=请输入元素个数:
- set /a n-=1
- if !n! leq 0 goto :head
- rem 头结点名称
- set "h=!random!!time::=!"
- rem ----------
- set /p %h%.data=
- set "str=!random!!time::=!"
- set %h%.next=!str!
- if !n!==0 set %h%.next=nil
- for /l %%a in (1,1,!n!) do (
- for %%b in (!str!) do (
- set /p %%b.data=
- if %%a neq !n! (set "%%b.next=!random!!time::=!") else (set %%b.next=nil)
- set str=!%%b.next!
- )
- )
- echo head id^:!h!
- echo !%h%.data!
- echo next^:!%h%.next!
- echo=
- if !%h%.next!==nil goto :f
- set str=!%h%.next!
- :x
- rem 按顺序显示出链表中的各个元素
- for %%b in (!str!) do (
- echo id^:%%b
- echo !%%b.data!
- echo next^:!%%b.next!
- echo=
- set str=!%%b.next!
- if "!str!"=="nil" goto :f
- )
- goto :x
- :f
- endlocal
- pause
复制代码
不知道这算不算是模拟链表。
作者: dengyuli 时间: 2015-5-24 11:42
本帖最后由 dengyuli 于 2015-5-24 11:46 编辑
应用:解决约瑟夫问题
题目:N个猴子围成一圈,从第一个开始报数,第M个将被淘汰,最后剩下一个,其余猴子都将被淘汰。例如N=6,M=5,被淘汰掉的顺序是:5,4,6,2,3,1。剩下最后一个可以当选猴群的大王。
代码如下:- @echo off
- setlocal enabledelayedexpansion
- set /p n=请输入猴子数量:
- set /p m=请输入报道几就退出的数:
- set /a m-=1
- set "h=!random!!time::=!"
- set str=!h!
- for /l %%a in (1,1,!n!) do (
- for %%b in (!str!) do (
- set %%b.data=%%a
- set "%%b.next=!random!!time::=!"
- if %%a==!n! set %%b.next=!h!
- set str=!%%b.next!
- )
- )
- set ctr=1
- :bs
- set /a "mod=ctr %% m"
- if !mod! neq 0 (
- for %%a in (!str!) do (
- set str=!%%a.next!
- )
- ) else (
- for %%a in (!str!) do (set t=!%%a.next!)
- for %%a in (!t!) do (
- set t=!%%a.next!
- echo !%%a.data!号已淘汰。
- set "%%a.data="
- set "%%a.next="
- )
- for %%a in (!str!) do (
- set %%a.next=!t!
- set str=!t!
- )
- set ctr=0
- )
- set /a ctr+=1
- for %%a in (!str!) do (if !%%a.next!==%%a goto :f)
- goto :bs
- :f
- for %%a in (!str!) do (
- echo 最终当选大王的是:!%%a.data!号
- )
- endlocal
- pause
复制代码
当猴子数量越多时,处理得就越慢,处理到后面就会越来越快。
作者: bailong360 时间: 2015-5-24 12:24
算法貌似有点不对哦
20,3
正确输出应该为16,而你输出了20
这是批处理贴吧群里的凡心写过的一段代码,很简洁- @echo off& setlocal enabledelayedexpansion
- set number=20
- for /l %%i in (1,1,%number%) do set __tmp1=!__tmp1! %%i
- :st
- set a=
- set __tmp=%__tmp1%
- set __tmp1=
- set count=
- for %%i in (%__tmp%) do (
- set /a a+=1
- set /a "1/(!a! %% 3)" 2>nul && (set /a count+=1&set __tmp1=%%i !__tmp1!)
- )
- if !count! == 2 (goto end) else (goto st)
- :end
- for %%i in (%__tmp1%) do set win=%%i&goto win
- :win
- echo %win%
- pause
复制代码
不同的语言有自己不同的特性,刻意去模仿别的语言反倒会导致代码冗长且效率低下
(比如我初学C的时候思考过该怎么实现变量嵌套......)
作者: dengyuli 时间: 2015-5-24 13:46
此方法效率低下的原因是随机分配变量名
我自己笔算了一下,没有错误
这个问题可以精简到一个公式,效率可以更高
作者: terse 时间: 2015-5-24 14:35
n = 总数
q = 步进
z = 起始位置- @echo off&setlocal enabledelayedexpansion
- set/a n=20,q=3,z=1,x=z-1
- for /l %%i in (%z% 1 !n!) do set "code=!code!,%%i"
- for /l %%i in (1 1 !x!) do set "code=!code!,%%i"
- set "code=!code!,"
- :lp
- for %%i in (!code!) do (
- set /a "m+=1,r=m %% q"
- if !r! equ 0 (
- set /a num+=1
- if !n! equ !num! goto end
- set "code=!code:,%%i,=,!"
- )
- )
- goto :lp
- :end
- set "s=!code:,=!"
- echo;!s!
- pause
复制代码
起始位置 1- @echo off&setlocal enabledelayedexpansion
- set/a n=20,s=1,q=3
- if %n% equ %s% set p=1
- :lp
- for /l %%i in (!s! 1 !n!) do (
- if not defined %%i (
- set/a m+=1,t=m%%q
- if !t! equ 0 (set %%i=%%i)else set/a str=%%i,p+=1,n=%%i,s=1
- if defined %%i echo,!%%i!
- )
- )
- if !p! gtr 1 set p=&goto lp
- echo 最后剩下的是原来的 !str! 号
- pause
复制代码
欢迎光临 批处理之家 (http://www.bathome.net/) |
Powered by Discuz! 7.2 |