數(shù)據(jù)結(jié)構(gòu)宋紅

1、122.1 線性表的基本概念線性表的基本概念線性表特點(diǎn)：在數(shù)據(jù)元素的非空有限集中線性表特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作存在唯一的一個(gè)被稱作“第一個(gè)第一個(gè)”的數(shù)據(jù)元素的數(shù)據(jù)元素存在唯一的一個(gè)被稱作存在唯一的一個(gè)被稱作“最后一個(gè)最后一個(gè)”的數(shù)據(jù)元素的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼繼線性表是類型相同的元素有限序列，記作：線性表是類型相同的元素有限序列，記作：（a1, ., ai-1, ai, ai+1, , an）32.

2、1 線性表的基本概念線性表的基本概念設(shè)設(shè) A=（a1, a2, . , ai-1, ai , ai+1, , an）是一線性表）是一線性表1）線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元）線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素必須是同一類型的；素必須是同一類型的；2）在表中）在表中 ai-1 領(lǐng)先于領(lǐng)先于 ai ，ai 領(lǐng)先于領(lǐng)先于 ai+1，稱，稱 ai-1 是是 ai 的直的直接前趨，接前趨， ai+1 是是ai 的直接后繼；的直接后繼；3）在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素）在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前

3、趨，有且僅有一個(gè)直接后繼。線性表都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)；是一種線性數(shù)據(jù)結(jié)構(gòu)；4）元素的個(gè)數(shù)）元素的個(gè)數(shù) n 稱為表的長度，稱為表的長度，n=0時(shí)稱為空表；時(shí)稱為空表；5）ai 是表的第是表的第 i 個(gè)元素，稱個(gè)元素，稱 i 為數(shù)據(jù)元素為數(shù)據(jù)元素 ai 的序號(hào)，每個(gè)元素的序號(hào)，每個(gè)元素在線性表中的位置，僅取決于它的序號(hào)。在線性表中的位置，僅取決于它的序號(hào)。6）可在表的任意位置進(jìn)行插入和刪除操作。）可在表的任意位置進(jìn)行插入和刪除操作。42.1 線性表的基本概念線性表的基本概念 對(duì)線性表的對(duì)線性表的ADT描述描述 ADT List 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：

4、D = ai | ai ElemSet, i=1,n，n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 = | ai-1,ai D, i=2, ,n 基本操作：基本操作： InitList (&L) 操作結(jié)果：構(gòu)造一個(gè)空的線性表操作結(jié)果：構(gòu)造一個(gè)空的線性表L。DetroyList (&L) 初始條件：線性表初始條件：線性表L已經(jīng)存在。已經(jīng)存在。 操作結(jié)果：銷毀線性表操作結(jié)果：銷毀線性表L。. ADTList52.1 線性表的基本概念線性表的基本概念 對(duì)線性表的基本操作對(duì)線性表的基本操作 1 初始化操作初始化操作 InitList (&L) 功能：建立空的線性表功能：建立空的線性表L； 2 銷毀操作銷毀操作 De

5、troyList (&L) 功能：回收為線性表功能：回收為線性表L動(dòng)態(tài)分配的存動(dòng)態(tài)分配的存儲(chǔ)空間；儲(chǔ)空間； 3 置空操作置空操作 ClearList (&L) 功能：功能：L中已存在，重新將其置成空中已存在，重新將其置成空表；表； 4 判空操作判空操作 ListEmpty (L) 功能：判斷線性表功能：判斷線性表L是否為空表，若是否為空表，若為空表返回為空表返回TRUE，否則返回，否則返回FALSE； 5 求表長操作求表長操作 ListLength (L) 功能：返回線性表功能：返回線性表L的表長；的表長；62.1 線性表的基本概念線性表的基本概念6 6 取元素操作：取元素操作：GetElem

6、 ( L, i, &e)GetElem ( L, i, &e) 功能：將線性表功能：將線性表L L中第中第 i i 個(gè)元素賦值給個(gè)元素賦值給 e e；7 7 查找操作查找操作 LocateElem ( L, e, compare() ) LocateElem ( L, e, compare() ) 功能：在線性表功能：在線性表 L L 中查找與元素中查找與元素e e 滿足滿足compare()compare()的第的第 1 1 個(gè)元素，返回該元素在表中的序號(hào)（或位個(gè)元素，返回該元素在表中的序號(hào)（或位置），若表中不存在這樣的元素，則返回置），若表中不存在這樣的元素，則返回 0 0；8 8 查找前

