多项式的代数运算和串

1、多项式的代数运算和串第1页，共40页，2022年，5月20日，14点25分，星期二1 作业问题3.3 对于用如下方式实现的已排序的线性表: (a)数组;(b)指针 写出INSERT,DELETE和LOCATE的程序3.6 已知一个单链式线性表如图3-27所示,试给一个算法将该线性表复制一个拷贝。Fa1a2an3.5 写出一个交换单向链表中位置P和NEXT(P)的元素的程序。第2页，共40页，2022年，5月20日，14点25分，星期二2第三章 线性表3.1 抽象数据型线性表3.2 线性表的实现 3.2.1 指针和游标 3.2.2 线性表的数组实现 3.2.3 线性表的指针实现 3.2.4 线性

2、表的游标实现 3.2.5 双向链接表 3.2.6 环形链表(循环链表)3.3 栈3.4 排队(队列)3.5 多项式的代数运算3.6 串、3.7 数组、3.8、广义表第3页，共40页，2022年，5月20日，14点25分，星期二3 1队列的顺序表示和实现 用内存中一组连续的存储单元（数组）存放队列中的各元素，简称顺序队列。 、 顺序队列第4页，共40页，2022年，5月20日，14点25分，星期二4struct QUEUE elementtype elementsmaxlength; int front; /指向队头元素的位置 int rear; /指向队头元素的位置; QUEUE Q;QUEU

3、E *Q;常见用法 elementtype elementsmaxlength; int front; /指向队头元素的位置 int rear; /指向队尾元素的位置2、C语言表示、 顺序队列第5页，共40页，2022年，5月20日，14点25分，星期二543210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=0、 顺序队列第6页，共40页，2022年，5月20日，14点25分，星期二643210EDCBAQ.rear=4Q.front=0EDCBQ.rear=4Q.front=1EDC

4、Q.rear=4Q.front=2什么是假上溢现象？Q.rear=4Q.front=4、 顺序队列第7页，共40页，2022年，5月20日，14点25分，星期二7 4.循环队列 把顺序队列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。EDC Q.rear=4Q.front=2EDCFQ.rear=0Q.front=2EDCGFQ.rear=1Q.front=2、 顺序队列第8页，共40页，2022年，5月20日，14点25分，星期二8EDCGFQ.rear=1Q.front=2CQ.rear=1Q.front=1Q.rear=1Q.front=2满队列：尾指针比头指针滞后一个位置；E

5、DCFQ.rear=0Q.front=2空队列：尾指针比头指针滞后一个位置；、 顺序队列第9页，共40页，2022年，5月20日，14点25分，星期二9(2)处理循环队列满还空的两种方法:a.另设一个标志以区别队列是“空”还是“满”；b.队满条件为：(Q.rear+2)%maxlength=Q-front队空条件为：(Q.rear+1)%maxlength =Q-frontEDCFQ.rear=0Q.front=2、 顺序队列第10页，共40页，2022年，5月20日，14点25分，星期二10a.置空队列 MAKENULL(QUEUE &Q) Q.front=0; Q.rear=maxleng

6、th-1; 、 顺序队列第11页，共40页，2022年，5月20日，14点25分，星期二11b.判队空 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; 、 顺序队列第12页，共40页，2022年，5月20日，14点25分，星期二12d.取队头元素 elementtype FRONT

