系统软件设计.doc

系统软件设计（全面版）资料
第四章 系统软件设计
4.1 通信协议
通信协议是指在计算机之间进行数据传输时的一些约定，包括通信方式、波特率、命令码的约定等。为保证计算机之间能准确、可靠地通信，相互之间必须遵循统一的通信协议。在通信之前一定要先设置好通信协议。本系统串行通信采用异步通信方式。协议如下：
1、一帧数据由 1 位起始位、8 位数据位、无奇偶校验位、1 位停止位共 10 位组成。
2、波特率设为 9600bps。单片机串行口按方式1工作，波特率由定时器 T1 控制，PC机串口波特率通过VB通讯控件的Settings属性设置，为保证数据传送的准确性，两者的波特率必须一致。
4.2 PC机高级语言部分
在PC机高级语言编程中，本设计采用了VISUAL BASIC 高级语言。VISUAL BASIC（VB）是MICROSOFT 公司推出的面向对象编程的高级语言，它以编程简单、ActiveX控件丰富、可移植性好、功能强大而受到广大编程人员的欢迎。因此本系统高级语言编程采用了VB。
1、控制界面的完成
使用高级语言编程可以在PC机上编制非常友好、直观的人机控制界面。把原来的人体直接控制变成了鼠标、键盘的间接控制；并且通过直观的控制界面可以很容易的实现控制，对现场的控制情况一目了然，增加了操作人员的视觉感、安全感，简化了操作。
控制界面包括：现场数据显示、予置数据输入、现场数据上下限数值、报警提示、数据记录、时间和日期、数据打印、本程序使用密码等。
2、 PC机对外通信
这个部分是本系统的重要部分， PC机的数据都可以设置，但要把PC机的数据送到串行端口上以及怎样才能把串行端口上数据接收进来，是PC机编程中的关键部分。
在VB的大量控件中，有一个MSCOmm控件，是专门用来实现串行端口数据的传输和接收的，为应用程序提供了串行通信功能，是一个标准的十位串口通信。本次设计就使用了该控件。下面就介绍一下该控件的使用方法。
控件属性：
（1）comport
设置并返回通信端口号。语法为：
object port[=value]
value是一个整型值，表明使用的端口号
说明：在设计时，value可以设成从1—16的任何数，在打开端口之前必须设置端号。
（2）settings
设置并返回波特率、奇偶校验、数据位、停止位等参数
语法为： object.settings[=value]
value是一字符串表达式，说明端口的设置值，由四个设置值组成，格式如下：
“BBBB，P，D，S”
其中，BBBB为波特率；P为奇偶校验；D为数据位；S为停止为数。要值得注意的是此处的设置值一定要和单片机系统的串行口波特率设置值一致。
（3）portopen
设置并返回通讯端口的状态；
语法为：object.portopen[=value]
value为一布尔表达式，说明通讯端口的状态；
value=true：端口开；value=false：端口关
要注意的地方是如果在端口打开之前，DTREnable或RtsENable属性设为true;当端口关闭时一定要将这两个属性设置为false.
（4）input
返回并删除接收缓冲区中的数据流
语法为：object.input
说明：inputlen属性确定被input属性读取的字符数。设置inputlen为0,则input属性读取缓冲区中全部的内容。Inputmode属性确定被input读取的数据类型。如果inputmode=cominputmodetext,则input属性通过一个variant返回文本数据；如果设置inputmode=cominputmodebinary,则input属性通过一个variant返回一个二进制数据的数组。
（5）output
往传输缓冲区写数据流
语法为：object.output[=value]
value是一准备写到传输缓冲区的一字符串。
说明：output属性可以传输文本数据或二进制数据
（6）commevent
返回最近的通讯事件或错误。用此属性处理在数据传输过程中的异常事件。
（7）handshaking
设置并返回硬件握手协议
语法为：object.handshaking[=value]
value为一整型值
value=0 没有握手
value=1 (xon/xoff)握手
value=2 (rts/cts)握手
value=3 (xon/xoff和rts/cts两种皆可)握手
说明:handshaking是指内部通讯协议,通过该协议,数据从硬件端口传输到接收缓冲区。握手协议保证在缓冲区过载时数据不丢失。
控件事件：
（8）oncomm
无论何时当commevent属性的值变化时，就产生oncomm事件。它标志发生了一个通讯事件或一个错误。Commevent属性包括实际错误或产生oncomm事件的编码。但是，当rthreshold或sthreshold属性被设置为0时，则会分别使comevreceive和comevsend事件无效。

