數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題

1、PAGE PAGE 85數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題 內(nèi) 容 簡(jiǎn) 介數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)的核心課，是重要的專(zhuān)業(yè)基礎(chǔ)課。實(shí)踐是學(xué)習(xí)本課程的一個(gè)重要的環(huán)節(jié)。目前各種“數(shù)據(jù)結(jié)構(gòu)”教材較為注重理論的敘述與介紹，算法描述不拘泥某種語(yǔ)言的語(yǔ)法細(xì)節(jié)，默認(rèn)讀者已具備扎實(shí)的程序設(shè)計(jì)基礎(chǔ)，可以在課下獨(dú)立完成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)。實(shí)際上在讀者群中程序設(shè)計(jì)的基礎(chǔ)并不一致，相當(dāng)一部分人基礎(chǔ)較為薄弱。多數(shù)學(xué)生反映數(shù)據(jù)結(jié)構(gòu)的上機(jī)實(shí)驗(yàn)存在一定的困難，希望有合適的實(shí)驗(yàn)參考書(shū)指導(dǎo)學(xué)習(xí)。數(shù)據(jù)結(jié)構(gòu)的理論學(xué)習(xí)也有一定的深度，存在一定的難度。學(xué)生必須完成一定數(shù)量的思考題、練習(xí)題、書(shū)面作業(yè)題，一方面鞏固基本知識(shí)、一方面提高聯(lián)系實(shí)際分析解決問(wèn)題的能力。正是基

2、于以上的原因編寫(xiě)了這本“數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題”。本參考書(shū)包括C語(yǔ)言基礎(chǔ)知識(shí)、上機(jī)實(shí)驗(yàn)習(xí)題和書(shū)面作業(yè)練習(xí)題三部分。在C語(yǔ)言基礎(chǔ)知識(shí)部分，主要介紹了輸入/輸出、函數(shù)及參數(shù)傳遞和結(jié)構(gòu)體的概念應(yīng)用。這部分內(nèi)容非常重要，掌握的是否熟練會(huì)直接影響“數(shù)據(jù)結(jié)構(gòu)“的學(xué)習(xí)。在實(shí)驗(yàn)部分，包括有完整的C語(yǔ)言源程序例題，介紹了一些設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)題目所需的C語(yǔ)言常用的知識(shí)和技巧。在實(shí)驗(yàn)題中，既有簡(jiǎn)單容易的驗(yàn)證題，即驗(yàn)證已經(jīng)給出的源程序，或者擴(kuò)充已經(jīng)給出的源程序，也有需獨(dú)立思考設(shè)計(jì)的綜合實(shí)驗(yàn)題。在習(xí)題部分，既有選擇題、判斷題，也有用圖表解答的練習(xí)題、算法設(shè)計(jì)題或綜合解答分析題。并且配有部分練習(xí)題的答案供學(xué)生自學(xué)、練習(xí)、參考。由

3、于時(shí)間倉(cāng)足、水平有限，書(shū)中難免存在錯(cuò)誤和不妥之處，敬請(qǐng)讀者指正。目 錄第一部分 C語(yǔ)言基本知識(shí)一 基本輸入和輸出1二 函數(shù)與參數(shù)傳遞3三 結(jié)構(gòu)體及運(yùn)用 5第二部分 上機(jī)實(shí)驗(yàn)習(xí)題上機(jī)實(shí)驗(yàn)要求及規(guī)范 8實(shí)習(xí)一 復(fù)數(shù)ADT及其實(shí)現(xiàn)10實(shí)習(xí)二 線性表12實(shí)習(xí)三 棧和隊(duì)列20實(shí)習(xí)四 串28實(shí)習(xí)五 數(shù)組30實(shí)習(xí)六 樹(shù)與二叉樹(shù)32實(shí)習(xí)七 圖34實(shí)習(xí)八 查找40實(shí)習(xí)九 排序42第三部分 書(shū)面作業(yè)練習(xí)題習(xí)題一 緒論48習(xí)題二 順序表示（線性表、棧和隊(duì)列）51習(xí)題三 鏈表（線性表、棧和隊(duì)列）54習(xí)題四 串57習(xí)題五 數(shù)組58習(xí)題六 樹(shù)與二叉樹(shù)60習(xí)題七 圖69習(xí)題八 查找75習(xí)題九 排序78第一部分 C語(yǔ)言基本知

4、識(shí)如何選擇描述數(shù)據(jù)結(jié)構(gòu)和算法的語(yǔ)言是十分重要的問(wèn)題。傳統(tǒng)的方法是用PASCAL語(yǔ)言，由于該語(yǔ)言語(yǔ)法規(guī)范、嚴(yán)謹(jǐn)，非常適用于數(shù)據(jù)結(jié)構(gòu)課程教學(xué)。在Windows 環(huán)境下涌現(xiàn)出一系列的功能強(qiáng)大、面向?qū)ο蟮某绦蜷_(kāi)發(fā)工具，如：Visual C+, Borland C+, Visual Basic, Visual Foxpro等。由于Visual Delphi的出現(xiàn)，使PASCAL仍不失為一種優(yōu)秀的算法描述工具。 近年來(lái)在計(jì)算機(jī)科學(xué)研究、系統(tǒng)開(kāi)發(fā)、教學(xué)以及應(yīng)用開(kāi)發(fā)中，語(yǔ)言的使用越來(lái)越廣泛。因此，本教材采用類(lèi)C語(yǔ)言進(jìn)行算法描述。按照傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)教材寫(xiě)法，只是注重算法思想和方法。并不關(guān)心具體使用何種語(yǔ)言工具來(lái)

5、實(shí)現(xiàn)，默認(rèn)學(xué)生已經(jīng)能夠具備扎實(shí)的程序設(shè)計(jì)基礎(chǔ)和能力。隨著計(jì)算機(jī)科學(xué)的發(fā)展、教學(xué)改革的深化，數(shù)據(jù)結(jié)構(gòu)的開(kāi)課時(shí)間各個(gè)高校有所不同，普遍有所提前。大學(xué)生入學(xué)起點(diǎn)就存在一定的差異，即使在大學(xué)一年級(jí)學(xué)習(xí)了某種程序設(shè)計(jì)語(yǔ)言，學(xué)生中能力和水平的差異依然存在。實(shí)踐表明在數(shù)據(jù)結(jié)構(gòu)教學(xué)過(guò)程中，如果學(xué)生的程序設(shè)計(jì)語(yǔ)言基礎(chǔ)薄弱，就會(huì)影響正常教學(xué)進(jìn)度。數(shù)據(jù)結(jié)構(gòu)不僅具有較強(qiáng)的理論性，更具有較強(qiáng)的實(shí)踐性。當(dāng)前國(guó)內(nèi)、國(guó)外一些優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)教材已經(jīng)是兼顧理論和實(shí)踐兩個(gè)方面。因此，有必要將數(shù)據(jù)結(jié)構(gòu)所必須使用的C語(yǔ)言語(yǔ)法在此做簡(jiǎn)單介紹。根據(jù)多年教學(xué)實(shí)踐，學(xué)生完成上機(jī)實(shí)驗(yàn)練習(xí)時(shí)遇到的主要問(wèn)題是，不能正確的輸入數(shù)據(jù)，結(jié)構(gòu)體概念陌生，函

