第二章线性表(无答案).ppt

第一章了解抽象数据类型的定义和实现方法，如数据结构、逻辑结构(分类)、顺序图像、顺序存储结构、链图像、链存储结构、抽象数据类型，了解算法的特性(“差”性、确定性、可行性、输入、输出)，并了解算法理解时间复杂性是算法运行时间随问题大小的增长速度T(n)=O(f(n)推荐练习：48910(1111720)课堂练习问题解答：课件FTP学习材料，三元组或复数，表以线性结构执行简单访问操作，还会有很多问题总结抽象、线性结构及其常用任务以供重复使用，一个或多个普遍适用的ADT抽象数据类型：逻辑结构工作集线性结构工作集1(添加和无限制)-线性表线性结构工作集2(添加相同端点，后进先出)-堆栈线性结构工作集3(添加每个端点，先进先出)-队列线性有一个唯一的数据元素，称为“第一个”。有一个唯一的数据元素，称为“最后一个”。除了第一个数据元素外，每个元素都有其自己的“之前”。除最后一个元素外，每个元素都有唯一的“后续”考虑因素：R=，线性结构吗？第2-3章线性结构和线性表、堆栈和队列、第2章线性表、linear_list、第2章线性表和线性表的抽象数据类型定义了线性表的顺序表示和线性表的链表示和实现。一元多项式表示和添加，定义2.1线性表的抽象数据类型，ADTList数据对象：ai | ai elem set，I=1，2，n，n=0)数据关系：r=| ai此外，行表还包含(a1，a2，an)，n是表长度，n=0时，行表是空表基本操作：InitList(初始条件：行表l已存在的操作结果：行表l删除、结构初始化操作和删除操作通用于所有类型的数据结构。参数l必须是两个操作中基于参考的参数，加工操作：是更改线型表结构的操作，参数l是参照传递方法ClearList(表长度减去1，参照操作3360是不更改线型表结构的操作列表空(l)列表长度(l) getelem (l，)附注：将AB标记为“行表”，从而行表组合基本工作思想：逐个访问b的元素。如果不在a中，则a问题：参考插入位置更改注释比较，voidUnion(List/后缀插入，示例2-2La和Lb中的元素不停机，转换回行表Lc，idea :初始化Lc，设置ijk 3光标，ij分别设置La和剩下的部分是什么？问题：使用边界3光标移动参照、voidmergelist (list la，list lb，list、2.2线性表的顺序表示和实现，1顺序表：表示使用内存中元素的“相邻”关系存储的线性表数据元素之间的关系。此储存的定线表格称为顺序表格。说明：顺序表元素存储在连续存储设备中。实际上对应于数组。根据第一个地址随机访问元素缺点的简单实现。插入或删除元素会移动表格结尾以外的许多资料元素。对于长度变化很大的线性表，必须一次分配足够的存储空间，但这些空间通常不能得到充分利用。顺序表格的容量扩充更复杂，定义2个顺序表格储存结构，定义typedefElemType * SqList的问题(1)表长度不固定，最大长度取决于问题，如何初始化？定义LIST_INIT_SIZE和LISTINCREMENT的动态分配，单位sizeof(ElemType)(2)如何区分元素和备用存储空间？成员变量length简介？设定结束标签？(3)插入元素时，何时需要增加连接的列表存储容量？引入成员变量listsize表示当前容量，/线性表中的动态分配顺序存储结构# definedlist _ init _ size 100/初始容量# definelistincrement 10/空间增量typedef-嗯？-嗯？-嗯？ElemTypeTypedefstruct ElemType * elem/存储空间基本地址intlength/表格长度，元素数intlistsize/表容量，空间大小 SqListLa.elem是阵列名称、La.length表格长度、3基本作业(initlist _ sq、status init list _ Sq(sqlist /init list)移动顺序表要长，不要忘记更改最坏的复杂性O(n)；好O(1)平均移动：listinsert _ sq、status list insert _ sq(sqlist /list insert _ sq、表范围判断和处理差异指针方法以及下标最佳O(1)平均移动：locate elem _ sq，intlocalelem _ sq (sqlistl，elemtype e，status (* compare)/p指向第一个元素inti=1。/i始终是p指向的元素的位顺序：while(in时间n，复杂性为o (n) */，listinsert _ l，status listinsert _ l(link list /复杂性为O(n)，与SqList一起插入表头的复杂性如何，2，1，ListDelete_L/详细信息与教材不同。statuslistdelete _ l(link list /list delete _ l，找到i-1节点。I不合理。如何在不忘记插入其他节点的情况下释放节点的无头节点？1，2、复习：作业和缺勤情况：数学课-程子强高彦韩建康李凤山6月梁王黄杨建州光良李春香统计课-刘广东王子奇李赵臣刘翠翠并发分析算法时间复杂性任务：编写实现22进退刀节点的单个链接列表的函数。同时分析算法的时间复杂性，CreateList_L/反向创建n节点链接表，statusreatelist _ l(插入到linklist/标头中 /create list _)如何考虑页脚插入？总时间复杂度O(n)单链路列表位置反向？mergelist _ l，voidmergelist _ l (linklist，idea :分别浏览La和Lb的元素，比较当前指向的两个元素，将Lc的PC位置插入较小的位置，时间复杂性O 改进自学习：可以根据任务特性修改单链路表结构(例如，引入双向链路表以方便前期工作，引入尾指针和循环链路表以方便页脚操作，添加表长成员和尾指针等实用的改进结构定义)，循环链路表如何确定到达表末尾？ 合并连接列表，P35-2.3.2循环和尾部指针，R2、R1、p=R2-next等易于从头到尾工作的连接列表定义中经常设置尾部指针。R2-next=R1-next；R1-next=p；free(R2-next)；typedefstruct LinkListhead/头指针LinkListtail/尾部指针 CircularLinkListCircularLinkListCLCL.tail-next=CL.head？2.3.3双向(循环)连结图纸double linked (circular) list，/线性图纸的双向(循环)连结表格储存结构-typedefstructdulnode elemtype datateStructDuLNode * priorStructDuLNode * nextDuLNode，* DuLinkList/双向链接列表有助于访问以前的节点，并查看分析复杂性的提高。、ListInsert_DuL(/确定插入位置s=(du lnode *)malloc(size of(du lnode)；s-data=e；s-prior=p；s-next=p-next；p-next-prior=s；p-next=s；status listinsert _ dul(dulin klist /list delete _ dul，从引导节点的双向链路表中删除节点，(1)p-prr(2)p-next-prior=p-prior；(3)自由(p)；P=null，status listdelete _ dul(dulin klist /list delete _ dul，list delete _ dul)*Link、*Position/Link和Position是指向LNode的指针类型typedefstructLinkhead，tail/分别指向头节点和尾节点的指针intlen LinkList/链存储结构的线性表格类型LinkListLa，Lb，Lc；/基于上述增强的单个链接表格存储结构添加仅页眉和页脚操作，可以提高故障排除的效率。选择特定任务和实施。FTP中增强的单个链接列表代码、课件最终选择部分的相关内容、实际应用程序启动增强的单个链接列表、引入尾部指针以轻松查找长表成员：基本操作：节点类操作StatusMakeNode(链接、初始化结构和删除结构类操作StatusInitList(Positionpriorpos (linklist l，linkp)；/p返回以前的位置，o (n) positionnextos (linklist l，linkp)。/o (1)使用statuslocatepos (link list l，inti，link/p返回第一个节点的位置，O(n)positionlocateelem(link list l)q(x)=x x x 50000 r(x)=1 x 3x 1000 x 20000 x 50000数学模型：仅保留系数非零的项目，以避免浪费空间；p=(1，0)，(3，1000)，(.m，m=0，TermSet中的元素包含一个表示系数的实数和一个表示指数的整数数据关系：r=| ai-1，ai-72d，并且ai-1的指数值小于ai的指数值，则i=2.n默认任务： 仅包含ADTPolynomial/示意图，如果确实需要调查，则CreatePolyn(intex pn； termTypedeftermElemTypeTypedeflinklistpolyail，示例2-4抽象数据类型Polynomial实现，/实施某些基本操作-statusreatepolyyn(Polynomial /createpolynt(n)=o(n)返回相似的单个链接列表，idea :设置两个指针QA和QB分别通过Pa和Pb，如果不是空的，则比较当前的两个，三个情况：之一，如果其中一个Pa的索引较小，则在QA后移动一个项目。第二，两个指数相同，系数加起来等于0，从和多项式Pa中删除项目(必须预先设置指针prea)，释放Pb的当前项目(已预先设置指针preb)。如果指数相等系数非零，则修改当前Pa条目的系数值并释放Pb的当前节点。3，如果Pb中间指数较小，则获取Pb的当前条目，并将其插入到Pa的当前条目之前。选择voidAddPoly(Polynomial)，课程设计，练习题到第2、3、6、7章相应的练习题中的至少一个作为课程设计标题。课程设计需要购买特别课程设计手册(非考试报告)、教材销售、课程设计编写规格和考试集样本。一般而言，(1)需求分析：包括问题的重新说明、问题解决思路、问题和重点分析及测试方法和