第7單元基本數(shù)據(jù)結(jié)構(gòu)

信息學(xué)奧賽課課通（C++）2021/10/101第1課結(jié)構(gòu)體的引入和應(yīng)用學(xué)習(xí)目標(biāo)1.理解結(jié)構(gòu)體的概念和應(yīng)用背景。2.學(xué)會(huì)使用結(jié)構(gòu)體解決一些實(shí)際問題。2021/10/102結(jié)構(gòu)體在存儲(chǔ)和處理大批量數(shù)據(jù)時(shí)，一般會(huì)使用數(shù)組來實(shí)現(xiàn)，但是每一個(gè)數(shù)據(jù)的類型及含義必須一樣。如果需要把不同類型、不同含義的數(shù)據(jù)當(dāng)作一個(gè)整體來處理，如1000個(gè)學(xué)生的姓名、性別、年齡、體重、成績(jī)等，怎么處理呢？C++提供了結(jié)構(gòu)體（struct）來解決這類問題。2021/10/1031.結(jié)構(gòu)體的定義C++中的結(jié)構(gòu)體是由一系列具有相同類型或不同類型的數(shù)據(jù)構(gòu)成的數(shù)據(jù)集合，也叫結(jié)構(gòu)。使用結(jié)構(gòu)體，必須要先聲明一個(gè)結(jié)構(gòu)體類型，再定義和使用結(jié)構(gòu)體變量。結(jié)構(gòu)體類型的聲明格式如下：struct類型名{

數(shù)據(jù)類型1成員名1;

數(shù)據(jù)類型2成員名2;…};2021/10/104定義結(jié)構(gòu)體變量定義結(jié)構(gòu)體變量格式如下：struct結(jié)構(gòu)體類型名變量名列表;也可以把結(jié)構(gòu)體類型聲明和變量定義合在一起，格式如下：struct類型名{

數(shù)據(jù)類型1成員名1;

數(shù)據(jù)類型2成員名2;…}變量名;2021/10/1052.結(jié)構(gòu)體的使用

結(jié)構(gòu)體變量具有以下特點(diǎn)：（1）可以對(duì)結(jié)構(gòu)體變量的整體進(jìn)行操作。

例如：swap(a[i],a[j])

（2）可以對(duì)結(jié)構(gòu)體變量的成員進(jìn)行操作。

引用結(jié)構(gòu)體變量中成員的格式為：

結(jié)構(gòu)體變量名.成員名（3）結(jié)構(gòu)體變量的初始化方法與數(shù)組類似。2021/10/106例1、學(xué)生信息【問題描述】輸入一個(gè)學(xué)生的信息，包括姓名、性別、年齡、體重，再輸出這些信息?！据斎敫袷健恳恍校来问菍W(xué)生的姓名、性別、年齡、體重?！据敵龈袷健恳恍?，依次是姓名、性別、年齡、體重（體重保留一位小數(shù)）。【輸入樣例】zhangsanm2090.5【輸出樣例】zhangsanm2090.52021/10/107//p7-1-1#include<bits/stdc++.h>usingnamespacestd;structstudent{stringname;charsex;intage;doubleweight;};intmain(){studentstu;cin>>>>stu.sex>>stu.age>>stu.weight;cout<<<<““<<stu.sex<<““<<stu.age<<““;cout<<fixed<<setprecision(1)<<stu.weight<<endl;return0;}2021/10/108例2、年齡排序【問題描述】輸入n個(gè)學(xué)生的信息，包括姓名、性別、出生年月。要求按年齡從小到大依次輸出這些學(xué)生的信息。數(shù)據(jù)保證沒有學(xué)生同年同月出生?！据斎敫袷健康谝恍幸粋€(gè)整數(shù)n，表示學(xué)生人數(shù)，n≤100。接下來n行，每一行依次輸入學(xué)生的姓名、性別、出生年份、出生月份?！据敵龈袷健堪茨挲g從小到大，一行輸出一個(gè)學(xué)生的原始信息。【輸入樣例】5Johnmale199912Davidfemale19998Jasonmale199811Jackfemale19988Kittyfemale20007【輸出樣例】Kittyfemale20007Johnmale199912Davidfemale19998Jasonmale199811Jackfemale199882021/10/109//p7-1-2#include<bits/stdc++.h>usingnamespacestd;structstu{stringname;stringsex;intyear,month;};constintMAXN=110;stua[MAXN];intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i].name>>a[i].sex>>a[i].year>>a[i].month;for(inti=1;i<=n;i++)for(intj=i+1;j<=n;j++)if(a[i].year<a[j].year||a[i].year==a[j].year&&a[i].month<a[j].month)swap(a[i],a[j]);for(inti=1;i<=n;i++){cout<<a[i].name<<””<<a[i].sex<<””;cout<<a[i].year<<””<<a[i].month<<endl;}return0;}2021/10/1010例3、猴子選大王【問題描述】有n只猴子圍成一圈，從1~n編號(hào)，大家決定從中選出一個(gè)大王。經(jīng)過協(xié)商，決定選大王的規(guī)則為：從編號(hào)為1的猴子開始報(bào)數(shù)，報(bào)到k的猴子出圈，然后再從下一只開始繼續(xù)報(bào)1到k……最后剩下來的那一只就是大王。要求編程從鍵盤輸入n、k，輸出成為大王的猴子編號(hào)?！据斎敫袷健恳恍袃蓚€(gè)正整數(shù)n和k，2≤n≤1000，2≤k≤10^9?！据敵龈袷健恳恍幸粋€(gè)正整數(shù)，代表猴王的編號(hào)?！据斎霕永?2【輸出樣例】32021/10/1011【問題分析】本題采用“模擬”法實(shí)現(xiàn)?？梢远x一個(gè)一維數(shù)組來模擬猴子在不在圈內(nèi)，用a[i]代表第i只猴子的狀態(tài)，0代表出圈，1代表在圈內(nèi)。然后不斷的掃描這個(gè)一維數(shù)組，如果猴子在圈內(nèi)，則計(jì)數(shù)器加1；如果不在就不加，當(dāng)計(jì)數(shù)器到達(dá)k時(shí)，就把當(dāng)前這只猴子標(biāo)志出圈，然后作出一些相關(guān)的處理；當(dāng)還剩一只猴子的時(shí)候就停止操作，輸出剩下的圈內(nèi)這只猴子的編號(hào)。以上算法的最大問題是，如果猴子數(shù)比較多，不斷掃描一維數(shù)組的時(shí)候會(huì)很慢，特別是當(dāng)大部分猴子都已經(jīng)出圈，會(huì)掃描很多無猴子的“無效”操作。如果建立一個(gè)循環(huán)鏈表，那么在掃描的時(shí)候就不會(huì)出現(xiàn)無猴子還掃描的情況，在猴子出圈的時(shí)候只需要在鏈表中刪除一個(gè)元素，這樣效率會(huì)提高很多。2021/10/1012具體操作如下：定義一個(gè)結(jié)構(gòu)體monkey，里面有兩個(gè)參數(shù)，一個(gè)代表猴子編號(hào)，另一個(gè)記錄這只猴子的下一只猴子的編號(hào)，注意一開始每只猴子的下一只猴子的編號(hào)是本身的編號(hào)加1，最后一只猴子的下一只猴子的編號(hào)是1號(hào)。如果需要?jiǎng)h除3號(hào)猴子，那么只需要把當(dāng)前3號(hào)猴子前一只猴子2號(hào)的下一只猴子序號(hào)，指向當(dāng)前猴子3號(hào)的下一只猴子序號(hào)4。具體程序參考教材228頁-229頁。2021/10/1013實(shí)踐鞏固2021/10/1014第2課結(jié)構(gòu)體的擴(kuò)展學(xué)習(xí)目標(biāo)1.理解運(yùn)算符重載的含義及其使用。2.理解成員函數(shù)的含義及其使用。2021/10/1015結(jié)構(gòu)體的擴(kuò)展

