數(shù)據(jù)結(jié)構(gòu)2331第2章線性表

1、12 2.1 線性表的基本概念線性表的基本概念 2.2 線性表的順序?qū)崿F(xiàn)線性表的順序?qū)崿F(xiàn) 2.3 線性表的鏈?zhǔn)綄?shí)現(xiàn)線性表的鏈?zhǔn)綄?shí)現(xiàn) 2.3.1 單鏈表單鏈表 2.3.2 單鏈表的簡(jiǎn)單操作單鏈表的簡(jiǎn)單操作 2.3.3 基本運(yùn)算在單鏈表上的實(shí)現(xiàn)基本運(yùn)算在單鏈表上的實(shí)現(xiàn) 2.4 其它運(yùn)算在單鏈表上的實(shí)現(xiàn)其它運(yùn)算在單鏈表上的實(shí)現(xiàn) 2.5 其它鏈表其它鏈表 2.7 順序?qū)崿F(xiàn)與鏈表實(shí)現(xiàn)的比較順序?qū)崿F(xiàn)與鏈表實(shí)現(xiàn)的比較 2.8 串串3一、線性表的邏輯定義一、線性表的邏輯定義線性表線性表 是是n(0)個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素a1，a2， an的有限的有限序列序列；表中每個(gè)元素（除第一個(gè)和最后一個(gè)外），有；表中每個(gè)元

2、素（除第一個(gè)和最后一個(gè)外），有且僅有一個(gè)直接前趨，有且只有一個(gè)直接后繼。且僅有一個(gè)直接前趨，有且只有一個(gè)直接后繼。 即線性表或?yàn)橐粋€(gè)即線性表或?yàn)橐粋€(gè)空表空表（n=0），或?yàn)椋海?，或?yàn)椋?（a1，a2，, ai-1，ai，ai+1， ，an） （n0） 其中數(shù)據(jù)元素的個(gè)數(shù)其中數(shù)據(jù)元素的個(gè)數(shù)n定義為定義為表的長(zhǎng)度表的長(zhǎng)度（表長(zhǎng)）。（表長(zhǎng)）。 這里的數(shù)據(jù)元素這里的數(shù)據(jù)元素ai(1in)只是一個(gè)抽象的符號(hào)，其具體只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。含義在不同的情況下可以不同。 例例1、26個(gè)英文字母組成的字母表個(gè)英文字母組成的字母表 （A，B，C、Z）2.1 線性表的基本概念線性表的

3、基本概念4例例2、學(xué)生健康情況登記表如下：、學(xué)生健康情況登記表如下：姓姓 名名學(xué)學(xué) 號(hào)號(hào)性性 別別年齡年齡 健康情況健康情況王小林王小林790631 男男 18 健康健康陳陳 紅紅790632 女女 20 一般一般劉建平劉建平790633 男男 21 健康健康張立立張立立790634 男男 17 神經(jīng)衰弱神經(jīng)衰弱 . . .記錄記錄由若干個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄。由若干個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄。文件文件含大量記錄的線性表稱為文件。含大量記錄的線性表稱為文件。a1a2a3a4。2.1 2.1 線性表的基本概線性表的基本概念念5二、線性表的邏輯結(jié)構(gòu)特征二、線性表的邏輯結(jié)構(gòu)特征 也就是線

4、性結(jié)構(gòu)的基本特征也就是線性結(jié)構(gòu)的基本特征 線性表是一種典型的線性結(jié)構(gòu)。線性表是一種典型的線性結(jié)構(gòu)。對(duì)于非空的線性表對(duì)于非空的線性表: 有且僅有一個(gè)有且僅有一個(gè)起始結(jié)點(diǎn)起始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，它沒(méi)有直接前趨， 但有且僅有一個(gè)直接后繼但有且僅有一個(gè)直接后繼a2； 有且僅有一個(gè)有且僅有一個(gè)終端結(jié)點(diǎn)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，它沒(méi)有直接后繼， 但有且僅有一個(gè)直接前趨但有且僅有一個(gè)直接前趨an-1； 其余的其余的內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)ai（2in-1）都有且僅有）都有且僅有 一個(gè)直接前趨一個(gè)直接前趨ai-1和一個(gè)直接后繼和一個(gè)直接后繼ai+1。 2.1 2.1 線性表的基本概線性表的基本概念念6 數(shù)據(jù)

5、結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。 線性表的基本運(yùn)算有：線性表的基本運(yùn)算有：1）Initiate(L),加工型運(yùn)算加工型運(yùn)算，作用是構(gòu)造空表，即表的初始化； 2）Length(L),引用型運(yùn)算引用型運(yùn)算，其結(jié)果是表的結(jié)點(diǎn)個(gè)數(shù)，即表長(zhǎng)； 3）Get (L,i), 引用型運(yùn)算引用型運(yùn)算，若1iLength(L)，其結(jié)果是表中的第i個(gè)結(jié)點(diǎn)；否則，為一特殊值。 4）Locate (L,x) ，引用型運(yùn)算引用型運(yùn)算，查找L中值為x的結(jié)點(diǎn)并返回結(jié)點(diǎn)在L中的位置，若有多個(gè)x則返回首個(gè)；否則返回特

6、殊值表示查找失敗。 5）Insert (L,x,i)，加工型運(yùn)算加工型運(yùn)算，在表的第i個(gè)位置插入值為x的新結(jié)點(diǎn)，要求1iLength(L)+1； 6）Delete (L,i)，加工型運(yùn)算加工型運(yùn)算，刪除表的第i個(gè)位置的結(jié)點(diǎn)，要求1iLength(L)； 三、線性表的基本運(yùn)算三、線性表的基本運(yùn)算2.1 2.1 線性表的基本概線性表的基本概念念7一、一、 順序表的定義順序表的定義 1、順序存儲(chǔ)方法順序存儲(chǔ)方法 把線性表的元素把線性表的元素按邏輯順序依次按邏輯順序依次存放在一存放在一組組地址連續(xù)地址連續(xù)的存儲(chǔ)單元里的存儲(chǔ)單元里。 2、順序表順序表 用順序存儲(chǔ)方法存儲(chǔ)的線性表簡(jiǎn)稱為用順序存儲(chǔ)方法存儲(chǔ)的

7、線性表簡(jiǎn)稱為順序表順序表。2.2 線性表的順序?qū)崿F(xiàn)線性表的順序?qū)崿F(xiàn)2.2.1 順序表順序表8 假設(shè)線性表的每個(gè)元素需占用假設(shè)線性表的每個(gè)元素需占用d d個(gè)存儲(chǔ)單元，并個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。并設(shè)表中開(kāi)始結(jié)點(diǎn)位置。并設(shè)表中開(kāi)始結(jié)點(diǎn)a1的存儲(chǔ)地址（簡(jiǎn)稱為基地的存儲(chǔ)地址（簡(jiǎn)稱為基地址）是址）是LOC（a1），那么結(jié)點(diǎn)），那么結(jié)點(diǎn)ai的存儲(chǔ)地址的存儲(chǔ)地址LOC（ai）可通過(guò)下式計(jì)算：可通過(guò)下式計(jì)算： LOC(ai)=LOC(a1)+(i-1)*d 二、結(jié)點(diǎn)結(jié)點(diǎn)ai 的存儲(chǔ)地址的存儲(chǔ)地址順序表的尋址公式順序表的尋址公

