【正文】 Pages: 47 2022/1/4 算法與數(shù)據(jù)結(jié)構(gòu) Algorithms and Data Structures CH2 線性表 +++教授 ***信息技術(shù)大學(xué) 計算機(jī)工程學(xué)院 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動態(tài)存儲管理 提綱 2022/1/4 2/114 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動態(tài)存儲管理 2022/1/4 3/114 線性結(jié)構(gòu)：只有一個開始結(jié)點和一個結(jié)束結(jié)點，所有結(jié)點排成一個線性序列 串、棧、隊列都是線性結(jié)構(gòu) 線性表 （簡稱為表）是零個或多個元素的有窮序列。 L = (k0, k1, …, k n1) 線性表的邏輯結(jié)構(gòu)： L=K, R 其中 K={ k0, k1, …, k n1}， R={ki, ki+1|0≤i≤n2 } i稱為元素 ki的 索引 或 下標(biāo) 基本概念 2022/1/4 4/114 表中所含元素的個數(shù)稱為表的 長度 。 長度為零的表稱為 空表 。 k0稱為 第一個 元素， kn1稱為 最后一個 元素， ki(0≤i≤n2)是 ki+1的 前驅(qū) ， ki+1是 ki的 后繼 。 k0只有一個后繼， kn1只有一個前驅(qū) 2022/1/4 5/114 例 1： 大寫英文字母 ： (A, B, C, D, …, Z) 110的整數(shù)： (1, 2, 3, 4, …, 10) 例 2：某院系的學(xué)生名冊 學(xué)號 姓名 性別 年齡 專業(yè)名稱 …… 09001001 張豐 男 17 信息與計算科學(xué) 09001002 劉小紅 女 18 信息與計算科學(xué) 09001003 李靜 女 18 數(shù)學(xué)與金融工程 09001004 王建平 男 18 數(shù)學(xué)與金融工程 … … … … … …… 2022/1/4 6/114 2022/1/4 7/114 某年南方 GDP排名前 20的城市 同年南方 GDP排名前 20的城市 List：線性表類型 ， DataType：元素類型， Position：元素的下標(biāo)類型。可說明如下 : List list。 DataType x。 Position p。 [注 ]元素的類型與討論無關(guān) 抽象數(shù)據(jù)類 型 (ADT) 2022/1/4 8/114 線性表的抽象數(shù)據(jù)類 型 (ADT) ADT List is operations List createNullList ( void ) //創(chuàng)建并且返回一個空線性表 int insertPre (List list, position p, DataType x) //在 list中 p位置前插入值為 x的元素，并返回插入成功與否的標(biāo)志 int insertPost (List list, position p, DataType x) //在 list中 p位置后插入值為 x的元素，并返回插入成功與否的標(biāo)志 int deleteV (List list, DataType x) //在 list中刪除一個值為 x的元素，并返回插入成功與否的標(biāo)志 2022/1/4 9/114 int deleteP (List list, position p) //在 list中刪除位置為 p的元素，并返回插入成功與否的標(biāo)志。 Position locate (List list, DataType x) //在 list中查找值為 x的元素的位置。 int isNull (List list) //判別 list是否為空線性表。 end ADT List 2022/1/4 10/114 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動態(tài)存儲管理 2022/1/4 11/114 線性表最簡單的存儲方法是采用順序方式，稱作線性表的 順序表示 ，通?？煞Q此時的線性表為 順序表 具體做法是：將線性表中的元素一個接一個地存儲在一片 相鄰的存儲區(qū)域 中。線性表的順序存儲結(jié)構(gòu)是一種可以 隨機(jī)存取 的存儲結(jié)構(gòu)。 2022/1/4 12/114 假設(shè)每個元素占用 c個存儲單元，則下標(biāo)為 i+1的元素的存儲位置與下標(biāo)為 i的元素的存儲位置之間，滿足下列關(guān)系： loc(ki+1) = loc(ki) + c 通常把順序表中 k0的存儲位置 loc(k0)，稱為線性表的 首地址或 基地址 ，下標(biāo)為 i的元素 ki的存儲位置為： loc(ki) = loc(k0) + i * c 存儲結(jié)構(gòu) 2022/1/4 13/114 2022/1/4 14/114 順序表定義 (C語言 )： 2022/1/4 15/114 define MAXNUM 100 DataType element[MAXNUM]。 define MAXNUM 100 int n。 /* 存放線性表中元素的個 n ≤ MAXNUM*/ DataType *element。 /* element[0],element[1]， …， element[n 1]存放線性表中的元素 */ 設(shè) palist是一個指向 SeqList類型的指針變量，則： palistMAXNUM：順序表中最大元素的個數(shù)； palistn：順序表中實際元素的個數(shù)； palistelement[0] ， … ， palistelement[palistn 1]：順序表中的各個元素。 2022/1/4 16/114 struct SeqList { int MAXNUM。 /*順序表中最大元素的個數(shù) */ int n。 /* 存放線性表中元素的個 n ≤ MAXNUM*/ DataType *element。 /* element[0],element[1]， …， element[n 1]存放線性表中的元素 */ }。 typedef struct SeqList *PSeqList。 1. 創(chuàng)建一個空順序表 PSeqList createNullList_seq(int m) 分配順序表空間 (PSeqList) malloc(sizeof(struct SeqList)) 為順序表分配數(shù)組空間，大小為 m (DataType *) malloc(sizeof(DataType)*m) MAXNUM置為 m， n置為 0 [說明 ] malloc：在內(nèi)存的動態(tài)存儲區(qū)域中分配一個長度為 size的連續(xù)空間 .如果未成功，返回空指針 NULL. free：釋放由 p指向的內(nèi)存區(qū) 運(yùn)算的實現(xiàn) 2022/1/4 17/114 2022/1/4 18/114 PSeqList createNullList_seq(int m) { /*創(chuàng)建新的順序表 */ PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList))。 if (palist!=NULL) { palistelement = (DataType*)malloc(sizeof(DataType)*m)。 if (palistelement) { palistMAXNUM=m。 palist n = 0。 /*空表長度為 0*/ return (palist)。 } else free (palist)。 } printf(Out of space!!!\n)。 /*存儲分配失敗 */ return NULL。 } 2. 判斷線性表是否為空 int isNullList_seq(PSeqList palist ) 判 斷 palist的 n字段是否為 0即可 2022/1/4 19/114 int isNullList_seq(PSeqList palist) { /*判別 palist所指順序表是否為空表 */ return ( palistn == 0 )。 } 3. 求某元素位置 int locate_seq(PSeqList palist, DataType x) x與表中元素依次，相同則返回下標(biāo) 若表中沒有 x，則返回 1 2022/1/4 20/114 int locate_seq(PSeqList palist, DataType x) { /* 求 x在 palist所指順序表中的下標(biāo) */ int q。 for ( q=0。 qpalistn 。 q++) if ( palistelement[q] == x) return (q)。 return 1。 } 4. 順序表的元素插入 int insertPre_seq(PSeqList palist, int p, DataType x) 在下標(biāo)為 p1與下標(biāo)為 p的元素之間插入一個新的元素 x 1) 溢出檢測 ： palistn palistMAXNUM 2) p的有效性： 0≤p≤palistn 3) 下標(biāo)為 n~p的元素依次后移一位 2022/1/4 21/114 2022/1/4 22/114 2022/1/4 23/114 int insertPre_seq(PSeqList palist, int p, DataType x) { /*在 palist所指順序表中下標(biāo)為 p的元素之前插入元素 x */ int q。 if ( palistn = palist MAXNUM) { /*溢出 */ printf(Overflow! \n)。 return 0。 } if (p0 || ppalistn) {