数据结构课件-版-ds线性表

第二章线性表 12章线性表（Liner线性表的抽象数据线性表的实栈串数组广义表（Generalized

第二章线性表 2

第二章线性 3

第二章线性表 4线性表的抽象数据[定义]线性表是由n(n≥0)(a1,a2,a3,……ai-1,ai,ai+1,…… 其中：①n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。②ai为线性表中的元素，类型定义为③a1为表中第1个元素，无前驱元素；an为表中最后一个④线性表是有限的，也是有序的

第二章线性表 5线性表LISTDD={ai|ai∈Elementset,i=1,2,…,n,n≥0R={HH={<ai-1,ai>|ai-1,ai∈D,i=2,…,n

第二章线性表 6操作：设L的型为LIST线性表实例，x的型为elementtype的元素实例p为位置变量。所有操作描述为①Insert(x,p,②Locate(x,③Retrive(p,④Delete(p,⑤Previous(p,L),Next(p,⑥Makenull(⑦First(⑧

第二章线性表 7例：设计函数Deleval（LIST&L,elementtype 为删除L中所有值为d的元素。voidDeleval(LIST&L,elementtyped{positionpp=First(L)while(p!=End(L){if(same(Retrieve(p,L),d))Delete(p,L);p=Next(p,L)}}

第二章线性表 8 结构的三种方式①连续 空间（数组 →静②非连 空间——指针（链表 →动 游标（连 空间+动态管理思想）→静态链

第二章线性表 9顺序是指用一组地址连续 单元依 线性表的数据元素特元间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用是一种随机结构，也就是可以随机存取表中的任意元素，其位 第二章线性表 第二章线性表 2— 第个元素2第i121i≤ maxlength-

池容

图2-1

第二章线性表 #definemaxlength LISTintlast;LISTtypedefint

L.elements[p]//L的第p个元素L.lastL的长度，最后元素的位置

第二章线性表 ①voidInsert(elementtypex,positionp,LIST{positionqifL.lastmaxlength1)error(“)；elseif((p>L.last+1)||(p<1)elsefor(q=L.last;q>=p;q--L.elements[q+1]=L.last=L.last+1;L.elements[p]=x;}

L.elements[q]}//时间复杂性

第二章线性表 ②positionLocate(elementtypex,LISTL positionqfor(q=1;q<=L.last;q++)if(L.elements[q]==x)return(q);return(L.last+1

第二章线性表 ③elementtypeRetrieve(positionp,LISTL{if(p>L.lastreturn(L.elements[p])

第二章线性表 ④voidDelete(positionp,LIST{positionqif((p>L.last)||(p<1){L.last=L.last–for(q=p;q<=L.last;q++)L.elements[q]=L.elements[q+1];}

第二章线性表 ⑤positionPrevious(positionp,LISTL{if((p<=1)||(p>L.last))errorreturn(p–1positionpositionNext(positionp,LISTL{if((p<1)||(p>=L.last))errorreturn(p+1

第二章线性表 ⑥ Makenull(LIST&L{L.last=0return(L.last+1⑦positionFirst(LISTL{return(1⑧positionEnd(LISTL{return(L.last+1}//

第二章线性表 单链表：式结构，简称单向链表或单向线性链表。结构特点逻辑次序和物理次序不一定相 间的逻辑关系用指针表示需要额外空 间的关系非随 结 第二章线性表 ∧

pheader

positionp,q;qq 第二章线性表 celltype{elementtypeelement;celltype*next;结点

typedefcelltype位置typedefcelltype

∧∧header positionp,记法

a2:(*p).elementq:(*p).next

a2:p→element;q:p→next; 第二章线性表 插入元素q=newcelltype;q→element=x;q→next=p→next;p→next=q;

x表头插入元x或temp=p→nextp→next=newcelltype;p→next→element=x;p→next→next=temp;讨论表头结点的作用

x x中间插入元∧∧∧x ∧x 入元 第二章线性表 ppqq=p→next;p→next=q→next;deleteq;q=p→nextp→next=p→next→next;deleteq;讨论结点ai

删除第一个元qqpp∧pq∧删除表尾元 第二章线性表 操作①positionEnd(LIST positionq;q=L;while(q→next!=NULL)q=q→next;return(q)∧L

第二章线性表 ②voidInsert(elementtypex,position{positionqq=newcelltype;q→element=x;q→next=p→next;p→next=q;完整的插入

第二章线性表

2—voidInsert(LIST&L,positionp,int{LISTq,s;while(s-{s=s-}} 第二章线性表 2—操作：③ Locate(elementtypex,LISTL{positionpp=Lwhile(p→next!=Nullif(p→next→element==x)returnp;p=p→next;returnp; L

…∧

第二章线性表 ④elementtypeRetrieve(position{return(p→next→element⑤ Delete(position positionqif(p→next!=NULL q=p→nextp→next=q→next;deleteq;} 第二章线性表 q

∧ positionPrevious(position∧{positionqif(p==L→nexterror(“不 {q=Lwhile(q→next!=p)q=q→next;returnq

第二章线性表 操作positionNextposition{positionqif(p→next==NULL{q=returnq}}//时间复杂性⑦positionMakenull(LIST&L{L=newcelltype;L→next=NULL;returnL;}//时间复杂性

第二章线性表 操作positionFirstLISTL{return}//时间复杂性 Travel(LISTL{positionpp=L→nextwhile(p!={cout<<p→element;p=p→next;}}

第二章线性表 静态链表与动态链表的比较

第二章线性表 静态链表把线性表的元素存放在数组的单元中（不一定按逻辑顺序 第二章线性表 结点形

L7d67d65c0a8e4b213M3结点信 下一结点位

9个池 第二章线性表 d65cd65c0a8e4b21typedefstruct7Lelementtypeelement 7L next spacestr;//结点类3spacestrSPACEmaxsize 3typedefint 3 av;//游标变量，标识线性67 池 第二章线性表 d65cd65c0a8e4b21L=(a,b,c L= 7M=(d,e M= 72L2空闲表3available= 3元素 3 “型” elementtype(基本、复合 下一元素位置SPACEi “

池 第二章线性表 1 1 2 9

432{432int5//依 池中结56for(j=0;j<maxsize-1;j++6778//最后一个接点指针域为89SPACE[j].next=-9//标识线性 第二章线性表2—3737M

0d6152c30d6152c304a586e74//q=newspacestr{cursor SPACE[*av].next=SPACE[q].next;//av=12}/*从池中删除

1

//delete SPACE[q].next=SPACE[*av].next;SPACE[*av].next=q;}/*放回池中

第二章线性表 ④voidInsert(elementtypex,positionp,spacestr&SPACE{positionqq=Malloc_SL();SPACE[q].element=x;SPACE[q].next=SPACE[p].next;SPACE[p].next=q;}⑤ Delete(positionp,spacestr&SPACE positionqif(SPACE[p].next!=-1 q=SPACE[p].nextSPACE[p].next=SPACE[q].next;Free_SL(q);

q=newcelltypeq→element=x;q→next=p→next;p→next=q;q=p→next;p→next=q→next;deleteq;}}思考题：利用静态链表实现集合运算(A-B)U(B-A):从键盘输入集合元素

第二章线性表 L->next-{p->next=L-L-q=q-}

方法二线性表由q来表{}

第二章线性表

2—一个域，用一指向该结点的前驱结点。表的这 结构称为双向链表 /*结点类型structdcelltypeelementtypeelement优点实现双向查找（单链表不易做到表中的位置i可以用指示含有第i个结的指针表示

dcelltype*next,*previous}/*表和位置的类缺点：空间开销大

dcelltype*DLIST;dcelltype*position 第二章线性表 结点形previouselementap∧an∧前驱结点指结点信后继结点指 第二章线性表 2—操作voidInsert(elementtypex,positionaappositionqq=newdcelltype;q→element=x;p→previous→next=q;q→previous=p→previous;q→next=p;p→previous=q}

删除位置p的元素voidDelete(position{if(p->previous!=NULL)ifp→next→previous=p→previous;deletep;}单单向线性链

第二章线性表 双向线性链对线性链表的改进向操问题；改进后的链双向线性链双向循环链置元素开始，表中的每双向循环链单向循环链单向环形链表：在(不带表头结点)的单向链表中，使末尾结点的指单向循环链∧左端结 右端结 空∧…结构:与单向链表相同(略 第二章线性表 操作：①在表左端插入结点Insert(xFirst(R),RLinsert(x,R) Linsert(elementtypex LIST&Rx celltype *p xp=newcelltypep→element=xif (R==NULL p→next=p R=p {p→next{p→next=R→nextR→next=p}}x…Rp②在表右端插入结点Insert(x,END(R),R);→Rinsert(x,R) Rinsert(elementtypex, LIST&R) Linsert(x,R R=R→next 第二章线性表 操作：③从表左端删除结点Delete(FirstR),R);→Ldelete(R) Ldelete(LIST&R celltype *p if …error “空表…else p=R→nextR→next=p→next;if p==R)x xdelete p} 第二章线性表 11……Ra 第二章线性表 R R算法如下 voidRevers(LIST&R{positionp,q,s;q=R;p=R→next;R=R→next

while(p->next!=R{s=q;q=pp=p→next;q→next=s;}} 第二章线性表

coeflinkcoeflink系 指 下一项地结点类structpolynode coef exppolylink*linktypedefpolynode*polypointer 第二章线性表 例如 p(x)=3x14+2x8+ 82310∧82310∧算法Attch(c,e,d)建立一个新结点，其系数coefc，指数exp=e；并把它链到d所指结点之后，返回该结点指针。polypointerAttch(intc,inte,polypointerd xx=new polynode;x→coef=c;x→exp=e;d→link=x;returnx;}

算法padd实现两个多项a，b相加c(x)=a(x)+

第二章线性表 polypointerPadd(polypointera,polypointerb{polypointerp,q,d,c;intx;p=a→link; q=b→link;c=newpolynode d=cwhile((p!=NULL)&&(q!=NULL))switch(compare(p→exp,q→exp)){case‘=‘x=p→coef+q→coefif(x d=attch(x,p→exp,d)p=p→link;q=q→link;break;cased=Attch(p→coef,p→exp,d}

第二章线性表p=p→linkbreak;case‘<‘:d=Attch(q→coef,q→exp,d);q=q→link;break

2—while(p!=NULL d=Attch(p→coef,p→exp,d);p=p→link;}while(q!=NULL d=Attch(q→coef,q→exp,d)q=q→link}d→link=NULL;p=c;c=c→link;deletep;returnc

第二章线性表 栈栈(LastInFirstOut线性表。

an-an-栈栈示意栈栈的基本操①MakeNull(S②Top(S③Pop(S④Push(x,S⑤Empty(S

第二章线性表 2—voidLineEdit({STACKcharcMakeNull(S);c=getchar();while(c!=‘\n’){

if(c==‘#’Pop(Selseif(c==‘@’MakeNull(S);Push(c,S);c=getchar();}逆序输出栈中所有元素｝ 第二章线性表 类型定义enumBoolen{TRUE, structinttop; STACKS;栈空：S.top0栈满：S.topmaxlength1

--210顺序栈示意

第二章线性表 ①voidMakeNull( &S{S.top=0;②BooleanEmpty( S{if(S.top<1return}

returnFALSE③elementtypeTop( S ifEmpty(Sreturn}

return(S.elements[S.top]

第二章线性表 ④ Pop( &S{if(Empty(S)error栈空S.top=S.top–1}⑤voidPush( x, &S{if(S.top==maxlength-1error栈满{S.top=S.top+1;S.elements[S.top]=x;}}

第二章线性表 的,要考虑链表的哪一端实现元素的

∧structnode∧Elementtype node*typedefnode*

第二章线性表 ①voidMakeNull(STACK{S=newS-}②voidPush(Elementtypex,STACK{STACKstk;}

第二章线性表 ③voidPop(STACK{STACKstk;if(S->next{stk=S-deletestk;}}{if(S-return} 第二章线性表 ⑤booleanEmpty(STACK{if(S->next)return} STACK[maxlength

Maxlength-

2、栈的简单应用

第二章线性表 例1算术表达式中括号作用域 intCorrect(charext[],intn)/*数组ext用 表达式{STACKintj=1;while(表达式没有结束时{ifexp[j]是左括号*左括号*/Push(ext[j],S)ifext[j]是右括号*右括号{x=Top(S);/*取栈首元素比较*/if(x与ext[j]匹配)Pop(S);elsereturn}j+}if(!Empty(S))return}elsereturn

例2表达式求表达式

第二章线性表 2—后缀表达式（逆波兰式(a+b)*(a－

(a+b)*(a－ 后缀表达式的特点 后缀表达式中不需要括弧定义计算顺序，而由（操作符）的位置来确定运算顺序

第二章线性表 对中缀表达式从左至右依次扫描，由于操作数的顺序保持不变，当遇到“（”进栈，当遇到“）栈输出直到“）”为止由后缀表达式计 第二章线性 2—例3、使用游标形式使得三栈共设用一个类型为STATICLIST的一维数组A[m]空间建立三个栈.其中前三个单元的next存放三个栈顶的指四个单元起共写一算法

如果输入数据为:100,30,68,90,120后结果应如下: 5670043056700430 第二章线性表 structstruct{intdata;inttypedefstructnodevoidShare(Node{inti,top;{}//初始{{}else{}{}}3、栈与递归问

第二章线性表 一、递归采用递归方法来解决问题，必须符合以下三个条件1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减2、可以应用这个转化过程使问题得到解决3、必定要有一个明确的结束递归的条件二、递归例：使用递归的方法求n!当n>1时，求n!的问题可以转化为n*(n-1比如

n*(n-1)!(n-1)*(n-2)!(n-2)*(n-3)!(n-3)*(n-4)!(n-5）! 5-5=0，得到值1，结束递归

第二章线性表

2—说明调返回↑t=5*fac(5-returnt=4*fac(4-return第二章线性表第二章线性表2—t=3*fac(3-returnt=2*fac(2-returnreturn 第二章线性表 2— intintmymax(intfrom,int{intmid,t1,t2;returna[from];{return(t1>t2)?t1:t2;}}intintmax(intn,int*{ifreturnarr[n-1];returnmax(n-}

第二章线性表 intfindmax(ints[],intl,int{int return returns[l]>s[r]?s[l]:s[r];x=findmax(s,l,m);returnx>y?x:} 第二章线性表 2—和栈相反，队列是一种先进先出（First InFirstOut，简称FIFO结构）的线性表。

队队队

队列示意

rear操作：MakeNull(Q)、Front(Q)、EnQueue(x,Q)、DeQueue(Q)、 第二章线性表 structcelltype{elementtypeelement；celltype*next；}

队列的“型”：structQueuecelltype*frontcelltype*rear…∧…∧队列的指针实现示意

第二章线性表 操作①voidMakeNull(Queue&Q{Q.front=newcelltype;Q.front→next=Null;Q.rear=Q.front;}②BooleanEmpty(QueueQ{if(Q.front==Q.rear)returnTrue;returnFalse}

③elementtypeFront(QueueQ{}

第二章线性表 ④voidEnQueue(elementtypex,Queue&Q Q.rear→next=newcelltypeQ.rear=Q.rear→next;Q.rear→element=x;Q.rear→next=NULL;}⑤ DeQueue( &Q{celltype*temp;if(Empty(Q)error空队列else{temp=Q.front→nextQ.front→next=temp→next;deletetemp;if(Q.front→next==NULL)Q.rear=Q.front; } 第二章线性表 2—队列的structQueueelementtypeelement[maxlength] front rearQ右图：队列Q状态

下图：队列Q状态Q

随着不断有元素出队和进个元素无法进队实际上， 第二章线性表 第二种方法是采用循环队插入元素Q.rear=(Q.rear+1）%删除元素Q.front=(Q.front+1）%

maxlength-0

(Q.rear+1）%maxlength==(Q.rear+1)%maxlength==

队列

第二章线性表

45

J445032

32J4J4450321 第二章线性表 2—操作intaddone(inti{return((i+1）%maxlength)}①voidMakeNull(Queue{Q.front=0Q.rear=maxlength–

②booleanEmpty(QueueQ{Q.frontreturnTRUE;returnFALSE}}

第二章线性表 操作：③elementtypeFront(QueueQ if(Empty(Q)returnNULLreturn(Q.elements[Q.front]}④voidEnQueue(Elementtypex,Queue&Q{ifaddoneaddone(Q.rearQ.fronterror(“队列满”);elseQ.rear=addone(Q.rear);Q.elements[Q.rear]=x;}}⑤voidDeQueue Queue&Q) if(Empty(Q)error(“Q.front=addone(Q.front)}

第二章线性表 (ab)i的系数三角形(Pascal’striangle) 11

i2345 第二章线性 2—

从前一行的数据可以计算下一行的数 第二章线性 s=0t=1t=2 t=1t=0 s+t

t=3t=1 t=0t=1 第二章线性表 利用队列打印二项展开式系数的程#include<stdio.h>#include"queue.h"{Queueq;队列初始化inti,j,s=0,t,u;q.enQueue(1);q.enQueuefori1;in;i++逐行计{cout<<endl;forj1;ji+2j下一{intt=q.deQueueu=s+t;s=t;if(j!=i+2)cout<<s<<'}} 第二章线性 2—作业：分时系统的模拟 ，具体情况如表1所示起 031221表1用户请求统计表 第二章线性表 队 队尾图2用户对

这种调度原则可归纳为以下三点1、当一用户请求CPU时间，它就进入请求使用CPU的队列 第二章线性表 005利用“先进先出”调度原则设计一个模拟简单的分时系统的算法 等 延图３用户时间分配情

第二章线性表 串(String串的基本形式可表示成：Sa1a2a3······an其中：charai0inn0n0为空串n串的长C2操作：stringMakeNull(BooleanIsNull(S);voidIn(S,a); Len(S)voidConcat(S1,S2)

str1[10]*str2stringSubstr(S,m,n);BooleanIndex(S,S1)

第二章线性 例1、将串TSiINSERT(STivoidInsert(STRING&S,STRINGT,inti{STRINGt1,t2if((i0||iLen(Serror‘指定位置不对;if(IsNull(S))S=T;if(IsNull(T) t1=Substr(S,1,i)t2=Substr(S,i+1,Len(S));S=Concat(t1,Concat(T,t2));}}

第二章线性表 例2、从串S中将子串T删除Delete(S,T Delete(STRING&S,STRINGT STRINGt1 t2int m,nm=Index(S,T);if (0)error‘串S中不包含子串T’else n=Len(T)t1=Substr(S,1,m-1)t2=Substr(S,m+n,Len(S));S=Concat(t1,t2);}} 第二章线性表 2—2.5.2串的实现1、串的顺 str[10

串的顺操作2、串的链 －－－定长结 structnode{chardata;node*link}typedefnodeSTRING1str1

第二章线性表structnode{chardata[4];node*link;}typedefnode*STRING2;STRING2str2;

2— ‘C’ ‘C’假设地址量（link）占用2

第二章线性表 intIndex(STRING1S,S1{

structnode*p,*q,*i;intt;if((S1!=NULL)&&(S!=NULL) t=1;i=S;q=S1doif(p→data==q→data q=q→linkif(q==NULL)return(t)若S1是S的子串则返

p=p→linkS1首字符在S中的位置

t=t+1;i=i→link否则，返回

p=i;q=S1}}while(p!=NULL)}return0} 第二章线性表 作业：Substr(S,m,n):求串S从第m个字符开始长度为n个字符的子串插入和删除时“无用”字符的处理主 模式串 ，指针I要回朔45次

第二章线性表

第二章线性表 第二章线性表 每一趟匹配过程中出现字符比较不等时，不需要回朔I指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比假设主串为‘s1s2sn，模式串为‘p1p2...pm’，当sipjipk，显然k<j,如下图：…si-jsi-j+1si-j+2…si-ksi-k+1si-k+2…si-2si-

p2…..Pk-2pk-说明：pj-k+1pj-k+2…pj-1=p1p2…pk-2pk-Substr(P,1k-1)=Substr(P,j-k+1,k-1) 第二章线性表 2—next函数的定 当jnext[j |1kjp

''

1 1

k jk

j若模式串P为’abaabc’，由定义可得next函数j123456模式abaabc011223 第二章线性表 2—主 S=‘acabaabaabcacaab模式串P=’abaab 主 acabaabaabcacaab a↑j=2 主 acabaabaabcacaab ↑j=1↓i=3 主

cabaabaabcacaab abaab↑j=1 ↑j=6↓i=8→ 主

acabaabaabcac(ab)aab

ab↑↑

第二章线性表 j123456789模式aaabcaaba j123456789模式abcabcacb0 4

第二章线性 已知next[1]0，假设next[j]ktjtk，则有next[j+1]=k+1=next[j]+1；若next[j]ktjtk，则需往前回溯，检查tjt?。这实际。k’=next[k]且tjtk’，则next[j]=next[k]+1，若tjtk’则继续往前回溯，直到存在k’’使tj=tk’’或k’’=0j12345678模式babbabab 第二章线性表 121234501234

p1与s4,p1与s4+1即与s5比较。有多余的比较操作，可以改进为:若next[j]=k而pj=pk则next[j]1212340000

第二章线性表 下面给出求next函数的伪voidget_next(SStringT,int{inti=1;next[1]=0;int j=0;whilei<T[0])//T[0]中存放数组长{if({++i; next[i]=j;}elsej=next[j];}

第二章线性表 算 char*t,int{//求串s的第pos个字符开始找首次与t串相等的inti=pos;int j=1;{if( ++i; elsej=next[j];//下一个匹配位置if(j>t[0])returnit[0];//成功返回位置elsereturn1;}

第二章线性表 数组()数组是由下标（index）和值（value）组成的序（index，value）的集合也可以定义为是由相同类型的数据元素组成有限序列 所有数组都是一个一维向量数组1：(a1,a2,a3, ai, an)数组2：(a11, a1n,a21, a2n,, ij, am1, amn)1≤i≤m,1≤j≤n数组3:(a111, a11n,a121, a12n, aijk, amn1, amnp)1≤i≤m,1≤j≤n,1≤k≤p

第二章线性表 n维数组中含有∏bi个数据元素,每个元素都受着 n个关系的约束。在每个关系中，元素aj1j2···jn（0≤ji ≤bi-2）都有一个直接后继元素。n维数组同样如此。操作：Create(）；建立一个空数组Retrieve(arra