數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件全套 陳波 第1-9章 緒論、線性表-排序

2024/9/261數(shù)據(jù)結(jié)構(gòu)案例教程2024/9/262導(dǎo)學(xué)問(wèn)題1問(wèn)題中的數(shù)據(jù)在計(jì)算機(jī)中如何組織？（1-1）計(jì)算某位同學(xué)高等數(shù)學(xué)、英語(yǔ)及計(jì)算機(jī)導(dǎo)論三門(mén)課程的總分。（1-2）已知一個(gè)班級(jí)20名學(xué)生的高等數(shù)學(xué)成績(jī)，求全班該門(mén)課的平均分。（1-3）已知一個(gè)班級(jí)20名學(xué)生的高等數(shù)學(xué)、英語(yǔ)及計(jì)算機(jī)導(dǎo)論課程的成績(jī)，計(jì)算每位同學(xué)的總分以及全班三門(mén)課程各自的均分。2024/9/263導(dǎo)學(xué)問(wèn)題1問(wèn)題中的數(shù)據(jù)在計(jì)算機(jī)中如何組織？（1-4）在問(wèn)題1-3的基礎(chǔ)上，列出全班成績(jī)的排名（列出學(xué)號(hào)、姓名及分?jǐn)?shù)），如表1-1所示。2024/9/264導(dǎo)學(xué)問(wèn)題1問(wèn)題中的數(shù)據(jù)在計(jì)算機(jī)中如何組織？（1-5）假設(shè)一個(gè)U盤(pán)中有3個(gè)文件夾，每個(gè)文件夾中又有若干文件，如圖1-1所示。請(qǐng)?jiān)O(shè)計(jì)一種文件信息存儲(chǔ)方法，當(dāng)輸入某個(gè)文件名稱(chēng)后，顯示該文件在U盤(pán)中的存儲(chǔ)路徑，若U盤(pán)中無(wú)該文件，則顯示“文件未找到”。2024/9/265導(dǎo)學(xué)問(wèn)題1問(wèn)題中的數(shù)據(jù)在計(jì)算機(jī)中如何組織？（1-6）某城市中5個(gè)地標(biāo)建筑間有多條道路相通，每條道路長(zhǎng)度不同，如圖1-2所示。設(shè)計(jì)一個(gè)道路查詢(xún)系統(tǒng)，能讓游客查詢(xún)從任一個(gè)地標(biāo)建筑到另一個(gè)地標(biāo)建筑之間的最短路徑。2024/9/266導(dǎo)學(xué)問(wèn)題1的分析計(jì)算機(jī)處理的對(duì)象由數(shù)值發(fā)展到非數(shù)值數(shù)據(jù)，而且處理的數(shù)據(jù)量也越來(lái)越大。在程序設(shè)計(jì)時(shí)面對(duì)這樣的數(shù)據(jù)，需要解決如何表示這些數(shù)據(jù)間的結(jié)構(gòu)關(guān)系？如何在計(jì)算機(jī)中存儲(chǔ)這些數(shù)據(jù)？計(jì)算機(jī)處理的不再只是加減乘除等數(shù)值計(jì)算，而是排序、信息可視化、求最短路徑等較為復(fù)雜的非數(shù)值計(jì)算。在程序設(shè)計(jì)時(shí)，需要解決如何在問(wèn)題數(shù)據(jù)上進(jìn)行非數(shù)值計(jì)算等操作？以上這些問(wèn)題正是數(shù)據(jù)結(jié)構(gòu)這門(mén)課程研究的內(nèi)容。2024/9/267導(dǎo)學(xué)問(wèn)題2編程實(shí)現(xiàn)對(duì)輸入的整數(shù)n計(jì)算sum=1!+2!+3!+4!+…+n!doublesum(intn){doubles=0;inti,j;doublep;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++) p*=j;s+=p;}returns;}2024/9/268導(dǎo)學(xué)問(wèn)題2的分析可考慮將雙重循環(huán)，進(jìn)一步簡(jiǎn)化為單重循環(huán)：doublesum2(intn){doubles=0;inti;doublep=1;for(i=1;i<=n;i++){ p*=i; s+=p;}returns;}為什么用單重循環(huán)實(shí)現(xiàn)比用雙重循環(huán)實(shí)現(xiàn)有效？2024/9/2691.1知識(shí)學(xué)習(xí)1.1.1數(shù)據(jù)結(jié)構(gòu)課程的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)就是研究非數(shù)值計(jì)算問(wèn)題中的數(shù)據(jù)以及它們之間的關(guān)系和操作算法的學(xué)科，具體主要包含3個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）和數(shù)據(jù)的操作算法。2024/9/26101.1知識(shí)學(xué)習(xí)1.1.2數(shù)據(jù)的結(jié)構(gòu)相關(guān)術(shù)語(yǔ)

數(shù)據(jù)

數(shù)據(jù)元素

數(shù)據(jù)對(duì)象數(shù)據(jù)結(jié)構(gòu)的三個(gè)要素

數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)要素，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作算法2024/9/26111.1知識(shí)學(xué)習(xí)1.1.3算法與算法分析1.什么是算法2.算法的評(píng)價(jià)3.算法的描述方法2024/9/2612算法性能分析與度量算法的性能標(biāo)準(zhǔn)算法的事前估計(jì)算法的后期測(cè)試2024/9/2613算法性能分析與度量算法的性能標(biāo)準(zhǔn)正確性健壯性可讀性高效率低存儲(chǔ)空間算法的事前估計(jì)算法的后期測(cè)試2024/9/2614

算法性能分析與度量算法的性能標(biāo)準(zhǔn)算法的事前估計(jì)時(shí)間復(fù)雜度空間復(fù)雜度算法的后期測(cè)試2024/9/2615算法性能分析與度量算法的性能標(biāo)準(zhǔn)算法的事前估計(jì)時(shí)間復(fù)雜度空間復(fù)雜度存儲(chǔ)空間的固定部分

程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分(如數(shù)組元素、結(jié)構(gòu)成分、對(duì)象的數(shù)據(jù)成員等)變量所占的空間可變部分

尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用的空間、通過(guò)new和delete命令動(dòng)態(tài)使用的空間2024/9/26161.2知識(shí)應(yīng)用導(dǎo)學(xué)問(wèn)題1-4的數(shù)據(jù)結(jié)構(gòu)2024/9/26171.2知識(shí)應(yīng)用導(dǎo)學(xué)問(wèn)題1-5的數(shù)據(jù)結(jié)構(gòu)2024/9/26181.2知識(shí)應(yīng)用導(dǎo)學(xué)問(wèn)題1-6的數(shù)據(jù)結(jié)構(gòu)2024/9/26191.2知識(shí)應(yīng)用導(dǎo)學(xué)問(wèn)題2的時(shí)間復(fù)雜度問(wèn)題2的原始程序是一個(gè)雙重循環(huán)，其中外循環(huán)體中的語(yǔ)句p=1;執(zhí)行次數(shù)為n；外循環(huán)體中的語(yǔ)句s+=p;執(zhí)行次數(shù)為n；內(nèi)循環(huán)體中語(yǔ)句p*=j;的執(zhí)行次數(shù)為：1+2+3+…+n=n(n+1)/2；因此該程序的基本語(yǔ)句執(zhí)行次數(shù)是n2數(shù)量級(jí)，時(shí)間復(fù)雜度T(n)=O(n2)。改進(jìn)后的程序是一個(gè)單重循環(huán)，循環(huán)體中的語(yǔ)句p*=j;和s+=p;分別執(zhí)行了n次，因此該程序的基本語(yǔ)句執(zhí)行次數(shù)是n數(shù)量級(jí)，時(shí)間復(fù)雜度T(n)=O(n)。2024/9/26201.3知識(shí)拓展算法時(shí)間復(fù)雜度的分析實(shí)例算法執(zhí)行時(shí)間的測(cè)試2024/9/2621小結(jié)數(shù)據(jù)結(jié)構(gòu)研究實(shí)際問(wèn)題中涉及到的數(shù)據(jù)的邏輯組織。數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)在計(jì)算機(jī)中如何存儲(chǔ)、處理。數(shù)據(jù)結(jié)構(gòu)研究的核心是數(shù)據(jù)的各種處理方法和技巧。第2章線性表2024/9/2623導(dǎo)學(xué)問(wèn)題1：簡(jiǎn)易的學(xué)生信息管理系統(tǒng)實(shí)現(xiàn)一個(gè)簡(jiǎn)易的學(xué)生信息管理系統(tǒng)，其中學(xué)生信息包括：學(xué)號(hào)、姓名、性別、年齡、專(zhuān)業(yè)等。要求系統(tǒng)能提供建立、查詢(xún)、刪除和增加學(xué)生信息等功能。2024/9/2624導(dǎo)學(xué)問(wèn)題2：簡(jiǎn)易的商品信息管理系統(tǒng)實(shí)現(xiàn)一個(gè)簡(jiǎn)易的商品信息管理系統(tǒng)，其中商品信息包括：商品代碼、品名、單價(jià)、庫(kù)存量等。要求系統(tǒng)能提供建立、查詢(xún)、刪除和增加商品信息等功能。2024/9/2625程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種合適的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，并設(shè)計(jì)基于此結(jié)構(gòu)上的一批高效的處理算法。因此，首先需要分析實(shí)際問(wèn)題中需要處理的數(shù)據(jù)對(duì)象的特點(diǎn)。問(wèn)題分析2024/9/2626學(xué)生信息表問(wèn)題分析2024/9/2627商品信息表問(wèn)題分析2024/9/2628考慮：數(shù)據(jù)元素之間的關(guān)系是什么？——數(shù)據(jù)如何表示？數(shù)據(jù)元素如何存儲(chǔ)？數(shù)據(jù)元素如何處理？2024/9/26292.1知識(shí)學(xué)習(xí)2.1.1線性表的概念線性表是具有相同數(shù)據(jù)類(lèi)型的n（n≥0）個(gè)數(shù)據(jù)元素組成的有限序列，通常記為L(zhǎng)=(a1，a2，…，ai

1，ai，ai+1，…，an)a1a3a4ana22024/9/26302.1知識(shí)學(xué)習(xí)非空線性表的特性有且僅有一個(gè)表頭結(jié)點(diǎn)a1，它沒(méi)有前驅(qū)，而僅有一個(gè)后繼a2；（2）有且僅有一個(gè)表尾結(jié)點(diǎn)an，它沒(méi)有后繼，而僅有一個(gè)前驅(qū)an－1；（3）其余的結(jié)點(diǎn)ai（2≤i≤n

1）都有且僅有一個(gè)前驅(qū)a

i－1和一個(gè)后繼a

i+1。2.1.1線性表的概念2024/9/26312.1知識(shí)學(xué)習(xí)2.1.2線性表的順序存儲(chǔ)結(jié)構(gòu)及基本操作2.1.2.1順序結(jié)構(gòu)342367434存儲(chǔ)要點(diǎn)用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素例：（34,23,67,43）2024/9/2632例：（34,23,67,43）34236743存儲(chǔ)空間的起始位置4用什么屬性來(lái)描述順序表？順序表的容量（最大長(zhǎng)度）順序表的當(dāng)前長(zhǎng)度2024/9/26332.1知識(shí)學(xué)習(xí)2.1.2線性表的順序存儲(chǔ)結(jié)構(gòu)及基本操作2.1.2.1順序結(jié)構(gòu)數(shù)據(jù)元素為整型數(shù)的順序表類(lèi)型描述。constintMAXSIZE=100;//順序表最大長(zhǎng)度typedefstruct{ intdata[MAXSIZE];//存放數(shù)據(jù)元素的數(shù)組 intlength;//順序表的長(zhǎng)度}SeqList;2024/9/2634算法描述：voidInitList_Seq(SeqList&L){L.length=0;}初始化操作——?jiǎng)?chuàng)建空表

datalength02.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2635初始化操作——?jiǎng)?chuàng)建長(zhǎng)度為n的順序表2.1.2.2順序表基本操作的實(shí)現(xiàn)順序表

數(shù)組a351224334253512243342算法描述：voidCreatList_Seq(SeqList&L,inta[],intn){if(n>L.MAXSIZE){cout<<"參數(shù)超出順序表容量"<<endl;exit(1);}

L.length=0;

for(inti=0;i<n;i++)

L.data[L.length++]=a[i];}2024/9/2636遍歷順序表2.1.2.2順序表基本操作的實(shí)現(xiàn)voidShow_Seq(SeqList&L){ for(inti=0;i<L.length;i++) cout<<L.data[i]<<""; cout<<endl;}