在C++中，由于類（class）技術(shù)的出現(xiàn)使結(jié)構(gòu)體功能得到了很大的增強(qiáng)。本課簡(jiǎn)單介紹一些與信息學(xué)競(jìng)賽有關(guān)的運(yùn)算符重載和成員函數(shù)知識(shí)，其他更詳細(xì)、復(fù)雜的內(nèi)容請(qǐng)參閱相關(guān)書籍和資料。2021/10/10161.運(yùn)算符重載“運(yùn)算符重載”常用于解決結(jié)構(gòu)體或自定義數(shù)據(jù)類型的加法、減法等特殊含義的運(yùn)算。運(yùn)算符重載的一般格式為：類型名operator運(yùn)算符(const類型名變量)const{…}2021/10/1017例1、作業(yè)統(tǒng)計(jì)【問題描述】為了了解學(xué)生的課后作業(yè)負(fù)擔(dān)情況，需要統(tǒng)計(jì)學(xué)生連續(xù)若干天完成作業(yè)所需的總時(shí)間?，F(xiàn)在，輸入某位學(xué)生n天完成作業(yè)的時(shí)間，格式為時(shí)、分、秒，最后輸出這位學(xué)生n天完成作業(yè)的總時(shí)間（秒）。【輸入格式】第1行一個(gè)正整數(shù)n，表示有n天；第2~第n+1行，每行3個(gè)整數(shù)，分別代表時(shí)、分、秒?！据敵龈袷健恳恍行畔?，表示這個(gè)學(xué)生完成作業(yè)的總時(shí)間，具體格式見輸出樣例?！据斎霕永?120301204511930【輸出樣例】4hour0minute45second2021/10/1018【問題分析】本題需要把若干時(shí)間（時(shí)、分、秒）相加，但又不是普通的加法運(yùn)算。所以，可以利用運(yùn)算符重載，另外定義一個(gè)“+”運(yùn)算，實(shí)現(xiàn)對(duì)兩個(gè)結(jié)構(gòu)體變量的加法。2021/10/1019//p7-2-1#include<bits/stdc++.h>usingnamespacestd;structworktime{//聲明一個(gè)結(jié)構(gòu)體類型worktime記錄學(xué)生完成作業(yè)的時(shí)間inthr,minut,sec;//hr,minut,sec分別代表時(shí)分秒worktimeoperator+(constworktimex)const{//對(duì)+進(jìn)行重新定義worktimetmp;tmp.sec=(sec+x.sec)%60;tmp.minut=(minut+x.minut+(sec+x.sec)/60)%60;tmp.hr=hr+x.hr+(minut+x.minut+(sec+x.sec)/60)/60;returntmp;}};intmain(){worktimestu,sum;intn;cin>>n;sum.hr=sum.minut=sum.sec=0;for(inti=1;i<=n;i++){cin>>stu.hr>>stu.minut>>stu.sec;sum=sum+stu;//兩個(gè)結(jié)構(gòu)體sum和stu通過重載+運(yùn)算符進(jìn)行加法運(yùn)算}cout<<sum.hr<<”hour”<<sum.minut<<”minute”<<sum.sec<<”second”;return0;}2021/10/10202.成員函數(shù)在C++中，允許在結(jié)構(gòu)中定義函數(shù)，該函數(shù)稱為“成員函數(shù)”。描述形式如下：struct結(jié)構(gòu)名{

數(shù)據(jù)成員

