徐士良《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》（第4版）筆記和課后習(xí)題詳解

目錄

內(nèi)容簡介

目錄

第1章預(yù)備知識(shí)

1.1復(fù)習(xí)筆記

1.2課后習(xí)題詳解

第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.1復(fù)習(xí)筆記

2.2課后習(xí)題詳解

第3章查找與排序技術(shù)

3.1復(fù)習(xí)筆記

3.2課后習(xí)題詳解

第4章資源管理技術(shù)

4.1復(fù)習(xí)筆記

4.2課后習(xí)題詳解

第5章數(shù)據(jù)庫設(shè)計(jì)技術(shù)

5.1復(fù)習(xí)筆記

5.2課后習(xí)題詳解

第6章編譯技術(shù)概述

6.1復(fù)習(xí)筆記

6.2課后習(xí)題詳解

第7章應(yīng)用軟件設(shè)計(jì)與開發(fā)技術(shù)

7.1復(fù)習(xí)筆記

7,2課后習(xí)題詳解

第1章預(yù)備知識(shí)

1.1復(fù)習(xí)筆記

一、集合

基本概念

集合是指若干個(gè)或無窮多個(gè)具有相同屬性的元(元素)的集體。通常，一個(gè)集合名稱用大

寫字母表示，而集合中的某個(gè)元素用小寫字母表示。如果集合M由n(n>0)個(gè)元素a“出

，…，a”組成，則稱集合M為有限集。如果一個(gè)集合中有無窮多個(gè)元素，則稱此集合為無

限集。不包括任何元素的集合稱為空集。空集通常用①表示。如果M是一個(gè)集合，a是集

合M中的一個(gè)元素，則記作aGM,稱元素a屬于集合M；如果a不是集合M中的元素，則記

作a￡M,稱元素a不屬于集合M。

(1)列舉法

用列舉法表示一個(gè)集合是將此集合中的元素全部列出來，或者列出若干項(xiàng)但能根據(jù)規(guī)律可

知其所有的元素。例如：

大于1而小于100的所有整數(shù)的集合A可以表示為

A={2,3,4,…,99}

(2)性質(zhì)敘述法

用性質(zhì)敘述法表示一個(gè)集合是將集合中的元素所具有的屬性描述出來。例如：

大于1而小于100的所有整數(shù)的集合A可以表示為

A={a[l<a<100的所有整數(shù)}

設(shè)M與N為兩個(gè)集合，若M中的每個(gè)元素也為N的元素，則稱M為N的子集，記作MGN,

若MGN且N中至少有一個(gè)元素a《M,則稱M為N的真子集，記作MuN。

基本運(yùn)算

(1)兩個(gè)集合的并

設(shè)有兩個(gè)集合M和N,它們的并集記作MUN,定義如下：

MUN={a|a^M或a^N}

(2)兩個(gè)集合的交

設(shè)有兩個(gè)集合M和N,它們的交集記作MAN,定義如下：

MCN={a|aGM且aGN}

兩個(gè)集合M和N的并、交均滿足交換律，即

MUN=NUM

MnN=NAM

(3)兩個(gè)集合的差

設(shè)有兩個(gè)集合M和N,它們的差集記作M-N,定義如下：

M-N={a|aCM但a《N}

兩個(gè)集合的差不滿足交換律，即

M-N^N-M

對于集合的并、交、差有以下幾點(diǎn)基本性質(zhì)：

①結(jié)合律

(AAB)nc=An(Bno

(AUB)UC=AU(BUC)

②分配律

An(BUC)=(AOB)U(AAC)

AU(BCIC)=(AUB)n(AUC)

(A-B)U<B-A)=(AUB)-(AnB)

BD(A-B)=0

(AnB)U(A-B)=A

③其他

(4)映射

映射的相關(guān)概念如下：

①設(shè)A、B是兩個(gè)非空集，如果根據(jù)一定的法則f,對于每一個(gè)xGA,在B中都有唯一確定

的y與之對應(yīng)，則稱f為定義在A上而在B中取值的映射，記作f：A-B,并將x與y的關(guān)系記

作y=f(x),x稱為自變元，y稱為在f作用下x的像；

②設(shè)給定映射f：A-B,且B=f(A),若對于每個(gè)yCB僅有唯一的xdA使f(x)=

y,則稱侑逆映射f"；

③若A、B兩個(gè)集合有一一映射f存在，使f(A)=

B,則稱A與B成對應(yīng)，A與B對等，記作A?B。

集合的對等具有以下性質(zhì)：

自反性：A~A；

對稱性：若A?B,則B?A；

傳遞性：若A?B且B?C,則A?C。

自然數(shù)集與數(shù)學(xué)歸納法

由所有自然數(shù)組成的集合［1，2,3,…}稱為自然數(shù)集。自然數(shù)集是一個(gè)無限集。由自然

數(shù)組成的集合均是自然數(shù)集的子集。自然數(shù)集的子集可以是有限集，也可以是無限集。它

們具有如下性質(zhì)：