4.3 单片机汇编语言部分
PC机只与一台单片机通信，由上述的通信协议，对单片机作了如下的设置，从而保证PC机与单片机的正常通信。
MOV TMOD,#20H ;设置定时器T1工作方式 2
MOV TH1,#0FDH ;定时器计数初值，波特率9600bps
MOV TL1,#0FDH ;定时器重装值
MOV SCON,#50H ;设置串口工作方式1,REN = 1 允许接收
MOV PCON,#00H ;波特率不倍增
SETB EA ;允许总的中断
SETB ES ;允许串行中断
流程图如下：

图4.1 主程序流程图 图4.2 中断服务程序

第四章　极限定理
一、 教学目标
概率统计主要研究随机现象的统计规律，而这种统计规律只有对随机现象进行大量重复观测才能显现出来。对大量重复观测作数学处理厂采用极限的方法，这就是对极限定理的研究。在本章教学过程中，重点的数熟练运用两种最基本的极限定理：大数定理和中心极限定理。
二、 基本要求
1. 理解切贝晓夫不等式，会利用切贝晓夫不等式作简单的证明和计算。
2. 了解依概率收敛和独立同分布随机变量序列的概念。
3. 理解切贝晓夫大数定理和贝努利大数定理，会利用大数定理作简单计算。
4. 理解独立同分布中心极限定理和隶莫弗－拉普拉斯中心极限定理，会利用正态分布表作近似计算。
三、 教学重点
1. 大数定理和中心极限定理的内容。
2. 大数定理和中心极限定理的应用。
四、 教学重点
大数定理和中心极限定理的应用。
五、 教学方法和教学手段
启发式教学，讲练结合法，多媒体教学和板书教学相结合。
六、 教学内容及课时安排（4课时）
§4.1大数定律 （2课时）
§4.2中心极限定理 （2课时）
七、参考书

[2] 魏忠舒.概率论与数理统计教程. 北京：高等教育出版社，1997
[3]复旦大学.概率论. 北京：人民教育出版社，1979

§4.1大数定律
一、教学目标与要求
1. 理解切贝晓夫不等式，会利用切贝晓夫不等式作简单的证明和计算。
2. 会利用大数定理作简单计算。
二、教学重点和难点
切贝晓夫不等式和大数定律的应用
三、教学方法与手段
启发式教学，多媒体课件教学与板书教学相结合。
四、教学过程（２学时）
（一） 授课内容
１. 切贝晓夫不等式
定理4.1　设随机变量x的期望及方差都存在，则对有

２. 依概率收敛

定义4.1　设是随机变量序列，是一常数，若对，有

或　　　　　　　　　　　　　
则称依概率收敛于，记作。
３. 独立同分布随机变量序列
定义4.2　设是随机变量序列，若相互独立且同分布，则称是独立同分布随机变量序列。
４. 大数定理
定理4.2（切贝晓夫大数定理）设是相互独立的随机变量序列，期望和方差都存在，且方差有界，即存在使，则对有

推论（辛钦大数定理）设是相互独立的随机变量序列，期望 ，则对有

定理4.3（贝努里大数定理）设是在重贝努里试验中事件发生的次数，是事件在每次试验中发生的概率，则对有