成員函數(shù)};2021/10/1021例2、身高問題【問題描述】輸入n個(gè)學(xué)生的信息，每個(gè)學(xué)生信息包括姓名、身高、學(xué)號(hào)。編程輸出身高最高的學(xué)生的信息?！据斎敫袷健康?行一個(gè)正整數(shù)n，表示學(xué)生個(gè)數(shù)，n≤100。以下n行，每一行依次輸入學(xué)生的姓名、身高、學(xué)號(hào)?！据敵龈袷健枯敵鲎罡叩膶W(xué)生信息，如存在身高一樣的請(qǐng)輸出學(xué)號(hào)小的那個(gè)同學(xué)。【輸入樣例】5Johaviason16820160309Jacitt輸出樣例】David173201603062021/10/1022//p7-2-2#include<bits/stdc++.h>usingnamespacestd;structstu{stringname;intheigh;intnum;voidinput(){cin>>name>>heigh>>num;}voidoutput(){cout<<name<<““<<heigh<<““<<num<<endl;}};stua[110];intmain(){intn;stumaxn;maxn.heigh=maxn.num=0;cin>>n;for(inti=1;i<=n;i++){a[i].input();if(a[i].heigh>maxn.heigh)maxn=a[i];elseif(a[i].heigh==maxn.heigh&&a[i].num<maxn.num)maxn=a[i];}maxn.output();return0;}2021/10/1023實(shí)踐鞏固2021/10/1024第3課共用體的引入和應(yīng)用學(xué)習(xí)目標(biāo)1.理解共用體的概念和應(yīng)用背景。2.學(xué)會(huì)使用共用體解決一些實(shí)際問題。2021/10/1025共用體在C++中，共用體也稱聯(lián)合（union），是一種數(shù)據(jù)格式，能存儲(chǔ)不同類型數(shù)據(jù)，但同一時(shí)間只能存儲(chǔ)其中的一種類型數(shù)據(jù)。例如，存放一個(gè)人的信息，如果是成年人，存放他的身份證號(hào)碼；否則，存放他的學(xué)籍號(hào)。這里面就有兩個(gè)成員，但是任何一個(gè)人只能使用其中的一個(gè)。使用共用體前必須先聲明一個(gè)共用體類型，才可以定義和使用共用體變量。例如，要聲明一個(gè)記錄個(gè)人信息的共用體，可以這樣：unionperson{//聲明一個(gè)共用體類型personcharid[18];//聲明一個(gè)字符數(shù)組，存儲(chǔ)身份證號(hào)碼intnum;//聲明一個(gè)整數(shù)，存放學(xué)籍號(hào)};2021/10/1026例1、成績(jī)統(tǒng)計(jì)【問題描述】興趣小組收集學(xué)員成績(jī)信息，每個(gè)學(xué)員的成績(jī)有兩種表示方法，一種用best、good、poor三種等級(jí)來表示，還有一種就是直接用分?jǐn)?shù)來表示（百分制）。請(qǐng)保存學(xué)員成績(jī)信息，并且統(tǒng)計(jì)有多少人是用等級(jí)來表示成績(jī)的，用分?jǐn)?shù)來表示成績(jī)的人的平均分是多少（取整就行）?！据斎敫袷健康?行一個(gè)正整數(shù)n，表示學(xué)員人數(shù)，n≤1000。第2~n+1行，每行一個(gè)字符和一個(gè)字符串，中間用一個(gè)空格隔開。第一個(gè)字符表示這個(gè)學(xué)生成績(jī)類型，有C、N兩種分別代表等級(jí)表示和分?jǐn)?shù)表示，第二個(gè)字符串表示成績(jī)信息。2021/10/1027【輸出格式】一行兩個(gè)整數(shù)，分別表示用等級(jí)表示成績(jī)的人數(shù)和用分?jǐn)?shù)表示成績(jī)?nèi)说钠骄郑ㄈ≌?，中間用一個(gè)空格隔開?！据斎霕永?CbestCgoodN90CpoorN98【輸出樣例】3942021/10/1028//p7-3-1#include<bits/stdc++.h>usingnamespacestd;intmain(){unionres{//聲明一個(gè)共用體rescharrank[5];//用等級(jí)表示成績(jī)intx;//用分?jǐn)?shù)表示成績(jī)};structstu{charf;//代表學(xué)生用哪種方式記錄成績(jī)r(jià)esscore;//定義score為共用體};stua[1001];intn,count=0,num=0;cin>>n;for(inti=1;i<=n;i++){cin>>a[i].f;switch(a[i].f){case‘C’:for(intj=0;j<4;j++)cin>>a[i].score.rank[j];count++;break;case‘N’:cin>>a[i].score.x;num+=a[i].score.x;}}cout<<count<<””<<num/(n-count)<<endl;return0;}2021/10/1029實(shí)踐鞏固2021/10/1030第4課文件學(xué)習(xí)目標(biāo)學(xué)會(huì)使用stream類流文件進(jìn)行數(shù)據(jù)的輸入輸出。2021/10/1031文件C++程序和文件緩沖區(qū)交流的方式有流式和I/O方式兩種。信息學(xué)競(jìng)賽中一般使用流式文件操作，流式文件類型一般分為stream類的流文件和文件指針FILE兩種，本課只介紹stream類的流文件。2021/10/10321.stream類流文件的操作ifstreamfin(“輸入流文件名”);作用是定義一個(gè)輸入流文件類型變量fin，初始化指向引號(hào)中指定的文本文件。ofstreamfout(“輸出流文件名”);作用是定義一個(gè)輸出流文件類型變量fout，初始化指向引號(hào)中指定的文本文件。fin>>變量名;//或fout<<變量名;作用是從fin文件中輸入數(shù)據(jù)給某個(gè)變量，或者把某個(gè)變量的值輸出到fout文件中，這兩個(gè)語句類似于cin和cout。fin.close();//或fout.close();作用是關(guān)閉輸入文件、輸出文件。如果文件沒有關(guān)閉，則程序結(jié)束時(shí)會(huì)自動(dòng)關(guān)閉，因此比賽時(shí)一般省略不寫。2021/10/1033例1、求和【問題描述】從文本文件sum.in中讀入n個(gè)正整數(shù)，要求對(duì)這n個(gè)數(shù)中的奇數(shù)和偶數(shù)分別求和，再將結(jié)果寫到文本文件sum.out中?！据斎敫袷健康?行一個(gè)正整數(shù)n，1≤n≤5000；第2~n+1行，每行一個(gè)正整數(shù)，每個(gè)數(shù)都在1~20000之間?！据敵龈袷健抗灿袃尚?，每行包含一個(gè)整數(shù)，第一行為輸入文件中的所有奇數(shù)之和，第二行為輸入文件中的所有偶數(shù)之和?！据斎霕永?310758【輸出樣例】15182021/10/1034//p7-4-1#include<iostream>#include<fstream>usingnamespacestd;ifstreamfin(“sum.in”);ofstreamfout(“sum.out”);intmain(){intn,x,s1=0,s2=0;fin>>n;for(inti=1;i<=n;i++){fin>>x;if(x%2==1)s1+=x;elses2+=x;}fout<<s1<<endl<<s2<<endl;fin.close();fout.close();return0;}2021/10/10352.文件的重定向在C++中，cin使用的輸入設(shè)備是鍵盤，稱之為“標(biāo)準(zhǔn)輸入（stdin）”。cout使用的輸出設(shè)備是顯示器，稱之為“標(biāo)準(zhǔn)輸出（stdout）”。C++可以使用freopen函數(shù)把stdin和stdout重新定向到某一個(gè)指定的文件，使原來的標(biāo)準(zhǔn)輸入、輸出變成指定文件的輸入、輸出。具體語句格式為：freopen(“輸入流文件名”,”r”,stdin);freopen(“輸出流文件名”,”w”,stdout);經(jīng)過重定向后，任何對(duì)stdin、stdout的操作都變成了對(duì)輸入流文件、輸出流文件的操作。2021/10/1036例2、替換型密碼【問題描述】簡(jiǎn)單的替換型密碼是很弱的，它通過將每個(gè)字母替換成另外一個(gè)字母來加密一個(gè)字母組成的信息。考慮下面的替換型密碼描述：ABCDEFGHIJKLMNOPQRSTUVWXYZNOPQRSTUVWXYZABCDEFGHIJKLM這樣的描述表示當(dāng)輸入中出現(xiàn)“A”的時(shí)候，輸出中應(yīng)該出現(xiàn)的是“N”。同理，每個(gè)“B”都變成“O”，以此類推，一直到“Z”都變成“M”。這個(gè)特殊的替換型密碼的例子被稱為“rot13”（旋轉(zhuǎn)13——rotate-13的簡(jiǎn)稱），有一個(gè)有趣的特性：它是自解密的。將信息再加密一次就會(huì)得到原始的信息。這樣的密碼中，單詞“CAT”就會(huì)成為“PNG”。而句子“NOWISTHETIMEFORALLGOODPEOPLETOPROGRAMWELL.”就成了“ABJVFGURGVZRSBENYYTBBQCRBCYRGBCEBTENZJRYY.”。注意，所有的空格、標(biāo)點(diǎn)符號(hào)以至于任何不在字符集A~Z中的字符都不變。請(qǐng)寫一個(gè)程序來實(shí)現(xiàn)替換型密碼。2021/10/1037【輸入格式】第1行：沒有空格隔開的亂序的26個(gè)字母A~Z，這些字母被用于描述替換型密碼。第2行：一段長(zhǎng)度在1~80之間的內(nèi)容，這段內(nèi)容將被加密。不會(huì)有小寫字母出現(xiàn)。標(biāo)點(diǎn)符號(hào)、空格和數(shù)字都可能出現(xiàn)。沒有奇怪的字符（像退格、響鈴字符之類）出現(xiàn)?！据敵龈袷健恳恍休斎雰?nèi)容加密后的一行文本?！据斎霕永縉OPQRSTUVWXYZABCDEFGHIJKLMNOWISTHETIMEFORALLGOODPEOPLETOPROGRAMWELL.【輸出樣例】ABJVFGURGVZRSBENYYTBBQCRBCYRGBCEBTENZJRYY.2021/10/1038//p7-4-2#include<bits/stdc++.h>usingnamespacestd;intmain(){freopen(“subcip.in”,”r”,stdin);freopen(“subcip.out”,”w”,stdout);strings,pass;getline(cin,pass);getline(cin,s);for(inti=0;i<s.size();i++)if(isupper(s[i]))s[i]=pass[s[i]-65];cout<<s<<endl;return0;}2021/10/1039例3、統(tǒng)計(jì)奇數(shù)【問題描述】輸入若干正整數(shù)，統(tǒng)計(jì)并輸出其中奇數(shù)的個(gè)數(shù)?！据斎敫袷健咳舾烧麛?shù)（不超過10000個(gè)）。【輸出格式】一行一個(gè)數(shù)，表示奇數(shù)的個(gè)數(shù)。【輸入樣例】245【輸入樣例】1【問題分析】當(dāng)不知道輸入數(shù)據(jù)的個(gè)數(shù)時(shí)，可以使用while（cin>>x）來不斷讀入數(shù)據(jù)，直到文件里所有數(shù)據(jù)都讀完為止。2021/10/1040//p7-4-3#include<iostream>usingnamespacestd;intmain(){intx,s=0;freopen(“odd.in”,”r”,stdin);freopen(“odd.out”,”w”,stdout);while(cin>>x){if(x%2==1)s++;}cout<<s<<endl;return0;}2021/10/1041實(shí)踐鞏固2021/10/1042第5課隊(duì)列學(xué)習(xí)目標(biāo)1.理解隊(duì)列的概念及其基本操作。2.學(xué)會(huì)使用隊(duì)列解決一些實(shí)際問題。2021/10/1043隊(duì)列隊(duì)列是一種操作（或者說運(yùn)算）受到限制的特殊線性表。其插入操作限定在表的一端進(jìn)行，稱為“入隊(duì)”；其刪除操作則限定在表的另一端進(jìn)行，稱為“出隊(duì)”。插入一端稱為隊(duì)尾（rear）；刪除一端稱為隊(duì)頭（front）。2021/10/1044隊(duì)列隊(duì)列也被稱作“先進(jìn)先出”線性表（FIFO，F(xiàn)irstInFirstOut）。類似于生活中排隊(duì)購票，先來先買，后來后買。在不斷入隊(duì)、出隊(duì)的過程中，隊(duì)列將會(huì)呈現(xiàn)出以下幾種狀態(tài)：隊(duì)空：隊(duì)列中沒有任何元素。隊(duì)滿：隊(duì)列空間已全被占用。溢出：當(dāng)隊(duì)列已滿，卻還有元素要入隊(duì)，就會(huì)出現(xiàn)“上溢（overflow）”；當(dāng)隊(duì)列已空，卻還要做“出隊(duì)”操作，就會(huì)出現(xiàn)“下溢（underflow）”。兩種情況合在一起稱為隊(duì)列的“溢出”。2021/10/10451.隊(duì)列的基本操作（具體參見教材245頁-246頁）（1）初始化（2）判空（3）求隊(duì)列中實(shí)際元素的個(gè)數(shù)（4）入隊(duì)，入隊(duì)操作前，需要判斷隊(duì)列是否已滿（5）出隊(duì)，出隊(duì)操作前，需要判斷隊(duì)列是否為空（6）取隊(duì)首元素2021/10/10462.循環(huán)隊(duì)列

