合工大數(shù)據(jù)結(jié)構(gòu)05-線性表

1、1數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)(第五章第五章 線性表線性表) Data Structures張晶張晶計算機與信息學(xué)院計算機與信息學(xué)院 2022-3-22022-3-22第五章第五章 線性表線性表 第五章第五章 線性表線性表 5.1 線性表的定義和運算 5.2 順序表 5.3 鏈表 5.4 其它結(jié)構(gòu)形式的鏈表 5.5 串 35.1 線性表的定義和運算 5.1.1 線性表的定義線性表的定義： 定義：定義： 線性表線性表L是由是由n個元素個元素a1，a2，an組成的組成的 有限有限 序列序列。 記作記作 L =（a1，a2，an） 其中其中n=0為為表長度表長度； n=0時時L為為空表空表，記作，記作L=

2、（）（） 表中元素表中元素ai的含義：在不同的場合有不同的含義。的含義：在不同的場合有不同的含義。 但是，在同一表中，元素類型相同。但是，在同一表中，元素類型相同。例例：字母表（：字母表（A，B，C，D，Z）；）； 數(shù)字表（數(shù)字表（0，1，2，3，4，9）；）； 2008年每月天數(shù)（年每月天數(shù)（31,29,31,30,31,30,31,31,30,31,30,31）; 成績表中，每個元素就是一個人的成績信息。成績表中，每個元素就是一個人的成績信息。特性特性： 除第一個元素外，其他元素有且僅有一個直接前趨（前驅(qū)）；除第一個元素外，其他元素有且僅有一個直接前趨（前驅(qū)）； 除最后一個元素外，其他元素

3、有且僅有一個直接后繼。除最后一個元素外，其他元素有且僅有一個直接后繼。邏輯結(jié)構(gòu)和運算邏輯結(jié)構(gòu)和運算45.1 線性表的定義和運算5.1.2 線性表的運算線性表的運算對線性表有如下對線性表有如下基本運算基本運算： (1)初始化：初始化： 將線性表設(shè)置為空將線性表設(shè)置為空 (2)求長度：求長度： 返回線性表中的元素個數(shù)。返回線性表中的元素個數(shù)。 (3)按序號取元素：按序號取元素： 從線性表中取出指定序號的元素。從線性表中取出指定序號的元素。 前提：存在該元素。否則，應(yīng)當(dāng)如何處理？前提：存在該元素。否則，應(yīng)當(dāng)如何處理？(4)按值查找元素：按值查找元素： 在線性表中查找給定值的元素所在的位置。在線性表中

4、查找給定值的元素所在的位置。 若不存在，應(yīng)如何給出相關(guān)信息？若不存在，應(yīng)如何給出相關(guān)信息？ (5)插入：插入： 在線性表中給定的位置（序號）插入給定值的元素。在線性表中給定的位置（序號）插入給定值的元素。 (6)刪除：刪除： 刪除線性表種指定序號的元素。刪除線性表種指定序號的元素。 前提：存在該元素。否則，應(yīng)當(dāng)如何處理？前提：存在該元素。否則，應(yīng)當(dāng)如何處理？55.1 線性表的定義和運算線性表運算的線性表運算的C+描述描述-封裝類封裝類 class list public: list(); int length( )const; error_code get_element (const int

5、 i, elementtype &x)const; int locate(const elementtype x)const; error_code insert (const int i, const elementtype x); error_code delete_element(const int i); private: /定義其它成員 ;運算運算： (1)初始化：初始化： (2)求長度：求長度： (3)按序號取元素：按序號取元素： (4)按值查找元素：按值查找元素： (5)插入：插入： (6)刪除：刪除： ?65.2 順序表5.2.1 存儲結(jié)構(gòu)：存儲結(jié)構(gòu)：o與順序棧、隊列的

6、討論類似：與順序棧、隊列的討論類似：n假設(shè)有一個足夠大的存儲空間（數(shù)組）假設(shè)有一個足夠大的存儲空間（數(shù)組）data,用于存儲線性表的元素。用于存儲線性表的元素。n則將線性表中的元素依次存儲到數(shù)組中則將線性表中的元素依次存儲到數(shù)組中-順序存儲方式，順序存儲方式，n由此得到順序表由此得到順序表。n如下圖所示：如下圖所示：o其中，設(shè)置一個計數(shù)變量其中，設(shè)置一個計數(shù)變量count ，以記錄表中的元素個數(shù)。，以記錄表中的元素個數(shù)。o將數(shù)組將數(shù)組data和和count作為類作為類list的數(shù)據(jù)成員。的數(shù)據(jù)成員。a1a2an01n-1maxlen-1datancount順序表存儲結(jié)構(gòu)順序表存儲結(jié)構(gòu)75.2

