1、軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)指導(dǎo)書(shū)班級(jí)姓名實(shí)驗(yàn)一 、二叉樹(shù)遍歷的程序編制二叉樹(shù)是一種典型、應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)。設(shè)置本實(shí)驗(yàn)可以使學(xué)生進(jìn)一步加強(qiáng)對(duì)二叉樹(shù)遍歷算法的理解。一、實(shí)驗(yàn)?zāi)康模? 理解二叉樹(shù)在計(jì)算機(jī)中存儲(chǔ)的物理結(jié)構(gòu)。2 掌握二叉樹(shù)遍歷算法。二、實(shí)驗(yàn)要求任意輸入一棵二叉樹(shù)，根據(jù)二叉樹(shù)前序、中序和后遍歷算法，分別輸出遍歷結(jié)果。三、實(shí)驗(yàn)設(shè)備1 計(jì)算機(jī)系統(tǒng)2 安裝Turbo C或其他C語(yǔ)言集成開(kāi)發(fā)工具四、實(shí)驗(yàn)原理1、前序遍歷原理：先訪問(wèn)根，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)，依次遞歸遍歷樹(shù)的所有節(jié)點(diǎn)。2、中序遍歷原理：先訪問(wèn)左子樹(shù)，再訪問(wèn)根，最后訪問(wèn)右子樹(shù)，依次遞歸遍歷樹(shù)的所有節(jié)點(diǎn)。3、中序遍歷原理：先訪問(wèn)右子樹(shù)

2、，再訪問(wèn)根，最后訪問(wèn)左子樹(shù)，依次遞歸遍歷樹(shù)的所有節(jié)點(diǎn)。ABCEDEFGH4、例子前序遍歷：ABDEGHCF中序遍歷：DBGEHACF后序遍歷：DGHEBFCA4、編程基本要領(lǐng)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);五、實(shí)驗(yàn)步驟1、 在C語(yǔ)言集成開(kāi)發(fā)工具的編輯器中輸入源程序2、 利用編譯器編譯源程序3、 連接生成執(zhí)行文件4、 執(zhí)行程序?qū)嶒?yàn)二 、單向鏈表插入與刪除的程序編制單向鏈表是一種典型、應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，對(duì)其插入與刪除算法較為復(fù)雜。設(shè)置本實(shí)驗(yàn)可以使學(xué)生進(jìn)一步加強(qiáng)對(duì)單向鏈表插入與刪除算法的理解。一、實(shí)驗(yàn)?zāi)康模?、理解單向鏈表在計(jì)算機(jī)中存儲(chǔ)的物理結(jié)構(gòu)。2、掌握單向

4、鏈表插入與刪除算法。二、實(shí)驗(yàn)要求任意輸入單向鏈表，根據(jù)單向鏈表插入與刪除算法，輸出插入與刪除后的結(jié)果。三、實(shí)驗(yàn)設(shè)備3 計(jì)算機(jī)系統(tǒng)4 安裝Turbo C或其他C語(yǔ)言集成開(kāi)發(fā)工具四、實(shí)驗(yàn)原理xheadqpsX1、 前插原理 pheadr=p-nextp-next=r-nextfree(r)rXX2、 刪除原理六、實(shí)驗(yàn)步驟1、在C語(yǔ)言集成開(kāi)發(fā)工具的編輯器中輸入源程序2、利用編譯器編譯源程序3、連接生成執(zhí)行文件4、執(zhí)行程序?qū)嶒?yàn)三 數(shù)據(jù)庫(kù)管理系統(tǒng)綜合應(yīng)用-零件交易中心管理系統(tǒng)（例）一、 實(shí)驗(yàn)?zāi)康模?通過(guò)完成從用戶需求分析、數(shù)據(jù)庫(kù)設(shè)計(jì)到上機(jī)編程、調(diào)試和應(yīng)用等全過(guò)程，進(jìn)一步了解和掌握數(shù)據(jù)庫(kù)這一章所講解的內(nèi)容