算法描述：2024/9/2637求順序表長(zhǎng)度2.1.2.2順序表基本操作的實(shí)現(xiàn)intListLength_Seq(SeqList&L){ returnL.length;}算法描述：2024/9/2638按值查找元素：535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值為12的元素，返回在表中的序號(hào)。iii注意序號(hào)和下標(biāo)之間的關(guān)系2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2639intLocateElem_Seq(SeqListL,inte){for(inti=0;i<L.length;i++) if(L.data[i]==e) returni+1;

return0;}按值查找算法描述：時(shí)間復(fù)雜度？2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2640插入操作2.1.2.2順序表基本操作的實(shí)現(xiàn)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,e

,ai,…,an)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系2024/9/264133例：（35，12，24，42），在i=2的位置上插入33。表滿(mǎn)：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序號(hào)）435122442a1a2a3a401234422412335什么時(shí)候不能插入？注意邊界條件2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/26422.1.2.2順序表基本操作的實(shí)現(xiàn)插入操作算法描述①檢查順序表的存儲(chǔ)空間是否已到最大值（被占滿(mǎn)），若是，則停止插入，并給出“上溢”出錯(cuò)提示；否則，執(zhí)行第②步。②檢查插入位置i是否合法，若不合法，則停止插入，并給出“插入位置非法”出錯(cuò)提示；否則，執(zhí)行第③步。③從最后一個(gè)元素向前直至第i個(gè)元素（下標(biāo)為i

1）為止，將每一個(gè)元素均后移一個(gè)存儲(chǔ)單元，將第i個(gè)元素的存儲(chǔ)位置空出。④將新元素e寫(xiě)入到第i個(gè)元素處，即下標(biāo)為i

1的位置。⑤將順序表長(zhǎng)度加1。2024/9/2643插入操作算法描述：2.1.2.2順序表基本操作的實(shí)現(xiàn)voidListInsert_Seq(SeqList&L,inti,inte){ if(L.length>=MAXSIZE)

{cout<<"線性表已滿(mǎn)"<<endl;exit(1);} if(i<1||i>L.length+1)

{cout<<"i值不合法"<<endl;exit(1);}

for(intj=L.length-1;j>=i-1;j--)

L.data[j+1]=L.data[j];

L.data[i-1]=e;

L.length++;}

2024/9/2644最好情況（i=n+1）：基本語(yǔ)句執(zhí)行0次，時(shí)間復(fù)雜度為O(1)。最壞情況（i=1）：基本語(yǔ)句執(zhí)行n+1次，時(shí)間復(fù)雜度為O(n)。平均情況（1≤i≤n+1）：時(shí)間復(fù)雜度為O(n)。插入算法時(shí)間性能分析：?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2645刪除操作：刪除前：(a1,…,ai-1,ai,ai+1,…,an)刪除后：(a1,…,ai-1,ai+1,…,an)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化2.1.2.2

