软件技术基础实验指导书

1、软件技术基础实验指导书班级姓名实验一 、二叉树遍历的程序编制二叉树是一种典型、应用非常广泛的数据结构。设置本实验可以使学生进一步加强对二叉树遍历算法的理解。一、实验目的：1 理解二叉树在计算机中存储的物理结构。2 掌握二叉树遍历算法。二、实验要求任意输入一棵二叉树，根据二叉树前序、中序和后遍历算法，分别输出遍历结果。三、实验设备1 计算机系统2 安装Turbo C或其他C语言集成开发工具四、实验原理1、前序遍历原理：先访问根，再访问左子树，最后访问右子树，依次递归遍历树的所有节点。2、中序遍历原理：先访问左子树，再访问根，最后访问右子树，依次递归遍历树的所有节点。3、中序遍历原理：先访问右子树

2、，再访问根，最后访问左子树，依次递归遍历树的所有节点。ABCEDEFGH4、例子前序遍历：ABDEGHCF中序遍历：DBGEHACF后序遍历：DGHEBFCA4、编程基本要领1） 前序遍历 void preorder( t ) bitree *t ; if(t)printf(“t%c n”,t-data); preorder( t-lchild ) ;preorder( t-rlchild ) ; 2) 中序遍历 void inorder( t ) bitree *t ; if(t)inorder(t-lchild );printf(“t%c n”,t-data); inorder(t-rch

3、ild ); 2) 后序遍历 void postorder( t ) bitree *t ; if(t)postorder (t-lchild );postorder (t-rchild ); printf(“t%c n”,t-data);五、实验步骤1、 在C语言集成开发工具的编辑器中输入源程序2、 利用编译器编译源程序3、 连接生成执行文件4、 执行程序实验二 、单向链表插入与删除的程序编制单向链表是一种典型、应用非常广泛的数据结构，对其插入与删除算法较为复杂。设置本实验可以使学生进一步加强对单向链表插入与删除算法的理解。一、实验目的：1、理解单向链表在计算机中存储的物理结构。2、掌握单向

4、链表插入与删除算法。二、实验要求任意输入单向链表，根据单向链表插入与删除算法，输出插入与删除后的结果。三、实验设备3 计算机系统4 安装Turbo C或其他C语言集成开发工具四、实验原理xheadqpsX1、 前插原理 pheadr=p-nextp-next=r-nextfree(r)rXX2、 删除原理六、实验步骤1、在C语言集成开发工具的编辑器中输入源程序2、利用编译器编译源程序3、连接生成执行文件4、执行程序实验三 数据库管理系统综合应用-零件交易中心管理系统（例）一、 实验目的： 通过完成从用户需求分析、数据库设计到上机编程、调试和应用等全过程，进一步了解和掌握数据库这一章所讲解的内容

5、。二、实验简述：零件交易管理系统主要提供顾客和供应商之间完成零件交易的功能，其中包括供应商信息、顾客信息以及零件信息。供应商信息包括供应商号、供应商名、地址、电话、简介；顾客信息包括顾客号、顾客名、地址、电话；零件信息包括零件号、零件名、重量、颜色、简介等。此系统可以让供应商增加、删除和修改所提供的零件产品，还可以让顾客增加、删除和修改所需求的零件。交易可以利用顾客提出的需求信息和供应商提出的供应信息来提出交易的建议，由供应商和顾客进行确认后即完成这笔交易。三、实验设备1、安装SQL Server的服务器系统2、安装了SQL Server客户端的计算机系统3、由服务器与客户端的计算机系统所构成

6、的计算机网络三、实验要求： 完成该系统的数据库设计；用SQL实现数据库的设计，并在SQL Server上调试通过。四、实验步骤与参考答案：1、 需求分析11 供应商供应商的操作流程图如图A.1所示。12 顾客顾客的地位和供应商几乎是对称的，所以功能分类上也很相似。顾客的操作流程图如图A.2所示。13 交易员交易员的工作就是提出交易和完成交易。这里需要仔细考虑的问题是：一个交易如何产生，并如何达成，可以用图A.3来说明这个问题。我们在处理交易的时候可能面临如下问题：（1） 一个交易只能在交易双方都同意的情况下才可以进行，所以数据库中的供求信息只能作为达成某个交易的基础；（2） 交易的双方可能不同

