线性表及其实现

多项式的表示（以一元多项式为例）

• 一元多项式：

• 顺序存储结构直接表示

  • 含义：每个数组元素蕴含两个信息：该元素的值表示系数 ，该元素的下标表示指数 ，数组各元素对应于多项式的各项。

  • 例子： 表示为数组 a = [1, 0, -3, 0, 0, 4]

  • 运算：两个多项式相加，即两个数组对应分量相加

  • 问题：需要利用大量连续空间，如果多项式的非零项较少，则造成大量空间浪费

  • 思考：剔除所有值为0的分量，只表示非零项

• 顺序存储结构表示非零项

  • 含义：将一个多项式看做一个 二元组的集合。用结构数组（数组内每个元素都是一个由 组成的结构）表示，每个分量对应一个非零项。

  • 例子：

    

    a[0]	a[1]	a[2]	a[3]
    9	15	3	82
    12	8	2	0

  • NOTE: 为了运算方便，必须按照 指数大小 进行有序存储

  • 运算：两个多项式相加时，应从头开始，比较当前对应项的指数，指数较大的项在前、较小的在后

• 链表存储结构表示非零项

  • 含义：每个结点存储多项式中一个非零项，结点包括系数、指数两个数据域及一个指针域

  • 结点的定义

    typedef struct PolyNode *Polynomial;
    struct PolyNode {
        int coef;
        int expon;
        Polynomial link;
    }
    

抽象数据类型描述

• 数据对象：

• 数据关系：

• 操作集

  • InitList()：初始化一个空表

  • DestroyList(): 销毁线性表

  • ClearList(): 重置为空表

  • ListEmpty(): 检测是否为空表

  • ListLength(): 获取表中元素个数

  • GetElem(): 返回表中第 i 个元素的值

  • LocateElem(): 返回表中第一个与e值相等的元素的位序

  • PriorElem()：返回前驱元素

  • NextElem()：返回后继元素

  • ListInsert()：在第 i 个位置之前插入新的数据元素 e

  • ListDelete()：删除第 i 个元素，并返回其值

  • ListTraverse(): 遍历线性表中各元素

线性表的顺序存储实现

• 线性表的定义

  typedef struct {
      ElemType *elem; //  存储空间基址(首地址)，相当于分量类型为ElemType的数组
      int length;     //  元素个数
      int list_size;  //  当前分配的存储量
  } SqList;
  

• 主要操作集的实现

线性表的链式存储实现

• 线性表的定义

  typedef struct {
      ElemType data;
      struct LNode *next;
  } LNode,  *Link;    // Link为指针，指向类型为 LNode 的结点
  
  typedef struct {
      Link head, tail;
      int length;
  } LinkList;
  

• 主要操作集的实现