順序表基本操作的實(shí)現(xiàn)2024/9/2646例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出算法的描述；3.分析時(shí)間復(fù)雜度。535a1a2a3a401234422412334a51224422.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2647刪除操作算法描述：2.1.2.2順序表基本操作的實(shí)現(xiàn)voidListDelete_Seq(SeqList&L,inti,int&e){ if((i<1)||(i>L.length))

{cout<<"i值不合法"<<endl;exit(1);} e=L.data[i-1]; for(intj=i;j<L.length;j++)

L.data[j-1]=L.data[j];

L.length--;}2024/9/26482.1.2.3順序表基本操作的優(yōu)化（1）增強(qiáng)通用性（2）增強(qiáng)靈活性（3）增強(qiáng)適應(yīng)性2024/9/26492.1.3線性表的鏈接存儲(chǔ)及基本操作鏈表：線性表的鏈接存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)思想：用一組任意的存儲(chǔ)單元存放線性表的元素。靜態(tài)存儲(chǔ)分配順序表事先確定容量鏈表動(dòng)態(tài)存儲(chǔ)分配運(yùn)行時(shí)分配空間連續(xù)不連續(xù)零散分布2024/9/26502.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例：(a1,a2

,a3,a4)的存儲(chǔ)示意圖存儲(chǔ)特點(diǎn)：邏輯次序和物理次序不一定相同。元素之間的邏輯關(guān)系用指針表示。0200020803000325…………a10200a20325a30300a4∧2024/9/26510200020803000325…………a10200a20325a30300a4∧結(jié)點(diǎn)數(shù)據(jù)域指針域單鏈表是由若干結(jié)點(diǎn)構(gòu)成的；單鏈表的結(jié)點(diǎn)只有一個(gè)指針域。data：存儲(chǔ)數(shù)據(jù)元素next：存儲(chǔ)指向后繼結(jié)點(diǎn)的地址datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：數(shù)據(jù)域指針域2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2652typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：如何申請(qǐng)一個(gè)結(jié)點(diǎn)？2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2653s=newNode;typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：……sNode2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2654s=newNode;datanext……sNode如何引用數(shù)據(jù)元素？s->data;(*s).data;data如何引用指針域？nexts->next;2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/26550200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表頭指針：指向第一個(gè)結(jié)點(diǎn)的地址。尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭铡?.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/26560200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表空表和非空表不統(tǒng)一，缺點(diǎn)？如何將空表與非空表統(tǒng)一？2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2657頭結(jié)點(diǎn)：在單鏈表的第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類(lèi)型相同的結(jié)點(diǎn)，以便空表和非空表處理統(tǒng)一。非空表heada1a2an∧空表head∧2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/26582.1.3.2單鏈表基本操作的實(shí)現(xiàn)voidInitList_L(LinkList&L){ L=newNode; L->next=NULL;}初始化——?jiǎng)?chuàng)建空的單鏈表2024/9/26592.1.3.2單鏈表基本操作的實(shí)現(xiàn)voidCreateList_L(LinkList&L,ElemTypea[],intn){

LinkLists;

L=newNode;L->next=NULL;for(inti=n-1;i>=0;i--)

{s=newNode;s->data=a[i];

s->next=L->next;L->next=s;}}初始化——用數(shù)組a中的n個(gè)元素創(chuàng)建單鏈表2024/9/26602.1.3.2單鏈表基本操作的實(shí)現(xiàn)voidShow_L(LinkListL){ LinkListp=L->next; while(p) { cout<<p->data<<"";//輸出結(jié)點(diǎn)數(shù)據(jù)域 p=p->next; } cout<<endl;}遍歷單鏈表2024/9/26612.1.3.2單鏈表基本操作的實(shí)現(xiàn)intListLength_L(LinkListL){LinkListp=L->next;intk=0;while(p)

{k++;//計(jì)數(shù)p=p->next;}returnk;}求單鏈表長(zhǎng)度。2024/9/26622.1.3.2單鏈表基本操作的實(shí)現(xiàn)intLocateElem_L(LinkListL,ElemTypee){LinkListp=L->next;

intindex=1;while(p&&p->data!=e)

{p=p->next;

index++;}

if(p)returnindex;

elsereturn0;}按值查找。2024/9/2663插入操作：

voidListInsert_L(LinkListL,inti,ElemTypee)如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1、e和ai之間邏輯關(guān)系的變化？pesheada1ai-1an∧ai算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2664注意分析邊界情況——表頭、表尾。

heada1an∧aipes算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;pxs∧由于單鏈表帶頭結(jié)點(diǎn)，表頭、表中、表尾三種情況的操作語(yǔ)句一致。

2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2665算法描述——偽代碼1.工作指針p初始化；累加器j清零；

2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；3.若查找不成功，說(shuō)明插入位置不合理，拋出插入位置異常；否則，

3.1生成一個(gè)元素值為e的新結(jié)點(diǎn)s；

3.2將新結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后；2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2666

voidListInsert_L(LinkListL,inti,ElemTypee){ LinkListp=L,s; intj=0; while(p&&j<i-1){ p=p->next; j++; }

算法描述

if(!p){cout<<"插入位置非法";exit(1);}else{

s=newNode; s->data=e;

s->next=p->next;

p->next=s; }}，基本語(yǔ)句？時(shí)間復(fù)雜度？2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2667刪除操作接口：voidListDelete_L(LinkListL,inti);p如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1和ai之間邏輯關(guān)系的變化？heada1ai-1ai+1ai算法描述：q=p->next;p->next=q->next;deleteq;q2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2668算法描述：q=p->next;p->next=q->next;deleteq;注意分析邊界情況——表頭、表尾。

pqpq表尾的特殊情況：雖然被刪結(jié)點(diǎn)不存在，但其前驅(qū)結(jié)點(diǎn)卻存在。p->next=NULLheada1ana2∧2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2669算法描述——偽代碼1.工作指針p初始化；累加器j清零；2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；3.若p不存在或p不存在后繼結(jié)點(diǎn)，則拋出位置異常；否則，否則刪除結(jié)點(diǎn)p的后一個(gè)結(jié)點(diǎn)。2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2670voidListDelete_L(LinkListL,inti){ LinkListp=L,q; intj=0; while(p&&j<i-1){ p=p->next; j++;}算法描述

if(!p||!p->next){cout<<"刪除位置非法";exit(1);}

else

{

q=p->next;

p->next=q->next;

deleteq;

}}2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2671將單鏈表中所有結(jié)點(diǎn)的存儲(chǔ)空間釋放。

單鏈表的銷(xiāo)毀操作：heada1a2an∧aipq算法描述：q=p;p=p->next;deleteq;p注意：保證鏈表未處理的部分不斷開(kāi)

2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2672voidDestroyList_L(LinkList&L){

LinkListp=L,q; while(p) { q=p; p=p->next; deleteq; } L=NULL;}2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/26732.2知識(shí)應(yīng)用2024/9/26742.2知識(shí)應(yīng)用2024/9/2675voidUnion(SeqList&La,SeqList&Lb){intLa_len=ListLength_Seq(La);//求線性表La的長(zhǎng)度ElemTypee;

while(Lb.length!=0)//Lb表的元素尚未處理完

{

ListDelete_Seq(Lb,1,e);//從Lb中刪除第一個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem_Seq(La,e))//若La中不存在值和e相等的元素，ListInsert_Seq(La,++La_len,e);//則將它插入到La的最后

}}2.3知識(shí)拓展——順序表的其他操作求集合的并集：2024/9/2676voidOrdInsert_Seq(SeqList&L,ElemTypex){

if(L.length>=MAXSIZE){cout<<"線性表已滿(mǎn)"<<endl;exit(1);}

inti=0;while(L.data[i]<=x&&i<L.length)//查找插入位置i

i++;

for(intj=L.length-1;j>=i;j--)//元素后移

L.data[j+1]=L.data[j];

L.data[i]=x;//插入元素x

L.length++;//表長(zhǎng)增1}2.3知識(shí)拓展——順序表的其他操作有序表的插入：2024/9/2677voidInvertLinkedList(LinkList&L)//逆置頭指針L所指鏈表{LinkLists,p=L->next;

L->next=NULL;//設(shè)逆置后的鏈表的初態(tài)為空表while(p){//p為待逆置鏈表的頭指針s=p;p=p->next;//從p所指鏈表中刪除第一個(gè)結(jié)點(diǎn)(s結(jié)點(diǎn))s->next=L->next;L->next=s;//將s結(jié)點(diǎn)插入到逆置表的表頭}}2.3

知識(shí)拓展——單鏈表的其他操作單鏈表的逆置：2024/9/2678voidMergeLinkList(LinkList&La,LinkList&Lb){LinkListpa=La->next;//pa指向La中當(dāng)前考察的結(jié)點(diǎn)LinkListpb=Lb->next;//pb指向Lb中當(dāng)前考察的結(jié)點(diǎn)LinkListpc=La;//pc指向Lc中當(dāng)前的表尾結(jié)點(diǎn)while(pa!=NULL&&pb!=NULL)

{if(pa->data<pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}else

{

pc->next=pb;pc=pb;pb=pb->next;}}if(pa)pc->next=pa;elsepc->next=pb;deleteLb;}2.3

知識(shí)拓展——單鏈表的其他操作合并有序單鏈表：2024/9/2679順序表和單鏈表的比較存儲(chǔ)分配方式比較順序表采用順序存儲(chǔ)結(jié)構(gòu)，即用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過(guò)存儲(chǔ)位置來(lái)實(shí)現(xiàn)。單鏈表采用鏈接存儲(chǔ)結(jié)構(gòu)，即用一組任意的存儲(chǔ)單元存放線性表的元素。用指針來(lái)反映數(shù)據(jù)元素之間的邏輯關(guān)系。2024/9/2680順序表和單鏈表的比較時(shí)間性能比較時(shí)間性能是指實(shí)現(xiàn)基于某種存儲(chǔ)結(jié)構(gòu)的基本操作（即算法）的時(shí)間復(fù)雜度。按位查找：順序表的時(shí)間為Ｏ(1)，是隨機(jī)存??；單鏈表的時(shí)間為Ｏ(n)，是順序存取。插入和刪除：順序表需移動(dòng)表長(zhǎng)一半的元素，時(shí)間為Ｏ(n)；單鏈表不需要移動(dòng)元素，在給出某個(gè)合適位置的指針后，插入和刪除操作所需的時(shí)間僅為Ｏ(1)。2024/9/2681順序表和單鏈表的比較空間性能比較空間性能是指某種存儲(chǔ)結(jié)構(gòu)所占用的存儲(chǔ)空間的大小。定義結(jié)點(diǎn)的存儲(chǔ)密度：數(shù)據(jù)域占用的存儲(chǔ)量整個(gè)結(jié)點(diǎn)占用的存儲(chǔ)量存儲(chǔ)密度＝2024/9/2682順序表和單鏈表的比較空間性能比較結(jié)點(diǎn)的存儲(chǔ)密度：順序表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)密度為1（只存儲(chǔ)數(shù)據(jù)元素），沒(méi)有浪費(fèi)空間；單鏈表的每個(gè)結(jié)點(diǎn)的存儲(chǔ)密度<1（包括數(shù)據(jù)域和指針域），有指針的結(jié)構(gòu)性開(kāi)銷(xiāo)。整體結(jié)構(gòu)：順序表需要預(yù)分配存儲(chǔ)空間，如果預(yù)分配得過(guò)大，造成浪費(fèi)，若估計(jì)得過(guò)小，又將發(fā)生上溢；單鏈表不需要預(yù)分配空間，只要有內(nèi)存空間可以分配，單鏈表中的元素個(gè)數(shù)就沒(méi)有限制。2024/9/2683順序表和單鏈表的比較⑴若線性表需頻繁查找卻很少進(jìn)行插入和刪除操作，或其操作和元素在表中的位置密切相關(guān)時(shí)，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)；若線性表需頻繁插入和刪除時(shí)，則宜采用單鏈表做存儲(chǔ)結(jié)構(gòu)。⑵當(dāng)線性表中元素個(gè)數(shù)變化較大或者未知時(shí)，最好使用單鏈表實(shí)現(xiàn)；而如果用戶(hù)事先知道線性表的大致長(zhǎng)度，使用順序表的空間效率會(huì)更高?？傊?，線性表的順序?qū)崿F(xiàn)和鏈表實(shí)現(xiàn)各有其優(yōu)缺點(diǎn)，不能籠統(tǒng)地說(shuō)哪種實(shí)現(xiàn)更好，只能根據(jù)實(shí)際問(wèn)題的具體需要，并對(duì)各方面的優(yōu)缺點(diǎn)加以綜合平衡，才能最終選定比較適宜的實(shí)現(xiàn)方法。第3章操作受限的線性表：棧和隊(duì)列導(dǎo)學(xué)問(wèn)題1：數(shù)制轉(zhuǎn)換問(wèn)題【問(wèn)題描述】