6、數(shù)的傳址調(diào)用概念不清，指針與鏈表有的沒(méi)有學(xué)過(guò)。由于篇幅所限，這里僅對(duì)前三個(gè)問(wèn)題加以介紹。如果學(xué)生基礎(chǔ)好，可以越過(guò)這一部分內(nèi)容不看。一、基本輸入和輸出對(duì)于重要的數(shù)據(jù)結(jié)構(gòu)算法，均要求進(jìn)行上機(jī)實(shí)驗(yàn)。而上機(jī)實(shí)踐中離不開(kāi)數(shù)據(jù)的輸入/輸出。看起來(lái)簡(jiǎn)單的輸入/輸出，往往是上機(jī)實(shí)驗(yàn)最容易出錯(cuò)的地方，尤其是輸入。對(duì)于一個(gè)算法程序，如果數(shù)據(jù)不能正確輸入，算法設(shè)計(jì)得再好也無(wú)法正常運(yùn)行。輸入C語(yǔ)言的輸入是由系統(tǒng)提供的scanf()等函數(shù)實(shí)現(xiàn)， 在程序的首部一般要求寫(xiě)入： # include 因?yàn)闃?biāo)準(zhǔn)輸入/輸出函數(shù)都存在于頭文件 stdio.h 之中，現(xiàn)將其包含進(jìn)來(lái)方可使用這些常用的輸入/輸出函數(shù)。有的系統(tǒng)允許不使用上

7、述包含語(yǔ)句，可以直接使用標(biāo)準(zhǔn)輸入/輸出函數(shù)。函數(shù)scanf()的功能很豐富，輸入格式也是多種多樣，這是大家較為熟悉的知識(shí)，這里不做詳細(xì)介紹。在使用中需要注意以下幾個(gè)問(wèn)題。一條scanf()語(yǔ)句有多個(gè)變量、并且都是數(shù)值型（int, float, double）時(shí)，在輸入數(shù)據(jù)時(shí)應(yīng)該在一行之內(nèi)鍵入多個(gè)數(shù)據(jù)，數(shù)據(jù)之間空格分隔。例如：int n; float x;scanf (“%d %f ” , &n, &x);正確的輸入應(yīng)是：整數(shù) 空格 實(shí)數(shù) 回車(chē)。例如：100 3.14 就是在兩個(gè)數(shù)據(jù)之間使用空格鍵為分隔符，最后打回車(chē)鍵。如果語(yǔ)句中在%d 和%f 之間有一個(gè)逗號(hào)：scanf (“%d ，%f ”

8、, &n, &x);正確的輸入應(yīng)是：整數(shù) 逗號(hào) 實(shí)數(shù) 回車(chē)。例如：100，3.14 在需要字符型變量或字符串輸入時(shí)，要單獨(dú)寫(xiě)一條輸入語(yǔ)句，這樣不易出錯(cuò)。如果在同一條scanf()語(yǔ)句中將字符型和數(shù)值型混合輸入常常會(huì)出錯(cuò)。因?yàn)殒I盤(pán)輸入時(shí)在數(shù)值型數(shù)據(jù)之間空格鍵起分隔符作用，但是在字符或字符串之間，空格會(huì)被當(dāng)做一個(gè)字符，而不能起到分隔符的作用。所以將它們混在一起容易出錯(cuò)。 （3）在scanf()語(yǔ)句中變量寫(xiě)法應(yīng)該是該變量的地址，這一點(diǎn)常被忽視。請(qǐng)看下列程序：1: viod main()2: char name10, ch ;3: int num; float x;4: printf(“n 請(qǐng)輸入姓名

9、：”); scanf(“%s”, name);5: printf(“n 請(qǐng)輸入性別：”); scanf(“%c”, &ch);6: printf(“n 請(qǐng)輸入學(xué)號(hào)和成績(jī)：”); scanf(“ %d%f”, &n, &x); 為了方便說(shuō)明問(wèn)題程序中加了行號(hào)，運(yùn)行時(shí)當(dāng)然不允許行號(hào)。一般情況下在scanf()語(yǔ)句中的變量名之前要加上求地址符&，上述程序第5，6行之中就是這樣。為什么第4行的name前面不加&呢？因?yàn)閚ame代表字符串，即是一維字符數(shù)組，一維數(shù)組名本身就是一個(gè)地址，是該數(shù)組的首地址，所以name前面不加&。在本程序中把字符串、字符、數(shù)值型變量分別寫(xiě)入不同的scanf()語(yǔ)句，輸入數(shù)據(jù)

10、的具體形式如下：請(qǐng)輸入姓名：ZhangHua 請(qǐng)輸入性別：v請(qǐng)輸入學(xué)號(hào)和成績(jī)：101 90.5請(qǐng)考慮如果姓名輸入成：Zhang Hua，會(huì)出現(xiàn)什么現(xiàn)象？那樣只會(huì)讀入Zhang做姓名，而Hua被忽略，還會(huì)影響后面的輸入語(yǔ)句無(wú)法正確讀入數(shù)據(jù)。 因此，應(yīng)該充分重視數(shù)據(jù)的輸入技術(shù)。輸出C語(yǔ)言的輸出是由系統(tǒng)提供的printf()等函數(shù)來(lái)實(shí)現(xiàn)， 在程序的首部一般要求寫(xiě)入： # include 因?yàn)闃?biāo)準(zhǔn)輸入/輸出函數(shù)都存在于頭文件 stdio.h 之中，現(xiàn)將其包含進(jìn)來(lái)方可使用這些常用的輸入/輸出函數(shù)。有的系統(tǒng)允許不使用上述包含語(yǔ)句，可以直接使用標(biāo)準(zhǔn)輸入/輸出函數(shù)。輸出函數(shù)printf()的語(yǔ)法一般容易掌握，

11、這里強(qiáng)調(diào)的是怎樣合理巧妙的使用它。在連續(xù)輸出多個(gè)數(shù)據(jù)時(shí)，數(shù)據(jù)之間一定要有間隔，不能連在一起。int n=10, m=20, p=30;printf(“n %d%d%d”,n,m,p);printf(“n %6d%6d%6d”,n,m,p); /提倡使用的語(yǔ)句第一行輸出是： 102030第二行輸出是： 10 20 30在輸入語(yǔ)句scanf()之前先使用printf()輸出提示信息，但是在printf()最后不能使用換行符。int x;printf(“n x=?”); /句尾不應(yīng)使用換行符scanf( “%d”,&x); 這樣使光標(biāo)與提示信息出現(xiàn)在同一行上，光標(biāo)停在問(wèn)號(hào)后邊：X=? 。在該換行的地

