数据结构与算法教学课件ppt作者王曙燕chapter2线性表.ppt

1、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值，从他顺时针方向的下一个人

2、开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。,第 2 章 线性表,2.1 应用实例,应用实例二：一元多项式运算器 要实现一元多项式运算器，首先要设计表示一元多项式P=p0+p1X+p2X2+pnXn的合适的数据结构，并支持多项式的下列运算。（1）建立多项式。（2）输出多项式。（3）+，两个多项式相加，建立并输出和多项式。（4），两个多项式相减，建立并输出差多项式。（5）*,多项式乘法。（6）(),求多项式的值。（7）derivative(),求多项式导数。,4,第 2 章 线性表,2.2 线性表的概念及运算,定义：线性表(Linear List)是由n(n0

3、)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1，an）。,数据元素之间是一对一的关系，即每个数 据元素最多有一个直接前驱和一个直接后继。,逻辑结构图：,5,第 2 章 线性表,2.2 线性表的概念及运算,特点：,同一性：,线性表由同类数据元素组成，每一个ai必须属于同一数据对象。,有穷性：,线性表由有限个数据元素组成，表长度就是表中数据元素的个数。,有序性：,线性表中相邻数据元素之间存在着序偶关系。,6,第 2 章 线性表,2.3 线性表的顺序存储,定义:,采用顺序存储结构的线性表通常称为顺序表。,假设线性表中每个元素占k个单元，第一个元素

4、的地址为loc(a1)，则第k个元素的地址为：,loc(ai)=loc(a1)+(i-1)k,7,第 2 章 线性表,2.3 线性表的顺序存储,数 据 结 构 与 算 法,8,第 2 章 线性表,2.3 线性表的顺序存储,C语言定义,#define maxsize 线性表可能达到的最大长度typedef struct ElemType elemmaxsize；int length；SeqList；,/表长,9,第 2 章 线性表,2.3 线性表的顺序存储,基本运算,查找操作,插入操作,删除操作,10,数 据 结 构,第 2 章 线性表,2.3 线性表的顺序存储,查找操作,按序号查找GetDat

5、a(L,i)：,要求查找线性表L中第i个数据元素，其结果是L.elemi。,按内容查找Locate（L,x）:,要求查找线性表L中与给定值x相等的数据元素，其结果是：若在表L中找到与x相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。,11,第 2 章 线性表,2.3 线性表的顺序存储,按内容查找Locate（L,x）:,int Locate(SeqList L，ElemType x)int i=1;while(i=L.length),int Opt_Locate(SeqList L，ElemType x)int i;L.elem0=x;/*标识边界*/i=L.le

6、ngth;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,21 28,30,30,42,51,62),#define OK 1#define ER

7、ROR 0 int InsList(SeqList*L,int i,ElemType x)int k;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)个元素删去，

8、使长度为n的线性表(e1，,ei-1，ei，ei+1，en)，变成长度为n-1的线性表(e1，,ei-1，ei+1，en)。,int DelList(SeqList*L,int i,ElemType*e)int k;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，其元素均为非递减 有序排列，编写一个算法