已知十進(jìn)制數(shù)n，試將其轉(zhuǎn)換成對(duì)應(yīng)的八進(jìn)制數(shù)?！痉治觥恳詎=1269為例

計(jì)算過(guò)程中，取余數(shù)的順序正好與計(jì)算產(chǎn)生余數(shù)的順序相反的，因此可將每次產(chǎn)生的余數(shù)依次保存起來(lái)，轉(zhuǎn)換結(jié)束后，再按保存的逆序取出余數(shù)打印即可。

顯然，保存的余數(shù)應(yīng)該具備“后進(jìn)先出”的特點(diǎn)，可用棧作為數(shù)據(jù)結(jié)構(gòu)。導(dǎo)學(xué)問(wèn)題2：銀行排隊(duì)問(wèn)題【問(wèn)題描述】

請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡(jiǎn)單的模擬銀行排隊(duì)系統(tǒng)，要求程序具有三項(xiàng)菜單：1）取號(hào)。選擇該菜單后，為客戶(hù)產(chǎn)生一個(gè)排隊(duì)號(hào)。2）叫號(hào)。選擇該菜單后，顯示可服務(wù)的客戶(hù)排隊(duì)號(hào)。3）退出系統(tǒng)。【分析】

銀行排隊(duì)問(wèn)題屬于典型的先來(lái)先服務(wù)，因此需要將產(chǎn)生的排隊(duì)號(hào)存放在具有“先進(jìn)先出”特性的數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列結(jié)構(gòu)可以滿(mǎn)足要求。

3.1棧3.1.1知識(shí)學(xué)習(xí)棧：限定僅在表尾進(jìn)行插入和刪除操作的線性表。空棧：不含任何數(shù)據(jù)元素的棧。允許插入和刪除的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。（a1,a2,……,an）棧頂棧底abc入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖3.1棧棧的操作特性：后進(jìn)先出abc入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂3.1棧棧的示意圖例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：3.1棧例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂情況2：3.1棧出棧序列：b棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？3.1棧如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top棧的順序存儲(chǔ)結(jié)構(gòu)及基本操作出棧：top減1進(jìn)棧：top加1棧空：top=-1

012345678a1topa2topa3top棧滿(mǎn)：top=MaxSize-1棧的順序存儲(chǔ)及基本操作constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; inttop;}SeqStack;順序棧的類(lèi)型定義voidInitStack(SeqStack&S){S.top=-1;}順序棧的實(shí)現(xiàn)——初始化voidPush(SeqStack&S,ElemTypex){if(S.top==MAXSIZE-1){cout<<"棧已滿(mǎn)"<<endl;exit(1);}

S.top++;

S.data[S.top]=x;}順序棧的實(shí)現(xiàn)——入棧ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"棧已空"<<endl;exit(1);}

