[其他] [已解决]批处理可以建立链表吗？

dengyuli

链表的优势是：插入、删除元素比较方便
下面给出我做的单向链表：

@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

应用：解决约瑟夫问题
题目：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

算法貌似有点不对哦
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

此方法效率低下的原因是随机分配变量名
我自己笔算了一下，没有错误
这个问题可以精简到一个公式，效率可以更高

terse

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
复制代码