(1)在自然數(shù)集的任一非空子集M中，必定有一個(gè)最小數(shù)；

(2)設(shè)M是由自然數(shù)形成的集合，如果它含有1,2,…，k,并且當(dāng)它含有數(shù)n-1,n-

2,n-k(n>k)時(shí)，那么它含有所有的自然數(shù)，即M是自然數(shù)集。

笛卡兒積

AXD2X???XD?={(?，/，…，點(diǎn))|d.e

設(shè)有n個(gè)集合D“D”…，D,?此n個(gè)集合的笛卡兒積定義為

其中(&,d?)稱為n元組，&稱為n元組的第i個(gè)分量。

由笛卡兒積的定義可以看出，n個(gè)集合的笛卡兒積是以n元組為元素的集合，而每一個(gè)n元

組中的第i個(gè)分量取自于第i個(gè)集合Di。

?二元關(guān)系

(I)笛卡兒積

設(shè)M和N是兩個(gè)集合，則其笛卡兒積

MxN={(x,y)|xdNtayWN}

其中每一個(gè)子集稱為在MxN上的一個(gè)二元關(guān)系。

如果M=N,則其笛卡兒積

MxM={(x,y)|x,y￡M}

其中每一個(gè)子集稱為在集合M上的一個(gè)二元關(guān)系，簡稱為在集合M上的一個(gè)關(guān)系。

(2)前后件、自反、對稱與傳遞

設(shè)R是集合M上的一個(gè)關(guān)系：

①如果(a,b)GR,則稱a是b的關(guān)于R的前件，b是a的關(guān)于R的后件；

②如果對于每一個(gè)aWM,都有(a,a)GR,則稱關(guān)系R是自反的；如果對于任何a?M,

(a,a)GR均不成立，則稱關(guān)系R是非自反的；

③如果（a,b）WR時(shí)必有（b,a）GR,則稱關(guān)系R是對稱的；

④如果當(dāng)（a,b）GR且（b,c）GR時(shí)必有（a,c）GR,則稱關(guān)系R是傳遞的。

（3）基與傳遞體

設(shè)R是M上的一個(gè)傳遞關(guān)系，且TGR,若對于任何（x,y）GR,在M中有元素x。，x,,x2

，…，x?（n>l）滿足：

①Xo=X;

②“y；

③（Xhi,Xi）GT（i=l,2,n）

則稱關(guān)系T是關(guān)系R的基，又稱關(guān)系R是關(guān)系T的傳遞體。

二、算法

基本概念

算法是指解題方案準(zhǔn)確而完整的描述。算法具有如下基本特征：

（1）能行性

算法的能行性包括以下兩個(gè)方面：

①算法中的每一個(gè)步驟必須能夠?qū)崿F(xiàn)；

②算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。

（2）確定性

算法的確定性，是指算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋

，也不允許有多義性。

（3）有窮性

算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之

后終止。算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。

（4）擁有足夠的情報(bào)

一個(gè)算法是否有效，還取決于為算法所提供的情報(bào)是否足夠。

綜上所述，算法是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明

確的，此順序?qū)⒃谟邢薜拇螖?shù)內(nèi)終止。

基本方法

（1）列舉法

列舉法的基本思想是：根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢

驗(yàn)?zāi)男┦切枰模男┦遣恍枰摹?/p>

列舉法的特點(diǎn)是算法比較簡單。但當(dāng)列舉的可能情況較多時(shí)，執(zhí)行列舉算法的工作量將會(huì)

很大，因此需要對算法進(jìn)行優(yōu)化。

(2)歸納法

歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。

(3)遞推法

遞推法是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。

(4)遞歸法

遞歸法的基本思想是在解決了逐層分解到最后的那些最簡單的問題后，再沿著原來分解的

逆過程逐步進(jìn)行綜合。

遞歸分為直接遞歸與間接遞歸兩種。如果一個(gè)算法P顯式地調(diào)用自己則稱為直接遞歸。如

果算法P調(diào)用另一個(gè)算法Q,而算法Q又調(diào)用算法P,則稱為間接遞歸調(diào)用。

(5)分治法(減半遞推技術(shù))

分治法，即對問題分而治之。工程上常用的分治法是減半遞推技術(shù)?！皽p半”是指將問題的

規(guī)模減半，而問題的性質(zhì)不變。“遞推”是指重復(fù)“減半”的過程。

(6)回溯法

通過對問題的分析，找出一個(gè)解決問題的線索，然后沿著這個(gè)線索逐步試探。對于每一步

試探，若試探成功，就得到問題的解；若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。

復(fù)雜度分析

算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。

(1)時(shí)間復(fù)雜度

①定義

算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

客觀地反應(yīng)算法的效率可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工

作量。而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量f(n)。其中n

是問題的規(guī)模。

②方法

在同一問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí)，可以用以

下兩種方法來分析算法的工作量。

a.平均性態(tài)

平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均值來度量算法的工作量。

設(shè)X是所有可能輸入中的某個(gè)特定輸入，P(X)是X出現(xiàn)的概率，t(X)是算法在輸入為X

