1、2.2線性表及其順序存儲(chǔ)結(jié)構(gòu),一、線性表及其運(yùn)算,線性表,定義： n（0）個(gè)數(shù)據(jù)元素的有限序列，記作（a1, ai-1, ai, ai+1, an） 其中,ai 是表中數(shù)據(jù)元素，n 是表長(zhǎng)度。 特點(diǎn): 同一線性表中元素具有相同特性。 相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。 除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。 除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。,順序表,定義：將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中。 存儲(chǔ)結(jié)構(gòu)：數(shù)組。 特點(diǎn)：線性表的順序存儲(chǔ)方式。 存取方式：隨機(jī)存取 順序存儲(chǔ)結(jié)構(gòu)示意圖,45 89 90 67 40 78,0 1 2 3 4 5,順序

2、表的存儲(chǔ)方式：,LOC(a i+1) = LOC( a 1 )+(i-1)*l LOC(a i) = LOC(a1)+(i-1)*l,順序表（SeqList）的類型定義 #define ListSize 100 /最大允許長(zhǎng)度 typedef int ListData; typedef struct ListData datalistsize; /存儲(chǔ)空間基址 int length; /當(dāng)前元素個(gè)數(shù) SeqList;,順序表基本運(yùn)算 初始化 void InitList ( SeqList ,按值查找：找x在表中的位置，若查找成功，返回表項(xiàng)的位置，否則返回-1 int Find ( SeqLis