7、时使用这个系统，因此需要系统提供一个双方交换信息的方式；（3） 系统需要提供一种方便系统（交易员）向用户提出建议来促成交易的途径，并在保证数据库完整性的情况下达成交易。2、 概念模型设计数据库需要表述的信息有以下几种：（1） 零件信息（2） 供应商信息（3） 顾客信息（4） 供应商和零件之间的联系（供应）（5） 顾客和零件之间的联系（求购）（6） 交易（三元联系）可以用ER模型表述该模型的设计，ER图如图A.4所示。3、 逻辑设计通过ER模型到关系模型的转化，可以得到如下关系模式：（1） Part（ID，Color，Name，Weight，Intro）（2） Provider（ID，Name，

8、Address，Tel，Intro）（3） Customer（ID，Name，Address，Tel）（4） Supply（PartID，ProviderID，Price，Quantity）（5） OfferToBuy（CustomerID，PartID，Price，Quantity）（6） Business（CustometID，ProviderID，PartID，Price，Quantity） 每个关系模式的键码都用下划线标出。同时，对于从联系导出的关系Supply（供应），OfferToBuy（求购）和Business（交易），使用与之联系的实体集的键码作为自己的键码，必须符合外键码约束

9、。对于Customer（顾客），Provider（供应商）和Part（零件）之间，不存在直接的约束，所以可以存在没有供应商供应同时也没有顾客求购的零件。4、 物理设计为了提高在表中搜索元组的速度，在实际实现的时候应该基于键码建立索引。下面是各表中建立索引的表项：（1） Part（ID）（2） Provider（ID）（3） Customer（ID）（4） Supply（PartID，ProviderID）（5） OfferToBuy（CustomerID，PartID）（6） Business（CustometID，ProviderID）5、 用SQL实现设计实现该设计的环境为Windows

10、2000 Professinal + MS SQL Server 7.051 建立Part表create table Part（ID smallint IDENTITY(1,1) PRIMARY KEY CLUSTERED， Color varchar(20), Name varchar(20) NOT NULL, weight int DEFAULT 0, Intro text);52 建立Provider表create table Provider（ID smallint IDENTITY(1,1) PRIMARY KEY CLUSTERED， Name varchar(20) NOT N

11、ULL, password varchar(8) NOT NULL,Address varchar(30), Tel varchar(20), Intro text);53 建立Customer表create table Customer（ID smallint IDENTITY(1,1) PRIMARY KEY CLUSTERED， Name varchar(20) NOT NULL, Address varchar(30), Tel varchar(20);54 建立Supply表create table Supply（ PartID smallint, ProviderID smalli

12、nt, Price int, Quantity int,CONSTRAINT PK_SUPPLY PRIMARY KEY CLUSTERED(PartID,ProviderID)，CONSTRAINT FK_SUPPLY_PARTID FOREIGN KEY(PartID) REFERENCES Part(ID), CONSTRAINT FK_SUPPLY_PROVIDERID FOREIGN KEY(ProviderID) REFERENCES Provider(ID);55 建立OfferToBuy表create table OfferToBuy（ CustomertID smallint

13、, PartID smallint, Price int, Quantity int,CONSTRAINT PK_OFFERTOBUY PRIMARY KEY CLUSTERED(CustomerID,PartID)，CONSTRAINT FK_ OFFERTOBUY_CUSTOMERID FOREIGN KEY(CustomerID) REFERENCES Customer(ID),CONSTRAINT FK_ OFFERTOBUY_PARTID FOREIGN KEY(PartID) REFERENCES Part(ID);56 建立Business表create table Busine