時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為

A(zz)=X小(工"(1)

b.最壞情況復(fù)雜性

W(ri')=max{寅JC)}

最壞情況分析是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為:

(2)空間復(fù)雜度

一個(gè)算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以

及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元

以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，

則稱該算法是原地工作的。

1.2課后習(xí)題詳解

集合M={d”&,小，d4,d5,d。}上的一個(gè)關(guān)系R如下：

R={(d,&)，(&,dj),(ds,d4),(di,d?),(di,4)，(di,d6)，(d,d3

),(小，出))

試驗(yàn)證Ti={(d,d：),(dj,d1),(di,&),(d“d(1),(d?4),(di,ds)}是

R的具有6個(gè)元素的基，而T?={(&,&),(d,,&),(di,ch),(d6,&)}不是R的

基。

答：對于T”顯然滿足T￡R,且對于關(guān)系R中的每一個(gè)二元組(x,y),在M中存在元素

RXo，N1，4，…，

（4&）d\,di（4,扇）￡丁】

(d，2,?)di

(4&)

(4,4)d\

(4,4)d\?dzgd4（4"2），（4，4）￡丁1

(4,4)d\,49d6(4,4)?(&&)GTi

(4,4)49a3（4,出）￡丁】

(&4)&，4(4,d6)en

X。，Xl,X2,…，Xn,滿足基的三個(gè)條件。驗(yàn)證過程如下:

由上可知，口是R的具有6個(gè)元素的基。

對于T2,由于（do,?。?R,因此，T?不是R的基。

設(shè)給定三個(gè)整數(shù)a,b,c,試寫出尋找其中數(shù)的一個(gè)算法（用C/C++描述），并分析在平

均情況與最壞情況下，算法分別要進(jìn)行多少次比較？

答：算法的C++描述如下：

khl.cpp

#include<iostream>

usingnamespacestd;

intmid(inta,mtb?mtc)

(

intm；

m=a；仔頁設(shè)a為中數(shù)

if(m>=b)

{

if(m>=c)

{

if(b>=c)m=b://b為中數(shù)

elsem=c;〃c為中數(shù)

}

)

else

(

if(m<=c)

{

if(b>=c)m=c;//c為中數(shù)

elsem=b;,7b為中數(shù)

}

}

return(m);〃返回中數(shù)

)

假設(shè)a,b,c中的每一個(gè)數(shù)為中數(shù)的概率相等(均為1/3)。由于當(dāng)a為中數(shù)時(shí)需要比較2次

2X(l/3)+3X(l/3)+3X(l/3)=8/3

,b或c為中數(shù)時(shí)均需要比較3次，因此，在平均情況下上述算法所需要的比較次數(shù)為

即在平均情況下，上述算法需要比較(8/3)次。

在最壞情況下，上述算法需要比較3次(當(dāng)b或c為中數(shù)時(shí))。

主函數(shù)例如下：

intmain。

(

int^bx;

M

cout?inputa1bb”；

cin?a?b?c;

cout?Hm=',?mid(a,b,c)?endl;

return0;

)

運(yùn)行結(jié)果如下(帶有下劃線的為鍵盤輸入)：

inputa,b,c=483

m=4

利用減半遞推技術(shù)，寫出求長度為n的數(shù)組中最大元素的遞歸算法(用C/C++描述)。設(shè)n

=2k,其中kNl。

答：利用減半遞推技術(shù)，求數(shù)組中最大元素的遞歸過程如下：如果數(shù)組中只有一個(gè)元素，

則該元素即是數(shù)組中最大的元素。否則將數(shù)組對分為前半部分和后半部分：

用同樣的方法求數(shù)組前半部分的最大值maxi。用同樣的方法求數(shù)組后半部分的最大值max

2o若maxl>max2,則maxi為數(shù)組中的最大值；否則max2為數(shù)組中的最大值。

算法的C++描述如下：

//chl_2.q)p

#include<iostream>

usingnamespacestd:

intmaxa(inta[]:n)

(

mtd,dl,d2;

if(m=n)return(a[m-l]);

else

(

d1=maxa(a.m,(m*n).2);

d2=maxa(a,(m*n)/2+l5n);

if(dl>d2)d=dl:

elsed=d2;

return(d):

)

}

主函數(shù)例如下：

(

inta[16]-{15,6,4,-1^.21.7,3.78,-51,4036,43,49,63,27);

cout?"max-"maxa(a,1,16)?endl,

return0;

}

運(yùn)行結(jié)果如下：

max=78

編寫二分法求方程實(shí)根的減半遞推算法(用C/C++描述)。

//chl_3.cpp

??include<iostream>

與include<cmath>

usingnamespacestd;

doubleroot(doublea,doubleb?doubleeps5double(*f)(double))

(

doublefOrflsc;

while(fabs(a-b)>=eps)

(

c=(a+b)2

n=(*f)(c)；

答：算法的C++描述如下:

retum(c);

if(f0*fl>0)

a=c;：取區(qū)間后半部分

else

b=c;；取區(qū)間前半部分

)

c=(a*b)2:

return(c);

}

主函數(shù)例如下：

intmainO

(

doublea=0.0,b=3.0;

doublef(double);

coutv<root(a1b000001J)?endl;

return0;

}

doublef(doublex)

{

retum(x*x*x-x*x-l.0);

)

運(yùn)行結(jié)果如下：

1.46557

編寫用回溯法求解皇后問題的算法（用C/C++描述）。

答：算法的C++描述如下：

//chl_4cpp

#mclude<iostreani>

#include<iomanip>

#include<cmath>

usingnamespacestd;

voidqueen(intn)

inti,j;k,jt,*q;

q=newint[n];

fbr(i=O;i<n;i-M-)

q[i]=o；

i=0；

jt=l；

cout?n???queenproblemJ,?endl:

while(jt=l)

if(q[i]<n)

k=0;

vvhile((k<i)&&((q[k]-q[i])*(febs(q[k]-q[i])-fabs(k-i)))!=O)

kf

if(k<i)

q[i]=q[i]+l;

else

{

if(i>n-l)

(

for(j=0:j<nj+H-)

cout?setu<5)?q[j]+l;

cout?endl;

q[n-l]=q[n-l]+l;

i=n-l;

)

)

)

else

(

q[>]=o；

if(i<0)

(

cout?endl:

deleteq;

return;

}

q[i]=q[i]+l;

)

)

}