12、方，要及時(shí)換行。int i;printf(“數(shù)據(jù)輸出如下：n”); / 需要換行for (i=0; i8; i+) printf(“%6d”, i ); / 幾個(gè)數(shù)據(jù)在同一行輸出，不能換行 4. 在調(diào)試程序時(shí)多加幾個(gè)輸出語(yǔ)句，以便監(jiān)視中間運(yùn)行狀況。程序調(diào)式成功后，再去掉這些輔助輸出語(yǔ)句。二、函數(shù)與參數(shù)傳遞函數(shù)的設(shè)計(jì)和調(diào)用是程序設(shè)計(jì)必不可少的技能，是程序設(shè)計(jì)最重要的基礎(chǔ)。一些初學(xué)者之之所以感到編程難，就是忽視了這個(gè)基礎(chǔ)。在傳統(tǒng)的面向過(guò)程的程序設(shè)計(jì)中，往往提倡模塊化結(jié)構(gòu)化程序設(shè)計(jì)，不論BASIC、 FONFTRAN、PASCAL還是其他高級(jí)語(yǔ)言，最終要涉及到子函數(shù)的設(shè)計(jì)和使用。C語(yǔ)言的源程序是由一

13、個(gè)主函數(shù)和若干（或零個(gè)）子函數(shù)構(gòu)成，函數(shù)是組成C語(yǔ)言程序的基本單位。函數(shù)具有相對(duì)獨(dú)立的功能，可以被其他函數(shù)調(diào)用，也可調(diào)用其他函數(shù)。當(dāng)函數(shù)直接或間接的調(diào)用自身時(shí)，這樣的函數(shù)稱(chēng)為遞歸函數(shù)。是否能夠熟練的設(shè)計(jì)和使用函數(shù)，是體現(xiàn)一個(gè)人程序設(shè)計(jì)能力高低的基本條件。因此有必要回顧和復(fù)習(xí)C語(yǔ)言函數(shù)的基本概念。1函數(shù)的設(shè)計(jì)函數(shù)設(shè)計(jì)的一般格式是： 類(lèi)型名 函數(shù)名（形參表） 函數(shù)體；函數(shù)設(shè)計(jì)一般是處理一些數(shù)據(jù)獲得某個(gè)結(jié)果，因此函數(shù)可以具有返回值，上面的類(lèi)型名就是函數(shù)返回值的類(lèi)型，可以是int, float.等。例如：float funx(形參表) 函數(shù)體；.函數(shù)也可無(wú)返回值，此時(shí)類(lèi)型是void。例如：void f

14、uny(形參表) 函數(shù)體；而函數(shù)體內(nèi)所需處理的數(shù)據(jù)往往通過(guò)形參表傳送，函數(shù)也可以不設(shè)形參表，此時(shí)寫(xiě)為：類(lèi)型名 函數(shù)名（void） 函數(shù)體；例1.2 設(shè)計(jì)一個(gè)函數(shù)計(jì)算三個(gè)整數(shù)之和，再設(shè)計(jì)一個(gè)函數(shù)僅輸出一條線。設(shè)計(jì)主函數(shù)調(diào)用兩個(gè)函數(shù)。#include int sumx (int a, int b, int c) /* 計(jì)算三個(gè)整數(shù)之和的函數(shù) */ int s; s=a+b+c; return s; void display(void) /* 輸出一條線的函數(shù) */ printf(”n“); void main( ) int x,y, z ,sa;x=y=z=2;display(); /* 畫(huà)一條線

15、 */printf(“n sum=%d”,sumx(x,y,z); /* 在輸出語(yǔ)句中直接調(diào)用函數(shù)sumx( ) */printf(“n %6d%6d%6d”,x,y,z);display(); x=5; y=6; z=7;sa=sumx(x, y, z); /* 在賦值語(yǔ)句中調(diào)用函數(shù)sumx( ) */printf(“n “ sum=%d”,sa);printf(“n %6d%6d%6d”,x,y,z); display(); /* 程序結(jié)束 */ 運(yùn)行結(jié)果：sum= 6 2 2 2 sum=48 15 16 172. 關(guān)于函數(shù)的參數(shù)傳遞 函數(shù)在被調(diào)用時(shí)，由主調(diào)程序提供實(shí)參，將信息傳遞給形參

16、。在調(diào)用結(jié)束后，有時(shí)形參可以返回新的數(shù)據(jù)給主調(diào)程序。這就是所謂參數(shù)傳遞。各種算法語(yǔ)言實(shí)現(xiàn)參數(shù)傳遞的方法通常分為傳值和傳址兩大類(lèi)。 在上例中函數(shù)sumx()的設(shè)計(jì)和主函數(shù)對(duì)它的調(diào)用，就是傳值調(diào)用。第一、第二次調(diào)用，帶入的實(shí)參均是三個(gè)整型變量。調(diào)用函數(shù)返回后，在主程序中輸出實(shí)參的值仍與調(diào)用之前相同。傳值調(diào)用的主要特點(diǎn)是數(shù)據(jù)的單向傳遞，由實(shí)參通過(guò)形參將數(shù)據(jù)代入被調(diào)用函數(shù)，不論在調(diào)用期間形參值是否改變，調(diào)用結(jié)束返回主調(diào)函數(shù)之后，實(shí)參值都不會(huì)改變。 在不同的算法語(yǔ)言中，傳址調(diào)用的語(yǔ)法有所不同。在PASCAL語(yǔ)言中用變參實(shí)現(xiàn)傳址。在C語(yǔ)言中采用指針變量做形參來(lái)實(shí)現(xiàn)傳址。傳址調(diào)用的主要特點(diǎn)是可以實(shí)現(xiàn)數(shù)據(jù)雙向

17、傳遞，在調(diào)用時(shí)實(shí)參將地址傳給形參，該地址中的數(shù)據(jù)代入被調(diào)用函數(shù)。如果在調(diào)用期間形參值被改變，也即該地址中的數(shù)據(jù)發(fā)生變化，調(diào)用結(jié)束返回主調(diào)函數(shù)之后，實(shí)參地址仍然不變，但是該地址中的數(shù)據(jù)發(fā)生相應(yīng)改變。這就是數(shù)據(jù)的雙向傳遞?，F(xiàn)看一例題：例1.3 設(shè)計(jì)一個(gè)函數(shù)實(shí)現(xiàn)兩個(gè)數(shù)據(jù)的交換，在主程序中調(diào)用。#include viod swap( int *a, int *b) ； /* 函數(shù)原型聲明 */void main( ) int x=100, y=800;printf(“n %6d%6d”, x, y); /* 輸出原始數(shù)據(jù) */ swap(&x, &y); /* 調(diào)用交換數(shù)據(jù)的函數(shù)swap() */ p

18、rintf(“n %6d%6d”, x ,y); /* 輸出交換后的數(shù)據(jù) */ viod swap( int *a, int *b) int c; c=*a; *a = *b; *b=c; 運(yùn)行結(jié)果：800 800 100實(shí)踐證明x,y 的數(shù)據(jù)在調(diào)用函數(shù)前后發(fā)生了交換變化。形參是指向整形的指針變量a和b，在函數(shù)體內(nèi)需要交換的是指針?biāo)傅拇鎯?chǔ)單元的內(nèi)容，因此使用*a = *b;這樣的寫(xiě)法。在調(diào)用時(shí)，要求實(shí)參個(gè)數(shù)、類(lèi)型位置與形參一致。因?yàn)閷?shí)參應(yīng)該是指針地址，所以調(diào)用語(yǔ)句swap(&x, &y)中，實(shí)參&x,和& y代入的是整型變量x,y的地址。在函數(shù)體內(nèi)交換的是實(shí)參地址中的內(nèi)容，而作為主函數(shù)變量x

