多项式的代数运算和串解读ppt课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,作业问题,3.2,FIRST,执行次数,END,执行次数,NEXT,执行次数,1,作业问题,3.3,对于用如下方式实现的,已排序,的线性表,:,(a),数组,;(b),指针,写出,INSERT,DELETE,和,LOCATE,的程序,3.6,已知一个单链式线性表如图,3-27,所示,试给一个算法将该线性表复制一个拷贝。,F,a1,a2,an,3.5,写出一个交换单向链表中位置,P,和,NEXT(P),的元素的程序。,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,1,队列的顺序表示和实现,用内存中一组连续的存储单元（数组）存放队列中的各元素，简称顺序队列。,3.4.2,、,顺序队列,4,struct,QUEUE,elementtype,elementsmaxlength,;,int front;/,指向队头元素的位置,int rear;/,指向队头元素的位置,;,QUEUE Q;QUEUE*Q;,常见用法,elementtype,elementsmaxlength,;,int front;/,指向队头元素的位置,int rear;/,指向队尾元素的位置,2,、,C,语言表示,3.4.2,、,顺序队列,5,4,3,2,1,0,Q.rear,=-1,Q.front,=-1,A,Q.rear,=0,Q.front,=0,B,A,Q.rear,=1,Q.front,=0,E,D,C,B,A,Q.rear,=4,Q.front,=0,3.4.2,、,顺序队列,6,4,3,2,1,0,E,D,C,B,A,Q.rear,=4,Q.front,=0,E,D,C,B,Q.rear,=4,Q.front,=1,E,D,C,Q.rear,=4,Q.front,=2,什么是假上溢现象？,Q.rear,=4,Q.front,=4,3.4.2,、,顺序队列,7,4.,循环队列,把顺序队列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。,E,D,C,Q.rear,=4,Q.front,=2,E,D,C,F,Q.rear,=0,Q.front,=2,E,D,C,G,F,Q.rear,=1,Q.front,=2,3.4.2,、,顺序队列,8,E,D,C,G,F,Q.rear,=1,Q.front,=2,C,Q.rear,=1,Q.front,=1,Q.rear,=1,Q.front,=2,满队列：尾指针比头指针滞后一个位置；,E,D,C,F,Q.rear,=0,Q.front,=2,空队列：尾指针比头指针滞后一个位置；,3.4.2,、,顺序队列,9,(2),处理循环队列满还空的两种方法,:,a.,另设一个标志以区别队列是“空”还是“满”；,b.,队满条件为：,(Q.rear+2)%maxlength=Q-front,队空条件为：,(Q.rear+1)%maxlength=Q-front,E,D,C,F,Q.rear,=0,Q.front,=2,3.4.2,、,顺序队列,10,a.,置空队列,MAKENULL(QUEUE&Q),Q.front,=0;,Q.rear,=maxlength-1;,3.4.2,、,顺序队列,11,b.,判队空,boolean,EMPTY(QUEUE Q),if(Q,-rear+1)%maxlength=Q-front),return TRUE;,else,return FALSE;,C.,判队满,boolean,FULL(sequeue,Q),if(Q,-rear+2)%maxlength=Q-front),return TRUE;,else return FALSE;,3.4.2,、,顺序队列,12,d.,取队头元素,elementtype,FRONT(QUEUE Q),if(EMPTY(Q,),return NULL;,else,return,Q.elementsQ.front,;,3.4.2,、,顺序队列,13,e.,入队,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,、,顺序队列,14,E.,出队,void DEQUEUE(QUEUE&Q),if(EMPTY(Q,),error(“queue,is empty”);,else,Q.front,=(Q.front+1)%maxlength;,3.4.2,、,顺序队列,15,D,C,sq-rear=3,sq-front=2,D,C,sq-rear=0,sq-front=4,3.4.2,、,顺序队列,F.,队列长度,16,int,queuelength(sequeue,Q),return(sq-rear-sq-front+MaxSize+1)%MaxSize;,#,3.4.2,、,顺序队列,17,3.5,、多项式的代数运算,假设多项式的形式为,:,其中,a,i,0,指数,e,i,满足,e,m,e,m-1,e,2,e,1,=0,.,18,3.5,、多项式的代数运算,链表实现：,1,、结构形式：,coef,exp,link,struct,polynode,int,coef,;,int,exp;,polynode,link;,;,typedef,polynode,*,polypointer,;,19,3.5,、多项式的代数运算,2,、增加新结点，链在链表尾端,polypointer,attach(int,c,int,e,polypointer,d),polypointer,x;,x=new,polynode,;,x-,coef,=c;,x-exp=e;,d-link=x;,return x;,20,3.5,、多项式的代数运算,3,、加法实现,(,无头结点,设两个多项式为,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,、多项式的代数运算,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,3.5,、多项式的代数运算,case:,d=,attach(p,-,coef,p,-,exp,d,),p=p-link;,break;,case,coef,q,-,exp,d,),q=q-link;,break;,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;,24,3.5,、多项式的代数运算,删除临时结点,d-link=NULL;,p=,c;c,=c-,link;delete,p;,return c;,*,25,3.6,、串,一、串的概念,1.,串,(String),的定义,是由零个或多个字符组成的有限序列。,记为：,s=”a,1,a,2,a,n,”(n0),其中，,s,是串的名，用双引号括起来的字符序列是串的值。,2.,串的长度,:,串中字符的数目,n,。,3.,空串,(Null string),:,长度为零的串。,4.,子串,:,串中任意个连续的字符组成的子序列。,26,5.,主串,:,包含子串的串相应地称为主串。,6.,位置,:,字符在序列中的序号。,子串在主串中的位置则以子串的第一个字符在主串的位置来表示。,7.,串相等,:,只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。,8.,空格串,(,空白串,)(blank string),由一个或多个空格组成的串。要和“空串”区别，空格串有长度就是空格的个数。,3.6,、串,27,二、串与线性表的区别,?,1,、串数据对象约束为,字符集,。,2,、基本操作的对象不同，线性表以“单个元素”为操作对象；串以“,串的整体,”为操作对象，操作的一般都是子串。,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.2,串的表示,(,存储结构,),一、顺序表示,二、链接存储,(,定长与不定长,),30,#define MAXSIZE 255,struct,seqstring,char,strMAXSIZE,;,int,len,;,;,seqstring,s;,3.6.2,串的表示,-,顺序表示,31,int,strcmp(s,t,),seqstring,s,t,;,int i=0;,while(i,s.len,&i,t.stri,),return(1);,else,if(,s.stri,t.len,),return(1);,else,if(,s.len,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;,return null;,35,算法分析,(,最好情况下的平均时间复杂度,),如：,S,：,a b c d e f g h,j k l,m (,主串长度为,n),T,：,j k l,(,子串长度为,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,操作,子串定位,36,最坏的情况时间复杂度为,如：,S,：,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1,T,：,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,平均比较次数,(n-m+2)m/2,最坏的情况时间复杂度为,O(n,m,),3.6.2,操作,子串定位,37,如果一个结点只存一个字符,空间浪费严重,:,如果采用,16,位地址,一个字符点,8,位,;,实际利用率只有,1/3,3.6.2,串的表示,-,链式存储,采用一个结点中存,m,个字符,;,38,3.6.2,串的表示,-,链式存储,1,、一个结点存,4,个字符的链式存储的,C,语言表示,struct,node,char data4;,node*link;,;,Typedef,node*STRING;,39,3.6.2,串的表示,-,定长链式存储,一、删除操作,:,1,、移动,2,、用空白填充，一个结点全空白时删除。,二、插入操作,