数据结构与算法（Python语言描述）课件

第第 三三 章章 线线 性性 表表2016 Fall数据结构数据结构第 三 章 线 性 表2016 Fall数据结构内容提要内容提要线性结构线性结构线性表的类型定义线性表的类型定义线性表的顺序表示和实现线性表的顺序表示和实现线性表的链式表示和实现线性表的链式表示和实现内容提要线性结构 线性结构线性结构线性结构学生信息表学生信息表通讯录通讯录短信、聊天记录短信、聊天记录邮件列表邮件列表购物清单购物清单账单账单何处用到线性结构？何处用到线性结构？学生信息表何处用到线性结构？首元素首元素相邻的元素相邻的元素组成组成前驱前驱与与后继后继关系关系线性表线性表线性表的逻辑结构线性表的逻辑结构 尾元素尾元素 首元素相邻的元素线性表线性表的逻辑结构 尾元素线性表线性表线性表是线性表是n个数据元素的有限序列。个数据元素的有限序列。一般形式：一般形式：(a1,ai-1,ai,ai+1,an)直接前驱、直接后继直接前驱、直接后继长度：表中元素的个数长度：表中元素的个数n (n=0时称为空表时称为空表)非空表中，每个元素都有一个确定的位置非空表中，每个元素都有一个确定的位置线性表线性表是n个数据元素的有限序列。结构结构+操作操作结构的创建、结构的销毁：构造与析构结构的创建、结构的销毁：构造与析构引用型（访问型）：引用型（访问型）：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。线性表类型线性表类型ADT List 线性表类型/引用型操作引用型操作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()失败，则操作失败。失败，则操作失败。数据结构与算法（Python语言描述）课件/加工型操作：加工型操作：&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/加工型操作：&L!题目：假设利用两个线性表题目：假设利用两个线性表LA和和LB分别表示两分别表示两个集合个集合A和和B，现要求一个新的集合，现要求一个新的集合A=A B。方法：只要从方法：只要从LB中依次取出每个数据元素，并依值在中依次取出每个数据元素，并依值在LA中进行查访，若不存在，则插入。中进行查访，若不存在，则插入。线性表类型的应用线性表类型的应用求集合的并集求集合的并集题目：假设利用两个线性表LA和LB分别表示两个集合A和B，现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);线性表类型的应用线性表类型的应用求集合的并集求集合的并集void unionSet(List&La,List L题目：已知线性表题目：已知线性表LA和和LB中的数据元素按值非递中的数据元素按值非递减有序排列，现要求将减有序排列，现要求将LA和和LB归并为一个新的线归并为一个新的线性表性表LC，且，且LC中的数据元素仍按值非递减有序排中的数据元素仍按值非递减有序排列。列。方法：设置两个指针分别指向方法：设置两个指针分别指向LA和和LB的当前元素，将的当前元素，将数值较小的元素插入数值较小的元素插入LC中。中。线性表类型的应用线性表类型的应用归并操作归并操作题目：已知线性表LA和LB中的数据元素按值非递减有序排列，现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);void MergeList(List La,List L线性表的顺序表示和实现线性表的顺序表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的表示和实现线性表的表示和实现线性表的顺序表示和实现线性表的表示和实现是指是指用一组地址连续的存储单元依次存放线性表用一组地址连续的存储单元依次存放线性表的数据元素的数据元素以元素在计算机内以元素在计算机内“物理位置相邻物理位置相邻”来表示线性表中数来表示线性表中数据元素之间的逻辑相邻据元素之间的逻辑相邻线性表的顺序表示线性表的顺序表示是指用一组地址连续的存储单元依次存放线性表的数据元素线性表的是指是指用一组地址连续的存储单元依次存放线性表用一组地址连续的存储单元依次存放线性表的数据元素的数据元素设每个数据元素需占用设每个数据元素需占用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;顺序存储结构的表示顺序存储结构的表示a1a2a3a6a7a4a5listsizeelemlength#define LIST_INIT_SIZE 100 /279103listsizelengthelem动态内存空间动态内存空间List类型的对象类型的对象L2024/6/1721279103listsizelengthelem动态内存空间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=0Status InitList(List&L)顺序存储【结构的销毁结构的销毁没有空间了！没有空间了！】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;Status GetElem(List L,int i,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,ElemTypint 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;int LocateElem(List L,ElemTyp插入操作：插入操作：Status InsertList()插入前的线性表：插入前的线性表：(a1,ai-1,ai,ai+1,an)插入后的线性表：插入后的线性表：(a1,ai-1,b,ai,ai+1,an)时间复杂度：最坏和平均的情况时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化逻辑关系发生了变化数据结构与算法（Python语言描述）课件数据结构与算法（Python语言描述）课件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也做了元素的拷贝工作也做了元素的拷贝工作么？么？】Status InsertList(List&L,int【数组方式的元素移动、插入数组方式的元素移动、插入】/从插入位置开始向后的元素，自后向前依次后从插入位置开始向后的元素，自后向前依次后移移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()数据结构与算法（Python语言描述）课件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;Status DeleteList(List&L,int/两个表的有序归并两个表的有序归并/此处作为此处作为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;/两个表的有序归并/有序归并有序归并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+;/修改表长修改表长Lc.length=La.length+Lb.length;时间复杂度：时间复杂度：O(La.Length+Lb.Length)空间复杂度：和空间申请、空间追加策略有关，空间复杂度：和空间申请、空间追加策略有关，至少需要至少需要 2(La.Length+Lb.Length)空间空间数据结构与算法（Python语言描述）课件