ElemTypex=S.data[S.top];

S.top--; returnx;}順序棧的實(shí)現(xiàn)——出棧ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"棧已空"<<endl;exit(1);}

returnS.data[S.top];}順序棧的實(shí)現(xiàn)——取棧頂元素boolStackEmpty(SeqStack&S){ returnS.top==-1;}順序棧的實(shí)現(xiàn)——判斷?？誦oolStackEmpty(SeqStack&S){ returnS.top==MAXSIZE-1;}順序棧的實(shí)現(xiàn)——判斷棧滿(mǎn)heada1a2an∧ai鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。棧的鏈?zhǔn)酱鎯?chǔ)及基本操作棧頂棧底鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)topanan-1a1∧兩種示意圖在內(nèi)存中對(duì)應(yīng)同一種狀態(tài)topa1an-1an∧棧頂棧底棧的鏈?zhǔn)酱鎯?chǔ)及基本操作typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}*LinkStack;鏈棧的類(lèi)型定義voidInitStack(LinkStack&S){ S=NULL;}鏈棧的實(shí)現(xiàn)——初始化算法描述：voidPush(LinkStack&S,ElemTypex){LinkStackp=newNode;

p->data=x;

p->next=S;

S=p;}Sanan-1a1∧xpS鏈棧的實(shí)現(xiàn)——入棧算法描述：ElemTypePop(LinkStack&S){

if(S==NULL)

{cout<<"棧已空";exit(1);}

ElemTypex=S->data;//暫存棧頂元素

LinkStackp=S;

S=S->next;//刪除棧頂結(jié)點(diǎn)

deletep;

returnx;}Sanan-1a1∧Sp

鏈棧的實(shí)現(xiàn)——出棧ElemTypeTop(LinkStack&S){ if(S==NULL) {cout<<"棧已空";exit(1);} returnS->data;}鏈棧的實(shí)現(xiàn)——取棧頂元素boolStackEmpty(LinkStack&S){ returnS==NULL;}鏈棧的實(shí)現(xiàn)——判斷棧空voidDestroyListStack(LinkStack&S){LinkStackp;

while(S)

{

p=S;

S=S->next;

deletep;

}}鏈棧的實(shí)現(xiàn)——銷(xiāo)毀順序棧和鏈棧的比較時(shí)間性能：相同，都是常數(shù)時(shí)間O(1)?？臻g性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題。鏈棧：沒(méi)有棧滿(mǎn)的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空間時(shí)才會(huì)出現(xiàn)棧滿(mǎn)，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開(kāi)銷(xiāo)?？傊?，當(dāng)棧的使用過(guò)程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。3.1.2知識(shí)應(yīng)用——導(dǎo)學(xué)問(wèn)題1voidconversion(intn){SeqStackS;InitStack(S);while(n){Push(S,n%8);n=n/8;}while(!StackEmpty(S))cout<<Pop(S);cout<<endl;}3.1.3知識(shí)拓展——算術(shù)表達(dá)式求值1、中綴表達(dá)式直接求值為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)工作棧：

1）運(yùn)算符OPTR棧,用以寄存運(yùn)算符；2）操作數(shù)OPND棧,用以寄存操作數(shù)或運(yùn)算結(jié)果。算法步驟：參見(jiàn)教材3.1.3知識(shí)拓展——算術(shù)表達(dá)式求值2、利用后綴表達(dá)式求值

將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí)，表達(dá)式中操作數(shù)次序不變，而操作符次序會(huì)發(fā)生變化，同時(shí)需要去掉圓括號(hào)。因此設(shè)置一個(gè)棧OPTR用以存放操作符。。算法步驟：參見(jiàn)教材3.1.3知識(shí)拓展——棧和遞歸求階乘的遞歸算法intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}3.1.3知識(shí)拓展——棧和遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程⑴運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；⑵每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；⑶每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。3.1.3知識(shí)拓展——棧和遞歸哪些問(wèn)題可以用遞歸解決大問(wèn)題可以分解為小問(wèn)題可以確定遞歸到何時(shí)終止3.2隊(duì)列3.2.1知識(shí)學(xué)習(xí)隊(duì)列的基本概念

隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。隊(duì)尾隊(duì)頭a1a2a3入隊(duì)出隊(duì)隊(duì)列的操作特性：先進(jìn)先出constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; intrear;}SeqQueue;隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（1）循環(huán)隊(duì)列的初始化voidInitQueue(SeqQueue&Q){Q.front=Q.rear=0;}（2）循環(huán)隊(duì)列的入隊(duì)操作voidEnQueue(SeqQueue&Q,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {cout<<"隊(duì)列已滿(mǎn)"<<endl;exit(1);}Q.rear=(Q.rear+1)%MAXSIZE; Q.data[Q.rear]=x;

}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（3）循環(huán)隊(duì)列的出隊(duì)操作ElemTypeDeQueue(SeqQueue&Q){if(Q.front==Q.rear) {cout<<"隊(duì)列已空"<<endl;exit(1);} Q.front=(Q.front+1)%MAXSIZE; ElemTypex=Q.data[Q.front];returnx;}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（4）判斷循環(huán)隊(duì)列是否為空的操作boolQueueEmpty(SeqQueue&Q){ returnQ.front==Q.rear;}（5）判斷循環(huán)隊(duì)列是否為滿(mǎn)的操作boolQueueFull(SeqQueue&Q){ return(Q.rear+1)%MAXSIZE==Q.front;}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)隊(duì)頭指針即為鏈表的頭指針heada1a2an∧如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？rearfront隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）非空鏈隊(duì)列fronta1a2an∧rear空鏈隊(duì)列front∧rear隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstruct{ Node*front; Node*rear;}LinkQueue;隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）voidInitQueue(LinkQueue&Q){Q.front=Q.rear=newNode; Q.front->next=NULL;}front∧rear鏈隊(duì)列的操作——初始化xpfronta1an∧rearrearfrontxp∧∧rearrear算法描述：p->next=NULL;rear->next=p;rear=p;有了頭結(jié)點(diǎn)兩種情況下的處理是一致的。鏈隊(duì)列的操作——入隊(duì)∧voidEnQueue(LinkQueue&Q,ElemTypex){

Node*p=newNode;//產(chǎn)生新結(jié)點(diǎn)p p->data=x; p->next=NULL; Q.rear->next=p;//將結(jié)點(diǎn)p插入到隊(duì)尾 Q.rear=p; }鏈隊(duì)列的操作——入隊(duì)fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;鏈隊(duì)列的操作——出隊(duì)fronta1a2an∧rearp考慮邊界情況：隊(duì)列中只有一個(gè)元素？fronta1p∧rear∧rear僅1個(gè)元素的隊(duì)列判斷：if(rear==p)rear=front;如何判斷邊界情況？鏈隊(duì)列的操作——出隊(duì)ElemTypeDeQueue(LinkQueue&Q){

if(Q.front==Q.rear)

{cout<<"隊(duì)列已空"<<endl;exit(1);} Node*p=Q.front->next; ElemTypex=p->data; Q.front->next=p->next; if(Q.rear==p)

Q.rear=Q.front;

deletep; returnx; }鏈隊(duì)列的操作——出隊(duì)boolQueueEmpty(LinkQueue&Q){ returnQ.front==Q.rear;}鏈隊(duì)列的操作——判斷隊(duì)空voidDestroyListQueue(LinkQueue&Q){while(Q.front) { Q.rear=Q.front->next; deleteQ.front; Q.front=Q.rear; }}鏈隊(duì)列的操作——銷(xiāo)毀

