北京工業(yè)大學(xué)-計(jì)算機(jī)軟件基礎(chǔ)考試習(xí)題

1、l1名詞解釋：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)。名詞解釋：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)：數(shù)據(jù)：數(shù)據(jù)就是計(jì)算機(jī)可以保存和處理的信息。數(shù)據(jù)就是計(jì)算機(jī)可以保存和處理的信息。數(shù)據(jù)元素：數(shù)據(jù)元素：是組成數(shù)據(jù)的基本單位。是組成數(shù)據(jù)的基本單位。 數(shù)據(jù)元素可以是一個(gè)數(shù)或字符串，也可以由數(shù)據(jù)元素可以是一個(gè)數(shù)或字符串，也可以由若干數(shù)據(jù)項(xiàng)組成。若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。l數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：簡單地說，數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)及數(shù)：簡單地說，數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)及數(shù)據(jù)元素之間關(guān)系的一門學(xué)科。據(jù)元素之間關(guān)系的一門學(xué)科。它包括三個(gè)方面的內(nèi)它包括三個(gè)方面的內(nèi)容：容： 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和

2、數(shù)據(jù)的運(yùn)數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。算。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組是指數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式?？梢詮募系挠^點(diǎn)對(duì)數(shù)據(jù)結(jié)構(gòu)加以形式化描織形式?？梢詮募系挠^點(diǎn)對(duì)數(shù)據(jù)結(jié)構(gòu)加以形式化描述，即是一個(gè)二元組：述，即是一個(gè)二元組：Data-Structure = (D, R)l其中：其中：D是數(shù)據(jù)元素的集合，是數(shù)據(jù)元素的集合，R是是D上關(guān)系的集合。上關(guān)系的集合。l邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)

3、的。計(jì)算機(jī)的。l存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)的實(shí)現(xiàn)(亦稱映像亦稱映像)，它是依賴于計(jì)算機(jī)語言的。，它是依賴于計(jì)算機(jī)語言的。l算法算法：是由若干條指令組成的有限序列。：是由若干條指令組成的有限序列。l2簡述算法的五要素。簡述算法的五要素。 有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。 確定性：每條指令的含義必須明確，無二義性。確定性：每條指令的含義必須明確，無二義性。 可行性：每條指令都應(yīng)在有限的時(shí)間內(nèi)完成。可行性：每條指令都應(yīng)在有限的時(shí)間內(nèi)完成。 輸入性：具有零個(gè)或多個(gè)輸入量，即算法開始前對(duì)

4、輸入性：具有零個(gè)或多個(gè)輸入量，即算法開始前對(duì)算法給出的初始量。算法給出的初始量。 輸出性：至少產(chǎn)生一個(gè)輸出。輸出性：至少產(chǎn)生一個(gè)輸出。l3評(píng)價(jià)一個(gè)評(píng)價(jià)一個(gè)“正確的正確的”算法主要有哪兩個(gè)指算法主要有哪兩個(gè)指標(biāo)？標(biāo)？l(1) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度：依據(jù)算法編制成程序后，在計(jì)算機(jī)：依據(jù)算法編制成程序后，在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間。上運(yùn)行時(shí)所消耗的時(shí)間。l(2) 空間復(fù)雜度空間復(fù)雜度：依據(jù)算法編制成程序后，在計(jì)算機(jī)：依據(jù)算法編制成程序后，在計(jì)算機(jī)執(zhí)行過程中所需要的最大存儲(chǔ)空間。執(zhí)行過程中所需要的最大存儲(chǔ)空間。l4描述以下三個(gè)概念的描述以下三個(gè)概念的區(qū)別區(qū)別：頭指針、頭結(jié)：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)點(diǎn)

5、、首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn)第一個(gè)元素結(jié)點(diǎn))。l頭指針頭指針就是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。單鏈表是就是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。單鏈表是由頭指針唯一確定的。因此可以用頭指針的名字來命由頭指針唯一確定的。因此可以用頭指針的名字來命名單鏈表。名單鏈表。l頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在單鏈表第一個(gè)元素所在結(jié)點(diǎn)之前附設(shè)的一是在單鏈表第一個(gè)元素所在結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的指針域存儲(chǔ)第一個(gè)元素所在結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的指針域存儲(chǔ)第一個(gè)元素所在結(jié)點(diǎn)的存儲(chǔ)位置；數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)存儲(chǔ)位置；數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長度等附加信息。設(shè)置頭結(jié)點(diǎn)后，可使空如線性表的長度等附加信息。

6、設(shè)置頭結(jié)點(diǎn)后，可使空表和非空表的邏輯狀態(tài)及運(yùn)算統(tǒng)一起來。表和非空表的邏輯狀態(tài)及運(yùn)算統(tǒng)一起來。l首元結(jié)點(diǎn)首元結(jié)點(diǎn)就是第一個(gè)數(shù)據(jù)元素所在的結(jié)點(diǎn)。就是第一個(gè)數(shù)據(jù)元素所在的結(jié)點(diǎn)。l5有一線性表存儲(chǔ)在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單有一線性表存儲(chǔ)在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表鏈表L中，寫出計(jì)算線性表元素個(gè)數(shù)的算法。中，寫出計(jì)算線性表元素個(gè)數(shù)的算法。lint length(NODE *L) l NODE *p;l int counter=0;l p=L-next;l while(p!=L) l p=p-next;l counter+; l return counter; l 6假設(shè)有一個(gè)假設(shè)有一個(gè)循環(huán)單鏈表循環(huán)單鏈表的長