19、,y的地址仍然沒(méi)有改變。從整數(shù)交換的角度看，本例題實(shí)現(xiàn)了雙向數(shù)據(jù)傳遞。若從指針地址角度看，調(diào)用前后指針地址不變?，F(xiàn)在回過(guò)頭來(lái)看P5頁(yè)復(fù)數(shù)ADT實(shí)現(xiàn)的面向過(guò)程C語(yǔ)言源程序的創(chuàng)建復(fù)數(shù)的函數(shù)：void creat(complex *c) .; c-x=x1; c-y=y1;在函數(shù)體中人們?nèi)菀渍J(rèn)識(shí)和習(xí)慣的寫(xiě)法c.x和c.y，也必須寫(xiě)成c-x和c-y。在調(diào)用該函數(shù)時(shí)，還必須將結(jié)構(gòu)體變量a求地址做實(shí)參：creat(&a)。初學(xué)者應(yīng)該特別注意這一點(diǎn)。 如果需要在函數(shù)體中改變指針的地址，這就需要在原指針基礎(chǔ)之上再加一級(jí)指針：void funz( int *a) /* 改變*a */ 函數(shù)調(diào)用返回后*a仍然不變

20、，而*a發(fā)生了變化。由此可以看出C語(yǔ)言的傳址調(diào)用比較復(fù)雜。不如PASCAL的變量參數(shù)簡(jiǎn)便，也不如C+的引用調(diào)用方便。三、 結(jié)構(gòu)體及運(yùn)用數(shù)據(jù)結(jié)構(gòu)課程所研究的問(wèn)題均運(yùn)用到“結(jié)構(gòu)體”。在C語(yǔ)言中結(jié)構(gòu)體的定義、輸入/輸出是數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)的重要語(yǔ)法基礎(chǔ)。定義結(jié)構(gòu)體的一般格式：struct 結(jié)構(gòu)體類(lèi)型名 類(lèi)型名1 變量名1； /數(shù)據(jù)子域類(lèi)型名2 變量名2；類(lèi)型名n 變量名n；其中struct是保留字。結(jié)構(gòu)體類(lèi)型名由用戶自己命名。在使用時(shí)必須聲明一個(gè)具體的結(jié)構(gòu)體類(lèi)型的變量，聲明創(chuàng)建一個(gè)結(jié)構(gòu)體變量的方法是：struct 結(jié)構(gòu)體類(lèi)型名 結(jié)構(gòu)體變量名；例如： struct ElemType /* 定義結(jié)構(gòu)體 *

21、/ int num; char name10; ;struct ElemType x； /* 聲明結(jié)構(gòu)體變量x */另外有一種方法使用typedef 語(yǔ)句定義結(jié)構(gòu)體，在聲明結(jié)構(gòu)體變量時(shí)可以不寫(xiě)struct，使得書(shū)寫(xiě)更加簡(jiǎn)便。例如： typedef struct int num; char name10; ElemType；ElemType就是一個(gè)新的類(lèi)型名，并且是結(jié)構(gòu)體類(lèi)型名。聲明變量x的語(yǔ)句是： ElemType x;一個(gè)結(jié)構(gòu)體中可以包含多個(gè)數(shù)據(jù)子域。數(shù)據(jù)子域的類(lèi)型名一般指基本數(shù)據(jù)類(lèi)型（int char 等），也可是已經(jīng)定義的另一結(jié)構(gòu)體名。數(shù)據(jù)子域變量名可以是簡(jiǎn)單變量，也可以是數(shù)組。它們也可

22、以稱(chēng)為結(jié)構(gòu)體的數(shù)據(jù)成員。通過(guò)“結(jié)構(gòu)體變量名.數(shù)據(jù)子域” 可以訪問(wèn)數(shù)據(jù)子域。例1.6 設(shè)計(jì)Student結(jié)構(gòu)體，在主程序中運(yùn)用。#include #include typedef struct /* 定義結(jié)構(gòu)體Student */ long num; /* 學(xué)號(hào) */ int x; /* 成績(jī) */ char name10; /* 姓名 */ Student;void main( ) Student s1; /* 聲明創(chuàng)建一個(gè)結(jié)構(gòu)體變量s1 */s1.num=1001 ; /* 為s1的數(shù)據(jù)子域提供數(shù)據(jù) */s1. x=83; strcpy( , “ 李 明”)； printf(

23、“n 姓名： %s”, ); /* 輸出結(jié)構(gòu)體變量s1 的內(nèi)容 */printf( “n 學(xué)號(hào)： %d”, s1.num);printf( “n 成績(jī)： %d”, s1.x); 或者使用鍵盤(pán)輸入: scanf(“%d”, s1.num);scanf(“%d”, s1.x);scanf(“%s”, ); 還可以通過(guò)“結(jié)構(gòu)體指針-數(shù)據(jù)子域” 來(lái)訪問(wèn)數(shù)據(jù)域。在實(shí)際問(wèn)題中還會(huì)使用到指向結(jié)構(gòu)體的指針，通過(guò)以下語(yǔ)句段可以說(shuō)明結(jié)構(gòu)體指針的一般用法。 Student *p; /* 聲明指針變量p */p=( Student *)malloc(sizeof( Student); /*

24、 分配存儲(chǔ)單元，首地址賦給p指針 */ p-num=101; p-x=83; strcpy( p-name, “李 明 ”); printf(“n %10s%6d%6d”,p-name,p-num,p-x);設(shè)計(jì)一個(gè)一維數(shù)組，每個(gè)數(shù)組元素是Student結(jié)構(gòu)體類(lèi)型，通過(guò)以下語(yǔ)句段可以說(shuō)明結(jié)構(gòu)體數(shù)組的一般用法?？梢酝ㄟ^(guò)“結(jié)構(gòu)體數(shù)組名下標(biāo).數(shù)據(jù)子域”訪問(wèn)數(shù)據(jù)域。 Student a5; /* 聲明創(chuàng)建一個(gè)結(jié)構(gòu)體數(shù)組a */ int i ;for( i=0, i5, i+) printf(“n 學(xué)號(hào)：%d”,ai.num) ; printf(“n 姓名：%s”,) ；printf(“n

25、 成績(jī)：%d”,ai.x) ; 以上是關(guān)于結(jié)構(gòu)體的基本概念和簡(jiǎn)單運(yùn)用。第二部分 上機(jī)實(shí)驗(yàn)習(xí)題上機(jī)實(shí)驗(yàn)要求及規(guī)范數(shù)據(jù)結(jié)構(gòu)課程具有比較強(qiáng)的理論性，同時(shí)也具有較強(qiáng)的可應(yīng)用性和實(shí)踐性。在上機(jī)實(shí)驗(yàn)是一個(gè)重要的教學(xué)環(huán)節(jié)。一般情況下學(xué)生能夠重視實(shí)驗(yàn)環(huán)節(jié)，對(duì)于編寫(xiě)程序上機(jī)練習(xí)具有一定的積極性。但是容易忽略實(shí)驗(yàn)的總結(jié)，忽略實(shí)驗(yàn)報(bào)告的撰寫(xiě)。對(duì)于一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書(shū)面表達(dá)能力。需要逐步培養(yǎng)書(shū)寫(xiě)科學(xué)實(shí)驗(yàn)報(bào)告以及科技論文的能力。拿到一個(gè)題目，一般不要急于編程。按照面向過(guò)程的程序設(shè)計(jì)思路（關(guān)于面向?qū)ο蟮挠?xùn)練將在其它后繼課程中進(jìn)行），正確的方法是：首先理解問(wèn)題，明確給定的條件和要求解決的問(wèn)題，然后按照自頂