7、順序表由此得到類由此得到類list如下如下：class listpublic: list(); int length()const; error_code get_element(const int i, elementtype &x)const; int locate(const elementtype x) const; error_code insert(const int i, const elementtype x); error_code delete_element(const int i); private: elementtype datamaxlen; int co

8、unt;list85.2 順序表5.2.1 順序表的運算實現(xiàn)：順序表的運算實現(xiàn)：n初始化：初始化：list:list() count = 0; n求長度：求長度： int list:length( ) return count; n 按序號取元素：按序號取元素： error_code list:get_element(const int i, elementtype &x)const if ( i count ) return range_error; x = datai 1; return success; 95.2 順序表n 按值查找元素按值查找元素：int list:locate

9、(const elmenttype x)const for ( i = 0; i length( ); i + ) if ( datai = x ) return ( i + 1 ); return 0; 105.2 順序表n插入運算插入運算：分析：分析：首先要注意，在表中插入元素的首先要注意，在表中插入元素的條件條件： 順序表不滿；順序表不滿； 序號正確：范圍在序號正確：范圍在 1 n+1之間之間 插入插入操作的步驟操作的步驟包括：包括： ai an后移：后移： 如何實現(xiàn)？如何實現(xiàn)？ 填入填入x； count + ；01n-1 ai a1a2anmaxlen-1datancount順序表結(jié)構(gòu)

10、順序表結(jié)構(gòu) x115.2 順序表插入算法插入算法：error_code list:insert(const int i, const elementtype x) if ( count = maxlen ) return overflow; if ( i length() + 1 ) return range_error; for( j = count; j = i; j - ) dataj = data j 1 ; datai 1 = x; count +; return success; 滿了：如何描述？滿了：如何描述？序號不正確：如何描述？序號不正確：如何描述？移動元素移動元素aian：

11、如何描述？如何描述？01n-1 ai a1a2anmaxlen-1datancount順序表結(jié)構(gòu)順序表結(jié)構(gòu) x125.2 順序表n刪除運算：刪除運算：分析：分析：在線性表中刪除的在線性表中刪除的條件條件是：是： 存在指定序號的元素。存在指定序號的元素。刪除的刪除的操作步驟操作步驟： 將后面的元素將后面的元素ai+1an前移前移 count-;由此得算法如下：由此得算法如下：error_code list:delete_element(const int i) if ( length() = 0 ) return underflow; if ( i length() ) return arran

