数据结构(C语言版)线性表.ppt

图2.13 循环链表 2.3.4 双向链表 循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗费是O(n) 。如果希望从表中快速确定某一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域prior。这样形成的链表中就有两条方向不同的链，我们可称之为双(向)链表(Double Linked List)。双链表的结构定义如下 typedef?struct?DulNode{????? ElemType??data; ????? struct?DulNode??*prior,?*next; }DulNode,*DuLinklist; 图2.14 双链表的结点结构 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：  p-prior-next = p = p-next-prior 图2.15 双向循环链表图示 1. 双向链表的前插操作 图2.16 双向链表插入操作 2. 双向链表的删除操作 算法描述： 图2.17 双向链表的删除操作 链表的运算效率分析 1. 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 时间效率分析 2. 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n)。 顺序表和链表的比较 1. 基于空间的考虑 在链表中的每个结点，除了数据域外，还要额外设置指针（或光标）域，从存储密度来讲，这是不经济的。所谓存储密度(Storage Density), 是指结点数据本身所占的存储量和整个结点结构所占的存储量之比， 即 存储密度=结点数据本身所占的存储量/结点结构所占的存储总量 一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。例如单链表的结点的数据均为整数，指针所占空间和整型量相同，则单链表的存储密度为50%。因此若不考虑顺序表中的备用结点空间，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50%。由此可知，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。 2. 基于时间的考虑 顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O(1)时间内直接地存取，而链表中的结点，需从头指针起顺着链找才能取得。因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。 在链表中的任何位置上进行插入和删除，都只需要修改指针。而在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。因此，对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。 3. 基于语言的考虑 对于没有提供指针类型的高级语言，若要采用链表结构， 则可以使用光标实现的静态链表。虽然静态链表在存储分配上有不足之处，但它和动态链表一样，具有插入和删除方便的特点。  值得指出的是，即使是对那些具有指针类型的语言，静态链表也有其用武之地。特别是当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。 2.4 一元多项式的表示及相加 对于符号多项式的各种操作，实际上都可以利用线性表来处理。比较典型的是关于一元多项式的处理。在数学上，一个一元多项式Pn(x)可按升幂的形式写成： 它实际上可以由n+1个系数唯一确定。因此，在计算机内， 可以用一个线性表P来表示： 假设Qm(x)是一个一元多项式， 则它也可以用一个线性表Q来表示， 即 若假设mn，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)， 也可以用线性表R来表示： 我们可以采用顺序存储结构来实现顺序表的方法，使得多项式的相加的算法定义十分简单，即p[0]存系数p0，p[1]存系数p1, …, p[n]存系数pn，对应单元的内容相加即可。但是在通常的应用中，多项式的指数有时可能会很高并且变化很大。例如： 若采用顺序存储，则需要20001个空间，而存储的有用数据只有三个，这无疑是