8、式 注意：注意： 在順序表中，每個(gè)結(jié)點(diǎn)在順序表中，每個(gè)結(jié)點(diǎn)a ai i的存儲(chǔ)地址是該結(jié)點(diǎn)在表的存儲(chǔ)地址是該結(jié)點(diǎn)在表中的位置中的位置i i的線性函數(shù)。只要知道基地址和每個(gè)結(jié)點(diǎn)的的線性函數(shù)。只要知道基地址和每個(gè)結(jié)點(diǎn)的大小，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。是大小，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。是一種一種隨機(jī)存取結(jié)構(gòu)。隨機(jī)存取結(jié)構(gòu)。2.2.1 2.2.1 順序表順序表順序表的尋址公式順序表的尋址公式9 三、順序表類型定義三、順序表類型定義用數(shù)組用數(shù)組 由于由于C C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。又

9、因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線性表的元素之外，類型來(lái)描述順序表。又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來(lái)表示線性表的長(zhǎng)度屬性，所以我們順序表還應(yīng)該用一個(gè)變量來(lái)表示線性表的長(zhǎng)度屬性，所以我們用結(jié)用結(jié)構(gòu)類型來(lái)定義順序表類型構(gòu)類型來(lái)定義順序表類型。 # define maxsize 100 /* maxsize稱為順序表的容量稱為順序表的容量 */ /*表空間的大小可根據(jù)實(shí)際需要而定，這里假設(shè)為表空間的大小可根據(jù)實(shí)際需要而定，這里假設(shè)為100 */ typedef struct /*結(jié)構(gòu)類型結(jié)構(gòu)類型*/ datatype datamaxsize ; /*存儲(chǔ)空間存儲(chǔ)空間*/ int

10、last ; /*當(dāng)前線性表的長(zhǎng)度當(dāng)前線性表的長(zhǎng)度*/ sqlist ;順序表類型順序表類型注：注：由于由于C C語(yǔ)言中向量的下標(biāo)從語(yǔ)言中向量的下標(biāo)從0 0開(kāi)始，所以若開(kāi)始，所以若L L是是sqlistsqlist類型類型的順序表，則線性表的開(kāi)始結(jié)點(diǎn)的順序表，則線性表的開(kāi)始結(jié)點(diǎn)a a1 1和終端結(jié)點(diǎn)和終端結(jié)點(diǎn)a an n分別存儲(chǔ)在分別存儲(chǔ)在L.data0L.data0和和L.dataL.last-1L.dataL.last-1中。中。 2.2.1 2.2.1 順序表順序表10四、順序表的特點(diǎn)四、順序表的特點(diǎn) 順序表是用向量實(shí)現(xiàn)的線性表，向量的下標(biāo)可順序表是用向量實(shí)現(xiàn)的線性表，向量的下標(biāo)可以看作

11、結(jié)點(diǎn)的相對(duì)地址。因此順序表的的特點(diǎn)是：以看作結(jié)點(diǎn)的相對(duì)地址。因此順序表的的特點(diǎn)是： 邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。 2.2.1 2.2.1 順序表順序表11問(wèn)題：?jiǎn)栴}：在表的第在表的第i個(gè)元素前，插入一個(gè)新元素個(gè)元素前，插入一個(gè)新元素x。(1in+1) 即使：即使： (a1，a i-1，ai，an) （長(zhǎng)度（長(zhǎng)度=n）解決方法解決方法： 從表中從表中最后一個(gè)元素最后一個(gè)元素開(kāi)始到開(kāi)始到第第i個(gè)元素個(gè)元素，依次，依次后移后移一一 個(gè)位置，空出插入位置；個(gè)位置，空出插入位置； 插入新元素，即插入新元素，即x置入空位；置入空位； 表長(zhǎng)加表長(zhǎng)加1。變成變成 (a1

12、，a i-1，x，ai，an) （長(zhǎng)度（長(zhǎng)度=n+1）1、順序表的插入運(yùn)算、順序表的插入運(yùn)算注意：注意：C語(yǔ)言中的數(shù)組下標(biāo)從語(yǔ)言中的數(shù)組下標(biāo)從“0”開(kāi)始，因此，若開(kāi)始，因此，若L是是sqlist類型的順類型的順序表，則序表，則表中第表中第i個(gè)元素是個(gè)元素是L.datai-1。2.2.2 基本運(yùn)算在順序表上的實(shí)現(xiàn)基本運(yùn)算在順序表上的實(shí)現(xiàn)12 void insert_sqlist (sqlist L, datatype x , int i ) /* 在順序表在順序表L中第中第i個(gè)元素前插入新的元素個(gè)元素前插入新的元素x */ /* i的合法值為的合法值為1iL.last+1 */ if ( L.l

13、ast=maxsize-1) /*當(dāng)前存儲(chǔ)空間已滿當(dāng)前存儲(chǔ)空間已滿*/ error(“表滿表滿”) ； if ( i L.last+1 ) error(“非法位置非法位置”) ； /* i值不合法值不合法*/ for ( j = L.last ; j = i ; j- - ) L.dataj = L.dataj-1 ; /*元素后移元素后移*/ L.datai1 = x ; /* 插入新元素插入新元素*/ L.last = L.last + 1 ; /* 表長(zhǎng)增表長(zhǎng)增1*/ 順序表的插入算法：（注意順序表的插入算法：（注意C語(yǔ)言數(shù)組下標(biāo)是從語(yǔ)言數(shù)組下標(biāo)是從0開(kāi)始）開(kāi)始）2.2.2 2.2.2

14、基本運(yùn)算在順序表上的實(shí)基本運(yùn)算在順序表上的實(shí)現(xiàn)現(xiàn)13解決方法：解決方法： （長(zhǎng)度（長(zhǎng)度=n）（長(zhǎng)度（長(zhǎng)度=n-1）變成變成 2.2.2 2.2.2 基本運(yùn)算在順序表上的實(shí)基本運(yùn)算在順序表上的實(shí)現(xiàn)現(xiàn)14 void delete_sqlist (sqlist L , int i ) /*在順序表在順序表L中刪除第中刪除第i個(gè)元素個(gè)元素*/ /* i的合法值為的合法值為1iL.last */ if ( i L.last ) /* i值不合法值不合法*/ error(“非法位置非法位置”) ； for ( j = i +1; j =L.last ; j+ ) L.dataj-2 = L.dataj-1

