Ch21-22線性表-順序存儲ppt課件

1、1第二章第二章 線性表線性表 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表的順序存儲及實現(xiàn)線性表的順序存儲及實現(xiàn) 線性表的鏈接存儲及實現(xiàn)線性表的鏈接存儲及實現(xiàn) 順序表和單鏈表的比較順序表和單鏈表的比較 線性表的其他存儲及實現(xiàn)線性表的其他存儲及實現(xiàn)本章的基本內(nèi)容是：本章的基本內(nèi)容是：2線性表(Linear List) ：由n(n)個數(shù)據(jù)元素(結(jié)點)a1,a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。 當n=0時稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 這里的數(shù)據(jù)元素ai(1in)只是一個抽象的符號，其具體含義在不同的情況下可以不同。 例1、26個英文字母組成

2、的字母表 （A，B，C、Z） 例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。 （6，17，28，50，92，188）2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)3例3、學(xué)生健康情況登記表如下：姓 名學(xué) 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . .4 從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨a n-1；其余的內(nèi)部結(jié)

3、點ai(2in-1)都有且僅有一個直接前趨a i-1和一個直接后繼a i+1。 線性表的邏輯特征5ADT 線性表的定義線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。抽象數(shù)據(jù)類型的定義為：P196 例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。 void union(List &La，List Lb) La-len=listlength(La); Lb-len=listlength(Lb); for(I=1;I=Lb-len;I+) getelem(Lb，I，e); if(!locateelem

4、(La，e，equal)listinsert(La，+la-en，e) 7 例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。 此問題的算法如下： 8 void mergelist(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while(I=la-len)&(j=lb-len) getelem(la，I，ai);getelem(lb，

5、j，bj); if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj);+j; 9 while(I=la-len) getelem(la，I+，ai);listinsert(lc，+k，ai); while(j=lb-len) getelem(lb，j+，bj);listinsert(lc，+k，bi); 10 2.2.1 線性表的順序表示 線性表的順序表示：把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。 如何計算數(shù)據(jù)元素的存儲位置？ 假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第

6、一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i個數(shù)據(jù)元素的存儲位置LOC(a I )之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+l 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC(ai)=LOC(a1)+(I-1)*l 11 由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。 # define ListSize 100 typedef ElemType DataType;

7、 typedef struct DataType dataListSize; int length; Sqlist;12 在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。 注意：C語言中的數(shù)組下標從“0開場，因而，若L是Sqlist類型的順序表，則表中第i個元素是L.dataI-1。 以下主要討論線性表的插入和刪除兩種運算。 1、插入 線性表的插入運算是指在表的第I(1in+1個位置上，插入一個新結(jié)點x，2.2.2 順序表上實現(xiàn)的基本操作13使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表 (a1，a i-1，x，ai，an)14

8、算法2.Void InsertList(Sqlist &L，DataType x，int I) int j; if(IL.length+1) printf(“Position error”); return ERROR15 if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1;j=I-1;j-) L.dataj+1=L.dataj; L.dataI-1=x; L.length+; 16 這里的問題規(guī)模是表的長度，設(shè)它的值為n。該算法的時間主要化費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)即移動

9、結(jié)點的次數(shù)是n-i+1。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。當插入操作在表尾進行時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是最好情況，其時間復(fù)雜度O1）；當插入操作在表頭進行時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，其時間復(fù)雜度為On）。算法的復(fù)雜度分析17由于插入可能在表中任何位置上進行，因此需分析算法的平均復(fù)雜度。 在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，

10、假設(shè)在表中任何位置(1in+1)上插入結(jié)點的機會是均等的，那么 p1=p2=p3=p n+1=1/(n+1) 因而，在等概率插入的情況下， Eis(n)= (n-I+1)/(n+1)=n/2 11ni11ni18 也就是說，在順序表上做插入運算，平均要移動表上一半結(jié)點。當表長 n較大時，算法的效率相當?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。 192、刪除 線性表的刪除運算是指將表的第i(1in)結(jié)點刪除，使長度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長度為n-1的線性表 (a1，a i-1，a i+1

11、，an)20算法2.Void deleteList(Sqlist &L，int I) int j; if(IL.length) printf(“Position error”); return ERROR； for(j=i;j=L.length-1;j+) L.dataj-1=L.dataj; L.length-; 21 該算法的時間分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長n和位置i決定。 若I=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點； 若I=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O

