第二章線性表及其順序存儲(chǔ)結(jié)構(gòu)2

數(shù)據(jù)結(jié)構(gòu)第二章線性表及其順序存儲(chǔ)結(jié)構(gòu)1/15/20231引言線性表是一種線性數(shù)據(jù)結(jié)構(gòu)，其用途非常廣泛，可用于信息檢索、存儲(chǔ)管理、模擬技術(shù)和通信等領(lǐng)域。1/15/20232第二章

知識(shí)點(diǎn)線性數(shù)據(jù)結(jié)構(gòu)的基本特征和基本運(yùn)算順序存儲(chǔ)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)的簡(jiǎn)單應(yīng)用難點(diǎn)利用本章的基本知識(shí)，設(shè)計(jì)有效的算法，解決與線性相關(guān)的應(yīng)用問題1/15/20233線性表要求熟練掌握以下內(nèi)容：線性表的基本運(yùn)算了解以下內(nèi)容：線性表運(yùn)算時(shí)間復(fù)雜性分析1/15/20234第二章目錄2.1線性表的基本概念2.2棧及其應(yīng)用2.5隊(duì)列及其應(yīng)用2.6字符串小結(jié)習(xí)題與練習(xí)1/15/20235

2.1.1線性表的基本概念線性表:是n個(gè)(表長(zhǎng)n≥0)同類型數(shù)據(jù)元素的有限序列。元素間是線性邏輯關(guān)系，排成線性序列。線性體現(xiàn)在前后件關(guān)系上。記作：(a1，a2，…，an)特點(diǎn)：有且僅有一個(gè)根結(jié)點(diǎn)，它無前件；有且僅有一個(gè)終端結(jié)點(diǎn)，它無后件；除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)前件；除尾結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)后件。n＝0的線性表為空表。

predecessorsuccessor1/15/20236線性表實(shí)例

英文字母表：(A，B，C，D，…，X，Y，Z)

某校1998-2003年計(jì)算機(jī)數(shù)量(50，100，250，300，500，1200)

學(xué)生信息表序號(hào)學(xué)號(hào)姓名性別英語英語英語01990301李曉明男數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)02990302張國慶男物理物理物理30990330王薇薇女868686體現(xiàn)在順序關(guān)系上記錄排列為順序關(guān)系1/15/20237線性表的基本運(yùn)算

Length(L)Get(1，i)Modify(L，i)Delete(L，i)Insert(L，i，x)Sort(L，key)Index(L，x)

其中：L-表，i-位序，x-數(shù)據(jù)元素

復(fù)雜運(yùn)算線性表的合并；對(duì)有序表的插入、刪除等1/15/202382.1.2線性表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)(SequentialMapping)

用內(nèi)存中一組地址連續(xù)的單元依次存放表中元素，每個(gè)元素的存儲(chǔ)空間大小相同。計(jì)算元素ai的地址假設(shè)每個(gè)元素占k個(gè)字節(jié)，首元素的地址為ADR(a1)，則有:

順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)。在高級(jí)語言環(huán)境中，常用一維數(shù)組來存儲(chǔ)線性表。ADR(ai)=ADR(a1)+(i-1)k轉(zhuǎn)圖1/15/20239線性表的順序存儲(chǔ)結(jié)構(gòu)－－順序表

