第2講 線性表及其順序存儲

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

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

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

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

5、結(jié)點地址計算l 設(shè)首元素設(shè)首元素a a1 1的存放地址為的存放地址為location(alocation(a1 1) )（稱稱為首地為首地址址），），l 設(shè)每個元素占用存儲空間（地址長度）為設(shè)每個元素占用存儲空間（地址長度）為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é)構(gòu)示意圖參見順序表存儲結(jié)構(gòu)示意圖）順序表存儲結(jié)構(gòu)示意圖順序表

6、存儲結(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一個一維數(shù)組，下標(biāo)的范圍是一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的到，每個數(shù)組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是9 9，則則 的第一個字節(jié)的地址是的第一個字節(jié)的地址是 113例例1因此

7、：因此：loction( M3 ) = 98 + 5 3 =113解：地址計算通式為：解：地址計算通式為：loction(ai)= loction(a0) + len *i1、順序表數(shù)據(jù)類型的定義、順序表數(shù)據(jù)類型的定義(1)定義數(shù)組的體積定義數(shù)組的體積(最多允許的元素個數(shù)最多允許的元素個數(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、序表的實現(xiàn)順序表的實現(xiàn)(3) 順序表的類型定義順序表的類型定義typedef struct datatype aMAXSIZE; /*存放線性表元素的數(shù)組存放線性表元素的數(shù)組*/ int size; /*表示表示 a中實際存放元素個數(shù)中實際存放元素個數(shù)(表長表長)*/ 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本課堂順序表的存儲結(jié)構(gòu)的本課堂順序表的存儲結(jié)構(gòu)的C語言描述如下：語言描述如下： #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;l即定義相應(yīng)運算的即定義相應(yīng)運算的C語言函數(shù)。語言函數(shù)。l定義函數(shù)要確定：定義函數(shù)要確定： 函數(shù)名函數(shù)名 形參形參 返回值返回值傳入量傳入量傳出量傳出量l 出錯處理函數(shù)出錯處理函數(shù)exi

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

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

12、實現(xiàn)算法實現(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 判順序表是否為空表判順序表是否為空表判斷表長是否為判斷表長是否為0。 函數(shù)形參：指定順序表變量函數(shù)形參：指定順序表變量 返回值：返回值： 1表示空表示空, 0表示非空表示非空 算法實現(xiàn)算法實現(xiàn)： int empty(sequence_list slt) return slt.size=0; 遍歷順序表，查找與給定值遍歷

13、順序表，查找與給定值x相同的元素，找到相同的元素，找到后返回元素的下標(biāo)值，沒找到返回后返回元素的下標(biāo)值，沒找到返回-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)中每個成員算法實現(xiàn)算法實現(xiàn)： 返回序號為返回序號為i的元素值的元素值。 函數(shù)形參：指定順序表變量函數(shù)形參：指定順序表變量 取元素值的序號取元素值的序號 返回值：序號為返回值：序號為i的元素值的元素值 i 的有效范圍01size-1算法算法2.6 取得順序表中序號為取得順序表中序號為i的元素值的元素值 datatype get(sequence_list slt,int i) if(i=slt.size) /*查找位置不正確查找位置不正確*/ printf(n指定位置的結(jié)點不存在指定位置的結(jié)點不存在!); exit(1); else return slt.ai; 算

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

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

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

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

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

20、置 移動次數(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個位置個位置按等概率考慮按等概率考慮, ,則刪除概率：則刪除概率：p pi i=1/n=1/n平均移動次數(shù)：平均移動次數(shù)：順序表刪除算法平均約需移動順序表刪除算法平均約需移動一半元素。一半元素。時間復(fù)雜度為時間復(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分裂成兩個線性表分裂成兩個線性表L2與與L3，L2由表由表中所奇數(shù)組成，中所奇數(shù)組成，L3由所有偶數(shù)組成。由所有偶數(shù)組成。 順序表上的一些其它常見算法順序表上的一些其它常見算法（3）void merge(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) 見順序表應(yīng)用見順序表應(yīng)用 將有序順序表將有序順序

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