12、(n)。 刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點，令Ede(n)表示所需移動結(jié)點的平均次數(shù)，刪除表中第i個結(jié)點的移動次數(shù)為n-i，故 Ede(n)= pi(n-I) 式中，pi表示刪除表中第i個結(jié)點的概率。算法的復(fù)雜度分析22 在等概率的假設(shè)下， p1=p2=p3=pn=1/n 由此可得： Ede(n)= (n-I)/n=(n-1)/2 即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是O(n)。 23小結(jié)：順序存儲方式的優(yōu)缺點 優(yōu)點： .在節(jié)點等長時可以隨機存取。 存儲密度高，節(jié)省存儲空間。 用結(jié)點的物理次序反映結(jié)點之間的邏輯關(guān)系。 缺點：

13、 插入和刪除結(jié)點時需要移動大量的結(jié)點。 必須靜態(tài)分配連續(xù)的空間。24課堂練習 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）。 【解答】108 在一個長度為n的順序表的第i1in+1個元素之前插入一個元素，需向后移動（ ）個元素，刪除第i1in個元素時，需向前移動（ ）個元素。 【解答】n-i+1，n-i 25 當線性表采用順序存儲結(jié)構(gòu)時，其主要特點是（ ）。 【解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰 26 作業(yè) 試寫一個刪除算法 Void elete_seq(Sqlist &plist， ElemType x), 在plist所指順序表

14、中，刪除一個值為的元素，返回刪除成功與否的標志。 （請首先給出順序表的定義，再寫出算法） 27 附: “指針”程序經(jīng)過編譯后,系統(tǒng)為變量分配內(nèi)存單元。不同類型的變量分配到的字節(jié)數(shù)是不同的。例如：整型變量分配2個字節(jié)，單精度分配4個字節(jié)。內(nèi)存區(qū)中的每一個字節(jié)有一個編號，稱為“地址”。概念辨析：內(nèi)存單元的地址和內(nèi)存單元的內(nèi)容例：假設(shè)程序中定義了2個整型變量i和j, 編譯時系統(tǒng)將3000和3001這兩個字節(jié)給變量I,將3002和3003這兩個字節(jié)給j. 那么地址為3000的內(nèi)存單元中存放著變量i的值。28 “直接訪問方式和“間接訪問方式 按變量地址存取變量值的方式稱為“直接訪問” 例如 ：print

15、f(“%d”,i) 是如何執(zhí)行的？ scanf(“%d”,&i) 是如何執(zhí)行的？將變量i的地址存放在另外一個變量中，通過這個變量的值也就是i的地址），找到i的內(nèi)存起始地址，讀取i的值。i_pointer=&i; /將i的地址3000存放到i_pointer中。 29 地址是指向變量的，知道地址就知道了地址所指向的變量。所以，一個變量的地址稱為該變量的“指針”。 變量的指針就是變量的地址。 存放變量地址的變量是指針變量。 定義一個指針變量 int *pointer_1; /pointer_1這個變量可以存放一個整型變量的地址。 float *pointer_2; /pointer

16、_2這個指針變量可以存放一個浮點型變量的地址。30指針變量的引用 兩個運算符 “&” 與 “*” &: 取地址符。 *: 指針運算符，取指針所指向的對象的內(nèi)容。 例如： &a 是變量a的地址； *p是指針變量p所指向的存儲單元的內(nèi)容， 也就是p所指向的變量的值。 31例子： 通過指針變量訪問整型變量。 #include Void main() int a; int *pointer_1; a=100; pointer_1=&a; printf(“%dn”,a); printf(“%dn”,*pointer_1); 運行結(jié)果： 100 100*pointer_1=

17、200思考加入下列語句，思考加入下列語句，得到什么結(jié)果？得到什么結(jié)果？32 結(jié)構(gòu)體類型 定義一個結(jié)構(gòu)體類型stu，這個結(jié)構(gòu)體類型包括學(xué)號、姓名、成果、家庭地址等四個數(shù)據(jù)項。 struct stu int num; char name20; float score; char addr30；可以用這個結(jié)構(gòu)體類型來定義變量，例如 struct stu student1,student2; 結(jié)構(gòu)體類型名結(jié)構(gòu)體變量名33 也可以在聲明類型的同時定義變量 struct stu int num; char name20; float score; char addr30；student1,student2

18、；結(jié)構(gòu)體變量的引用例1. student1.num=2019003;例2. printf(“%s”,)例3. scanf(“%d”, &student1.num)34指向結(jié)構(gòu)體類型數(shù)據(jù)的指針 一個結(jié)構(gòu)體變量的指針就是該變量所占據(jù)的內(nèi)存段的起始地址。可以設(shè)一個指針變量，用來指向一個結(jié)構(gòu)體變量，此時該指針變量的值是結(jié)構(gòu)體變量的起始地址。 舉例：指向結(jié)構(gòu)體變量的指針的應(yīng)用 （見下一頁中的程序）35#include#includevoid main() struct student long num;char name20;float score;struct studen