多項式的代數(shù)運算和串

多項式的代數(shù)運算和串1第1頁，課件共40頁，創(chuàng)作于2023年2月作業(yè)問題3.3對于用如下方式實現(xiàn)的已排序的線性表:(a)數(shù)組;(b)指針寫出INSERT,DELETE和LOCATE的程序3.6已知一個單鏈?zhǔn)骄€性表如圖3-27所示,試給一個算法將該線性表復(fù)制一個拷貝。Fa1a2an^…3.5寫出一個交換單向鏈表中位置P和NEXT(P)的元素的程序。2第2頁，課件共40頁，創(chuàng)作于2023年2月第三章線性表3.1抽象數(shù)據(jù)型線性表3.2線性表的實現(xiàn)

3.2.1指針和游標(biāo)

3.2.2線性表的數(shù)組實現(xiàn)

3.2.3線性表的指針實現(xiàn)

3.2.4線性表的游標(biāo)實現(xiàn)

3.2.5雙向鏈接表

3.2.6環(huán)形鏈表(循環(huán)鏈表)3.3棧3.4排隊(隊列)3.5多項式的代數(shù)運算3.6串、3.7數(shù)組、3.8、廣義表3第3頁，課件共40頁，創(chuàng)作于2023年2月

1．隊列的順序表示和實現(xiàn)用內(nèi)存中一組連續(xù)的存儲單元（數(shù)組）存放隊列中的各元素，簡稱順序隊列。3.4.2、