15、 ; /*元素前移元素前移*/ L.last = L.last - 1 ; /* 表長(zhǎng)減表長(zhǎng)減1*/ 順序表的刪除算法：順序表的刪除算法：2.2.2 2.2.2 基本運(yùn)算在順序表上的實(shí)基本運(yùn)算在順序表上的實(shí)現(xiàn)現(xiàn)15 int locate_ sqlist (sqlist L ; datatype x ) i = 1 ; while ( i = L.last & L.data i-1 != x ) +i ; if ( idata的值的值p指針?biāo)附Y(jié)點(diǎn)的指針?biāo)附Y(jié)點(diǎn)的data域的值域的值 p-next的值的值結(jié)點(diǎn)結(jié)點(diǎn)p的后繼結(jié)點(diǎn)的地址的后繼結(jié)點(diǎn)的地址 幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：282.3.2 單鏈

16、表的簡(jiǎn)單操作單鏈表的簡(jiǎn)單操作 1 1、初始化、初始化 lklist initiate_lklist（）（） /*建立一個(gè)帶表頭結(jié)點(diǎn)的空單鏈表建立一個(gè)帶表頭結(jié)點(diǎn)的空單鏈表*/ t= malloc ( sizeof( struct node ) ); /*生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)t*/ t-next = NULL; return t ; 建立一個(gè)空的單鏈表，空的單鏈表由一個(gè)頭指針建立一個(gè)空的單鏈表，空的單鏈表由一個(gè)頭指針 和一個(gè)頭結(jié)點(diǎn)組成。和一個(gè)頭結(jié)點(diǎn)組成。292 2、求表長(zhǎng)、求表長(zhǎng)求單鏈表中所含元素結(jié)點(diǎn)的個(gè)數(shù)。求單鏈表中所含元素結(jié)點(diǎn)的個(gè)數(shù)。 int length_lklist（lklist head

17、） /*求帶表頭結(jié)點(diǎn)的單鏈表求帶表頭結(jié)點(diǎn)的單鏈表head的長(zhǎng)度的長(zhǎng)度*/ p=head; j=0; while (p-next != NULL) p=p-next; j=j+1; return (j) ; 303、按序號(hào)查找運(yùn)算、按序號(hào)查找運(yùn)算問(wèn)題：?jiǎn)栴}：在單鏈表中查第在單鏈表中查第i個(gè)數(shù)據(jù)元素，存在則送其個(gè)數(shù)據(jù)元素，存在則送其 結(jié)點(diǎn)地址；否則返回空。結(jié)點(diǎn)地址；否則返回空。分析：分析： 順鏈走到第順鏈走到第i個(gè)結(jié)點(diǎn)，有兩種可能：個(gè)結(jié)點(diǎn)，有兩種可能： 鏈表中無(wú)第鏈表中無(wú)第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i表長(zhǎng)表長(zhǎng))，查找失敗，返回空指針；，查找失敗，返回空指針；鏈表中有第鏈表中有第i個(gè)結(jié)點(diǎn)，則返回該結(jié)點(diǎn)的指針。

18、個(gè)結(jié)點(diǎn)，則返回該結(jié)點(diǎn)的指針。注：注：在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i i，也不能象順序，也不能象順序表中那樣直接按序號(hào)表中那樣直接按序號(hào)i i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域順鏈域nextnext逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i i個(gè)結(jié)點(diǎn)為止。個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。31 lklist find_lklist ( lklist head, int i ) /*在帶表頭結(jié)點(diǎn)的單鏈表在帶表頭結(jié)點(diǎn)的單鏈表L中，查找第中，查找第i個(gè)元素結(jié)點(diǎn)個(gè)元素

19、結(jié)點(diǎn)*/ /*若找到則返回其指針，否則返回空若找到則返回其指針，否則返回空NULL*/ p = head ; /*初始化初始化*/ j = 0 ; /* j為計(jì)數(shù)器為計(jì)數(shù)器,變量變量j的值始終是的值始終是p指結(jié)點(diǎn)的序號(hào)指結(jié)點(diǎn)的序號(hào)*/ while ( p-next!=NULL & jnext ; j+ ; /*順指針向后查找，直到順指針向后查找，直到p指向第指向第i個(gè)元素或已到尾結(jié)點(diǎn)個(gè)元素或已到尾結(jié)點(diǎn)*/ if ( j=i ) return (p) ; /*找到，返回其指針找到，返回其指針*/ else return (NULL); /*未找到，返回空指針未找到，返回空指針*/ 單鏈表

20、的按序號(hào)查找算法：?jiǎn)捂湵淼陌葱蛱?hào)查找算法：322.3.3 基本運(yùn)算在單鏈表上的實(shí)現(xiàn)基本運(yùn)算在單鏈表上的實(shí)現(xiàn) 1、定位運(yùn)算、定位運(yùn)算單鏈表按值查找單鏈表按值查找問(wèn)題：?jiǎn)栴}： 在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值x x 的結(jié)點(diǎn)，若有的話，則返回首次找到的其值的結(jié)點(diǎn)，若有的話，則返回首次找到的其值 為為x x的結(jié)點(diǎn)的序號(hào)；否則返回的結(jié)點(diǎn)的序號(hào)；否則返回0 0。分析：分析： 順鏈查找值為順鏈查找值為x的結(jié)點(diǎn)，有兩種可能：的結(jié)點(diǎn)，有兩種可能： 鏈表中無(wú)值為鏈表中無(wú)值為x 的結(jié)點(diǎn)，查找失敗，返回的結(jié)點(diǎn)，查找失敗，返回0；鏈表中有值為鏈表中有值為x的結(jié)點(diǎn)，則返回該結(jié)點(diǎn)的序

21、號(hào)。的結(jié)點(diǎn)，則返回該結(jié)點(diǎn)的序號(hào)。33 查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值x x作比較。其算法如下：作比較。其算法如下： int locate_lklist ( lklist head, datatype x ) /*在帶表頭結(jié)點(diǎn)的單鏈表在帶表頭結(jié)點(diǎn)的單鏈表L中，查找第一個(gè)值為中，查找第一個(gè)值為x的結(jié)點(diǎn)序號(hào)的結(jié)點(diǎn)序號(hào)*/ /*不存在這種結(jié)點(diǎn)則返回不存在這種結(jié)點(diǎn)則返回0*/ p = head; /*初始化初始化*/ j=0； /* j為計(jì)數(shù)器為計(jì)數(shù)器,變量變量j的值始終是的值始終是p指結(jié)點(diǎn)的序號(hào)指結(jié)點(diǎn)的序號(hào)*/ while

22、( p-next!=NULL & p-data!=x ) p = pnext ; /*順指針向后查找，直到找到或已到尾結(jié)點(diǎn)順指針向后查找，直到找到或已到尾結(jié)點(diǎn)*/ j+; if (p-data=x ) return (j) ; / /* *找到，返回其序號(hào)找到，返回其序號(hào)* */ / else return (0); / /* *未找到，返回未找到，返回0 0* */ / 單鏈表的按值查找算法：?jiǎn)捂湵淼陌粗挡檎宜惴ǎ?4 插入運(yùn)算是將值為插入運(yùn)算是將值為x x的新結(jié)點(diǎn)插入到表的第的新結(jié)點(diǎn)插入到表的第i i個(gè)結(jié)點(diǎn)的位置上，個(gè)結(jié)點(diǎn)的位置上，即插入到即插入到a ai-1i-1與與a ai i

