数据结构与算法(Python语言描述)课件1

第三章线性表2016Fall《数据结构》内容提要•线性结构•线性表的类型定义•线性表的顺序表示和实现•线性表的链式表示和实现线性结构•学生信息表•通讯录•短信、聊天记录•邮件列表•购物清单•账单何处用到线性结构？？？首元素相邻的元素组成前驱与后继关系线性表线性表的逻辑结构尾元素线性表•线性表是n个数据元素的有限序列。•一般形式：(a1,…,ai-1,ai,ai+1,…,an)•直接前驱、直接后继•长度：表中元素的个数n(n=0时称为空表)•非空表中，每个元素都有一个确定的位置•结构+操作–结构的创建、结构的销毁：构造与析构–引用型（访问型）：get–加工型（改变型）：set线性表抽象数据类型？ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|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已存在，且1≤i≤LengthList(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已存在，且1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)//删除数据元素初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList•题目：假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。–方法：只要从LB中依次取出每个数据元素，并依值在LA中进行查访，若不存在，则插入。线性表类型的应用——求集合的并集voidunionSet(List&La,ListLb){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中。线性表类型的应用——归并操作voidMergeList(ListLa,ListLb,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)+C–LOC(ai)=LOC(a1)+(i-1)×C线性表的顺序表示和实现•是指用一组地址连续的存储单元依次存放线性表的数据元素线性表的顺序存储结构是一种能够随机存取的存储结构，通常用动态数组来实现。线性表的顺序表示和实现#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}List;顺序存储结构的表示a1a2a3a6a7a4a5listsizeelemlength2020/3/29数学科学学院21279103listsizelengthelem动态内存空间List类型的对象LStatusInitList(List&L){//分配空间L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//空间总长赋初值L.listsize=LIST_INIT_SIZE;//表长赋初值0L.length=0;returnOK;}顺序存储时基本操作的实现listsizeelemlength=0【结构的销毁——没有空间了！】voidDestroyList(List&L){//空间释放free(L.elem);L.elem=NULL;L.length=0;L.listsize=0;}【清空——表空间还在，只是“没有”元素了！】voidClearList(List&L){L.length=0;}//引用型voidTraverseList(ListL,void(*visit)(ElemType)){for(i=0;iL.length;i++)(*visit)(L.elem[i]);}//加工型——map操作！voidTraverseList(List&L,void(*visit)(&ElemType)){for(i=0;iL.length;i++)(*visit)(L.elem[i]);}//注意引用参数的使用！！！StatusGetElem(ListL,inti,ElemType&e){//i的合法性检测if(i1||iL.length)returnERROR;//取元素e=L.elem[i-1];returnOK;}intLocateElem(ListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//起步i=1;p=L.elem;//在有效范围内查询while(i=L.length&&!(*compare)(*p++,e))++i;//返回元素的真实位置if(i=L.length)returni;elsereturn0;}intLocateElem(ListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//起步i=1;//在有效范围内查询while(i=L.length&&!(*compare)(L.elem[i-1],e))++i;//返回元素的真实位置if(i=L.length)returni;elsereturn0;}插入操作：StatusInsertList()插入前的线性表：(a1,…,ai-1,ai,ai+1,…,an)插入后的线性表：(a1,…,ai-1,b,ai,ai+1,…,an)时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化StatusInsertList(List&L,inti,ElemTypee){//插入范围的合法性检测if(i1||iL.length+1)returnERROR;//空间不够，追加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.elem[j]=L.elem[j-1];}//插入e，修改表长L.elem[i-1]=e;++L.length;returnOK;}【指针方式的元素移动、插入，有些难以阅读。。。。】//从插入位置开始向后的元素，自后向前依次后移q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//插入e，修改表长*q=e;++L.length;returnOK;}删除操作：StatusDeleteList()删除前的线性表：(a1,…,ai-1,ai,ai+1,…,an)删除后的线性表：(a1,…,ai-1,ai+1,…,an)时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化StatusDeleteList(List&L,inti,ElemType&e){//合法性检测if((i1)||(iL.length))returnERROR;//取出元素带回p=&(L.elem[i-1]);e=*p;//自前向后前移元素q=L.elem+L.length-1;for(++p;p=q;++p)*(p-1)=*p;//修改表长--L.length;returnOK;}//两个表的有序归并//此处作为List类型的基本操作直接定义！！！voidMergeList(ListLa,ListLb,List&Lc){【此处应细致考虑，如果Lc.elem！=NULL，要先做销毁DestroyList操作，再重新开空间！】//开了最少的空间Lc.listsize=La.length+Lb.length;Lc.elem=(E