• 線性表及其實現
  • • 多項式的表示
    • 什么是線性表
    • 線性表的抽象數據類型描述
    • 線性表的順序存儲實現
    • 線性表的鏈式存儲實現

線性表及其實現

多項式的表示

[例] 一元多項式及其運算
一元多項式 ：
主要運算：多項式相加、相減、相乘等
【分析】如何表示多項式?
多項式的關鍵數據：
多項式項數n
各項系數ai 及指數 i
方法1：順序存儲結構直接表示
數組各分量對應多項式各項： a[i]: 項xi的系數ai

方法2：順序存儲結構表示非零項

按指數大小有序存儲！
相加過程：從頭開始，比較兩個多項式當前對應項的指數

方法3：鏈表結構存儲非零項

什么是線性表

多項式表示問題的啟示：
1. 同一個問題可以有不同的表示（存儲）方法
2. 有一類共性問題：有序線性序列的組織和管理
線性表(Linear List) : 由同類型數據元素構成有序序列的線性結構
1.表中元素個數稱為線性表的長度
2.線性表沒有元素時，稱為空表
3.表起始位置稱表頭，表結束位置稱表尾

線性表的抽象數據類型描述

類型名稱：線性表（List）

數據對象集：線性表是 n (≥0)個元素構成的有序序列( a1, a2,… ,an )

操作集：線性表L屬于 List，整數i表示位置，元素X 屬于 ElementType， 線性表基本操作主要有：

1、List MakeEmpty()：初始化一個空線性表L；
2、ElementType FindKth( int K, List L )：根據位序K，返回相應元素 ；
3、int Find( ElementType X, List L )：在線性表L中查找X的第一次出現位置；
5、void Delete( int i, List L )：刪除指定位序i的元素；
6、int Length( List L )：返回線性表L的長度n。

線性表的順序存儲實現

利用數組的連續存儲空間順序存放線性表的各元素

主要操作的實現

typedef int Position; typedef struct LNode *List; struct LNode {ElementType Data[MAXSIZE];Position Last; };/* 初始化 */ List MakeEmpty() {List L;L = (List)malloc(sizeof(struct LNode));L->Last = -1;return L; }/* 查找 */ #define ERROR -1Position Find( List L, ElementType X ) {Position i = 0;while( i <= L->Last && L->Data[i]!= X )i++;if ( i > L->Last ) return ERROR; /* 如果沒找到，返回錯誤信息 */else return i; /* 找到后返回的是存儲位置 */ }/* 插入 */ /*注意:這里P是存儲下標位置（從0開始）*/ bool Insert( List L, ElementType X, Position P ) { /* 在L的指定位置P前插入一個新元素X */Position i;if ( L->Last == MAXSIZE-1) {/* 表空間已滿，不能插入 */printf("表滿"); return false; } if ( P<0 || P>L->Last+1 ) { /* 檢查插入位置的合法性 */printf("位置不合法");return false; } for( i=L->Last; i>=P; i-- )L->Data[i+1] = L->Data[i]; /* 將位置P及以后的元素順序向后移動 */L->Data[P] = X; /* 新元素插入 */L->Last++; /* Last仍指向最后元素 */return true; } /* 刪除 */ /*注意:這里P是存儲下標位置（從0開始）/ bool Delete( List L, Position P ) { /* 從L中刪除指定位置P的元素 */Position i;if( P<0 || P>L->Last ) { /* 檢查空表及刪除位置的合法性 */printf("位置%d不存在元素", P ); return false; }for( i=P+1; i<=L->Last; i++ )L->Data[i-1] = L->Data[i]; /* 將位置P+1及以后的元素順序向前移動 */L->Last--; /* Last仍指向最后元素 */return true; }

線性表的鏈式存儲實現

不要求邏輯上相鄰的兩個元素物理上也相鄰；通過“鏈”建 立起數據元素之間的邏輯關系。
插入、刪除不需要移動數據元素，只需要修改“鏈”。
訪問序號為 i 的元素？ 求線性表的長度？

int Length ( List PtrL ) { List p = PtrL; /* p指向表的第一個結點*/ int j = 0; while ( p ) { p = p->Next; j++; /* 當前p指向的是第 j 個結點*/ } return j; } typedef struct LNode *PtrToLNode; struct LNode {ElementType Data;PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List;/* 查找 */ #define ERROR NULLPosition Find( List L, ElementType X ) {Position p = L; /* p指向L的第1個結點 */while ( p && p->Data!=X )p = p->Next;/* 下列語句可以用 return p; 替換 */if ( p )return p;elsereturn ERROR; }/* 帶頭結點的插入 */ /*注意:這里P是鏈表結點指針，在P之前插入新結點 */ bool Insert( List L, ElementType X, Position P ) { /* 這里默認L有頭結點 */Position tmp, pre;/* 查找P的前一個結點 */ for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; if ( pre==NULL ) { /* P所指的結點不在L中 */printf("插入位置參數錯誤\n");return false;}else { /* 找到了P的前一個結點pre *//* 在P前插入新結點 */tmp = (Position)malloc(sizeof(struct LNode)); /* 申請、填裝結點 */tmp->Data = X; tmp->Next = P;pre->Next = tmp;return true;} }/* 帶頭結點的刪除 */ /*注意:在刪除位置參數P上與課程視頻有所不同，課程視頻中i是序列位序（從1開始），這里P是擬刪除結點指針 */ bool Delete( List L, Position P ) { /* 這里默認L有頭結點 */Position tmp, pre;/* 查找P的前一個結點 */ for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; if ( pre==NULL || P==NULL) { /* P所指的結點不在L中 */printf("刪除位置參數錯誤\n");return false;}else { /* 找到了P的前一個結點pre *//* 將P位置的結點刪除 */pre->Next = P->Next;free(P);return true;} }

廣義表(Generalized List)
廣義表是線性表的推廣
對于線性表而言， n個元素都是基本的單元素；
廣義表中，這些元素不僅可以是單元素也可以是另一個廣義表

多重鏈表：
鏈表中的節點可能同時隸屬于多個鏈
多重鏈表中結點的指針域會有多個，如前面例子包含了Next和 SubList兩個指針域；但包含兩個指針域的鏈表并不一定是多重鏈表，比如在雙向鏈表 不是多重鏈表。
多重鏈表有廣泛的用途： 基本上如樹、圖這樣相對 復雜的數據結構都可以采 用多重鏈表方式實現存儲。

矩陣可以用二維數組表示，但二維數組表示有兩個缺陷：
數組的大小需要事先確定，對于“稀疏矩陣 ”，將造成大量的存儲空間浪費
采用一種典型的多重鏈表——十字鏈表來存儲稀疏矩陣
只存儲矩陣非0元素項結點的數據域：行坐標Row、列坐標Col、數值Value
每個結點通過兩個指針域，把同行、同列串起來;
行指針(或稱為向右指針)Right
列指針（或稱為向下指針）Down

用一個標識域Tag來區分頭結點和非0元素結點：
頭節點的標識值為“Head”，矩陣非0元素結點的標識值為“Term”。

總結

以上是生活随笔為你收集整理的线性表总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。