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

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

數(shù)據(jù)

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

數(shù)據(jù)對象數(shù)據(jù)結構的三個要素

數(shù)據(jù)結構涉及三個要素，分別是數(shù)據(jù)的邏輯結構、存儲結構和操作算法2024/9/26111.1知識學習1.1.3算法與算法分析1.什么是算法2.算法的評價3.算法的描述方法2024/9/2612算法性能分析與度量算法的性能標準算法的事前估計算法的后期測試2024/9/2613算法性能分析與度量算法的性能標準正確性健壯性可讀性高效率低存儲空間算法的事前估計算法的后期測試2024/9/2614

算法性能分析與度量算法的性能標準算法的事前估計時間復雜度空間復雜度算法的后期測試2024/9/2615算法性能分析與度量算法的性能標準算法的事前估計時間復雜度空間復雜度存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結構成分、對象的數(shù)據(jù)成員等)變量所占的空間可變部分

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

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

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

i－1和一個后繼a

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

datalength02.1.2.2順序表基本操作的實現(xiàn)2024/9/2635初始化操作——創(chuàng)建長度為n的順序表2.1.2.2順序表基本操作的實現(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順序表基本操作的實現(xiàn)voidShow_Seq(SeqList&L){ for(inti=0;i<L.length;i++) cout<<L.data[i]<<""; cout<<endl;}

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

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

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

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

1）為止，將每一個元素均后移一個存儲單元，將第i個元素的存儲位置空出。④將新元素e寫入到第i個元素處，即下標為i

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

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

順序表基本操作的實現(xiàn)2024/9/2646例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出算法的描述；3.分析時間復雜度。535a1a2a3a401234422412334a51224422.1.2.2順序表基本操作的實現(xiàn)2024/9/2647刪除操作算法描述：2.1.2.2順序表基本操作的實現(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）增強通用性（2）增強靈活性（3）增強適應性2024/9/26492.1.3線性表的鏈接存儲及基本操作鏈表：線性表的鏈接存儲結構。存儲思想：用一組任意的存儲單元存放線性表的元素。靜態(tài)存儲分配順序表事先確定容量鏈表動態(tài)存儲分配運行時分配空間連續(xù)不連續(xù)零散分布2024/9/26502.1.3.1鏈式存儲結構例：(a1,a2

,a3,a4)的存儲示意圖存儲特點：邏輯次序和物理次序不一定相同。元素之間的邏輯關系用指針表示。0200020803000325…………a10200a20325a30300a4∧2024/9/26510200020803000325…………a10200a20325a30300a4∧結點數(shù)據(jù)域指針域單鏈表是由若干結點構成的；單鏈表的結點只有一個指針域。data：存儲數(shù)據(jù)元素next：存儲指向后繼結點的地址datanext單鏈表的結點結構：數(shù)據(jù)域指針域2.1.3.1鏈式存儲結構2024/9/2652typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結點結構：如何申請一個結點？2.1.3.1鏈式存儲結構2024/9/2653s=newNode;typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結點結構：……sNode2.1.3.1鏈式存儲結構2024/9/2654s=newNode;datanext……sNode如何引用數(shù)據(jù)元素？s->data;(*s).data;data如何引用指針域？nexts->next;2.1.3.1鏈式存儲結構2024/9/26550200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表頭指針：指向第一個結點的地址。尾標志：終端結點的指針域為空。2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/26560200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表空表和非空表不統(tǒng)一，缺點？如何將空表與非空表統(tǒng)一？2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2657頭結點：在單鏈表的第一個元素結點之前附設一個類型相同的結點，以便空表和非空表處理統(tǒng)一。非空表heada1a2an∧空表head∧2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/26582.1.3.2單鏈表基本操作的實現(xiàn)voidInitList_L(LinkList&L){ L=newNode; L->next=NULL;}初始化——創(chuàng)建空的單鏈表2024/9/26592.1.3.2單鏈表基本操作的實現(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個元素創(chuàng)建單鏈表2024/9/26602.1.3.2單鏈表基本操作的實現(xiàn)voidShow_L(LinkListL){ LinkListp=L->next; while(p) { cout<<p->data<<"";//輸出結點數(shù)據(jù)域 p=p->next; } cout<<endl;}遍歷單鏈表2024/9/26612.1.3.2單鏈表基本操作的實現(xiàn)intListLength_L(LinkListL){LinkListp=L->next;intk=0;while(p)

{k++;//計數(shù)p=p->next;}returnk;}求單鏈表長度。2024/9/26622.1.3.2單鏈表基本操作的實現(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)如何實現(xiàn)結點ai-1、e和ai之間邏輯關系的變化？pesheada1ai-1an∧ai算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2664注意分析邊界情況——表頭、表尾。

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

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

2.查找第i-1個結點并使工作指針p指向該結點；3.若查找不成功，說明插入位置不合理，拋出插入位置異常；否則，

3.1生成一個元素值為e的新結點s；

3.2將新結點s插入到結點p之后；2.1.3.2單鏈表基本操作的實現(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; }}，基本語句？時間復雜度？2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2667刪除操作接口：voidListDelete_L(LinkListL,inti);p如何實現(xiàn)結點ai-1和ai之間邏輯關系的變化？heada1ai-1ai+1ai算法描述：q=p->next;p->next=q->next;deleteq;q2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2668算法描述：q=p->next;p->next=q->next;deleteq;注意分析邊界情況——表頭、表尾。

pqpq表尾的特殊情況：雖然被刪結點不存在，但其前驅(qū)結點卻存在。p->next=NULLheada1ana2∧2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2669算法描述——偽代碼1.工作指針p初始化；累加器j清零；2.查找第i-1個結點并使工作指針p指向該結點；3.若p不存在或p不存在后繼結點，則拋出位置異常；否則，否則刪除結點p的后一個結點。2.1.3.2單鏈表基本操作的實現(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單鏈表基本操作的實現(xiàn)2024/9/2671將單鏈表中所有結點的存儲空間釋放。

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

2.1.3.2單鏈表基本操作的實現(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單鏈表基本操作的實現(xiàn)2024/9/26732.2知識應用2024/9/26742.2知識應用2024/9/2675voidUnion(SeqList&La,SeqList&Lb){intLa_len=ListLength_Seq(La);//求線性表La的長度ElemTypee;

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

{

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

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

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

if(L.length>=MAXSIZE){cout<<"線性表已滿"<<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++;//表長增1}2.3知識拓展——順序表的其他操作有序表的插入：2024/9/2677voidInvertLinkedList(LinkList&L)//逆置頭指針L所指鏈表{LinkLists,p=L->next;

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

知識拓展——單鏈表的其他操作單鏈表的逆置：2024/9/2678voidMergeLinkList(LinkList&La,LinkList&Lb){LinkListpa=La->next;//pa指向La中當前考察的結點LinkListpb=Lb->next;//pb指向Lb中當前考察的結點LinkListpc=La;//pc指向Lc中當前的表尾結點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

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

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

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

顯然，保存的余數(shù)應該具備“后進先出”的特點，可用棧作為數(shù)據(jù)結構。導學問題2：銀行排隊問題【問題描述】

請設計一個簡單的模擬銀行排隊系統(tǒng)，要求程序具有三項菜單：1）取號。選擇該菜單后，為客戶產(chǎn)生一個排隊號。2）叫號。選擇該菜單后，顯示可服務的客戶排隊號。3）退出系統(tǒng)。【分析】

銀行排隊問題屬于典型的先來先服務，因此需要將產(chǎn)生的排隊號存放在具有“先進先出”特性的數(shù)據(jù)結構中，隊列結構可以滿足要求。

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

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

top棧的順序存儲結構及基本操作出棧：top減1進棧：top加1?？眨簍op=-1

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

S.top++;

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

ElemTypex=S.data[S.top];

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

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

p->data=x;

p->next=S;

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

if(S==NULL)

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

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

LinkStackp=S;

S=S->next;//刪除棧頂結點

deletep;

returnx;}Sanan-1a1∧Sp

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

while(S)

{

p=S;

S=S->next;

deletep;

}}鏈棧的實現(xiàn)——銷毀順序棧和鏈棧的比較時間性能：相同，都是常數(shù)時間O(1)?？臻g性能：順序棧：有元素個數(shù)的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結構性開銷?？傊?，當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應該采用順序棧。3.1.2知識應用——導學問題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知識拓展——算術表達式求值1、中綴表達式直接求值為實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧：

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

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

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

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

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

if(Q.front==Q.rear)

{cout<<"隊列已空"<<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; }鏈隊列的操作——出隊boolQueueEmpty(LinkQueue&Q){ returnQ.front==Q.rear;}鏈隊列的操作——判斷隊空voidDestroyListQueue(LinkQueue&Q){while(Q.front) { Q.rear=Q.front->next; deleteQ.front; Q.front=Q.rear; }}鏈隊列的操作——銷毀

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

若e<max，則將任務e移至隊尾，移動的任務為需要打印的任務，則重置需打印任務的位置flag；

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

S=“a1a2…an”

其中：S是串名，雙引號是定界符，雙引號引起來的部分是串值，ai（1≤i≤n）是一個任意字符。4.1

知識學習4.1.1串的基本概念兩個串相等：如果兩個串的長度相等且對應字符都相等。子串：串中任意連續(xù)的字符組成的子序列稱為該串。主串：包含子串的串。子串的第一個字符在主串中的序號稱為子串的位置。4.1.2串的存儲結構（1）用一個變量來表示串的長度。4.1知識學習如何表示串的長度？1.串的順序存儲結構（2）在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結符

。

4.1知識學習如何表示串的長度？4.1.2串的存儲結構1.串的順序存儲結構（3）用數(shù)組的0號單元存放串的長度，串值從1號單元開始存放。

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

…sn-1"和t="t0t1

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

1趟abcac

4.1知識學習——BF模式匹配算法ababcabcacbabi=2，j=2失敗；i回溯到1，j回溯到0ji第

1趟abcac

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

2趟ijabcac

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

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知識學習——BF模式匹配算法ababcabcacbababcac

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1趟abcac

ababcabcacbab第

2趟abcac

4.3知識拓展——KMP模式匹配算法i=2，j=2失敗；

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

1趟abcac

ababcabcacbababcac

第

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

第

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

第

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