隨著入隊(duì)與出隊(duì)操作的不斷進(jìn)行，隊(duì)頭指針在數(shù)組中不斷向隊(duì)尾方向移動(dòng)，而在隊(duì)頭前面產(chǎn)生了一片不能利用的“空閑區(qū)”，當(dāng)隊(duì)尾指針指向數(shù)組最后一個(gè)位置，即rear=maxn時(shí)，如果再有元素入隊(duì)就會(huì)出現(xiàn)“溢出”，這種溢出稱作“假溢出”。

如何解決這種情況呢？一種方法是每次出隊(duì)操作時(shí)，都向“空閑區(qū)”整體移動(dòng)一位，帶來的后果是時(shí)間復(fù)雜度高了；另一種方法是讓數(shù)組首尾相連，形成“環(huán)”狀，即所謂的“循環(huán)隊(duì)列”。2021/10/10472.循環(huán)隊(duì)列循環(huán)隊(duì)列初始時(shí)，front=rear=0，如果maxn個(gè)元素一個(gè)個(gè)依次入隊(duì)，則rear=maxn，此時(shí)再有元素入隊(duì)，則它會(huì)被存放在q[0]這個(gè)單元，也會(huì)出現(xiàn)front=rear=0，與隊(duì)空時(shí)的狀態(tài)一樣。解決方法是少用一個(gè)元素空間，約定數(shù)據(jù)入隊(duì)前，測(cè)試“隊(duì)尾指針在循環(huán)意義下加1后是否等于頭指針”作為判斷“隊(duì)滿”的條件。循環(huán)隊(duì)列的實(shí)際長(zhǎng)度為(rear-front+maxn)