9、，将它们合并成 一个顺序表LC，要求LC也是非递减有序排列。,算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.elemj，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。,void merge(SeqList*LA,SeqList*LB,SeqList*LC)i=1;j=1;k=1;while(ilength,15,第 2 章 线性表,2.3 线性表的顺序

10、存储,优点：,可方便地随机存取表中的任一元素。,缺点：,插入或删除运算不方便，除表尾的位置外，在表的其 它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；,无须为表示结点间的逻辑关系而增加额外的存储空间；,由于顺序表要求占用连续的存储空间，存储分配只能预 先进行静态分配。因此当表长变化较大时，难以确定合 适的存储规模。,返回,16,第 2 章 线性表,2.4 线性表的链式存储,定义:,采用链式存储结构的线性表称为链表。,动态链表,静态链表,单链表,双链表,循环链表,实现角度,链接方式,17,第 2 章 线性表,2.4 线性表的链式存储,单链表,：链表中的每个结点只有一个指针域,结点（

11、Node）：,单链表包括两个域,数据域：,指针域：,用来存储结点的数据值,用来存储数据元素的直接后继的地址（或位置）,头指针：,指向链表头结点的指针。,18,第 2 章 线性表,2.4 线性表的链式存储,单链表,H,19,第 2 章 线性表,2.4 线性表的链式存储,单链表,头结点,带头结点的空单链表,带头结点的单链表,20,数 据 结 构,第 2 章 线性表,2.4 线性表的链式存储,单链表,存储结构描述,typedef struct Node ElemType data；struct Node*next；LNode,*LinkList；,21,第 2 章 线性表,2.4 线性表的链式存储,

12、单链表,的基本运算,建立单链表单链表查找 单链表插入单链表删除求单链表的长度,22,第 2 章 线性表,2.4 线性表的链式存储,建立单链表,头插法建表,s指向新申请的结点s-data=A;,插入第一个结点：,插入某一个结点：,s-next=H-next;,H-next=s;,顺序可以颠倒吗？,23,第 2 章 线性表,2.3 线性表的链式存储,建立单链表,头插法建表,算法,Linklist CreateFromHead()LinkList L;LNode*s;int x;int flag=1;L=(Linklist)malloc(sizeof(LNode)；L-next=NULL;scanf

13、(“%d”,24,第 2 章 线性表,2.4 线性表的链式存储,建立单链表,尾插法建表,s指向新申请的结点s-data=A;,插入第一个结点：,插入某一个结点：,r-next=s;,r=s;,顺序可以颠倒吗？,25,第 2 章 线性表,2.4 线性表的链式存储,建立单链表,尾插法建表,算法,Linklist CreateFromTail()LinkList L;LNode*r,*s;int x;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;r=L;scanf(“%d”,26,第 2 章 线性表,2.4 线性表的链式存储,单链表按序号查找,按序号查找,设带

14、头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从第一个结点（L-next）开始顺着链域扫描。用指针p指向当前扫描到的结点,初值指向第一个结点（p=L-next），用j做记数器，累计当前扫描过的结点数（初值为0），当j=i 时，指针p所指的结点就是要找的第i个结点。,Node*Get(LinkList L,int i)LNode*p；p=L；j=0；while(p-next!=NULL)&(jnext；j+；if（i=j）return p；else return NULL；,27,第 2 章 线性表,2.4 线性表的链式存储,按值查找,指在单链表中查找是否有结点值

15、等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的第一个结点出发，顺着链逐个将结点的值和给定值e作比较。,Node*Locate(LinkList L,ElemType key)LNode*p;p=L-next;while(p!=NULL)if(p-data!=key)p=p-next;else break;return p;,单链表按内容查找,28,第 2 章 线性表,2.4 线性表的链式存储,单链表插入,要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申

16、请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。,s-next=pre-next;,pre-next=s;,顺序可以颠倒吗？,29,算法实现,第 2 章 线性表,2.3 线性表的链式存储,单链表插入,void InsList(LinkList L,int i,ElemType e)LNode*pre,*s;int k=0;pre=L;while(pre!=NULL,30,第 2 章 线性表,2.4 线性表的链式存储,单链表删除,欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使pre指向第

17、i-1个结点，而后删除第i个结点并释放结点空间。,pre-next=pre-next-next;,free(r);,31,算法实现,第 2 章 线性表,2.3 线性表的链式存储,单链表删除,void DelList(LinkList L,int i,ElemType*e)LNode*pre,*r;pre=L;int k=0;while(pre-next!=NULL,32,第 2 章 线性表,2.4 线性表的链式存储,求单链表的长度,可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p-next=NULL）。,算法实现,int

18、ListLength(LinkList L)LNode*p;p=L-next;j=0;while(p!=NULL)p=p-next;j+;return j;,33,第 2 章 线性表,2.3 线性表的链式存储,例2-2 有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：新表 LC利用原表的存储空间。,LinkList MergeLinkList(LinkList LA,LinkList LB)LNode*pa,*pb;LinkList LC;pa=LA-next;pb=LB-next;LC=LA;LC-next=NUL

19、L;r=LC;while(pa,34,数 据 结 构,第 2 章 线性表,2.4线性表的链式存储,循环链表(Circular Linked List)：,是一个首尾相接的链表。,特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。,35,第 2 章 线性表,2.4线性表的链式存储,循环链表(Circular Linked List),例2-3 有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。,先找到两个链表的尾，并分别

20、由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。,p-next=LB-next;,q-next=LA;,free(LB);,36,第 2 章 线性表,2.4线性表的链式存储,循环链表(Circular Linked List),算法实现1,LinkList merge_1(LinkList LA,LinkList LB)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-

21、next=LA;return(LA);,时间复杂度为 O(n),37,第 2 章 线性表,2.4线性表的链式存储,循环链表(Circular Linked List),例2-3 有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。,采用带尾指针的循环链表，执行时间可降低为O(1)。,RA-next=RB-next-next;,RB-next=p;,free(RB-next);,38,第 2 章 线性表,2.4线性表的链式存储,循环链表(Circular Linked List),算法实现2,LinkList merge_2(LinkList

22、 RA,LinkList RB)LNode*p;p=RA-next;RA-next=RB-next-next;free(RB-next);RB-next=p;return(RB);,39,第 2 章 线性表,2.4线性表的链式存储,双向链表(Double Linked List),在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表。,结构定义：,typedef struct DNode ElemType data；struct DNode*prior，*next；DNode,*DoubleList；,定义：,40,第 2 章

23、 线性表,2.4线性表的链式存储,双向链表(Double Linked List),示意图：,41,第 2 章 线性表,2.4线性表的链式存储,双向链表(Double Linked List),前插操作：,s,p,p-prior-next=s;,s-prior=p-prior;,顺序可以颠倒吗？,p-prior=s;,s-next=p;,顺序可以颠倒吗？,顺序可以颠倒吗？,42,第 2 章 线性表,2.3线性表的链式存储,双向链表(Double Linked List)前插操作,算法实现：,int DlinkIns(DoubleList L,int i,ElemType e)DNode*s,*

24、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;return 1;else return 0;,43,第 2 章 线性表,2.4线性表的链式存储,双向链表(Double Linked List),删除操作：,p,p-prior-next=p-next;,p-next-prior=p-prior;,free(p);,44,第 2 章 线性表,2.4 线性表的链式存储,双向链表(Double Linked List)删除操作,算法实现：,int Dlin

25、kDel(DoubleList L,int i,ElemType*e)DNode*p;*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return 1;,返回,第 2 章 线性表,2.5 顺序表和链表的比较,顺序存储的优点：（1）用数组存储数据元素，操作方法简单，容易实现。（2）无须为表示结点间的逻辑关系而增加额外的存储开销。（3）存储密度高。（4）顺序表可按元素位序随机存取结点。,顺序存储的缺点：（1）做插入、删除操作时，须大量地移动数据元素，效率比较低。（2）要占用连续的存储空间，存储分配只能预先进行。如果估计过大，可能

26、导致后部大量空间闲置；如果预先分配过小，又会造成数据溢出。,46,第 2 章 线性表,2.6 一元多项式的表示及相加,一个一元多项式pn(x)可按升幂的形式写成：pn(x)=p0+p1x+p2x2+p3x3+pnxn,可用单链表存储多项式的结点结构：,typedef struct Polynode int coef;int exp;Polynode*next;Polynode,*Polylist;,47,约定：系数为0作结束标志，且指数按从小到大顺序排列。,输入多项式的系数和指数，用尾插法建立一元多项式的链表。,第 2 章 线性表,2.6 一元多项式的表示及相加,Polylist polycr

27、eate()Polynode*head,*rear,*s;int c,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);,