12、ge_error; for ( j = i + 1; j next = p - next; p - next = s; /注意注意：兩條語句順序不能顛倒 頭指針頭指針首元素結(jié)點首元素結(jié)點尾結(jié)點尾結(jié)點 aaaa X headPs155.3 鏈表 上述操作在鏈表表尾插入時也成立， 然而，在鏈表頭位置插入時， 操作需要另行編寫。 因此，需要引入“頭結(jié)點”（附加結(jié)點），以保證操作的一致性。a1a2an 165.3 鏈表o帶頭結(jié)點的單鏈表存儲結(jié)構(gòu)帶頭結(jié)點的單鏈表存儲結(jié)構(gòu)得到類得到類list的描述如下：的描述如下： 其中：函數(shù)成員中增加了析構(gòu)函數(shù)，其中：函數(shù)成員中增加了析構(gòu)函數(shù)， 數(shù)據(jù)成員中，以頭指針和計

13、數(shù)變量數(shù)據(jù)成員中，以頭指針和計數(shù)變量count作為數(shù)據(jù)成員作為數(shù)據(jù)成員 class list public: list(); int length( )const; error_code get_element(const int i, elementtype &x) const; node * locate( const elmenttype x ) const; error_code insert(const int i, const elmenttype x); error_code delete_element(const int i); list（）； private:int

14、 count; node * head;a1a2an head175.3 鏈表o運算實現(xiàn)：運算實現(xiàn)：n初始化函數(shù)的實現(xiàn)初始化函數(shù)的實現(xiàn)：list:list() head = new node; head - next = NULL; count = 0;n求長度的實現(xiàn)求長度的實現(xiàn)：（假設(shè)不用（假設(shè)不用count分量，先畫出流程圖，再討論）分量，先畫出流程圖，再討論）int list:length()const p = head - next; n = 0; while ( p != NULL ) n +; p = p - next; return n; /若定義若定義count成員，則直接返回

15、成員，則直接返回count值即可值即可a1a2an headhead185.3 鏈表n按序號取元素的實現(xiàn)按序號取元素的實現(xiàn)：先畫出流程圖，再討論先畫出流程圖，再討論error_code list:get_element(const int i, element &x)const p = head - next; j= 1; while ( j != i & p != NULL ) p = p - next; j +; if ( p = NULL ) return range_error; x = p - data; return success;n按值查找元素的實現(xiàn)按值查找元素

16、的實現(xiàn)：先畫出流程圖，再討論先畫出流程圖，再討論node * list:locate(const elementtype x)const p = head - next; while ( p != NULL ) if ( p - data = x ) return p; else p = p - next; return NULL;序號不正確：如何描述？序號不正確：如何描述？a1a2an head195.3 鏈表n插入運算的實現(xiàn)插入運算的實現(xiàn)：先畫出流程圖，再討論先畫出流程圖，再討論error_code list:insert(const int i, const elementtype x)

17、 p = head; j = 0; while ( j != i -1 & p != NULL ) p = p - next; j +; if ( i count + 1 ) / if ( p = NULL ) return range_error; s = new node; s - data = x; s-next=NULL; s - next = p - next; p - next = s; count +; return success;序號不正確：如何判斷？序號不正確：如何判斷？ai-1aixSP205.3 鏈表n刪除運算的實現(xiàn)刪除運算的實現(xiàn)：先畫出流程圖，再討論先畫出流程

18、圖，再討論error_code list:delete_element(const int i)p = head; j = 0;while ( j != i -1 & p != NULL ) p = p - next; j +; if ( i count ) / if ( p = NULL |p-next=NULL ) return range_error;u = p - next;p - next = u - next; delete u;count -;return success;序號不正確：如何判斷？序號不正確：如何判斷？Pai-1aiai+1 215.3 鏈表o 構(gòu)造鏈表構(gòu)造

19、鏈表基本方法：基本方法： 從鍵盤輸入數(shù)據(jù)，每讀入一個元素，產(chǎn)生結(jié)點裝入，從鍵盤輸入數(shù)據(jù)，每讀入一個元素，產(chǎn)生結(jié)點裝入， 插入鏈表中，重復(fù)上述操作插入鏈表中，重復(fù)上述操作討論：產(chǎn)生結(jié)點：討論：產(chǎn)生結(jié)點：s = new node; s-data = x; 插入鏈表：插入位置如何確定，插入鏈表：插入位置如何確定， 有有 表頭、表尾表頭、表尾 兩個位置可選兩個位置可選 表頭插入法，表尾插入表頭插入法，表尾插入 法法 重復(fù)上述操作：重復(fù)上述操作： 何時結(jié)束何時結(jié)束封裝的鏈表類中增加兩個成員函數(shù)：封裝的鏈表類中增加兩個成員函數(shù)：class listpublic: void create1(); /頭插法頭

20、插法 void create2(); /尾插法尾插法;X是結(jié)束是結(jié)束0cin xs = new node;s - data = x;插入到表中插入到表中;NYcin x225.3 鏈表n表頭插入法運算實現(xiàn)：表頭插入法運算實現(xiàn)：void list:create1() cin x; while ( x != 結(jié)束符 ) count +; s = new node; s - data = x; s-next=NULL; s - next = head - next; head - next = s; cin x; sxa1a2an head235.3 鏈表n表尾插入法運算實現(xiàn)：表尾插入法運算實現(xiàn)：v

21、oid list:create2() cin x; rear = head; while ( x != 結(jié)束符 ) count +; s = new node; s - data = x; s-next=NULLL; rear - next = s; rear = s; rear - next = NULL; cin x; a1a2an headrears x 245.3 鏈表練習(xí)練習(xí)：A、B鏈表之間復(fù)制void copy(list A, list &B) B = new node; B - next = NULL; PA = A - next; PB = B; while ( PA

22、!= NULL ) s = new node; s - data = PA - data; PB - next = s; PB = s; PB - next = NULL; PA = PA - next; 練習(xí)練習(xí)： A表分成奇、偶兩個子表表分成奇、偶兩個子表A、B（A表做刪除，表做刪除，B表做插入）表做插入） 鏈表集合鏈表集合 求求 交交 并并 差差 子集子集255.3 鏈表練習(xí)練習(xí)： A表分成奇、偶兩個子表表分成奇、偶兩個子表A、B（A表做刪除，表做刪除，B表做插入）表做插入）void copy(list &A, list &B) PA=A.head-next; PB=B.

23、head-next;while ( PA != NULL )If(PA-data %2=0)/delete form A; u=PA; PA=PA-next;/insert to B at head; u-next=PB-next; PB = u; PA = PA - next;Else PA=PA-next; 練習(xí)練習(xí)： 鏈表集合鏈表集合 求求 交交 并并 差差 子集子集/insert to B at tailPB=u;PB=PB-next;265.3 鏈表練習(xí)練習(xí)： 線性表的逆置void queue:reverse() node *pp=NULL; node *p=front-next;

24、while(p!=NULL)node *pn=p-next;p-next=pp;pp=p;p=pn; front-next=pp; 275.4 其他結(jié)構(gòu)形式的鏈表o1。單循環(huán)鏈表。單循環(huán)鏈表（優(yōu)點：可在表中反復(fù)搜索優(yōu)點：可在表中反復(fù)搜索 ）o在采用這種存儲結(jié)構(gòu)時的運算的實現(xiàn)在采用這種存儲結(jié)構(gòu)時的運算的實現(xiàn)：n初始化操作為初始化操作為： head = new node; head - next = head;n求長度：求長度： p = head - next; n = 0; while ( p != head ) p = p - next; n + ;應(yīng)用應(yīng)用： m人開人開m把鎖問題（每人一把鑰

25、匙，要求所有鎖都能開）把鎖問題（每人一把鑰匙，要求所有鎖都能開） 約瑟夫環(huán)問題（利用循環(huán)鏈表，不帶頭結(jié)點的循環(huán)鏈表都可）約瑟夫環(huán)問題（利用循環(huán)鏈表，不帶頭結(jié)點的循環(huán)鏈表都可）a1a2an headhead285.4 其他結(jié)構(gòu)形式的鏈表2. 帶尾指針的單循環(huán)鏈表帶尾指針的單循環(huán)鏈表o 結(jié)構(gòu)如下圖所示：結(jié)構(gòu)如下圖所示：o 優(yōu)點：優(yōu)點：既便于求得表尾指針，也便于求得表頭指針。既便于求得表尾指針，也便于求得表頭指針。因而方便那些需要同時涉及到表頭和表尾的操作。因而方便那些需要同時涉及到表頭和表尾的操作。reara1a2an 295.4 其他結(jié)構(gòu)形式的鏈表應(yīng)用應(yīng)用：將：將A、B兩鏈表首尾相連兩鏈表首尾相

26、連實現(xiàn)部分語句為：實現(xiàn)部分語句為： u = A - next; A - next = B - next - next; delete B - next; B - next = u; A = B; Aa1a2an Bb1b2bn u305.4 其他結(jié)構(gòu)形式的鏈表3. 雙鏈表雙鏈表o 結(jié)點的結(jié)構(gòu)結(jié)點的結(jié)構(gòu)：每個結(jié)點中：每個結(jié)點中n不僅有指向后繼結(jié)點的指針不僅有指向后繼結(jié)點的指針next,n還有指向前驅(qū)的指針還有指向前驅(qū)的指針prior. typedef struct elementtype data; dunode * prior, * next; dunode; o優(yōu)點優(yōu)點：求前驅(qū)后繼都方便：求

27、前驅(qū)后繼都方便o鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)：有：有帶頭結(jié)點帶頭結(jié)點 或者或者 不帶頭結(jié)點不帶頭結(jié)點, 循環(huán)循環(huán)與與非循環(huán)非循環(huán) 之分。之分。 prior data next a1a2 an head315.4 其他結(jié)構(gòu)形式的鏈表初始化初始化 head = new node; head - prior = head - next = head;求長度查找類似求長度查找類似插入時：插入時： s - prior = p - prior; s - next = p; p - prior = s; s - prior - next = s; 刪除時：刪除時： p - prior - next = p - next

