多项式的代数运算和串.ppt

1、1,作业问题,3.2,FIRST执行次数,END执行次数,NEXT执行次数,2,作业问题,3.3 对于用如下方式实现的已排序的线性表: (a)数组;(b)指针 写出INSERT,DELETE和LOCATE的程序,3.6 已知一个单链式线性表如图3-27所示,试给一个算法将该线性表复制一个拷贝。,F,3.5 写出一个交换单向链表中位置P和NEXT(P)的元素的程序。,3,第三章 线性表,3.1 抽象数据型线性表 3.2 线性表的实现 3.2.1 指针和游标 3.2.2 线性表的数组实现 3.2.3 线性表的指针实现 3.2.4 线性表的游标实现 3.2.5 双向链接表 3.2.6 环形链表(循环

2、链表) 3.3 栈 3.4 排队(队列) 3.5 多项式的代数运算 3.6 串、3.7 数组、3.8、广义表,4,1队列的顺序表示和实现 用内存中一组连续的存储单元（数组）存放队列中的各元素，简称顺序队列。,3.4.2、 顺序队列,5,struct QUEUE elementtype elementsmaxlength; int front; /指向队头元素的位置 int rear; /指向队头元素的位置 ; QUEUE Q;QUEUE *Q;,常见用法 elementtype elementsmaxlength; int front; /指向队头元素的位置 int rear; /指向队尾元素

3、的位置,2、C语言表示,3.4.2、 顺序队列,6,Q.rear=-1 Q.front=-1,Q.rear=0 Q.front=0,Q.rear=1 Q.front=0,Q.rear=4 Q.front=0,3.4.2、 顺序队列,7,Q.rear=4 Q.front=0,Q.rear=4 Q.front=1,Q.rear=4 Q.front=2,什么是假上溢现象？,Q.rear=4 Q.front=4,3.4.2、 顺序队列,8,4.循环队列 把顺序队列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。,Q.rear=4 Q.front=2,Q.rear=0 Q.front=2,Q.r

4、ear=1 Q.front=2,3.4.2、 顺序队列,9,Q.rear=1 Q.front=2,Q.rear=1 Q.front=1,Q.rear=1 Q.front=2,满队列：尾指针比头指针滞后一个位置；,Q.rear=0 Q.front=2,空队列：尾指针比头指针滞后一个位置；,3.4.2、 顺序队列,10,(2)处理循环队列满还空的两种方法: a.另设一个标志以区别队列是“空”还是“满”； b.队满条件为： (Q.rear+2)%maxlength=Q-front 队空条件为： (Q.rear+1)%maxlength =Q-front,Q.rear=0 Q.front=2,3.4.

5、2、 顺序队列,11,a.置空队列 MAKENULL(QUEUE ,3.4.2、 顺序队列,12,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、 顺序队列,13,d.取队头元素 elementtype FRONT(QUEUE Q) if(EMPTY(Q

6、) return NULL; else return Q.elementsQ.front; ,3.4.2、 顺序队列,14,e.入队 void ENQUEUE(elementtype x,QUEUE ,3.4.2、 顺序队列,15,E.出队 void DEQUEUE(QUEUE ,3.4.2、 顺序队列,16,sq-rear=3 sq-front=2,sq-rear=0 sq-front=4,3.4.2、 顺序队列,F. 队列长度,17,int queuelength(sequeue Q) return (sq-rear-sq-front+MaxSize+1)%MaxSize; ,#,3.4.

7、2、 顺序队列,18,3.5、多项式的代数运算,假设多项式的形式为:,其中ai0,指数ei满足emem-1e2e1=0.,19,3.5、多项式的代数运算,链表实现：,1、结构形式：,struct polynode int coef; int exp; polynode link; ; typedef polynode *polypointer;,20,3.5、多项式的代数运算,2、增加新结点，链在链表尾端,polypointer attach(int c,int e,polypointer d),polypointer x; x=new polynode; x-coef=c; x-exp=e;

8、 d-link=x; return x; ,21,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;,22,3.5、多项式的代数运算,while(p!=NULL),23,3.5、多项式的代数运算,case : d=attach(p-coef,p-exp,d) p=p-link; break;,case coef,q-exp,d) q=q-link; break;,24,

9、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; ,25,3.5、多项式的代数运算,删除临时结点,d-link=NULL; p=c;c=c-link;delete p; return c; ,*,26,3.6、串,一、串的概念 1.串(String)的定义 是由零个或多个字符组成的有限序列。 记为：s=”a1a2an” (n0) 其中，s是串的名，用双引号括起来的字符序列是串的值。 2.串的长度:串中字符的数目n。

10、 3.空串(Null string):长度为零的串。 4.子串:串中任意个连续的字符组成的子序列。,27,5. 主串:包含子串的串相应地称为主串。 6. 位置:字符在序列中的序号。 子串在主串中的位置则以子串的第一个字符在主串的位置来表示。 7.串相等: 只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。 8.空格串(空白串)(blank string) 由一个或多个空格组成的串。要和“空串”区别，空格串有长度就是空格的个数。,3.6、串,28,二、串与线性表的区别? 1、串数据对象约束为字符集。 2、基本操作的对象不同，线性表以“单个元素”为操作对象；串以“串的整体”为操作对

11、象，操作的一般都是子串。,3.6、串,29,三、基本操作： (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、串,*,30,3.6.2 串的表示(存储结构),一、顺序表示 二、链接存储(定长与不定长),31,#define MAXSIZE 255 struct seqstring char strMAXSIZE; int len; ; seqstring s;,3.6.2 串的表示-顺序表示,32,int strcmp(

12、s,t) seqstring s,t; int i=0; while (it.stri) return(1); else if (s.strit.stri) return(-1); else i+; ,3.6.2 串的操作串比较,if (s.lent.len) return(1); else if (s.lent.len) return(-1); else return(0); ,*,33,1、单字符链式存储的C语言表示 struct node char data; node *link; ; typedef node *STRING;,3.6.2 串的表示-链接表示,34,子串定位（模式匹配

13、）index(S,S1)的实现 S为主串，S1为子串，又叫模式串 如果S中存在子串S1，返回S1第一个字符在主串中的位置（第几个）； 如果S中不存在子串S1，返回零。,3.6.2 操作子串定位,35,int INDEX(S,S1) STRING S,S1; node *p,*q,*first; if(S1!=NULL),3.6.2 操作子串定位,else first=first-link; p=first;q=S1; return null; ,36,算法分析(最好情况下的平均时间复杂度) 如： S：a b c d e f g h j k l m (主串长度为n) T：j k l (子串长度为

14、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 操作子串定位,37,最坏的情况时间复杂度为 如： 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(nm),3.6.2 操作子串定位,38,如果一个结点只存一个字符,空间浪费严重:,如果采用16位地址,一个字符点8位;实际利用率只有1/3,3.6.2 串的表示