多项式的代数运算和串

多项式的代数运算和串第一页，共四十页，2022年，8月28日1作业问题3.3对于用如下方式实现的已排序的线性表:(a)数组;(b)指针写出INSERT,DELETE和LOCATE的程序3.6已知一个单链式线性表如图3-27所示,试给一个算法将该线性表复制一个拷贝。Fa1a2an^…3.5写出一个交换单向链表中位置P和NEXT(P)的元素的程序。第二页，共四十页，2022年，8月28日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、广义表第三页，共四十页，2022年，8月28日3

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

顺序队列第四页，共四十页，2022年，8月28日4structQUEUE{elementtypeelements[maxlength];intfront;//指向队头元素的位置

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

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

顺序队列第五页，共四十页，2022年，8月28日543210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=0、

顺序队列第六页，共四十页，2022年，8月28日643210EDCBAQ.rear=4Q.front=0EDCBQ.rear=4Q.front=1EDCQ.rear=4Q.front=2什么是假上溢现象？Q.rear=4Q.front=4、

顺序队列第七页，共四十页，2022年，8月28日7

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

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

顺序队列第八页，共四十页，2022年，8月28日8EDCGFQ.rear=1Q.front=2CQ.rear=1Q.front=1Q.rear=1Q.front=2满队列：尾指针比头指针滞后一个位置；EDCFQ.rear=0Q.front=2空队列：尾指针比头指针滞后一个位置；、

顺序队列第九页，共四十页，2022年，8月28日9(2)处理循环队列满还空的两种方法:a.另设一个标志以区别队列是“空”还是“满”；b.队满条件为：(Q.rear+2)%maxlength==Q->front队空条件为：(Q.rear+1)%maxlength==Q->frontEDCFQ.rear=0Q.front=2、

顺序队列第十页，共四十页，2022年，8月28日10a.置空队列

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

顺序队列第十一页，共四十页，2022年，8月28日11b.判队空

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

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

顺序队列第十二页，共四十页，2022年，8月28日12d.取队头元素

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

returnQ.elements[Q.front];}、

顺序队列第十三页，共四十页，2022年，8月28日13e.入队

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

顺序队列第十四页，共四十页，2022年，8月28日14E.出队

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

顺序队列第十五页，共四十页，2022年，8月28日15DCsq->rear=3sq->front=2DCsq->rear=0sq->front=4、

顺序队列F.队列长度第十六页，共四十页，2022年，8月28日16intqueuelength(sequeueQ){return(sq->rear-sq->front+MaxSize+1)%MaxSize;}#、

顺序队列第十七页，共四十页，2022年，8月28日17

3.5、多项式的代数运算假设多项式的形式为:其中ai≠0,指数ei满足em>em-1>…>e2>e1>=0.第十八页，共四十页，2022年，8月28日18

3.5、多项式的代数运算链表实现：1、结构形式：coefexplinkstructpolynode{intcoef;intexp;polynodelink;};typedefpolynode*polypointer;第十九页，共四十页，2022年，8月28日19

3.5、多项式的代数运算2、增加新结点，链在链表尾端polypointerattach(intc,inte,polypointerd){polypointerx;x=newpolynode;x->coef=c;x->exp=e;d->link=x;returnx;}第二十页，共四十页，2022年，8月28日20

3.5、多项式的代数运算3、加法实现(无头结点,设两个多项式为a和b)polypointerpadd(polypointera,polypointerb){polypointerp,q,d,c;intx;p=a;q=b;c=newpolynode;d=c;第二十一页，共四十页，2022年，8月28日21

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;第二十二页，共四十页，2022年，8月28日22

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;第二十三页，共四十页，2022年，8月28日23

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;}第二十四页，共四十页，2022年，8月28日24

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

d->link=NULL;p=c;c=c->link;deletep;returnc;}**第二十五页，共四十页，2022年，8月28日25

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

3.6、串第二十七页，共四十页，2022年，8月28日27二、串与线性表的区别?1、串数据对象约束为字符集。

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

3.6、串第二十八页，共四十页，2022年，8月28日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、串*第二十九页，共四十页，2022年，8月28日29

3.6.2串的表示(存储结构)一、顺序表示二、链接存储(定长与不定长)第三十页，共四十页，2022年，8月28日30#defineMAXSIZE255structseqstring

{charstr[MAXSIZE];

intlen;

};seqstrings;3.6.2串的表示-顺序表示第三十一页，共四十页，2022年，8月28日31intstrcmp(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);}*第三十二页，共四十页，2022年，8月28日321、单字符链式存储的C语言表示

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