示意圖1/15/202310線性表類的聲明為更好體現(xiàn)信息隱蔽原則和數(shù)據(jù)抽象原則，把線性表封裝起來。(使用類模板)template<classT>classsq_LList{public:sq_LList(){m=0;n=0}sq_LList(int); intflag_sq_LList()const; boolIns_sq_LList(int,T,int,T); boolDel_sq_LList(int); boolprint_sq_LList()const;protected:intm,n;T*v;//容量、長(zhǎng)度、首指針};1/15/202311建立一個(gè)容量為m的空順序表

C++描述（使用函數(shù)模板）usingnamespacestd;template<classT>voidinit_sq_LList(T*v,intm,intn){ v=newT[m];//動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間n=0;//順序表長(zhǎng)度為0。}1/15/2023122.1.3線性表的運(yùn)算插入

刪除

1/15/202313a0a1…ai1.數(shù)據(jù)元素的插入(insert)插入操作

insert(i,x)：在表中下標(biāo)為i的元素ai后插入x。若i=-1，則將新元素x插在最前面。若插入成功返回true。后移n-i-1個(gè)元素01…ii+1i+2…n-1…m-1an-1x…ai+1…操作演示n-11/15/202314插入

算法描述（新元素插入到位置i之后處）邊界情況處理若存儲(chǔ)空間滿，判為“上溢”，不能插入，返回false；若i>=n-1時(shí)，插到表尾元素之后；若i<0時(shí)，插到首元素之前。將尾元素至i+1元素逐一向后移動(dòng)一個(gè)位置。將新元素插入到第i＋1的位置上，并將順序表長(zhǎng)度增加1，返回true。1/15/202315順序表的插入(C++描述)template<classT>boolsq_LList<T>::ins_sq_LList(inti,Tx){if(n==m){cout<<"OverFlow"<<endl;retrunfalse;}if(i<0)i=0;if(i>n-1)i=n;for(intj=n-1;j>i;j--)v[j+1]=v[j];v[i]=x;n++;returntrue;}1/15/2023162.數(shù)據(jù)元素的刪除(delete)

aia0…

ai-1

刪除操作

Delete(i)：

刪除元素ai。前移n-i-1個(gè)元素

0…i-1ii+1

…n-1

m-1an-1……刪除它ai+1ain-1操作演示1/15/202317刪除

算法描述（刪除位置為i元素）邊界情況處理若存儲(chǔ)空間為空，判為“下溢”，無刪除，返回false；若i<0orI>n-1時(shí)，待刪除元素不在表中，無刪除操作，返回false；將表中i+1元素至尾元素逐一向前移動(dòng)一個(gè)位置，并將順序表長(zhǎng)度減少1，返回true。1/15/202318順序表的刪除(C++描述)template<classT>boolsq_LList<T>::Del_sq_LList(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){ cout<<"OutOfBounds"<<endl;returnfalse;}for(intj=i+1;j<n;j++)v[j-1]=v[j];n--;returntrue;}1/15/202319例2.3建立容量為100的空順序表，表中能插入多個(gè)新元素，也能刪除若干元素，并能順序輸出表中所有元素線性表完整程序D:\\2-1-4-sq_LList.hD:\\2-1-14-sq_LList.cpp1/15/202320時(shí)間復(fù)雜度分析

在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入或刪除一個(gè)元素，其時(shí)間主要耗費(fèi)在元素移動(dòng)上，其次數(shù)取決于插入或刪除元素的位置。假設(shè)：Pi：表示在第i個(gè)元素之后插入一個(gè)元素的概率n：表示線性表長(zhǎng)度

則，插入一個(gè)元素需移動(dòng)元素的平均次數(shù)為：n-1Ains＝∑Pi(n-i)＝Pi*[n+(n-1)+(n-2)+……+1]i=01/15/202321

時(shí)間復(fù)雜度分析假設(shè)：

Qi：是刪除第i個(gè)元素的概率，

n：為線性表的長(zhǎng)度則，刪除一個(gè)元素時(shí)需移動(dòng)元素的平均次數(shù)為：

n-1Adel＝∑Qi(n-i-1)i=01/15/202322【時(shí)間復(fù)雜度分析】如果在線性表的任何位置插入或刪除元素的概率相等，即:Pi＝1/n；Qi＝

1/n；則:

可見，在順序表中插入或刪除一個(gè)元素時(shí)，平均要移動(dòng)表中大約一半的數(shù)據(jù)元素。若表長(zhǎng)為n，前兩個(gè)算法的時(shí)間復(fù)雜度為O(n)。1/15/2023231、線性表采用順序存儲(chǔ)結(jié)構(gòu)操作時(shí)，需大量移動(dòng)數(shù)據(jù)元素，效率較低。2、由于是靜態(tài)存儲(chǔ)結(jié)構(gòu)，需預(yù)先定義大小確定的數(shù)組，容量有限。3、適于直接(隨機(jī))存取操作。

【結(jié)論】本課完1/15/2023241/15/2023252.2棧及其應(yīng)用

2.2.1棧

棧（stack）的定義

棧是限定在一端進(jìn)行插入或刪除操作的線性表。先進(jìn)后出(FirstInLastOut)的線性表

棧底棧頂進(jìn)棧出棧a1a4a2a3NULL堆棧a51/15/202326

2.1.2棧的順序存儲(chǔ)結(jié)構(gòu)(向量)棧的順序存儲(chǔ)結(jié)構(gòu)（順序棧）

用一維數(shù)組來實(shí)現(xiàn)。當(dāng)top等于最大下標(biāo)值時(shí)為棧滿。

1/15/202327FILO棧的基本運(yùn)算和操作InitStack(S)：初始化操作，設(shè)定一個(gè)空棧。EmptyStack(S)：判空棧操作,返回值邏輯值。Push(S，x)：入棧操作，在S棧頂插入一個(gè)元素x。Pop(S)：出棧操作，若棧S不空在棧頂刪除一個(gè)元素。GetTop(S)：取棧頂元素，若棧S不空則取棧頂元素的值。ClearStack(S)：清?？詹僮?。CurrentSize(S)：求當(dāng)前棧中元素的個(gè)數(shù)。DestroyStack(S)：銷毀S棧。1/15/202328順序存儲(chǔ)的棧類C++描述棧類聲明：template<classT>classStack{public: virtualboolflag()const=0; virtualboolreadTop(T)const=0; virtualboolpush(T)=0; virtualboolpop()=0; virtualboolprint()const=0;};1/15/202329

順序棧(由棧類派生)類聲明template<classT>classSqStack:publicStack<T>{public: SqStack(intmSize); ~SqStack(){delete[]s;} boolfalgl()const; boolreadTop(T)const; boolpush(T); boolpop(); private: inttop;//總是指向棧頂元素 intm;//棧容量

T*s;//線性表指針

}1/15/202330構(gòu)造函數(shù)template<classT>SqStack<T>::SeqStack(intmSize){m=mSize-1;s=newT[mSize];top=-1;}析構(gòu)函數(shù)SqStack<T>::~SqStack(){delete[]s;}an-1a1a0topn-110圖順序棧Sm………1/15/202331例：建立容量為10的空棧，將10、20、30、40、50一次壓入棧內(nèi)，完成棧的操作。D:\code\2-2-3-sq_stack.hD:\code\2-2-3-sq_stack.cpp1/15/2023321/15/2023332.2.4表達(dá)式計(jì)算-堆棧應(yīng)用表達(dá)式：由操作數(shù)、操作符和界限符組成。分類：中綴式：操作符在兩個(gè)操作數(shù)之間的表達(dá)式，如：a/(b–c)+d*e前綴式：操作符在兩個(gè)操作數(shù)之前的表達(dá)式，如：+/a–bc*de后綴式：操作符在兩個(gè)操作數(shù)之后的表達(dá)式（逆波蘭表達(dá)式），如：abc-/de*+1/15/202334表達(dá)式計(jì)算表達(dá)式的優(yōu)先級(jí)表2-1操作符的優(yōu)先級(jí)操作符優(yōu)先級(jí)-,!7*,/,%6+,-5<,<=,>,>=4==,!=3&&2||11/15/202335例：中綴表達(dá)式及其對(duì)應(yīng)的后綴表達(dá)式a*b+ca*b/ca*b*c*d*e*fa+(b*c+d)/ea*((b+c)/(d-e)-f)a/(b-c)+d*eab*c+ab*c/ab*c*d*e*f*abc*d+e/+abc+de-/f-*abc-/de*+表2.2中綴表達(dá)式和后綴表達(dá)式中綴表達(dá)式后綴表達(dá)式1/15/202336計(jì)算中綴表達(dá)式的算法為便于處理，設(shè)所有操作數(shù)均為單變量，在表達(dá)式后添加一個(gè)’；’，并設(shè)置兩個(gè)堆棧：存放運(yùn)算符的棧（OPS，棧頂指針topp），初始化時(shí)壓’；‘入棧。存放操作數(shù)的棧（OVS，棧頂指針topv）。算法

從左至右，依次讀取表達(dá)式中各個(gè)符號(hào)。對(duì)讀出的每一個(gè)符號(hào)分情形處理：①若是操作數(shù)，將其壓入操作數(shù)棧，再讀下一個(gè)符號(hào)；1/15/202337②若是運(yùn)算符，則：

⑴

若（該運(yùn)算符==’;’）&&（top->運(yùn)算符==’;’），則結(jié)束整個(gè)表達(dá)式的計(jì)算；

⑵若（該運(yùn)算符>topp->運(yùn)算符），則將該運(yùn)算符壓入運(yùn)算符棧；

⑶

否則，則從操作數(shù)棧連續(xù)彈出兩個(gè)操作數(shù)，從運(yùn)算符棧彈出topp->運(yùn)算符，做相應(yīng)計(jì)算后，將結(jié)果壓入操作數(shù)棧；（注：當(dāng)前讀出的運(yùn)算符下次不再重讀）。1/15/202338例：表達(dá)式A+B*C-D/E的計(jì)算過程OPSOVS/-DECB*+A;TOPvTOPp+*>?運(yùn)算符比較：()表達(dá)式：真-*假計(jì)算：T2=A+T1T1/T2T1=B*C；;-T3=D/ET3/T4=T2–T3T4;=結(jié)果：T4開始：構(gòu)造堆棧讀符號(hào)進(jìn)棧：A、+、B讀符號(hào)：*讀符號(hào)：C讀符號(hào)：-再判符號(hào)：-讀符號(hào)：D、/讀符號(hào)：E、;再判符號(hào)：;再次判別符號(hào)：;1/15/202339帶括號(hào)的表達(dá)式計(jì)算例：A*(B+C/D)–E*F請(qǐng)學(xué)生畫出圖，分析堆棧中數(shù)據(jù)變化。1/15/202340例：編寫程序，實(shí)現(xiàn)從鍵盤輸入一個(gè)帶括號(hào)的簡(jiǎn)單四則運(yùn)算表達(dá)式字符串，計(jì)算并輸出結(jié)果（要求，輸入的字符串長(zhǎng)度不超過60）。D:\code\c++DataStruct\L2_5.cppD:\code\c++DataStruct\sq_Stack.h1/15/2023411/15/202342

一、單棧操作算法1、棧初始化voidInitStack(structSqStack*S)

／*構(gòu)造一個(gè)空棧由指針S指出*／{p＝(structSqStack*)malloc(sizeof(structSqStack))；if(!p)exit(OVERFLOW)；S＝p；S->top＝0；}1/15/202343單棧操作算法2、進(jìn)棧操作voidPush(srtuctSqStack*S；ElemTypeX){if(S->top<MAXSIZE-1){S->top=S->top+1；S->elem[S->top]＝x；}elseprintf(“Overflow!＼n”)；／*棧滿*／

}1/15/202344單棧操作算法3、出棧操作ElemTypePop(structSqStack*p){if(S->top!＝0){x＝S->elem[S->top]；S->top＝S->top-1；return(x)；}else{printf(“Underflow!＼n”)；exit(1)；}／*?？眨乱?／}1/15/202345二、多棧操作算法兩個(gè)棧共用一個(gè)向量有不同的分配方法：棧底在左端、中部棧底在兩端一個(gè)棧已滿,即使另一個(gè)棧仍有空間也不能利用向量空間利用率高1/15/202346棧底在兩邊的存儲(chǔ)結(jié)構(gòu)structDupSqStack{ElemTypeelem[n]；inttop[2]；}另外，還必須預(yù)先設(shè)置：intd[2]，z[2]；d[0]＝-1；d[1]＝n；／*左、右棧判斷?？盏臈l件*／z[0]＝1；z[1]＝-1；／*左、右棧進(jìn)棧時(shí)棧頂指針增量*／在進(jìn)行棧操作時(shí)，需要指定棧號(hào)：i＝0為左棧，i＝1為右棧；判斷棧滿的條件為：（S->top[O]+1＝＝S->top[1]）

1/15/2023471、進(jìn)棧操作voidPush2(structDubSqStack*S；inti；ElemTypex){if(S->top[0]+1＝＝S->top[1])/*棧滿*/{printf(“StackOverflow!\n”)；else{S->top[i]＝S->top[i]+z[i]；S->elem[S->top[i]]＝x；}}1/15/2023482、出棧操作ElemTypePop2(structDubSqStack*S；inti){if(S->top[i]＝＝d[i])/*?？?/printf(“StackUnderflow\n”)；else{x＝S->elem[S->top[i]]；S->top[i]＝S->top[i]-z[i]；return(x)；}}1/15/2023493.1.3棧的鏈表存儲(chǔ)結(jié)構(gòu)棧的鏈表存儲(chǔ)結(jié)構(gòu)：structLsnode{ElemTypedata；structLsnode*next；}1/15/2023501/15/2023511/15/2023521/15/2023531/15/202354

2.3線性表的鏈表存儲(chǔ)結(jié)構(gòu)

不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。

1/15/202355單鏈表

定義結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)：structnode{ELEMTPdata；／*數(shù)據(jù)域*／structnode*next；／*指針域*／}數(shù)據(jù)域指針域附加頭結(jié)點(diǎn)NULL1/15/2023562.3.1有用的C語句

1、定義指向結(jié)點(diǎn)的指針：structnode*h，*p，*q；

/*一個(gè)指針變量占4個(gè)單元*/2、讓p指向一個(gè)新分配的結(jié)點(diǎn)：p＝(structnode*)malloc(sizeof(structnode))；

/*數(shù)據(jù)域p->data*/

3、把此結(jié)點(diǎn)歸還給系統(tǒng)：free(p)；4、結(jié)點(diǎn)p中域的引用p->data；p->next；1/15/2023572.3.2單鏈表的基本運(yùn)算

一、插入(1)

在已知P指針?biāo)赶虻慕Y(jié)點(diǎn)后插入一個(gè)元素x。

{s＝(structnode*)malloc(sizeof(structnode))；s->data＝x；s->next＝p->next；p->next＝s；}演示1/15/202358(2)在P所指向的結(jié)點(diǎn)前插入元素x{q＝head；while(q->next!＝p)q＝q->next；s＝(structnode*)malloc(sizeof(structnode))；s->data＝x；s->next＝p；q->next＝s；}1/15/202359(3)在線性表中值為x的元素前插入一個(gè)值為y的數(shù)據(jù)元素如果值為x的結(jié)點(diǎn)不存在，則將y插在表尾1/15/202360在x元素前插入y元素voidinsert(structnode*head){s＝(structnode*)malloc(sizeof(structnode))；s->data＝y(tǒng)；q＝head；p＝q->next；while((p!＝NULL)&&(p->data1!＝x)){q＝p；p＝p->next；}s->next＝p；q->next＝s；}算法2.31/15/202361二、刪除（1）刪除p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)(假設(shè)存在)

{q＝p->next；p->next＝q->next；free(q)；}演示1/15/202362(2)刪除p所指向的結(jié)點(diǎn){q＝head；while(q->next!＝p)q＝q->next；q->next＝p->next；free(p)；}1/15/202363(3)刪除線性表中值為x的數(shù)據(jù)元素刪除線性表中值為x的數(shù)據(jù)元素，輸出“YES!”；如果x不存在，輸出“NO!”?！舅惴ㄋ枷搿肯扔靡粋€(gè)指針p從表頭開始向后查找值為x的結(jié)點(diǎn)；用另一個(gè)指針q緊跟在指針p后面；如果x不存在：先讓q->next＝p->next；再用free(p)刪除p結(jié)點(diǎn)，輸出“YES!”；如果x(p=NULL)不存在：不必進(jìn)行刪除操作，只輸出“NO!”。1/15/202364刪除值為x的數(shù)據(jù)元素voiddelete(structnode*head){q＝head；p＝q->next；while((p!＝NULL)&&(p->data!＝x){q＝p；p＝p->next；}/*查找*/if(p＝＝NULL)print(“NO!”)；else{q->next＝p->next；free(p)；print{(“YES！”)；}}算法2.41/15/202365三、單鏈表的逆置

【算法思想】在附加頭結(jié)點(diǎn)和第一個(gè)存放數(shù)據(jù)元素的結(jié)點(diǎn)之間不斷插入后邊元素結(jié)點(diǎn)。

1/15/202366單鏈表的逆置voidnizhi(structnode*head){p＝head->next；head->next＝NULL；while(p!＝NULL){q＝p->next；p->next＝head->next；head->next=p；p=q；}}算法2.51/15/202367四、單鏈表的建立voidcreat(){head＝(NODE*)malloc(sizeof(NODE))；head->next＝NULL；p＝head；/*head為附加頭結(jié)點(diǎn)*／print(”x＝”)；scanf(“％d”，x)；while(x!＝-999){ptr＝(NODE*)malloc(sizeof(NODE))；ptr->data＝x；ptr->next＝NULL；p->next＝ptr；p=ptr；printf(“x＝”)；scanf(”％d”，x)；

／*輸入下一個(gè)數(shù)據(jù)元素*／}}演示算法2.6【算法思想】按照原始數(shù)據(jù)的先后順序一一輸入，新結(jié)點(diǎn)在表尾插入。

1/15/202368單鏈表建立小結(jié)在這個(gè)算法中從第一個(gè)數(shù)據(jù)元素開始輸入，然后按順序逐一輸入，最后以一999為結(jié)束標(biāo)志。由上述算法可見，建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程是一個(gè)動(dòng)態(tài)生成鏈表的過程，即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表，其時(shí)間復(fù)雜度為O(n)。

缺點(diǎn)：在單鏈表中，從任何一個(gè)結(jié)點(diǎn)能通過指針域找到它的后繼結(jié)點(diǎn)，但無法找出它的前趨結(jié)點(diǎn)。

1/15/2023692.4循環(huán)鏈表和雙向鏈表單向循環(huán)鏈表:是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，表中最后一個(gè)結(jié)點(diǎn)的指針指向單鏈表的表頭結(jié)點(diǎn)，形成一個(gè)循環(huán)鏈表。優(yōu)點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。

尾指針1/15/2023702.4.1將兩個(gè)單向循環(huán)鏈表首尾相接

{A->next＝HB->next；B->next＝A->next；free(HB)；A＝B；}/*運(yùn)算時(shí)間為O(1)*/合并前合并后1/15/2023712.4.2雙向循環(huán)鏈表

優(yōu)點(diǎn)：1、可以從兩個(gè)方向搜索某個(gè)結(jié)點(diǎn)，遍歷整個(gè)鏈表。2、可以利用另一根鏈修復(fù)整個(gè)鏈表?？真湵黼p向鏈表左指針右指針1/15/202372（1）在雙向鏈表中插入一個(gè)結(jié)點(diǎn)s{s->next＝p；s->prior＝p->prior；p->prior＝s；p->prior->next＝s；}1/15/202373（2）在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)

{p->prior->next＝p->next；p->next->prio＝p->prior；free(p)；}1/15/2023742.5線性表處理的典型用例

多項(xiàng)式相加問題數(shù)學(xué)上的一個(gè)n項(xiàng)多項(xiàng)式：

p=anxn+an-1xn-1+…+a1x+a0(0≤i≤n)多項(xiàng)式可以使用順序表也可以使用鏈表來表示。設(shè)有兩個(gè)多項(xiàng)式：

A＝3x14+2x8-x3+5B＝8x14+3x10+10x6+x3要求將兩個(gè)多項(xiàng)式相加得一個(gè)新的多項(xiàng)式：

C＝11x14+3x10+2x8+10x6+5

例：1/15/2023752.5.1鏈表存儲(chǔ)結(jié)構(gòu)的多項(xiàng)式相加

用鏈表來表示多項(xiàng)式的結(jié)點(diǎn)：structpoly{intcoef；／*變量的系數(shù)*／intexp；／*變量的指數(shù)*／structpoly*next；

／*指到下一結(jié)點(diǎn)的指針*／}1/15/2023762.5.2多項(xiàng)式相加的算法實(shí)現(xiàn)設(shè)置p、q指針分別指向pa、pb兩個(gè)鏈表的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)；設(shè)pc鏈表頭指針指向pa(節(jié)省資源)，設(shè)指針變量r也指向pa，其作用是指向pc鏈表中最新鏈入的結(jié)點(diǎn)，當(dāng)有結(jié)點(diǎn)連入pc表時(shí)，頭指針pc不動(dòng)，r向前移動(dòng)。對(duì)p、q兩個(gè)結(jié)點(diǎn)的指數(shù)域進(jìn)行比較；指數(shù)相同，系數(shù)相加，連入pc鏈表；指數(shù)不同，將指數(shù)較大的結(jié)點(diǎn)連入pc表；每處理一次，相關(guān)指針p/q/r一般需要向前移動(dòng)?！径囗?xiàng)式相加算法】1/15/202377多項(xiàng)式相加的算法實(shí)現(xiàn)第一次處理后第二次處理后1/15/202378多項(xiàng)式相加的算法實(shí)現(xiàn)structpoly*add_poly(structpoly*pa，structpoly*pb){p＝pa->next；q＝pb->next；r＝pa；pc＝pa；

while((p!＝NULL)&&(q!＝NULL){if(p->exp＝＝q->exp){x＝p->coef+q->coef；if(x!＝0){p->coef＝x；r->next＝p；r＝p；}p++,q++；}elseif(p->exp>q->exp){r->next＝p；r＝p；p++；}else{r->next＝q；r＝q；q++；}}if(p＝＝NULL)r->next＝q；elser->next＝p；return(pc)}算法2.71/15/202379數(shù)據(jù)結(jié)構(gòu)第三章棧和隊(duì)列1/15/202380第三章棧和隊(duì)列知識(shí)點(diǎn)堆棧的定義和基本運(yùn)算堆棧應(yīng)用算法隊(duì)列的定義和基本運(yùn)算循環(huán)隊(duì)列的特征、運(yùn)算以及溢出判斷與普通隊(duì)列的差別隊(duì)列的簡(jiǎn)單應(yīng)用算法難點(diǎn)循環(huán)隊(duì)列的特點(diǎn)及溢出判斷利用本章的基本知識(shí)設(shè)計(jì)有效的算法解決與線性相關(guān)的應(yīng)用問題1/15/202381棧和隊(duì)列要求掌握堆棧的特征、基本運(yùn)算并能設(shè)計(jì)簡(jiǎn)單算法掌握隊(duì)列和循環(huán)隊(duì)列的特征、基本運(yùn)算并能設(shè)計(jì)簡(jiǎn)單算法了解以下內(nèi)容：堆棧、隊(duì)列實(shí)際應(yīng)用1/15/2023823.1棧3.2隊(duì)列小結(jié)習(xí)題與練習(xí)第三章目錄1/15/202383棧的鏈表存儲(chǔ)結(jié)構(gòu)一個(gè)鏈表?xiàng)Ｓ蓷ｍ斨羔榯op唯一確定，當(dāng)top為NULL時(shí)是一個(gè)空棧。

棧頂指針棧底1/15/202384一、單鏈表?xiàng)５闹饕惴?、進(jìn)棧：viodPush(structLsnode*top；ElemTypex){p＝(structLsnode*)mallco(sizeof(structLsnode))；p->data＝x；p->next＝top；top＝p；}