28、; p - next - prior = p - prior; delete p;應(yīng)用應(yīng)用：判斷雙循環(huán)鏈表是否對稱判斷雙循環(huán)鏈表是否對稱 雙循環(huán)鏈表倒置（動指針、動結(jié)點值）雙循環(huán)鏈表倒置（動指針、動結(jié)點值）head ai-1 aip ai-1 ai ai+1p xs325.4 其他結(jié)構(gòu)形式的鏈表o 小結(jié)：小結(jié)： 線性表線性表 順序表：順序表： 邏輯上相鄰的元素物理上也相鄰邏輯上相鄰的元素物理上也相鄰 ； 可直接定位，節(jié)省搜索時間可直接定位，節(jié)省搜索時間 然而，在然而，在 插入、刪除時，需移動元素，浪費時間插入、刪除時，需移動元素，浪費時間 鏈鏈 表：表：邏輯上相鄰的元素物理上不一定相鄰；邏輯上

29、相鄰的元素物理上不一定相鄰； 插入、刪除時，不需移動元素插入、刪除時，不需移動元素335.5 串o 1.定義：定義：串串是由是由n個字符個字符a1,a2,an組成的有限序列。組成的有限序列。 記作記作 S=“a1,a2,an”， 其中其中n =0為為串長度串長度。 n=0時為時為空串空串。 （或者說：元素是字符的線性表）（或者說：元素是字符的線性表） 注意注意：空串空串和和空格串空格串的區(qū)別。的區(qū)別。 空串空串沒有元素。沒有元素。 空格串空格串元素是空格符。元素是空格符。 子串子串 串串S中若干個連續(xù)的字符組成的序列。中若干個連續(xù)的字符組成的序列。345.5 串o 2. 基本運算基本運算： 賦

