1、 作业问题作业问题3.23.2FIRSTFIRST执行次数执行次数12)1(1.)1(1nnnnENDEND执行次数执行次数2)1(122.)1()1()1(nnnnnnnNEXTNEXT执行次数执行次数6)12)(1(2)1(nnnnnn1 作业问题作业问题3.3 3.3 对于用如下方式实现的对于用如下方式实现的已排序已排序的线性表的线性表:(a)(a)数组数组;(b);(b)指针指针 写出写出INSERT,DELETEINSERT,DELETE和和LOCATELOCATE的程序的程序3.6 3.6 已知一个单链式线性表如图已知一个单链式线性表如图3-273-27所示所示,试试给一个算法将该
2、线性表复制一个拷贝。给一个算法将该线性表复制一个拷贝。F Fa1a2an 3.5 3.5 写出一个交换单向链表中位置写出一个交换单向链表中位置P P和和NEXT(P)NEXT(P)的元素的程序。的元素的程序。2第三章第三章 线性表线性表3.1 3.1 抽象数据型线性表抽象数据型线性表3.2 3.2 线性表的实现线性表的实现 3.2.1 3.2.1 指针和游标指针和游标 3.2.2 3.2.2 线性表的数组实现线性表的数组实现 3.2.3 3.2.3 线性表的指针实现线性表的指针实现 3.2.4 3.2.4 线性表的游标实现线性表的游标实现 3.2.5 3.2.5 双向链接表双向链接表 3.2.
3、6 3.2.6 环形链表环形链表(循环链表循环链表)3.3 3.3 栈栈3.4 3.4 排队排队(队列队列)3.5 3.5 多项式的代数运算多项式的代数运算3.6 3.6 串、串、3.7 3.7 数组、数组、3.83.8、广义表、广义表3 1 1队列的顺序表示和实现队列的顺序表示和实现 用内存中一组连续的存储单元（数组）用内存中一组连续的存储单元（数组）存放队列中的各元素，简称顺序队列。存放队列中的各元素，简称顺序队列。3.4.2、顺序队列顺序队列4struct QUEUE elementtype elementsmaxlength;int front;/指向队头元素的位置指向队头元素的位置
4、int rear;/指向队头元素的位置指向队头元素的位置;QUEUE Q;QUEUE*Q;常见用法常见用法 elementtype elementsmaxlength;int front;/指向队头元素的位置指向队头元素的位置 int rear;/指向队尾元素的位置指向队尾元素的位置2、C语言表示语言表示3.4.2、顺序队列顺序队列543210Q.rear=-1Q.front=-1AQ.rear=0Q.front=0BAQ.rear=1Q.front=0EDCBAQ.rear=4Q.front=03.4.2、顺序队列顺序队列643210EDCBAQ.rear=4Q.front=0EDCBQ.r
5、ear=4Q.front=1EDCQ.rear=4Q.front=2什么是假上溢现象？什么是假上溢现象？Q.rear=4Q.front=43.4.2、顺序队列顺序队列7 4.4.循环队列循环队列 把顺序队列构造成一个首尾相连的循环表。把顺序队列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。指针和队列元素之间关系不变。EDC Q.rear=4Q.front=2EDCFQ.rear=0Q.front=2EDCGFQ.rear=1Q.front=23.4.2、顺序队列顺序队列8EDCGFQ.rear=1Q.front=2CQ.rear=1Q.front=1Q.rear=1Q.front=2
6、满队列：尾指针比头指针滞后一个位置；满队列：尾指针比头指针滞后一个位置；EDCFQ.rear=0Q.front=2空队列：尾指针比头指针滞后一个位置；空队列：尾指针比头指针滞后一个位置；3.4.2、顺序队列顺序队列9(2)处理循环队列满还空的两种方法处理循环队列满还空的两种方法:a.另设一个标志以区别队列是另设一个标志以区别队列是“空空”还是还是“满满”；b.队满条件为：队满条件为：(Q.rear+2)%maxlength=Q-front队空条件为：队空条件为：(Q.rear+1)%maxlength=Q-frontEDCFQ.rear=0Q.front=23.4.2、顺序队列顺序队列10a.
7、置空队列置空队列 MAKENULL(QUEUE&Q)Q.front=0;Q.rear=maxlength-1;3.4.2、顺序队列顺序队列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;3.4.2、顺序队列顺序队列12d.d.取队头元素取队头元素 elementtypeel
8、ementtype FRONT(QUEUE Q)FRONT(QUEUE Q)if(EMPTY(Qif(EMPTY(Q)return NULL;return NULL;else else return Q.elementsQ.front;3.4.2、顺序队列顺序队列13e.e.入队入队 void void ENQUEUE(elementtypeENQUEUE(elementtype x,QUEUEx,QUEUE&Q)&Q)if(FULL(Qif(FULL(Q)error(“queueerror(“queue is full”);is full”);else else Q.rearQ.rear=(
9、Q.rear+1)%maxlength;=(Q.rear+1)%maxlength;Q.elementsQ.rearQ.elementsQ.rear=x;=x;3.4.2、顺序队列顺序队列14E.E.出队出队 void DEQUEUE(QUEUE&Q)void DEQUEUE(QUEUE&Q)if(EMPTY(Qif(EMPTY(Q)error(“queueerror(“queue is empty”);is empty”);else else Q.frontQ.front=(Q.front+1)%maxlength;=(Q.front+1)%maxlength;3.4.2、顺序队列顺序队列1
10、5DCsq-rear=3sq-front=2DCsq-rear=0sq-front=43.4.2、顺序队列顺序队列F.F.队列长度队列长度 16intint queuelength(sequeuequeuelength(sequeue Q)Q)return(sq-rear-sq-front+MaxSize+1)%MaxSize;return(sq-rear-sq-front+MaxSize+1)%MaxSize;#3.4.2、顺序队列顺序队列17 3.5、多项式的代数运算、多项式的代数运算假设多项式的形式为假设多项式的形式为:1111.)(eememxaxaxaxAmm其中其中a ai i0,
11、指数指数ei i满足满足em mem-1m-1e2 2e1 1=0.18 3.5、多项式的代数运算、多项式的代数运算链表实现：链表实现：1 1、结构形式：、结构形式：coefexplinkstructstruct polynodepolynode intint coefcoef;intint exp;exp;polynodepolynode link;link;typedeftypedef polynodepolynode *polypointerpolypointer;19 3.5、多项式的代数运算、多项式的代数运算2 2、增加新结点，链在链表尾端、增加新结点，链在链表尾端polypoint
12、erpolypointer attach(intattach(int c,intc,int e,polypointere,polypointer d)d)polypointerpolypointer x;x;x=new x=new polynodepolynode;x-x-coefcoef=c;=c;x-exp=e;x-exp=e;d-link=x;d-link=x;return x;return x;20 3.5、多项式的代数运算、多项式的代数运算3 3、加法实现、加法实现(无头结点无头结点,设两个多项式为设两个多项式为a a和和b)b)polypointerpolypointer padd
13、(polypointerpadd(polypointer a,polypointera,polypointer b)b)polypointerpolypointer p,q,d,cp,q,d,c;intint x;x;p=p=a;qa;q=b;=b;c=new c=new polynode;dpolynode;d=c;=c;21 3.5、多项式的代数运算、多项式的代数运算 while(pwhile(p!=!=NULL)&(qNULL)&(q!=NULL)!=NULL)switch(compare(pswitch(compare(p-exp,qexp,q-exp)-exp)case=:case=
14、:x=p-x=p-coef+qcoef+q-coefcoef;if(xif(x!=0)!=0)d=d=attach(x,pattach(x,p-exp,dexp,d)p=p-link;p=p-link;q=q-link;q=q-link;break;break;22 3.5、多项式的代数运算、多项式的代数运算 case:case:d=d=attach(pattach(p-coef,pcoef,p-exp,dexp,d)p=p-link;p=p-link;break;break;case:case-coef,qcoef,q-exp,dexp,d)q=q-link;q=q-link;break;b
15、reak;23 3.5、多项式的代数运算、多项式的代数运算 while(pwhile(p!=NULL)!=NULL)d=d=attach(qattach(q-coef,qcoef,q-exp,dexp,d););p=p-link;p=p-link;while(qwhile(q!=NULL)!=NULL)d=d=attach(qattach(q-coef,qcoef,q-exp,dexp,d););q=q-link;q=q-link;24 3.5、多项式的代数运算、多项式的代数运算删除临时结点删除临时结点 d-link=NULL;d-link=NULL;p=p=c;cc;c=c-=c-link;
16、deletelink;delete p;p;return c;return c;*25 3.6、串、串一、串的概念一、串的概念1.1.串串(String)(String)的定义的定义是由零个或多个字符组成的有限序列。是由零个或多个字符组成的有限序列。记为：记为：s=”as=”a1 1a a2 2aan n”(n0)”(n0)其中，其中，s s是串的名，用双引号括起来的字符序列是是串的名，用双引号括起来的字符序列是串的值。串的值。2.2.串的长度串的长度:串中字符的数目串中字符的数目n n。3.3.空串空串(Null string)(Null string):长度为零的串。长度为零的串。4.4.
17、子串子串:串中任意个连续的字符组成的子序列。串中任意个连续的字符组成的子序列。265.5.主串主串:包含子串的串相应地称为主串。包含子串的串相应地称为主串。6.6.位置位置:字符在序列中的序号。字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主子串在主串中的位置则以子串的第一个字符在主串的位置来表示。串的位置来表示。7.7.串相等串相等:只有当两个串的长度相等，并且各个对应位置的只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。字符都相等，称两串相等。8.8.空格串空格串(空白串空白串)(blank string)(blank string)由一个或多个空格组成的串
18、。要和由一个或多个空格组成的串。要和“空串空串”区别，区别，空格串有长度就是空格的个数。空格串有长度就是空格的个数。3.6、串、串27 二、串与线性表的区别二、串与线性表的区别?1 1、串数据对象约束为、串数据对象约束为字符集字符集。2 2、基本操作的对象不同，线性表以、基本操作的对象不同，线性表以“单个元素单个元素”为操作对象；串以为操作对象；串以“串的整串的整体体”为操作对象，操作的一般都是子串。为操作对象，操作的一般都是子串。3.6、串、串28 三、基本操作：三、基本操作：(1)NULL()(1)NULL()(2)ISNULL()(2)ISNULL()(3)IN(S,a)(3)IN(S,
19、a)(4)LEN(S)(4)LEN(S)(5)CONCAT(S1,S2)(5)CONCAT(S1,S2)(6)SUBSTR(S,m,n)(6)SUBSTR(S,m,n)(7)INDEX(S,S1)(7)INDEX(S,S1)(8)STRCMP(S1,S2)(8)STRCMP(S1,S2)3.6、串、串*29 3.6.2 串的表示串的表示(存储结构存储结构)一、顺序表示一、顺序表示二、链接存储二、链接存储(定长与不定长定长与不定长)30#define MAXSIZE 255#define MAXSIZE 255structstruct seqstringseqstring char char s
20、trMAXSIZEstrMAXSIZE;int int lenlen;seqstringseqstring s;s;3.6.2 串的表示串的表示-顺序表示顺序表示31int int strcmp(s,tstrcmp(s,t)seqstringseqstring s,ts,t;int i=0;int i=0;while(i while(is.lens.len&i&it.strit.stri)return(1);return(1);else else if(if(s.stris.stri t.lent.len)return(1);return(1);elseelse if(if(s.lens.le
21、n data=q-data)-data=q-data)q=q-link;q=q-link;if(qif(q=NULL)=NULL)retrun(firstretrun(first););p=p-link;p=p-link;3.6.2 操作操作子串定位子串定位elseelsefirst=first-link;first=first-link;p=p=first;qfirst;q=S1;=S1;return null;return null;35算法分析算法分析(最好情况下的平均时间复杂度最好情况下的平均时间复杂度)如：如：S S：a b c d e f g h a b c d e f g h j
22、 k lj k l m (m (主串长度为主串长度为n)n)T T：j k lj k l (子串长度为子串长度为m)m)假设从第假设从第i i个位置匹配成功，前个位置匹配成功，前i-1i-1次共比较了次共比较了i-1i-1次。次。第第i i次比较了次比较了m m次次,共比较了共比较了i+m-1i+m-1次。次。i i从从1 1到到n-m+1,n-m+1,共共(n+m)(n-m+1)/2(n+m)(n-m+1)/2平均需比较平均需比较(n+m)/2(n+m)/2最好的情况平均时间复杂度为最好的情况平均时间复杂度为O(n+mO(n+m)3.6.2 操作操作子串定位子串定位36最坏的情况时间复杂度为
23、最坏的情况时间复杂度为如：如：S S：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1T T：0 0 0 0 0 0 0 0 0 0 0 0 1 1若第若第i i趟比较成功，共比较了多少次？趟比较成功，共比较了多少次？前前i-1i-1趟比较每次都比较趟比较每次都比较m m次，第次，第i i趟也比较趟也比较m m次次共共imim次次i i从从1 1到到n-m+1n-m+1共比较了共比较了(n-m+2)(n-m+1)m/2(n-m+2)(n-m+1)m/2平均比较次数平均比较次数(n-m+2)m/2
24、(n-m+2)m/2最坏的情况时间复杂度为最坏的情况时间复杂度为O(nO(n m m)3.6.2 操作操作子串定位子串定位37如果一个结点只存一个字符如果一个结点只存一个字符,空间浪费空间浪费严重严重:如果采用如果采用1616位地址位地址,一个字符点一个字符点8 8位位;实际利用率只有实际利用率只有1/31/33.6.2 串的表示串的表示-链式存储链式存储采用一个结点中存采用一个结点中存m m个字符个字符;383.6.2 串的表示串的表示-链式存储链式存储1 1、一个结点存、一个结点存4 4个字符的链式存储的个字符的链式存储的C C语言表示语言表示 structstruct node node char data4;char data4;node node*link;link;TypedefTypedef node node*STRING;STRING;393.6.2 串的表示串的表示-定长链式存储定长链式存储一、删除操作一、删除操作:1 1、移动、移动2 2、用空白填充，一个结点全空白时删除。、用空白填充，一个结点全空白时删除。二、插入操作二、插入操作:1 1、插入位置存在无用符，用实际元素取、插入位置存在无用符，用实际元素取代无用符。代无用符。2 2、申请新串。、申请新串。3 3、分开块。、分开块。*40