7、驅(qū)查找前驅(qū) PriorElem ( &L, cur_e, &pre_e ) PriorElem ( &L, cur_e, &pre_e ) 功能：若功能：若 cur_e cur_e 是是 L L 中的數(shù)據(jù)元素且不是第一個(gè)，中的數(shù)據(jù)元素且不是第一個(gè)，則用則用 pre_e pre_e 返回它的前驅(qū)，否則失敗，返回它的前驅(qū)，否則失敗，pre_epre_e無定無定義。義。72.1 線性表的基本概念線性表的基本概念9 9 查找后繼查找后繼 NextElem ( &L, cur_e, &next_e ) NextElem ( &L, cur_e, &next_e ) 功能：若功能：若 cur_e cur_

8、e 是是L L中的數(shù)據(jù)元素且不是最后一個(gè)，中的數(shù)據(jù)元素且不是最后一個(gè)，則用則用next_enext_e返回它的后繼，否則失敗，返回它的后繼，否則失敗，next_enext_e無定義。無定義。10 10 插入操作插入操作 ListInsert ( &L, i, e ) ListInsert ( &L, i, e ) 功能：在線性表功能：在線性表L L的第的第i i個(gè)元素之前插入個(gè)元素之前插入1 1個(gè)新元素個(gè)新元素e e；11 11 刪除操作刪除操作 ListDelete ( &L, i, &e ) ListDelete ( &L, i, &e ) 功能：刪除線性表功能：刪除線性表L L的第的第i

9、 i個(gè)元素，并用個(gè)元素，并用 e e 返回；返回；12 12 遍歷操作遍歷操作 ListTraverse ( &L,visit( ) ) ListTraverse ( &L,visit( ) ) 功能：依次對(duì)線性表功能：依次對(duì)線性表L L的每個(gè)元素調(diào)用函數(shù)的每個(gè)元素調(diào)用函數(shù)visit()visit()。若若visit()visit()失敗，則返回失敗，則返回 ERROR ERROR，否則返回，否則返回 OK OK；82.1 線性表的基本概念線性表的基本概念 說明說明1 1、基本操作是一種數(shù)據(jù)結(jié)構(gòu)中最常、基本操作是一種數(shù)據(jù)結(jié)構(gòu)中最常見的操作，它具有明確的邏輯意義。見的操作，它具有明確的邏輯意義。

10、2 2、可以將基本操作看成一個(gè)整體，、可以將基本操作看成一個(gè)整體，使用基本操作來解決新的問題，設(shè)計(jì)新的算使用基本操作來解決新的問題，設(shè)計(jì)新的算法。使我們可以在更高的層次上進(jìn)行抽象，法。使我們可以在更高的層次上進(jìn)行抽象，在更高的基礎(chǔ)上進(jìn)行設(shè)計(jì)。在更高的基礎(chǔ)上進(jìn)行設(shè)計(jì)。3 3、在算法的程序?qū)崿F(xiàn)的過程中，基、在算法的程序?qū)崿F(xiàn)的過程中，基本操作需要通過編制公共函數(shù)進(jìn)行具體實(shí)現(xiàn)。本操作需要通過編制公共函數(shù)進(jìn)行具體實(shí)現(xiàn)。可以為基本操作建立公共函數(shù)庫?？梢詾榛静僮鹘⒐埠瘮?shù)庫。92.1 線性表的基本概念線性表的基本概念 利用基本操作進(jìn)行算法設(shè)計(jì)利用基本操作進(jìn)行算法設(shè)計(jì)例例1 1：若有兩個(gè)集合：若有兩個(gè)集

11、合 A A 和和 B B 分別用分別用兩個(gè)線性表兩個(gè)線性表 LA LA 和和 LB LB 表示，即：線表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個(gè)新的集合：現(xiàn)要求一個(gè)新的集合：A AABAB。 問題分析問題分析上述問題可以演繹為：擴(kuò)大線性表上述問題可以演繹為：擴(kuò)大線性表 LALA，將存在于線性表，將存在于線性表LB LB 中而不存在于中而不存在于線性表線性表 LA LA 中的數(shù)據(jù)元素插入到線性中的數(shù)據(jù)元素插入到線性表表 LA LA 中去。中去。102.1 線性表的基本概念線性表的基本概念 利用基本操作進(jìn)行算法設(shè)計(jì)利用基本操作進(jìn)行算法設(shè)計(jì)1從線性表從