銀行排隊(duì)其實(shí)就是隊(duì)列的操作，取號(hào)對(duì)應(yīng)的是入隊(duì)操作，叫號(hào)對(duì)應(yīng)的是出隊(duì)操作。為了完成導(dǎo)學(xué)問(wèn)題2，可首先創(chuàng)建一個(gè)隊(duì)列，有客戶(hù)選擇“取號(hào)”功能時(shí)，產(chǎn)生一個(gè)排隊(duì)序號(hào)，并將該序號(hào)加入隊(duì)列中；當(dāng)服務(wù)員選擇“叫號(hào)”功能時(shí)，從隊(duì)列頭部取出一個(gè)排隊(duì)序號(hào)即可。3.2.2知識(shí)應(yīng)用——導(dǎo)學(xué)問(wèn)題2的實(shí)現(xiàn)3.2.3知識(shí)拓展打印任務(wù)隊(duì)列管理步驟如下：①創(chuàng)建隊(duì)列并設(shè)置需打印任務(wù)的位置flag，初始化打印時(shí)間time；②依次將隊(duì)頭任務(wù)e出隊(duì)，重置需打印任務(wù)位置flag，并將e與隊(duì)列的最高優(yōu)先級(jí)別max進(jìn)行比較：

若e<max，則將任務(wù)e移至隊(duì)尾，移動(dòng)的任務(wù)為需要打印的任務(wù)，則重置需打印任務(wù)的位置flag；

若e>=max，打印時(shí)間time增1（表示該任務(wù)完成打印），若e為需要打印的任務(wù)，則執(zhí)行步驟3）；③顯示打印時(shí)間time。第4章元素受限的線性表：串導(dǎo)學(xué)問(wèn)題——微信中的安全提醒微信（WeChat）是騰訊公司于2011年推出的一個(gè)為智能終端提供即時(shí)通訊服務(wù)的免費(fèi)應(yīng)用程序，人們通過(guò)微信可以進(jìn)行便捷的交流。然而，微信中的詐騙信息也讓人們深受其害。為了提醒微信用戶(hù)免受欺騙，新版微信設(shè)置了安全提示功能，當(dāng)與微信好友聊天中提及帳號(hào)、密碼、財(cái)物等敏感信息時(shí)，微信會(huì)立即彈出安全提示，提醒大家注意，如圖所示。請(qǐng)編寫(xiě)程序，模擬簡(jiǎn)單的微信安全提示功能。4.1知識(shí)學(xué)習(xí)4.1.1串的基本概念串：由零個(gè)或多個(gè)任意字符組成的有限序列。串長(zhǎng)度：串中所包含的字符個(gè)數(shù)?？沾洪L(zhǎng)度為0的串，記為：""。非空串通常記為：

S=“a1a2…an”

其中：S是串名，雙引號(hào)是定界符，雙引號(hào)引起來(lái)的部分是串值，ai（1≤i≤n）是一個(gè)任意字符。4.1

知識(shí)學(xué)習(xí)4.1.1串的基本概念兩個(gè)串相等：如果兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)字符都相等。子串：串中任意連續(xù)的字符組成的子序列稱(chēng)為該串。主串：包含子串的串。子串的第一個(gè)字符在主串中的序號(hào)稱(chēng)為子串的位置。4.1.2串的存儲(chǔ)結(jié)構(gòu)（1）用一個(gè)變量來(lái)表示串的長(zhǎng)度。4.1知識(shí)學(xué)習(xí)如何表示串的長(zhǎng)度？1.串的順序存儲(chǔ)結(jié)構(gòu)（2）在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符

。

4.1知識(shí)學(xué)習(xí)如何表示串的長(zhǎng)度？4.1.2串的存儲(chǔ)結(jié)構(gòu)1.串的順序存儲(chǔ)結(jié)構(gòu)（3）用數(shù)組的0號(hào)單元存放串的長(zhǎng)度，串值從1號(hào)單元開(kāi)始存放。

4.1知識(shí)學(xué)習(xí)如何表示串的長(zhǎng)度？4.1.2串的存儲(chǔ)結(jié)構(gòu)1.串的順序存儲(chǔ)結(jié)構(gòu)（1）非壓縮形式（2）圧縮形式4.1知識(shí)學(xué)習(xí)4.1.2串的存儲(chǔ)結(jié)構(gòu)1.串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4.1知識(shí)學(xué)習(xí)串的基本操作算法串的復(fù)制strcpy(字符數(shù)組名1,字符數(shù)組名2)功能：把字符數(shù)組2中的字符串，連同字符串結(jié)束符'\0'，賦值到字符數(shù)組1中。串的連接strcat(字符數(shù)組名1,字符數(shù)組名2)功能：把字符數(shù)組2中的字符串連接到字符數(shù)組1中字符串的后面，并去掉字符數(shù)組1中的字符串后的字符串標(biāo)志'\0'。串的比較strcmp(字符數(shù)組名1,字符數(shù)組名2)功能：將兩個(gè)字符串從左至右逐個(gè)字符按照ASCII碼值進(jìn)行比較，直到出現(xiàn)不相等的字符或遇到‘\0’為止。如果所有字符都相等，則這兩個(gè)字符串相等。如果出現(xiàn)了不相等的字符，以第一個(gè)不相等字符的比較結(jié)果為準(zhǔn)。4.1知識(shí)學(xué)習(xí)串的簡(jiǎn)單模式匹配模式匹配：給定兩個(gè)串s="s0s1

