第2講 線性表及其順序存儲(chǔ)

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)于存儲(chǔ)結(jié)構(gòu)2.1 線性表線性表2.2 順序表順序表A=（a1, a2, ai-1，ai, ai1 ，, an）2.1 線性表線性表1. 定義：定義：n個(gè)（個(gè)（n0）數(shù)據(jù)元素）數(shù)據(jù)元素(結(jié)點(diǎn)結(jié)點(diǎn))的有限序列的有限序列n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)ai的直接前驅(qū)的直接前驅(qū)ai的直接后繼的直接后繼下標(biāo)，是元素的下標(biāo)，是元素的序號(hào)，表示元素序號(hào)，表示元素在表中的位置在表中的位置n為元素總個(gè)為元素總個(gè)數(shù)，即表長(zhǎng)數(shù)，即表長(zhǎng)空表空表終端結(jié)點(diǎn)終端結(jié)點(diǎn)線性表的特性：線

2、性表的特性：邏輯結(jié)構(gòu)是線性結(jié)構(gòu)邏輯結(jié)構(gòu)是線性結(jié)構(gòu)除開(kāi)始結(jié)點(diǎn)外，任何一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)除開(kāi)始結(jié)點(diǎn)外，任何一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)除終端結(jié)點(diǎn)外，任何一個(gè)結(jié)點(diǎn)有且僅有一個(gè)后繼除終端結(jié)點(diǎn)外，任何一個(gè)結(jié)點(diǎn)有且僅有一個(gè)后繼其中其中n n 稱為線性表的表長(zhǎng)稱為線性表的表長(zhǎng)說(shuō)明：(a1，a2，an) 其中數(shù)據(jù)元素ai(1in)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。例例 ：26 個(gè)英文字母組成的英文表個(gè)英文字母組成的英文表 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)2001011810205于春梅于春梅女女 182001級(jí)電信級(jí)電信016班班2001011

3、810260何仕鵬何仕鵬男男 182001級(jí)電信級(jí)電信017班班2001011810284王王 爽爽女女 182001級(jí)通信級(jí)通信011班班2001011810360王亞武王亞武男男 182001級(jí)通信級(jí)通信012班班例：學(xué)生情況登記表例：學(xué)生情況登記表數(shù)據(jù)元素都是學(xué)生記錄數(shù)據(jù)元素都是學(xué)生記錄; 元素間關(guān)系是線性；表長(zhǎng)為元素間關(guān)系是線性；表長(zhǎng)為4數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性；表長(zhǎng)為元素間關(guān)系是線性；表長(zhǎng)為26同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性2. 線性表上的運(yùn)算線性表上的運(yùn)算l 置一個(gè)空表置一個(gè)空表l 建一個(gè)線性表建一個(gè)線性表l 求表長(zhǎng)

4、求表長(zhǎng)l 查找某個(gè)元素查找某個(gè)元素l 插入一個(gè)元素插入一個(gè)元素l 刪除一個(gè)元素刪除一個(gè)元素l 拆分線性表拆分線性表l 合并合并l 排序排序l 2.2 順序表順序表2.2.1 順序表的基本概念及描述順序表的基本概念及描述2.2.2 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)2.2.1 順序表的基本概念及描述順序表的基本概念及描述 線性表的順序存儲(chǔ)稱為順序表線性表的順序存儲(chǔ)稱為順序表1、順序表的定義順序表的定義 用一組用一組連續(xù)的存儲(chǔ)單元連續(xù)的存儲(chǔ)單元（地址連續(xù)）（地址連續(xù)）依次存放線性表的各個(gè)數(shù)據(jù)元素。依次存放線性表的各個(gè)數(shù)據(jù)元素。 即利用數(shù)組技術(shù)存放元素。即利用數(shù)組技術(shù)存放元素。2、順序表的結(jié)點(diǎn)地址計(jì)算順序表的

5、結(jié)點(diǎn)地址計(jì)算l 設(shè)首元素設(shè)首元素a a1 1的存放地址為的存放地址為location(alocation(a1 1) )（稱稱為首地為首地址址），），l 設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為lenlen字節(jié)，字節(jié)，l 則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： loction(ai)= loction(a1)+ len*（i-1） (1in) l 若首元素為若首元素為a a0 0： loction(ai)= loction(a0)+len*i (0in-1) （參見(jiàn)順序表存儲(chǔ)結(jié)構(gòu)示意圖參見(jiàn)順序表存儲(chǔ)結(jié)構(gòu)示意圖）順序表存儲(chǔ)結(jié)構(gòu)示意圖順序表