12、線性表LB中依次察看每個(gè)數(shù)據(jù)元素；中依次察看每個(gè)數(shù)據(jù)元素；2依值在線性表依值在線性表LA中進(jìn)行查訪；中進(jìn)行查訪； 3若不存在，則插入之。若不存在，則插入之。GetElem ( LB, i ) e LocateElem ( LA, e, equal( ) ) ListInsert ( LA, n+1, e ) ListInsert ( LA, n+1, e )112.1 線性表的基本概念線性表的基本概念 利用基本操作進(jìn)行算法設(shè)計(jì)利用基本操作進(jìn)行算法設(shè)計(jì) GetElem(Lb, i, e); / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給e if ( ! LocateElem ( La, e,

13、 equal( ) ) ) ListInsert ( La, +La_len, e ); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之void union ( List &La, List Lb ) La_len = ListLength (La); / 求線性表的長度求線性表的長度 Lb_len = ListLength (Lb); for ( i = 1; i = Lb_len; i+ ) / union12集合集合 B2.1 線性表的基本概念線性表的基本概念 例例2-1：已知一個(gè)非純集合：已知一個(gè)非純集合B，試構(gòu)造一個(gè)純集合，試構(gòu)造一個(gè)純集合 A，使

14、使 A中只包含中只包含 B 中所有值各不相同的數(shù)據(jù)元素。中所有值各不相同的數(shù)據(jù)元素。 問題分析：采用線性表表示集合問題分析：采用線性表表示集合集合集合 A算法策略：從集合算法策略：從集合 B 取出物件放入集合取出物件放入集合 A。 要求集合要求集合 A 中同樣的物件不能有兩件以上。中同樣的物件不能有兩件以上。132.1 線性表的基本概念線性表的基本概念 利用基本操作進(jìn)行算法設(shè)計(jì)利用基本操作進(jìn)行算法設(shè)計(jì) GetElem(Lb, i, e); / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給e if ( ! LocateElem ( La, e, equal( ) ) ) ListInsert

15、( La, +La_len, e ); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之void union ( List &La, List Lb ) La_len=ListLength (La); Lb_len=ListLength (Lb); for ( i = 1; i = Lb_len; i+ ) / unionInitList (La); / 構(gòu)造構(gòu)造(空的空的)線性表線性表LA142.1 線性表的基本概念線性表的基本概念 例例2-2：已知一個(gè)非純集合：已知一個(gè)非純集合B，試構(gòu)造一個(gè)純集合，試構(gòu)造一個(gè)純集合 A，使使 A中只包含中只包含 B 中所有

16、值各不相同的數(shù)據(jù)元素。中所有值各不相同的數(shù)據(jù)元素。 問題分析：采用有序表表示集合問題分析：采用有序表表示集合有序表：有序表： 若線性表中的數(shù)據(jù)元素相互之間可以比較若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即：遞增有序排列，即：aiai-1 或或 aiai-1 (i=2,3,n)則稱該線性表為有序表則稱該線性表為有序表(Ordered List)。152.1 線性表的基本概念線性表的基本概念例如：例如： （2 2，3 3，3 3，5 5，6 6，6 6，6 6，8 8，1212）對(duì)集合對(duì)集合 B 而言，而言， 值

17、相同的數(shù)據(jù)元素必定相鄰；值相同的數(shù)據(jù)元素必定相鄰；對(duì)集合對(duì)集合 A 而言，而言， 數(shù)據(jù)元素依值從小至大的順序插入。數(shù)據(jù)元素依值從小至大的順序插入。因此，數(shù)據(jù)結(jié)構(gòu)改變了，因此，數(shù)據(jù)結(jié)構(gòu)改變了， 解決問題的策略也要相應(yīng)進(jìn)行改變。解決問題的策略也要相應(yīng)進(jìn)行改變。162.1 線性表的基本概念線性表的基本概念 利用基本操作進(jìn)行算法設(shè)計(jì)利用基本操作進(jìn)行算法設(shè)計(jì)void purge ( List &La, List Lb ) InitList ( La ); La_len = ListLength ( La ); Lb_len = ListLength ( Lb ); / 求線性表的長度求線性表的長度 fo

18、r ( i = 1; i = Lb_len; i+ ) / purge GetElem ( Lb, i, e ); / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給 eif ( ListEmpty(La) | ! equal (en, e) ) ListInsert ( La, +La_len, e ); en = e; / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之172.2 線性表的順序表示與實(shí)現(xiàn) 線性結(jié)構(gòu)的順序表示是指使用一組地址連續(xù)線性結(jié)構(gòu)的順序表示是指使用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的