1/15/202385單鏈表?xiàng)５闹饕惴?、出棧ElemTypePop(structLsnode*top){if(top!＝NULL){p＝top；top＝top->next；x＝p->data；free(p)；return(x)；}else{print(”StackNULL!＼n”)；exit(1)；}}1/15/202386二、多個(gè)鏈表?xiàng)５倪\(yùn)算

【算法思想】在同時(shí)使用兩個(gè)以上的棧時(shí),若用一個(gè)表結(jié)構(gòu)來處理是極不方便的。最好采用多個(gè)單鏈表作存儲(chǔ)結(jié)構(gòu)。

定義指針數(shù)組：structLsnode*top[n]；讓top[0]，…，top[n-1]指向n個(gè)不同的單鏈表。

1/15/202387多個(gè)鏈表?xiàng)Ｋ惴?、元素X進(jìn)第i號(hào)棧操作：

voidPushn(structLsnode*top[n]；inti；ElemTypex){p＝(structLsnode*)mallco(sizeof(structLsnode))；p->data＝x；p->next＝top[i]；top[i]＝p；}

1/15/202388多個(gè)鏈表?xiàng)Ｋ惴?、第i號(hào)棧出棧ElemTypePopn(structLsnode*top[n]；inti){if(top[i]!＝NULL){p＝top[i]；top[i]＝p->next；x＝p->data；free(p)；return(x)；}elseprintf(“StackNULL!＼n”)；}1/15/2023893.1.4棧的應(yīng)用-表達(dá)式的計(jì)算高級(jí)語言編譯中的一個(gè)基本問題是對(duì)表達(dá)式進(jìn)行處理。要把一個(gè)表達(dá)式翻譯成正確求值的一個(gè)機(jī)器指令序列，首先要能夠正確解釋表達(dá)式。例如，求下面算術(shù)表達(dá)式的值：