…sn-1"和t="t0t1

…tm-1"（其中n和m分別是串s和t的長(zhǎng)度），在主串s中尋找子串t的過(guò)程稱(chēng)為模式匹配，t稱(chēng)為模式。如果在s中找到等于t的子串，則稱(chēng)匹配成功，返回t在s中的首次出現(xiàn)的下標(biāo)位置；否則匹配失敗，返回-1。4.1知識(shí)學(xué)習(xí)BF模式匹配基本思想：從主串s中下標(biāo)為0的字符開(kāi)始，與模式串t中下標(biāo)為0的字符比較，若相同，則繼續(xù)逐個(gè)比較s和t中的后續(xù)字符；若不同，從主串s中下標(biāo)為1的字符開(kāi)始，與模式串t中下標(biāo)為0的字符比較。以此類(lèi)推，重復(fù)上述過(guò)程，若t中字符全部比完，則說(shuō)明匹配成功；否則匹配失敗。例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=2失?。籭回溯到1，j回溯到0ijijij第

1趟abcac

4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbabi=2，j=2失?。籭回溯到1，j回溯到0ji第

1趟abcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbabi=1，j=0失敗i回溯到2，j回溯到0第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbabi=1，j=0失敗i回溯到2，j回溯到0第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=6，j=4失敗i回溯到3，j回溯到0第

3趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=6，j=4失敗i回溯到3，j回溯到0第

3趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=3，j=0失敗i回溯到4，j回溯到0第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=3，j=0失敗i回溯到4，j回溯到0第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=4，j=0失敗i回溯到5，j回溯到0第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=4，j=0失敗i回溯到5，j回溯到0第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法ababcabcacbababcac

i=10，j=5，T中全部字符都比較完畢，匹配成功。第

6趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.1知識(shí)學(xué)習(xí)——BF模式匹配算法4.1知識(shí)學(xué)習(xí)——BF模式匹配算法回溯位置j的確定，j=0回溯位置i的確定

i=i-j+1新i原i原j122210364430540intBF(char*s,char*t){ i=0;j=0; n=strlen(s);m=strlen(t); while(i<n&&j<m) { if(s[i]==t[j]) {i++;j++;} else {i=i-j+1;j=0; } } if(j>=m)returni-j;//匹配成功，返回

子串在

主串中首次出現(xiàn)的下標(biāo)位置 elsereturn-1;//匹配不成功，返回-1}4.1知識(shí)學(xué)習(xí)——BF模式匹配算法4.1知識(shí)學(xué)習(xí)——BF模式匹配算法設(shè)串s長(zhǎng)度為n，串t長(zhǎng)度為m，在匹配成功的情況下，考慮兩種極端情況：最好情況：每趟不成功的匹配都發(fā)生在第一對(duì)字符比較時(shí)：例如：s="aaaaabcd"t="bcd"設(shè)匹配成功發(fā)生在si處，則在前i趟比較中，匹配均不成功。每趟不成功的匹配都發(fā)生在第一對(duì)字符比較時(shí)，因此前面i趟匹配中共比較了i次，第i+1趟成功的匹配共比較了m次，所以總共比較了i+m次，所有匹配成功的可能共有n－m+1種，設(shè)從si開(kāi)始與t串匹配成功的概率為pi，在等概率情況下pi=1/(n－m+1)，平均比較的次數(shù)是因此最好情況下的時(shí)間復(fù)雜度是O(n+m)。4.1知識(shí)學(xué)習(xí)——BF模式匹配算法設(shè)串s長(zhǎng)度為n，串t長(zhǎng)度為m，在匹配成功的情況下，考慮兩種極端情況：最壞情況：不成功的匹配都發(fā)生在串t的最后一個(gè)字符。例如：s="aaaaab"t="aaab“設(shè)匹配成功發(fā)生在si處，則在前面i趟匹配中共比較了i*m次，第i+1趟成功的匹配共比較了m次，所以總共比較了(i+1)*m次，因此平均比較的次數(shù)是：一般情況下，m<<n，因此最壞情況下的時(shí)間復(fù)雜度是O(nm)。4.2知識(shí)應(yīng)用intmain(){chars[MaxSize],t[]="轉(zhuǎn)賬";intflag;

cout<<"請(qǐng)輸入聊天信息：\n";cin>>s;flag=BF(s,t);if(flag!=-1)cout<<"***安全提示：如果聊天中提及財(cái)產(chǎn)，請(qǐng)一定先核實(shí)好友身份！***\n";

return0;}4.3知識(shí)拓展——KMP模式匹配算法為什么BF算法時(shí)間性能低？在每趟匹配不成功時(shí)存在大量回溯，沒(méi)有利用已經(jīng)部分匹配的結(jié)果。如何在匹配不成功時(shí)主串不回溯？主串不回溯，模式就需要向右滑動(dòng)一段距離。如何確定模式的滑動(dòng)距離？i=2，j=2失?。?/p>

s1=t1;t0≠t1∴t0≠s1ababcabcacbabij第

1趟abcac

ababcabcacbab第

2趟abcac

4.3知識(shí)拓展——KMP模式匹配算法i=2，j=2失??；

s1=t1;t0≠t1∴t0≠s1ababcabcacbabij第

1趟abcac

ababcabcacbababcac

第

3趟4.3知識(shí)拓展——KMP模式匹配算法ababcabcacbababcac

第

3趟iji=6，j=4失敗s3=t1;t0≠t1∴t0≠s3ababcabcacbababcac

第

4趟4.3知識(shí)拓展——KMP模式匹配算法ababcabcacbaba