主函數(shù)例如下：

intmainQ

(

intn;

cout???input口:“；

cin?n;

queen(n);

return0;

)

運(yùn)行結(jié)果如下：(帶有下劃線的為鍵盤輸入)

inputn:4

4queenproblem

2413

3142

設(shè)有12個(gè)小球。其中11個(gè)小球的重量相同，稱為好球；有一個(gè)小球的重量與II個(gè)好球的

重量不同(或輕或重)，稱這個(gè)小球?yàn)閴那?。試編寫一個(gè)算法(用C/C++描述)，用一個(gè)

無法碼的天平稱3次找出這個(gè)壞球，并確定其比好球輕還是重。

答：用一個(gè)長度為12的整型數(shù)組A(1：12)模擬表示編號(hào)分別為1?12的12個(gè)小球，其中

的元素值分別是各小球的重量。即在這個(gè)整型數(shù)組中，11個(gè)元素值是相同的，稱為好元素

;只有一個(gè)元素的值與11個(gè)好元素值不同(其值或大或小)，稱為壞元素。

下面通過對數(shù)組中元素值的比較來找出這個(gè)壞元素。具體比較過程如下。

首先將12個(gè)元素分成以下三組：

第一組為A(1),A(2),A(3),A(4)四個(gè)元素；第二組為A(5),A(6),A

(7),A(8)四個(gè)元素；第三組為A(9),A(10),A(11),A(12)四個(gè)元素。

3次比較過程如表1-1所示。

表1-1比較過程

第一次比較第二次比較第三次比較

若A⑴+A(9)=A(1O)+A(11),若A⑴>A(12),則A(12)壞且輕

若A(l)+A(2)