6、存儲(chǔ)結(jié)構(gòu)示意圖a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在數(shù)組中的下標(biāo)元素在數(shù)組中的下標(biāo)0i-11n-1空閑區(qū)空閑區(qū)ilenloction(a1) = bb + lenb +(i-1)lenb +(n-1)lenb +(MAX-1)lenMAX-1一個(gè)一維數(shù)組，下標(biāo)的范圍是一個(gè)一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組元素用相鄰的到，每個(gè)數(shù)組元素用相鄰的個(gè)字節(jié)個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素元素 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是9 9，則則 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是 113例例1因此

7、：因此：loction( M3 ) = 98 + 5 3 =113解：地址計(jì)算通式為：解：地址計(jì)算通式為：loction(ai)= loction(a0) + len *i1、順序表數(shù)據(jù)類型的定義、順序表數(shù)據(jù)類型的定義(1)定義數(shù)組的體積定義數(shù)組的體積(最多允許的元素個(gè)數(shù)最多允許的元素個(gè)數(shù))#define MAXSIZE 100(2)數(shù)據(jù)元素類型定義為數(shù)據(jù)元素類型定義為datatype如：處理學(xué)生信息如：處理學(xué)生信息typedef struct int n; char name20; int s;datatype;如：處理如：處理 inttypedef int datatype;2.2.2 順

8、序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)(3) 順序表的類型定義順序表的類型定義typedef struct datatype aMAXSIZE; /*存放線性表元素的數(shù)組存放線性表元素的數(shù)組*/ int size; /*表示表示 a中實(shí)際存放元素個(gè)數(shù)中實(shí)際存放元素個(gè)數(shù)(表長(zhǎng)表長(zhǎng))*/ sequence_list; /* 順序表的數(shù)據(jù)類型順序表的數(shù)據(jù)類型sequence_list*/(4) 順序表變量的定義順序表變量的定義sequence_list slt; /*slt為順序表變量為順序表變量*/sequence_list *lp; /*lp為順序表指針變量為順序表指針變量*/結(jié)構(gòu)體變量結(jié)構(gòu)體變量slta(數(shù)組

9、數(shù)組)size (變量變量)slt.aislt.size結(jié)構(gòu)指針結(jié)構(gòu)指針lpa(數(shù)組數(shù)組)size(變量變量)lp-ailp-size本課堂順序表的存儲(chǔ)結(jié)構(gòu)的本課堂順序表的存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下：語(yǔ)言描述如下： #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;l即定義相應(yīng)運(yùn)算的即定義相應(yīng)運(yùn)算的C語(yǔ)言函數(shù)。語(yǔ)言函數(shù)。l定義函數(shù)要確定：定義函數(shù)要確定： 函數(shù)名函數(shù)名 形參形參 返回值返回值傳入量傳入量傳出量傳出量l 出錯(cuò)處理函數(shù)出錯(cuò)處理函數(shù)exi

10、t(1); /*返回返回OS,告知告知OS程序非正常結(jié)束，該函數(shù)定程序非正常結(jié)束，該函數(shù)定義在義在stdlib.h中中*/2、順序表的算法實(shí)現(xiàn)、順序表的算法實(shí)現(xiàn)算法算法2.1 初始化初始化建立一個(gè)空表建立一個(gè)空表空表的表長(zhǎng)為空表的表長(zhǎng)為0，使順序表變量中的，使順序表變量中的size為為0。 函數(shù)形參：須初始化順序表的地址函數(shù)形參：須初始化順序表的地址 返回值：無(wú)返回值：無(wú)算法實(shí)現(xiàn)算法實(shí)現(xiàn)： void init(sequence_list lp) lp-size=0; a(數(shù)組數(shù)組)size(變量變量)lp0算法算法2.2 在表尾插入元素在表尾插入元素即在數(shù)組的即在數(shù)組的size位置插入元素，表

11、長(zhǎng)增位置插入元素，表長(zhǎng)增1。 函數(shù)形參：指定順序表的地址，插入元素函數(shù)形參：指定順序表的地址，插入元素 返回值：無(wú)返回值：無(wú)算法實(shí)現(xiàn)算法實(shí)現(xiàn)： void append(sequence_list lp,datatype x) if(lp-size=MAXSIZE) printf(順序表是滿的順序表是滿的!);exit(1); lp-alp-size=x; lp-size+; 共size個(gè)元素01size-1sizex算法算法2.3 打印表中每個(gè)元素打印表中每個(gè)元素遍歷整個(gè)順序表，輸出元素值。遍歷整個(gè)順序表，輸出元素值。 函數(shù)形參：指定順序表變量函數(shù)形參：指定順序表變量 返回值：無(wú)返回值：無(wú)算法

