数据结构与算法-课件

第第 三三 章章 线 性性 表表2016 Fall数据数据结构构内容提要内容提要线线性性结结构构线线性表的性表的类类型定型定义义线线性表的性表的顺顺序表示和序表示和实现实现线线性表的性表的链链式表示和式表示和实现实现 线性性结构构学生信息表学生信息表通通讯录讯录短信、聊天短信、聊天记录记录邮邮件列表件列表购购物清物清单单账单账单何何处用到用到线性性结构？构？首元素首元素相邻的元素相邻的元素组成组成前驱前驱与与后继后继关系关系线性表性表线性表的逻辑结构线性表的逻辑结构 尾元素尾元素线线性表性表线性表是性表是n个数据元素的有限序列。个数据元素的有限序列。一般形式：一般形式：(a1,ai-1,ai,ai+1,an)直接前直接前驱、直接后、直接后继长度：表中元素的个数度：表中元素的个数n (n=0时称称为空表空表)非空表中，每个元素都有一个确定的位置非空表中，每个元素都有一个确定的位置 结构构+操作操作结构的构的创建、建、结构的构的销毁：构造与析构：构造与析构引用型（引用型（访问型）：型）：get加工型（改加工型（改变型）：型）：set线性表抽象数据性表抽象数据类型？型？ADT List 数据数据对象：象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 基本操作：基本操作：InitList(&L)/初始化初始化操作操作结果：构造一个空的果：构造一个空的线性表性表L。CreatList(&L,n)/创建建操作操作结果：构造一个含果：构造一个含n个元素的个元素的线性表性表L。DestroyList(&L)/结构构销毁初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：果：销毁线性表性表L。线性表类型线性表类型/引用型操作引用型操作ListLength(L)/求求线性表的性表的长度度初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：返回果：返回L中元素个数。中元素个数。ListEmpty(L)/判断判断线性表是否性表是否为空空初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：若果：若L不空，返回不空，返回true，否，否则为false。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无定无定义。GetElem(L,i,&e)/取取线性表中第性表中第i个数据元素个数据元素初始条件：初始条件：线性表性表L已存在，且已存在，且1iLengthList(L)。操作操作结果：用果：用e返回返回L中第中第i个元素的个元素的值。LocateElem(L,e,compare()/定位函数定位函数初始条件：初始条件：线性表性表L已存在，已存在，e为给定定值，compare()是元素判定函数。是元素判定函数。操作操作结果：返回第果：返回第1个与个与e满足足compare关系的元素关系的元素的位序。的位序。若若这样的元素不存在，的元素不存在，则返回返回值为0。ListTraverse(L,visit()/遍遍历线性表性表初始条件：初始条件：线性表性表L已存在，已存在，visit()为某个某个访问函数。函数。操作操作结果：依次果：依次对L的每个元素的每个元素调用函数用函数visit()。一旦一旦visit()失失败，则操作失操作失败。/加工型操作：加工型操作：&L!ClearList(&L)/线性表置空性表置空初始条件：初始条件：线性表性表L已存在。已存在。操作操作结果：将果：将L重置重置为空表空表ListInsert(&L,i,e)/插入数据元素插入数据元素初始条件：初始条件：线性表性表L已存在，且已存在，且1iLengthList(L)+1。操作操作结果：在果：在L的第的第i个元素之前插入新个元素之前插入新的元素的元素e，L的的长度增度增1。ListDelete(&L,i,&e)/删除数据元素除数据元素初始条件：初始条件：线性表性表L已存在且非空，已存在且非空，1iLengthList(L)。操作操作结果：果：删除除L的第的第i个元素，并用个元素，并用e返返回其回其值，L的的长度减度减1。ADT List题目：假目：假设利用两个利用两个线性表性表LA和和LB分分别表示两表示两个集合个集合A和和B，现要求一个新的集合要求一个新的集合A=A B。方法：只要从方法：只要从LB中依次取出每个数据元素，并依中依次取出每个数据元素，并依值在在LA中中进行行查访，若不存在，若不存在，则插入。插入。线性表性表类型的型的应用用求集合的并集求集合的并集void unionSet(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,EQUAL)InsertList(La,+La_len,e);线性表性表类型的型的应用用求集合的并集求集合的并集题目：已知目：已知线性表性表LA和和LB中的数据元素按中的数据元素按值非非递减有序排列，减有序排列，现要求将要求将LA和和LB归并并为一个新的一个新的线性表性表LC，且，且LC中的数据元素仍按中的数据元素仍按值非非递减有序排减有序排列。列。方法：方法：设置两个指置两个指针分分别指向指向LA和和LB的当前元素，将的当前元素，将数数值较小的元素插入小的元素插入LC中。中。线线性表性表类类型的型的应应用用归归并操作并操作void MergeList(List La,List Lb,List&Lc)ClearList(Lc);/这里假定里假定Lc已已经做做过InitList操作，操作，/ClearList之后表的空之后表的空间还在！在！i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while(i=La_len)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);线性表的性表的顺序表示和序表示和实现线性表的性表的链式表示和式表示和实现线性表的表示和性表的表示和实现是指是指用一用一组地址地址连续的存的存储单元依次存放元依次存放线性表性表的数据元素的数据元素以元素在以元素在计算机内算机内“物理位置相物理位置相邻”来表示来表示线性表中数据性表中数据元素之元素之间的的逻辑相相邻线性表的性表的顺序表示序表示是指是指用一用一组地址地址连续的存的存储单元依次存放元依次存放线性表性表的数据元素的数据元素设每个数据元素需占用每个数据元素需占用C个存个存储单元元LOC(ai)=LOC(ai-1)+CLOC(ai)=LOC(a1)+(i-1)C线性表的性表的顺序表示和序表示和实现是指是指用一用一组地址地址连续的存的存储单元依次存放元依次存放线性表性表的数据元素的数据元素线性表的性表的顺序存序存储结构是一种能构是一种能够随机存取的存随机存取的存储结构，通常用构，通常用动态数数组来来实现。线性表的性表的顺序表示和序表示和实现#define LIST_INIT_SIZE 100 /线性表存性表存储空空间的初始的初始分配量分配量#define LISTINCREMENT 10 /线性表存性表存储空空间的分的分配增量配增量typedef struct ElemType*elem;/存存储空空间基址基址int length;/当前当前长度度int listsize;/当前分配的存当前分配的存储容量容量 List;顺序存储结构的表示顺序存储结构的表示a1a2a3a6a7a4a5listsizeelemlength279103listsizelengthelem动态内存空间动态内存空间List类型的对象类型的对象L2024/6/2521数学科学学院Status InitList(List&L)/分配空分配空间L.elem=(ElemType*)malloc(LIST_INIT_SIZE *sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/空空间总长赋初初值 L.listsize=LIST_INIT_SIZE;/表表长赋初初值0L.length=0;return OK;顺序存储时基本操作的实现顺序存储时基本操作的实现listsizeelemlength=0【结构的构的销毁没有空没有空间了！了！】void DestroyList(List&L)/空空间释放放free(L.elem);L.elem=NULL;L.length=0;L.listsize=0;【清空清空表空表空间还在，只是在，只是“没有没有”元素了！元素了！】void ClearList(List&L)L.length=0;/引用型引用型void TraverseList(List L,void(*visit)(ElemType)for(i=0;i L.length;i+)(*visit)(L.elemi);/加工型加工型map操作！操作！void TraverseList(List&L,void(*visit)(&ElemType)for(i=0;i L.length;i+)(*visit)(L.elemi);/注意引用参数的使用！注意引用参数的使用！Status GetElem(List L,int i,ElemType&e)/i 的合法性的合法性检测if(i L.length)return ERROR;/取元素取元素e=L.elemi-1;return OK;int LocateElem(List L,ElemType e,Status(*compare)(ElemType,ElemType)/起步起步i=1;p=L.elem;/在有效范在有效范围内内查询while(i=L.length&!(*compare)(*p+,e)+i;/返回元素的真返回元素的真实位置位置if(i=L.length)return i;else return 0;int LocateElem(List L,ElemType e,Status(*compare)(ElemType,ElemType)/起步起步i=1;/在有效范在有效范围内内查询while(i=L.length&!(*compare)(L.elemi-1,e)+i;/返回元素的真返回元素的真实位置位置if(i=L.length)return i;else return 0;插入操作：插入操作：Status InsertList()插入前的插入前的线性表：性表：(a1,ai-1,ai,ai+1,an)插入后的插入后的线性表：性表：(a1,ai-1,b,ai,ai+1,an)时间复复杂度：最坏和平均的情况度：最坏和平均的情况O(n)逻辑关系关系发生了生了变化化Status InsertList(List&L,int i,ElemType e)/插入范插入范围的合法性的合法性检测if(i L.length+1)return ERROR;/空空间不不够，追加，追加 if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;【实验时可先假定空可先假定空间总是是够用，先不考用，先不考虑空空间追加，先做好基本的元素移追加，先做好基本的元素移动、和插入，回、和插入，回头再再考考虑空空间的追加与元素的拷的追加与元素的拷贝！】【问题：实验一下一下realloc也做了元素的拷也做了元素的拷贝工作工作么？么？】【数数组方式的元素移方式的元素移动、插入、插入】/从插入位置开始向后的元素，自后向前依次后从插入位置开始向后的元素，自后向前依次后移移for(j=L.length;j=i;j-)L.elemj=L.elemj-1;/插入插入e，修改表，修改表长L.elemi-1=e;+L.length;return OK;【指指针方式的元素移方式的元素移动、插入，有些、插入，有些难以以阅读。】/从插入位置开始向后的元素，自后向前依次后从插入位置开始向后的元素，自后向前依次后移移q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入插入e，修改表，修改表长*q=e;+L.length;return OK;删除操作：除操作：Status DeleteList()删除前的除前的线性表：性表：(a1,ai-1,ai,ai+1,an)删除后的除后的线性表：性表：(a1,ai-1,ai+1,an)时间复复杂度：最坏和平均的情况度：最坏和平均的情况O(n)逻辑关系关系发生了生了变化化Status DeleteList(List&L,int i,ElemType&e)/合法性合法性检测if(i L.length)return ERROR;/取出元素取出元素带回回p=&(L.elemi-1);e=*p;/自前向后前移元素自前向后前移元素q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;/修改表修改表长-L.length;return OK;/两个表的有序两个表的有序归并并/此此处作作为List类型的基本操作直接定型的基本操作直接定义！void MergeList(List La,List Lb,List&Lc)【此此处应细致考致考虑，如果，如果Lc.elem！=NULL，要先做，要先做销毁DestroyList操作，再重新开空操作，再重新开空间！】/开了最少的空开了最少的空间 Lc.listsize=La.length+Lb.length;Lc.elem=(Elemtype*)malloc(Lc.listsize*sizeof(Elemtype);if(!Lc.elem)exit(OVERFLOW);/起步准起步准备pc=Lc.elempa=La.elem;pb=Lb.elem;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length 1;