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

1、 作業(yè)問(wèn)題3.2FIRST執(zhí)行次數(shù)END執(zhí)行次數(shù)NEXT執(zhí)行次數(shù)1 作業(yè)問(wèn)題3.2FIRST執(zhí)行次數(shù)END執(zhí)行次數(shù)NEXT執(zhí) 作業(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è)拷貝。Fa1a2an3.5 寫(xiě)出一個(gè)交換單向鏈表中位置P和NEXT(P)的元素的程序。2 作業(yè)問(wèn)題3.3 對(duì)于用如下方式實(shí)現(xiàn)的已排序的線性表:3.第三章 線性表3.1 抽象數(shù)據(jù)型線性表3.2 線性表的實(shí)現(xiàn) 3.2.1 指針和游標(biāo) 3.2.2 線性表的數(shù)組實(shí)現(xiàn) 3.2.3

2、 線性表的指針實(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第三章 線性表3.1 抽象數(shù)據(jù)型線性表3 1隊(duì)列的順序表示和實(shí)現(xiàn) 用內(nèi)存中一組連續(xù)的存儲(chǔ)單元（數(shù)組）存放隊(duì)列中的各元素，簡(jiǎn)稱順序隊(duì)列。 3.4.2、 順序隊(duì)列4 1隊(duì)列的順序表示和實(shí)現(xiàn)3.4.2、 順序隊(duì)列4struct QUEUE elementtype elementsmaxlength; int front; /指向隊(duì)頭元素的位置 int rear; /指向隊(duì)頭元素的位置; QUEUE Q

3、;QUEUE *Q;常見(jiàn)用法 elementtype elementsmaxlength; int front; /指向隊(duì)頭元素的位置 int rear; /指向隊(duì)尾元素的位置2、C語(yǔ)言表示3.4.2、 順序隊(duì)列5struct QUEUE常見(jiàn)用法 2、C語(yǔ)言表示3.4.2、43210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=03.4.2、 順序隊(duì)列643210Q.rear=-1AQ.rear=0BAQ.rea43210EDCBAQ.rear=4Q.front=0EDCBQ.rear=

4、4Q.front=1EDCQ.rear=4Q.front=2什么是假上溢現(xiàn)象？Q.rear=4Q.front=43.4.2、 順序隊(duì)列743210EDCBAQ.rear=4EDCBQ.rear=4 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 4.循環(huán)隊(duì)列EDC Q.rear=4EDCFQ.EDCGFQ.rear=1Q.front=2CQ.rear=1Q.front=1Q.rear=1Q.front=2滿隊(duì)列

5、：尾指針比頭指針滯后一個(gè)位置；EDCFQ.rear=0Q.front=2空隊(duì)列：尾指針比頭指針滯后一個(gè)位置；3.4.2、 順序隊(duì)列9EDCGFQ.rear=1CQ.rear=1Q.rear=1(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(2)處理循環(huán)隊(duì)列滿還空的兩種方法:EDCFQ.rear=0a.置空隊(duì)列 MAKENULL(QUEUE &Q) Q.

6、front=0; Q.rear=maxlength-1; 3.4.2、 順序隊(duì)列11a.置空隊(duì)列3.4.2、 順序隊(duì)列11b.判隊(duì)空 boolean EMPTY(QUEUE Q) if(Q-rear+1)%maxlength =Q-front) return TRUE; else return FALSE; C.判隊(duì)滿 boolean FULL(sequeue Q) if(Q-rear+2)%maxlength =Q-front) return TRUE; else return FALSE; 3.4.2、 順序隊(duì)列12b.判隊(duì)空C.判隊(duì)滿3.4.2、 順序隊(duì)列12d.取隊(duì)頭元素 elemen

