算法与数据结构-线性表第2章3.pptVIP

2.4线性表实现方法的比较 对于线性表的逻辑结构有两种存储结构：顺序表和链表。 实现不同 顺序表方法简单，各种高级语言中都有数组类型，容易实现； 链表的操作是基于指针的，相对来讲复杂些。 存储空间的占用和分配不同 从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。 而链表是动态分配存储空间的，不用事先估计存储规模。可见对线性表的长度或存储规模难以估计时，采用链表。 线性表运算的实现不同 按序号访问数据元素，使用顺序表优于链表。 插入删除操作 ，使用链表优于顺序表。 2.5其他形式的链表一、循环链表 循环链表（Circular Linker List） 是单链表的另一种形式,它是一个首尾相接的链表。 它的特点是表中最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，整个链表形成一个环，构成单循环链表。 其特点： 从表中任意结点出发均可找到表中其它结点。 单循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。 有的时候，在循环链表中设立尾指针而不设立头指针，使某些操作简化。 例如将两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相接。 语句段如下： p= R1–next; //保存L1 的头结点指针 R1-next=R2-next-next;//头尾连接 free(R2-next); //释放第二个表的头结点 R2-next=p; 若不设置尾结点，则算法时间复杂度为O(m+n);设置尾结点，算法时间复杂度为O(1) 二、双链表 在单链表中，求后继的执行时间为O(1)，而求前驱的执行时间为O(n)。 双(向)链表(Double Linked List)：每个结点有两个指针域，其中一个指向直接后继，另一个指向直接前驱，用语言可描述如下： typedef struct DNode { ElemType data； /*数据域*/ struct DNode *prior，*next； /*指针域*/ }DNode, *DoubleList； 在双向链表中，若p为指向表中某一结点的指针，则显然有： p-next-prior=p-prior-next=p 这个表达式恰当的反映了这种结构的特性。 在双向链表中，有些操作如：Length、Get、和Locate等仅需涉及一个方向的指针，则它们的算法和线性表的操作相同，但在插入、删除是有很大的不同. 双向链表的插入 双向链表的删除 习题 1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 ______ 个元素。N-i+1 ?? 3. 在顺序表中访问任意一结点的时间复杂度均为 ___n___，因此，顺序表也称为 ____随机存取____的数据结构。 ? 4.顺序表中逻辑上相邻的元素的物理位置 ___也___相邻。单链表中逻辑上相邻的元素的物理位置 ___不____相邻。 5.在单链表中，除了首元结点外，任一结点的存储位置由 ____前驱______指示。 ? 6． 在n个结点的单链表中要删除已知结点*p，需找到它的____前驱______，其时间复杂度____n___。 （0 ）1. 链表的每个结点中都恰好包含一个指针。 （0 ）2. 链表的物理存储结构具有同链表一样的顺序。 （0 ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （0 ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （0 ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （0 ）7. 线性表在物理存储空间中也一定是连续的。 （0 ）8.线性表的链式存储结构优于顺序存储结构。 1．数据结构的一个结点代表一个（A） （A）数据元素 （B）数据项 （C）数据 （D）数据元素 2.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：C （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 （ B ）3.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120? （ C ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素 （A）8 （B）63.5 （C）63