-线性表ppt课件

《-线性表ppt课件》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

第二章线性表1

1【学习目标】了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。【重点和难点】链表。熟练掌握链表的操作对以后各章的学习将有很大帮助。2

2什么是线性结构？简单地说，线性结构是一个数据元素的有序集合。它有四个基本特征：1．集合中必存在唯一的一个"第一元素"；没有"前驱"2．集合中必存在唯一的一个"最后元素"；没有"后继"3．除最后元素之外，其它数据元素均有唯一的"直接后继"；4．除第一元素之外，其它数据元素均有唯一的"直接前驱"。课前回顾3

32.1线性表的逻辑定义2.1.1线性表的定义什么是线性表？具有相同数据类型的n个数据元素的有限序列。L＝(a1,a2,...,ai,...,an)表长:序列中数据元素的个数n；n=0——空表若ai是第i个数据元素，称i为ai在线性表中的位序。Linear_list=(D,R)D＝{ai|ai∈datatype,i=1,2,...,n,n≥0}R＝{|ai-1,ai∈D,i=2,...,n}4

42.1线性表的逻辑定义2.1.2线性表的基本操作基本操作：1.线性表初始化：Init_List(L)初始条件：线性表L不存在。　操作结果：构造一个空的线性表L。2.求线性表的长度：Length_List(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。3.取表元：Get_List(L,i)初始条件：线性表L已存在，1≤i≤Length_List(L)。操作结果：返回L中第i个元素的值或地址。5

52.1线性表的逻辑定义2.1.2线性表的基本操作4.按值查找：Locate_List(L,x)初始条件：线性表L已存在，x是给定的一个数据元素。操作结果：返回L中第一个值为x的数据元素的位序或地址。若这样的元素不存在，则返回-1。5.插入操作：Insert_List(L,i,x)初始条件：线性表L已存在，1≤i≤Length_List(L)+1。操作结果：在L的第i个元素之前插入新的元素x，L的长度增1。6.删除操作：Delete_List(L,i)初始条件：线性表L已存在且非空，1≤i≤Length_List(L)。操作结果：删除L的第i个元素，L的长度减1。6

6

7

82.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现intLength_List(SeqList*L){return(L->last＋1);}datatypeGet_List(SeqList*L,intpos){returnL->data[pos-1];}9

92.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现重点讨论:一、初始化操作二、元素定位操作三、插入元素操作四、删除元素操作10

102.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现函数名:malloc功 能:内存分配函数用 法:void*malloc(unsignedsize);返回值：指针，指向长度为size的存储空间；若分配失败，返回NULL。11

11一、初始化操作SeqList*init_SeqList(){SeqList*L;L=malloc(sizeof(SeqList));L->last=-1;returnL;}时间复杂度为：O(1)12

12二、按值查找若顺序表中存在和给定值相等的数据元素，就返回第一个满足条件元素的在线性表中的位置，以-1返回值表示不存在这样的数据元素。intLocation_SeqList(SeqList*L,datatypex){inti=0;//数组下标从0开始while(i<=L->last&&L->data[i]!=x)i++;//依次进行判定if(i>L->last)return-1;//下标超出范围，不存在elsereturni;//返回的是数组下标}时间复杂度为：O(n)13

13三、插入元素操作按定义，在线性表的第i个元素之前插入一个元素x，使得线性表(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,x,ai,…,an)逻辑结构的变换：(1)改变了表中ai-1,ai元素之间的关系，使改变为和(2)表长增101ii+1i+2n-1MAX-1a1a2…ai-1aiai+1…an…01ii+1i+2nMAX-1a1a2…ai-1xai…an…线性表中数据元素的插入前后如下图所示14

14在线性表L中第i个数据元素之前插入数据元素XintInsert_SeqList(SeqList*L，inti，datatypex){intj;if(L->last==MAXSIZE－1){printf(＂表满＂);return(-1);}/*表空间已满，不能插入*/if(i<1||i>L->last+2)/*检查插入位置的正确性*/{printf(＂位置错＂);return(0);}for(j=L->last;j>=i-1;j--)L->data[j+1]=L->data[j];/*插入位置及之后的元素后移*/L->data[i-1]=x;/*新元素插入*/L->last++;/*last仍指向最后元素*/return(1);/*插入成功，返回*/}时间复杂度为：O(n)15

15四、删除元素操作假设删除线性表中第i个元素，使得线性表(a1,…,ai-1,ai,ai＋1,…,an)改变为(a1,…,ai-1,ai＋1,…,an)逻辑结构的变化：(1)改变了表中元素ai-1,ai,ai＋1之间的关系，使和改变为(2)表长减1线性表中数据元素的删除前后如下图所示01ii+1i+2n-1MAX-1a1a2…ai-1aiai+1…an…01ii+1i+2n-2MAX-1a1a2…ai-1ai+1ai+2…an…16

16删除L的第i个元素，L的长度减1。intDelete_SeqList(SeqList*L;inti){intj;if(i<1||i>L->last+1)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);return(0);}for(j=i;j<=L->last;j++)L->data[j-1]=L->data[j];/*被删除元素之后的元素前移*/L->last--;return(1);/*删除成功*/}时间复杂度为：O(n)17

