多项式的代数运算和串

多项式的代数运算和串1第1页，课件共40页，创作于2023年2月作业问题3.3对于用如下方式实现的已排序的线性表:(a)数组;(b)指针写出INSERT,DELETE和LOCATE的程序3.6已知一个单链式线性表如图3-27所示,试给一个算法将该线性表复制一个拷贝。Fa1a2an^…3.5写出一个交换单向链表中位置P和NEXT(P)的元素的程序。2第2页，课件共40页，创作于2023年2月第三章线性表3.1抽象数据型线性表3.2线性表的实现

3.2.1指针和游标

3.2.2线性表的数组实现

3.2.3线性表的指针实现

3.2.4线性表的游标实现

3.2.5双向链接表

3.2.6环形链表(循环链表)3.3栈3.4排队(队列)3.5多项式的代数运算3.6串、3.7数组、3.8、广义表3第3页，课件共40页，创作于2023年2月

1．队列的顺序表示和实现用内存中一组连续的存储单元（数组）存放队列中的各元素，简称顺序队列。3.4.2、

顺序队列4第4页，课件共40页，创作于2023年2月structQUEUE{elementtypeelements[maxlength];intfront;//指向队头元素的位置

intrear;//指向队头元素的位置};QUEUEQ;QUEUE*Q;常见用法elementtypeelements[maxlength];intfront;//指向队头元素的位置

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

顺序队列5第5页，课件共40页，创作于2023年2月43210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=03.4.2、

顺序队列6第6页，课件共40页，创作于2023年2月43210EDCBAQ.rear=4Q.front=0EDCBQ.rear=4Q.front=1EDCQ.rear=4Q.front=2什么是假上溢现象？Q.rear=4Q.front=43.4.2、

顺序队列7第7页，课件共40页，创作于2023年2月

4.循环队列把顺序队列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。EDC

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

顺序队列8第8页，课件共40页，创作于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页，创作于2023年2月(2)处理循环队列满还空的两种方法:a.另设一个标志以区别队列是“空”还是“满”；b.队满条件为：(Q.rear+2)%maxlength==Q->front队空条件为：(Q.rear+1)%maxlength==Q->frontEDCFQ.rear=0Q.front=23.4.2、

顺序队列10第10页，课件共40页，创作于2023年2月a.置空队列

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

顺序队列11第11页，课件共40页，创作于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页，创作于2023年2月d.取队头元素

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

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

顺序队列13第13页，课件共40页，创作于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页，创作于2023年2月E.出队

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

顺序队列15第15页，课件共40页，创作于2023年2月DCsq->rear=3sq->front=2DCsq->rear=0sq->front=43.4.2、

顺序队列F.队列长度16第16页，课件共40页，创作于2023年2月intqueuelength(sequeueQ){return(sq->rear-sq->front+MaxSize+1)%MaxSize;}#3.4.2、

顺序队列17第17页，课件共40页，创作于2023年2月

3.5、多项式的代数运算假设多项式的形式为:其中ai≠0,指数ei满足em>em-1>…>e2>e1>=0.18第18页，课件共40页，创作于2023年2月

3.5、多项式的代数运算链表实现：1、结构形式：coefexplinkstructpolynode{intcoef;intexp;polynodelink;};typedefpolynode*polypointer;19第19页，课件共40页，创作于2023年2月

3.5、多项式的代数运算2、增加新结点，链在链表尾端polypointerattach(intc,inte,polypointerd){polypointerx;x=newpolynode;x->coef=c;x->exp=e;d->link=x;returnx;}20第20页，课件共40页，创作于2023年2月

3.5、多项式的代数运算3、加法实现(无头结点,设两个多项式为a和b)polypointerpadd(polypointera,polypointerb){polypointerp,q,d,c;intx;p=a;q=b;c=newpolynode;d=c;21第21页，课件共40页，创作于2023年2月

3.5、多项式的代数运算{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页，创作于2023年2月

3.5、多项式的代数运算

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页，创作于2023年2月

3.5、多项式的代数运算

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页，创作于2023年2月

3.5、多项式的代数运算删除临时结点

d->link=NULL;p=c;c=c->link;deletep;returnc;}**25第25页，课件共40页，创作于2023年2月

3.6、串一、串的概念1.串(String)的定义是由零个或多个字符组成的有限序列。记为：s=”a1a2…an”(n≥0)其中，s是串的名，用双引号括起来的字符序列是串的值。2.串的长度:串中字符的数目n。3.空串(Nullstring):长度为零的串。4.子串:串中任意个连续的字符组成的子序列。26第26页，课件共40页，创作于2023年2月5.主串:包含子串的串相应地称为主串。6.位置:字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串的位置来表示。7.串相等:只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。8.空格串(空白串)(blankstring)由一个或多个空格组成的串。要和“空串”区别，空格串有长度就是空格的个数。

3.6、串27第27页，课件共40页，创作于2023年2月二、串与线性表的区别?1、串数据对象约束为字符集。

2、基本操作的对象不同，线性表以“单个元素”为操作对象；串以“串的整体”为操作对象，操作的一般都是子串。

3.6、串28第28页，课件共40页，创作于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页，创作于2023年2月

3.6.2串的表示(存储结构)一、顺序表示二、链接存储(定长与不定长)30第30页，课件共40页，创作于2023年2月#defineMAXSIZE255structseqstring

{charstr[MAXSIZE];

intlen;

};seqstrings;3.6.2串的表示-顺序表示31第31页，课件共40页，创作于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页，创作于2023年2月1、单字符链式存储的C语言表示

structnode{chardata;node*link;};typedefnode*STRING;3.6.2串的表示--链接表示33第33页，课件共40页，创作于2023年2月子串定位（模式匹配）index(S,S1)的实现S为主串，S1为子串，又叫模式串如果S中存在子串S1，返回S1第一个字符在主串中的位置（第几个）；如果S中不存在子串S1，返回零。3.6.2操作—子串定位34第34页，课件共40页，创作于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页，创作于2023年2月算法分析(最好情况下的平均时间复杂度)如：S：abcdefghjklm(主串长度为n)T：jkl

(子串长度为m)假设从第i个位置匹配成功，前i-1次共比较了i-1次。第i次比较了m次,共比较了i+m-1次。i从1到n-m+1,共(n+m)(n-m+1)/2平均需比较(n+m)/2最好的情况平均时间复杂度为O(n+m)3.6.2