或　　　　　　　　　　　　　
（二） 课堂练习
例１设是随机变量则　　　　　　　　　　。
例２　设事件在每次试验中发生的概率为，试利用切贝晓夫不等式估计在次独立试验中，事件发生的次数在之间的概率？
例３　证明的充要条件是随机变量以概率取常数，即。
例４　设表示在次试验中事件发生的次数，是事件在第次试验中发生的概率，试证对有

（三） 小结
大数定理主要是采用极限方法研究统计规律，重点是熟练掌握切贝晓夫不等式的内容和应用。
（四） 课后练习
课本156页习题四

§4.2中心极限定理
一、教学目标与要求
1.理解独立同分布中心极限定理，和棣莫弗－拉普拉斯定理。
2.会利用中心极限定理作近似计算。
二、教学重点和难点
中心极限定理的内容和应用
三、教学方法与手段
启发式教学，多媒体课件教学与板书教学相结合。
四、教学过程（２学时）
（一）授课内容
１. 独立同分布中心极限定理
定理4.４设是相互独立的随机变量序列，期望 ，则对任意的实数，有

其中是标准正态分布的分布函数。
２. 棣莫弗－拉普拉斯定理
定理4.5　设服从参数为的二项分布，则对任意实数，有

其中是标准正态分布的分布函数。
（二） 课堂练习
例１一射击运动员在一次射击中所得的环数的概率分布如下

10 9 8 7 6

0.05 0.5 0.3 0.1 0.05
问在100次的射击中，所得的总环数介于900环和930环之间的概率是多少？超过950环的概率又是多少？
例２　设某商店每天接待顾客100人，每位顾客的消费额（元）服从上的均匀分布，并且顾客的消费是相互独立的，求商店的日销售额超过3500元的概率？
例３　设每颗子弹击中飞机的概率为0.01，求500发子弹中有5发击中的概率？
例４ 某单位有100个职工，设每个职工中午到食堂用餐的概率为0.5，试问食堂准备了60份饭菜，不能满足供应的概率？
例5 某单位内部有260架 分机，每个分机有4%的时间要与外线通话，且每个分机使用外线是相互独立的，问总机要备有多少条外线才能以95％的把握保证各个分机在用外线时不用等待？
（三）小结
中心极限定理是论证大量随机变量和的极限分布是正态分布的定理，因此，在应用时需要注意定理的内容和正态分布表的应用。
（三） 课后练习
　　课本156页习题四7、10、11、13

第四章   电路定理

基本内容

介绍叠加定理、替代定理、戴维宁定理和诺顿定理、对偶原理及其在线性电路分析中的应用。

重       点

1．叠加定理；
2．戴维宁定理和诺顿定理；
3．特勒根定理。

难       点

1．各电路定理的应用条件；
2．各电路定理对含受控源电路的处理。
 §4-1   叠加定理

1．定理推导

+
-
+

-

。
。

+
-
+

-

+

-

图4.R1.1  叠加定理

对于图所示电路，用网孔方程解，有

可见，由于电阻都是线性的，故支路电流和支路电压都是电流源和电压源的一次函数。
当总能作用，有

当时，单独作用，有

而 

2．定理描述

叠加定理：在线性电路中，由n个独立电源共同作用产生的各支路电流或支路电压，等于各个独立电源分别单独作用时在相应支路中产生的电流或电压的叠加。
所谓独立电源不作用，指独立电压源短路，独立电流源开路，受控源则保留。

注意：
1）叠加定理适用于非线性电路；
2）叠加时，电路的连接以及电路中所有电路和受控源都不要变动。所谓独立电源不作用，是指将电压源用短路替代，电流源用开路替代。
3）叠加时，要注意电流、电压的参考方向；
4）功率不是电流或电压的一次函数，故不能用叠加定理计算功率。