172.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现插入和删除操作的性能分析基本操作(移动元素)的执行次数不仅和表长有关，还依赖于插入和删除的位置。在顺序表中任何一个合法位置上进行"一次"插入操作时，需要移动的元素个数的平均值:18

182.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现在顺序表中任何一个合法位置上进行"一次"删除操作时，需要移动的元素个数的平均值:19

192.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现分析结论：顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。20

202.3线性表的链式存储及操作实现2.3.1单链表"链式存储表示"——以"附加信息(指针)"表示数据元素之间的逻辑关系。数据域data指针域nexttypedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；"结点“:结点定义:21

212.3线性表的链式存储及操作实现2.3.1单链表线性表的链式存储表示:由分别表示(a1,a2,...,an)的n个结点依次相链构成的序列。线性表链式存储结构示意图22

222.3线性表的链式存储及操作实现2.3.1单链表带头结点的单链表:为了便于处理一些特殊情况，在第一个结点之前附加一个叫“头结点”的结点，令该结点中指针域的指针指向第一个元素结点.头指针指向头结点。线性表为空:23

232.3线性表的链式存储表示和实现2.3.2单链表上基本操作的实现.初始化操作创建一个带头结点的空链表,L为指向头结点的指针LinkListInit_LinkList(){LinkListL；L=malloc(sizeof(LNode));L->next=NULL;returnL;}//InitList_L算法的时间复杂度为O(1)。24

242建立单链表头插法(不带头结点)LinkListCreat_LinkList1(){LinkListL；LNode*s;intx;/*设数据元素的类型为int*/L=NULL；scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;s->next=L;L=s;scanf(＂%d＂,&x);}returnL;}时间复杂度为：O(n)25

25头插法(带头结点)LinkListCreat_LinkList1(){LinkListL；LNode*s;intx;/*设数据元素的类型为int*/L=Init_LinkList();/*创建一个带头结点的空链表*/scanf(＂%d＂,&x);while(x!=flag)/*设flag为数据元素的结束标志*/{s=malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s;scanf(＂%d＂,&x);}returnL;}时间复杂度为：O(n)26

26尾插法（不带头结点）LinkListCreat_LinkList2(){LinkListL;LNode*s,*R;intx;L=NULL;R=L;scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;if(L==NULL)L=s;elseR->next=s;R=s;scanf(＂%d＂,&x);}If(R!=NULL)R->next=NULL;returnL;}时间复杂度：O(n)27

27尾插法（带头结点）LinkListCreat_LinkList1(){LinkListL;LNode*s,*R;intx;L=Init_LinkList();R=L;scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;R->next=s;R=s;scanf(＂%d＂,&x);}R->next=NULL;returnL;}时间复杂度为：O(n)28