23、之間。因此，我們必須之間。因此，我們必須首先首先找到找到a ai-1i-1的存儲(chǔ)位置的存儲(chǔ)位置p p，然后然后生成一個(gè)數(shù)據(jù)域?yàn)樯梢粋€(gè)數(shù)據(jù)域?yàn)閤 x的新結(jié)點(diǎn)的新結(jié)點(diǎn)* *s s，并令結(jié)點(diǎn)，并令結(jié)點(diǎn)* *p p的指針域指向新結(jié)的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)a ai i。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)a ai-1i-1，x x和和a ai i之之間的邏輯關(guān)系的變化，即：間的邏輯關(guān)系的變化，即：2、單鏈表的插入運(yùn)算、單鏈表的插入運(yùn)算問(wèn)題：?jiǎn)栴}：在單鏈表的第在單鏈表的第i個(gè)元素位置前插入新元素個(gè)元素位置前插入新元素x。 分析：分析： 在鏈表第在鏈表第i個(gè)元素前

24、插入元素個(gè)元素前插入元素x，需做工作：，需做工作：順鏈尋找第順鏈尋找第 i - 1 個(gè)元素結(jié)點(diǎn)個(gè)元素結(jié)點(diǎn)p：找到：找到： 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s 在第在第 i - 1 和第和第 i 個(gè)元素結(jié)點(diǎn)間個(gè)元素結(jié)點(diǎn)間 插入新結(jié)點(diǎn)插入新結(jié)點(diǎn)s（即修改兩條鏈）；（即修改兩條鏈）；未找到：輸入出錯(cuò)信息。未找到：輸入出錯(cuò)信息。35 void insert_lklist ( lklist head, datatype x, int i ) /*在帶頭結(jié)點(diǎn)的單鏈表在帶頭結(jié)點(diǎn)的單鏈表head的第的第i個(gè)元素位置前插入新元素個(gè)元素位置前插入新元素x*/ p = head ; j = 0 ; while ( p-next

25、!=NULL & jnext ; j = j+1 ; /*順鏈尋找第順鏈尋找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ if ( jdata = x ; snext = pnext; /*新結(jié)點(diǎn)插入鏈表中新結(jié)點(diǎn)插入鏈表中*/ pnext = s ; 單鏈表的插入算法：?jiǎn)捂湵淼牟迦胨惴ǎ?6 刪除運(yùn)算是將表的第刪除運(yùn)算是將表的第i個(gè)元素結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)個(gè)元素結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn) a i-1的指針域的指針域next中，所以我中，所以我們必須首先找到們必須首先找到a i-1的存儲(chǔ)位置的存儲(chǔ)位置p。然后令。然后令pnext指向指向a

26、i的直接的直接后繼結(jié)點(diǎn)，即把后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸的空間，將其歸還給還給“存儲(chǔ)池存儲(chǔ)池”。即：即：3、單鏈表的刪除運(yùn)算、單鏈表的刪除運(yùn)算問(wèn)題：?jiǎn)栴}：在單鏈表中刪除第在單鏈表中刪除第i個(gè)數(shù)據(jù)元素。個(gè)數(shù)據(jù)元素。 分析：分析： 在鏈表中刪除第在鏈表中刪除第i個(gè)元素結(jié)點(diǎn)，需做工作：個(gè)元素結(jié)點(diǎn)，需做工作：順鏈尋找第順鏈尋找第 i - 1 個(gè)元素結(jié)點(diǎn)個(gè)元素結(jié)點(diǎn)p：找到：找到： 第第 i 個(gè)元素結(jié)點(diǎn)存在，則從鏈表中摘除，并個(gè)元素結(jié)點(diǎn)存在，則從鏈表中摘除，并 將之送將之送 回系統(tǒng)；回系統(tǒng)；未找到：刪除位置不合理，輸入出錯(cuò)信息。未找到：刪除位置不合理

27、，輸入出錯(cuò)信息。37 void delete_lklist ( lklist head, int i ) /*在帶頭結(jié)點(diǎn)的單鏈表在帶頭結(jié)點(diǎn)的單鏈表head中刪除第中刪除第i個(gè)元素結(jié)點(diǎn)個(gè)元素結(jié)點(diǎn)*/ p = head ; j = 0 ; while ( p-next!=NULL & jnext ; j = j+1 ; /*順鏈尋找第順鏈尋找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ if ( p-next!=NULL &j=i-1 ) q=p-next ; /*q指向第指向第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ pnext = qnext; /*從表刪除結(jié)點(diǎn)從表刪除結(jié)點(diǎn)q*/ free ( q ) ; /*釋放結(jié)點(diǎn)

28、釋放結(jié)點(diǎn)q*/ else error (“第第i個(gè)結(jié)點(diǎn)不存在個(gè)結(jié)點(diǎn)不存在”) 單鏈表的刪除算法：?jiǎn)捂湵淼膭h除算法：38 設(shè)單鏈表的長(zhǎng)度為設(shè)單鏈表的長(zhǎng)度為n n，則刪去第，則刪去第i i個(gè)結(jié)點(diǎn)僅當(dāng)個(gè)結(jié)點(diǎn)僅當(dāng)1in1in時(shí)是合法的。注意，當(dāng)時(shí)是合法的。注意，當(dāng)i=n+1i=n+1時(shí)，雖然時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨* *p p存在并存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)* *p p存在存在（即（即p!=NULLp!=NULL）且）且* *p p

29、不是終端結(jié)點(diǎn)不是終端結(jié)點(diǎn) （即（即p pnext!=NULLnext!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)）時(shí)，才能確定被刪結(jié)點(diǎn)存在。存在。 顯然此算法的時(shí)間復(fù)雜度也是顯然此算法的時(shí)間復(fù)雜度也是O(n)O(n)。 從上面的討論可以看出，從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。391. 已知一個(gè)單鏈表中，指針已知一個(gè)單鏈表中，指針q指向指針指向指針p的前趨結(jié)點(diǎn)，若在指針的前趨結(jié)點(diǎn)，若在指針q所指所指 結(jié)點(diǎn)和指針結(jié)點(diǎn)和指針p所指結(jié)點(diǎn)之間插入指針?biāo)附Y(jié)點(diǎn)之間插入指針s所指結(jié)點(diǎn)，則需執(zhí)行（所指結(jié)點(diǎn)，則需執(zhí)行（ ） Aq