運(yùn)算符和界限符統(tǒng)稱為算符(OP)。這個(gè)算術(shù)表達(dá)式的計(jì)算順序應(yīng)為：

(5-3)*6+10／5＝2*6+10／2＝12+10／2＝12+5＝17(5–3)*6+10／5界限符delimiter運(yùn)算符operator1/15/202390算符之間的優(yōu)先關(guān)系算符優(yōu)先級(jí)：θ1<θ2，θ1的優(yōu)先權(quán)低于θ2θ1=θ2，θ1的優(yōu)先權(quán)等于θ2θ1>θ2，θ1的優(yōu)先權(quán)高于θ2設(shè)“#”是表達(dá)式的開始、結(jié)束符，“#”：“#”表示整個(gè)表達(dá)式求值完畢?！?”與“(”、“#”與“)”以及“(”與“#”之間無優(yōu)先關(guān)系（語法錯(cuò)誤）。

1/15/202391表達(dá)式求解算法用兩個(gè)工作棧：運(yùn)算符棧OPTR，初始化為空。操作數(shù)棧OPND，棧底放表達(dá)式起始符“#”。1、初始化棧；2、依次讀入表達(dá)式中每一個(gè)字符；3、若是操作數(shù)則進(jìn)OPND棧；4、若是運(yùn)算符，則將OPTR棧頂運(yùn)算符與其比較，根據(jù)優(yōu)先權(quán)作相應(yīng)的操作5、重復(fù)2，直至整個(gè)表達(dá)式求值完畢(即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”)。