12、實(shí)現(xiàn)算法實(shí)現(xiàn)： void display(sequence_list slt) int i; if(!slt.size) printf(n順序表是空的順序表是空的!); else for(i=0;islt.size;i+) printf(%5d,slt.ai); 算法算法2.4 判順序表是否為空表判順序表是否為空表判斷表長(zhǎng)是否為判斷表長(zhǎng)是否為0。 函數(shù)形參：指定順序表變量函數(shù)形參：指定順序表變量 返回值：返回值： 1表示空表示空, 0表示非空表示非空 算法實(shí)現(xiàn)算法實(shí)現(xiàn)： int empty(sequence_list slt) return slt.size=0; 遍歷順序表，查找與給定值遍歷

13、順序表，查找與給定值x相同的元素，找到相同的元素，找到后返回元素的下標(biāo)值，沒(méi)找到返回后返回元素的下標(biāo)值，沒(méi)找到返回-1。 函數(shù)形參：指定順序表變量函數(shù)形參：指定順序表變量 被找元素值被找元素值 返回值：若找到返回值：若找到下標(biāo)值下標(biāo)值 若未找到若未找到 -1 遍歷查找的范圍01size-1算法算法2.5 順序表中查找指定值的元素順序表中查找指定值的元素 int find(sequence_list slt,datatype x) int i; for(i=0;islt.size;i+) if(slt.ai=x) return i; return -1; 若datatype是結(jié)構(gòu)類型，不能用“=

14、”直接整體比較，應(yīng)逐一比較結(jié)構(gòu)中每個(gè)成員算法實(shí)現(xiàn)算法實(shí)現(xiàn)： 返回序號(hào)為返回序號(hào)為i的元素值的元素值。 函數(shù)形參：指定順序表變量函數(shù)形參：指定順序表變量 取元素值的序號(hào)取元素值的序號(hào) 返回值：序號(hào)為返回值：序號(hào)為i的元素值的元素值 i 的有效范圍01size-1算法算法2.6 取得順序表中序號(hào)為取得順序表中序號(hào)為i的元素值的元素值 datatype get(sequence_list slt,int i) if(i=slt.size) /*查找位置不正確查找位置不正確*/ printf(n指定位置的結(jié)點(diǎn)不存在指定位置的結(jié)點(diǎn)不存在!); exit(1); else return slt.ai; 算

15、法實(shí)現(xiàn)算法實(shí)現(xiàn)：順序表的插入運(yùn)算是將一個(gè)值為順序表的插入運(yùn)算是將一個(gè)值為x的結(jié)點(diǎn)插入到順的結(jié)點(diǎn)插入到順序表的第序表的第i個(gè)位置個(gè)位置0in，即將，即將x插入到插入到ki-1和和ki之間，如之間，如果果i=n，則表示插入到表的最后，一般地可表示為：，則表示插入到表的最后，一般地可表示為：插入前：插入前：k0, k1, , ki-1, ki, , kn-1插入后：插入后：k0, k1, , ki-1,x ki, , kn-1 插入過(guò)程的圖示見(jiàn)下圖：插入過(guò)程的圖示見(jiàn)下圖：k ik0k1k i-1k n-1k0k1k i-1k n-1xk i后移開(kāi)始位置后移開(kāi)始位置后移結(jié)束位置后移結(jié)束位置插入前插入前

16、插入后插入后順序表的插入運(yùn)算順序表的插入運(yùn)算 在順序表在順序表下標(biāo)為下標(biāo)為i（0= i size=MAXSIZE) /*判表滿判表滿*/ printf(n順序表是滿的順序表是滿的!沒(méi)法插入沒(méi)法插入!);exit(1); if(ilp-size) /*判插入位置不對(duì)判插入位置不對(duì)*/ printf(n指定的插入位置不存在指定的插入位置不存在!);exit(1); for(j=lp-size-1;j=i;j-) /*從后往前元素后移從后往前元素后移*/ lp-aj+1=lp-aj; lp-ai=x; lp-size+; /*插入并表長(zhǎng)增插入并表長(zhǎng)增1*/ 插入算法實(shí)現(xiàn)：插入算法實(shí)現(xiàn)： 元素可插入位

