多項(xiàng)式的代數(shù)運(yùn)算和串

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

3.2.1指針和游標(biāo)

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

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

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

3.2.5雙向鏈接表

3.2.6環(huán)形鏈表(循環(huán)鏈表)3.3棧3.4排隊(duì)(隊(duì)列)3.5多項(xiàng)式的代數(shù)運(yùn)算3.6串、3.7數(shù)組、3.8、廣義表3第三頁(yè)，共四十頁(yè)，編輯于2023年，星期日

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

順序隊(duì)列4第四頁(yè)，共四十頁(yè)，編輯于2023年，星期日structQUEUE{elementtypeelements[maxlength];intfront;//指向隊(duì)頭元素的位置

intrear;//指向隊(duì)頭元素的位置};QUEUEQ;QUEUE*Q;常見(jiàn)用法elementtypeelements[maxlength];intfront;//指向隊(duì)頭元素的位置

intrear;//指向隊(duì)尾元素的位置2、C語(yǔ)言表示3.4.2、

順序隊(duì)列5第五頁(yè)，共四十頁(yè)，編輯于2023年，星期日43210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=03.4.2、

順序隊(duì)列6第六頁(yè)，共四十頁(yè)，編輯于2023年，星期日43210EDCBAQ.rear=4Q.front=0EDCBQ.rear=4Q.front=1EDCQ.rear=4Q.front=2什么是假上溢現(xiàn)象？Q.rear=4Q.front=43.4.2、

順序隊(duì)列7第七頁(yè)，共四十頁(yè)，編輯于2023年，星期日

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

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

順序隊(duì)列8第八頁(yè)，共四十頁(yè)，編輯于2023年，星期日EDCGFQ.rear=1Q.front=2CQ.rear=1Q.front=1Q.rear=1Q.front=2滿隊(duì)列：尾指針比頭指針滯后一個(gè)位置；EDCFQ.rear=0Q.front=2空隊(duì)列：尾指針比頭指針滯后一個(gè)位置；3.4.2、

順序隊(duì)列9第九頁(yè)，共四十頁(yè)，編輯于2023年，星期日(2)處理循環(huán)隊(duì)列滿還空的兩種方法:a.另設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)列是“空”還是“滿”；b.隊(duì)滿條件為：(Q.rear+2)%maxlength==Q->front隊(duì)空條件為：(Q.rear+1)%maxlength==Q->frontEDCFQ.rear=0Q.front=23.4.2、

順序隊(duì)列10第十頁(yè)，共四十頁(yè)，編輯于2023年，星期日a.置空隊(duì)列

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

順序隊(duì)列11第十一頁(yè)，共四十頁(yè)，編輯于2023年，星期日b.判隊(duì)空

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

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

順序隊(duì)列12第十二頁(yè)，共四十頁(yè)，編輯于2023年，星期日d.取隊(duì)頭元素

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

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

順序隊(duì)列13第十三頁(yè)，共四十頁(yè)，編輯于2023年，星期日e.入隊(duì)

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

順序隊(duì)列14第十四頁(yè)，共四十頁(yè)，編輯于2023年，星期日E.出隊(duì)

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

順序隊(duì)列15第十五頁(yè)，共四十頁(yè)，編輯于2023年，星期日DCsq->rear=3sq->front=2DCsq->rear=0sq->front=43.4.2、

順序隊(duì)列F.隊(duì)列長(zhǎng)度16第十六頁(yè)，共四十頁(yè)，編輯于2023年，星期日intqueuelength(sequeueQ){return(sq->rear-sq->front+MaxSize+1)%MaxSize;}#3.4.2、

順序隊(duì)列17第十七頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算假設(shè)多項(xiàng)式的形式為:其中ai≠0,指數(shù)ei滿足em>em-1>…>e2>e1>=0.18第十八頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算鏈表實(shí)現(xiàn)：1、結(jié)構(gòu)形式：coefexplinkstructpolynode{intcoef;intexp;polynodelink;};typedefpolynode*polypointer;19第十九頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算2、增加新結(jié)點(diǎn)，鏈在鏈表尾端polypointerattach(intc,inte,polypointerd){polypointerx;x=newpolynode;x->coef=c;x->exp=e;d->link=x;returnx;}20第二十頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算3、加法實(shí)現(xiàn)(無(wú)頭結(jié)點(diǎn),設(shè)兩個(gè)多項(xiàng)式為a和b)polypointerpadd(polypointera,polypointerb){polypointerp,q,d,c;intx;p=a;q=b;c=newpolynode;d=c;21第二十一頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算{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第二十二頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算

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第二十三頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算

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第二十四頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.5、多項(xiàng)式的代數(shù)運(yùn)算刪除臨時(shí)結(jié)點(diǎn)

d->link=NULL;p=c;c=c->link;deletep;returnc;}**25第二十五頁(yè)，共四十頁(yè)，編輯于2023年，星期日

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

3.6、串27第二十七頁(yè)，共四十頁(yè)，編輯于2023年，星期日二、串與線性表的區(qū)別?1、串?dāng)?shù)據(jù)對(duì)象約束為字符集。

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

3.6、串28第二十八頁(yè)，共四十頁(yè)，編輯于2023年，星期日三、基本操作：

(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第二十九頁(yè)，共四十頁(yè)，編輯于2023年，星期日

3.6.2串的表示(存儲(chǔ)結(jié)構(gòu))一、順序表示二、鏈接存儲(chǔ)(定長(zhǎng)與不定長(zhǎng))30第三十頁(yè)，共四十頁(yè)，編輯于2023年，星期日#defineMAXSIZE255structseqstring

{charstr[MAXSIZE];

intlen;

};seqstrings;3.6.2串的表示-順序表示31第三十一頁(yè)，共四十頁(yè)，編輯于2023年，星期日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第三十二頁(yè)，共四十頁(yè)，編輯于2023年，星期日1、單字符鏈?zhǔn)酱鎯?chǔ)的C語(yǔ)言表示

structnode{chardata;node*link;};typedefnode*STRING;3.6.2串的表示--鏈接表示33第三十三頁(yè)，共四十頁(yè)，編輯于2023年，星期日子串定位（模式匹配）index(S,S1)的實(shí)現(xiàn)S為主串，S1為子串，又叫模式串如果S中存在子串S1，返回S1第一個(gè)字符在主串中的位置（第幾個(gè)）；如果S中不存在子串S1，返回零。3.6.2操作—子串定位34第三十四頁(yè)，共四十頁(yè)，編輯于2023年，星期日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第三十五頁(yè)，共四十頁(yè)，編輯于2023年，星期日算法分析(最好情況下的平均時(shí)間復(fù)雜度)如：S：abcdefghjklm(主串長(zhǎng)度為n)T：jkl

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