%maxn。循環(huán)隊(duì)列的重要操作修改如下(使用q[0]這個(gè)單元)：（1）判斷隊(duì)滿：如果(rear+1)

%maxn=front，則隊(duì)列已滿。（2）入隊(duì)：如果隊(duì)列未滿，則執(zhí)行：rear=(rear+1)

%maxn；q[rear]

=x；（3）出隊(duì)：如果隊(duì)列不為空，則執(zhí)行：front=(front+1)

%maxn；2021/10/10483.隊(duì)列的應(yīng)用舉例例1、周末舞會(huì)【問題描述】假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。跳舞開始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。規(guī)定每個(gè)舞曲只能有一對(duì)跳舞者。若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲?，F(xiàn)要求寫一個(gè)程序，模擬上述舞伴配對(duì)問題?！据斎敫袷健康?行兩個(gè)正整數(shù)，表示男士人數(shù)m和女士人數(shù)n，1≤m，n≤1000；第2行一個(gè)正整數(shù)，表示舞曲的數(shù)目k，k≤1000。2021/10/1049【輸出格式】共k行，每行兩個(gè)數(shù)，之間用一個(gè)空格隔開，表示配對(duì)舞伴的序號(hào)，男士在前，女士在后。【輸入樣例】246【輸出樣例】1122132411222021/10/1050【問題分析】顯然，舞伴配對(duì)的順序符合“先進(jìn)先出”，所以用兩個(gè)隊(duì)列分別存放男士隊(duì)伍和女士隊(duì)伍。然后，模擬k次配對(duì)：每次取各隊(duì)隊(duì)頭元素“配對(duì)”輸出，并進(jìn)行“出隊(duì)”和重新“入隊(duì)”操作。參考程序參見教材247頁-248頁。2021/10/1051例2、取牌游戲【問題描述】小明正在使用一堆共K張紙牌與N-1個(gè)朋友玩取牌游戲。其中，N≤K≤100000，2≤N≤100，K是N的倍數(shù)。紙牌中包含M=K/N張“good”牌和K-M張“bad”牌。小明負(fù)責(zé)發(fā)牌，他當(dāng)然想自己獲得所有“good”牌。他的朋友懷疑他會(huì)欺騙，所以他們給出以下一些限制，以防小明耍詐：1）游戲開始時(shí)，將最上面的牌發(fā)給小明右手邊的人。2）每發(fā)完一張牌，他必須將接下來的P張牌（1≤P≤10）一張一張地依次移到最后，放在牌堆的底部。3）以逆時(shí)針方向，連續(xù)給每位玩家發(fā)牌。小明迫切想贏，請(qǐng)你幫助他算出所有“good”牌放置的位置，以便他得到所有“good”牌。牌從上往下依次標(biāo)注為#1，#2，#3，…2021/10/1052【輸入格式】第1行，3個(gè)用一個(gè)空格間隔的正整數(shù)N、K和P?！据敵龈袷健縈行，從頂部按升序依次輸出“good”牌的位置?！据斎霕永?92【輸出樣例】3782021/10/1053【問題分析】方法1、利用普通隊(duì)列模擬。結(jié)合題目中的條件1和3，可以推出“小明是第n個(gè)拿到牌的”，根據(jù)數(shù)據(jù)范圍大致推出隊(duì)列存儲(chǔ)容量上界為K+10×N×(100000/N)

