课件2线性表讲述.ppt

2.3.3 循环链表 L-next=L (a) 非空单循环链表 L (b) 空表 L 2.3.4 双向链表 Λ Λ a1 a2 ...... 双链表： head 空链表： head 双向链表的插入 1. s-prior=p-prior; 双向链表的插入 a b x ... ... 1 p s 双向链表的插入 1. s-prior=p-prior; 2. p-prior-next=s; a b x ... ... 1 2 p s 双向链表的插入 1. s-prior=p-prior; 2. p-prior-next=s; 3. s-next=p; 双向链表的插入 4. p-prior=s; a b x ... ... 1 2 3 4 p s 1. s-prior=p-prior; 2. p-prior-next=s; 3. s-next=p; 双向链表的删除 1. p-prior-next=p-next; 双向链表的删除 双向链表的删除 1. p-prior-next=p-next; 2. p-next-prior=p-prior; 2.3.5 双向循环链表 (a) 空双向循环链表 (b) 双向循环链表 （1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻 链表（链式存储结构）的特点 （2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等 　这种存取元素的方法被称为顺序存取法 优点 数据元素的个数可以自由扩充 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高 链表的优缺点 缺点 存储密度小 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜） 链表的优缺点 2.4 　线性表的应用 Josephus问题 2 有序表的合并 3 多项式的表示及其计算 Josephus问题 问题描述： n个小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩就离开，小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。究竟胜利者是第几个小孩呢？ 问题举例： 假设有11个小孩，数到7的小孩离开，那么胜利者是哪个小孩呢？出圈的顺序又是多少？ n=11，m=7。出圈的顺序为：7 3 11 9 8 10 2 6 1 4 5 问题模型： 可以使用长度为n的线性表来存放小孩，位置为m的小孩出线性表。从执行效率考虑，选取链表较为合适。 算法描述：1、根据n和m初始化线性表L 2、while(L不空)输出L中符合条件的元素，并删除 关键问题：删除元素i之后如何寻找下一个元素 a1 ai … ak … … 删除的元素 下一个元素 k与i之间的关系：k=(i+m-1)%length 多项式的表示及其计算 定义：多项式是由变量以及标量（一般是实数或复数）经乘法及加法构法而成，属于整式的代数式。 特点： 1、每一项x 的次幂按顺序递增 2、每一项都含有一个系数 多项式类型表示： 1、使用元素的位置表示次幂 2、系数作为元素内容存放 多项式的类型： Ploy{ int * ratios; int max,size,incresize; } ； 多项式的类型：f（x）=5+4x-8x^2+7x^3 5 4 -8 7 ratios max=3 size 稀疏多项式：多项式中的系数大部分为零 例如：f（x）=5+4x-8x^60 特点：多项式中的大多数项的系数为零 表示：使用有序链表，结点中含系数和次幂 稀疏多项式的表示： struct SparsePolyNode{ int ratio, power; SparsePolyNode *next; }; 稀疏多项式的基本运算： 创建：void SparsePolyCreate(Poly A) 销毁：void SparsePolyDestroy(Poly A) 相加：void SparsePolyAdd (Poly A, Poly B, Poly C) 相乘：void SparsePolyMul (Poly A, Poly B, Poly C) 将两个递增的有序顺序表A、B合并为一个新的递增的有序顺序表C。要求新表C中不允许有重复的数据。 函数声明： void SeqListUnion (SeqList A, SeqLi