应用叠加定理时，也可以把电路中的所有电源分成几组，按组计算电流和电压后再叠加起来。
由叠加定理可推出：
齐性定理：线性电路中，当所有激励（电压源和电流源）都同时增大或缩小K倍（K为实常数）时，响应（电流和电压）也将同样增大或缩小K倍。当电路中只有一个激励时，响应与激励成正比。
用齐性定理分析梯形电路特别有效。

总结：
1）      当用观察法就能把各独立电源单独作用下所产生的电压或电流求出时，应用叠加定理很方便，如果各电源单独作用时，须由回路法或节点法等才能求出各支路电流和电压，则不如直接对原电路用这些方法求解。
2）      当电路中的各电源不是相同的时间函数时，最好应用叠加定理求解。这样，每次只有一种时间函数的独立电源作用于电路，电路响应也只有这样相应的时间函数。
3）      叠加定理是分析线性电路的基础，应用它，更重要的是可用来证明线性电路的某些重要定理（如戴维宁——诺顿定理）和引出某些重要的分析方法（非正弦）。
§4-2   戴维宁定理和诺顿定理

在第二章中，我们已知道：一个线性有源二端网络，其最简等效电路是一个电压源与电阻的串联组合，或一个电流源与电导的并联组合。利用电源的等效变换，或写端口处的伏安关系，可得到上述等效电路。
并不是所有的有源二端网络，都能用等效变换的方法求出其等效电路，因此，希望找到一种普遍的方法。戴维宁——诺顿定理提供了这种普遍方法，不论怎样复杂的有源线性二端网络，都可用戴维南定理和诺顿定理得到其等效电路。

一、戴维宁定理
1．定理描述
戴维宁定理：一个含独立电源，线性电路和受控源的一端口，对外电路来说，可以用一个电压源和电阻的串联组合来等效变换（如图4.2.1所示），此电压源的电压等于该一端口的开路电压，而电阻等于把该一端口的全部独立电源置零后的输入电阻。
上述电压源和电阻的串联组合称为戴维宁等效电路，等效电路中的电阻有时称为戴维宁等效电阻。

图4.2.1   戴维宁定理

用戴维宁等效电路来替代二端网络后，对外电路没有任何影响，即外电路中的电压和电流仍等于替代前的值。这种等效变换称为对外等效。

2．定理证明

图4.2.2  戴维宁定理的证明过程

设线性有源二端网络与外电路相连，如图4.2.2a所示，端口电压为u，电流为i，应用替代定理，将外电路用电流源替代。如图4.2.2b所示。
根据叠加定理，令，一端口内所有电源共同作用得图4.2.2c，则
，
再令单独作用，一端口内所有电源均不作用，或为无源网络，得图4.2.2d，此时

其中，为无源网络的等效电阻。
依叠加定理，有：

得图4.2.2e。证毕。

可见，戴维南定理确实提供了一种求有源一端口等效电路的普遍适用方法，无论怎样复杂的端口，都可以求出其，，从而代替原网络。

3．定理的应用
应用戴维南定理的关键，在于求出开路电压和戴维南等效电阻。后者用求输入电阻的方法得到。
Req的求法
1）若除源后的一端口网络只含电阻，不含受控源，用电阻的串、并联以及等效变换求得。
2）      分别求出含源一端口网络的开路电压及短路电流，则： 
3）      若除源后一端口网络含有受控源，则用“外加电源法”求得端口处看入的输入电阻，且：。
电路含有受控源时，应注意：
1）      受控源与其控制量必须同在含源一端口网络内，即受控源与其控制量不能分属于端口内、外，但控制量可以是端口处的电压和电流。
2）      含受控源的有源一端口网络，求时要用上述方法2）和3）。在除源时，切不可将受控源像独立电源一样以开路或短路替代，而应将其保留在电路中。

应用场合
由于戴维南定理将有源一端口简化成了二个电路元件组成的等效电路。因此，它主要应用于：
1）      复杂电路中只需计算电路中某一支路的U、I时；
2）      分析某一参数变动的影响(如分析负载如何获得最大功率等)；
3）      一些简单的非线性电路(外电路可以是非线性的)。