7、(QUEUE Q) if(EMPTY(Q) return NULL; else return Q.elementsQ.front; 、 顺序队列第13页，共40页，2022年，5月20日，14点25分，星期二13e.入队 void ENQUEUE(elementtype x,QUEUE &Q) if(FULL(Q) error(“queue is full”); else Q.rear=(Q.rear+1)%maxlength; Q.elementsQ.rear=x; 、 顺序队列第14页，共40页，2022年，5月20日，14点25分，星期二14E.出队 void DEQUEUE(QUEUE

8、 &Q) if(EMPTY(Q) error(“queue is empty”); else Q.front=(Q.front+1)%maxlength; 、 顺序队列第15页，共40页，2022年，5月20日，14点25分，星期二15DCsq-rear=3sq-front=2DCsq-rear=0sq-front=4、 顺序队列F. 队列长度 第16页，共40页，2022年，5月20日，14点25分，星期二16int queuelength(sequeue Q)return (sq-rear-sq-front+MaxSize+1)%MaxSize;#、 顺序队列第17页，共40页，2022年

9、，5月20日，14点25分，星期二17 3.5、多项式的代数运算假设多项式的形式为:其中ai0,指数ei满足emem-1e2e1=0.第18页，共40页，2022年，5月20日，14点25分，星期二18 3.5、多项式的代数运算链表实现：1、结构形式：coefexplinkstruct polynodeint coef; int exp; polynode link;typedef polynode *polypointer;第19页，共40页，2022年，5月20日，14点25分，星期二19 3.5、多项式的代数运算2、增加新结点，链在链表尾端polypointer attach(int c

10、,int e,polypointer d)polypointer x; x=new polynode; x-coef=c; x-exp=e; d-link=x; return x;第20页，共40页，2022年，5月20日，14点25分，星期二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页，共40页，2022年，5月20日，14点25分，星期二21 3.5

11、、多项式的代数运算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页，共40页，2022年，5月20日，14点25分，星期二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页，共40页，2022年，5月20日，14点2

12、5分，星期二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页，共40页，2022年，5月20日，14点25分，星期二24 3.5、多项式的代数运算删除临时结点 d-link=NULL; p=c;c=c-link;delete p; return c; *第25页，共40页，2022年，5月20日，14点25分，星期二25 3.6、串一、串的概念1.串(String)的定义是由零个或多个字符组成的有限序

13、列。记为：s=”a1a2an” (n0)其中，s是串的名，用双引号括起来的字符序列是串的值。2.串的长度:串中字符的数目n。3.空串(Null string):长度为零的串。4.子串:串中任意个连续的字符组成的子序列。第26页，共40页，2022年，5月20日，14点25分，星期二265. 主串:包含子串的串相应地称为主串。6. 位置:字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串的位置来表示。7.串相等:只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。8.空格串(空白串)(blank string)由一个或多个空格组成的串。要和“空串”区别，空格串有长度就

14、是空格的个数。 3.6、串第27页，共40页，2022年，5月20日，14点25分，星期二27 二、串与线性表的区别? 1、串数据对象约束为字符集。 2、基本操作的对象不同，线性表以“单个元素”为操作对象；串以“串的整体”为操作对象，操作的一般都是子串。 3.6、串第28页，共40页，2022年，5月20日，14点25分，星期二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页，共40页

15、，2022年，5月20日，14点25分，星期二29 3.6.2 串的表示(存储结构)一、顺序表示二、链接存储(定长与不定长)第30页，共40页，2022年，5月20日，14点25分，星期二30#define MAXSIZE 255struct seqstring char strMAXSIZE; int len; ; seqstring s; 3.6.2 串的表示-顺序表示第31页，共40页，2022年，5月20日，14点25分，星期二31int strcmp(s,t) seqstring s,t; int i=0; while (is.len & it.stri) return(1); el

16、se 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;q=S1; return null;第35页，共40页，2022年，5月20日，14点25分，星期二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次比较了

17、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页，共40页，2022年，5月20日，14点25分，星期二36最坏的情况时间复杂度为如：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平均比较次数(n-m+2)m/2最坏的情况时间复杂度为O(nm)3.6.2 操作子串定位第37页，共40页，2022年，5月20日，14点25分，星期二37如果一个结点只存一个字符,空间浪费严重:如果采用16位地址,一个字符点8位;实际利用率只有1/33.6.2 串的表示-链式存储采用一个结点中存m个字符;第38页，共40页，2022年