数据结构与算法教学课件ppt作者王曙燕chapter2线性表.ppt
《数据结构与算法教学课件ppt作者王曙燕chapter2线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法教学课件ppt作者王曙燕chapter2线性表.ppt(49页珍藏版)》请在冰点文库上搜索。
1,第2章线性表,2.2线性表的概念及运算,2.3线性表的顺序存储,2.4线性表的链式存储,2.5顺序表和链表的比较,2.1应用实例,2.6实例分析与实现,第2章线性表,2.1应用实例,应用实例一:
约瑟夫环(Josephus)问题约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的。
问题描述为:
编号为1,2,n的n个人按顺时针方向围坐在一张圆桌周围,每人持有一个密码(正整数)。
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的那个人出列,将他的密码作为新的m值,从他顺时针方向的下一个人开始重新从1报数,数到m的那个人又出列;如此下去,直至圆桌周围的人全部出列为止。
第2章线性表,2.1应用实例,应用实例二:
一元多项式运算器要实现一元多项式运算器,首先要设计表示一元多项式P=p0+p1X+p2X2+pnXn的合适的数据结构,并支持多项式的下列运算。
(1)建立多项式。
(2)输出多项式。
(3)+,两个多项式相加,建立并输出和多项式。
(4),两个多项式相减,建立并输出差多项式。
(5)*,多项式乘法。
(6)(),求多项式的值。
(7)derivative(),求多项式导数。
4,第2章线性表,2.2线性表的概念及运算,定义:
线性表(LinearList)是由n(n0)个类型相同的数据元素a1,a2,,an组成的有限序列,记做(a1,a2,,ai-1,ai,ai+1,an)。
数据元素之间是一对一的关系,即每个数据元素最多有一个直接前驱和一个直接后继。
逻辑结构图:
5,第2章线性表,2.2线性表的概念及运算,特点:
同一性:
线性表由同类数据元素组成,每一个ai必须属于同一数据对象。
有穷性:
线性表由有限个数据元素组成,表长度就是表中数据元素的个数。
有序性:
线性表中相邻数据元素之间存在着序偶关系。
6,第2章线性表,2.3线性表的顺序存储,定义:
采用顺序存储结构的线性表通常称为顺序表。
假设线性表中每个元素占k个单元,第一个元素的地址为loc(a1),则第k个元素的地址为:
loc(ai)=loc(a1)+(i-1)k,7,第2章线性表,2.3线性表的顺序存储,数据结构与算法,8,第2章线性表,2.3线性表的顺序存储,C语言定义,#definemaxsize线性表可能达到的最大长度typedefstructElemTypeelemmaxsize;intlength;SeqList;,/表长,9,第2章线性表,2.3线性表的顺序存储,基本运算,查找操作,插入操作,删除操作,10,数据结构,第2章线性表,2.3线性表的顺序存储,查找操作,按序号查找GetData(L,i):
要求查找线性表L中第i个数据元素,其结果是L.elemi。
按内容查找Locate(L,x):
要求查找线性表L中与给定值x相等的数据元素,其结果是:
若在表L中找到与x相等的元素,则返回该元素在表中的序号;若找不到,则返回一个“空序号”,如-1。
11,第2章线性表,2.3线性表的顺序存储,按内容查找Locate(L,x):
intLocate(SeqListL,ElemTypex)inti=1;while(i=L.length),intOpt_Locate(SeqListL,ElemTypex)inti;L.elem0=x;/*标识边界*/i=L.length;while(L.elemi!
=x)i-;return(i);,12,第2章线性表,2.2线性表的顺序存储,插入操作,是指在表的第i(1in+1)个位置,插入一个新元素e,使长度为n的线性表(e1,ei-1,ei,en)变成长度为n+1的线性表(e1,,ei-1,x,ei,en)。
例如:
线性表(4,9,15,28,30,30,42,51,62),需在第4个元素之前插入一个元素“21”。
则需要将第9个位置到第4个位置的元素依次后移一个位置,然后将“21”插入到第4个位置。
(4,9,15,2128,30,30,42,51,62),#defineOK1#defineERROR0intInsList(SeqList*L,inti,ElemTypex)intk;if(iL-length+1)printf(“插入位置i值不合法”);return(ERROR);if(L-length=maxsize-1)printf(“表已满无法插入”);return(ERROR);for(k=L-length;k=i;k-)L-elemk+1=L-elemk;L-elemi=x;L-length+;return(OK);,时间复杂度:
O(n),数据结构与算法,13,第2章线性表,2.3线性表的顺序存储,删除操作,是指将表的第i(1in)个元素删去,使长度为n的线性表(e1,,ei-1,ei,ei+1,en),变成长度为n-1的线性表(e1,,ei-1,ei+1,en)。
intDelList(SeqList*L,inti,ElemType*e)intk;if(iL-length)printf(“删除位置不合法!
”);return(ERROR);*e=L-elemi;for(k=i;klength-1;k+)L-elemk=L-elemk+1;L-length-;return(OK);,时间复杂度:
O(n),14,第2章线性表,2.2线性表的顺序存储,例2-1:
有两个顺序表LA和LB,其元素均为非递减有序排列,编写一个算法,将它们合并成一个顺序表LC,要求LC也是非递减有序排列。
算法思想:
设表LC是一个空表,为使LC也是非递减有序排列,可设两个指针i、j分别指向表LA和LB中的元素,若LA.elemiLB.elemj,则当前先将LB.elemj插入到表LC中,若LA.elemiLB.elemj,当前先将LA.elemi插入到表LC中,如此进行下去,直到其中一个表被扫描完毕,然后再将未扫描完的表中剩余的所有元素放到表LC中。
voidmerge(SeqList*LA,SeqList*LB,SeqList*LC)i=1;j=1;k=1;while(ilength,15,第2章线性表,2.3线性表的顺序存储,优点:
可方便地随机存取表中的任一元素。
缺点:
插入或删除运算不方便,除表尾的位置外,在表的其它位置上进行插入或删除操作都必须移动大量的结点,其效率较低;,无须为表示结点间的逻辑关系而增加额外的存储空间;,由于顺序表要求占用连续的存储空间,存储分配只能预先进行静态分配。
因此当表长变化较大时,难以确定合适的存储规模。
返回,16,第2章线性表,2.4线性表的链式存储,定义:
采用链式存储结构的线性表称为链表。
动态链表,静态链表,单链表,双链表,循环链表,实现角度,链接方式,17,第2章线性表,2.4线性表的链式存储,单链表,:
链表中的每个结点只有一个指针域,结点(Node):
单链表包括两个域,数据域:
指针域:
用来存储结点的数据值,用来存储数据元素的直接后继的地址(或位置),头指针:
指向链表头结点的指针。
18,第2章线性表,2.4线性表的链式存储,单链表,H,19,第2章线性表,2.4线性表的链式存储,单链表,头结点,带头结点的空单链表,带头结点的单链表,20,数据结构,第2章线性表,2.4线性表的链式存储,单链表,存储结构描述,typedefstructNodeElemTypedata;structNode*next;LNode,*LinkList;,21,第2章线性表,2.4线性表的链式存储,单链表,的基本运算,建立单链表单链表查找单链表插入单链表删除求单链表的长度,22,第2章线性表,2.4线性表的链式存储,建立单链表,头插法建表,s指向新申请的结点s-data=A;,插入第一个结点:
插入某一个结点:
s-next=H-next;,H-next=s;,顺序可以颠倒吗?
23,第2章线性表,2.3线性表的链式存储,建立单链表,头插法建表,算法,LinklistCreateFromHead()LinkListL;LNode*s;intx;intflag=1;L=(Linklist)malloc(sizeof(LNode);L-next=NULL;scanf(“%d”,24,第2章线性表,2.4线性表的链式存储,建立单链表,尾插法建表,s指向新申请的结点s-data=A;,插入第一个结点:
插入某一个结点:
r-next=s;,r=s;,顺序可以颠倒吗?
25,第2章线性表,2.4线性表的链式存储,建立单链表,尾插法建表,算法,LinklistCreateFromTail()LinkListL;LNode*r,*s;intx;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;r=L;scanf(“%d”,26,第2章线性表,2.4线性表的链式存储,单链表按序号查找,按序号查找,设带头结点的单链表的长度为n,要查找表中第i个结点,则需要从单链表的头指针L出发,从第一个结点(L-next)开始顺着链域扫描。
用指针p指向当前扫描到的结点,初值指向第一个结点(p=L-next),用j做记数器,累计当前扫描过的结点数(初值为0),当j=i时,指针p所指的结点就是要找的第i个结点。
Node*Get(LinkListL,inti)LNode*p;p=L;j=0;while(p-next!
=NULL)&(jnext;j+;if(i=j)returnp;elsereturnNULL;,27,第2章线性表,2.4线性表的链式存储,按值查找,指在单链表中查找是否有结点值等于e的结点,若有的话,则返回首次找到的其值为e的结点的存储位置,否则返回NULL。
查找过程从单链表的头指针指向的第一个结点出发,顺着链逐个将结点的值和给定值e作比较。
Node*Locate(LinkListL,ElemTypekey)LNode*p;p=L-next;while(p!
=NULL)if(p-data!
=key)p=p-next;elsebreak;returnp;,单链表按内容查找,28,第2章线性表,2.4线性表的链式存储,单链表插入,要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e,需要首先在单链表中找到第i-1个结点并由指针pre指示,然后申请一个新的结点并由指针s指示,其数据域的值为e,并修改第i-1个结点的指针使其指向s,然后使s结点的指针域指向第i个结点。
s-next=pre-next;,pre-next=s;,顺序可以颠倒吗?
29,算法实现,第2章线性表,2.3线性表的链式存储,单链表插入,voidInsList(LinkListL,inti,ElemTypee)LNode*pre,*s;intk=0;pre=L;while(pre!
=NULL,30,第2章线性表,2.4线性表的链式存储,单链表删除,欲在带头结点的单链表L中删除第i个结点,则首先要通过计数方式找到第i-1个结点并使pre指向第i-1个结点,而后删除第i个结点并释放结点空间。
pre-next=pre-next-next;,free(r);,31,算法实现,第2章线性表,2.3线性表的链式存储,单链表删除,voidDelList(LinkListL,inti,ElemType*e)LNode*pre,*r;pre=L;intk=0;while(pre-next!
=NULL,32,第2章线性表,2.4线性表的链式存储,求单链表的长度,可以采用“数”结点的方法来求出单链表的长度,用指针p依次指向各个结点,从第一个元素开始“数”,一直“数”到最后一个结点(p-next=NULL)。
算法实现,intListLength(LinkListL)LNode*p;p=L-next;j=0;while(p!
=NULL)p=p-next;j+;returnj;,33,第2章线性表,2.3线性表的链式存储,例2-2有两个单链表LA和LB,其元素均为非递减有序排列,编写一个算法,将它们合并成一个单链表LC,要求LC也是非递减有序排列。
要求:
新表LC利用原表的存储空间。
LinkListMergeLinkList(LinkListLA,LinkListLB)LNode*pa,*pb;LinkListLC;pa=LA-next;pb=LB-next;LC=LA;LC-next=NULL;r=LC;while(pa,34,数据结构,第2章线性表,2.4线性表的链式存储,循环链表(CircularLinkedList):
是一个首尾相接的链表。
特点:
将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点,就得到了单链形式的循环链表,并称为循环单链表。
在循环单链表中,表中所有结点被链在一个环上。
35,第2章线性表,2.4线性表的链式存储,循环链表(CircularLinkedList),例2-3有两个带头结点的循环单链表LA、LB,编写一个算法,将两个循环单链表合并为一个循环单链表,其头指针为LA。
先找到两个链表的尾,并分别由指针p、q指向它们,然后将第一个链表的尾与第二个表的第一个结点链接起来,并修改第二个表的尾q,使它的链域指向第一个表的头结点。
p-next=LB-next;,q-next=LA;,free(LB);,36,第2章线性表,2.4线性表的链式存储,循环链表(CircularLinkedList),算法实现1,LinkListmerge_1(LinkListLA,LinkListLB)LNode*p,*q;p=LA;q=LB;while(p-next!
=LA)p=p-next;while(q-next!
=LB)q=q-next;p-next=LB-next;free(LB);q-next=LA;return(LA);,时间复杂度为O(n),37,第2章线性表,2.4线性表的链式存储,循环链表(CircularLinkedList),例2-3有两个带头结点的循环单链表LA、LB,编写一个算法,将两个循环单链表合并为一个循环单链表,其头指针为LA。
采用带尾指针的循环链表,执行时间可降低为O
(1)。
RA-next=RB-next-next;,RB-next=p;,free(RB-next);,38,第2章线性表,2.4线性表的链式存储,循环链表(CircularLinkedList),算法实现2,LinkListmerge_2(LinkListRA,LinkListRB)LNode*p;p=RA-next;RA-next=RB-next-next;free(RB-next);RB-next=p;return(RB);,39,第2章线性表,2.4线性表的链式存储,双向链表(DoubleLinkedList),在单链表的每个结点里再增加一个指向其前趋的指针域prior。
这样形成的链表中就有两条方向不同的链,我们称之为双(向)链表。
结构定义:
typedefstructDNodeElemTypedata;structDNode*prior,*next;DNode,*DoubleList;,定义:
40,第2章线性表,2.4线性表的链式存储,双向链表(DoubleLinkedList),示意图:
41,第2章线性表,2.4线性表的链式存储,双向链表(DoubleLinkedList),前插操作:
s,p,p-prior-next=s;,s-prior=p-prior;,顺序可以颠倒吗?
p-prior=s;,s-next=p;,顺序可以颠倒吗?
顺序可以颠倒吗?
42,第2章线性表,2.3线性表的链式存储,双向链表(DoubleLinkedList)前插操作,算法实现:
intDlinkIns(DoubleListL,inti,ElemTypee)DNode*s,*p;s=(DNode*)malloc(sizeof(DNode);if(s)s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return1;elsereturn0;,43,第2章线性表,2.4线性表的链式存储,双向链表(DoubleLinkedList),删除操作:
p,p-prior-next=p-next;,p-next-prior=p-prior;,free(p);,44,第2章线性表,2.4线性表的链式存储,双向链表(DoubleLinkedList)删除操作,算法实现:
intDlinkDel(DoubleListL,inti,ElemType*e)DNode*p;*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return1;,返回,第2章线性表,2.5顺序表和链表的比较,顺序存储的优点:
(1)用数组存储数据元素,操作方法简单,容易实现。
(2)无须为表示结点间的逻辑关系而增加额外的存储开销。
(3)存储密度高。
(4)顺序表可按元素位序随机存取结点。
顺序存储的缺点:
(1)做插入、删除操作时,须大量地移动数据元素,效率比较低。
(2)要占用连续的存储空间,存储分配只能预先进行。
如果估计过大,可能导致后部大量空间闲置;如果预先分配过小,又会造成数据溢出。
46,第2章线性表,2.6一元多项式的表示及相加,一个一元多项式pn(x)可按升幂的形式写成:
pn(x)=p0+p1x+p2x2+p3x3+pnxn,可用单链表存储多项式的结点结构:
typedefstructPolynodeintcoef;intexp;Polynode*next;Polynode,*Polylist;,47,约定:
系数为0作结束标志,且指数按从小到大顺序排列。
输入多项式的系数和指数,用尾插法建立一元多项式的链表。
第2章线性表,2.6一元多项式的表示及相加,Polylistpolycreate()Polynode*head,*rear,*s;intc,e;rear=head=(Polynode*)malloc(sizeof(Polynode);scanf(“%d,%d”,48,第2章线性表,2.6一元多项式的表示及相加,两个多项式相加,运算规则:
两个多项式中所有指数相同的项的对应系数相加,若和不为零,则构成“和多项式”中的一项;所有指数不相同的项均复抄到“和多项式”中。
若p-expexp,则结点p所指的结点应是“和多项式”中的一项,令指针p后移;若p-exp=q-exp,则将两个结点中的系数相加,当和不为零时修改结点p的系数域,释放q结点;若和为零,则和多项式中无此项,从A中删去p结点,同时释放p和q结点;若p-expq-exp,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。
49,第2章线性表,2.6一元多项式的表示及相加,两个多项式相加,A(x)=7+3x+9x8+5x17,B(x)=8x+22x7-9x8,p,q,tail,tail,p,11,tail,p,temp,q,free(temp);,tail,q,temp,p,free(temp);,temp,q=NULL;,free(temp);,