求解电路的步骤
1）      把待求支路以外的部分作为有源二端网络，求出其开路电压Uoc作为等效电路中的电压源电压；
2）      求等效电阻 Req ；
3）      用电压源Uoc与等效电阻 Req 串联组成戴维南等效电路代替有源二端网络（注意Uoc 的参考方向），然后计算电路。

二、诺顿定理

1．定理描述
一个含独立电源，线性电路和受控源的一端口，对外电路来说，可以用一个电流源和电导的并联组合来等效变换（如图4.2.3所示），此电流源的电流等于该一端口的短路电流，而电导等于把该一端口的全部独立电源置零后的输入电导。
此电流源和并联电导组合的电路称为诺顿等效电路。

图4.2.3   诺顿定理

用戴维宁等效电路来替代二端网络后，对外电路没有任何影响，即外电路中的电压和电流仍等于替代前的值。
显然，诺顿等效电导与戴维南等效电阻互为倒数，且戴维南等效电路和诺顿等效电路可以互换。

2．说明

1）  应注意等效电路中电压源和电流源的方向。
2）  当一端口内部含受控源时，将它的全部独立电源置零后，它的输入电阻可能等于零。这时，戴维南等效电阻为零，等效电路成为一个电压源。在这种情况下，对应的诺顿等效电路就不存在，因Geq=∞。同理，如果输入电导等于零，诺顿等效电路成为一个电流源。这种情况下，对应的戴维南等效电路就不存在，因Req=∞。通常情况下，两种等效电路同时存在。
3）  当只研究电路的某一部分电压或电流，或研究电路中电压和电流对某一元件变化后灵敏度，或分析电路中某一电阻获得最大功率时，用戴维宁——诺顿定理特别方便。

§4-3   替代定理
1．定理推导

图4.3.1   替代定理

图4.3.1(a)所示电路中，可求得：U=8V，IS=1A，I2=1A，I1=2A。
图4.3.1(b)电路，用US=8V代替4V+4 W支路；可求得：IS=1A，I1=2A，I2=1A。
图4.3.1(c)电路，用IS=1A代替4V+4W支路；仍可求得：I1=2A，I2=1A。

2．定理描述

任意一个线性电路，其中第k条支路的电压已知为uK（电流为iK），那么就可以用一个电压等于uK的理想电压源（电流等于ik的独立电流源）来替代该支路，替代前后电路中各处电压和电流均保持不变。

注意：
1)     适用于线性、非线性电路；定常和时变电路。
2)     被替代的支路可以是电阻、电压源串联电阻、电流源并联电阻。
3)     用独立源代替支路时，不可改变原支路的参考方向。
4)     一般不用于与网络其它支路有耦合关系的支路，如含受控源的支路、支路电压(电流)是其它支路受控源的控制量。
§4-4   对偶原理

1．原理描述

对偶原理：电路中某些元素之间的关系（各方程），用它的对偶元素对应置换后，所得的新关系（新方程）也一定成立。这个新关系（新方程）与原来的关系（方程）互为对偶。
例如，若两个平面电路，其中一个电路的网孔电流方程组（和节点电压方程组），由对偶元素相应的置换后，可以转换成另一个电路的节点电压方程组（网孔电流方程组）。这两个电路便互为对偶，称为对偶电路。

2．原理说明
电阻R元件上，U=Ri或i=GU，CCVS有：=，VCCS有：=。在上述关系式中，若将U和i互换；R与G呼唤，与互换，则对应关系式可彼此转换。因此，R与G，U与i，与分别互为对偶元素。

图4.4.1   对偶原理电路图1

图4.4.1中的两个电路，图a由，和串联组成；图b则由,和并联组成。电路N的网孔电流方程（KVL）为：

电路的节点电压方程(KCL)为:

