線性表及其順序存儲課件

1、第2章 線性表及其順序存儲線性表順序表棧隊列1第1頁，共24頁。線性表是一種常用的數(shù)據結構，本章介紹線性表及其順序存儲，并對棧和隊列及它們的順序實現(xiàn)給出了詳細的設計描述。 2.1線性表 線性表是一個線性結構，它是一個含有n0個結點的有限序列，一般地，一個線性表可以表示成一個線性序列：k1,k2,kn，其中k1是開始結點，kn是終端結點。 2第2頁，共24頁。例1、26個英文字母組成的字母表 （A，B，C、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。 （6，17，28，50，92，188）3第3頁，共24頁。姓 名學 號性 別年 齡 健康情況王小林790631 男 1

2、8 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 貧血 . . .例3 學生健康情況登記表如下：4第4頁，共24頁。例4、一副撲克的點數(shù) （2，3，4，J，Q，K，A）從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內部結點ai(2in-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。 線性表是一種典型的線性結構。5第5頁，共24頁。2.2.1順序表 線性表采用順序存儲的方式存儲就稱之

3、為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續(xù)的存儲單元中。 2.2順序表順序表的存儲結構如下圖所示： 存儲地址 location(k1) location(k1)+(i-1)l en 結點序號 1 2 i n len len len lenk1k2k ik n內存狀況6第6頁，共24頁。一個一維數(shù)組，下標的范圍是到，每個數(shù)組元素用相鄰的個字節(jié)存儲。存儲器按字節(jié)編址，設存儲數(shù)組元素的第一個字節(jié)的地址是 98 ，則的第一個字節(jié)的地址是 113例1因此：LOC( M3 ) = 98 + 5 3 =113解：地址計算通式為：LOC(ai) = LOC(a0) + L *i如順序表的

4、每個結點占用len個內存單元，用location (ki)表示順序表中第i個結點ki所占內存空間的第1個單元的地址。則有如下的關系location (ki+1) = location (ki) +lenlocation (ki) = location(k1) + (i-1)len7第7頁，共24頁。存儲結構要體現(xiàn)數(shù)據的邏輯結構順序表的存儲結構中，內存中物理地址相鄰的結點一定具有順序表中的邏輯關系。 8第8頁，共24頁。2.2.2順序表的實現(xiàn) 用C語言中的數(shù)組存儲順序表。 C語言中數(shù)組的下標是從0開始的，即數(shù)組中下標為0的元素對應的是順序表中的第1個結點，數(shù)組中下標為i的元素對應的是順序表中的第

5、i+1個結點。 為了方便，將順序表中各結點的序號改為和對應數(shù)組元素的下標序號一致，即將順序表中各結點的序號從0開始編號。這樣，一個長度為n的順序表可以表示為 k0, k1, k2, , kn-19第9頁，共24頁。順序表的存儲結構的C語言描述如下：/*順序表的頭文件，文件名sequlist.h */#define MAXSIZE 10 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;表長10第10頁，共24頁。順序表的幾個基本操作的具體實現(xiàn) ：/ 函數(shù)功能:順序表的初始化置空表 /

6、函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / 函數(shù)返回值:空 / 文件名:sequlist.c, 函數(shù)名:init() / void init(sequence_list slt) slt-size=0; 算法2.1順序表的初始化-置空表11第11頁，共24頁。/ 函數(shù)功能:在順序表后部進行插入操作 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / datatype類型的變量x / 函數(shù)返回值:空 / 文件名:sequlist.c, 函數(shù)名:append() / void append(sequence_list slt,datatype x) if

7、(slt-size=MAXSIZE) printf(順序表是滿的!);exit(1); slt-aslt-size=x; slt-size=slt-size+1; 算法2.2 在順序表后部進行插入操作12第12頁，共24頁。打印順序表的各結點值 / 函數(shù)功能:打印順序表的各結點值 / 函數(shù)參數(shù):sequence_list型變量slt / 函數(shù)返回值:空 / 文件名:sequlist.c, 函數(shù)名:display() / void display(sequence_list slt) int i; if(!slt.size) printf(n順序表是空的!); else for(i=0;islt

8、.size;i+) printf(%5d,slt.ai); 算法2.3 打印順序表的各結點值13第13頁，共24頁。判斷順序表是否為空 / 函數(shù)功能:判斷順序表是否為空 / 函數(shù)參數(shù):sequence_list型變量slt / 函數(shù)返回值:int類型。1表示空,0表示非空 / 文件名:sequlist.c,函數(shù)名:empty() / int empty(sequence_list slt) return(slt.size=0 ? 1:0); 算法2.4 判斷順序表是否為空14第14頁，共24頁。查找順序表中值為x的結點位置 / 函數(shù)功能:查找順序表中值為x的結點位置 / 函數(shù)參數(shù):sequen

9、ce_list型變量slt,datatype型變量x / 函數(shù)返回值:int類型。返回x的位置值,-1表示沒找到 / 文件名:sequlist.c,函數(shù)名:find() / int find(sequence_list slt,datatype x) int i=0; while(islt.size&slt.ai!=x) i+; return(islt.size? i:1); 算法2.5 查找順序表中值為x的結點位置15第15頁，共24頁。 取得順序表中第i個結點的值 / 函數(shù)功能:取得順序表中第i個結點的值 / 函數(shù)參數(shù):sequence_list型變量slt,int型變量i / 函數(shù)返回值

10、:datatype類型。返回第i個結點的值 / 文件名:sequlist.c,函數(shù)名:get() / datatype get(sequence_list slt,int i) if(i=slt.size) printf(n指定位置的結點不存在!);exit(1); else return slt.ai; 算法2.6 取得順序表中第i個結點的值16第16頁，共24頁。 順序表的插入運算是將一個值為x的結點插入到順序表的第p個位置0pn，即將x插入到kp-1和kp之間，一般地可表示為：插入前：k0, k1, , kp-1, kp, , kn-1插入后：k0, k1, , kp-1,x, kp,

11、, kn-1 插入過程的圖示見下圖： k ik0k1k i-1k n-1k0k1k i-1k n-1xk i后移開始位置后移結束位置插入前插入后p+1 nppp-1p-117第17頁，共24頁。/ 函數(shù)功能:在順序表的position位置插入值為x的結點 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / datatype型變量x,int型變量 position / 函數(shù)返回值:空 文件名:sequlist.c,函數(shù)名:insert() / void insert(sequence_list slt,datatype x,int position) int i; if(sl

12、t-size=MAXSIZE) printf(n順序表是滿的!沒法插入!);exit(1); if(positionslt-size) printf(n指定的插入位置不存在!);exit(1); for(i=slt-size;iposition;i-) slt-ai=slt-ai1; slt-aposition=x; slt-size+; 算法2.7 在順序表的position位置插入值為x的結點18第18頁，共24頁。算法2.7中，所花費的時間主要是元素后移操作，對于在第i個位置上插入一個新的元素，需要移動（n-i）個元素，設在第i個位置上插入一個元素的概率為pi，且在任意一個位置上插入元素

13、的概率相等，即p0=p1=p2=pn=1/(n+1)，則在一個長度為n的順序表中插入一個元素所需的平均移動次數(shù)為： 即在長度為n的順序表中插入一個元素平均需要移動表中的一半元素。該算法的時間復雜度為O（n）。 19第19頁，共24頁。 順序表的刪除操作是指刪除順序表中的第i個結點，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前移結束位置前移開始位置刪除前刪除后k i+120第

14、20頁，共24頁。刪除操作的具體實現(xiàn)見算法2.8 / 函數(shù)功能:刪除順序表中第position位置的結點 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / int型變量 position / 函數(shù)返回值:空 文件名:sequlist.c,函數(shù)名:dele() / void dele(sequence_list slt,int position) int i; if(slt-size=0) printf(n順序表是空的!);exit(1); if(position=slt-size) printf(n指定的刪除位置不存在!);exit(1); for(i=position;

15、isize-1;i+) slt-ai=slt-ai+1; slt-size-; 算法2.8 刪除順序表中第position位置的結點 21第21頁，共24頁。 要刪除順序表中的第i個結點，則需要稱動（n-i-1）個元素，設刪除表中第i個結點的概率為qi，且在表中每一個位置刪除的概率相等，即：q0=q1=qn-1=1/n則在一個長度為n的順序表中刪除一個結點的平均移動次數(shù)為： 在一個長為n的順序表中刪除一個元素平均需要移動表中大約一半的元素。該算法的時間復雜度為O（n）22第22頁，共24頁。（1）void verge(sequence_list l) 將順序表L就地轉置，即借助于O（1）的輔助空間。（2）void sprit(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) 略 將有序順序表L1分裂成兩個線性表L2與L3，L2由表中所奇數(shù)組