1/15/202392表達(dá)式求解算法OperandTypeEvaluateExpression(){InitStack(OPTR)；Push(OPTR，‘#’)；InitStack(OPND)；c=getchar()；while(c!=‘#’||GetTop(OPTR)!=‘#’)if(!in(c，OP)){Push(OPND，c)；c=getchar()；}elseswitch(Precede(GetTop(OPTR)，c){case‘<’：Push(OPTR，c)；c=getehar()；break；case‘=’：Pop(OPTR，x)；c=getchar()；break；算法3.2轉(zhuǎn)下頁1/15/202393表達(dá)式求解算法case‘>’：Pop(OPTR，theta)；Pop(OPND，b)；Pop(OPND，a)；Push(OPND，Operate(a，theta，b))；Break；／*退棧并將運(yùn)算結(jié)果入棧*／}return(GetTop(OPND))；}θ接上頁演示1/15/202394棧的應(yīng)用-子程序的嵌套調(diào)用設(shè)三個(gè)函數(shù)A1、A2、A3有如下調(diào)用關(guān)系：A1在r處調(diào)用A2，A2在t處調(diào)用A3，函數(shù)A3不調(diào)用其他函數(shù)。rtA1A2A31/15/202395函數(shù)嵌套調(diào)用A1調(diào)用A2，A2調(diào)用A3時(shí)的返回地址在堆棧中的情況如右圖所示。toprtSTACK1/15/202396棧的應(yīng)用-遞歸調(diào)用n階Hanoi塔問題假設(shè)有3個(gè)分別命名為a、b和c的塔座，在塔座a上插有n個(gè)大小不同的圓盤?，F(xiàn)要按下列規(guī)則將a軸上n個(gè)圓盤通過b軸移至c軸上,并仍按同樣順序疊放：每次只能移動(dòng)一個(gè)圓盤；圓盤可以插在a、b和c中的任一塔座上；任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。

演示1/15/202397【n階Hanoi塔算法】當(dāng)n＝1時(shí)，只要將編號(hào)為l的圓盤從塔座a直接移至塔座c上即可；當(dāng)n>1時(shí)，將壓在n號(hào)圓盤之上的n-1個(gè)圓盤從a移至b，再將第n號(hào)圓盤從a移至c，然后再將b上的n-1個(gè)圓盤移至c。

1/15/202398n階Hanoi塔算法VoidHanoi(intn，chara，charb，charc){if(n==1)move(a，1，c)；else{Hanoi(n-1，a，c，b)；move(a，n，c)；Hanoi(n-1，b，a，c)；}}

算法3.3演示實(shí)現(xiàn)把n號(hào)盤從a移到c1/15/2023992.2隊(duì)列（Queue）

隊(duì)列的定義及運(yùn)算

隊(duì)列(queue)是在一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。

FirstInFirstOut-FIFOa1a2a3a4a5出隊(duì)進(jìn)隊(duì)隊(duì)頭隊(duì)尾Queue1/15/20231002.3.2隊(duì)列的運(yùn)算．InsQ(x)：在隊(duì)列尾部插入一個(gè)新元素x。．DelQ()：刪除隊(duì)列中隊(duì)首元素。．EmptyQ()：測(cè)試隊(duì)列是否為空,為空時(shí)返回一個(gè)真值，否則返回一個(gè)假值。．FrontQ()：取得隊(duì)列中隊(duì)首元素。．SetNULL(Q)：創(chuàng)建一個(gè)空隊(duì)列Q?！?/15/2023101隊(duì)列類模板聲明（C++描述）template<classT>classQueue{public:virtualboolins_Queue(constT)=0;virtualbooldel_Queue()=0;virtualboolprt_Queue(T&)=0; virtualboolflag_Queue()const=0; };1/15/2023102順序隊(duì)列類聲明template<classT>classsq_Queue:publicQueue<T>{public:sq_Queue(int);

boolflag_Queue()const；boolprt_Queue(T&x)const;boolins_Queue(Tx);booldel_Queue();private:intfront,rear,n;T*q;};1/15/20231032.3.2循環(huán)隊(duì)列及其運(yùn)算把隊(duì)列空間從邏輯上看成是一個(gè)首尾相連的環(huán)。如何判斷一個(gè)循環(huán)隊(duì)列是滿還是空？

frontrear162345a6a5a1a7a4a3a2隊(duì)列空隊(duì)列滿1/15/2023104如何判斷循環(huán)隊(duì)列是空？是滿？判滿條件(設(shè)n=6)：判空條件：

162345frontrear162345a1a2a3a4a5frontrearfront==rear(rear+1)%n==front1/15/2023105循環(huán)隊(duì)列存在的問題及解決方法問題：

在隊(duì)列滿時(shí)仍有一個(gè)元素的空間未使用解決方法：

啟用該單元，并設(shè)置一標(biāo)志s，定義如下：

0（隊(duì)列中無元素）1（隊(duì)列中有元素）于是有：判空條件：front==rear&&s==0;判滿條件：front==rear&&s==1;1/15/2023106順序循環(huán)隊(duì)列類模板聲明template<classT>classsq_c_Queue:publicQueue<T>{public:

sq_c_Queue(int);

boolflag_Queue()const；boolprt_Queue(T&x)const;boolins_Queue(Tx);booldel_Queue();private:intfront,rear,n，s;T*q;};1/15/2023107例2.6建立容量為10的循環(huán)空隊(duì)列。輸出隊(duì)列；再依次將50、60、70、80、90、100等六個(gè)數(shù)入隊(duì)，輸出隊(duì)列中元素；最后連續(xù)將三個(gè)元素出隊(duì)，輸出隊(duì)列中元素。D:\code\c++DataStruct\sq_Queue.hD:\code\c++DataStruct\L2_6.cpp1/15/2023108循環(huán)隊(duì)列的運(yùn)算算法1、將循環(huán)隊(duì)列置為空：voidSetNULL(structSeQueue*p){p＝(structSeQueue*)malloc(sizeof(SeQueue));Q＝*p；Q.front＝0；Q.rear＝0；}1/15/2023109循環(huán)隊(duì)列的運(yùn)算算法

2、判斷循環(huán)隊(duì)列是否為空intEmpty(structSeQueue*p){if(Q.rear＝＝Q.front)return(1)；elsereturn(0)；}1/15/20231103、在循環(huán)隊(duì)列中插入新的元素xvoidAddQ(structSeQueue*p，ElemTypex){Q＝*p；if((Q.rear+1)％MAXSIZE＝＝Q.front)printf(“QueueIsFull＼n”)else{Q.rear＝(Q.rear+1)％MAXSIZE；Q.elem[Q.rear]＝x；}}循環(huán)隊(duì)列的運(yùn)算算法1/15/2023111循環(huán)隊(duì)列的運(yùn)算算法4、刪除隊(duì)列中隊(duì)首元素:ElemTypeDelQ(structSeQueue*p){Q＝*p；if(Q.front==Q.rear)printf(”QueueIsEmpty＼n”)；else{Q.front＝(Q.front+1)％MAXSIZE；return(Q.elem[Q.front])；}}1/15/2023112循環(huán)隊(duì)列的運(yùn)算算法5、取隊(duì)列中的隊(duì)首元素ElemTypeFront(structSeQueue*p){ElemTypex；if(Q.front==Q.rear)printf(“QUEUEISEMPTY＼n”)；elsex=Q.elem[(Q.front+1)％MAXSIZE]；return(X)；}1/15/20231133.2.3隊(duì)列的鏈表存儲(chǔ)結(jié)構(gòu)用鏈表表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)列。

頭結(jié)點(diǎn)1/15/2023114隊(duì)列的鏈表存儲(chǔ)結(jié)構(gòu)鏈隊(duì)列結(jié)構(gòu)：structNodeType{ElemTypedata；structNodeType*next；}structLinkQueue{structNodeTypefront，rear；}1/15/2023115鏈隊(duì)列運(yùn)算算法

1、隊(duì)列初始化：voidSetNULL(structLinkQueue*Q){structNodeType*p；Q＝(structLinkQueue*）malloc(sizeof(structLinkQueue))；p＝(structNodeType*)malloc(sizeof(structNodeType))；Q->front＝p；Q->rear＝p；p->next＝NULL；}

1/15/2023116鏈隊(duì)列運(yùn)算算法

2、判隊(duì)列是否為空intEmpty(structLinkQueue*Q){if(Q->front==q->rear)return(1)；elsereturn(0)；}1/15/2023117鏈隊(duì)列運(yùn)算算法3、在隊(duì)尾結(jié)點(diǎn)之后插入一個(gè)元素

voidAddQ(structLinkQueue*Q，ElemTypex){structNodeType*p；p＝(NodeType*)malloc(sizeof(structNodeType))；p->data＝x；p->next＝NULL；Q->rear->next＝p；Q->rear＝p；}1/15/2023118鏈隊(duì)列運(yùn)算算法4、刪除隊(duì)頭元素ElemTypeDelQ(structLinkQueue*Q){structNodeType*p；if(Empty(Q))printf(”QUEUEISEMPTY＼n”)；else{p＝Q->front->next；Q->front->next＝p->next；if(p->next＝＝NULL)Q->rear＝Q->front；return(p一>data)；free(p)}}1/15/2023119鏈隊(duì)列運(yùn)算算法

5、取隊(duì)列首元素

Elem