=1100000。參考程序參見教材248頁-249頁。方法2、利用循環(huán)隊(duì)列模擬實(shí)現(xiàn)。參考程序參見教材249頁-250頁。2021/10/1054實(shí)踐鞏固2021/10/1055第6課隊(duì)列的應(yīng)用學(xué)習(xí)目標(biāo)1.使用隊(duì)列解決一些實(shí)際應(yīng)用問題。2.學(xué)會(huì)用隊(duì)列實(shí)現(xiàn)簡(jiǎn)單的寬度優(yōu)先搜索。2021/10/1056例1、Blah數(shù)集【問題描述】數(shù)學(xué)家高斯小時(shí)候偶然間發(fā)現(xiàn)一種有趣的自然數(shù)集合Blah。對(duì)于以a為基的集合Blah定義如下：1）a是集合Blah的基，且a是Blah的第一個(gè)元素；2）如果x在集合Blah中，則2x+1和3x+1也都在集合Blah中；3）沒有其他元素在集合Blah中了。現(xiàn)在小高斯想知道如果將集合Blah中元素按照升序排列，第n個(gè)元素會(huì)是多少？注意：集合中沒有重復(fù)的元素。2021/10/1057【輸入格式】一行兩個(gè)正整數(shù)，分別表示集合的基a以及所求元素序號(hào)n，1≤a≤50，1≤n≤1000000?！据敵龈袷健恳恍幸粋€(gè)正整數(shù)，表示集合Blah的第n個(gè)元素值。【輸入樣例1】1100【輸出樣例1】418【輸入樣例2】285437【輸出樣例2】9005852021/10/1058【問題分析】根據(jù)條件，除了第一個(gè)數(shù)a以外，可以把數(shù)集q[]的所有數(shù)分成兩個(gè)子集，一個(gè)是用2x+1來表示的數(shù)的集合1，另一個(gè)是用3x+1來表示的數(shù)的集合2，兩個(gè)集合要保持有序非常容易，只需用兩個(gè)指針two和three來記錄。其中two表示集合1下一個(gè)要產(chǎn)生的數(shù)是由q[two]*2+1得到，three表示集合2下一個(gè)要產(chǎn)生的數(shù)是由q［three］*3+1得到。接下來比較q[two]*2+1和q[three]*3+1的大小關(guān)系：1）如果q[two]*2+1<q[three]*3+1，則把q[two]*2+1加入數(shù)集中。2）如果q[two]*2+1>q[three]*3+1，則把q[three]*3+1加入數(shù)集中。3）如果q[two]*2+1=q[three]*3+1，則取任意其一加入數(shù)集中即可。所以，本題就是利用隊(duì)列先進(jìn)先出的特點(diǎn)，模擬n個(gè)數(shù)依次產(chǎn)生的過程。2021/10/1059//p7-6-1#include<bits/stdc++.h>usingnamespacestd;intq[1000011];intmain(){inta,n,x,two,three,rear;cin>>a>>n;two=three=rear=1;q[1]=a;while(rear!=n){if(2*q[two]+1>3*q[three]+1){rear++;q[rear]=3*q[three]+1;three++;}elseif(2*q[two]+1<3*q[three]+1){rear++;q[rear]=2*q[two]+1;two++;}else{rear++;q[rear]=3*q[three]+1;two++;three++;}}cout<<q[n]<<endl;return0;}2021/10/1060例2、關(guān)系網(wǎng)絡(luò)【問題描述】有n個(gè)人，他們的編號(hào)為1~n，其中有一些人相互認(rèn)識(shí)，現(xiàn)在x想要認(rèn)識(shí)y，可以通過他所認(rèn)識(shí)的人來認(rèn)識(shí)更多的人（如果a認(rèn)識(shí)b，b認(rèn)識(shí)c，那么a可以通過b來認(rèn)識(shí)c），求出x最少需要通過多少人才能認(rèn)識(shí)y?！据斎敫袷健康?行3個(gè)整數(shù)n、x、y，2≤n≤100；接下來的n行是一個(gè)n×n的鄰接矩陣，a[i][j]=1表示i認(rèn)識(shí)j，a[i][j]=0表示不認(rèn)識(shí)。保證i=j時(shí)，a[i][j]=0，并且a[i][j]=a[j][i]?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示x認(rèn)識(shí)y最少需要通過的人數(shù)。數(shù)據(jù)保證x一定能認(rèn)識(shí)y?！据斎霕永?150100010110010100110100010【輸出樣例】22021/10/1061【問題分析】本題是求最優(yōu)值問題。顯然，如果x和y本身就認(rèn)識(shí)，則答案是0；否則，答案至少為1。如果x和y通過z這一個(gè)人就間接認(rèn)識(shí)，那么答案是1，可以通過窮舉z來實(shí)現(xiàn)；否則，答案至少為2?！绱俗鱿氯ィ欢苷业酱鸢?最大為n-2)。這種算法叫作“寬度優(yōu)先搜索”，簡(jiǎn)稱“寬搜”，具體實(shí)現(xiàn)需要通過一個(gè)隊(duì)列在實(shí)現(xiàn)過程中擴(kuò)展到所有人。把x加入隊(duì)列并設(shè)置為隊(duì)頭元素，設(shè)q[x][1]=0，從隊(duì)頭開始進(jìn)行寬搜，窮舉鄰接矩陣的第x行，看x認(rèn)識(shí)誰(判斷a[x][j]=1)，認(rèn)識(shí)的人(j)全部依次入隊(duì)，并且q[j][1]++。如果出現(xiàn)了y，則輸出q[f][1]-1，結(jié)束搜索；否則，取出隊(duì)頭元素繼續(xù)寬搜。2021/10/1062//p7-6-2#include<bits/stdc++.h>usingnamespacestd;intq[10010][2],a[110][110];boolp[110];intmain(){inti,j,r,f,tmp,x,y,n;memset(p,true,sizeof(p));cin>>n>>x>>y;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j];f=r=1;q[f][0]=x;q[f][1]=0;p[x]=false;while(f<=r){tmp=q[f][0];if(tmp==y){cout<<q[f][1]-1<<endl;return0;}for(i=1;i<=n;i++)if(a[i][tmp]==1&&p[i]){r++;q[r][0]=i;q[r][1]=q[f][1]+1;p[i]=false;}f++;}return0;}2021/10/1063例3、圖的寬度優(yōu)先遍歷【問題描述】讀入一個(gè)用鄰接矩陣存儲(chǔ)的無向圖，輸出它的寬度優(yōu)先遍歷序列?！据斎敫袷健康?行1個(gè)正整數(shù)n，表示圖中頂點(diǎn)數(shù)，2≤n≤100；接下來的n行是一個(gè)n×n的鄰接矩陣，a[i][j]=1表示頂點(diǎn)i和頂點(diǎn)j之間有直接邊相連，a[i][j]=0表示沒有直接邊相連。保證i=j時(shí)，a[i][j]=0，并且a[i][j]=a[j][i]?！据敵龈袷健枯敵?~n的某一種排列，表示從頂點(diǎn)1開始，對(duì)該圖進(jìn)行寬度優(yōu)先遍歷得到的頂點(diǎn)序列，每?jī)蓚€(gè)數(shù)之間用一個(gè)“-”分隔。2021/10/1064【輸入樣例】80110000010011000100000110100010001000100000110000010000100100010【輸出樣例】1-2-3-4-5-7-8-62021/10/1065【問題分析】圖7.6-1所示為圖的寬度優(yōu)先遍歷。用隊(duì)列來實(shí)現(xiàn)圖的寬度優(yōu)先遍歷：先從某個(gè)頂點(diǎn)出發(fā)，把這個(gè)頂點(diǎn)入隊(duì)，作為隊(duì)首元素。然后把跟隊(duì)首元素相連的頂點(diǎn)再依次入隊(duì)，最后隊(duì)首元素出隊(duì)。接著再把新的隊(duì)首元素相連的所有頂點(diǎn)入隊(duì)，新的隊(duì)首元素出隊(duì)。……如此下去，直到所有元素都出隊(duì)，出隊(duì)的順序就是圖的寬度優(yōu)先遍歷序列。2021/10/1066//p7-6-3#include<bits/stdc++.h>usingnamespacestd;constintN=110;inta[N][N],q[N],h[N];intmain(){intn;cin>>n;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)cin>>a[i][j];cout<<1;q[1]=1;h[1]=1;for(intl=1,r=1;l<=r;l++){intu=q[l];for(inti=1;i<=n;i++)if(a[u][i]&&!h[i]){cout<<‘-‘<<i;q[++r]=i;h[i]=1;}}return0;}2021/10/1067實(shí)踐鞏固2021/10/1068第7課棧學(xué)習(xí)目標(biāo)1.理解棧的概念及其基本操作。2.學(xué)會(huì)使用棧解決一些實(shí)際問題。2021/10/1069棧也是一種操作（或者說運(yùn)算）受到限制的特殊線性表。其插入和刪除操作都限制在表的一端進(jìn)行，這一端被稱為“棧頂（top）”，相對(duì)的另一端稱為“棧底（bottom）”。插入操作稱為“進(jìn)棧（PUSH）”或者“壓?！保瑒h除操作稱為“出棧（POP）”。棧的特點(diǎn)是“先進(jìn)后出（FILO，F(xiàn)irstInLastOut）”2021/10/10701.棧的基本操作（具體參見教材260頁-261頁）（1）初始化（2）判空（3）求棧中實(shí)際元素的個(gè)數(shù)（4）進(jìn)棧（壓棧）（5）出棧（6）取棧頂元素2021/10/10712.棧的應(yīng)用舉例例1、程序員輸入問題【問題描述】程序員輸入程序出現(xiàn)差錯(cuò)時(shí)，可以采取以下的補(bǔ)救措施：按錯(cuò)了一個(gè)鍵時(shí)，可以補(bǔ)按一個(gè)退格符“#”，以表示前一個(gè)字符無效；發(fā)現(xiàn)當(dāng)前一行有錯(cuò)，可以按一個(gè)退行符“@”，以表示“@”與前一個(gè)換行符之間的字符全部無效。【輸入格式】輸入一行字符，個(gè)數(shù)不超過100?！据敵龈袷健枯敵鲆恍凶址?，表示實(shí)際有效字符?！据斎霕永縮dfosif@for（ii#=1，#；i<.#=8；i+++#）；【輸出樣例】for（i=1；i<=8；i++）；2021/10/1072【問題分析】通過棧的操作，模擬這一過程：1、逐行處理，處理完一行后輸出結(jié)果、棧重新置空。2、對(duì)于每行，逐個(gè)字符處理：①既不是退格符“?！保膊皇峭诵蟹埃馈?，則將該字符壓棧；②是退格符“＃”，則出棧；③是退行符“＠”，就把棧置空。2021/10/1073//p7-7-1#include<bits/stdc++.h>usingnamespacestd;intmain(){freopen(“editor.in“,“r“,stdin);freopen(“editor.out“,“w“,stdout);chars[110];inttop=0;stringstr;while(getline(cin,str)){for(inti=0;i<str.size();++i){switch(str[i]){case’#’：top--;break;case’@’：top=0;break;default：top++;s[top]=str[i];}}for(inti=1;i<=top;i++)cout<<s[i];cout<<endl;}return0;}2021/10/1074例2、溶液模擬器【問題描述】小謝雖然有很多溶液，但是還是沒有辦法配成想要的溶液，因?yàn)槿f一倒錯(cuò)了就沒有辦法挽回了。因此，小謝到網(wǎng)上下載了一個(gè)溶液配置模擬器。模擬器在計(jì)算機(jī)中構(gòu)造一種虛擬溶液，然后可以虛擬地向當(dāng)前虛擬溶液中加入一定濃度、一定體積的這種溶液，模擬器會(huì)快速地算出倒入后虛擬溶液的濃度和體積。當(dāng)然，如果倒錯(cuò)了可以撤銷。模擬器的使用步驟如下：1）為模擬器設(shè)置一個(gè)初始體積和濃度V0、C0%。2）進(jìn)行一系列操作，模擬器支持兩種操作：P(v,c)操作：表示向當(dāng)前的虛擬溶液中加入體積為v濃度為c的溶液；Z操作：撤銷上一步的P操作。2021/10/1075【輸入格式】第一行兩個(gè)整數(shù)，表示V0和C0，0≤C0≤100；第二行一個(gè)整數(shù)n，表示操作數(shù)，n≤10000；接下來n行，每行一條操作，格式為：P_v_c或Z。其中_代表一個(gè)空格，當(dāng)只剩初始溶液的時(shí)候，再撤銷就沒有用了。任意時(shí)刻質(zhì)量不會(huì)超過2^31-1。【輸出格式】n行，每行兩個(gè)數(shù)Vi，Ci，其中Vi為整數(shù)，Ci為實(shí)數(shù)（保留5位小數(shù)）。其中，第i行表示第i次操作以后的溶液體積和濃度?！据斎霕永?001002P1000Z【輸出樣例】20050.00000100100.000002021/10/1076【問題分析】使用棧來模擬實(shí)現(xiàn)：1）讀入撤銷時(shí)，棧頂元素出棧。2）讀入溶液時(shí)，把新的溶液的體積和濃度壓棧。3）每次操作完，輸出棧頂?shù)捏w積和濃度。2021/10/1077//p7-7-2#include<bits/stdc++.h>usingnamespacestd;constintN=10010;structnode{intw;doublec;}a[N];intmain(){freopen(“simulator.in”,”r”,stdin);freopen(“simulator.out”,”w”,stdout);intv,n,c,top=1;cin>>v>>c>>n;a[top].w=v,a[top].c=c;//將初始溶液入棧while(n--){charch;cin>>ch;if(ch==‘Z’&&top>1)top--;//出棧if(ch==‘P’){cin>>v>>c;top++;a[top].w=a[top-1].w+v;//將新溶液的質(zhì)量入棧a[top].c=(a[top-1].w*a[top-1].c+v*c)/(double)a[top].w;//將新溶液的濃度入棧}cout<<a[top].w<<““;cout<<fixed<<setprecision(5)<<a[top].c<<endl;}return0;}2021/10/1078實(shí)踐鞏固2021/10/1079第8課棧的應(yīng)用學(xué)習(xí)目標(biāo)1.使用棧解決一些實(shí)際應(yīng)用問題。2.學(xué)會(huì)用棧實(shí)現(xiàn)簡(jiǎn)單的深度優(yōu)先搜索。2021/10/1080例1、括號(hào)匹配【問題描述】假設(shè)表達(dá)式中允許包含圓括號(hào)和方括號(hào)兩種括號(hào)，其嵌套的順序隨意，如（［］（））或［（［］［］）］等為正確的匹配，［（］）或（［］（）或（（）））均為錯(cuò)誤的匹配。本題的任務(wù)是檢驗(yàn)一個(gè)給定表達(dá)式中的括號(hào)是否正確匹配。輸入一個(gè)只包含圓括號(hào)和方括號(hào)的字符串，判斷字符串中的括號(hào)是否匹配，匹配就輸出“OK”，不匹配就輸出“Wrong”?！据斎敫袷健恳恍凶址?，只含有圓括號(hào)和方括號(hào)，個(gè)數(shù)小于255?！据敵龈袷健?/p>