則A(12)壞若A(D則A(12)壞且重

+A(3)+A(4)

若A(1)+A(9)>A(10)+A(11),若A(10)=A(11),則A(9)壞且重

=A(5)+A(6)

則A⑼壞且重若A(10)>A(11),則A(11)壞且輕

+A(7)+A(8)

或A(10)與A(11)中有壞且輕若A(10)<A(11),則A(10)壞且輕

則A(9),A(10),

若A(l)+A(9)<A(10)+A(ll),若A(10)=A(11),則A(9)壞且輕

A(11),A(12)

則A(9)壞且輕若A(10)>A(11),則A(ID壞且重

中有壞

或A(10)與A(11)中有壞目重若A(10)<A(11),則A(10)壞且重

若A⑴+A(2)若A⑴+A(2)+A(6)=A(3)若A(D=A(7),則A(8)壞且輕

+A(3)+A(4)>A+A(4)+A(5),則A(7),A(8)

若A(D手A(7),則A(7)壞且輕

(5)+A(6)+A中有壞且輕

⑺+A(8)若A⑴+A(2)+A(6)>A⑶若A(l)=A(2),則A(5)壞且輕

則A⑴,A⑵，+A(4)+A(5),則A⑴,A(2)若A(D>A(2),則A(D壞且重

A(3),A(4)中有壞且重，或A(5)壞且輕若A⑴<A(2),則A⑵壞且重

中有壞且重若A(3)=A(4),則A(6)壞且輕

若A(1)+A(2)+A(6)<A(3)

或A⑸,A(6),若A(3)>A(4),則A(3)壞且重

+A(4)+A(5),則A⑶，A(4)

A(7),A(8)

中有壞且重，或A(6)壞且輕若A(3)<A(4),則A(4)壞且重

中有壞且輕

若A(D+A(2)若A⑴+A(2)+A(6)=A(3)若A(l)=A(7),則A(8)壞且重

+A(3)+A(4)+A(4)+A(5),則A⑺，A⑶

若A⑴盧A(7),則A(7)壞且重

<A(5)+A(6)中有壞且重

+A(7)+A(8)若A⑴+A(2)+A(6)>A(3)若A(3)=A(4),則A(6)壞且重

則A⑴,A(2),+A(4)+A(5),則A(3),A(4)若A(3)>A(4),則A(4)壞且輕

A(3),A(4)中有壞且輕，或A(6)壞且重若A(3)<A(4),則A(3)壞且輕

中有壞且輕，若A(l)=A(2),則A(5)壞且重

若A(1)+A(2)+A(6)<A(3)

或A(5),A(6),若A(D>A(2),則A(2)壞且輕

+A(4)+A(5),則A⑴,A(2)

A(7),A(8)

中有壞且輕，或A(5)壞且重若A⑴<A(2),則A⑴壞且輕

中有壞且重

根據(jù)表1-1所示的比較過程，可以寫出算法的C++描述如下:

?chl_5.cpp

??mclude<iostreain>

usingnamespacestd;

intal2(inta[])

(

if(a[l]+a[2]^a[3]-a[4]=a[5ba[6]*a[7H[8])//a[9],a[10],a[12]中有壞

if(a[l]-a[9]=a[10]-a[ll])/7a[12]壞

-a[12])

return(-l2);/a[l2]壞且輕

else

retum(12);〃a[12]壞且重

elseif(a[l]^a[9]>a[10]-a[ll])〃a[9]壞且重，或a[10]與a[U]中有壞且輕

if(a[10]=a[ll])

retum(9);〃a[9]壞且重

elseif(a[10]>a[ll])

retum(-ll);//a[11]壞且輕

else

retum(-lO);10]壞且輕

else〃a[9]壞且輕，或a[10]與a[U]中有壞且重

if(a[10]=a[ll])

retum(?9);〃a[9]壞且輕

elseif(a[10]>a[ll])

retum(l0);//a[l0]壞且重

else

retum(ll);//a[ll]壞且重

dseif(a[l]+a[2J+a[3]+a[4]>a[5]+a[6h-a[7]+a[8D

力a[l]>a[2],a[3],a[4]中有壞目重，或a[5],a[6],a[7],a[8]中有壞且輕

if(a[l]^[2]-a[6]=a[3]^a[4ba[5])a[8]中有壞且輕

if(a[l]=a[7])

retum(-S);閥8]壞且羥

else

retum(-7);洞7]壞且輕

elseif(a[l]^a[2]^a[6]>a[3]-a[4]^a(5D間1]…⑵中有壞且重，或a[5]壞且輕

if(a[l]=a[2])

retum(-5);/7a[習(xí)壞且輕

elseif(a[l]>a[2])

retum(l);Za[l]壞且重

else

retum(2);〃a[2]壞且重

elsea[4]中有壞且重，或a[6]壞且輕

if(a[3]=a[4])

retum(-6);〃a[6]壞且輕

elseif(a[3]>a[4])

return⑶；〃a[3]壞且重

else

retum(4);a[4]壞且重

else/a[l],a[2],a[3],a[4]中有壞且輕，或a[習(xí)，a[6],a[7],a[8]中有壞且重

if(a[l]-a[2]+a[6]=a[3]-a[4卜a[習(xí))〃a[7],a[8]中有壞且重

if(a[l]=a[7])

retum(8);〃a[8]壞目重

else

return⑺；/a[7]壞且重

elseif(a[l]，a[2]-a[6]>a[3]-a[4]-aA])a[4]中有壞且輕，或a[6]壞且重

if(a[3]=a[4])

retum(6);[習(xí)壞且重

elseif(a[3]>a[4])

return(-4);間4]壞且輕

else

return。)；”a[3]壞且輕

else.間1],a[2]中有壞且輕，或a[5]壞且重

if(a[l]=a[2])

retum(5);”a[習(xí)壞且重

elseif(a[l]>a[2])

retum(-2);〃a[2]壞且輕

else

retum(-l);"a[l]壞且輕

)

在上述C—程序中，為了直觀起見，定義的數(shù)組長度為13,其中數(shù)組元素a[0]在程序中不用。

主函數(shù)例如下：

intmainO

(

皿a[13]={0,5,5,555,5,5,455,5,5};

cout?,,k=,,?al2(a)?endl;

return0;

)

運(yùn)行結(jié)果如下：

k=-8表示數(shù)組中第8個(gè)元素為壞元素，即編號(hào)為8的小球?yàn)閴那?，且比好球輕。

第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.1復(fù)習(xí)筆記

一、基本概念

數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。

①數(shù)據(jù)的邏輯結(jié)構(gòu)包含的信息：

a.表示數(shù)據(jù)元素的信息；

b.表示各數(shù)據(jù)元素之間的前后件關(guān)系。

②數(shù)據(jù)的邏輯結(jié)構(gòu)要素：

a.數(shù)據(jù)元素的集合，通常用D來表示；

b.D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。

即數(shù)據(jù)結(jié)構(gòu)可以表示成

B={D,R}

其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元表示。

(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)

構(gòu))。

在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后

件關(guān)系的信息。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)的圖形表示

(1)將數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，稱為數(shù)據(jù)結(jié)點(diǎn)，

簡稱結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，將關(guān)系R中的每一個(gè)二元組

，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。

(2)在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)(也稱

為葉子結(jié)點(diǎn))。

數(shù)據(jù)結(jié)構(gòu)的類型

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)與非

線性結(jié)構(gòu)。

線性結(jié)構(gòu)又稱線性表，與其相關(guān)的幾個(gè)性質(zhì)如下：

(1)若一個(gè)線性結(jié)構(gòu)非空，則其有且只有一個(gè)根結(jié)點(diǎn)，且每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，

最多有一個(gè)后件；

(2)在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)；

(3)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)滿足上述兩個(gè)條件，但當(dāng)在此數(shù)據(jù)結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)

點(diǎn)后就不滿足這兩個(gè)條件了，則該數(shù)據(jù)結(jié)構(gòu)不能稱為線性結(jié)構(gòu)。

線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。一個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還

是屬于非線性結(jié)構(gòu)，這要根據(jù)具體情況來確定。

二、線性表及其順序存儲(chǔ)結(jié)構(gòu)

線性表及其運(yùn)算

(1)定義

線性表是由n(n>0)個(gè)數(shù)據(jù)元素a“a”…，心組成的一個(gè)有限序列。矩陣也是一個(gè)線性

表，在矩陣中，既可以把每一行看成是一個(gè)數(shù)據(jù)元素，也可以把每一列看成是一個(gè)數(shù)據(jù)元

素。其中，每一個(gè)數(shù)據(jù)元素實(shí)際上又是一個(gè)簡單的線性表。

非空線性表有如下一些結(jié)構(gòu)特征：

①有且只有一個(gè)根結(jié)點(diǎn)a“它無前件；

②有且只有一個(gè)終端結(jié)點(diǎn)a.，它無后件；

③除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。

(2)順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：

①線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；

②線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

在程序設(shè)計(jì)語言中，通常定義一個(gè)一維數(shù)組來表示線性表的順序存儲(chǔ)空間。在用一維數(shù)組

存放線性表時(shí)，該一維數(shù)組的長度通常要定義得比線性表的實(shí)際長度略大，以便對線性表

進(jìn)行各種運(yùn)算，特別是插入運(yùn)算。

建立一個(gè)容量為m的空線性表的順序存儲(chǔ)空間的C++描述如下：

templatecnpenameT>模板聲明，T為類型參數(shù)

voidinit_sq_LList（T*nLint*n）

（

\-=newT[m];動(dòng)態(tài)申請存儲(chǔ)空間

*n=0;.,線性表長度置為0

return:

）

在上述描述中，T為線性表中元素的虛擬數(shù)據(jù)類型。

要釋放線性表的順序存儲(chǔ)空間時(shí)，可以用“delete[]v；

（3）順序存儲(chǔ)下的插入運(yùn)算

假設(shè)線性表的存儲(chǔ)空間為V（1：m）,線性表的長度為n（n<m）,插入的位置為i（i表示

在第i個(gè)元素之前插入）。要插入新元素b,則插入的過程如下：

①首先處理以下三種異常情況。

a.當(dāng)存儲(chǔ)空間已滿（即n=m）時(shí)為“上溢”錯(cuò)誤，不能進(jìn)行插入，算法結(jié)束；

b.當(dāng)i>n時(shí)，認(rèn)為在最后一個(gè)元素之后插入；

c.當(dāng)i<l時(shí)，認(rèn)為在第1個(gè)元素之前插入；

②從最后一個(gè)元素開始，直到第i個(gè)元素，其中每一個(gè)元素均往后移動(dòng)一個(gè)位置；

③最后將新元素b插入到第i個(gè)位置，并且將線性表的長度增加1。

線性表在順序存儲(chǔ)結(jié)構(gòu)下插入算法的C++描述如下：

usingnamespacestd;

template<typen<imeT>〃模板聲明，T為類型參數(shù)

voidins_sq_LLi8t(T*v/intm,int?n,inti,Tb)

intk;

if(*n=?m)//存儲(chǔ)空間已滿，上溢錯(cuò)誤

{cout?"overflow!\nw;return;}

if(i>*n)i?*n+1;〃默認(rèn)為在最后一個(gè)元素之后插入

if(i<2>￡=%"或認(rèn)為在第一個(gè)元素之前播入

for(k**n;k>-i

v[k]?v(k^i]；〃從最后一個(gè)元素開始，直到第i個(gè)元素均往后移動(dòng)一個(gè)位置

v[i-1J-b;//插入新元素

*n-?n+1;〃線性表長度增加1

return;

（4）順序存儲(chǔ)下的刪除運(yùn)算

假設(shè)線性表的存儲(chǔ)空間為V（1：m）,線性表的長度為n（n<m）,刪除的位置為i,則刪

除的過程如下：

①首先處理以下兩種異常情況。

a.當(dāng)線性表為空時(shí)為“下溢”錯(cuò)誤，不能進(jìn)行刪除，算法結(jié)束；

b.當(dāng)i<l或i>n時(shí)，認(rèn)為在最后一個(gè)元素之后刪除。

②從第i+1個(gè)元素開始，直到最后一個(gè)元素，其中每一個(gè)元素均依次往前移動(dòng)一個(gè)位置；

③最后將線性表的長度減1。

（5）順序表類

下面的描述是將順序表的數(shù)據(jù)和基本操作（初始化、輸出、插入與刪除操作）封裝成一個(gè)

sqJLList類：

//sq_LList.h

#include<iostream>

usingnamespacestd;

template<classT>//模板聲明，數(shù)據(jù)元素虛擬類型為T

classsq_LList〃順序表類

{private:〃數(shù)據(jù)成員

intmm;〃存儲(chǔ)空間容量

intnn;//順序表長度

T*v;〃順序表存儲(chǔ)空間首地址

public:〃成員函數(shù)

sq_LList(){mm=O;nn=O;return;)

sq^LList(int);〃建立空順序表，申請存儲(chǔ)空間

voidprt_sq_LList();〃順序輸出順序表中的元索與順序表長度

intflag_sq__LList();〃檢測順序表的狀態(tài)

voidins_sq_LList(int,T);〃在表的指定元素前插入新元素

voiddel_sq_LList(int)；〃在表中耐除指定元素

)；

〃建立空順序表

template<classT>

sq_LList<T>::sqJLList(intm)

〃存儲(chǔ)空間容敏

v?newT[mm];〃動(dòng)態(tài)申請存儲(chǔ)空間

nn*0；〃順序表長度為0,即建立空順序表

recurn;

}

〃順序輸出順序裳中的元素與順序表長度

tempiate<classT>

voidsq_LList<T>::prt^sq_LList()

(inti;

cout?nnn-w?nn?endl;

for(i-0;i<nn；“?)cout?v[1]?end1;

return;

)

〃檢滯順序表的狀態(tài)

template<classT>

intsq_LList<T>::flag^sq_DList()

<if(nn-?mn)return(-1)；〃存儲(chǔ)空間已滿，返回-1

if(nn-?0)return(0);〃順序賽為空，返回Q

return(1);〃正拿返回1

i

〃在表的指定元素前插入新元素

template<classT>

voidsq_LList<T>::ins_sq_LList(inti,Tb)

(intk;

if(nnw-twn)〃存儲(chǔ)空間已滿，上溢錯(cuò)誤

{cout<^"ovetflowu?endl;return；)

ifU>nnl"nn+1;〃默認(rèn)為在數(shù)后一個(gè)元素之后插人

if<i<l)i-1;〃默認(rèn)為在第一個(gè)元素之前插人

for()c?nn;k>*i；k--)

vlkj-vlk-l}^〃從最后一個(gè)元素直到第i個(gè)元素均后移一個(gè)位置

〃插入揚(yáng)元素

nn-nn*l;//順序表長度加1

return;

)

“在聯(lián)洋表中刪除指定元素

template<classT>

voidsq^LList<T>::del_sg_LLlst(inti)

Iintk;

if<nn--0)〃順用表為空，下溢的識(shí)

(cout?*underflow!*?endl;return;}

ifH(i>nn))〃順序表中沒有這個(gè)元索

{cout?wNotthiselementinthelist!n?endl;

return;

for(k?i;k<nn;k+

v[k-l]av[k];//從第i個(gè)元素直到最后一個(gè)元素均前移一個(gè)位置

nn=nn-1;//順序表長度減1

return;

利用順序表類中的成員函數(shù)flag_sq_LList()可以解決上溢錯(cuò)誤信息沒有返回給調(diào)用程序

，調(diào)用程序無法處理的情況。成員函數(shù)flag_sq_LList()的功能是檢測順序表的當(dāng)前狀態(tài)

o若順序表滿，則返回函數(shù)值-1；若順序表空，則返回函數(shù)值0；正常情況則返回函數(shù)值1。

棧及

(1)定義

棧實(shí)際上也是線性表，只不過是一種特殊的線性表。其插入和刪除運(yùn)算都只在線性表的一

端進(jìn)行。

在棧中，將允許插入與刪除的一端稱為棧頂，將不允許插入與刪除的一端稱為棧底。棧頂

元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入的元素，

也是最后才被刪除的元素。即棧是按照“先進(jìn)后出"(FirstlnLast

Out,FILO)或“后進(jìn)先出”(LastInFirst

Out,LIFO)的原則組織數(shù)據(jù)的，通常用指針top來指向棧頂?shù)奈恢?，用指針bottom指向棧

底。往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素稱為退棧運(yùn)算。棧頂指針to

p動(dòng)態(tài)反映了棧中元素的變化情況。圖2-1是棧的示意圖。

入棧退棧

棧頂top

棧底bottom

圖2-1棧的示意圖

(2)順序存儲(chǔ)及運(yùn)算

①概念

在程序設(shè)計(jì)語言中，用一維數(shù)組S(1：m)作為棧的順序存儲(chǔ)空間，其中m為棧的最大容

量。通常，棧底指針指向?？臻g的低地址一端。S(bottom)通常為棧底元素(在棧非空

的情況下)，S(top)為棧頂元素。top=0表示棧空；top=m表示棧滿。

templatec^penameT>模板聲明，T為類型參數(shù)

voidinit_Stack（T皿血*top）

s-newT(m];動(dòng)態(tài)申請容量為m的存儲(chǔ)空間

*top-0;棧頂指針用為0,即?？?/p>

)

建立一個(gè)空棧的順序存儲(chǔ)空間(即初始化棧的順序存儲(chǔ)空間)的C++描述如下：

當(dāng)要釋放棧的順序存儲(chǔ)空間時(shí)，可以用“deleted；

②入棧運(yùn)算

入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。設(shè)棧順序存儲(chǔ)空間為S(1：m),棧頂指針為

top,入棧的元素為x。則入棧運(yùn)算的操作過程如下：

a.首先判斷棧頂指針是否已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置。如果是，則說明棧空間已

滿，不可能再進(jìn)行入棧操作，即為棧“上溢”錯(cuò)誤。算法結(jié)束；

b.將棧頂指針進(jìn)一(即top加1)；

c.最后將新元素x插入到棧頂指針指向的位置。

??mclude<iostream>

usingnamespacestd:

templatevtypenameT>

voidpush(T*ssmtm:int*topsTx)

(

if(*top=m){cout?wStack-overflownM;retuni:)

*top=*top-l;

s[*top-l]=x;

return:

}

在順序存儲(chǔ)結(jié)構(gòu)下入棧算法的C++描述如下：

③退棧運(yùn)算

退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。設(shè)棧順序存儲(chǔ)空間為S(1：m),棧

頂指針為top。則退棧運(yùn)算的操作過程如下：

a.首先判斷棧頂指針是否為0,如果是，則說明棧空，不可能進(jìn)行退棧操作，即為棧“下

溢”錯(cuò)誤，算法結(jié)束；

b.將棧頂元素賦給一個(gè)指定的變量；

c.最后將棧頂指針退一(即top減1)o

④讀棧頂元素

讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。設(shè)棧順序存儲(chǔ)空間為S(1：m),棧頂

指針為top。則讀棧頂元素的操作過程如下：

a.首先判斷棧頂指針是否為()，如果是，則說明?？?，讀不到棧頂元素，算法結(jié)束；

b.將棧頂元素賦給指定的變量y。

必須注意，這個(gè)運(yùn)算不刪除棧頂元素，只是將它的值賦給一個(gè)變量。因此，在這個(gè)運(yùn)算中

棧頂指針不會(huì)改變。

在順序存儲(chǔ)結(jié)構(gòu)下讀棧頂元素算法的C++描述如下：

#include<iostream>

usingnamespacestd:

templatecbpenameT>

Ttop（T*s5mtm:int*top）

（

Ty;

if（*top=0）{cout?HStackemptynM:retuni;}

y=s[*tcpl]

retum（y）;

）

（3）表達(dá)式的計(jì)算

①概念

計(jì)算機(jī)系統(tǒng)在具體處理表達(dá)式前，首先設(shè)置以下兩個(gè)棧：一是運(yùn)算符棧，用于在表達(dá)式處

理過程中存放運(yùn)算符。在開始時(shí)，運(yùn)算符棧中先壓入一個(gè)表達(dá)式結(jié)束符“；二是操作數(shù)

棧，用于在表達(dá)式處理過程中存放操作數(shù)。然后從左到右依次讀出表達(dá)式中的各個(gè)符號(hào)（

運(yùn)算符或操作數(shù)）。

②原則

每讀出一個(gè)符號(hào)按以下原則進(jìn)行處理：

a.若讀出的是操作數(shù)，則將該操作數(shù)壓入操作數(shù)棧，并依次讀下一個(gè)符號(hào)；

b.若讀出的是運(yùn)算符，則作進(jìn)一步判斷：

第一，若讀出運(yùn)算符的優(yōu)先級(jí)大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級(jí)，則將讀出的運(yùn)算符壓入

運(yùn)算符棧，并依次讀下一個(gè)符號(hào)。

第二，若讀出的是表達(dá)式結(jié)束符“；”，且運(yùn)算符棧棧頂?shù)倪\(yùn)算符也是表達(dá)式結(jié)束符“；”，

則表達(dá)式處理結(jié)束，最后的計(jì)算結(jié)果在操作數(shù)棧的棧頂位置。

第三，若讀出運(yùn)算符的優(yōu)先級(jí)不大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級(jí)，則從操作數(shù)棧連續(xù)退

出兩個(gè)操作數(shù)，并從運(yùn)算符棧退出一個(gè)運(yùn)算符，然