数据结构与算法Python语言描述.pptx

内容提要线性结构线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现第1页/共37页 线性结构第2页/共37页学生信息表通讯录短信、聊天记录邮件列表购物清单账单何处用到线性结构？第3页/共37页 首元素相邻的元素组成前驱与后继关系线性表线性表的逻辑结构 尾元素第4页/共37页线性表线性表是n个数据元素的有限序列。一般形式：(a1,ai-1,ai,ai+1,an)直接前驱、直接后继长度：表中元素的个数n (n=0时称为空表)非空表中，每个元素都有一个确定的位置第5页/共37页 结构+操作结构的创建、结构的销毁：构造与析构引用型（访问型）：get加工型（改变型）：set线性表抽象数据类型？第6页/共37页ADT List 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,aiD,i=2,.,n 基本操作：InitList(&L)/初始化操作结果：构造一个空的线性表L。CreatList(&L,n)/创建操作结果：构造一个含n个元素的线性表L。DestroyList(&L)/结构销毁初始条件：线性表L已存在。操作结果：销毁线性表L。线性表类型线性表类型第7页/共37页/引用型操作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无定义。第8页/共37页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()失败，则操作失败。第9页/共37页/加工型操作：&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第10页/共37页题目：假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。方法：只要从LB中依次取出每个数据元素，并依值在LA中进行查访，若不存在，则插入。线性表类型的应用求集合的并集求集合的并集第11页/共37页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);线性表类型的应用求集合的并集求集合的并集第12页/共37页题目：已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。方法：设置两个指针分别指向LA和LB的当前元素，将数值较小的元素插入LC中。线性表类型的应用归并操作第13页/共37页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);第14页/共37页线性表的顺序表示和实现线性表的链式表示和实现线性表的表示和实现第15页/共37页是指用一组地址连续的存储单元依次存放线性表的数据元素以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑相邻线性表的顺序表示第16页/共37页是指用一组地址连续的存储单元依次存放线性表的数据元素设每个数据元素需占用C个存储单元LOC(ai)=LOC(ai-1)+CLOC(ai)=LOC(a1)+(i-1)C线性表的顺序表示和实现第17页/共37页是指用一组地址连续的存储单元依次存放线性表的数据元素线性表的顺序存储结构是一种能够随机存取的存储结构，通常用动态数组来实现。线性表的顺序表示和实现第18页/共37页#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 List;顺序存储结构的表示顺序存储结构的表示a1a2a3a6a7a4a5listsizeelemlength第19页/共37页2023/3/1220279103listsizelengthelem动态内存空间List类型的对象L第20页/共37页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第21页/共37页【结构的销毁没有空间了！】void DestroyList(List&L)/空间释放free(L.elem);L.elem=NULL;L.length=0;L.listsize=0;【清空表空间还在，只是“没有”元素了！】void ClearList(List&L)L.length=0;第22页/共37页/引用型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);/注意引用参数的使用！第23页/共37页Status GetElem(List L,int i,ElemType&e)/i 的合法性检测if(i L.length)return ERROR;/取元素e=L.elemi-1;return OK;第24页/共37页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;第25页/共37页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;第26页/共37页插入操作：Status InsertList()插入前的线性表：(a1,ai-1,ai,ai+1,an)插入后的线性表：(a1,ai-1,b,ai,ai+1,an)时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化第27页/共37页第28页/共37页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也做了元素的拷贝工作么？】第29页/共37页【数组方式的元素移动、插入】/从插入位置开始向后的元素，自后向前依次后移for(j=L.length;j=i;j-)L.elem j=L.elem j-1;/插入e，修改表长L.elemi-1=e;+L.length;return OK;第30页/共37页【指针方式的元素移动、插入，有些难以阅读。】/从插入位置开始向后的元素，自后向前依次后移q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入e，修改表长*q=e;+L.length;return OK;第31页/共37页删除操作：Status DeleteList()删除前的线性表：(a1,ai-1,ai,ai+1,an)删除后的线性表：(a1,ai-1,ai+1,an)时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化第32页/共37页第33页/共37页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;第34页/共37页/两个表的有序归并/此处作为List类型的基本操作直接定义！void MergeList(List La,List Lb,List&Lc)【此处应细致考虑，如果！=NULL，要先做销毁DestroyList操作，再重新开空间！】/开了最少的空间 Lc.listsize=La.length+Lb.length;Lc.elem=(Elemtype*)malloc(Lc.listsize*sizeof(Elemtype);if(!Lc.elem)exit(OVERFLOW);/起步准备pa=La.elem;pb=Lb.elem;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length 1;第35页/共37页/有序归并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)空间第36页/共37页2023/3/12数学科学学院37感谢您的观看！第37页/共37页