数据结构第2章线性表.ppt

数据结构 与 算法第二讲：线性表（一）内容提要v线性表的定义和基本操作v线性表的顺序存储结构v线性表的链式存储结构（单链表）11/05/20242什么叫线性表？11/05/20243线性表的定义和基本操作v线性表的定义q线性表是由n(n 0)个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,.,ai-1,ai,ai+1,.,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。11/05/20244线性表的结构分析11/05/20245（a1,a2,ai-1，ai,ai1，,an）n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点线性表特性1.线性表中元素之间的关系是线性关系：2.存在唯一的第一个元素；3.存在唯一的最后一个元素；4.除第一个元素之外，每个元素均只有一个直接前驱；5.除最后一个元素之外，每个元素均只有一个直接后继。11/05/20246现实生活中的线性表【思考】下列哪些关系属于线性关系呢？q家族的亲戚关系？q同学之间的友谊？q恋人之间的爱情？q班级同学的名册？q食堂窗口前排队？q自习教室里占座？11/05/20247线性表中的元素类型（）原子类型：如整数、字符等。（）结构类型：如表示一个学生信息的数据元素，包含学号、姓名、性别等数据项。11/05/20248线性表举例1.La=（34，89，765，12，90，-34，22）数据元素类型为int。2.Ls=(Hello,World,China,Welcome)数据元素类型为string。3.Lb=(book1,book2,.,book100)数据元素类型为下列所示的结构类型：11/05/202491.struct bookinfo2.3.int No;/图书编号4.char*name;/图书名称5.char*auther;/作者名称6.;7.抽象数据类型线性表定义ADT List数据对象：D=ai|aiElemSet,i=1,2,.,n,n0数据关系：R=|ai,ai+1 D,i=1,2,.,n,n0基本操作：InitList(&L)/初始化操作，建立一个空的线性表LDestroyList(&L)/销毁已存在的线性表LClearList(&L)/将线性表清空ListInsert(&L,i,e)/在线性表L中第i个位置插入新元素eListDelete(&L,i,&e)/删除线性表L中第i个位置元素，并用e返回其值IsEmpty(L)/若线性表为空，返回true，否则返回falseListLength(L)/返回线性表L的元素个数LocateElem(L,e)/将线性表L中查找与给定值e相等的元素，若成功返回该/元素在表中的序号，否则返回 0GetElem(L,i,&e)/将线性表L中的第i个位置元素返回给eADT List11/05/202410改进型操作引用型操作实现两个线性集合的并集11/05/202411/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/1.void ListUnion(List&La,List Lb)2.3.int La_len,Lb_len,i;4.ElemType e;/*声明与La和Lb相同的数据元素e*/5.La_len=ListLength(La);/*求线性表的长度*/6.Lb_len=ListLength(Lb);7.for(i=1;i elem=(ElemType*)malloc(LIST_MAX_LENGTH*sizeof(ElemType);/分配空间4.if(L-elem=NULL)5.return ERROR;/若分配空间不成功，返回ERROR6.L-length=0;/将当前线性表长度置07.return OK;/成功返回OK8.1.初始化线性表L【注意】线性表长度和数组长度的区别。数组长度一般是所分配空间的最大长度，一般是不变的；线性表长度是当前数据元素的数目，一开始为零，且随着数据的插入删除而变化。length=0elemLsizeof(ElemType)LIST_MAX_LENGTH线性表顺序结构的算法实现（2）2.销毁线性表L11/05/2024211.void DestroyList(SQ_LIST*L)2.3.if(L-elem)4.free(L-elem);/释放线性表占据的所有存储空间5.1.void ClearList(SQ_LIST*L)2.3.L-length=0;/将线性表的长度置为04.3.清空线性表Llength=9elemLlength=9elemLlength=0线性表顺序结构的算法实现（3）11/05/2024224.求线性表L的长度1.int GetLength(SQ_LIST L)2.3.return(L.length);4.5.判断线性表L是否为空1.int IsEmpty(SQ_LIST L)2.3.if(L.length=0)4.return TRUE;5.else 6.return FALSE;7.线性表顺序结构的算法实现（4）11/05/2024236.获取线性表L中的某个数据元素的内容1.int GetElem(SQ_LIST L,int i,ElemType*e)2.3.if(iL.length)4.return ERROR;/判断i值是否合理，若不合理，返回ERROR4.*e=L.elemi-1;/数组中第i-1的单元存储着线性表中第i个数据元素的内容5.return OK;6.【注意】现实中的例子，还记得周星星的电影吗？“9527，出来！”线性表顺序结构的算法实现（5）11/05/2024247.在线性表L中检索值为e的数据元素1.int LocateElem(SQ_LIST L,ElemType e)/算法2.62.3.for(i=0;ilength=LIST_MAX_LENGTH)4.return ERROR;/检查是否有剩余空间5.if(iL-length+1)6.return ERROR;/检查i值是否合理7.for(j=L-length-1;j=i;i-)/将线性表第i个元素 之后的所有元素向后移动8.9.L.-elemj=L-elemj-1;10.11.L-elemi-1=e;/将新元素的内容放入线性表的第i个位置12.L-length+;/线性表的长度加一13.return OK;14.线性表顺序结构的算法实现（6续）11/05/202426ABCDEFGH空闲空间插队前大哥，求求你？ABCDEFGH空闲空间插队后大哥，谢谢你！加塞的出去！插入算法的分析v时间复杂度q从算法流程上看，查找插入位置、插入元素的时间花费是常数级，而算法执行时间主要消耗在插入前元素的移动上，而移动元素的个数与插入位置i有关。o最好情况:在表尾插入，不移动元素，T(n)=O(1)o最坏情况:在表头插入，移动n个元素，T(n)=O(n)o平均复杂度：设pi为在第i个元素之前插入一个元素的概率，且P1=P2=Pi=Pn=1/(n+1)，则平均移动次数为：即T(n)=O(n)v空间复杂度q不需要额外空间，S(n)=O(1)11/05/202427线性表顺序结构的算法实现（7）9.将线性表L中第i个数据元素删除11/05/2024281.Status ListDelete(SQ_LIST*L,int i,ElemType*e)/算法2.52.3.if(IsEmpty(L)4.return ERROR;/检测线性表是否为空5.if(iL-length)6.return ERROR;/检查i值是否合理7.*e=L-elemi-1;/将欲删除的数据元素内容保留在e所指示的存储 /单元中8.for(j=i;jlength-1;j+)/将线性表第i+1个元素 之后的所有元素向前移动9.10.L-elemj-1=L-elemj;11.12.L-length-;13.return OK;14.线性表顺序结构的算法实现（7续）11/05/202429ABCDEFGH空闲空间逃离后ABCDEFGH空闲空间逃离前骗子，还我钱删除算法的分析v 时间复杂度q在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：v 分析结论q顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。11/05/202430顺序结构总结v顺序表的优缺点q优点：o利用存储顺序表示相应的逻辑顺序，不需要额外的存储空间来表示元素间的逻辑关系；o可以快速地存取表中的任意一个元素；q缺点：o插入和删除元素时要移动大量的元素；o对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；o容易造成存储空间的“碎片”。v顺序表的基本运算的复杂度q插入oT(n)=O(n)，S(n)=O(1)q删除oT(n)=O(n)，S(n)=O(1)11/05/202431怎么应对线性表顺序存储结构的缺点？11/05/202432内容提要v线性表的定义和基本操作v线性表的顺序存储结构v线性表的链式存储结构（单链表）11/05/202433线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存储：11/05/202434 链式存储结构的特点v线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；v在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。11/05/202435【注意】和随机存取方式的不同。想想单线联系的地下党组织。线性表链式存储结构的结点v 术语q表示每个数据元素的两部分信息组合在一起被称为结点；q其中表示数据元素内容的部分被称为数据域（data）；q表示直接后继元素存储地址的部分被称为指针或指针域（next）。v单链表简化的描述形式11/05/202436headabcd 其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。v带头结点的单链表headabcd我们为了更方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，成为头结点。头结点的数据域可以不存储任何信息，或者存储如线性表的长度等附加信息。头结点的指针域存储指向第一个结点的指针。线性表链式存储结构的结点（续）11/05/202437头指针头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针即便链表为空，头指针也可能不为空。头指针是链表的必要元素头指针具有标识作用，是访问链表数据的唯一入口。头结点头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了头结点不一定是链表必须要素headabcdheadabcd线性表的链式存储结构的类型定义（C语言）11/05/2024381.typedef struct node /结点类型2.3.ElemType data;4.struct node*next;5.NODE;6.typedef struct link_list /链表类型7.8.NODE*head;9.LINK_LIST;datanextNODEheadLINK_LIST线性表链式存储类型的基本操作1.构造一个空的线性表L InitList(&L)2.求线性表L的长度 ListLength(L)3.判断线性表L是否为空 IsEmpty(L)4.获取线性表L中的某个数据元素内容 GetElem(L,i,&e)5.检索值为e的数据元素 LocateELem(L,e)6.返回线性表L中e的直接前驱元素 PriorElem(L,&e)7.返回线性表L中e的直接后继元素 NextElem(L,&e)8.在线性表L中插入一个数据元素 ListInsert(&L,i,e)9.删除线性表L中第i个数据元素 ListDelete(&L,i,&e)10.销毁已存在的线性表L DestoryList(&L)11.清空已存在的线性表L ClearList(&L)11/05/202439线性表链式结构的算法实现（1）1.初始化链表L11/05/2024401.int InitList(LINK_LIST*L)2.3.L-head=(*NODE)malloc(sizeof(NODE);/为头结点分配存储单元4.if(L-head)5.6.L-head-next=NULL;7.return OK;8.9.else 10.return ERROR;11.NULLnextheadLhead线性表链式结构的算法实现（2）11/05/2024412.求链表L的长度1.int ListLength(LINK_LIST L)2.3.NODE*p;4.int len;5.for(p=L.head,len=0;p-next!=NULL;p=p-next,len+);6.return(len);7.NULLnextheadLdata1nextdata2nextPlen=0Plen=1Plen=2return len线性表链式结构的算法实现（3）11/05/2024423.判链表L空否1.int IsEmpty(LINK_LIST L)2.3.if(L.head-next=NULL)4.return TRUE;5.else 6.return FALSE;7.NULLnextheadLreturn TRUE线性表链式结构的算法实现（4）11/05/2024434.通过e返回链表L中第i个数据元素的内容1.void GetElem(LINK_LIST L,int i,ElemType*e)2.3.NODE*p;4.int j;5.if(iListLength(L)/检测i值的合理性6.exit ERROR;7.for(p=L.head,j=0;j!=i;p=p-next,j+);/找到第i个结点8.*e=p-data;/将第i个结点的内容赋给e指针所指向的存储单元中9.NULLnextheadLdata1nextdata2nextPj=0Pj=1Pj=2【假设】i=2*e=p-data线性表链式结构的算法实现（5）11/05/2024445.在链表L中检索值为e的数据元素1.NODE*LocateElem(LINK_LIST L,ElemType e)2.3.NODE*p;4.for(p=L.head-next;p&p-data!=e;p=p-next);/寻找满足条件的结点5.return(p);6.NULLnextheadLdata1nextenextPPreturn p线性表链式结构的算法实现（6）11/05/2024456.返回链表L中结点e的直接前驱结点1.NODE*PriorElem(LINK_LIST L,NODE*e)2.3.NODE*p;4.if(L.head-next=e)/检测第一个结点5.return NULL;6.for(p=L.head;p-next&p-next!=e;p=p-next);7.if(p-next=e)8.return p;9.else 10.return NULL;11.NULLnextheadLdata1nextdata2nextPdata3nextePreturn pP线性表链式结构的算法实现（7）11/05/2024467.返回链表L中结点e的直接后继结点1.NODE*NextElem(LINK_LIST L,NODE*e)2.3.NODE*p;4.for(p=L.head-next;p&p!=e;p=p-next);5.if(p)6.p=p-next;7.return p;8.NULLnextheadLdata1nextdata2nextPdata3nextPreturn peP线性表链式结构的算法实现（8）11/05/2024478.在链表L中第i个数据元素之前插入数据域为e的元素 1.int ListInsert(LINK_LIST*L,int i,ElemType e)2.3.NODE*p,*s;4.int j;5.if(iListLength(L)+1)6.return ERROR;7.s=(NODE*)malloc(sizeof(NODE);/line(7-10)创建数据域为e的元素8.if(s=NULL)9.return ERROR;10.s-data=e;11.for(p=L-head,j=0;p&jnext;j+);/寻找第i-1个结点12.s-next=p-next;/line(12-13)将s结点插入13.p-next=s;14.return OK;15.线性表链式结构的算法实现（8续）11/05/2024488.在链表L中第i个数据元素之前插入数据域为e的元素 1.int ListInsert(LINK_LIST*L,int i,ElemType e)2.3.NODE*p,*s;4./(0)检查i是否在合理范围内5./(1)创建数据域为e的元素，此时s指向被创建的新数据元素6./(2)寻找第i-1个结点，此时p指向第i-1个结点7.s-next=p-next;8.p-next=s;/(3)将s结点插入9.return OK;10.datai-1dataiPdatasnextSnextnextnextnextdatai-1datainextnextdatasnextPS线性表链式结构的算法实现（9）11/05/2024499.将链表L中第i个数据元素删除，并将其内容保存在e中1.int ListDelete(LINK_LIST*L,int i,ElemType*e)2.3.NODE*p,*s;4.int j;5.if(iListLength(L)/检查i值的合理性6.return ERROR;7.for(p=L-head,j=0;jnext,j+);/寻找第i-1个结点8.s=p-next;/用s指向将要删除的结点9.*e=s-data;10.p-next=s-next;/删除s指针所指向的结点11.free(s);12.return OK;13.线性表链式结构的算法实现（9续）11/05/2024509.将链表L中第i个数据元素删除，并将其内容保存在e中1.int ListDelete(LINK_LIST*L,int i,ElemType*e)2.3.NODE*p,*s;4./(0)检查i值的合理性5./(1)寻找第i-1个结点，p指向第i-1个结点6.s=p-next;/(2)用s指向将要删除的结点7.*e=s-data;/(3)将要删除的内容保存在e中8.p-next=s-next;/(4)删除s指针所指向的结点9.free(s);10.return OK;11.datai-1datai+1nextnextdatainextPSnext*e=s-data线性表链式结构的算法实现（10）10.销毁链表L 11/05/2024511.void DestoryList(LINK_LIST*L)2.3.NODE*p;4.while(L-head)/依次删除链表中的所有结点5.6.p=L-head;7.L-head=L-head-next;8.free(p);9.10.NULLnextheadLdatanextPheadPhead线性表链式结构的算法实现（11）11/05/20245211.清空链表L 1.void ClearList(LINK_LIST*L)2.3.NODE*p;4.while(L-head-next)5.6.p=L-head-next;/p指向链表中头结点后面的第一个结点7.L-head-next=p-next;/删除p结点8.free(p);/释放p结点占据的存储空间9.10.NULLnextLdata2nextPnextPnextnextheaddata1单链表结构和顺序存储结构的对比存储分配方式顺序存储结构用一段连续的存储单元依次存储线性表的数据元素单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素时间性能查找顺序存储结构O(1)单链表O(n)插入和删除顺序存储结构需要平均移动表长一半的元素，时间为O(n)单链表在找出某位置的指针后，插入和删除的时间仅为O(1)空间性能顺序存储结构需要预分配存储空间，分大了，浪费，分小了，易发生溢出单链表不需要预分配一整块存储空间，只要有就可以分配，元素个数也不受限制11/05/202453【思考】游戏设计中，存储用户注册信息用什么结构？存储玩家的装备或武器列表用什么结构？用类C语言实现单链表结构的归并算法11/05/2024541.void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)2./归并两个非递减单链表La、Lb到Lc中，且使Lc非递减3.pa=La-next;pb=Lb-next;4.Lc=pc=La;5.while(pa&pb)6.7.if(pa-data data)8.9.pc-next=pa;pc=pa;pa=pa-next;10.11.else12.13.pc-next=pb;pc=pb;pb=pb-next;14.15./while16.pc-next =pa?pa:pb;17.free(Lb);18./MergeList_L用类C语言实现顺序存储结构的归并算法11/05/2024551.void MergeList(SqList La,SqList Lb,SqList&Lc)/算法2.72.3./已知顺序线性表La和Lb的元素按值非递减排列。4./归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列5.ElemType*pa,*pa_last,*pb,*pb_last,*pc;6.pa=La.elem;7.pb=Lb.elem;8.Lc.listsize=Lc.length=La.length+Lb.length;/不用InitList()创建空表Lc9.pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);10.if (!Lc.elem)exit(OVERFLOW);/存储分配失败 11.pa_last=La.elem+La.length-1;12.pb_last=Lb.elem+Lb.length-1;13.while(pa=pa_last&pb=pb_last)/表La和表Lb均非空14./归并15.if(*pa=*pb)*pc+=*pa+;else *pc+=*pb+;16.17.while(pa=pa_last)/表La非空且表Lb空18.*pc+=*pa+;/插入La的剩余元素19.while(pb=pb_last)/表Lb非空且表La空20.*pc+=*pb+;/插入Lb的剩余元素21.