資料結構—線性結構—線性及其實作

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;
}