30、next=s；pnext=s； B. qnext=s；snext=p； C. qnext=s；qnext=p； D. qnext=s；snext=q； 2. 在一個(gè)單鏈表中，若在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除p所指結(jié)點(diǎn)的所指結(jié)點(diǎn)的 后繼結(jié)點(diǎn)的正確操作是后繼結(jié)點(diǎn)的正確操作是( ) A. p=p-next B. p-next=p-next C. p-next=p-next-next D. p-next=p3. 對(duì)于單鏈表，以下說(shuō)法正確的是（對(duì)于單鏈表，以下說(shuō)法正確的是（ ） A. 存儲(chǔ)空間必須連續(xù)存儲(chǔ)空間必須連續(xù) B. 可以方便、迅速地存取表中任一元素可

31、以方便、迅速地存取表中任一元素 C. 插入和刪除運(yùn)算比順序表的效率高插入和刪除運(yùn)算比順序表的效率高 D. 無(wú)需為表示元素間的邏輯關(guān)系而增加額外的存儲(chǔ)空間無(wú)需為表示元素間的邏輯關(guān)系而增加額外的存儲(chǔ)空間4. 在單鏈表的一個(gè)結(jié)點(diǎn)中有幾個(gè)指針？（在單鏈表的一個(gè)結(jié)點(diǎn)中有幾個(gè)指針？（ ） A.0 B. 1 C. 2 D.3想一想想一想請(qǐng)你給出答案請(qǐng)你給出答案40 尾插法建立單鏈表尾插法建立單鏈表 該方法從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新該方法從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，直到讀

32、入結(jié)束標(biāo)志新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，直到讀入結(jié)束標(biāo)志為止。為止。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針為此必須增加一個(gè)尾指針p p，使其始終指向當(dāng)前鏈表的，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。尾結(jié)點(diǎn)。2.4 其它運(yùn)算在單鏈表上的實(shí)現(xiàn)其它運(yùn)算在單鏈表上的實(shí)現(xiàn)1 1、建立單鏈表運(yùn)算、建立單鏈表運(yùn)算41 lklist create_lklist（）（） /*順位序輸入若干數(shù)據(jù)元素順位序輸入若干數(shù)據(jù)元素(以以-1為結(jié)束為結(jié)束)，建立帶表頭結(jié)點(diǎn)的單鏈表，建立帶表頭結(jié)點(diǎn)的單鏈表*/ head=malloc( sizeof( struct nod

33、e) ) ; p = head ; /*p用于指向生成鏈表的當(dāng)前表尾結(jié)點(diǎn)用于指向生成鏈表的當(dāng)前表尾結(jié)點(diǎn)*/ scanf ( “%d”,&x ) ; while ( x!= -1 ) q = malloc( sizeof( struct node) ) ; /*生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)*/ q-data = x ; p-next = q ; /*新結(jié)點(diǎn)插入到表尾新結(jié)點(diǎn)插入到表尾*/ p = q ; /*修改尾指針指向新的表尾修改尾指針指向新的表尾*/ scanf ( “%d”,&x ) ; /*輸入下一個(gè)元素值輸入下一個(gè)元素值*/ p-next=NULL ; /*置尾結(jié)點(diǎn)標(biāo)志置尾結(jié)點(diǎn)

34、標(biāo)志*/ return (head) ; 尾插法建立單鏈表算法：尾插法建立單鏈表算法：42 問(wèn)題：設(shè)鏈表問(wèn)題：設(shè)鏈表la中的數(shù)據(jù)元素遞增有序。編寫(xiě)算法，中的數(shù)據(jù)元素遞增有序。編寫(xiě)算法， 將元素將元素x插入到有序鏈表的適當(dāng)位置上，以保持插入到有序鏈表的適當(dāng)位置上，以保持 鏈表的遞增有序性。鏈表的遞增有序性。 算法思想：算法思想： （1 1）順鏈找到插入位置，即順序找到第一個(gè)結(jié)點(diǎn)數(shù)據(jù)順鏈找到插入位置，即順序找到第一個(gè)結(jié)點(diǎn)數(shù)據(jù) 域值域值x的結(jié)點(diǎn)的結(jié)點(diǎn)p，并保留其前趨結(jié)點(diǎn)，并保留其前趨結(jié)點(diǎn)q； （2）生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s s，其數(shù)據(jù)域置為，其數(shù)據(jù)域置為x x； （3 3）在）在q q和和p p結(jié)點(diǎn)之

35、間插入新結(jié)點(diǎn)結(jié)點(diǎn)之間插入新結(jié)點(diǎn)s s，即修改二條鏈。，即修改二條鏈。2 2、 有序鏈表的插入有序鏈表的插入43void insert_linllist ( lklist La ; datatype x ) /*在有序鏈表在有序鏈表La（帶表頭結(jié)點(diǎn)）中按序插入元素（帶表頭結(jié)點(diǎn)）中按序插入元素x*/ LNode *p, *s, *q ; s = malloc ( sizeof( struct node ) ) ; s-data = x ; q = La ; /*為為s結(jié)點(diǎn)尋找插入位置，結(jié)點(diǎn)尋找插入位置，p指向待比較的結(jié)點(diǎn)指向待比較的結(jié)點(diǎn)*/ p = q-next ; /*q指向指向p的前驅(qū)結(jié)點(diǎn)的前

36、驅(qū)結(jié)點(diǎn)*/ while ( p!=NULL & p-datanext; s-next = p ; q-next = s ; 有序鏈表的插入算法：有序鏈表的插入算法：441、定義：、定義：仍是單鏈表，只是在最后一個(gè)結(jié)點(diǎn)的鏈域中不仍是單鏈表，只是在最后一個(gè)結(jié)點(diǎn)的鏈域中不是放是放“NULL”，而是放上頭結(jié)點(diǎn)的地址，形成環(huán)形。，而是放上頭結(jié)點(diǎn)的地址，形成環(huán)形。表形式：表形式：2、特點(diǎn)：、特點(diǎn)： 1）環(huán)形：可以從表中任一結(jié)點(diǎn)開(kāi)始訪問(wèn)到其它任意結(jié)點(diǎn)；）環(huán)形：可以從表中任一結(jié)點(diǎn)開(kāi)始訪問(wèn)到其它任意結(jié)點(diǎn)； 2）不必提供頭指針，也可找到表頭結(jié)點(diǎn)，即表的開(kāi)始位置；）不必提供頭指針，也可找到表頭結(jié)點(diǎn)，即表的開(kāi)

37、始位置； 3）可簡(jiǎn)化某些運(yùn)算。）可簡(jiǎn)化某些運(yùn)算。(空表空表,即即h-next=h)h2.5.1 循環(huán)鏈表循環(huán)鏈表 a1 an .h(非空表非空表)2.5 其它鏈表其它鏈表453、循環(huán)鏈表的運(yùn)算（插、刪、查）：、循環(huán)鏈表的運(yùn)算（插、刪、查）： 與單鏈表的運(yùn)算基本一致，差別只是循環(huán)條件的與單鏈表的運(yùn)算基本一致，差別只是循環(huán)條件的判別。判別。 由于循環(huán)鏈表中沒(méi)有由于循環(huán)鏈表中沒(méi)有NULLNULL指針，故涉及查找操作指針，故涉及查找操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p p或或p-nextp-next是否為空，而是判斷它們是否等于某一指定是否為空，而是判

38、斷它們是否等于某一指定指針，如頭指針指針，如頭指針。 在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便. .如果如果改用尾指針改用尾指針rearrear來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)a a1 1和和終端結(jié)點(diǎn)終端結(jié)點(diǎn)a an n都很方便，它們的存儲(chǔ)位置分別是都很方便，它們的存儲(chǔ)位置分別是(rear-(rear-next)-nextnext)-next和和rearrear，顯然，查找時(shí)間都是，顯然，查找時(shí)間都是O(1)O(1)