19、起始地址，線性表的起始地址，稱作線性表的基地址稱作線性表的基地址 a1 a2 ai-1 ai an線性表元素之間的邏輯關(guān)線性表元素之間的邏輯關(guān)系，通過元素的存儲(chǔ)順序系，通過元素的存儲(chǔ)順序反映（表示）出來；反映（表示）出來； 假設(shè)：線性表中每個(gè)數(shù)據(jù)元素占用假設(shè)：線性表中每個(gè)數(shù)據(jù)元素占用 k k 個(gè)存儲(chǔ)單個(gè)存儲(chǔ)單元，那么，在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第元，那么，在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第 i i 個(gè)元個(gè)元素的存儲(chǔ)位置與第素的存儲(chǔ)位置與第 1 1 個(gè)元素的存儲(chǔ)位置的關(guān)系：個(gè)元素的存儲(chǔ)位置的關(guān)系：Loc ( ai ) = Loc ( a1 ) + (i 1) Loc ( ai ) = Loc ( a1

20、 ) + (i 1) k k182.2 線性表的順序表示與實(shí)現(xiàn) 線性表的順序表示線性表的順序表示內(nèi)存狀態(tài)內(nèi)存狀態(tài)a1a1a2a2aiaiananb bb+kb+kb+(i-1)kb+(i-1)k存儲(chǔ)地址存儲(chǔ)地址b+(n-1)kb+(n-1)kb+(maxlen-1)kb+(maxlen-1)k1 12 2i i元素位序元素位序n n空閑空閑順序表的特點(diǎn)順序表的特點(diǎn)用連續(xù)的存儲(chǔ)單元存用連續(xù)的存儲(chǔ)單元存放線性表的元素。放線性表的元素。元素存儲(chǔ)順序與元素元素存儲(chǔ)順序與元素的邏輯順序一致。的邏輯順序一致。192.2 線性表的順序表示與實(shí)現(xiàn) 順序表的類型定義順序表的類型定義#define LIST_IN

21、IT_SIZE 100#define LIST_INIT_SIZE 100 / / 線性表存儲(chǔ)空間的初始分配量線性表存儲(chǔ)空間的初始分配量 #define LISTINCREMENT 10 #define LISTINCREMENT 10 / / 線性表存儲(chǔ)空間的分配增量線性表存儲(chǔ)空間的分配增量 typedef struct typedef struct ElemType ElemType * * elem; / elem; /線性表存儲(chǔ)空間基址線性表存儲(chǔ)空間基址 int length; / int length; /當(dāng)前線性表長度當(dāng)前線性表長度 int listsize; / int list

22、size; /當(dāng)前分配的表空間大小當(dāng)前分配的表空間大小 / /（以（以sizeof(ElemType)sizeof(ElemType)為單位）為單位）SqList;SqList;202.2 線性表的順序表示與實(shí)現(xiàn) 設(shè)設(shè) A = A =（a1a1，a2a2， a3 a3，.，anan）是一線性表，）是一線性表，L L是是 SqList SqList 類型的結(jié)構(gòu)變量，用于存放線性表類型的結(jié)構(gòu)變量，用于存放線性表 A A，則，則 L L 在內(nèi)存中的狀態(tài)：在內(nèi)存中的狀態(tài)：存放線性表存放線性表元素的一維元素的一維數(shù)組數(shù)組 a1 a1 a2 a2ai-1ai-1 ai aiai+1ai+1 an an0

23、01 1i-2i-2i-1i-1i in-1n-19999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n100100212.2 線性表的順序表示與實(shí)現(xiàn)順序表基本操作的算法順序表基本操作的算法初始化操作初始化操作 InitList_Sq ( SqList &L)功能：建立空的順序表功能：建立空的順序表L參數(shù)：參數(shù)：L: 順序表順序表0 01 1.i i.9999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsize0 0100100O(1)算法時(shí)間復(fù)雜度：222.2 線性表的順序表示與實(shí)現(xiàn)兩個(gè)兩個(gè)C

24、函數(shù)之一：函數(shù)之一：malloc ( int size )功能：在內(nèi)存中分配長度為功能：在內(nèi)存中分配長度為size個(gè)字節(jié)的存儲(chǔ)單元，個(gè)字節(jié)的存儲(chǔ)單元，并返回該空間的基址。并返回該空間的基址。使用方法：使用方法： int m = 100, float *p; p = (float *) malloc ( m*sizeof(float ) );0 01 1.i i.9999p p232.2 線性表的順序表示與實(shí)現(xiàn)0 01 1.i i.9999p p調(diào)用調(diào)用free ( p )兩個(gè)兩個(gè)C函數(shù)之二：函數(shù)之二：free ( p )功能：回收指針功能：回收指針 p 所指向的內(nèi)存空間。所指向的內(nèi)存空間。使用