7、度大于的長度大于1，且表，且表中既無頭結(jié)點(diǎn)也無頭指針。已知中既無頭結(jié)點(diǎn)也無頭指針。已知S為指向鏈表為指向鏈表中某結(jié)點(diǎn)的指針，試編寫算法，在鏈表中刪除中某結(jié)點(diǎn)的指針，試編寫算法，在鏈表中刪除結(jié)點(diǎn)結(jié)點(diǎn)S的前趨結(jié)點(diǎn)。的前趨結(jié)點(diǎn)。l提示：提示：l(1) 定義一個(gè)指針變量定義一個(gè)指針變量p指向結(jié)點(diǎn)指向結(jié)點(diǎn)*s的直接后繼；的直接后繼；l(2) 定義一個(gè)指針變量定義一個(gè)指針變量q指向結(jié)點(diǎn)指向結(jié)點(diǎn)*s；l(3) 當(dāng)當(dāng)p-next不等于不等于s時(shí)，令時(shí)，令q=p，p=p-next; 重復(fù)上述處理直至重復(fù)上述處理直至p-next=s；l(4) 令令q-next=s; free(p)。lvoid delprior(

8、NODE *s) l NODE *p, *q;l p=s-next; q=s;l while(p-next!=s) l q=p; p=p-next; l q-next=s;l free(p);ll7已知指針已知指針ha和和hb分別指向兩個(gè)單鏈表的頭分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的數(shù)據(jù)域中存放鏈表的長度，結(jié)點(diǎn)，且頭結(jié)點(diǎn)的數(shù)據(jù)域中存放鏈表的長度，試寫一算法將這兩個(gè)鏈表連接在一起試寫一算法將這兩個(gè)鏈表連接在一起(即令其中即令其中一個(gè)表的首元結(jié)點(diǎn)連在另一個(gè)表的最后一個(gè)結(jié)一個(gè)表的首元結(jié)點(diǎn)連在另一個(gè)表的最后一個(gè)結(jié)點(diǎn)之后點(diǎn)之后)，hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以

9、盡可能短的時(shí)間完成連接運(yùn)算。請(qǐng)分求算法以盡可能短的時(shí)間完成連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。析你的算法的時(shí)間復(fù)雜度。l8設(shè)計(jì)一個(gè)將線性鏈表進(jìn)行逆置的算法。設(shè)計(jì)一個(gè)將線性鏈表進(jìn)行逆置的算法。l對(duì)于單鏈表，借助中間變量實(shí)現(xiàn)數(shù)據(jù)元素指針域中地對(duì)于單鏈表，借助中間變量實(shí)現(xiàn)數(shù)據(jù)元素指針域中地址值的變化。參見址值的變化。參見Shiyan12.c的的 reverse( )函數(shù)。函數(shù)。l9設(shè)有多項(xiàng)式設(shè)有多項(xiàng)式l A(x) = 7 + 3x + 9x8 + 3x15l B(x) = 5x + 6x7-9x8l (1) 用單鏈表給出用單鏈表給出A(x)的存儲(chǔ)表示；的存儲(chǔ)表示；l (2) 用單鏈表給出用單鏈表給

10、出B(x)的存儲(chǔ)表示；的存儲(chǔ)表示；l數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：l typedef struct polyterm l int coef;l int exp;l struct polyterm *next;l TERM;l10設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。l1，2，3，4 1，2，4，3 1，3，2，4l1，3，4，2 1，4，3，2 2，1，3，4l2，1，4，3 2，3，1，4 2，3，4，1l2，4，3，1 3，2，1，4 3，2，4，1l3，4，2，1 4，3，2，1l11假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)單鏈表表示隊(duì)列，

11、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)單鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(不設(shè)頭指不設(shè)頭指針針)，試編寫相應(yīng)的入列和出列算法。，試編寫相應(yīng)的入列和出列算法。l12假設(shè)以數(shù)組假設(shè)以數(shù)組sequm存放循環(huán)隊(duì)列的元素存放循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量，同時(shí)設(shè)變量rear和和quelen分別指示隊(duì)尾元素分別指示隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入列和出列算法。的隊(duì)滿條件，并寫出相應(yīng)的入列和出列算法。l隊(duì)滿條件：隊(duì)滿條件：quelen=mlstep1. 判定循環(huán)隊(duì)列是否已滿，若滿，則給出隊(duì)列溢判定循環(huán)隊(duì)

12、列是否已滿，若滿，則給出隊(duì)列溢出出錯(cuò)信息；出出錯(cuò)信息；lstep2. 隊(duì)尾指針后移，將入隊(duì)元素放入隊(duì)尾指針?biāo)戈?duì)尾指針后移，將入隊(duì)元素放入隊(duì)尾指針?biāo)傅拇鎯?chǔ)位置。的存儲(chǔ)位置。lstep3. 隊(duì)列元素個(gè)數(shù)增隊(duì)列元素個(gè)數(shù)增1。l#define MAXSIZE ml /* m為隊(duì)列中數(shù)據(jù)元素個(gè)數(shù)的最大可能值為隊(duì)列中數(shù)據(jù)元素個(gè)數(shù)的最大可能值*/l int sequMAXSIZE；l /* 假設(shè)數(shù)據(jù)元素的類型為整型假設(shè)數(shù)據(jù)元素的類型為整型*/l int quelen=0, rear=MAXSIZE-1；lvoid addqueue(int x) lif (quelen = MAXSIZE) lprint