順序隊列4第4頁，課件共40頁，創(chuàng)作于2023年2月structQUEUE{elementtypeelements[maxlength];intfront;//指向隊頭元素的位置

intrear;//指向隊頭元素的位置};QUEUEQ;QUEUE*Q;常見用法elementtypeelements[maxlength];intfront;//指向隊頭元素的位置

intrear;//指向隊尾元素的位置2、C語言表示3.4.2、

順序隊列5第5頁，課件共40頁，創(chuàng)作于2023年2月43210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=03.4.2、

順序隊列6第6頁，課件共40頁，創(chuàng)作于2023年2月43210EDCBAQ.rear=4Q.front=0EDCBQ.rear=4Q.front=1EDCQ.rear=4Q.front=2什么是假上溢現(xiàn)象？Q.rear=4Q.front=43.4.2、

順序隊列7第7頁，課件共40頁，創(chuàng)作于2023年2月

4.循環(huán)隊列把順序隊列構(gòu)造成一個首尾相連的循環(huán)表。指針和隊列元素之間關(guān)系不變。EDC

Q.rear=4Q.front=2EDCFQ.rear=0Q.front=2EDCGFQ.rear=1Q.front=23.4.2、

順序隊列8第8頁，課件共40頁，創(chuàng)作于2023年2月EDCGFQ.rear=1Q.front=2CQ.rear=1Q.front=1Q.rear=1Q.front=2滿隊列：尾指針比頭指針滯后一個位置；EDCFQ.rear=0Q.front=2空隊列：尾指針比頭指針滯后一個位置；3.4.2、

順序隊列9第9頁，課件共40頁，創(chuàng)作于2023年2月(2)處理循環(huán)隊列滿還空的兩種方法:a.另設(shè)一個標(biāo)志以區(qū)別隊列是“空”還是“滿”；b.隊滿條件為：(Q.rear+2)%maxlength==Q->front隊空條件為：(Q.rear+1)%maxlength==Q->frontEDCFQ.rear=0Q.front=23.4.2、

順序隊列10第10頁，課件共40頁，創(chuàng)作于2023年2月a.置空隊列

MAKENULL(QUEUE&Q){Q.front=0;Q.rear=maxlength-1;}3.4.2、

順序隊列11第11頁，課件共40頁，創(chuàng)作于2023年2月b.判隊空

booleanEMPTY(QUEUEQ){if((Q->rear+1)%maxlength==Q->front)returnTRUE;elsereturnFALSE;}C.判隊滿

booleanFULL(sequeueQ){if((Q->rear+2)%maxlength==Q->front)returnTRUE;elsereturnFALSE;}3.4.2、

順序隊列12第12頁，課件共40頁，創(chuàng)作于2023年2月d.取隊頭元素

elementtypeFRONT(QUEUEQ){if(EMPTY(Q)){returnNULL;else

returnQ.elements[Q.front];}3.4.2、

順序隊列13第13頁，課件共40頁，創(chuàng)作于2023年2月e.入隊

voidENQUEUE(elementtypex,QUEUE&Q){if(FULL(Q))error(“queueisfull”);else{Q.rear=(Q.rear+1)%maxlength;Q.elements[Q.rear]=x;}}3.4.2、

順序隊列14第14頁，課件共40頁，創(chuàng)作于2023年2月E.出隊

voidDEQUEUE(QUEUE&Q){if(EMPTY(Q))error(“queueisempty”);elseQ.front=(Q.front+1)%maxlength;}3.4.2、

順序隊列15第15頁，課件共40頁，創(chuàng)作于2023年2月DCsq->rear=3sq->front=2DCsq->rear=0sq->front=43.4.2、

順序隊列F.隊列長度16第16頁，課件共40頁，創(chuàng)作于2023年2月intqueuelength(sequeueQ){return(sq->rear-sq->front+MaxSize+1)%MaxSize;}#3.4.2、

順序隊列17第17頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算假設(shè)多項式的形式為:其中ai≠0,指數(shù)ei滿足em>em-1>…>e2>e1>=0.18第18頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算鏈表實現(xiàn)：1、結(jié)構(gòu)形式：coefexplinkstructpolynode{intcoef;intexp;polynodelink;};typedefpolynode*polypointer;19第19頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算2、增加新結(jié)點，鏈在鏈表尾端polypointerattach(intc,inte,polypointerd){polypointerx;x=newpolynode;x->coef=c;x->exp=e;d->link=x;returnx;}20第20頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算3、加法實現(xiàn)(無頭結(jié)點,設(shè)兩個多項式為a和b)polypointerpadd(polypointera,polypointerb){polypointerp,q,d,c;intx;p=a;q=b;c=newpolynode;d=c;21第21頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算{while((p!=NULL)&&(q!=NULL))switch(compare(p->exp,q->exp)){case‘=’:x=p->coef+q->coef;if(x!=0)d=attach(x,p->exp,d)p=p->link;q=q->link;break;22第22頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算

case‘>’:d=attach(p->coef,p->exp,d)p=p->link;break;

case‘<’:d=attach(q->coef,q->exp,d)q=q->link;break;23第23頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算

while(p!=NULL){d=attach(q->coef,q->exp,d);p=p->link;}

while(q!=NULL){d=attach(q->coef,q->exp,d);q=q->link;}24第24頁，課件共40頁，創(chuàng)作于2023年2月

3.5、多項式的代數(shù)運算刪除臨時結(jié)點

d->link=NULL;p=c;c=c->link;deletep;returnc;}**25第25頁，課件共40頁，創(chuàng)作于2023年2月

3.6、串一、串的概念1.串(String)的定義是由零個或多個字符組成的有限序列。記為：s=”a1a2…an”(n≥0)其中，s是串的名，用雙引號括起來的字符序列是串的值。2.串的長度:串中字符的數(shù)目n。3.空串(Nullstring):長度為零的串。4.子串:串中任意個連續(xù)的字符組成的子序列。26第26頁，課件共40頁，創(chuàng)作于2023年2月5.主串:包含子串的串相應(yīng)地稱為主串。6.位置:字符在序列中的序號。子串在主串中的位置則以子串的第一個字符在主串的位置來表示。7.串相等:只有當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等，稱兩串相等。8.空格串(空白串)(blankstring)由一個或多個空格組成的串。要和“空串”區(qū)別，空格串有長度就是空格的個數(shù)。

3.6、串27第27頁，課件共40頁，創(chuàng)作于2023年2月二、串與線性表的區(qū)別?1、串?dāng)?shù)據(jù)對象約束為字符集。

2、基本操作的對象不同，線性表以“單個元素”為操作對象；串以“串的整體”為操作對象，操作的一般都是子串。

3.6、串28第28頁，課件共40頁，創(chuàng)作于2023年2月三、基本操作：

(1)NULL()(2)ISNULL()(3)IN(S,a)(4)LEN(S)(5)CONCAT(S1,S2)(6)SUBSTR(S,m,n)(7)INDEX(S,S1)(8)STRCMP(S1,S2)

3.6、串*29第29頁，課件共40頁，創(chuàng)作于2023年2月

3.6.2串的表示(存儲結(jié)構(gòu))一、順序表示二、鏈接存儲(定長與不定長)30第30頁，課件共40頁，創(chuàng)作于2023年2月#defineMAXSIZE255structseqstring

{charstr[MAXSIZE];

intlen;

};seqstrings;3.6.2串的表示-順序表示31第31頁，課件共40頁，創(chuàng)作于2023年2月intstrcmp(s,t)seqstrings,t;{inti=0;while(i<s.len&&i<t.len){if(s.str[i]>t.str[i])return(1);elseif(s.str[i]<t.str[i])return(-1);elsei++;}3.6.2串的操作—串比較if(s.len>t.len)return(1);elseif(s.len<t.len)return(-1);elsereturn(0);}*32第32頁，課件共40頁，創(chuàng)作于2023年2月1、單字符鏈?zhǔn)酱鎯Φ腃語言表示

structnode{chardata;node*link;};typedefnode*STRING;3.6.2串的表示--鏈接表示33第33頁，課件共40頁，創(chuàng)作于2023年2月子串定位（模式匹配）index(S,S1)的實現(xiàn)S為主串，S1為子串，又叫模式串如果S中存在子串S1，返回S1第一個字符在主串中的位置（第幾個）；如果S中不存在子串S1，返回零。3.6.2操作—子串定位34第34頁，課件共40頁，創(chuàng)作于2023年2月intINDEX(S,S1)STRINGS,S1;{node*p,*q,*first;if((S1!=NULL)&&(S!=NULL)){first=S;p=S;q=S1;}while(p!=NULL){if(p->data==q->data){q=q->link;if(q==NULL)retrun(first);p=p->link;}3.6.2操作—子串定位else{first=first->link;p=first;q=S1;}}returnnull;}35第35頁，課件共40頁，創(chuàng)作于2023年2月算法分析(最好情況下的平均時間復(fù)雜度)如：S：abcdefghjklm(主串長度為n)T：jkl

(子串長度為m)假設(shè)從第i個位置匹配成功，前i-1次共比較了i-1次。第i次比較了m次,共比較了i+m-1次。i從1到n-m+1,共(n+m)(n-m+1)/2平均需比較(n+m)/2最好的情況平均時間復(fù)雜度為O(n+m)3.6.2