图4.4.1(a)的等效电路和图4.4.1(b)的等效电导：

在以上关系式中，将R和互换；与互换，串联与并联互换，网孔与节点互换，则上述两组关系式可以互相转换。我们就称上述各组关系式中两个关系式互为对偶。

图4.4.2   对偶原理电路图2

又如图4.4.2所示两个电路N和，N的网孔电流方程（规定所有网孔电流均为顺时针方向）为：

电路的节点电压方程为：

对偶原理的作用：根据对偶原理，如果导出了电路某一个关系式和结论，就等于解决了与它对偶的另一个关系式和结论。例如，含源一端口网络的两种等效电路（，）和（，）互为对偶，只要论证了戴维宁定理的正确性，它的对偶（诺顿定理）自然也成立。
两个电路互为对偶，并不说明两个电路等效，要注意区分“对偶”和“等效”这两个不同的概念。
对偶原理同样也适用于正弦电流电路，例如根据电容和电感的电压电流关系，可知它的互为对偶元素。
对偶原理的应用价值在于，若以知原电路的电路方程及其解答，则根据对偶关系即可直接写出其对偶电路的电路方程及其解答。它不但为电路的分析与计算提供了一种新方法。使电路的计算方法及对公式的记忆工作减少了一半，而且为研究新的电路开辟了新的蹊径。
电路中对偶元素总结如下表：