5、。二、實(shí)驗(yàn)簡(jiǎn)述：零件交易管理系統(tǒng)主要提供顧客和供應(yīng)商之間完成零件交易的功能，其中包括供應(yīng)商信息、顧客信息以及零件信息。供應(yīng)商信息包括供應(yīng)商號(hào)、供應(yīng)商名、地址、電話、簡(jiǎn)介；顧客信息包括顧客號(hào)、顧客名、地址、電話；零件信息包括零件號(hào)、零件名、重量、顏色、簡(jiǎn)介等。此系統(tǒng)可以讓供應(yīng)商增加、刪除和修改所提供的零件產(chǎn)品，還可以讓顧客增加、刪除和修改所需求的零件。交易可以利用顧客提出的需求信息和供應(yīng)商提出的供應(yīng)信息來(lái)提出交易的建議，由供應(yīng)商和顧客進(jìn)行確認(rèn)后即完成這筆交易。三、實(shí)驗(yàn)設(shè)備1、安裝SQL Server的服務(wù)器系統(tǒng)2、安裝了SQL Server客戶端的計(jì)算機(jī)系統(tǒng)3、由服務(wù)器與客戶端的計(jì)算機(jī)系統(tǒng)所構(gòu)成

6、的計(jì)算機(jī)網(wǎng)絡(luò)三、實(shí)驗(yàn)要求： 完成該系統(tǒng)的數(shù)據(jù)庫(kù)設(shè)計(jì)；用SQL實(shí)現(xiàn)數(shù)據(jù)庫(kù)的設(shè)計(jì)，并在SQL Server上調(diào)試通過(guò)。四、實(shí)驗(yàn)步驟與參考答案：1、 需求分析11 供應(yīng)商供應(yīng)商的操作流程圖如圖A.1所示。12 顧客顧客的地位和供應(yīng)商幾乎是對(duì)稱(chēng)的，所以功能分類(lèi)上也很相似。顧客的操作流程圖如圖A.2所示。13 交易員交易員的工作就是提出交易和完成交易。這里需要仔細(xì)考慮的問(wèn)題是：一個(gè)交易如何產(chǎn)生，并如何達(dá)成，可以用圖A.3來(lái)說(shuō)明這個(gè)問(wèn)題。我們?cè)谔幚斫灰椎臅r(shí)候可能面臨如下問(wèn)題：（1） 一個(gè)交易只能在交易雙方都同意的情況下才可以進(jìn)行，所以數(shù)據(jù)庫(kù)中的供求信息只能作為達(dá)成某個(gè)交易的基礎(chǔ)；（2） 交易的雙方可能不同

7、時(shí)使用這個(gè)系統(tǒng)，因此需要系統(tǒng)提供一個(gè)雙方交換信息的方式；（3） 系統(tǒng)需要提供一種方便系統(tǒng)（交易員）向用戶提出建議來(lái)促成交易的途徑，并在保證數(shù)據(jù)庫(kù)完整性的情況下達(dá)成交易。2、 概念模型設(shè)計(jì)數(shù)據(jù)庫(kù)需要表述的信息有以下幾種：（1） 零件信息（2） 供應(yīng)商信息（3） 顧客信息（4） 供應(yīng)商和零件之間的聯(lián)系（供應(yīng)）（5） 顧客和零件之間的聯(lián)系（求購(gòu)）（6） 交易（三元聯(lián)系）可以用ER模型表述該模型的設(shè)計(jì)，ER圖如圖A.4所示。3、 邏輯設(shè)計(jì)通過(guò)ER模型到關(guān)系模型的轉(zhuǎn)化，可以得到如下關(guān)系模式：（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） 每個(gè)關(guān)系模式的鍵碼都用下劃線標(biāo)出。同時(shí)，對(duì)于從聯(lián)系導(dǎo)出的關(guān)系Supply（供應(yīng)），OfferToBuy（求購(gòu)）和Business（交易），使用與之聯(lián)系的實(shí)體集的鍵碼作為自己的鍵碼，必須符合外鍵碼約束

