拓扑排序中为什么需要使用栈?可不可以使用其他的数据结构,为什么

1个回答

小铭学姐

专业答主服务有保障

关注

展开全部

摘要在以往学习高级语言时，提到栈，下意识都会反映上来FILO，它是暂存数据的一种数据结构，但是为什么会用到栈？却一直讳莫如深，这是高级语言不会涉及到的底层的实现，最近在学习王爽老师的《汇编语言》，其中有一段点醒了我，现整理如下。

（一）这个问题的由来是对如下datasg段中每个单词改写为大写字母。

assume cs:codesg,ds:datasg

datasg segment

\x09db 'ibm '

\x09db 'dec '

\x09db 'dos '

\x09db 'vax '

datasg ends

codesg segment

start:\x09

codesg ends

end start

（二）分析：需要进行4x3次的二重循环，使用bx来定位要修改的行，用si定位要修改的列，用[bx+si]的寻址方式对目标单元进行寻址，实现如下

咨询记录 · 回答于2021-11-09

拓扑排序中为什么需要使用栈?可不可以使用其他的数据结构,为什么

您好，您的问题我已经看到了，正在整理答案，请稍等一会，我们是一个一个回答，请耐心等待，打字需要一点时间，很高兴能为您服务

[吃鲸]

在以往学习高级语言时，提到栈，下意识都会反映上来FILO，它是暂存数据的一种数据结构，但是为什么会用到栈？却一直讳莫如深，这是高级语言不会涉及到的底层的实现，最近在学习王爽老师的《汇编语言》，其中有一段点醒了我，现整理如下。（一）这个问题的由来是对如下datasg段中每个单词改写为大写字母。assume cs:codesg,ds:datasg datasg segment\x09db 'ibm '\x09db 'dec '\x09db 'dos '\x09db 'vax 'datasg ends codesg segmentstart:\x09 codesg endsend start（二）分析：需要进行4x3次的二重循环，使用bx来定位要修改的行，用si定位要修改的列，用[bx+si]的寻址方式对目标单元进行寻址，实现如下

assume cs:codesg,ds:datasg datasg segment\x09db 'ibm '\x09db 'dec '\x09db 'dos '\x09db 'vax 'datasg ends codesg segmentstart:\x09mov ax,datasg\x09\x09mov ds,ax\x09\x09mov bx,0\x09\x09\x09\x09mov cx,4\x09s0:\x09mov si,0\x09\x09mov cx,3\x09\x09\x09s:\x09mov al,[bx+si]\x09\x09and al,11011111b\x09\x09mov [bx+si],al\x09\x09inc si\x09\x09loop s\x09\x09\x09\x09add bx,16\x09\x09loop s0\x09\x09\x09\x09mov ax,4c00h\x09\x09int 21h codesg endsend start这种实现方式有个问题，由于2层循环使用同一个计数器cx，内层循环在运行过程中修改了外层循环的计数器，导致这个程序会无限循环下去，破坏其他内存地址的数据。

我在datasg段后面接着添加一个测试段，作一个测试datasg segment\x09db 'ibm '\x09db 'dec '\x09db 'dos '\x09db 'vax 'datasg ends ceshi segment\x09db 'abc '\x09db 'def '\x09db 'ghi 'ceshi endsdebug调试，程序运

debug调试，程序运行前各寄存器的状态和程序的反汇编状态：

内存状态

程序循环4次之后，内存状态：

此时，程序退出内循环，再次进入外循环s0处，cx被重新赋值为3：

由此继续下一次内循环，将继续修改不应被修改的数据，进入无限循环……程序失控。

（三）为解决这个问题，选择在每次内循环开始之前，将外层循环的cx值保存起来，在进行外循环时再进行恢复：codesg segmentstart:\x09mov ax,datasg\x09\x09mov ds,ax\x09\x09mov bx,0\x09\x09\x09\x09mov cx,4\x09s0:\x09mov dx,cx #将外循环的cx值暂存\x09\x09mov si,0\x09\x09mov cx,3\x09\x09\x09s:\x09mov al,[bx+si]\x09\x09and al,11011111b\x09\x09mov [bx+si],al\x09\x09inc si\x09\x09loop s\x09\x09\x09\x09add bx,16 move cx,dx #恢复cx的值\x09\x09loop s0\x09\x09\x09\x09mov ax,4c00h\x09\x09int 21h codesg endsend start这样使用寄存器来对数据进行临时存储，在这样的小程序中固然可行，但若程序稍大些、复杂些，剩余的寄存器也不够我们使用的，所以引出使用内存空间来对数据进行暂存。datasg segment\x09db 'ibm '\x09db 'dec '\x09db 'dos '\x09db 'vax '\x09dw 0 #开辟一个内存空间，暂存数据datasg ends但是这种方式会造成程序猿的极大困扰，要记得每个临时性数据在什么地方存储不是容易的事情，也不便于维护，这样很不方便使用。最后引出栈的使用，开辟一个内存空间用做栈段，通过push和pop操作便捷地对临时性数据进行暂存，解放了程序猿要记忆和寻找数据内存地址的痛苦过程。stacksg segment\x09dw 0,0,0,0,0,0,0,0stacksg ends安全又便捷。

所以，为什么要使用栈这样的数据结构呢？1.cpu内部寄存器数量有限。2.解放程序猿。

希望我们的回答能帮助到您，祝您生活愉快！好人一生平安！谢谢麻烦记得点个赞！

已赞过

评论收起