数据结构与算法课件：线性表.ppt

位置值与指针的转换插入新元素删除元素赋值、取值查找例2-9返回指针curr指向结点的位置效率分析如果给定了当前指针，则插入操作和删除操作的时间复杂度均为O(1)判定链表是否为空的时间复杂度也为O(1)清空表操作的时间复杂度是O(n)求表长，两种实现分别是O(1)和O(n)查找操作的时间复杂度是根据查找目标在链表中的位置而定的最优情况下为O(1)最坏的情况下为O(n)平均来看是O(n)查找失败是O(n)循环链表修改单链表的定义，将表尾结点的指针指回头结点，从而形成一类新链表这样的链表中，从任何一个结点出发沿着指针域的指示可以再回到这个结点，好象转了一个圈一样，形象地称这样的链表为循环链表双向链表双向链表中，表结点及链表的定义typedefintELEMType;typedefstructnode{ //双向链表结点 ELEMTypedata; structnode*next; //指向后继结点 structnode*prev; //指向前驱结点}DouLinkNode;typedefDouLinkNode*DouLinkList; //双向链表typedefintPosition;双向链表双向链表的初始化辅助函数setCurr插入新元素删除元素双向循环链表例2-11在双向循环链表中，在指针p所指向的结点（非尾结点）之后插入指针s指向的结点，下列选项中，正确的修改指针的语句序列是（）。A．p-next=s;s-prev=p;p-next-prev=s;s-next=p-next;B．p-next-prev=s;p-next=s;s-prev=p;s-next=p-next;C．s-prev=p;s-next=p-next;p-next=s;p-next-prev=s;D．s-prev=p;s-next=p-next;p-next-prev=s;p-next=s;答案是D。第四节进一步讨论两种基本实现方式线性表有两种基本的实现方式，分别是顺序实现和链式实现简单地说，这两种实现方式各有优势。在不同的情况下，对应于不同的操作，某一种方式可能会优于另外一种。但是哪种方式都不能适用于所有情况示例将下列特性对应到顺序表和链表中，对号入座A．逻辑上相邻的元素，在内存中的存储位置也相邻B．不必事先估计存储空间C．所需空间与元素个数成正比D．插入、删除时不需要移动元素E．支持随机存取F．支持顺序存取顺序表具有的特性有：A、E和F链表具有的特性有：B、C、D和F对比存储每个数据元素时空间比较紧凑，并且是占用连续的空间数组的每个单元中只需要保存数据本身，没有额外的开销链表在每个结点上除存储数据元素外，还要留出空间存放指针。单链表中每个结点包含一个指针，双向链表中每个结点包含两个指针。这些指针占用的空间称为结构性开销为顺序表分配的数组，通常要宽松一些。通常数组中会有空闲的空间，此时并没能充分利用数组的全部空间链表中占用的空间大小与链表中的元素个数成正比，分配的结点是全部使用的当线性表的元素个数相对较少时，链表的实现比顺序表的实现更节省空间当线性表中的元素个数接近分配的最大个数，数组的空间存储效率很高设n表示线性表中当前元素的个数，D表示最多可以在数组中存储的元素个数，也就是数组的大小，P表示指针的存储单元大小，E表示数据元素的存储单元大小顺序表的空间需求为D?E单链表的空间需求为n?(P+E)n的临界值n=D?E/(P+E)双向链表比单链表中每个结点的指针数多1个。所以双向链表的结构性开销是单链表的2倍顺序表的显著特点?分配了数组空间后，将线性表中的n个元素依次保存在数组中，从表头至表尾的各个元素分别对应下标0到下标n-1的位置数组是内存中一片连续的空间，相邻的两个单元在内存中的实际地址也是相邻的，这表明，线性表中逻辑上相邻的两个元素，其存储地址也是相邻的存储示意图假设线性表L=(a0,a1,a2,a3,a4,a5)，每个元素需要占用2个字节，分配一个含8个元素的数组A保存LA在内存中的示意图数组下标与线性表元素的位置相对应线性表元素依次存放的特性，决定着表中元素i（i≥0）存储在数组的下标i处表头元素保存在位置0处，这个位置也称为数组的首地址只要给定数组下标，就能立即计算出相应元素的存储地址，并据此访问该元素地址计算?设LOC(ai)表示元素ai的存储首地址，每个元素需占用d个存储单元，则有 LOC(ai)=LOC(ai-1)+d进一步地有 LOC(ai)=LOC(a0)+i?dLOC(a0)即是数组