17、置元素可插入位置(0size)0 isize-1sizex 從表尾開(kāi)始到下標(biāo)i的元素依次向后移一位k0k1 ki kn-1移動(dòng)n-i次插入位置 移動(dòng)次數(shù) 0 n 最壞O(n) 1 n-1 n-1 1 n 0 最好O(1) i n-i插入算法分析：插入算法分析： 可能的插入位置為可能的插入位置為i=0,1,n共共n+1個(gè)位置個(gè)位置按等概率考慮按等概率考慮,則插入概率：則插入概率：pi=1/(n+1)平均移動(dòng)次數(shù)：平均移動(dòng)次數(shù)：22)1(11nnnnniniiIinninPE00)(11)(順序表插入算法平均約需移動(dòng)順序表插入算法平均約需移動(dòng)一半元素，時(shí)間復(fù)雜度為一半元素，時(shí)間復(fù)雜度為O(n)順序

18、表的刪除運(yùn)算順序表的刪除運(yùn)算 順序表的刪除操作是指刪除順序表中的第順序表的刪除操作是指刪除順序表中的第i個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，0in-1，一般地可表示為：，一般地可表示為： 刪除前：刪除前：k0, k1, , ki-1, ki, ki+1, , kn-1 刪除后：刪除后：k0, k1, , ki-1, ki+1, , kn-1 刪除過(guò)程的圖示見(jiàn)下圖刪除過(guò)程的圖示見(jiàn)下圖 ：k ik0k1k i-1k n-1k0k1k i-1k n-1k i+1前移結(jié)束位置前移結(jié)束位置前移開(kāi)始位置前移開(kāi)始位置刪除前刪除前刪除后刪除后k i+1在順序表中刪除在順序表中刪除下標(biāo)為下標(biāo)為i（0= i size=0) /*判表

19、為空判表為空*/ printf(n順序表是空的順序表是空的!);exit(1); if(i=lp-size) )/*判刪除位置不對(duì)判刪除位置不對(duì)*/ printf(n指定的刪除位置不存在指定的刪除位置不存在!);exit(1); for(j=i+1;jsize-1;j+) /*元素前移元素前移*/ lp-aj-1=lp-aj; lp-size-; /*表長(zhǎng)減表長(zhǎng)減1*/刪除算法實(shí)現(xiàn)：刪除算法實(shí)現(xiàn)： 刪除元素位置(0size-1)0 i size-1 size刪除 從下標(biāo)從下標(biāo)i+1開(kāi)始到表尾的元素依次向前移一位開(kāi)始到表尾的元素依次向前移一位k0k1 kiki+1 kn-1移動(dòng)n-i-1次刪除位

20、置 移動(dòng)次數(shù) 0 n-1 最壞O(n) 1 n-2 n-2 1 n-1 0 最好O(1) i n-i-1刪除算法分析刪除算法分析： 可能的刪除位置為可能的刪除位置為i=0,1,n-1i=0,1,n-1共共n n個(gè)位置個(gè)位置按等概率考慮按等概率考慮, ,則刪除概率：則刪除概率：p pi i=1/n=1/n平均移動(dòng)次數(shù)：平均移動(dòng)次數(shù)：順序表刪除算法平均約需移動(dòng)順序表刪除算法平均約需移動(dòng)一半元素。一半元素。時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)1010) 1(1) 1(niniiIinninPE212)11nnnn（1）void reverse (sequence_list *lp) 將順序表將順序表L就

21、地倒置，即借助于就地倒置，即借助于O（1）的輔助空間。）的輔助空間。（2）void sprit(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) 將有序順序表將有序順序表L1分裂成兩個(gè)線性表分裂成兩個(gè)線性表L2與與L3，L2由表由表中所奇數(shù)組成，中所奇數(shù)組成，L3由所有偶數(shù)組成。由所有偶數(shù)組成。 順序表上的一些其它常見(jiàn)算法順序表上的一些其它常見(jiàn)算法（3）void merge(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) 見(jiàn)順序表應(yīng)用見(jiàn)順序表應(yīng)用 將有序順序表將有序順序

22、表L1與與L2合并成有序順序表合并成有序順序表L3。元素類型元素類型：typedef struct int num;/*學(xué)生學(xué)號(hào)學(xué)生學(xué)號(hào)*/ char name20; /*學(xué)生姓名學(xué)生姓名*/ int score; /*成績(jī)成績(jī)*/datatype;建表要求：建表要求：按輸入順序依次建表按輸入順序依次建表, 輸入學(xué)號(hào)為負(fù)時(shí)結(jié)束輸入學(xué)號(hào)為負(fù)時(shí)結(jié)束函數(shù)形參：被建順序表地址函數(shù)形參：被建順序表地址返回值：無(wú)返回值：無(wú)建立順序表建立順序表void Create(sequence_list slt) /*建立學(xué)生結(jié)點(diǎn)順序表建立學(xué)生結(jié)點(diǎn)順序表*/ datatype e; int i=0; /*i為計(jì)結(jié)點(diǎn)個(gè)數(shù)變量為計(jì)結(jié)點(diǎn)個(gè)數(shù)變量*/ while(1) printf(“nEnter new student:”); scanf(“%d”,&e.num); if(e.numai=e; i+; slt-size=i; /*表長(zhǎng)就是結(jié)點(diǎn)數(shù)表長(zhǎng)就是結(jié)點(diǎn)數(shù)*/運(yùn)算實(shí)現(xiàn)運(yùn)算實(shí)現(xiàn)：優(yōu)點(diǎn)：優(yōu)點(diǎn)： (1) 邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理位置也是相鄰邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理位