26、向下，逐步求精，分而治之的策略，逐一地解決子問(wèn)題。具體實(shí)習(xí)步驟如下：1.問(wèn)題分析與系統(tǒng)結(jié)構(gòu)設(shè)計(jì)充分地分析和理解問(wèn)題本身，弄清要求做什么（而不是怎么做），限制條件是什么。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，搞清數(shù)據(jù)的邏輯結(jié)構(gòu)（是線性表還是樹(shù)、圖？），確定數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（是順序結(jié)構(gòu)還是鏈表結(jié)構(gòu)？）。然后設(shè)計(jì)有關(guān)操作的函數(shù)。在每個(gè)函數(shù)模塊中，要綜合考慮系統(tǒng)功能，使系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試。最后寫(xiě)出每個(gè)模塊的算法頭和規(guī)格說(shuō)明，列出模塊之間的調(diào)用關(guān)系（可以用圖表示），便完成了系統(tǒng)結(jié)構(gòu)設(shè)計(jì)。2.詳細(xì)設(shè)計(jì)和編碼詳細(xì)設(shè)計(jì)是對(duì)函數(shù)（模塊）的進(jìn)一步求精，用偽高級(jí)語(yǔ)言（如類(lèi)C語(yǔ)言）或自然語(yǔ)言寫(xiě)出算法框架，

27、這時(shí)不必確定很多結(jié)構(gòu)和變量。編碼，即程序設(shè)計(jì)，是對(duì)詳細(xì)設(shè)計(jì)結(jié)果的進(jìn)一步求精，即用某種高級(jí)語(yǔ)言（如C/C+語(yǔ)言）表達(dá)出來(lái)。盡量多設(shè)一些注釋語(yǔ)句，清晰易懂。盡量臨時(shí)增加一些輸出語(yǔ)句，便于差錯(cuò)矯正，在程序成功后再刪去它們。3.上機(jī)準(zhǔn)備熟悉高級(jí)語(yǔ)言用法，如C語(yǔ)言。熟悉機(jī)器（即操作系統(tǒng)），基本的常用命令。靜態(tài)檢查主要有兩條路徑，一是用一組測(cè)試數(shù)據(jù)手工執(zhí)行程序（或分模塊進(jìn)行）；二是通過(guò)閱讀或給別人講解自己的程序而深入全面地理解程序邏輯，在這個(gè)過(guò)程中再加入一些注釋和斷言。如果程序中邏輯概念清楚，后者將比前者有效。4.上機(jī)調(diào)試程序調(diào)試最好分塊進(jìn)行，自底向上，即先調(diào)試底層函數(shù)，必要時(shí)可以另寫(xiě)一個(gè)調(diào)用驅(qū)動(dòng)程序，表

28、面上的麻煩工作可以大大降低調(diào)試時(shí)所面臨的復(fù)雜性，提高工作效率。5.整理實(shí)習(xí)報(bào)告 在上機(jī)實(shí)開(kāi)始之前要充分準(zhǔn)備實(shí)驗(yàn)數(shù)據(jù)，在上機(jī)實(shí)踐過(guò)程中要及時(shí)記錄實(shí)驗(yàn)數(shù)據(jù)，在上機(jī)實(shí)踐完成之后必須及時(shí)總結(jié)分析。寫(xiě)出實(shí)驗(yàn)報(bào)告。一、實(shí)驗(yàn)報(bào)告的基本要求： 一般性、較小規(guī)模的上機(jī)實(shí)驗(yàn)題，必須遵循下列要求。養(yǎng)成良好的習(xí)慣。姓名 班級(jí) 學(xué)號(hào) 日期題目：內(nèi)容敘述程序清單（帶有必要的注釋?zhuān)┱{(diào)試報(bào)告：實(shí)驗(yàn)者必須重視這一環(huán)節(jié)，否則等同于沒(méi)有完成實(shí)驗(yàn)任務(wù)。這里可以體現(xiàn)個(gè)人特色、或創(chuàng)造性思維。具體內(nèi)容包括：測(cè)試數(shù)據(jù)與運(yùn)行記錄；調(diào)試中遇到的主要問(wèn)題，自己是如何解決的；經(jīng)驗(yàn)和體會(huì)等。二、實(shí)驗(yàn)習(xí)報(bào)告的提高要求：階段性、較大規(guī)模的上機(jī)實(shí)驗(yàn)題，應(yīng)該

29、遵循下列要求。養(yǎng)成科學(xué)的習(xí)慣。需求和規(guī)格說(shuō)明描述問(wèn)題，簡(jiǎn)述題目要解決的問(wèn)題是什么。規(guī)定軟件做什么。原題條件不足時(shí)補(bǔ)全。設(shè)計(jì)設(shè)計(jì)思想：存儲(chǔ)結(jié)構(gòu)（題目中限定的要描述）；主要算法基本思想。設(shè)計(jì)表示：每個(gè)函數(shù)的頭和規(guī)格說(shuō)明；列出每個(gè)函數(shù)所調(diào)用和被調(diào)用的函數(shù)，也可以通過(guò)調(diào)用關(guān)系圖表達(dá)。實(shí)現(xiàn)注釋?zhuān)焊黜?xiàng)功能的實(shí)現(xiàn)程度、在完成基本要求的基礎(chǔ)上還有什么功能。用戶手冊(cè)：即使用說(shuō)明。調(diào)試報(bào)告：調(diào)試過(guò)程中遇到的主要問(wèn)題是如何解決的；設(shè)計(jì)的回顧、討論和分析；時(shí)間復(fù)雜度、空間復(fù)雜度分析；改進(jìn)設(shè)想；經(jīng)驗(yàn)和體會(huì)等。實(shí)習(xí)一 復(fù)數(shù)ADT及其實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?. 了解抽象數(shù)據(jù)類(lèi)型（ADT）的基本概念，及描述方法。 2. 通過(guò)對(duì)復(fù)數(shù)

30、抽象數(shù)據(jù)類(lèi)型ADT的實(shí)現(xiàn)，熟悉C語(yǔ)言語(yǔ)法及程序設(shè)計(jì)。為以后章節(jié)的學(xué)習(xí)打下基礎(chǔ)。二、實(shí)例 復(fù)數(shù)抽象數(shù)據(jù)類(lèi)型ADT的描述及實(shí)現(xiàn)。 復(fù)數(shù)ADT的描述 ADT complex 數(shù)據(jù)對(duì)象：D= c1,c2 c1,c2FloatSet 數(shù)據(jù)關(guān)系：R= c1 c2 基本操作：創(chuàng)建一個(gè)復(fù)數(shù) creat(a); 輸出一個(gè)復(fù)數(shù) outputc(a); 求兩個(gè)復(fù)數(shù)相加之和 add(a,b); 求兩個(gè)復(fù)數(shù)相減之差 sub(a,b); 求兩個(gè)復(fù)數(shù)相乘之積 chengji(a,b); 等等; ADT complex; 復(fù)數(shù)ADT實(shí)現(xiàn)的源程序#include #include /* 存儲(chǔ)表示，結(jié)構(gòu)體類(lèi)型的定義 */type