3、t L, ListData x ) int i = 0; while ( i L.length ,求表的長(zhǎng)度 int Length ( SeqList ,按值查找：尋找x的后繼 listdata Next ( SeqList ,插入,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,順序表插入時(shí)，平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng) 插入概率相等時(shí),順序表的插入 int Insert ( SeqList /插入成功 ,刪除,25 34 57 50 16 48 09 6

4、3 ,16,刪除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,順序表刪除平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng) 刪除概率相等時(shí),順序表的刪除 int Delete ( SeqList /表中沒有 x ,順序表的應(yīng)用:集合的“并”運(yùn)算,void Union ( SeqList ,集合的“交”運(yùn)算,void Intersection ( SeqList /未找到在A中刪除它 ,二、棧及其應(yīng)用,定義:是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 允許插入和刪除的一端 稱為棧頂(top)，另一端 稱為棧底(bottom) 特點(diǎn)：后進(jìn)先出 (LIFO),a1,top,botto

5、m,an . . . .,進(jìn)棧,出棧,棧的主要操作,ADT Stack /對(duì)象由數(shù)據(jù)類型為StackData的元素構(gòu)成 int Push (stack *S, StackData x); /進(jìn)棧 int Pop (stack *S, StackData /判棧滿否 ,棧的表示和實(shí)現(xiàn),順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個(gè)位置， base為棧底指針，指向棧底的位置。,base,順序棧的類型表示:,#define STACK_SIZE 100； typedef struct /順序棧定義 int dataSTAC

6、K_SIZE; int top; /棧頂指針 SeqStack；,判棧空 int StackEmpty (SeqStack *S) if( S.top = 0 ) return 1 /判?？?空則返回1 else return 0; /否則返回0 判棧滿 int StackFull (SeqStack *S) if( S.Top= STACK_SIZE ) return 1 /判棧滿,滿則返回1 else return 0; /否則返回0 ,順序棧的基本運(yùn)算:,初始化 void InitStack ( SeqStack *S) S-top = 0 ; ,入棧 int Push (SeqStac

7、k S, StackData x) if (StackFull (S) ) return 0; /失敗 else (S.dataS.top)=x; (S.top)+; Return 1 ,取棧頂元素 int Gettop (SeqStack S) if ( StackEmpty(S) ) return error; else return (S.datas.top-1); ,出棧 int pop (SeqStack S ) /若棧空返回0, 否則棧頂元素退出到x并返回1 if ( StackEmpty(S) ) return error; else return (S.datas.top-1)

8、; (S.top) -; ,三、隊(duì)列,定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。 在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear） ，允許刪除的一端稱為對(duì)頭(front)。 特點(diǎn)：先進(jìn)先出 (FIFO),a1 ，a2， a3，an,出隊(duì)列,入隊(duì)列,隊(duì) 頭,隊(duì) 尾,隊(duì)列的主要運(yùn)算,（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)； （3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；,2.3.2 隊(duì)列 2.3.2.1 隊(duì)列的定義與運(yùn)算 定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。 設(shè)隊(duì)列 q = (

9、 a1, a2, a3, , an )中，a1是允許刪除的一端，稱為隊(duì)頭（front），an是允許插入的一端為隊(duì)尾（rear）。,a1 , a2 , a3 , a4 , an-1 , an,隊(duì) 列 示 意 圖,隊(duì)頭,隊(duì)尾,先進(jìn)先出FIFO,隊(duì)列的存儲(chǔ)結(jié)構(gòu),（1）順序存儲(chǔ)結(jié)構(gòu),(a)線性隊(duì)列,和棧一樣，用順序結(jié)構(gòu)表示隊(duì)列是一種簡(jiǎn)單的方法，通常用一維數(shù)組實(shí)現(xiàn)，其中MAX表示隊(duì)列允許的最大容量，在隊(duì)的兩端設(shè)置兩個(gè)整型變量作指針，front為頭指針，rear為尾指針。,隊(duì)空時(shí)， 令rear=front= -1，當(dāng)有新元素入隊(duì)時(shí)，尾指針加1，當(dāng)有元素出隊(duì)時(shí)，頭指針加1。故在非空隊(duì)列中，頭指針始終指向隊(duì)頭

10、元素前一個(gè)位置，而尾指針始終指向隊(duì)尾元素的位置,MAX=4,假設(shè)MAX=4，當(dāng)隊(duì)列處于圖（c）狀態(tài)，rear+1=4時(shí)隊(duì)滿，此時(shí)不能插入新元素，但實(shí)際上隊(duì)列可用空間沒有滿，這是一種假溢出現(xiàn)象。解決方法：將隊(duì)列頭尾相連形成一個(gè)環(huán)。,線性隊(duì)列隊(duì)滿的條件： rear + 1 = MAX 線性隊(duì)列隊(duì)空的條件： rear = front,MAX=4,(b) 循環(huán)隊(duì)列,區(qū)別隊(duì)空與隊(duì)滿的方法：如果隊(duì)尾加1后等于隊(duì)頭指針即為隊(duì)滿，即少用一個(gè)元素空間。,將頭尾連接成一個(gè)環(huán)，形成循環(huán)隊(duì)列。,循環(huán)隊(duì)列隊(duì)空的條件： rear=front,循環(huán)隊(duì)列全部空間占滿 rear=front,(b) 循環(huán)隊(duì)列,rear,隊(duì)滿條件

11、： (rear+1)%MAX=front 注：實(shí)際上為了避免與隊(duì)空標(biāo)志沖突，還留有一個(gè)空間。,將頭尾連接成一個(gè)環(huán)，形成循環(huán)隊(duì)列。,%-取余數(shù)運(yùn)算符。當(dāng)指針處于MAX-1，下一個(gè)位置為“0”，而非MAX。,循環(huán)隊(duì)列的類型表示:,#define queue_SIZE 100； typedef struct QueueData dataQueue_SIZE; int front,rear; Queue；,循環(huán)隊(duì)列中加入一個(gè)元素的算法（入隊(duì)算法）： int EnQueue(Queue Q, QueueData x) if(q.rear+1)%MAX= =q.front) return 0; else q.rear=(q.rear+1)%MAX; Q.dataq.rear=x; return(1); ,循環(huán)隊(duì)列中刪除一個(gè)元素的算法： QueueData DeQueue(Queue Q) if(q.rear= =q.front) return error; else q.front=(q.front+1)%MAX;