14、ss（ CustomertID smallint, ProviderID smallint, PartID smallint, Price int, Quantity int,CONSTRAINT PK_BUSINESSPRIMARY KEY CLUSTERED(CustomerID,ProviderID, PartID)，CONSTRAINT FK_ BUSINESS _CUSTOMERID FOREIGN KEY(CustomerID) REFERENCES Customer(ID),CONSTRAINT FK_ BUSINESS _PROVIDERID FOREIGN KEY(Provi

15、derID) REFERENCES Provider(ID),CONSTRAINT FK_ BUSINESS _PARTID FOREIGN KEY(PartID) REFERENCES Part(ID);57 供应商操作（1）注册（register） INSERT INTO Provider(Name, Address, Tel,Intro)VALUES(#Name, #Address, #Tel, #Intro)在登记操作后，供应商得到一个唯一的ID，可以根据这个ID来查询和修改供应商的数据。（2）注销（unregister） DELETE Provider WHERE(ID=#ID)（3

16、）修改个人信息（update）UPDATE Provider Set(Name=#Name,Address=#Address,Tel=#Tel,Intro=#Intro) WHERE(ID=#ID)（4）增加供应项（add_supply_item）INSERT INTO Supply(PartID, ProviderID,Price,Quantity) VALUES(#PartID,#ProviderID,#Price,#Quantuty)（5）删除供应项（delete_supply_item）DELETE Supply WHERE(PartID=# PartID AND ProviderID

17、 =#ProviderID)（6）修改供应项（update_supply_item）UPDATE Supply Set(Price=#Price,Quantity=# Quantity) WHERE(PartID=# PartID AND ProviderID =#ProviderID) 很明显，系统并没有提供面向供应商修改零件信息的接口，所以供应商提供的零件必须已知在零件表中存在；可以这样假设，交易所的管理员负责更新零件信息，而供应商可以向交易所申请增加某种零件的信息。事实上顾客也可以提出这样的要求。58 顾客操作（1）注册（register）INSERT INTO Customer(Nam

18、e ,Address, Tel) VALUES(#Name ,#Address,#Tel) 在登记操作后，顾客得到一个唯一的ID，可以根据这个ID来查询和修改顾客的数据。（2）注销（unregister） DELETE Customer WHERE(ID=#ID)（3）修改个人信息（update）UPDATE Customer Set(Name=#Name,Address=#Address,Tel=#Tel)WHERE(ID=#ID)（4）增加需求项（add_OfferToBuy_item）INSERT INTO OfferToBuy (PartID, CustomerID,Price,Qua

19、ntity) VALUES(#PartID,# CustomerID,#Price,#Quantuty)（5）删除需求项（delete_ OfferToBuy _item）DELETE OfferToBuy WHERE(PartID=# PartID AND CustomerID =# CustomerID)（6）修改需求项（update_ OfferToBuy _item）UPDATE OfferToBuy Set(Price=#Price,Quantity=# Quantity) WHERE(PartID=# PartID AND CustomerID =# CustomerID)59 交

20、易员针对需求分析中提出的问题，提出了“协议书”的解决方案，方案的说明如下：（1）每个交易在达成以前都作为协议书保存在数据库中，协议书具有和交易一样的完备信息，可以在条件成熟的情况下转为一个达成的交易；（2）协议书只有在供应商和顾客都签字的情况下才有效；有效的协议书由交易员签发，协议书一经签发，就生效，表明一个交易的达成，数据库中的数据将同时予以修改；（3）协议书可以由供应商、顾客或者交易员中的任意一个提出申请。当协议书在双方没有都签字前，协议的双方或者交易员都可以删除这个协议书；但是，当协议书签字完毕后，协议书就不得删除（修改），只能由交易员进行处理；（4）协议书有可能在转成交易的过程中失败，

21、因为在交易达成以前，数据库中的数据有可能因为其他交易而变化，一个协议书可能失效，这是允许的。根据以上分析，对数据库的模型作一些修改，增加协议书表，其关系模型如下：Agreement(CustomerID,ProviderID,PartID,Price,Quantity,CustomerSign,ProviderSign)对应的SQL描述为：CREATE TABLE Agreement(CustomerID smallint, ProviderID smallint, PartID smallint, Price int, Quantity int, CustomerSign int, Prov

22、iderSign int,CONSTRAINT PK_AGREEMENTPRIMARY KEY CLUSTERED(CustomerID,ProviderID, PartID)，CONSTRAINT FK_ AGREEMENT _CUSTOMERID FOREIGN KEY(CustomerID) REFERENCES Customer(ID),CONSTRAINT FK_ AGREEMENT _PROVIDERID FOREIGN KEY(ProviderID) REFERENCES Provider(ID),CONSTRAINT FK_ AGREEMENT _PARTID FOREIGN

23、KEY(PartID) REFERENCES Part(ID);与上述其他操作相比，交易的操作对数据完整性要求比较高，其中需要注意的地方是：（1）切防止同一用户（供应商、顾客）的数据因两个交易而同时修改；（2）需要同时对供应数据库（Supply）、需求数据库（OfferToBuy）、交易数据库（Business）和协议数据库（Agreement）作出修改，而且需要保持这些修改的原子性；（3）很显然，这些要求正是对于一个事务（transaction）的要求，所以可以用一个事务来完成签发一个协议的操作。事务的描述如下：CREATE PROC PASS_AGREEMENT providerID in

24、t, customerID int, partID intAS DECLARE TransName varchar(20) SELECT TransName=Pass_Agreement BEGINTRANSACTION TransName DECLARE price int, quantity int SELECT price=price, quantity=quantity FROM Agreement WHERE providerID=providerID AND customerID=customerID AND partID=partID INSERT INTO Business(P

25、roviderID, CustomerID, PartID,Price, Quantity) VALUES(providerID, customerID,partID,price,quantity) UPDATE Supply SET quantity=quantity-quantity WHERE ProviderID=providerID AND partID=partID IF(SELECT quantity FROM Supply WHERE providerID=providerID AND partID=partID)0 ROLLBACK TRANSACTION TransName

26、 DELETE FROM Supply Where quantity=0 UPDATE OfferToBuy SET quantity=quantity-quantity WHERE customerID=customerID AND partID=partID IF(SELECT quantity FROM OfferToBuy WHERE customerID=customerID AND partID=partID)0ROLLBACK TRANSACTION TransNameDELETE FROM OfferToBuy Where quantity=0 COMMIT TRANSACTI

27、ON TransName GO为了使用方便，这里定义了一个存贮过程，功能是完成从Agreement的一个元组到Business 的一个元组的转化工作。这里考虑到了删除空的Supply 和OfferToBuy项；更加重要的是，这里考虑到了非法的Agreement的情况，在一段时间后，由于供应商或者顾客修改数据， Agreement可能就非法，这时就需要把这个事务废除，所以，这里检查了Supply表和OfferToBuy表中的数据，确保数据仍然正确。另外，交易员或者说交易所必须承担的一项任务是更新零件列表。这里在考虑顾客和供应商的时候，并没有给予他们修改零件列表的权利，所以他们必须根据数据库中已有

28、的项更新自己的供求信息。由于这个数据库实际上更加偏重于模型化，而不是一个实际环境中的数据库，所以在实现应用模型的时候还需要对这个数据库的模型作一些修改。由于本实验在模型设计上使用了Microsoft Transact-SQL的语法，因此以上的数据库操作都是在 SQL SERVER7.0上测试通过的。6、 实验数据示例插入零件作息： insert into Part(Color, Name, Weght, Intro) values(black,stick,30,of steel);显示刚插入的零件id： select id from Part where name=stick; id 1(1

29、row(s) affected)（不同的实验，id值可能不同。以后相应操作要保持前后一致就可以了。）插入供应商信息：insert into Provider(Name, password, Address, Tel, Intro) values(com1,1234,北京,nothing);显示刚插入的供应商id：select id from Provider where name=com1; id 1(1 row(s) affected)插入顾客信息：insert into Customer(Name, Address, Tel) values(cus1,北京,);显示刚插入的顾客id：sel

30、ect id from Customer where name=cus1; id 1(1 row(s) affected)插入供应商供应信息：insert into Supply(PartID, ProviderID,Price, Quantity) values(1,1,20,100);插入顾客需求信息：insert into OfferToBuy(PartID, CustomerID,Price, Quantity) values(1,1,20,50);插入协议信息：insert into Agreement(CustomerID,ProviderID,PartID,Price,Quant

31、ity,CustomerSign,ProviderSign) values(1,1,1,20,30,1,1);执行交易操作：PASS_AGREEMENT 1,1,1（后面的三个参数分别对应前面选择出的供应商ID、顾客ID和零件ID。）显示交易后供应信息和需求信息：select Quantity from Supply where PartID=1 and ProviderID=1; Quantity 70(1 row(s) affected)select Quantity from OfferToBuy where PartID=1 and CustomerID=1; Quantity 20(

32、1 row(s) affected)我们来分析上面的结果：首先，保存在Supply 表中ID 为1的零件供应量为100（参见Supply表的Insert语句），保存在 OfferToBuy表中 ID为1的零件需求量为50（参见 OfferToBuy表中的Insert语句）。在Agreement表中指出ID为1的供应商和ID为1的顾客要交易30个ID为1的零件。当执行存储过程PASS_AGREEMENT之后，Supply和OfferToBuy表中相应的数量都减少了30，交易成功。再次执行交易操作： delete from Business;PASS_AGREEMENT 1,1,1显示交易后供应信息和需求信息：select Quantity