《数据结构》--静态链表.pptx

计科系王丹丹第章线性表()静态链表每个下标都对应一个和一个。 数据域:用来存放数据元素。 :存放该元素的后继在数组中的下标。用数组描述的链表叫做静态链表。数据域指针域(结点)数组?datacur下标*线性表的静态链表存储结构*假设链表的最大长度是{ ; ; 游标(),为时表示无指向},[];对数组第一个和最后一个元素作为特殊元素处理,不存数据。备用链表:未被使用的数组元素。图示相当于初始化的数组状态。*将一维数组中各分量链成一备用链表**[]为头指针,“”表示空指针*(){ ; (;<;) []; 目前静态链表为空,最后一个元素的为 []; ;}假设我们已经将数据存入静态链表,比如分别存放着“甲”、“乙”、“丁”、“戊”、“己”、“庚”等数据。静态链表的插入、删除操作丙丙静态链表的插入操作示意图静态链表的删除操作示意图静态链表优缺点在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。优点没有解决连续存储分配带来的表长难以确定的问题; 失去了顺序存储结构随机存取的特性。缺点循环链表循环链表() 将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表。头指针…头指针与单链表的差异在于循环的判断条件单链表:>是否为空。循环链表:>不等于头结点,则循环未结束。循环链表访问最后一个结点访问第一个结点单链表()()有没有可能用()的时间由链表指针访问到最后一个结点?…头指针尾指针终端结点用尾指针指示终端结点:查找时间复杂度();开始结点:>>,时间复杂度为()。例:将两个循环链表合并成一个,有了尾指针就非常简单了。……>>>>