30、值賦值（=）：）： 將一個串值將一個串值S1傳送給一個串名傳送給一個串名S。（如：。（如：S=S1） 求長度求長度length(S)： 返回串返回串S的長度值。的長度值。 連接運算連接運算（如（如S1+S2）：）： 將將S1和和S2連接成一個新串。連接成一個新串。 求子串求子串（substr（S,i,j）：）： 返回串返回串S從第從第i個元素開始的個元素開始的j個元素所組成個元素所組成 的子串。的子串。 串比較串比較：（：（strcmp(S1,S2)） 比較兩個串的大小。對齊按比較兩個串的大小。對齊按ASCII碼進行比較。碼進行比較。 結(jié)果可定為結(jié)果可定為-1 0 1 也可以定為其他取值方式也

31、可以定為其他取值方式355.5 串常用運算常用運算：可由基本運算實現(xiàn)可由基本運算實現(xiàn) 插入插入（insert（S,i,S1）：）： 將子串將子串S1插入到串插入到串S的從第的從第i個字符開始的位置上。個字符開始的位置上。 刪除刪除（deletestr（S,i,len）：）： 刪除串刪除串S中從第中從第i個字符開始的個字符開始的len個字符。個字符。 替換替換（replace(S,i,len,S1)）：）： 用字串用字串S1替換串替換串S中從第中從第i個字符開始的個字符開始的len個字符。個字符。 定位定位（index（S,S1）/模式匹配模式匹配 例：例：S=“a1,a2,an”，在，在S的第

32、的第i個位置插入個位置插入S1 運算為運算為 insert(S,i,S1)，為常用運算，為常用運算 可操作為：可操作為：substr(1,i-1,X1) substr(i, length() - (i - 1), X2) S = X1 + S1 + X2 /為基本運算為基本運算 兩者可互換兩者可互換365.5 串o3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 順序串順序串 非緊湊格式：非緊湊格式： 優(yōu)點：運算方便；優(yōu)點：運算方便； 缺點：浪費空間。缺點：浪費空間。 緊湊格式：緊湊格式： 優(yōu)點：節(jié)省空間；優(yōu)點：節(jié)省空間； 缺點：運算不方便。缺點：運算不方便。 鏈串鏈串-結(jié)點大?。ㄒ?guī)模）：結(jié)點大小（規(guī)模）： 等于等于1

33、： 大于大于1： S a1 a2 a3ana4. a3. a2. a1a8. a7. a6. a5ana1a2a3a4a5a6a7a8an 375.5 串4. 串的運算o 模式匹配 index(p,S):n簡單的理解:int index(p,S) i=1; while (i=length(S)-length(p)+1) if (substr(S,i, length(p)=p) return i; else i+;o 分析:時間性能:費時n改進:KMP算法,n 其他改進方法字符串S模式p串 例子3839內(nèi)容回顧o 線性表的相關(guān)概念：定義、運算及其C+描述o 順序存儲結(jié)構(gòu)及其描述，順序表運算的實現(xiàn)o 鏈表存儲結(jié)構(gòu)及其描述，鏈表中運算的實現(xiàn)o 其他形式的鏈表結(jié)構(gòu)