線性表及其實現(xiàn)

多項式的表示（以一元多項式為例）
- 一元多項式： $f(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n$
- 順序存儲結(jié)構(gòu)直接表示
  - 含義：每個數(shù)組元素蘊含兩個信息：該元素的值表示系數(shù) $a_i$ ，該元素的下標表示指數(shù) $i$ ，數(shù)組各元素對應(yīng)于多項式的各項。
  - 例子： $f(x)=4x^5-3x^2+1$ 表示為數(shù)組 a = [1, 0, -3, 0, 0, 4]
  - 運算：兩個多項式相加，即兩個數(shù)組對應(yīng)分量相加
  - 問題：需要利用大量連續(xù)空間瑟啃，如果多項式的非零項較少，則造成大量空間浪費
  - 思考：剔除所有值為0的分量揩尸，只表示非零項
- 順序存儲結(jié)構(gòu)表示非零項
  - 含義：將一個多項式看做一個 $(a_i, i)$ 二元組的集合蛹屿。用結(jié)構(gòu)數(shù)組（數(shù)組內(nèi)每個元素都是一個由 $\{a_i, i\}$ 組成的結(jié)構(gòu)）表示，每個分量對應(yīng)一個非零項岩榆。
  - 例子：
    
    $P_1(x)=9x^{12}+15x^8+3x^2+82$
    
    a[0] a[1] a[2] a[3]
    
    9 15 3 82
    
    12 8 2 0
  - NOTE: 為了運算方便错负，必須按照 指數(shù)大小 進行有序存儲
  - 運算：兩個多項式相加時，應(yīng)從頭開始勇边，比較當前對應(yīng)項的指數(shù)犹撒，指數(shù)較大的項在前、較小的在后
- 鏈表存儲結(jié)構(gòu)表示非零項
  - 含義：每個結(jié)點存儲多項式中一個非零項粥诫，結(jié)點包括系數(shù)油航、指數(shù)兩個數(shù)據(jù)域及一個指針域
  - 結(jié)點的定義
```
typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int expon;
    Polynomial link;
}
```
抽象數(shù)據(jù)類型描述
- 數(shù)據(jù)對象： $D=\{a_i | a_i\in ElemSet, i=1,2,...,n, n>=0\}$
- 數(shù)據(jù)關(guān)系： $R1=\{\langle a_{i-1},a_i\rangle | a_{i-1}, a_i \in D, i=2,...,n\}$
- 操作集
  - InitList()：初始化一個空表
  - DestroyList(): 銷毀線性表
  - ClearList(): 重置為空表
  - ListEmpty(): 檢測是否為空表
  - ListLength(): 獲取表中元素個數(shù)
  - GetElem(): 返回表中第 i 個元素的值
  - LocateElem(): 返回表中第一個與e值相等的元素的位序
  - PriorElem()：返回前驅(qū)元素
  - NextElem()：返回后繼元素
  - ListInsert()：在第 i 個位置之前插入新的數(shù)據(jù)元素 e
  - ListDelete()：刪除第 i 個元素，并返回其值
  - ListTraverse(): 遍歷線性表中各元素

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

線性表的順序存儲實現(xiàn)

線性表的定義

typedef struct {
    ElemType *elem; //  存儲空間基址(首地址)怀浆，相當于分量類型為ElemType的數(shù)組
    int length;     //  元素個數(shù)
    int list_size;  //  當前分配的存儲量
} SqList;

主要操作集的實現(xiàn)

線性表的鏈式存儲實現(xiàn)

線性表的定義

typedef struct {
    ElemType data;
    struct LNode *next;
} LNode,  *Link;    // Link為指針，指向類型為 LNode 的結(jié)點

typedef struct {
    Link head, tail;
    int length;
} LinkList;

主要操作集的實現(xiàn)

最后編輯于：2019.10.19 15:58:11

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者