数据结构—线性结构—线性及其实现

2.1线性及其实现

一、如何表示多项式

方法1：顺序存储结构直接表示

这个方法用了一个数组，把数组的对应系数存了起来。这个方法的优点是：多项式相加比较好算，缺点是：下面要表示2000次的时候，要一个2001大的数组，显然是巨大的浪费。

方法2：顺序存储结构表示非零项

特点，只表示非零向量。每个非零向量有两个信息，系数和指数，所以可以将一个多项式看成是一个（ai, i ）二元组的集合。

用结构数组表示：数组分量有系数、指数组成的结构。对应一个非零项。

这样表示运算方便吗？要有序进行存储。

两个多项式相加。也不一定要用数组来做，也可以用链表

方法三：链表结构存存储非零项

链表中每个结点存储多项式中的一个非零项，包含洗漱和指数两个数据域以及一个指针域。

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

存储的形式为

存储方法，要么数组，要么链表

什么是线性表？

定义：有同类型数据元素构成有序序列的线性结构。

- 表中元素个数成为线性表的长度。

- 线性表没有元素时，称为空表。

- 表起初位置成为表头，表结尾称为表尾。

线性表的抽象数据类型

线性表的存储方法：线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素。

使用以下结构表示线性表

typedef struct{
    ElementType Data[MAXSIZE];
    int Last;         /*线性表的最后一个元素，见上图*/
}List;
List L,*PtrL;
           

访问一个下标为i的元素： L.Data[i] 或者是 Ptrl->Data[i]

线性表的长度 ：L.Last +1 或者是 Ptrl->Last +1

操作集的实现

1.初始化（建立空的顺序表（表的表示呢，是由结构来表示的，它包含数组，还有最后一个Last，所以呢，申请一个结构））

List *MakeEmpty(){      //
    List *PtrL;
    PtrL = (List *)malloc(sizeof(List))
    PtrL->Last = -;       /* last=0 表示数组的第一个元素，没有呢，就赋值给-1了。*/
    return PtrL;    /*然后把结构的指针返回回去*/
}
           

2、查找

PtrL线性表结构的指针，我们要找X所在的位置，可以通过一个循环来实现

int Find (ElementType X,List *Ptrl){
    int i = ;
    while(i<=Ptrl->Last && Ptrl->Data[i] != X )
        i++;
    if(i > Ptrl -> Last ) return -;   大也只能大一个
    else return i;
}
           

所以这个查找成功的平均比较次数为（n + 1）/ 2 ，平均时间性能为O( n )。

3、插入：在第i个位置之前 插入一个值为X的新元素。

要插入，先移动，后插入，数组长度有5的时候，里面存有01234 这5个元素，MAXSIZE 是5；但是Ptrl->List是4 ，在顺序表L中第i个数据元素之前插入一个元素，插入前表长：L->last+1，

位置 i 是从1开始的，数组下标是从0开始的，L->last返回的是数组下标，第i个元素是Data[i-1]

void insert(ElementType X , int  i, List *Ptrl){
    int j;
    if( Ptrl->Last  > MAXSIZE -  ){
        printf("表满"); return;
    }
    if( i <  || i > Ptrl->Last + ){  /* i=1表示是在第一个元素之前插入数据。 i=Ptrl->Last +2 表示在数组最后一个元素的后面插入。*/
        printf("位置不合法"); return;
    }
    for(j = Ptrl->Last;j>=i- ;j-- )
        Ptrl->Data[j+] = Ptrl->Data[j];
    Ptrl->Data[i-] = X;
    Ptrl->Last++;
    return;
}
           

线性表的链式存储实现：不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。插入和删除不需要移动数据元素，只需要修改“链”

1、求表长

int length(List *Ptrl){
    List *p = Ptrl；
    int j = ;
    while (p ){
        p = p->Next;
        j++;
    }
}
           

2、查找

（1）按序号查找：FindKth

List *FindKth(int k,List *Ptrl){
    List *p=Ptrl;
    int i = ;
    while(p!=null&& i<k){
        p=p->Next;
        j++;
    }
    if(i = k) return p;
    else return NULL;
}
           

（2）按序号查找：Find 根据元素

List *Find(ElementType x,List *Ptrl){
    List *p=Ptrl;
    while(p!=null&& p->Data != x ){
        p=p->Next;
    }
    if(p->Data == x ) return p;
    else return NULL;
}