39、。因此，因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。實(shí)際中多采用尾指針表示單循環(huán)鏈表。46例、在鏈表上實(shí)現(xiàn)將兩個(gè)線性表例、在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1，a2，a3，an)和和(b1，b2，b3，bn)鏈接成一個(gè)線性表的運(yùn)算（設(shè)線鏈接成一個(gè)線性表的運(yùn)算（設(shè)線性表分別用帶尾指針的循環(huán)鏈表表示）。性表分別用帶尾指針的循環(huán)鏈表表示）。LinkList connect(LinkList R1，LinkList R2) p = R1-next ; R1-next = R2-next-next ; free(R2-next) ; R2-next = p ; return(R2) ; 47任給一點(diǎn)任給一點(diǎn)P P

40、，線性鏈表：只能找到其后繼結(jié)點(diǎn)，由線性鏈表：只能找到其后繼結(jié)點(diǎn)，由P P得不到其前趨結(jié)點(diǎn)。得不到其前趨結(jié)點(diǎn)。循環(huán)鏈表：由循環(huán)鏈表：由P P其前趨、后繼均能得到，但查其前趨、后繼均能得到，但查P P的前趨要兜的前趨要兜 圈子。圈子。 一、定義一、定義 在鏈表中，每個(gè)結(jié)點(diǎn)都有二個(gè)鏈域在鏈表中，每個(gè)結(jié)點(diǎn)都有二個(gè)鏈域 為為方便查結(jié)點(diǎn)的前趨方便查結(jié)點(diǎn)的前趨雙向循環(huán)鏈表雙向循環(huán)鏈表prior data next 結(jié)點(diǎn)形式：結(jié)點(diǎn)形式： 前趨指針前趨指針指向直接前趨結(jié)點(diǎn)指向直接前趨結(jié)點(diǎn) 后繼指針后繼指針指向直接后繼結(jié)點(diǎn)指向直接后繼結(jié)點(diǎn)2.5.2 雙向循環(huán)鏈表雙向循環(huán)鏈表 48二、示意圖：二、示意圖： （見(jiàn)黑板

41、）（見(jiàn)黑板）三、特點(diǎn)：三、特點(diǎn)： 對(duì)任一結(jié)點(diǎn)，找其前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)都很容易；對(duì)任一結(jié)點(diǎn)，找其前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)都很容易； 所需空間增加。所需空間增加。四、類型定義：四、類型定義：typedef struct dnode datatype data ; struct dnode *prior, *next ; *dlklist ; 491、摘除操作、摘除操作 p指向待刪結(jié)點(diǎn)，則從雙向鏈表中摘除結(jié)點(diǎn)指向待刪結(jié)點(diǎn)，則從雙向鏈表中摘除結(jié)點(diǎn)p 需修改二條鏈。需修改二條鏈。五、雙向循環(huán)鏈表的運(yùn)算五、雙向循環(huán)鏈表的運(yùn)算2、插入操作、插入操作 要在要在p指向結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)指向結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)q

42、，則，則 需修改四條鏈。需修改四條鏈。注意：注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。502.6 順序表和鏈表的比較順序表和鏈表的比較51想一想想一想1. 為了最快地對(duì)線性結(jié)構(gòu)的數(shù)據(jù)進(jìn)行某數(shù)據(jù)元素的讀取操作，則其為了最快地對(duì)線性結(jié)構(gòu)的數(shù)據(jù)進(jìn)行某數(shù)據(jù)元素的讀取操作，則其 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用( ) A單鏈表單鏈表 B雙鏈表雙鏈表 C循環(huán)鏈表循環(huán)鏈表 D順序表順序表2. 在一個(gè)單鏈表中，若在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則

43、在結(jié)所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則在結(jié) 點(diǎn)點(diǎn)p、q之間插入結(jié)點(diǎn)之間插入結(jié)點(diǎn)s的正確操作是的正確操作是( ) A. s-next=q；p-next=s B. p-next=q；p-next=s C. s-next=q-next；p-next=s D. s-next=q-next；p-next=s-next3. 若線性表最常用的操作是存取第若線性表最常用的操作是存取第i個(gè)元素及其前趨的值，那么最節(jié)省個(gè)元素及其前趨的值，那么最節(jié)省 操作時(shí)間的存儲(chǔ)方式是（操作時(shí)間的存儲(chǔ)方式是（ ） A. 單鏈表單鏈表 B. 雙鏈表雙鏈表 C. 單循環(huán)鏈表單循環(huán)鏈表 D. 順序表順序表4. 順序表中有順序表中有20個(gè)元素，第一

44、個(gè)元素的地址為個(gè)元素，第一個(gè)元素的地址為300，且每個(gè)元素占一個(gè)，且每個(gè)元素占一個(gè) 字節(jié)，則第字節(jié)，則第16個(gè)元素的存儲(chǔ)地址為（個(gè)元素的存儲(chǔ)地址為（ ） A. 314 B. 315 C. 316 D. 3175. 若某線性表中數(shù)據(jù)需經(jīng)常進(jìn)行插入刪除操作，則該線性表的存儲(chǔ)結(jié)構(gòu)若某線性表中數(shù)據(jù)需經(jīng)常進(jìn)行插入刪除操作，則該線性表的存儲(chǔ)結(jié)構(gòu) 宜采用下列哪種方式宜采用下列哪種方式?（ ） A. 順序存儲(chǔ)順序存儲(chǔ) B. 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) C. 索引存儲(chǔ)索引存儲(chǔ) D. 散列存儲(chǔ)散列存儲(chǔ)請(qǐng)你給出答案請(qǐng)你給出答案52 串串由零個(gè)或多個(gè)字符組成的有限序列。由零個(gè)或多個(gè)字符組成的有限序列。 記作記作: S=: S=

45、“a a1 1a a2 2a a3 3a an n”， 其中其中: S : S 是是串名串名， 雙引號(hào)括起來(lái)的字符序列是雙引號(hào)括起來(lái)的字符序列是串值串值； a ai i(1in)(1in)可以是字母、數(shù)字或其它字符；可以是字母、數(shù)字或其它字符；串的長(zhǎng)度串的長(zhǎng)度串中所包含的字符個(gè)數(shù)。串中所包含的字符個(gè)數(shù)?？沾沾L(zhǎng)度為零的串，它不包含任何字符。長(zhǎng)度為零的串，它不包含任何字符?？瞻状瞻状畠H由一個(gè)或多個(gè)空格組成的串。僅由一個(gè)或多個(gè)空格組成的串。 注意：注意：空串和空白串的不同空串和空白串的不同，例如，例如“ ”和和“”“”分別表分別表示長(zhǎng)度為示長(zhǎng)度為1 1的空白串和長(zhǎng)度為的空白串和長(zhǎng)度為0 0的空