13、f(循環(huán)隊(duì)列已滿，上溢循環(huán)隊(duì)列已滿，上溢! n);lexit(1);llelse lrear = (rear+1)% MAXSIZE;lsequ rear = x;lquelen+;lllstep1. 判定循環(huán)隊(duì)列是否為空，若空，則給出隊(duì)列溢判定循環(huán)隊(duì)列是否為空，若空，則給出隊(duì)列溢出出(下溢下溢)信息；信息；lstep2. 計(jì)算隊(duì)頭指針值，并讀取隊(duì)頭元素；計(jì)算隊(duì)頭指針值，并讀取隊(duì)頭元素；lstep3. 隊(duì)列元素個(gè)數(shù)減隊(duì)列元素個(gè)數(shù)減1。l#define MAXSIZE mlint sequMAXSIZE；lint quelen=0, rear=MAXSIZE-1；lint delqueue( )

14、 lint front, x;lif (quelen = 0) l printf(循環(huán)隊(duì)列已空，下溢！循環(huán)隊(duì)列已空，下溢！ n);l x =-1;lelse l front=(rear-quelen+MAXSIZE+1)% MAXSIZE;l x = sequfront;l quelen-;llreturn x;ll13試將下列稀疏矩陣試將下列稀疏矩陣A用三元組形式來表示。用三元組形式來表示。 0 3 0 0 -7 0 0 0 0 0 8 0 0 0 0 20 0 0 0 0 0 0 -13 0 0 A=05551123215-7331844120553-13l16二維數(shù)組二維數(shù)組A的元素是的

15、元素是6個(gè)字符組成的串，行個(gè)字符組成的串，行下標(biāo)下標(biāo)i的范圍從的范圍從0到到8，列下標(biāo)，列下標(biāo)j的范圍從的范圍從1到到10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存儲(chǔ)敘述中儲(chǔ)敘述中( )內(nèi)的正確答案。內(nèi)的正確答案。l (1) 存放存放A至少需要至少需要( )個(gè)字節(jié)。個(gè)字節(jié)。l (2) A的第的第8列和第列和第5行共占行共占( )個(gè)字節(jié)。個(gè)字節(jié)。l (3) 若若A按行存放，元素按行存放，元素A8，5 的起始地址與當(dāng)?shù)钠鹗嫉刂放c當(dāng)A按按列存放時(shí)的元素列存放時(shí)的元素( )的起始地址一致。的起始地址一致。l 供選擇答案供選擇答案l(1) a. 90； b. 18

16、0； c. 240； d. 270； e. 540；l(2) a. 108；b. 114；c. 54； d. 60； e. 150；l(3) a. A8,5；b. A3,10；c. A5,8；d. A0,9。l (1) 9*10*6=540l (2) (9+9)*6=108l (3) 8*10+5=85；85/9=9 余余 4l 答案：答案：A3，10；試驗(yàn)一：線性表的設(shè)計(jì)與實(shí)現(xiàn)試驗(yàn)一：線性表的設(shè)計(jì)與實(shí)現(xiàn) l1. 線性表基本操作的實(shí)現(xiàn)線性表基本操作的實(shí)現(xiàn)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)l#define MaxSize 1024 typedef int DataType; typedef stru

17、ct node DataType dataMaxSize; int last; SequenList;人人機(jī)交互部分機(jī)交互部分l內(nèi)容：通過屏幕提示功能選擇菜單；內(nèi)容：通過屏幕提示功能選擇菜單；通過鍵盤輸入實(shí)現(xiàn)功能的選擇；通過鍵盤輸入實(shí)現(xiàn)功能的選擇；l要求：提示內(nèi)容清晰易讀，要求：提示內(nèi)容清晰易讀，鍵盤操作簡單準(zhǔn)確；鍵盤操作簡單準(zhǔn)確；l實(shí)現(xiàn)：循環(huán)掃描鍵盤，等待用戶輸入；實(shí)現(xiàn)：循環(huán)掃描鍵盤，等待用戶輸入；根據(jù)輸入內(nèi)容確定要執(zhí)行的分支程序。根據(jù)輸入內(nèi)容確定要執(zhí)行的分支程序。lint main( ) l SequenList MyList,*L;l char cmd;l int i, t, x;l L

18、=&MyList; L-last=-1;l do l do l clrscr( );l printf(nt c, C.Create Listn);l printf(nt i, I .Insert);l printf(nt d, D.Delete);l printf(nt q, Q.QuitntYour choice:);l cmd=getchar( );l while (?);while (cmd!=d)&(cmd!=D)& (cmd!=q)&(cmd!=Q)& (cmd!=i)&(cmd!=I)& (cmd!=c)&(cmd!=

19、C);While (toupper(cmd)!=D)& (toupper(cmd)!=Q)& (toupper(cmd)!=I)&(toupper(cmd)!=C);l switch (cmd) l case c:l case C: CreateList(L); break;l case i:l case I: ? ? ? Insert(L,x,i); PrintOut(L);l getch(); break;l case d:l case D: ? ? ?l Delete(L,i); PrintOut(L);l getch(); break;l default: br