31、def struct float x; /* 實(shí)部子域 */ float y; /* 虛部的實(shí)系數(shù)子域 */ comp;/* 全局變量的說(shuō)明 */comp a,b,a1,b1;int z;/* 子函數(shù)的原型聲明 */void creat(comp *c);void outputc(comp a);comp add(comp k,comp h);/* 主函數(shù) */main() creat(&a); outputc(a); creat(&b); outputc(b); a1=add(a,b); outputc(a1); /* maijn */* 創(chuàng)建一個(gè)復(fù)數(shù) */void creat(comp *

32、c) float c1,c2; printf(輸入實(shí)部real x=?);scanf(%f,&c1); printf(輸入虛部xvpu y=?);scanf(%f,&c2); (*c).x=c1; c -y=c2; /* creat */* 輸出一個(gè)復(fù)數(shù) */void outputc(comp a) printf(n %f+%f i nn,a.x,a.y); /* 求兩個(gè)復(fù)數(shù)相加之和 */comp add(comp k,comp h) comp l; l.x=k.x+h.x; l.y=k.y+h.y; return(l); /* add */三、實(shí)習(xí)題首先將上面源程序輸入計(jì)算機(jī)，進(jìn)行調(diào)試。運(yùn)行

33、程序，輸入下列兩個(gè)復(fù)數(shù)的實(shí)部域虛部，記錄兩個(gè)復(fù)數(shù)相加的輸出結(jié)果。 原始數(shù)據(jù)：2.0 + 3.5i ，3.0 6.3i 然后在上面程序的基礎(chǔ)上，增加自行設(shè)計(jì)的復(fù)數(shù)減、復(fù)數(shù)乘的兩個(gè)子函數(shù)，適當(dāng)補(bǔ)充必需的語(yǔ)句（例如函數(shù)原型聲明、主函數(shù)中的調(diào)用等）。提示：/ 求兩個(gè)復(fù)數(shù)相減之差的函數(shù) comp sub(comp k,comp h) / 求兩個(gè)復(fù)數(shù)相乘之積的函數(shù) comp chengji(comp k,comp h) 再次調(diào)試運(yùn)行程序。輸入數(shù)據(jù)，記錄結(jié)果，最后完成實(shí)驗(yàn)報(bào)告。實(shí)習(xí)二 線性表一、實(shí)驗(yàn)?zāi)康?. 了解線性表的邏輯結(jié)構(gòu)特性，以及這種特性在計(jì)算機(jī)內(nèi)的兩種存儲(chǔ)結(jié)構(gòu)。 2. 重點(diǎn)是線性表的基本操作在兩種

34、存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；其中以鏈表的操作為側(cè)重點(diǎn)；并進(jìn)一步學(xué)習(xí)結(jié)構(gòu)化的程序設(shè)計(jì)方法。二、實(shí)例 1. 線性表的順序存儲(chǔ)表示（結(jié)構(gòu)）及實(shí)現(xiàn)。閱讀下列程序請(qǐng)注意幾個(gè)問(wèn)題：（1）關(guān)于線性表的順序存儲(chǔ)結(jié)構(gòu)的本質(zhì)是：在邏輯上相鄰的兩個(gè)數(shù)據(jù)元素ai-1, ai，在存儲(chǔ)地址中也是相鄰的,既地址連續(xù)。不同的教材有不同的表示，有的直接采用一維數(shù)組，這種方法有些過(guò)時(shí)。有的采用含動(dòng)態(tài)分配一維數(shù)組的結(jié)構(gòu)體，這種方法過(guò)于靈活抽象（對(duì)讀者要求過(guò)高）。我們采用的是含靜態(tài)一維數(shù)組和線性表長(zhǎng)的結(jié)構(gòu)體： typedef struct ElemType aMAXSIZE; /* 一維數(shù)組 子域 */ int length; /* 表長(zhǎng)度子

35、域 */ SqList; /* 順序存儲(chǔ)的結(jié)構(gòu)體類(lèi)型 */ （2）本程序是一個(gè)完整的、子函數(shù)較多的源程序。目的為學(xué)生提供一個(gè)示范，提供順序存儲(chǔ)表示的資料，供學(xué)生參考。比如，主函數(shù)中簡(jiǎn)單“菜單設(shè)計(jì)”(do-while循環(huán)內(nèi)嵌套一個(gè) switch結(jié)構(gòu))技術(shù)。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的初級(jí)階段，并不強(qiáng)要求學(xué)生一定使用“菜單設(shè)計(jì)”技術(shù)，同學(xué)們可以在main()函數(shù)中直接寫(xiě)幾個(gè)簡(jiǎn)單的調(diào)用語(yǔ)句，就象前面的復(fù)數(shù)處理程序中的main()一樣。但是隨著學(xué)習(xí)的深入，盡早學(xué)會(huì)使用“菜單設(shè)計(jì)”技術(shù)，會(huì)明顯提高編程和運(yùn)行效率。 源程序#include #include #define MAXSIZE 20 /* 數(shù)組最大界限 *

36、/typedef int ElemType; /* 數(shù)據(jù)元素類(lèi)型 */typedef struct ElemType aMAXSIZE; /* 一維數(shù)組 子域 */ int length; /* 表長(zhǎng)度子域 */ SqList; /* 順序存儲(chǔ)的結(jié)構(gòu)體類(lèi)型 */SqList a,b,c;/* 函數(shù)聲明 */void creat_list(SqList *L);void out_list(SqList L);void insert_sq(SqList *L,int i,ElemType e);ElemType delete_sq(SqList *L,int i);int locat_sq(SqL

37、ist L,ElemType e);/* 主函數(shù) */main() int i,k,loc; ElemType e,x; char ch; do printf(nnn); printf(n 1. 建立線性表 ); printf(n 2. 在i位置插入元素e); printf(n 3. 刪除第i個(gè)元素，返回其值); printf(n 4. 查找值為 e 的元素); printf(n 6. 結(jié)束程序運(yùn)行); printf(n=); printf(n 請(qǐng)輸入您的選擇（1，2，3，4，6）); scanf(%d,&k); switch(k) case 1: creat_list(&a); out_li