46、串。的空串。2.7 串串2.7.1 串的基本概念串的基本概念53兩串相等兩串相等當(dāng)且僅當(dāng)兩個(gè)串的值相等，即串和長(zhǎng)度相當(dāng)且僅當(dāng)兩個(gè)串的值相等，即串和長(zhǎng)度相 等且各個(gè)對(duì)應(yīng)位置上的字符都相等。等且各個(gè)對(duì)應(yīng)位置上的字符都相等。子串子串串中任意個(gè)連續(xù)字符組成的子序列稱為該串中任意個(gè)連續(xù)字符組成的子序列稱為該串串 的子串；的子串；主串主串包含子串的串稱包含子串的串稱為主串為主串。子串在主串中的位置子串在主串中的位置為子串在主串中首次出現(xiàn)時(shí)，為子串在主串中首次出現(xiàn)時(shí)，第一個(gè)字符在主串中的序號(hào)，定義為第一個(gè)字符在主串中的序號(hào)，定義為子串在主串中子串在主串中的序號(hào)（或位置）的序號(hào)（或位置）。例如：例如：設(shè)設(shè)A

47、A和和B B分別為分別為 A=A=“This is a stringThis is a string” B= B=“isis”則則B B是是A A的子串，的子串，A A為主串。為主串。B B在在A A中出現(xiàn)了兩次，其中首中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)的主串位置是次出現(xiàn)所對(duì)應(yīng)的主串位置是3 3。因此，稱。因此，稱B B在在A A中的序中的序號(hào)（或位置）為號(hào)（或位置）為3 3。 54 對(duì)于串的基本操作，許多高級(jí)語(yǔ)言均提供了相應(yīng)的運(yùn)算或?qū)τ诖幕静僮鳎S多高級(jí)語(yǔ)言均提供了相應(yīng)的運(yùn)算或 標(biāo)準(zhǔn)庫(kù)函數(shù)來(lái)實(shí)現(xiàn)。標(biāo)準(zhǔn)庫(kù)函數(shù)來(lái)實(shí)現(xiàn)。 1）串賦值串賦值 AGGIGN(S，T) 2）判等函數(shù)判等函數(shù) EQUAL

48、(S，T) 3）求串長(zhǎng)求串長(zhǎng) LENGTH（S） 2.7.2 串的基本運(yùn)算串的基本運(yùn)算4）串聯(lián)接串聯(lián)接 CONCAT(S，T) 將串將串T連接在連接在S的的 末尾，組成一個(gè)新的串。末尾，組成一個(gè)新的串。 例：例：a=“BEI” b=“JING” CONCAT( a, b ) ; /結(jié)果為結(jié)果為“BINJING”555）求子串求子串 SUBSTR（S, i, j） 返回串返回串S的的 第第i個(gè)字符起，長(zhǎng)為個(gè)字符起，長(zhǎng)為j的子串。的子串。 例：例：d=“BEIJING” t=SUBSTR( d, 1, 3 ); /t為為“BEI” t=SUBSTR( d, 4, 4 ); /則則t為為“JING”

49、568）定位操作定位操作INDEX（S，T）求子串在串中的序號(hào)求子串在串中的序號(hào) 串串T是是S中子串，則結(jié)果為子串中子串，則結(jié)果為子串T的第一個(gè)字的第一個(gè)字 符在串符在串S中的字符序號(hào)；中的字符序號(hào)； 串串T不是不是S中子串，則結(jié)果為中子串，則結(jié)果為0。例：例： a=“BROTHER” b=“ER” m=INDEX（a，b）；）； 則：則：m=？ c=“AABBAB” d=“AB” e=“CD”n1=INDEX (c, d) ; 則：則：n1=? n2=INDEX (c, e) ; 則：則：n2=？（指串中第一個(gè)指串中第一個(gè)d子串的序號(hào)子串的序號(hào)）（串中無(wú)串中無(wú)e子串，則序號(hào)為子串，則序號(hào)為0

50、）579）替換操作替換操作REPLACE（&S，T，V)若若T是是S中的子串，則中的子串，則 以以V代替代替T，否則，否則S不變。不變。( 此運(yùn)算可實(shí)現(xiàn)串的插、刪、改）此運(yùn)算可實(shí)現(xiàn)串的插、刪、改） 例：例： a=“MONDAY” (1) b=“MON” c=“SUN” REPLACE(a, b, c) ; /*a=“SUNDAY”*/ 實(shí)現(xiàn)修改實(shí)現(xiàn)修改 (2) b=“MON” c=“” REPLACE (a, b, c) ; /*a=“DAY” */ 實(shí)現(xiàn)刪除實(shí)現(xiàn)刪除 (3) b=“N” c=“NA” REPLACE (a, b, c) ; /*a=“MONADAY”*/ 實(shí)現(xiàn)插入實(shí)現(xiàn)

51、插入 (4) b=“MAN” c=“FRI” REPLACE (a, b, c) ; /*a不變不變*/ (5) S=“BBABBABBA” T=“AB” V=“C” REPLACE (S, T, V) ; /*S=“BBCBCBA” */ 串串S中所有子串中所有子串T都用都用V置換置換58 因?yàn)榇翘厥獾木€性表，故其存儲(chǔ)結(jié)構(gòu)與線性表因?yàn)榇翘厥獾木€性表，故其存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。只不過(guò)由于組成串的結(jié)點(diǎn)是單個(gè)字的存儲(chǔ)結(jié)構(gòu)類似。只不過(guò)由于組成串的結(jié)點(diǎn)是單個(gè)字符。符。一、串的順序存儲(chǔ)一、串的順序存儲(chǔ) 用一組連續(xù)的存儲(chǔ)單元來(lái)依次存放串中的字符。用一組連續(xù)的存儲(chǔ)單元來(lái)依次存放串中的字符。 順

52、序存儲(chǔ)的串稱為順序存儲(chǔ)的串稱為順序串。順序串。 2.7.3 2.7.3 串的存儲(chǔ)串的存儲(chǔ)串順序存儲(chǔ)的兩種方法串順序存儲(chǔ)的兩種方法非緊縮格式非緊縮格式緊縮格式緊縮格式59 順序串上的插入和刪除操作不方便，需要移動(dòng)大量順序串上的插入和刪除操作不方便，需要移動(dòng)大量的字符。因此，我們可用單鏈表方式來(lái)存儲(chǔ)串值，串的字符。因此，我們可用單鏈表方式來(lái)存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串鏈串。二、串的鏈接存儲(chǔ)二、串的鏈接存儲(chǔ) 為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義