. 第四章 栈和队列.习 题 四 一、单选题 1.栈的插入与删除操作在 A 进行. A 栈顶 B 栈底 C 任意位置 D 指定位置 2.当利用大小为N的数组顺序存储一个栈时,假定用top==N表示栈空,则向这个栈 插入一个元素时,首先应执行 B 语句修改top指针。 A top++1; B top--; C top=0; D top; 3.若让元素1，2，3依次进栈，则出栈次序不可能出现 C 种情况。 A 3，2，1 B 2，1，3 C 3，1，2 D 1，3，2 4.在一个顺序队列中，队首指针指向队首元素的 A 位置。 A 前一个 B 后一个 C 当前 D 后面 5.当利用大小为N的数组顺序存储一个队列时，该队列的最大长度为 B 。 A N-2 B N-1 C N D N+1 6.从一个顺序队列删除元素时，首先需要 B 。 A 前移一个队首指针 B 后移一位队首指针 C 取出队首指针所指位置上的元素 D 取出队尾指针所指位置上的元素 7.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空指针的条件为 D 。 A f+1==r B r+1==f C f==0 D f==r 8.假定一个链队的队首和队尾指针分别为fron和rear，则判断队空的条件为 D 。 A fron==rear B fron!=NULL C rear!=NULL D fron==NULL 二、填空题 1.队列的插入操作在 队首 进行，删除操作在 队尾 进。 2.栈又称为 后进先出 表，队列又称为 先进先出 表。 3.向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入 到这个位置上。 4.从一个栈删除元素时，首先取出 栈顶元素 ，然后再前移一位 栈顶指针 。 5.在一个顺序队列Q中，判断对空的条件为 Q.front==Q.next ,判断队满的条件为 (Q.rear+1)%QueueMaxSize+1==Q.front 。* 6.在一个顺序栈中，若栈顶指针等于 -1 ，则为空栈；若栈顶指针等于 StackMaxSize-1 ， 则为满栈。 7.在一个链栈中，若栈顶指针等于NULL则为 空栈 ；在一个链队中，若队首指针与队尾指针的 值相同，则表示该队为 空 或该队 只含有一个结点 。 8.向一个链栈插入一个新结点时，首先把栈顶指针的值赋给 新结点的指针域 ，然后把新结点的 存储位置赋给 栈顶指针 。 9.从一个链栈中删除一个结点时，需要把栈顶结点 指针域 的值赋给 栈顶指针 。 10.向一个顺序队列中插入元素时，需要首先移动 队尾指针 ，然后再向所指位置 写入 新 插入的元素。 11.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为 top==0 。 12.向一个栈顶指针为HS的链栈中插入一个新结点*p时，应执行 p->next=HS; 和 HS=p; 操作。 13.从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时， 应执行 HS=HS->nex
t; 操作。 14.假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件 为 (front==rear)&&(front!=NULL)或者(front==rear)&&(rear!=NULL) 。 15.中缀表达式3*(x+2)-5所对应的后缀表达式为 3x2+*5- 。 16.后缀表达式“45*32+-”的值为 15 。 17.在求解迷宫问题的递归算法中，输出每一个位置的坐标是按照从入口到出口的 相反 次顺 进行的。 18.在进行函数调用时，需要把每个实参的值和调用后的 返回地址 传送给被调用的函 数中。 19.当被调用的函数执行结束后，将自动按所保存的 返回地址 执行。 三、普通题 1.假定有四个元素A、B、C、D，按所列次序进栈，试写出所有可能的出栈列，注意，每一 个元素进栈后都允许出栈，如ACDB就是一种出栈序列。 解： ABCD ABDC ACBD ADCB BACD BADC BCAD BCDA BDCA CBAD CDBA DCBA 2.在一个数组空间stack[StackMaxSize]中可以同时存放两个顺序栈，栈底分别在数组的两端 ，当第一个栈的栈顶指针top1等于-1时则栈1为空，当第二个栈的栈顶指针top2等于StackMax Size时栈2为空。两个栈均向中间增长，当向栈1插入元素时，使top1增1得到新的栈顶位置， 当向栈2插入元素时，则使top2减1才能够得到新的栈顶位置。当top1等于top2-1或者top2等 于top1+1时，存储空间用完，无法再向任一栈插入元素。用于双栈操作的顺序存储类型可定 义为： struct Bothstack{ ElemType stack[stackMaxSize]; int top1,top2; }; 双栈操作的抽象数据类型可定义为： DAT BSTACK is Data:采用顺序结构存储的双栈，其存储类型为Bothstack operations: void InitStack(Bothstack& BS,int k); //初始化栈。当k=1或2时对应置栈1或栈2为空，k=3时置两个格均为空 void Clearstack(BothStack& BS,int k) //清除栈。当k=1或2时对应栈1或栈2被清除，k=3时两个栈均被清除 int StackEmpty(BothStack& BS,int k) //判断栈是否为空。当k=1或2时判断对应的栈1或栈是否为空，k=3时 //判断两个栈是否同时为空。若判断结果为空则返回1，否则返回0 ElemType Peek(BothStack& BS,int k) //取栈顶元素。当k=1或2时对应返回栈1或栈2的栈顶元素 void Push(BothStack& Bs,int k,const ElemType& item) //进栈。当k=1或2时对应向栈1或栈2的顶端压入元素item End BSTACK 1.试写出上述抽象数据类型中每一种操作的算法。 解： void InitStack(BothStack& BS,int k) { if(k==1) BS.top1=-1; else if(k==2) BS.top2=StackMaxSize; else if(k==3){ BS.top1=-1; BS.top2=StackMaxSize; } } void ClearStack(BothStack& BS,int k) { //函数体同上 } int StackEmpty(BothStack& BS,int k){ i
f(k==1) return BS.top1==-1; else if(k==2) return BS.top2==StackMaxSize; else if(k==3) return(BS.top1==-1)&&(BS,top2==StackMaxSize); else{ cerr<<"k的值不正确!"'; exit(1); } } ElemType peek(BothStack& BS,int k) { if(k==1){ if(BS.top1==-1){ cerr<<"Stack 1 is empty!"<<end1; exit(1); } return BS,stack(bs,top1); } else if(k==2){ if(BS.top2==StackMaxSize){ cerr<<"Stack 2 is empty!"<<end1; exit(1); } return BS,stack[BS,top2]; } else{ cerr<<"k的值不正确!"; exit(1); } } void push(BothStack& BS,int k,const ElemType& item) { if(BS.top1==BS.top2-1){ cerr<<"Stack overflow!"<<end1; exit(1); } if(k==1){ BS.top1++; Bs.stack[BS.top1]=item; } else if(k==2){ BS.top1--; BS.stack[BS.top2]=item; } } ElemType pop(BothStack& BS,int k] { if(k==1){ if(BS.top==-1){ cerr<<"Stack 1 is empty!"<<end1; exit(1); } BS.top--; return BS,stack[BS.top1+1]; } else if(k==2){ if(BS.top==StackMaxSize){ cerr<<"Stack 2 is empty!"<<end1; exit(1); } BS.top2++; return BS.stack[BS,top2-1]; } else{ cerr<<"k的值不正确!"; exit(1); } } 2.假定上述所有操作的算法已存于头文件"bstack.h"中，试编写一个程序，让计算机随机 产生出100以内的20个正整数并输出，同时把它们中的偶数依次存入到第一个栈中，奇数 依次存入到第二个栈中，接着按照存入每个栈中元素的次序分别输出每个栈中的所有元素 (此操作不改变栈的状态)，然后按照后进先出的原则输出每个栈中的所有元素。 解： #include<iostream.h> #include<stdlib.h> const int StackMaxSize=50; typedef int ElemType; struct BothStack{ ElemType stack[StackMaxSize]; int top1,top2; }; #include"bstack.h" void main() { BothStack a; InitStack(a,3);//初始化两个栈 int i,j,k; //计算机产生20个随机数并输出，同时按奇偶数不同分别放入不同的栈中 for(i=0;i<20;i++){ j=rand()%100; cout<<j<<""; if(j%2==0) push(a,1,j); else push(a,2,j); } cout<<end1; //按照存入栈1中元素的次序输出栈1中的所有元素 cout<<"栈1："; for(i=0;i<=a.top1;i+
+) cout<<a.stack[i]<<""; cout<<end1; //按照存入栈2中元素的次序输出栈2中的所有元素 cout<<"栈2："; for(i=StackMaxSize-1;i>=a.top2;i--) cout<<a.stack[i]<<""; cout<<end1; //按照后进先出的原则输出每个栈中的所有元素 for(k=1;k<=2;k++){ if(k==1) cout<<"栈1："; else cout<<"栈2："; while(!StackEmpty(a,k)) cout<<Pop(a,k)<<""; cout<<end1; } } 该程序输入并运行后将得到如下结果(由于机器系统和C++版本不同，你得到的结果可能 与此不同)： 41 67 34 0 69 24 78 58 62 5 45 81 27 61 91 95 42 27 36 栈1：34 0 24 78 58 62 64 42 36 栈2：41 67 69 5 45 81 27 61 91 95 27 栈1：36 42 64 62 58 78 24 0 34 栈2：27 95 91 61 27 81 45 5 69 67 41 3.设用第二章定义的类型为AlinkList的一维数组MS[MaxSize]建立三个链接堆栈，其中前三个元 素的next域用来存储三个栈顶指针，从下标为3的元素起作为空闲元素提供给三个栈共同使用， 试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同的栈： ⑴若输入的整数x小于60，则进第一个栈； ⑵若输入的整数x大于等于60同时小于100，则进第二个栈； ⑶若输入的整数大于100，则进第三个栈。 解： void MoreStack(ALinkList MS,int n) //把从键盘上输入的n个整数按不同条件分别进入到三个不同的链接栈中 { if(n>MaxSize-3){ cerr<<"存储空间不足!"; exit(1); } int i,x,av; for(i=0;i<3;i++) MS[i].next=0//置空栈，即给三个栈顶指针赋0 av=3;//av指向可利用元素的下标，赋初值为3 cout<<"输入"<<n<<"个整数："<<end1; for(i=0;i<n;