匹配就輸出一行文本“OK”，不匹配就輸出一行文本“Wrong”?！据斎霕永縖(])【輸出樣例】Wrong2021/10/1081【問題分析】一個(gè)匹配的括號(hào)序列，必定是左、右圓括號(hào)、方括號(hào)的數(shù)量一樣多。但是反過來，一樣多不一定是匹配的。定義一個(gè)字符型的棧來維護(hù)左括號(hào)，按順序處理括號(hào)序列：1）遇到左括號(hào)：將它壓棧。2）遇到右括號(hào)：檢查棧頂元素與右括號(hào)是否匹配：如果匹配，將棧頂左括號(hào)出棧；否則，判斷出序列不匹配，結(jié)束。如果讀到了右括號(hào)，而棧為空，也不匹配。如果序列處理完畢，棧非空，也不匹配。具體程序參考教材267頁。2021/10/1082例2、表達(dá)式求值【問題描述】給定一個(gè)只包含加法和乘法的算術(shù)表達(dá)式，請(qǐng)編程計(jì)算表達(dá)式的值。【輸入格式】輸入僅有一行，為需要計(jì)算的表達(dá)式。表達(dá)式中只包含數(shù)字、加法運(yùn)算符“+”和乘法運(yùn)算符“*”，且沒有括號(hào)，所有參與運(yùn)算的數(shù)字均為0~2^31-1之間的整數(shù)。輸入數(shù)據(jù)保證這一行只有0~9、+、*這12種字符?！据敵龈袷健枯敵鲋挥幸恍?，包含一個(gè)整數(shù)，表示這個(gè)表達(dá)式的值。注意：當(dāng)答案長(zhǎng)度多于4位時(shí)，請(qǐng)只輸出最后4位，前導(dǎo)0不輸出。2021/10/1083【輸入樣例1】1+1*3+4【輸出樣例1】8【輸入樣例2】1+1234567890*1【輸出樣例2】7891【輸入樣例3】1+1000000003*1【輸出樣例3】42021/10/1084【輸入輸出樣例說明】樣例1計(jì)算的結(jié)果為8，直接輸出8。樣例2計(jì)算的結(jié)果為1234567891，輸出后4位，即7891。樣例3計(jì)算的結(jié)果為1000000004，輸出后4位，即4?！緮?shù)據(jù)范圍】對(duì)于30%的數(shù)據(jù)，0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤100。對(duì)于80%的數(shù)據(jù)，0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤1000。對(duì)于100%的數(shù)據(jù)，0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤100000。2021/10/1085【問題分析】由于只有加號(hào)和乘號(hào)，只要從左往右掃一遍，如果遇到乘號(hào)直接計(jì)算（做乘法）；如果遇到加號(hào)，若后面沒有符號(hào)或者后面一個(gè)符號(hào)也是加號(hào)，則直接計(jì)算（做加法）；否則，先把后面緊接著的連續(xù)的乘號(hào)算完，最后再加。算法實(shí)現(xiàn)中，只要設(shè)置一個(gè)棧保存沒有立即進(jìn)行的加法，掃描結(jié)束后再一起處理?xiàng)Ｖ械募臃ㄟ\(yùn)算；同時(shí)，因?yàn)榘岩粋€(gè)數(shù)字串轉(zhuǎn)換成數(shù)也需要單獨(dú)編寫一個(gè)子程序；最后，還要注意實(shí)現(xiàn)過程中及時(shí)對(duì)10000取模。具體程序參考教材269頁。2021/10/1086例3、圖的深度優(yōu)先遍歷【問題描述】讀入一個(gè)用鄰接矩陣存儲(chǔ)的無向圖，輸出它的深度優(yōu)先遍歷序列?！据斎敫袷健康?行1個(gè)正整數(shù)n，表示圖中的頂點(diǎn)數(shù)，2≤n≤100。接下來的n行是一個(gè)n×n的鄰接矩陣，a[i][j]=1表示頂點(diǎn)i和頂點(diǎn)j之間有直接邊相連，a[i][j]=0表示沒有直接邊相連。保證i=j時(shí)，a[i][j]=0，并且a[i][j]=a[j][i]?！据敵龈袷健枯敵?~n的某一種排列，表示從頂點(diǎn)1開始，對(duì)該圖進(jìn)行深度優(yōu)先遍歷得到的頂點(diǎn)序列，每?jī)蓚€(gè)數(shù)之間用一個(gè)“-”分隔。2021/10/1087【輸入樣例】80110000010011000100000110100010001000100000110000010000100100010【輸出樣例】1-2-4-6-5-3-7-82021/10/1088【問題分析】圖的深度優(yōu)先遍歷如圖7.8-1所示。用手工棧來實(shí)現(xiàn)圖的深度優(yōu)先遍歷：先任意找一個(gè)頂點(diǎn)入棧，即為棧頂元素，然后找到跟棧頂元素相連的一個(gè)頂點(diǎn)入棧，接著繼續(xù)把跟棧頂元素相連的一個(gè)頂點(diǎn)入棧，若棧頂元素沒有相連的頂點(diǎn)或者相連的頂點(diǎn)都已經(jīng)入過棧那么棧頂元素就出棧，循環(huán)操作直到棧為空，那么元素的入棧順序就是圖的深度優(yōu)先遍歷。具體程序參考教材270頁。2021/10/1089實(shí)踐鞏固2021/10/1090第9課哈希表學(xué)習(xí)目標(biāo)初步掌握哈希表的基本思想和簡(jiǎn)單應(yīng)用。2021/10/1091哈希表哈希表，也稱散列表，是一種高效的數(shù)據(jù)結(jié)構(gòu)。它的最大優(yōu)點(diǎn)就是把數(shù)據(jù)存儲(chǔ)和查找所消耗的時(shí)間大大降低，幾乎可