53、為結(jié)點(diǎn)的大小結(jié)點(diǎn)的大小，顯然，當(dāng)結(jié)點(diǎn)大小大于顯然，當(dāng)結(jié)點(diǎn)大小大于 1 1時(shí)，串的長(zhǎng)度不一定正好是時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來(lái)填充最后一個(gè)結(jié)結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來(lái)填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。點(diǎn)，以表示串的終結(jié)。例：見(jiàn)例：見(jiàn)P39 P39 60 問(wèn)題：?jiǎn)栴}：設(shè)順序表設(shè)順序表L中的數(shù)據(jù)元素遞增有序。編寫(xiě)算法，中的數(shù)據(jù)元素遞增有序。編寫(xiě)算法， 將元素將元素x插入到順序表的適當(dāng)位置上，以保持該表插入到順序表的適當(dāng)位置上，以保持該表 的有序性。的有序性。 算法思想：算法思想： （1）查找）查找x在順序表中的插入位置，即在在順序表中的插入位置，即在; ; （2）將

54、順序表中的最后一個(gè)元素到第）將順序表中的最后一個(gè)元素到第i號(hào)元素依次后移號(hào)元素依次后移一一 個(gè)位置，空出插入位置個(gè)位置，空出插入位置; （3）將）將x插入到空位；插入到空位； （4）表長(zhǎng)增）表長(zhǎng)增1。例例1 1、 有序順序表的插入有序順序表的插入2.8 線性表的應(yīng)用線性表的應(yīng)用61void InsertOrderList ( sqlist L , datatype x ) /*將元素將元素x插入到遞增排列的順序表插入到遞增排列的順序表L中中*/ if ( L.last=maxsize) /*當(dāng)前存儲(chǔ)空間已滿當(dāng)前存儲(chǔ)空間已滿*/ error(“表滿表滿”); i = 1 ; if ( i= i

55、; j- - ) L.dataj = L.dataj-1 ; /*元素后移元素后移*/ L.datai1 = x ; /* 插入新元素插入新元素x*/ else L.datai-1 = x ; /*直接插入在表尾直接插入在表尾*/ L.last = L.last + 1 ; /* 表長(zhǎng)增表長(zhǎng)增1*/ 有序順序表的插入算法：有序順序表的插入算法：62 問(wèn)題：?jiǎn)栴}：有順序表有順序表A和和B，其元素均按從小到大的升序，其元素均按從小到大的升序 排列，編寫(xiě)一個(gè)算法將它們合并成一個(gè)順序排列，編寫(xiě)一個(gè)算法將它們合并成一個(gè)順序 表表C，要求，要求C的元素也是從小到大升序排列。的元素也是從小到大升序排列。例例

56、2 2、兩個(gè)有序順序表的合并、兩個(gè)有序順序表的合并 sqlist merge ( sqlist A, sqlist B ) sqlist merge ( sqlist A, sqlist B ) int i,j,k; int i,j,k; i=1; j=1; k=1; i=1; j=1; k=1; while( i=A.last & j=B.last ) while( i=A.last & j=B.last ) if ( A.datai-1 B.dataj-1 ) if ( A.datai-1 B.dataj-1 ) C.datak-1=A.datai-1; i+; k+; C

57、.datak-1=A.datai-1; i+; k+; else else C.datak-1=B.dataj-1; j+; k+; C.datak-1=B.dataj-1; j+; k+; while( i=A.last ) while( i=A.last ) C.datak-1=A.datai-1; i+; k+; C.datak-1=A.datai-1; i+; k+; while( j=B.last ) while( jnext ; while ( p!=NULL ) if ( p-data != x ) n+; p=p-next; return n ; 例例3 3、統(tǒng)計(jì)值為、統(tǒng)計(jì)值為

58、x x的結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)個(gè)數(shù) 問(wèn)題：?jiǎn)栴}：編寫(xiě)一個(gè)函數(shù)編寫(xiě)一個(gè)函數(shù)int count(struct node *head,datatype x) 統(tǒng)計(jì)單鏈表中數(shù)據(jù)域值為統(tǒng)計(jì)單鏈表中數(shù)據(jù)域值為x的結(jié)點(diǎn)個(gè)數(shù)。的結(jié)點(diǎn)個(gè)數(shù)。64 int count ( struct node *head ) /*在以在以head為頭指針的單鏈表中，統(tǒng)計(jì)單鏈表中為頭指針的單鏈表中，統(tǒng)計(jì)單鏈表中*/ /*數(shù)據(jù)域值為數(shù)據(jù)域值為8的結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)個(gè)數(shù)*/ n=0; p=head-next ; while ( p!=NULL ) if ( p-data != 8 ) n+; p=p-next; return n ; 例例4 4、

59、統(tǒng)計(jì)值為、統(tǒng)計(jì)值為8 8的結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)個(gè)數(shù) 問(wèn)題：?jiǎn)栴}：設(shè)某單鏈表中，存在多個(gè)結(jié)點(diǎn)其數(shù)據(jù)值均為設(shè)某單鏈表中，存在多個(gè)結(jié)點(diǎn)其數(shù)據(jù)值均為8， 試編寫(xiě)一算法統(tǒng)計(jì)該類結(jié)點(diǎn)的個(gè)數(shù)。試編寫(xiě)一算法統(tǒng)計(jì)該類結(jié)點(diǎn)的個(gè)數(shù)。 65 問(wèn)題：編寫(xiě)出一個(gè)將問(wèn)題：編寫(xiě)出一個(gè)將單鏈表逆轉(zhuǎn)單鏈表逆轉(zhuǎn)的算法。即將下圖的算法。即將下圖 （）中的鏈表修改成（）的形式。（）中的鏈表修改成（）的形式。 H a1 a2 . an （）（） H an an-1. a1 （b） 例例5 5、單鏈表逆轉(zhuǎn)、單鏈表逆轉(zhuǎn)( (略略) )66方法一：方法一：void reverse_linklist1 ( lklist H ) void revers

60、e_linklist1 ( lklist H ) / /* *對(duì)對(duì)H H所指的單鏈表所指的單鏈表( (不帶表頭結(jié)點(diǎn)不帶表頭結(jié)點(diǎn)) )進(jìn)行逆置進(jìn)行逆置* */ / LNode LNode * *p, p, * *q, q, * *s;s; if(!H|!H-next) return; if(!H|!H-next) return; / /* *若為空表或只有一個(gè)結(jié)點(diǎn)，則返回若為空表或只有一個(gè)結(jié)點(diǎn)，則返回* */ /q = H; q = H; / /* *q q記住第一個(gè)結(jié)點(diǎn)記住第一個(gè)結(jié)點(diǎn)* */ / p = H-next ; p = H-next ; / /* *p p指向當(dāng)前處理結(jié)點(diǎn)指向當(dāng)前處理結(jié)點(diǎn)* */ /while ( p ) while ( p ) s=p-next ; s=p-next ; / /* *保存當(dāng)前處理結(jié)點(diǎn)的后繼保