38、st(a); break; case 2: printf(n i,e=?); scanf(%d,%d,&i,&e); insert_sq(&a,i,e); out_list(a); break; case 3: printf(n i=?); scanf(%d,&i); x=delete_sq(&a,i); out_list(a); printf(n x=%d,x); break; case 4: printf(n e=?); scanf(%d,&e); loc=locat_sq(a,e); if (loc=-1) printf(n 未找到 %d,loc); else printf(n 已找到，

39、元素位置是 %d,loc); break; /* switch */ while(k!=6); printf(n 再見(jiàn)！); printf(“n 打回車(chē)鍵，返回?！?; ch=getch(); /* main */* 建立線性表 */void creat_list(SqList *L) int i; printf(n n=?); scanf(%d,&L-length); for(i=0;ilength;i+) printf(n data %d=?,i); scanf(%d,&(L-ai); /* creat_list */* 輸出線性表 */void out_list(SqList L) in

40、t i; char ch; printf(n); for(i=0;ilength=MAXSIZE) printf(n overflow !); else if(iL-length+1) printf(n erroe i !); else for(j=L-length-1; ji-1; j-) L-aj+1=L-aj; /* 向后移動(dòng)數(shù)據(jù)元素 */ L-ai-1=e; /* 插入元素 */ L-length+; /* 線性表長(zhǎng)加1 */ /* insert_sq */* 刪除第i個(gè)元素，返回其值 */ElemType delete_sq(SqList *L, int i) ElemType x;

41、 int j; if( L-length=0) printf(n 是空表。underflow !); else if(i L-length) printf(n error i !); x=-1; else x=L-ai-1; for(j=i; jlength-1; j+) L-aj-1=L-aj; L-length-; return(x); /* delete_sq */* 查找值為 e 的元素，返回它的位置 */int locat_sq(SqList L, ElemType e) int i=0; while(i=L.length-1 & L.ai!=e) i+; if(i=L.length

42、-1) return(i+1); else return(-1); /* locat_sq */ 2. 線性表的鏈表存儲(chǔ)表示（結(jié)構(gòu)）及實(shí)現(xiàn)。 閱讀下列程序請(qǐng)注意幾個(gè)問(wèn)題：（1）關(guān)于線性表的鏈表存儲(chǔ)結(jié)構(gòu)的本質(zhì)是：在邏輯上相鄰的兩個(gè)數(shù)據(jù)元素ai-1, ai，在存儲(chǔ)地址中可以不相鄰,既地址不連續(xù)。不同的教材的表示基本是一致的。 typedef struct LNode ElemType data; /* 數(shù)據(jù)子域 */ struct LNode *next; /* 指針子域 */ LNode; /* 結(jié)點(diǎn)結(jié)構(gòu)類(lèi)型 */ （2）本程序是一個(gè)完整的、子函數(shù)較多的源程序。目的為學(xué)生提供一個(gè)示范，提供關(guān)于鏈

43、表操作的資料，供學(xué)生參考?？梢钥吹奖境绦虻膍ain()與前一程序的main()函數(shù)的結(jié)構(gòu)十分相似。稍加改動(dòng)還可為其他題目的源程序所用。 源程序#include #include #include typedef int ElemType;typedef struct LNode ElemType data; /* 數(shù)據(jù)子域 */ struct LNode *next; /* 指針子域 */ LNode; /* 結(jié)點(diǎn)結(jié)構(gòu)類(lèi)型 */LNode *L; /* 函數(shù)聲明 */LNode *creat_L();void out_L(LNode *L);void insert_L(LNode *L,int

44、 i ,ElemType e);ElemType delete_L(LNode *L,int i);int locat_L(LNode *L,ElemType e);/* 主函數(shù) */main() int i,k,loc; ElemType e,x; char ch;do printf(nnn); printf(nn 1. 建立線性鏈表 ); printf(nn 2. 在i位置插入元素e); printf(nn 3. 刪除第i個(gè)元素，返回其值); printf(nn 4. 查找值為 e 的元素); printf(nn 5. 結(jié)束程序運(yùn)行); printf(n=); printf(n 請(qǐng)輸入您的

45、選擇 (1,2,3,4,5); scanf(%d,&k); switch(k) case 1: L=creat_L( ); out_L(L); break; case 2: printf(n i,e=?); scanf(%d,%d,&i,&e); insert_L(L,i,e); out_L(L); break; case 3: printf(n i=?); scanf(%d,&i); x=delete_L(L,i); out_L(L); if(x!=-1) printf(n x=%dn,x); break; case 4: printf(n e=?); scanf(%d,&e); loc=l

46、ocat_L(L,e); if (loc=-1) printf(n 未找到 %d,loc); else printf(n 已找到，元素位置是 %d,loc); break; /* switch */ printf(n ); while(k=1 & knext=NULL; p=h; printf(n data=?); scanf(%d,&x); /* 輸入第一個(gè)數(shù)據(jù)元素 */ while( x!=-111) /* 輸入-111，結(jié)束循環(huán) */ s=(LNode *)malloc(sizeof(LNode); /* 分配新結(jié)點(diǎn) */ s-data=x; s-next=NULL; p-next=s;

47、 p=s; printf(data=?( -111 end) ); scanf(%d,&x); /* 輸入下一個(gè)數(shù)據(jù)*/11h2233建成后的鏈表h return(h); /* creat_L */* 輸出單鏈表中的數(shù)據(jù)元素*/void out_L(LNode *L) LNode *p; char ch; p=L-next; printf(nn); while(p!=NULL) printf(%5d,p-data); p=p-next; ; printf(nn 打回車(chē)鍵，繼續(xù)?！?; ch=getch(); /* out_link */* 在i位置插入元素e */void insert_L(L

48、Node *L,int i, ElemType e) LNode *s,*p,*q; int j; p=L; /* 找第i-1個(gè)結(jié)點(diǎn) */ j=0; while(p!=NULL & jnext; j+; if(p=NULL | ji-1) printf(n i ERROR !); else s=(LNode *)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; /* insert_L */* 刪除第i個(gè)元素，返回其值 */ElemType delete_L(LNode *L,int i) LNode *p,*q; int j; E

49、lemType x; p=L; j=0; while(p-next!=NULL & jnext; j+; if(p-next=NULL) printf(n i ERROR !); return(-1); else q=p-next; x=q-data; p-next=q-next; free(q); return(x); /* delete_L */ /* 查找值為 e 的元素, 返回它的位置 */ int locat_L(LNode *L,ElemType e) LNode *p; int j=1; p=L-next; while(p!=NULL & p-data!=e) p=p-next;

50、 j+; if(p!=NULL)return(j); else return(-1); /* locat_L */3.約瑟夫問(wèn)題的一種描述：編號(hào)為1，2，n的n個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)。方法1報(bào)m的人出列（將其刪除），從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開(kāi)始重新從一報(bào)數(shù)，如此下去，直到所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。要求利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序打印出各人的編號(hào)和此人密碼。方法2. 報(bào)m的人出列（將其刪除），將他的密碼作為新的m值，從他在順時(shí)針?lè)较蛏系?/p>

51、下一個(gè)人開(kāi)始重新從一報(bào)數(shù)，如此下去，直到所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。要求利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序打印出各人的編號(hào)和此人密碼。 方法1的程序清單 #include #include typedef struct node /* 結(jié)點(diǎn)的結(jié)構(gòu)定義 */ int num; /* 編號(hào)子域 */ int sm; /* 密碼子域 */ struct node *next; /* 指針域 */ JOS;/* 函數(shù)聲明 */JOS *creat();void outs(JOS *h, int m);/* 主函數(shù) */main() int m; JOS *h; h=

52、creat(); printf(“n enter the begin secret code, m=（m1）”); scanf(“%d”,&m); outs(h, m); /* main */* 生成約瑟夫環(huán) */hJOS *creat() int i=0, mi; JOS *new, *pre, *h; h=(JOS *)malloc(sizeof(JOS); /* 為頭結(jié)點(diǎn)申請(qǐng)空間 */ h-link=h; /* 頭結(jié)點(diǎn)h形成環(huán) */ pre=h; printf(“n 個(gè)人密碼 =?”); scanf(“%d”,&mi); while( mi != -111) /* 密碼為-111，結(jié)束循

53、環(huán) */ new=(JOS *)malloc(sizeof(JOS); /* 申請(qǐng)數(shù)據(jù)元素結(jié)點(diǎn)空間 */ i+; new-num=i; new-sm=mi; /* 結(jié)點(diǎn)送值 */ new-link=h; pre-link=new; pre=new; /* 形成循環(huán)鏈表 */ printf(“n 個(gè)人密碼 =?”); scanf(“%d”,&mi); /* 讀入下一個(gè)密碼 */ /* while */ pre-link= h-link; free(h); /* 刪除頭結(jié)點(diǎn)h */ h=pre-link; return(h); /* 頭指針指向第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn) */ /* JOS *creat

54、, 該約瑟夫環(huán)無(wú)附加頭結(jié)點(diǎn) */* 按m被叫出列的順序，輸出結(jié)點(diǎn)信息 */void outs(JOS *h, int m) int i; JOS *q=h, p; printf(“n “); while (q-link!=q) for(i=1;ilink; /* 報(bào)數(shù)到第m個(gè)人 */ printf(“%6d %6d ”,q-num,q-sm); /* 輸出第m個(gè)人的編號(hào)和密碼 */ p-link=q-link; free(q); /* 第m個(gè)人出列 */ q=p-link; printf(“%6d %6d n”,q-num,q-sm); /* 輸出最后一個(gè)結(jié)點(diǎn)的編號(hào)值 */ free(q);

55、/* outs */本程序用了不帶頭結(jié)點(diǎn)的循環(huán)鏈表，也可以加上頭結(jié)點(diǎn)，對(duì)于本題有頭結(jié)點(diǎn)會(huì)使操作麻煩，（同學(xué)們可以試一試，加進(jìn)頭結(jié)點(diǎn)如何實(shí)現(xiàn)？）并不是任何時(shí)候有頭結(jié)點(diǎn)都能使程序操作簡(jiǎn)化，要根據(jù)實(shí)際情況，決定用是否使用頭結(jié)點(diǎn)。感興趣的同學(xué)可以設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)約瑟夫環(huán)的方法2。在一般情況下默認(rèn)使用頭結(jié)點(diǎn)。不論是單向鏈表還是循環(huán)鏈表，頭指針不能丟。三、實(shí)習(xí)題 1. 用順序存儲(chǔ)表示（數(shù)組）實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題。 2. 一個(gè)線性表有n個(gè)元素（nMAXSIZE, MAXSIZE指線性表的最大長(zhǎng)度），且遞增有?，F(xiàn)有一元素x要插入到線性表的適當(dāng)位置上，并保持線性表原有的順序不變。設(shè)計(jì)程序?qū)崿F(xiàn)。要求：采用順序存儲(chǔ)表示

56、實(shí)現(xiàn)；采用鏈?zhǔn)酱鎯?chǔ)表示方法實(shí)現(xiàn)；比較兩種方法的優(yōu)劣。 3. 從單鏈表中刪除指定的元素x，若x在單鏈表中不存在，給出提示信息。 要求： （1）指定的值x由鍵盤(pán)輸入；（2）程序能處理空鏈表的情況。 4.用鏈表建立通訊錄。通訊錄內(nèi)容有：姓名、通訊地址、電話號(hào)碼。 要求：（1）通訊錄是按姓名項(xiàng)的字母順序排列的； （2）能查找通訊錄中某人的信息； 提示 可用鏈表來(lái)存放這個(gè)通訊錄，一個(gè)人的信息作為一個(gè)結(jié)點(diǎn)。成鏈的過(guò)程可以這樣考慮：先把頭結(jié)點(diǎn)后面的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)作為鏈中的首結(jié)點(diǎn)，也是末結(jié)點(diǎn)。從第二個(gè)數(shù)據(jù)開(kāi)始逐一作為工作結(jié)點(diǎn)，需從鏈表的首結(jié)點(diǎn)開(kāi)始比較，如果工作結(jié)點(diǎn)的數(shù)據(jù)比鏈中的當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)小，就插在其前

57、面。否則，再看后面是否還有結(jié)點(diǎn)，若沒(méi)有結(jié)點(diǎn)了就插在其后面成為末結(jié)點(diǎn)；若后面還有結(jié)點(diǎn)，再與后面的結(jié)點(diǎn)逐一比較處理。 5. 超長(zhǎng)正整數(shù)的加法，設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)求和運(yùn)算 提示 可采用一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表來(lái)表示一個(gè)非負(fù)的超大整數(shù)。從低位 開(kāi)始每四位組成的數(shù)字，依次放在鏈表的第一個(gè)、第二個(gè)、結(jié)點(diǎn)中，不足四位的最高位存放在鏈表的最后一個(gè)結(jié)點(diǎn)中，表頭結(jié)點(diǎn)值規(guī)定位-1。例如：大整數(shù)“567890987654321”可用如下的頭結(jié)點(diǎn)的鏈表表示：-1432187658909-567head 按照此數(shù)據(jù)結(jié)構(gòu)，可以從兩個(gè)表頭結(jié)點(diǎn)開(kāi)始，順序依次對(duì)應(yīng)相加，求出所需要的進(jìn)位后，將其代入下一個(gè)結(jié)點(diǎn)進(jìn)行運(yùn)算

58、。實(shí)習(xí)三 棧和隊(duì)列一、實(shí)習(xí)目的掌握棧這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。 了解和掌握遞歸程序設(shè)計(jì)的基本原理和方法。二、實(shí)例在各種教科書(shū)中關(guān)于棧和隊(duì)列敘述十分清晰。但是，它們?cè)谟?jì)算機(jī)內(nèi)的實(shí)現(xiàn)介紹不夠詳細(xì)。為了減輕學(xué)生上機(jī)實(shí)驗(yàn)的困難，在此給出幾個(gè)例題供參考。棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)。#include #include #define MAXSIZE 20 /* 數(shù)組最大界限 */typedef int ElemType; /* 數(shù)據(jù)元素類(lèi)型 */typedef struct ElemType aMAXSIZE

59、; /* 一維數(shù)組子域 */ int top; /* 棧頂指針子域 */ SqStack; /* 棧的順序結(jié)構(gòu)體類(lèi)型 */SqStack s1;/* 函數(shù)聲明 */void init_s(SqStack *s);void out_s(SqStack s);void push(SqStack *s,ElemType e);ElemType pop(SqStack *s);/* 主函數(shù) */main() int k; ElemType e,x; char ch; init_s( &s1); /* 初始化一個(gè)空棧 */ do printf(nnn); printf(nn 1. 數(shù)據(jù)元素e進(jìn)棧 );

60、printf(nn 2. 出棧一個(gè)元素，返回其值)； printf(nn 3. 結(jié)束程序運(yùn)行); printf(n=); printf(n 請(qǐng)輸入您的選擇 (1,2,3); scanf(%d,&k); switch(k) case 1: printf(n 進(jìn)棧 e=?); scanf(%d,&e); push( &s1,e); out_s( s1 ); break; case 2: x= pop( &s1); printf(n出棧元素 : %d, x); out_s( s1 ); break; case 3: exit(0); /* switch */ printf(n ); while(k=