25、方法：使用方法： int m = 100, float *p; p = (float *) malloc (m*sizeof(float) ); /一旦不再需要一旦不再需要p所指向的內(nèi)存空間所指向的內(nèi)存空間 /調(diào)用調(diào)用 free( ) 回收之回收之 free(p);242.2 線性表的順序表示與實(shí)現(xiàn) 初始化操作初始化操作InitList_Sq( SqList &L)InitList_Sq( SqList &L) Status InitList_Sq ( SqList &L )Status InitList_Sq ( SqList &L ) / /構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表L L L.

26、elem = ( ElemType L.elem = ( ElemType * * ) ) malloc(LIST_INIT_SIZE malloc(LIST_INIT_SIZE * *sizeof(ElemType);sizeof(ElemType); if ( !L.elem ) if ( !L.elem ) exit ( OVERFLOW ); exit ( OVERFLOW ); L.length = 0; / L.length = 0; /空表長度為空表長度為0 0 L.listsize = LIST_INIT_SIZE; L.listsize = LIST_INIT_SIZE; r

27、eturn OK; return OK; /InitList_Sq /InitList_Sq252.2 線性表的順序表示與實(shí)現(xiàn)順序表基本操作的算法順序表基本操作的算法銷毀操作銷毀操作 DetroyList_Sq ( SqList &L )功能：銷毀順序表功能：銷毀順序表L0 01 1.i i.9999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsize0 0100100NULLNULL0 00 0262.2 線性表的順序表示與實(shí)現(xiàn) 銷毀操作銷毀操作 DetroyList_Sq ( SqList &L) Status DetroyList_Sq ( S

28、qList &L) free (L.elem); L.elem = NULL; L.length = 0; L.Listsize = 0; return OK; / DetroyList_Sq272.2 線性表的順序表示與實(shí)現(xiàn) 插入操作插入操作 定義：線性表的插入是指在第定義：線性表的插入是指在第 i（1i n+1）個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素 x，使長度為，使長度為 n 的線性表：的線性表： A =（a1, a2, . , ai-1, ai , ai+1, , an）變成長度為變成長度為n+1的線性表：的線性表： A =（a1, a2, . , ai-1, x

29、, ai , ai+1, , an） 需將第需將第 i 至第至第 n 共（共（n-i+1）個(gè)元素后移。）個(gè)元素后移。282.2 線性表的順序表示與實(shí)現(xiàn) 插入操作：插入操作：ListInsert_Sq(SqList &L, int i, ElemType e)L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n100100a10a21.ai-1i-299nann-1.ai+1iaii-1L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen+1n+1100100a10a21.ai-1i-299ann.n

30、-1.aii+1ei算法的時(shí)間算法的時(shí)間復(fù)雜度為：復(fù)雜度為：O( ListLength(L) )292.2 線性表的順序表示與實(shí)現(xiàn)內(nèi)存內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)數(shù)組下標(biāo)n-1in12i元素序號(hào)元素序號(hào)i+1nn+1e內(nèi)存內(nèi)存a1a2aiai+1an01i-1數(shù)組下標(biāo)數(shù)組下標(biāo)n-1in12i元素序號(hào)元素序號(hào)i+1nn+1an-1302.2 線性表的順序表示與實(shí)現(xiàn)插入操作：基本算法插入操作：基本算法Status ListInsert_Sq (SqList &L, int i, ElemType e) /在順序線性表在順序線性表L中第中第 i 個(gè)位置之前插入新的個(gè)位置之前插入新的

31、元素元素e, if ( iL.length+1 ) return ERROR; / i 超出表長則不超出表長則不合法合法q = & ( L.elemi-1 ); / q 指向插入位指向插入位置置 for ( p=&(L.elemL.length-1); p=q; -p ) / 初始化時(shí)初始化時(shí)p指向最后一個(gè)數(shù)據(jù)元素指向最后一個(gè)數(shù)據(jù)元素*(p+1) = *p; *q = e; / 插入插入e +L.length; / 表長增表長增1 return OK; / ListInsert_Sq312.2 線性表的順序表示與實(shí)現(xiàn)Status ListInsert_Sq(SqList &L, int i,

32、ElemType e) /在順序線性表在順序線性表L中第中第 i 個(gè)位置之前插入新的元素個(gè)位置之前插入新的元素e, if ( iL.length+1 ) return ERROR; /i不合法不合法 if ( L.length = L.listsize ) /空間已滿，重新分配空間空間已滿，重新分配空間 newbase = (ElemType*) realloc (L.elem, (L.listsize+L.incresize) * sizeof(ElemType) ); if ( !newbase ) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 L.elem = newbase; /新基址新基址 L.listsize+= L.incresize; /增加存儲(chǔ)容量增加存儲(chǔ)容量 q = & ( L.elemi-1 ); / q為插入位置為插入位置 fo