20、eak;l l while(cmd!=q) & (cmd!=Q);lprintf (nInput the data to be inserted:);scanf (%d,&x);printf (nInput the poistion to be inserted:);printf (n(1-%d)n,(L-last+2);scanf (%d,&i);printf(nInput the index_No of data to be deletedn);printf(n(1-%d):n,(L-last+1);scanf(%d,&i); while (toupper

21、(cmd)!=Q);運(yùn)算處理運(yùn)算處理l內(nèi)容：建表、插入、刪除、輸出；內(nèi)容：建表、插入、刪除、輸出；l實(shí)現(xiàn)：利用指針變量作為函數(shù)參數(shù)，傳遞實(shí)現(xiàn)：利用指針變量作為函數(shù)參數(shù)，傳遞 線性表地址；線性表地址；void CreateList (SequenList *L) int n, i, mydata; printf(nPlease input total number of data itemn); scanf(%d,&n); for(i=0;idatai=mydata; L-last=n-1; printf(nPress any key to continuen); getch( );li

22、nt Insert (SequenList *L, DataType x, int i) l int j;l if (L-last=(MaxSize-1) l printf (nOverflow!);l return Null; l else if (i(L-last+2) l printf (range error);l return Null; l else l for (j=L-last;j=i-1;j-)l L-dataj+1=L-dataj;l L-datai-1=x;l L-last=L-last+1; l return (1);lint Delete (SequenList *L

23、,int i) int j; if (iL-last+1) printf (range error); return Null; else for (j=i;jlast;j+) L-dataj-1=L-dataj; L-last-; return (1);void PrintOut(SequenList *L) int i; for (i=0;ilast;i+) printf (data%d=, i+1); printf (%dt, L-datai); if (i!=0)&(i%4)=0) printf (n); l完善程序：完善程序：l #include l #include l #

24、define Null 0l線性表初值設(shè)置：線性表初值設(shè)置：l L-last=-1;l2. 一元多項(xiàng)式的相加、相乘的程序設(shè)計(jì)一元多項(xiàng)式的相加、相乘的程序設(shè)計(jì)l數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：l typedef struct polyterm l int coef;l int exp;l struct polyterm *next;l TERM;人人機(jī)交互部分機(jī)交互部分l內(nèi)容：通過屏幕提示需要輸入的數(shù)據(jù)和程內(nèi)容：通過屏幕提示需要輸入的數(shù)據(jù)和程序執(zhí)行的結(jié)果；序執(zhí)行的結(jié)果；l要求：提示內(nèi)容清晰易讀，要求：提示內(nèi)容清晰易讀，鍵盤操作簡單準(zhǔn)確。鍵盤操作簡單準(zhǔn)確。void main() TERM *ha,*h

25、b,*hc,*p,*q,*h; printf(nInput the 1st polynomial); ha=creatpoly(); printf(nInput the 2nd polynomial); hb=creatpoly(); printf(nthe 1st polynomial is:); polyout(ha); printf(nthe 2nd polynomial is:); polyout(hb); hc=polyadd(ha,hb); printf(nthe addition of the two polynomial is:); polyout(hc); h=polymul

26、ti(ha,hb); printf(nthe multiplication of the two polynomial is:); polyout(h); return ; 運(yùn)算處理運(yùn)算處理l內(nèi)容：建表、相加、相乘、輸出；內(nèi)容：建表、相加、相乘、輸出；l實(shí)現(xiàn)：使用指針變量作為函數(shù)返回的參數(shù)，實(shí)現(xiàn)：使用指針變量作為函數(shù)返回的參數(shù)， 傳遞線性表地址；傳遞線性表地址；l條件：鏈表無頭結(jié)點(diǎn)；條件：鏈表無頭結(jié)點(diǎn)； 多項(xiàng)式系數(shù)和指數(shù)均為多項(xiàng)式系數(shù)和指數(shù)均為int型數(shù)據(jù)；型數(shù)據(jù)； 每個(gè)多項(xiàng)式數(shù)據(jù)輸入的方式為：每個(gè)多項(xiàng)式數(shù)據(jù)輸入的方式為： 系數(shù)，指數(shù)系數(shù)，指數(shù) 數(shù)據(jù)按指數(shù)遞減的順序依次輸入；數(shù)據(jù)按指數(shù)遞減的順

27、序依次輸入； 結(jié)束多項(xiàng)式數(shù)據(jù)輸入的條件是：結(jié)束多項(xiàng)式數(shù)據(jù)輸入的條件是： 0，0lTERM *creatpoly( ) l TERM *head,*r,*s;l int m,n;l head=(TERM *)malloc (sizeof(TERM);l printf(input coef and exp(1,2):n);l scanf(%d,%d,&n,&m);l r=head;l while(n) l s=(TERM *)malloc (sizeof(TERM);l s-coef=n; s-exp=m;l r-next=s; r=s;l printf(nInput coef a

28、nd exp:n);l scanf(%d,%d, &n, &m); l r-next=Null; r=head;l head=head-next; free(r);/* 無頭結(jié)點(diǎn)無頭結(jié)點(diǎn) */l return (head);llTERM *polyadd(TERM *ha,TERM *hb) l TERM *hc,*p,*q,*s,*r;l int x;l p=ha; q=hb; /* 無頭結(jié)點(diǎn)無頭結(jié)點(diǎn) */l hc=(TERM *)malloc(sizeof(TERM);l s=hc;l while(p!=Null)&(q!=Null) l if(p-exp=q-ex

29、p) l x=p-coef+q-coef;l if(x!=0) l r=(TERM *)malloc(sizeof(TERM);l r-exp=p-exp; r-coef=x;l s-next=r; s=r; l p=p-next; q=q-next; l else if (p-expexp) l r=(TERM *)malloc (sizeof(TERM);l r-coef=q-coef; r-exp=q-exp;l s-next=r; s=r;l q=q-next; l else l r=(TERM *)malloc(sizeof(TERM);l r-exp=p-exp; r-coef=p

30、-coef;l s-next=r; s=r;l p=p-next; l l while(p!=Null) l r=(TERM *)malloc(sizeof (TERM);l r-exp=p-exp; r-coef=p-coef;l s-next=r; s=r;l p=p-next; l while(q!=Null) l r=(TERM *)malloc (sizeof(TERM);l r-exp=q-exp; r-coef=q-coef;l s-next=r; s=r;l q=q-next; l s-next=Null; r=hc;l hc=hc-next; free(r);l return

31、 (hc);llTERM *polymulti(TERM *f,TERM *g) l TERM *fp,*gp,*hp,*q,*h;l int maxp,p,r,x;l maxp=f-exp+g-exp;l h=(TERM *)malloc(sizeof(TERM);l hp=h;l g=reverse(g);l for(r=maxp;r=0;r-) l x=0;l fp=f;gp=g; while(fp!=Null)&(gp!=Null) p=fp-exp+gp-exp; if(pr)fp=fp-next; else if(pnext; else x+=fp-coef*gp-coef

32、; fp=fp-next; gp=gp-next; /*end of while */l if(x!=0) l q=(TERM *)malloc(sizeof(TERM);l q-exp=r;q-coef=x;l q-next=Null;l hp-next=q; hp=q;l /* end of for */l hp=h;h=h-next;l free(hp);l return (h);llTERM* reverse(TERM *q) l TERM *p1,*p2;l if(q!=Null) l p1=q-next;l q-next=Null;l while(p1!=Null) l p2=p1

33、-next;p1-next=q;l q=p1;p1=p2;l /* end of while */l l return (q);llvoid polyout(TERM *head) l TERM *p,*q;l p=head;l while(p!=Null) l printf(%d,%d ,p-coef,p-exp);l p=p-next; l printf(n);ll3. 約瑟夫環(huán)的程序設(shè)計(jì)約瑟夫環(huán)的程序設(shè)計(jì)l數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)描述：數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)描述：l typedef struct tagnode l int num;l struct tagnode *next;l LinkList;l Lin

34、kList *head=Null,*last;人人機(jī)交互部分機(jī)交互部分l內(nèi)容：通過屏幕提示需要輸入的數(shù)據(jù)和程內(nèi)容：通過屏幕提示需要輸入的數(shù)據(jù)和程序執(zhí)行的結(jié)果；序執(zhí)行的結(jié)果；l要求：提示內(nèi)容清晰易讀，要求：提示內(nèi)容清晰易讀，鍵盤操作簡單準(zhǔn)確。鍵盤操作簡單準(zhǔn)確。lint main( ) l int n,m;l printf (nInput the total number of people:n);l scanf (%d,&n);l printf (ninput the number of person you are to call:n);l scanf (%d,&m);l he

35、ad=creat (n);l last=select (head,m);n=last-num;l printf (the last one:%dn,n);free(last);l printf (nPress any key to continue.n);l getch ( );return (1);llLinkList *creat (int n) l LinkList *head,*s, *p;l int i;l s=(LinkList *)malloc (sizeof (LinkList);l head=s;l s-num=1;p=s;l for (i=2;inum=i;l p-next

36、=s;p=s;l p-next=head;l return (head);llLinkList *select (LinkList *head, int m) l LinkList *p,*q;l int i, t, flag=0;l p=head;l t=1;l q=p; /* q-前趨指針前趨指針, p-當(dāng)前指針當(dāng)前指針 */l do l p=q-next;l t=t+1;l if(t%m=0) l printf(%4dt,p-num);l if(q-next=q) flag=1;break; l q-next=p-next;l free(p);l p=q;l else q=p;l whi

37、le(q=p)|(flag=0);l head=p;l return (head);l2021-12-855試驗(yàn)二：棧和隊(duì)列的應(yīng)用試驗(yàn)二：棧和隊(duì)列的應(yīng)用l1. “停車場管理的模擬停車場管理的模擬”部分部分l問題說明問題說明 設(shè)有一個(gè)可以設(shè)有一個(gè)可以停放停放 n 輛汽車輛汽車的狹長停車場，它只有一的狹長停車場，它只有一個(gè)大門可以供車輛進(jìn)出。個(gè)大門可以供車輛進(jìn)出。車輛按到達(dá)停車場的時(shí)間依次從停車場車輛按到達(dá)停車場的時(shí)間依次從停車場最里面向大門口處停放最里面向大門口處停放（最先到達(dá)的第一輛車放在停車場的最里（最先到達(dá)的第一輛車放在停車場的最里面）。面）。l如果停車場已放滿如果停車場已放滿 n 輛車，

38、則后到達(dá)的車輛輛車，則后到達(dá)的車輛停在門外的便道上停在門外的便道上等等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進(jìn)入停待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進(jìn)入停車場。車場。l停車場內(nèi)如果有某輛車要開走，在它之后進(jìn)入停車場的車輛都必停車場內(nèi)如果有某輛車要開走，在它之后進(jìn)入停車場的車輛都必須先退出停車場，待其開出停車場后，這些車輛再依原來的次序須先退出停車場，待其開出停車場后，這些車輛再依原來的次序進(jìn)場。進(jìn)場。l每輛車在離開停車場時(shí)，應(yīng)根據(jù)在停車場內(nèi)每輛車在離開停車場時(shí)，應(yīng)根據(jù)在停車場內(nèi)停留的時(shí)間停留的時(shí)間交納交納保管保管費(fèi)用費(fèi)用。l如果停留在如果停留在便道上的車輛便道上的車

39、輛沒有進(jìn)入停車場就要離去，則允許其離沒有進(jìn)入停車場就要離去，則允許其離去，不收停車費(fèi)，并且仍然保持在便道上等待的車輛的次序。去，不收停車費(fèi)，并且仍然保持在便道上等待的車輛的次序。2021-12-856l編制一程序模擬停車場的管理。編制一程序模擬停車場的管理。l基本要求基本要求 程序能輸出每輛車到達(dá)后的程序能輸出每輛車到達(dá)后的停車位置停車位置（停車場（停車場/便道），每輛車離開停車場時(shí)應(yīng)交納便道），每輛車離開停車場時(shí)應(yīng)交納的的費(fèi)用費(fèi)用。2021-12-857l數(shù)據(jù)結(jié)構(gòu)描述：數(shù)據(jù)結(jié)構(gòu)描述：l(1) 停車場棧：停車場棧：ltypedef struct element l int num;l int

40、arrtime;l ElemType;ltypedef struct stacktag l ElemType stackN;l int top;l STACK;2021-12-858l(2) 便道隊(duì)列：便道隊(duì)列：ltypedef struct nodetag l int num;l struct nodetag *next;l QUEUE;ltypedef struct queuetag l QUEUE *front,*rear;l LinkedQueTp;2021-12-859l人人機(jī)交互部分機(jī)交互部分l內(nèi)容：通過屏幕提示輸入數(shù)據(jù)；內(nèi)容：通過屏幕提示輸入數(shù)據(jù)；通過數(shù)據(jù)內(nèi)容實(shí)現(xiàn)功能的選擇；通過

41、數(shù)據(jù)內(nèi)容實(shí)現(xiàn)功能的選擇；l要求：提示內(nèi)容清晰易讀，要求：提示內(nèi)容清晰易讀，鍵盤操作簡單準(zhǔn)確；鍵盤操作簡單準(zhǔn)確；l實(shí)現(xiàn)：循環(huán)掃描鍵盤，等待用戶輸入；實(shí)現(xiàn)：循環(huán)掃描鍵盤，等待用戶輸入；根據(jù)輸入內(nèi)容確定要執(zhí)行的分支程序。根據(jù)輸入內(nèi)容確定要執(zhí)行的分支程序。2021-12-860lvoid main() l flag=True;l for(;) l if(flag=False)break;l l return;lint flag; printf(“?n); scanf(?); or: ch=getchar( );switch(?) if ( ) else 2021-12-861lvoid main()

42、l char ch1, ch2;l STACK *s1, *s2;l LinkedQueTp *p;l ElemType x;l int flag, t1, t2;l s1=(STACK *)malloc(sizeof(STACK);l s2=(STACK *)malloc(sizeof(STACK);l p=(LinkedQueTp *)malloc(sizeof(LinkedQueTp);l IniStack(s1); /* 初始化停車場棧初始化停車場棧 */l IniStack(s2); /* 初始化車輛規(guī)避所棧初始化車輛規(guī)避所棧 */l IniLinkedQue(p); /* 初始化便

43、道隊(duì)列初始化便道隊(duì)列 */2021-12-862lflag=True;lfor(;) l clrscr( );l printf(n輸入數(shù)據(jù)：輸入數(shù)據(jù)：A/D, 車牌號(hào)，到達(dá)時(shí)間車牌號(hào)，到達(dá)時(shí)間/離開時(shí)間離開時(shí)間n);l printf(E-退出。退出。n);l scanf(%c, %d, %d,&ch1, &t1, &t2);l x.num=t1;x.arrtime=t2;l ch2=getchar( );2021-12-863l switch(ch1) l case a:l case A: Arrive(s1, p, x);l printf(nPress any key

44、 to continue.n);l getch( );break;l case d:l case D: Delive(s1, s2, p, x);l printf(nPress any key to continue.n);l getch( );break;2021-12-864l case e:l case E: flag=False;l printf(n程序正常結(jié)束程序正常結(jié)束n);l break;l default: printf(“n選擇錯(cuò)誤，重新輸入選擇錯(cuò)誤，重新輸入n);l printf(nPress any key to continue.n);l getch( );break;

45、l if(flag=False)break;l l return;l2021-12-865l內(nèi)部處理內(nèi)部處理初始化棧初始化棧：void IniStack(STACK *s); 進(jìn)棧：進(jìn)棧： int Push(STACK *s, ElemType x); 出棧：出棧： ElemType Pop(STACK *s);初始化隊(duì)列：初始化隊(duì)列：void IniLinkedQue(LinkedQueTp *s);入隊(duì)：入隊(duì)：void EnLinkedQue(LinkedQueTp *s,int num1);出隊(duì)：出隊(duì)：int DeLinkedQue(LinkedQueTp *s);到達(dá)處理：到達(dá)處理：v

46、oid Arrive(STACK *s1, LinkedQueTp *p, ElemType x);離開處理：離開處理：void Delive(STACK *s1, STACK *s2, LinkedQueTp *p, ElemType x);2021-12-866lvoid IniStack(STACK *s) l s-top=-1;l return;llvoid IniLinkedQue(LinkedQueTp *s) l QUEUE *p1;l s-front=(QUEUE *)malloc(sizeof(QUEUE);l s-rear=s-front;l p1=s-front;l p1

47、-num=0;l p1-next=Null;l2021-12-867lvoid Arrive(STACK *s1,LinkedQueTp *p,ElemType x) l int f, no1, no2;l f=Push(s1, x); /* 入棧：車進(jìn)停車場入棧：車進(jìn)停車場 */l if (f=False) /* 停車場已滿，車停在便道停車場已滿，車停在便道 */l EnLinkedQue(p, x.num);l no1=p-front-num;l printf(第第%d號(hào)車停在便道的第號(hào)車停在便道的第%d號(hào)車位上號(hào)車位上n, x.num, no1);l else /* 顯示車在停車場的位置

48、顯示車在停車場的位置 */l no1=s1-top+1;no2=x.num;l printf(第第%d號(hào)車停在停車場的第號(hào)車停在停車場的第%d號(hào)車位上號(hào)車位上n, no2, no1);l2021-12-868lvoid Arrive(STACK *s1,LinkedQueTp *p,ElemType x) l int f;l f=Push(s1, x); /* 入棧：車進(jìn)停車場入棧：車進(jìn)停車場 */l if (f=False) /* 停車場已滿，車停在便道停車場已滿，車停在便道 */l EnLinkedQue(p, x.num);l printf(第第%d號(hào)車停在便道的第號(hào)車停在便道的第%d號(hào)

49、車位上號(hào)車位上n, x.num, p-front-num);l else /* 顯示車在停車場的位置顯示車在停車場的位置 */l printf(第第%d號(hào)車停在停車場的第號(hào)車停在停車場的第%d號(hào)車位上號(hào)車位上n, x.num, s1-top+1);l2021-12-869l離開處理：離開處理：已知：已知：車牌號(hào)，離開時(shí)間車牌號(hào)，離開時(shí)間處理：處理：從停車場棧中尋找車牌號(hào)；從停車場棧中尋找車牌號(hào)； 循環(huán)條件：循環(huán)條件： 棧不為空；棧不為空； 沒有找到?jīng)]有找到( (標(biāo)志為假標(biāo)志為假) )； 注意：注意：利用一個(gè)臨時(shí)棧保存每次出棧的結(jié)點(diǎn)元素；利用一個(gè)臨時(shí)棧保存每次出棧的結(jié)點(diǎn)元素；出車處理：出車處理：

50、 顯示停車費(fèi)用，將臨時(shí)棧結(jié)點(diǎn)數(shù)據(jù)返回到停車棧中，顯示停車費(fèi)用，將臨時(shí)棧結(jié)點(diǎn)數(shù)據(jù)返回到停車棧中， 將便道上的一輛車出隊(duì)，并將該車加入到停車棧中；將便道上的一輛車出隊(duì)，并將該車加入到停車棧中；從便道隊(duì)列中尋找車牌號(hào)；從便道隊(duì)列中尋找車牌號(hào)； 循環(huán)條件：循環(huán)條件：沒有到隊(duì)尾；沒有找到?jīng)]有到隊(duì)尾；沒有找到( (標(biāo)志為假標(biāo)志為假) )；出車處理：出車處理： 顯示車輛離開信息；顯示車輛離開信息；錯(cuò)誤處理：錯(cuò)誤處理： 在停車場棧和便道隊(duì)列中都沒有找到給定車牌號(hào)。在停車場棧和便道隊(duì)列中都沒有找到給定車牌號(hào)。2021-12-870lvoid Delive(STACK *s1, STACK *s2, Linked

51、QueTp *p, ElemType x) l int n, f=False;l ElemType y;l QUEUE *q;l while(s1-top-1) & (f!=True) l y=Pop(s1);l if(y.num!=x.num)n=Push(s2, y);l elsef=True;函數(shù)調(diào)用應(yīng)注意的問題：函數(shù)調(diào)用應(yīng)注意的問題：1. 函數(shù)的功能；函數(shù)的功能；2. 函數(shù)需要的參數(shù)；函數(shù)需要的參數(shù)；3. 函數(shù)返回結(jié)果。函數(shù)返回結(jié)果。2021-12-871l if (y.num=x.num) l printf(第第%d號(hào)車應(yīng)收費(fèi)號(hào)車應(yīng)收費(fèi)%d元元, y.num, (x.arrt

52、ime-y.arrtime)*M);l while (s2-top-1) l y=Pop(s2);f=Push(s1,y);l n=DeLinkedQue(p);l if (n!=Null) l y.num=n;y.arrtime=x.arrtime;l f=Push(s1,y);l printf(“第第%d號(hào)車停在停車場第號(hào)車停在停車場第%d號(hào)車位上號(hào)車位上l n, y.num, s1-top+1);l 2021-12-872l else l while(s2-top-1) l y=Pop(s2);f=Push(s1,y);l q=p-front;f=False;l while(f=Fals

53、e & q-next !=Null)l if(q-next-num!=x.num) q=q-next;l else l q-next=q-next-next;l p-front-num-;l if(q-next=Null) p-rear=q; /* p-front; */l printf(第第%d號(hào)車離開便道號(hào)車離開便道n, x.num);l f=True;l if(f=False)printf(輸入數(shù)據(jù)錯(cuò)誤輸入數(shù)據(jù)錯(cuò)誤,停車場和停車場和便道上均無第便道上均無第%d號(hào)車號(hào)車n,x.num);l2021-12-873int Push(STACK *s, ElemType x) int m

54、ytop; if(s-top=N-1) printf(nStack Overflow!n); return (False); else mytop=s-top;mytop+; s-stackmytop=x;s-top=mytop; return (True);2021-12-874lElemType Pop(STACK *s) l ElemType x;l int i;l if(s-toptop-;l i=s-top+1;x=s-stacki;l return x;l2021-12-875void EnLinkedQue(LinkedQueTp *s,int num1) QUEUE *p,*p

55、1; p=(QUEUE *)malloc(sizeof(QUEUE); p-num=num1;p-next=Null; p1=s-rear;p1-next=p; s-rear=p; p1=s-front; p1-num+;2021-12-876lint DeLinkedQue(LinkedQueTp *s) l QUEUE *p;l int n;l if(s-front=s-rear) return(Null);l else l p=s-front-next;l s-front-next=p-next;l if(p-next=Null)s-rear=s-front;l n=p-num;l fr

56、ee(p);l s-front-num-;l return (n);l2021-12-877l2. 迷宮問題迷宮問題l 問題說明問題說明 模擬心理學(xué)實(shí)驗(yàn)中老鼠對(duì)僅有一入模擬心理學(xué)實(shí)驗(yàn)中老鼠對(duì)僅有一入口和一個(gè)出口的迷宮找出路的過程?？诤鸵粋€(gè)出口的迷宮找出路的過程。l 基本要求基本要求 設(shè)計(jì)一程序?qū)θ我庠O(shè)定的迷宮，求設(shè)計(jì)一程序?qū)θ我庠O(shè)定的迷宮，求出一條從入口到出口的路線，或得出沒有可行通出一條從入口到出口的路線，或得出沒有可行通路的結(jié)論。路的結(jié)論。2021-12-878l2. 迷宮問題迷宮問題l 數(shù)據(jù)結(jié)構(gòu)描述：數(shù)據(jù)結(jié)構(gòu)描述：l typedef struct elem l int x, y, dir

57、;l ElemType;l typedef struct stktag l ElemType stackMAXLEN;l int top;l STACK;l typedef struct moved l int dx, dy;l MOVE;2021-12-879人人機(jī)交互部分機(jī)交互部分l內(nèi)容：通過屏幕提示需要輸入的數(shù)據(jù)和程內(nèi)容：通過屏幕提示需要輸入的數(shù)據(jù)和程序執(zhí)行的結(jié)果；序執(zhí)行的結(jié)果；l要求：提示內(nèi)容清晰易讀，要求：提示內(nèi)容清晰易讀，鍵盤操作簡單準(zhǔn)確。鍵盤操作簡單準(zhǔn)確。2021-12-880lvoid main( ) l STACK *s;l int mazeM2N2;l MOVE move8

58、;l IniMaze(maze);/* 初始化迷宮數(shù)組初始化迷宮數(shù)組 */l getch( );l s=(STACK *)malloc(sizeof(STACK);l IniStack(s);l IniMove(move);l path(maze, move, s);l draw(maze, s);l2021-12-881void IniMaze(int mazeN2) /*初始化迷宮初始化迷宮*/ int i, j, num; for(i=0, j=0; i=M+1; i+)mazeij=1; for(i=0, j=N+1; i=M+1; i+)mazeij=1; for(i=0, j=0;

59、 j=N+1; j+)mazeij=1; for(i=M+1, j=0; j=N+1; j+)mazeij=1; for(i=1; i=M; i+) for(j=1; j=N; j+) num=(800*(i+j)+1500) % 327; if (num150)&(i!=M|j!=N) mazeij=1; else mazeij=0; printf(n);2021-12-882 for(i=0; i=M+1; i+) printf(n); for(j=0; jtop=-1;llint Push(STACK *s,ElemType x) l if(s-top=MAXLEN-1)retu

60、rn (False);l else l s-stack+s-top=x;l return (True);l2021-12-885lElemType Pop(STACK *s) l ElemType elem;l if (s-toptop-;l return (s-stacks-top+1);l2021-12-886lvoid path(int maze N2, MOVE move , STACK *s) l int i, j, dir, x, y, f;l ElemType elem;l i=1;l j=1;l dir=0;l maze11=-1; /* 設(shè)設(shè)11為入口處為入口處 */l do l x=i+movedir.dx; /* 求下一步可行的到達(dá)點(diǎn)的求下一步可行的到達(dá)點(diǎn)的坐標(biāo)坐標(biāo) */l y=j+movedir.dy;2021-12-887 if(mazexy=0) elem.x=i;elem.y=j; elem.dir=dir; f=Push(