9、。對(duì)于Customer（顧客），Provider（供應(yīng)商）和Part（零件）之間，不存在直接的約束，所以可以存在沒(méi)有供應(yīng)商供應(yīng)同時(shí)也沒(méi)有顧客求購(gòu)的零件。4、 物理設(shè)計(jì)為了提高在表中搜索元組的速度，在實(shí)際實(shí)現(xiàn)的時(shí)候應(yīng)該基于鍵碼建立索引。下面是各表中建立索引的表項(xiàng)：（1） Part（ID）（2） Provider（ID）（3） Customer（ID）（4） Supply（PartID，ProviderID）（5） OfferToBuy（CustomerID，PartID）（6） Business（CustometID，ProviderID）5、 用SQL實(shí)現(xiàn)設(shè)計(jì)實(shí)現(xiàn)該設(shè)計(jì)的環(huán)境為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 供應(yīng)商操作（1）注冊(cè)（register） INSERT INTO Provider(Name, Address, Tel,Intro)VALUES(#Name, #Address, #Tel, #Intro)在登記操作后，供應(yīng)商得到一個(gè)唯一的ID，可以根據(jù)這個(gè)ID來(lái)查詢和修改供應(yīng)商的數(shù)據(jù)。（2）注銷(xiāo)（unregister） DELETE Provider WHERE(ID=#ID)（3

16、）修改個(gè)人信息（update）UPDATE Provider Set(Name=#Name,Address=#Address,Tel=#Tel,Intro=#Intro) WHERE(ID=#ID)（4）增加供應(yīng)項(xiàng)（add_supply_item）INSERT INTO Supply(PartID, ProviderID,Price,Quantity) VALUES(#PartID,#ProviderID,#Price,#Quantuty)（5）刪除供應(yīng)項(xiàng)（delete_supply_item）DELETE Supply WHERE(PartID=# PartID AND ProviderID

17、 =#ProviderID)（6）修改供應(yīng)項(xiàng)（update_supply_item）UPDATE Supply Set(Price=#Price,Quantity=# Quantity) WHERE(PartID=# PartID AND ProviderID =#ProviderID) 很明顯，系統(tǒng)并沒(méi)有提供面向供應(yīng)商修改零件信息的接口，所以供應(yīng)商提供的零件必須已知在零件表中存在；可以這樣假設(shè)，交易所的管理員負(fù)責(zé)更新零件信息，而供應(yīng)商可以向交易所申請(qǐng)?jiān)黾幽撤N零件的信息。事實(shí)上顧客也可以提出這樣的要求。58 顧客操作（1）注冊(cè)（register）INSERT INTO Customer(Nam

18、e ,Address, Tel) VALUES(#Name ,#Address,#Tel) 在登記操作后，顧客得到一個(gè)唯一的ID，可以根據(jù)這個(gè)ID來(lái)查詢和修改顧客的數(shù)據(jù)。（2）注銷(xiāo)（unregister） DELETE Customer WHERE(ID=#ID)（3）修改個(gè)人信息（update）UPDATE Customer Set(Name=#Name,Address=#Address,Tel=#Tel)WHERE(ID=#ID)（4）增加需求項(xiàng)（add_OfferToBuy_item）INSERT INTO OfferToBuy (PartID, CustomerID,Price,Qua

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

20、易員針對(duì)需求分析中提出的問(wèn)題，提出了“協(xié)議書(shū)”的解決方案，方案的說(shuō)明如下：（1）每個(gè)交易在達(dá)成以前都作為協(xié)議書(shū)保存在數(shù)據(jù)庫(kù)中，協(xié)議書(shū)具有和交易一樣的完備信息，可以在條件成熟的情況下轉(zhuǎn)為一個(gè)達(dá)成的交易；（2）協(xié)議書(shū)只有在供應(yīng)商和顧客都簽字的情況下才有效；有效的協(xié)議書(shū)由交易員簽發(fā)，協(xié)議書(shū)一經(jīng)簽發(fā)，就生效，表明一個(gè)交易的達(dá)成，數(shù)據(jù)庫(kù)中的數(shù)據(jù)將同時(shí)予以修改；（3）協(xié)議書(shū)可以由供應(yīng)商、顧客或者交易員中的任意一個(gè)提出申請(qǐng)。當(dāng)協(xié)議書(shū)在雙方?jīng)]有都簽字前，協(xié)議的雙方或者交易員都可以刪除這個(gè)協(xié)議書(shū)；但是，當(dāng)協(xié)議書(shū)簽字完畢后，協(xié)議書(shū)就不得刪除（修改），只能由交易員進(jìn)行處理；（4）協(xié)議書(shū)有可能在轉(zhuǎn)成交易的過(guò)程中失敗，

