线性结构

          ——线性表示及其实现

一.多项式的表示（项数n和各项系数 ，指数i）

     法一：顺序存储结构直接表示——数组各分量对应多项式各项，a[i]: 项的系数

           eg:          

下标i	0           1             2         3               4            5     .......
a[i]	1	0	-3	0	0	4

    法二：顺序存储结构表示非零项——将一个多项式看成是一个（,i）二元组集合，用结构数组表示，数组分量是由系数和指                                                                数i 组成的结构 ，对应一个非零项

下标i	0                    1                      2                   ......
系数	4	-3	1
指数i	5	2	0

                  * 按指数大小有序存储

     法三：链表结构存储非零项 —— 链表中每个结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域

系数

指数

指针（link）

    eg：   

二.什么是线性表？

    由同类型数据元素构成的有序序列的线性结构

  1.  抽象数据类型描述——  类型名称：线性表（List ）

                                      数据对象集：线性表是n个元素构成的有序序列

                                              操作集：,整数i表示位置，元素，基本操作主要有：

                                                         1.ListMakeEmpty()：初始化一个空线性表L    

                                                         2.ElementTyp FindKth(int K,list L):根据位序    K，返回相应元素

                                                         3. int Find(ElementType X,List L):  在线性表L中查找X第一次出现的位置

                                                         4.Void Insert（Element Type X，int i,List L）:在位序i前 插入一个新元素X                 

    2. 顺序存储实现：利用数组的连续存储空间顺序存放线性表的各元素

       访问下标为i的元素：L.Data[i] 或者 Ptrl->Data[i]                  线性表长度：L.Last+1 或者 Ptrl->Last+1

      3. 链式存储实现：不要求逻辑上相邻的两个元素物理上也相邻，通过链建立起数据元素之间的逻辑关系。

    

                         

 3. 广义表

             

广义表示线性表的推广，线性表元素为单元素，对于广义表，元素也可以是广义表

多重链表：节点可能隶属于多个链  

 eg:  稀疏矩阵的链表表示   :只存储非零元素项，每个结点通过两个指针域把同行同列串起来