《数据结构-第二章--线性表课件.ppt》由会员分享，可在线阅读，更多相关《数据结构-第二章--线性表课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示和相加2.1 线性表的类型定义一、定义：线性表是由n个具有相同特性的数据元素 a1,a2,an组成的有限序列。记为(a1,a2,an)。例 英文字母表（A,B,C,.Z)是一个线性表例数据元素概念：前驱、后继 线性表长度；空表 数据元素在线性表中的位序；2.1 线性表的类型定义二、特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据
2、元素均只有一个后继三、抽象数据类型线性表的定义ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 n为表长，n=0为空表 数据关系：R=|ai,ai+1D，1in-1 i为位序。2.1线性表的类型定义三、抽象数据类型线性表的定义Listempty(L)初始条件：线性表L已存在。操作结果：若L为空，则返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare()初始条件
3、：线性表L已存在。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的元素不存在，则返回值为0。2.1线性表的类型定义三、抽象数据类型线性表的定义2.1线性表的类型定义PriorElem(L,cur-e,&pre-e)初始条件：线性表L已存在。操作结果：若cur-e是L的数据元素，且不是第一个，则用pre-e返回它的前驱，否则操作失败，pre-e无定义。NextElem(L,cur-e,&next-e)初始条件：线性表L已存在。操作结果：若cur-e是L的数据元素，且不是最后一个，则用next-e返回它的后继，否则操作失败，next-e无定义。ListInsert(
4、&L,i,e)初始条件：线性表L已存在,1i ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)初始条件：线性表L已存在,1i ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L 的长度减1。三、抽象数据类型线性表的定义2.1线性表的类型定义ADT List三、抽象数据类型线性表的定义void union(List&La,List Lb)/将所有在线性表Lb中但不在La中的数据元素插入到La中。La.len=ListLength(La);/求线性表的长度 Lb.len=ListLe
5、ngth(Lb);for(i=1;i=Lb.len;i+)GetElem(Lb,i,&e);/取Lb中的第i个数据元素给e if(!LocateElem(La,e,equal)ListInsert(La,+La.len,e);该算法的时间复杂度为：O(ListLength(La)ListLength(Lb)LocateElem时间复杂度为o(n)2.1线性表的类型定义2.2 线性表的顺序表示和实现一、概念二、线性表顺序存储结构的表示三、顺序表基本操作的算法描述（实现）二、线性表顺序存储结构的表示2.2线性表的顺序表示和实现用动态分配的一维数组描述线性表的顺序存储结构/线性表的动态分配顺序存储结
6、构#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define INCREMENT 10/线性表存储空间的分配增量typedef struct ElemType*elem;/存储空间的基址 int length;/线性表当前长度 int listsize;/当前分配的存储容量 SqList;三、顺序表基本操作的算法描述2.2线性表的顺序表示和实现2、求表长 L.length取第i个元素 L.elemi-1求第i个元素的前驱 L.elemi-2求第i个元素的后继 L.elemi时间复杂度：O(1)三、顺序表基本操作的算法描述2.2线性表的顺序表示和实现3、查找函
7、数 Int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)i=1;/i的初值为第1元素的位序 p=L.elem;/p的初值为第1元素的存储位置 while(i=L.length&!(*compare)(*p+,e)i+;if(i=L.length)return i;else return 0;*p+！=e两个变化：ai-1和ai的位置关系发生变化线性表的长度增1a1a2ai-1aiana1 a2ai-1 aiane2.2线性表的顺序表示和实现三、顺序表基本操作的算法描述4、插入 问题：线性表的逻辑结构发
8、生了什么变化？void insert(elemtype s,int i,elemtype e,int n)int j;for(j=n;j=i;j-)sj=sj-1;sj=e;n+;Status insertlist(sqlist*L,int i,elemtype e)if(i L.length+1)return ERROR;if(L.length=L.listsize)newbase=(elemtype*)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(elemtype);if(!newbase)exit(OVERFLOW);L.elem=newbas
9、e;L.listsize+=INCREMENT;q=&(L.elemi-1);/q为插入位置 for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置之后元素右移*q=e;+L.length;return OK;a0 a1 e a2 a3 a4 a5 a6插入ea0 a1 a2 a3 a4 a5 a6时间复杂度：O(n)r eal loc(*p,siz e)2.2线性表的顺序表示和实现三、顺序表基本操作的算法描述2.2线性表的顺序表示和实现三、顺序表基本操作的算法描述5、删除 问题：线性表的逻辑结构发生了什么变化？两个变化：ai-1和ai+1的位置关系发
10、生变化线性表的长度减1a1a2ai-1aiai+1ana1a2ai-1ai+1anvoid delete(elemtype s,int i,int n)int j;elemtype e;e=si-1;for(j=i;jn;j+)sj-1=sj;n-;Status listdelete(sqlist*l,int i)if(iL.length)return ERROR;p=&(L.elemi-1);/p为被删除元素的位置 e=*p;q=L.elem+L.length-1;/表尾元素的位置 p=p+1;for(p;p=q;+p)/被删除元素之后的*(p-1)=*p;元素左移-L.length;ret
11、urn OK;删除a2给e时间复杂度：O(n)a0 a1 a2 a3 a4 a5 a6a0 a1 a3 a4 a5 a62.2线性表的顺序表示和实现三、顺序表基本操作的算法描述2.2线性表的顺序表示和实现三、顺序表基本操作的算法描述 void MergeList_sq(SqList La,Sqlist Lb,Sqlist&Lc)pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem)e
12、xit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+La.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;时间复杂度：O(length(La)+Length(Lb)例：两个有序顺序表的合并一、概 念1、链式存储结构方式 用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续。2.3线性表的链式表示和实现
13、 结点(Node)数据域：数据元素信息。指针域：存储直接后继的存储位置。(单链表)一、概 念2、首元结点、头结点、头指针2.3线性表的链式表示和实现首元结点：链表中第一个数据元素结点；例(a1,a2,an)头结点：链表中在首元结点之前附设一个结点，称为头结点；头指针：指向链表中第一个结点(头结点或首元结点)的指针。唯一确定一个单链表。首元结点注：头结点的指针域存放首元结点的地址；数据域可以不存储任何信息，也可存储线性表的长度等类的附加信息；作用：对链表进行操作时，可以在链表空和非空时，对头指针进行统一处理；区分带头结点的链表和不带头结点链表的差别。LL头指针NULL：链表的最后一个结点的指针，
14、意为“空”。头结点作用非空表：无头结点：有头结点：LNULLLNULL空表：无头结点：有头结点：L=NULLL-next=NULL;LNULL一、概 念2.3线性表的链式表示和实现2.3线性表的链式表示和实现二、单链表的描述Typedef struct Lnode elemtype data;/结点数据 struct Lnode*next;/指向后继结点的指针 Lnode,*LinkList;用“结构指针“描述单链表可用Lnode定义单链表中的结点；可用LinkList定义头指针；三、单链表基本操作的算法描述2.3线性表的链式表示和实现1、GetElem时间复杂度 T(n)=O(n)3、删除三
15、、单链表基本操作的算法描述2.3线性表的链式表示和实现删除过程 找到第(i-1)个数据元素位置；执行删除操作(修改指针)；释放删除结点所指的内存区:free(q)pa b c删除bq注：当指针变量p指向单链表中最后一个数据元素结点时，pNULL,但p-next=NULL时间复杂度 T(n)=O(n)4、CreateList三、单链表基本操作的算法描述2.3线性表的链式表示和实现 建立链表，首先生成表头结点，形成一个空链表，然后依次建立各数据元素结点，并逐个插入链表。逆向建立单链表headLLppLP-next=L-next;L-next=p;时间复杂度 T(n)=O(n)5、两个有序链表的归并
16、三、单链表基本操作的算法描述2.3线性表的链式表示和实现 已知：la，lb为单链表且元素按值非递减排列。合并后得到新单链表lc也按值非递减排列。Void mergelist(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)/while(pa!=NULL&pb!=NULL)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(lb);时间复杂度：O
17、(lengh(la)+lengh(lb)循环链表的操作和单链表基本一致。所不同是判断表尾的条件不同。若p指向表尾：循环链表:p-next=head 单链表:p-next=NULL 空表：L-next=L;1.链式存储结构的另一种形式。特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任一结点出发均可找到表中其它结点。2.3线性表的链式表示和实现四、循环链表2.带尾指针的单循环链表 带尾指针的单循环链表，可以很方便地搜索到表头和表尾结点。2.3线性表的链式表示和实现四、循环链表 优点：简化某些操作。例如：将两个线性表归并 O(1)一个链表的每一个结点含有两个指针域：一个指
18、针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。双向链表有两个方向的指针，这样能快速确定一个结点的直接前驱，对链表的访问就非常方便。解决了单链表中寻找结点的前驱结点必需从表头指针开始的不足。2.3线性表的链式表示和实现五、双向链表prior Data next结构如图：1双向链表的存储结构 typedef struct DuLNode Elemtype data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*Dulinklist;2.3线性表的链式表示和实现五、双向链表在双向链表中，若p是指向表中任一结点的指针，则有：2
19、.双向链表的c语言描述p-prior-next=p-next-prior=p；(1)在双向链表的操作中，有些操作与单链表相同，如：Listlength、GetElem、LocateElem；只涉及一个方向指针；删除 插入2.3线性表的链式表示和实现五、双向链表3、双向链表中基本操作的实现(2)插入、删除等操作，须同时修改两个方向的指针。注：双向链表中插入、删除时，须首先找到第i个结点位置；插入 xS11、sprior=pprior2、ppriornext=s33、snext=p44、pprior=s b ap2.3线性表的链式表示和实现五、双向链表2 删除 b ap c11、ppriornex
20、t=pnext22、pnextprior=pprior2.3线性表的链式表示和实现五、双向链表2.4 一元多项式的表示和相加一元多项式：Pn(x)=p0+p1x+p2x2+pnxn在计算机中，可用一个线性表示:P=(p0,p1,p2,pn)每一项的指数i隐含在其系数pi(零或非零)的序号里。但若多项式的次数很高，且变化大，如：S(x)=1+3x1000+2x2000，浪费内存。一般情况下，一元n次多项式可写成：Pn(x)=p1xe1+p2xe2+pmxem其中:pi为指数为ei项的非零系数；0e1e2 em=n 线性表表示为：(p1,e1),(p2,e2),(pm,em)如：一个一元多项式：P
21、999(x)=7x3-2x12-8x999在计算机中，可以用一个线性表表示：(7,3),(-2,12),(-8,999)2.4 一元多项式的表示和相加实现一元多项式，可采用链式存储结构：Typedef struct Lnode float coef;/系数 int expn;/指数 struct Lnode*next;Lnode，polynomial;coef expnext顺序存储 链式存储 Typedef struct float coef;/系数 int expn;/指数 ElemType;2.4 一元多项式的表示和相加-1A7 0 3 1 9 8 5 17-1B8 1 22 7-9 8
22、-1C7 0 11 1 22 7 5 17 一元多项式相加2.4 一元多项式的表示和相加设p,q分别指向A,B 中某一结点，p,q初值是第一结点比较p-exp 与q-expp-exp exp:p 结点是和多项式中的一项 p后移,q不动p-exp q-exp:q 结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp=q-exp:系数相加0：从A 表中删去p,释放p,q，p,q后移0：修改p系数域,释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B 中剩余部分链接到A 上即可运算规则2.4 一元多项式的表示和相加q-1pa7 0 3 1 9 8 5 17
23、-1pb8 1 22 7-9 8 ppreq-1pa7 0 3 1 9 8 5 17-1pb8 1 22 7-9 8 ppreq-1pa7 0 11 1 9 8 5 17-1pb8 1 22 7-9 8 ppre q-1pa7 0 11 1 9 8 5 17-1pb8 1 22 7-9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17-1pb8 1 22 7-9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17-1pb8 1 22 7-9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述1.简述以下算法的功能(1)Status A(Link
24、edlist L)/L是无表头结点的单链表 if(L&L-next)Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;return OK;(2)void BB(Lnode*s,Lnode*q)p=s;while(p-next!=q)p=p-next;p-next=s;void AA(Lnode*pa,Lnode*pb)/pa和pb分别是指向单循环链表中的两个结点 BB(pa,pb);BB(pb,pa);习 题第一个结点移到表尾 拆成两个循环链表2设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。3、试写一算法，实现顺序表的就地逆置。即(a1,a2,an)逆置为(an,a2,a1)4、描述以下概念的区别：首元结点、头结点、头指针5、试写一算法，对单链表实现就地逆置。习 题