21、因?yàn)樵诮灰走_(dá)成以前，數(shù)據(jù)庫(kù)中的數(shù)據(jù)有可能因?yàn)槠渌灰锥兓?，一個(gè)協(xié)議書(shū)可能失效，這是允許的。根據(jù)以上分析，對(duì)數(shù)據(jù)庫(kù)的模型作一些修改，增加協(xié)議書(shū)表，其關(guān)系模型如下：Agreement(CustomerID,ProviderID,PartID,Price,Quantity,CustomerSign,ProviderSign)對(duì)應(yīng)的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);與上述其他操作相比，交易的操作對(duì)數(shù)據(jù)完整性要求比較高，其中需要注意的地方是：（1）切防止同一用戶（供應(yīng)商、顧客）的數(shù)據(jù)因兩個(gè)交易而同時(shí)修改；（2）需要同時(shí)對(duì)供應(yīng)數(shù)據(jù)庫(kù)（Supply）、需求數(shù)據(jù)庫(kù)（OfferToBuy）、交易數(shù)據(jù)庫(kù)（Business）和協(xié)議數(shù)據(jù)庫(kù)（Agreement）作出修改，而且需要保持這些修改的原子性；（3）很顯然，這些要求正是對(duì)于一個(gè)事務(wù)（transaction）的要求，所以可以用一個(gè)事務(wù)來(lái)完成簽發(fā)一個(gè)協(xié)議的操作。事務(wù)的描述如下：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為了使用方便，這里定義了一個(gè)存貯過(guò)程，功能是完成從Agreement的一個(gè)元組到Business 的一個(gè)元組的轉(zhuǎn)化工作。這里考慮到了刪除空的Supply 和OfferToBuy項(xiàng)；更加重要的是，這里考慮到了非法的Agreement的情況，在一段時(shí)間后，由于供應(yīng)商或者顧客修改數(shù)據(jù)， Agreement可能就非法，這時(shí)就需要把這個(gè)事務(wù)廢除，所以，這里檢查了Supply表和OfferToBuy表中的數(shù)據(jù)，確保數(shù)據(jù)仍然正確。另外，交易員或者說(shuō)交易所必須承擔(dān)的一項(xiàng)任務(wù)是更新零件列表。這里在考慮顧客和供應(yīng)商的時(shí)候，并沒(méi)有給予他們修改零件列表的權(quán)利，所以他們必須根據(jù)數(shù)據(jù)庫(kù)中已有

28、的項(xiàng)更新自己的供求信息。由于這個(gè)數(shù)據(jù)庫(kù)實(shí)際上更加偏重于模型化，而不是一個(gè)實(shí)際環(huán)境中的數(shù)據(jù)庫(kù)，所以在實(shí)現(xiàn)應(yīng)用模型的時(shí)候還需要對(duì)這個(gè)數(shù)據(jù)庫(kù)的模型作一些修改。由于本實(shí)驗(yàn)在模型設(shè)計(jì)上使用了Microsoft Transact-SQL的語(yǔ)法，因此以上的數(shù)據(jù)庫(kù)操作都是在 SQL SERVER7.0上測(cè)試通過(guò)的。6、 實(shí)驗(yàn)數(shù)據(jù)示例插入零件作息： 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)（不同的實(shí)驗(yàn)，id值可能不同。以后相應(yīng)操作要保持前后一致就可以了。）插入供應(yīng)商信息：insert into Provider(Name, password, Address, Tel, Intro) values(com1,1234,北京,nothing);顯示剛插入的供應(yīng)商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)插入供應(yīng)商供應(yīng)信息：insert into Supply(PartID, ProviderID,Price, Quantity) values(1,1,20,100);插入顧客需求信息：insert into OfferToBuy(PartID, CustomerID,Price, Quantity) values(1,1,20,50);插入?yún)f(xié)議信息：insert into Agreement(CustomerID,ProviderID,PartID,Price,Quant

31、ity,CustomerSign,ProviderSign) values(1,1,1,20,30,1,1);執(zhí)行交易操作：PASS_AGREEMENT 1,1,1（后面的三個(gè)參數(shù)分別對(duì)應(yīng)前面選擇出的供應(yīng)商ID、顧客ID和零件ID。）顯示交易后供應(yīng)信息和需求信息：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)我們來(lái)分析上面的結(jié)果：首先，保存在Supply 表中ID 為1的零件供應(yīng)量為100（參見(jiàn)Supply表的Insert語(yǔ)句），保存在 OfferToBuy表中 ID為1的零件需求量為50（參見(jiàn) OfferToBuy表中的Insert語(yǔ)句）。在Agreement表中指出ID為1的供應(yīng)商和ID為1的顧客要交易30個(gè)ID為1的零件。當(dāng)執(zhí)行存儲(chǔ)過(guò)程PASS_AGREEMENT之后，Supply和OfferToBuy表中相應(yīng)的數(shù)量都減少了30，交易成功。再次執(zhí)行交易操作： delete from Business;PASS_AGREEMENT 1,1,1顯示交易后供應(yīng)信息和需求信息：select Quantity