283.求表长(不带头结点的)intLength_LinkList1(LinkListL){LNode*p=L;intj;if(P==NULL)return0;//空表j=1；while(p->next){p=p->next;j++;}returnj;}时间复杂度：O(n)29

29求表长(带头结点的)intLength_LinkList1(LinkListL){LNode*p=L;/*p指向头结点*/intj=0;while(p->next){p=p->next;j++;/*p所指的是第j个结点*/}returnj;}时间复杂度为：O(n)30

304.查找操作(1)按序号查找Get_Linklist(L,i)在单链表L中查找第i个元素结点，找到返回其指针，否则返回空Lnode*Get_LinkList(LinkListL,Inti);{LNode*p=L;intj=0;while(p->next!=NULL&&jnext;j++;}if(j==i)returnp;elsereturnNULL;}时间复杂度为：O(n)31

31(2)按值查找Locate_LinkList(L,x)在单链表L中查找值为x的结点，找到后返回其指针，否则返回空Lnode*Locate_LinkList(LinkListL,datatypex){LNode*p=L->next;while(p!=NULL&&p->data!=x)p=p->next;returnp;}时间复杂度为：O(n)32

325.插入操作如图，线性表的两个数据元素y和z之间插入一个数据元素a，已知p指向线性链表的结点y，s指向要插入的新结点.插入后的线性链表变化如下：插入的过程如下：s->next=p->next；p->next=s；33

335.插入操作在单链表L的第i个位置上插入值为x的元素intInsert_LinkList(LinkListL,inti,datatypex){LNode*p,*s;p=Get_LinkList(L,i-1);/*查找第i-1个结点*/if(p==NULL){printf(＂参数i错＂);return0;}/*第i-1个不存在不能插入*/else{s=malloc(sizeof(LNode));/*申请、填装结点*/s->data=x;s->next=p->next;/*新结点插入在第i-1个结点的后面*/p->next=s;return1;}}时间复杂度为：O(n)34

346.删除操作在如图线性表中，删除y所在的结点.只要修改指针域的指针，就可实现删除操作。删除后的线性链表变化。方法：使指针p指向要删除结点的前驱(y所在的结点)；将p的指针域指向要删除结点的后继结点；将要删除的结点释放。过程：s=p->next;p->next=s->next;free(s);35

356.删除操作删除单链表L上的第i个数据结点intDel_LinkList(LinkListL，inti){LinkListp,s;p=Get_LinkList(L,i-1);/*查找第i-1个结点*/if(p==NULL){printf(＂第i-1个结点不存在＂);return-1;}elseif(p->next==NULL){printf(＂第i个结点不存在＂);return0;}else{s=p->next;/*s指向第i个结点*/p->next=s->next;/*从链表中删除*/free(s);/*释放*s*/return1;}}时间复杂度为：O(n)36

362.3线性表的链式存储表示和实现2.3.2单链表上基本操作的实现链式存储结构的优势：能有效利用存储空间；动态存储分配，随用随取。插入或删除方便。只需要修改指针，而不需要进行大量元素的移动。链式存储结构的劣势：不能随机存取数据元素，只能从头指针开始一个个顺序进行37

372.3线性表的链式存储表示和实现2.3.3循环链表循环链表：表中最后一个结点的指针域不是空而是指向头结点，整个链表成为一个由链指针相链接的环。判别链表中最后一个结点的条件不再是"后继是否为空"，而是"后继是否为头结点"。为了提高操作效率，将头指针设成指向最后一个结点。38

382.3线性表的链式存储表示和实现2.3.4双向链表双向链表:typedefstructdLNode{datatypedata;structdLNode*prior;structdLNode*next;}DLNode,*DLinkList;假设指针p指向双向链表中某个结点，则：p->prior->next=p=p->next->prior39

392.3线性表的链式存储表示和实现2.3.4双向链表s->next=p->next;p->next=s;s->next->prior=s;s->prior=p;插入:在带头结点的双向循环链表L中结点*p之后插入结点*s143240

402.3线性表的链式存储表示和实现2.3.4双向链表q=p->next;e=q->data;p->next=q->next;p->next->prior=p;free(q);删除删除带头结点的双向循环链表L中结点*p的后继，并以e返回它的数据元素1241

412.3线性表的链式存储表示和实现2.3.4双向链表双向循环链表:让链表尾结点的后继指针指向头结点，而头结点的前驱指针指向尾结点，这就构成了2个方向的环。空的双向循环链表:由只含一个自成双环的头结点表示。42