7、ttype FRONT(QUEUE Q) if(EMPTY(Q) return NULL; else return Q.elementsQ.front; 3.4.2、 順序隊(duì)列13d.取隊(duì)頭元素3.4.2、 順序隊(duì)列13e.入隊(duì) void ENQUEUE(elementtype x,QUEUE &Q) if(FULL(Q) error(“queue is full”); else Q.rear=(Q.rear+1)%maxlength; Q.elementsQ.rear=x; 3.4.2、 順序隊(duì)列14e.入隊(duì)3.4.2、 順序隊(duì)列14E.出隊(duì) void DEQUEUE(QUEUE &Q) i

8、f(EMPTY(Q) error(“queue is empty”); else Q.front=(Q.front+1)%maxlength; 3.4.2、 順序隊(duì)列15E.出隊(duì)3.4.2、 順序隊(duì)列15DCsq-rear=3sq-front=2DCsq-rear=0sq-front=43.4.2、 順序隊(duì)列F. 隊(duì)列長(zhǎng)度 16DCsq-rear=3DCsq-rear=03.4.2、int queuelength(sequeue Q)return (sq-rear-sq-front+MaxSize+1)%MaxSize;#3.4.2、 順序隊(duì)列17int queuelength(sequeue

9、 Q)#3.4 3.5、多項(xiàng)式的代數(shù)運(yùn)算假設(shè)多項(xiàng)式的形式為:其中ai0,指數(shù)ei滿足emem-1e2e1=0.18 3.5、多項(xiàng)式的代數(shù)運(yùn)算假設(shè)多項(xiàng)式的形式為:其中 3.5、多項(xiàng)式的代數(shù)運(yùn)算鏈表實(shí)現(xiàn)：1、結(jié)構(gòu)形式：coefexplinkstruct polynodeint coef; int exp; polynode link;typedef polynode *polypointer;19 3.5、多項(xiàng)式的代數(shù)運(yùn)算鏈表實(shí)現(xiàn)：1、結(jié)構(gòu)形式： 3.5、多項(xiàng)式的代數(shù)運(yùn)算2、增加新結(jié)點(diǎn)，鏈在鏈表尾端polypointer attach(int c,int e,polypointer d)polyp

10、ointer x; x=new polynode; x-coef=c; x-exp=e; d-link=x; return x;20 3.5、多項(xiàng)式的代數(shù)運(yùn)算2、增加新結(jié)點(diǎn)，鏈在鏈表 3.5、多項(xiàng)式的代數(shù)運(yùn)算3、加法實(shí)現(xiàn)(無(wú)頭結(jié)點(diǎn),設(shè)兩個(gè)多項(xiàng)式為a和b)polypointer padd(polypointer a,polypointer b)polypointer p,q,d,c; int x; p=a;q=b; c=new polynode;d=c; 21 3.5、多項(xiàng)式的代數(shù)運(yùn)算3、加法實(shí)現(xiàn)(無(wú)頭結(jié)點(diǎn), 3.5、多項(xiàng)式的代數(shù)運(yùn)算while(p!=NULL)&(q!=NULL) switch

11、(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 3.5、多項(xiàng)式的代數(shù)運(yùn)算while(p!=N 3.5、多項(xiàng)式的代數(shù)運(yùn)算 case : d=attach(p-coef,p-exp,d) p=p-link; break; case coef,q-exp,d) q=q-link; break;23 3.5、多項(xiàng)式的代數(shù)運(yùn)算 case : 3.5、多項(xiàng)式的代數(shù)運(yùn)算 while(p!=NULL) d=attach(q-coef,q-exp,d)

12、; p=p-link; while(q!=NULL) d=attach(q-coef,q-exp,d); q=q-link; 24 3.5、多項(xiàng)式的代數(shù)運(yùn)算 while(p!=N 3.5、多項(xiàng)式的代數(shù)運(yùn)算刪除臨時(shí)結(jié)點(diǎn) d-link=NULL; p=c;c=c-link;delete p; return c; *25 3.5、多項(xiàng)式的代數(shù)運(yùn)算刪除臨時(shí)結(jié)點(diǎn) d-l 3.6、串一、串的概念1.串(String)的定義是由零個(gè)或多個(gè)字符組成的有限序列。記為：s=”a1a2an” (n0)其中，s是串的名，用雙引號(hào)括起來(lái)的字符序列是串的值。2.串的長(zhǎng)度:串中字符的數(shù)目n。3.空串(Null string

13、):長(zhǎng)度為零的串。4.子串:串中任意個(gè)連續(xù)的字符組成的子序列。26 3.6、串一、串的概念265. 主串:包含子串的串相應(yīng)地稱為主串。6. 位置:字符在序列中的序號(hào)。子串在主串中的位置則以子串的第一個(gè)字符在主串的位置來(lái)表示。7.串相等:只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相等，稱兩串相等。8.空格串(空白串)(blank string)由一個(gè)或多個(gè)空格組成的串。要和“空串”區(qū)別，空格串有長(zhǎng)度就是空格的個(gè)數(shù)。 3.6、串275. 主串:包含子串的串相應(yīng)地稱為主串。 3.6、 二、串與線性表的區(qū)別? 1、串?dāng)?shù)據(jù)對(duì)象約束為字符集。 2、基本操作的對(duì)象不同，線性表以“單個(gè)元素”為操作對(duì)象；

14、串以“串的整體”為操作對(duì)象，操作的一般都是子串。 3.6、串28 二、串與線性表的區(qū)別? 3.6、串28 三、基本操作： (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 三、基本操作： 3.6、串*29 3.6.2 串的表示(存儲(chǔ)結(jié)構(gòu))一、順序表示二、鏈接存儲(chǔ)(定長(zhǎng)與不定長(zhǎng))30 3.6.2 串的表示(存儲(chǔ)結(jié)構(gòu))一、順序#define MAXSIZE 255struct seqstring char strM

15、AXSIZE; int len; ; seqstring s; 3.6.2 串的表示-順序表示31#define MAXSIZE 2553.6.2 串的表示int strcmp(s,t) seqstring s,t; int i=0; while (is.len & it.stri) return(1); else if (s.strit.len) return(1);else if (s.lendata=q-data) q=q-link; if(q=NULL) retrun(first); p=p-link;3.6.2 操作子串定位elsefirst=first-link; p=first;

16、q=S1; return null;35int INDEX(S,S1)3.6.2 操作子串定位e算法分析(最好情況下的平均時(shí)間復(fù)雜度)如：S：a b c d e f g h j k l m (主串長(zhǎng)度為n)T：j k l (子串長(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 操作子串定位36算法分析(最好情況下的平均時(shí)間復(fù)雜度)3.6.2 操作子最壞的情況時(shí)間復(fù)雜度為如：S：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1T：0 0 0 0 0 0 1若第i趟比較成功，共比較了多少次？前i-1趟比較每次都比較m次，第i趟也比較m次共im次i從1到n-m+1共比較了(n-m+2)(n-m+1)m/2平均比較次數(shù)(n-m+2)m/2最壞的情況時(shí)間復(fù)雜度為O(nm)3.6.2 操作子串定位37最壞的情況時(shí)間復(fù)雜度為3.6.2 操作子串定位37如果一個(gè)結(jié)點(diǎn)只存一個(gè)字符,空間浪費(fèi)嚴(yán)重:如果采用16位地址,一個(gè)字符點(diǎn)8位;實(shí)際利用率只有1/33.6.2 串的表示-鏈?zhǔn)酱鎯?chǔ)采用一個(gè)結(jié)點(diǎn)中存m個(gè)字符;38如果一個(gè)結(jié)點(diǎn)只存一個(gè)字符,