線性表及其順序存儲結構

線性表及其順序存儲結構第1頁，共32頁，2023年，2月20日，星期六第2頁，共32頁，2023年，2月20日，星期六2.2.1線性表及其運算1、概念線性表（簡稱表）：零個或多個具有相同類型的數據元素的有限序列。數據元素的個數稱為線性表的長度?！らL度等于零時稱為空表，通常記為：L＝()；·非空表通常記為：L＝(a1，a2，……，an)。理解線性表的定義有以下要點：⑴序列——順序性：元素具有線性順序，第一個元素無前驅，最后一個元素無后繼，其他每個元素有且僅有一個前驅和一個后繼。⑵有限——有限性：元素個數有限，在計算機中處理的對象都是有限的。⑶相同類型——相同性：元素取自于同一個數據對象，這意味著每個元素占用相同數量的存儲單元。⑷元素類型不確定——抽象性：數據元素的類型是抽象的、不具體的，需要根據具體問題確定。第3頁，共32頁，2023年，2月20日，星期六順序表用一段地址連續(xù)的存儲單元依次存儲線性表的數據元素。線性表(a1，a2，……，an)的順序存儲示意圖如圖2.5所示。由于線性表中每個數據元素的類型相同，可以用C++語言中的一維數組來實現順序表，也就是把線性表中相鄰的元素存儲在數組中相鄰的位置，如圖2.6所示第4頁，共32頁，2023年，2月20日，星期六在稍微復雜的線性表中，一個數據元素還可以由若干個數據項組成。例如，某班的學生情況登記表是一個復雜的線性表，表中每一個學生的情況就組成了線性表中的每一個元素，每一個數據元素包括學號、姓名、性別、入學成績4個數據項。

第5頁，共32頁，2023年，2月20日，星期六2、線性表的順序存儲線性表的順序存儲結構稱為順序表。

線性表的順序存儲結構具有兩個基本特點：①線性表中所有元素所占的存儲空間是連續(xù)的；②

線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。

第6頁，共32頁，2023年，2月20日，星期六假設線性表中的第一個數據元素的存儲地址（即首地址）為ADR(a1)，每一個數據元素占k個字節(jié)，則線性表中第i個元素ai在計算機存儲空間中的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k第7頁，共32頁，2023年，2月20日，星期六長度為n的線性表在計算機中的順序存儲結構第8頁，共32頁，2023年，2月20日，星期六在程序設計語言中，通常定義一個一維數組來表示線性表的順序存儲空間。應注意數組的基本類型要與線性表中數據元素的類型相同。數組需要根據情況預設足夠的大小，同時還需要一個變量指出線性表在數組中的當前狀況，如元素個數或最后一個元素在數組中的位置等。這兩方面的信息共同描述一個順序表，可將它們封裝在一起。對C語言，順序表可定義如下：

第9頁，共32頁，2023年，2月20日，星期六對C語言，順序表可定義如下：#defineMaxLength50typedefintElemType;typedefstruct

{ElemTypelist[MaxLength];intlength;}SeqList;

今后使用此定義時，MaxLength及ElemType要根據實際問題的需要可重新選定。

第10頁，共32頁，2023年，2月20日，星期六3、順序表的基本運算

1.順序表的插入操作接口voidInsert(inti,Tx)：在線性表的第i（1≤i≤n+1）個位置上插入一個新元素x。插入前：(a1，…，ai-1，ai，…，an)，插入后：(a1，…，ai-1，x，ai，…，an)，順序表在插入前后的狀態(tài)對比如圖2.12所示。第11頁，共32頁，2023年，2月20日，星期六插入操作要點：

·順序存儲要求邏輯上相鄰的元素存儲在數組中相鄰的單元。

·注意元素移動的方向——后移一個單元。

·從最后一個元素開始移動，直至第i個元素。

分析邊界條件：

·如果表滿了，則引發(fā)上溢異常。

·如果元素的插入位置不合理，則引發(fā)位置異常。第12頁，共32頁，2023年，2月20日，星期六C語言描述

template<classT>

voidSeqList::Insert(inti,Tx)

{

if(length>=MaxSize)throw"上溢";

if(i<1||i>length+1)throw"位置";

for(j=length;j>=i;j--)//注意j指的是元素序號

data[j]=data[j-1];//注意第j個元素存儲在數組下標為j-1處

data[i-1]=x;

length++;}第13頁，共32頁，2023年，2月20日，星期六

2.順序表的刪除

操作接口TDelete(inti)：將線性表中的第i（1≤i≤n）個元素刪除，并返回被刪除元素的值。刪除前：(a1，…，ai-1，ai，ai+1，…，an)，刪除后：(a1，…，ai-1，ai+1，…，an)，順序表刪除前后狀態(tài)的對比如圖2.13所示

第14頁，共32頁，2023年，2月20日，星期六

刪除操作要點：

·元素移動的方向——前移一個單元；

·從第i+1個元素開始移動，直至最后一個元素；

·在移動元素之前要取出被刪元素。分析邊界情況：

·如果表空，則發(fā)生下溢異常；·如果元素的刪除位置不合理，則引發(fā)刪除位置異常。

1.如果表空，則拋出下溢異常;

2.如果刪除位置不合理，則拋出刪除位置異常；

3.取出被刪元素；

4.將第i+1個元素直至最后一個元素分別向前移動一個位置；

5.表長減1，返回被刪元素值；第15頁，共32頁，2023年，2月20日，星期六

C語言描述

template<classT>

TSeqList::Delete(inti)

{

if(length==0)throw"下溢";

if(i<1||i>length)throw"位置";

x=data[i-1];

for(j=i+1;j<=length;j++)for(j=i;j<length;j++)

data[j-2]=data[j-1];data[j-1]=data[j];

length--;

returnx;

}第16頁，共32頁，2023年，2月20日，星期六2.2.3隊列及其基本運算

1.什么是隊列

隊列（queue）是一種只允許在表的一端進行插入，而在另一端進行刪除的線性表。允許插入（入隊）的一端稱為隊尾（rear），允許刪除（出隊）的一端稱為隊頭（front）。不含元素的隊列稱為空隊列。第17頁，共32頁，2023年，2月20日，星期六退出隊列時，也只能按a1,a2,a3,…,an的順序出隊。這和日常生活中的排隊是一致的。出隊列←a1a2a3…an←入隊列↑↑隊頭隊尾

隊列示意圖在隊列中，最先插入的元素，將最先能夠被刪除。反之，最后插入的元素，將最后才能被刪除。因此，隊列又稱為“先進先出”或后進后出的線性表。第18頁，共32頁，2023年，2月20日，星期六

2.隊列的順序存儲結構和基本運算

隊列的順序存儲結構稱為順序隊列。順序隊列通常用一個一維數組來存放隊列中的數據元素。此外，還需設置兩個整形變量front和rear作為隊頭指示器和隊尾指示器，分別指示隊頭和隊尾元素在向量空間中的位置。第19頁，共32頁，2023年，2月20日，星期六我們約定在隊列初始化時，這兩個指示器均置0值。入隊時，將新元素插入到rear所指位置后，再將rear的值加1；出隊時，刪除front所指位置的元素后，再將front的值加1并返回被刪元素。由此可見，當隊頭和隊尾指示器值相等時，隊列為空。

在非空隊列里，front始終指向隊頭元素，而rear始終指向隊尾元素的下一位置。在隊列中，隊尾指示器rear與隊頭指示器front共同反映了隊列中元素動態(tài)變化的情況。第20頁，共32頁，2023年，2月20日，星期六假設給隊列分配的最大存儲空間為4。在圖(b)所示滿隊列狀態(tài)下，如果還有新元素請求入隊，則會出現“上溢”錯誤。

01230123frontfrontrearrear(a)隊列初值為空(b)A、B、C、D入隊

01230123frontrearfrontrear(c)A出隊(d)B、C、D出隊，隊空順序隊列操作示意圖

ABCD

BCD

第21頁，共32頁，2023年，2月20日，星期六在圖(c)所示狀態(tài)下，如果還有新元素請求入隊，這時，雖然隊列的實際可用空間沒有占滿，但由于尾指針已超越存儲空間的上界，故不能做入隊操作，否則會出現“假上溢”的錯誤；在圖(d)所示狀態(tài)下，如果還要進行出隊操作，由于這時隊列已空，隊列的頭、尾指針均已超越存儲空間的上界，故不能進行出隊操作，否則會出現“下溢”的錯誤。第22頁，共32頁，2023年，2月20日，星期六

3.循環(huán)隊列及其運算為避免發(fā)生順序隊列的“假上溢”現象，充分利用隊列的存儲空間，可以將順序隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用，我們稱這樣的隊列為循環(huán)隊列。第23頁，共32頁，2023年，2月20日，星期六

frontrearfrontrear(a)初始隊列為空(b)A、B、C入隊

rearfrontfrontrear(c)D入隊后隊滿(d)A、B、C、D出隊隊空

循環(huán)隊列入、出隊操作示意圖

A3021CBDA3021CB

3021

3021

第24頁，共32頁，2023年，2月20日，星期六在循環(huán)隊列中進行出隊、入隊操作時，頭、尾指針仍要加1，只不過當頭尾指針指向上界時，其加1的操作結果是指向下界0。假設當前循環(huán)隊列最多能容納MAXSIZE個元素，這種循環(huán)意義下的加1操作可表示為：

i=(i+1)%MAXSIZE/*i表示front或rear*/

第25頁，共32頁，2023年，2月20日，星期六在循環(huán)隊列中，僅依據頭尾指針相等，是無法判斷隊列是“空”還是“滿”。要解決這個問題，常用的方法是：少用一個元素空間，約定入隊前，若尾指針加1后等于頭指針，則認為隊列滿（rear所指單元始終為空）。第26頁，共32頁，2023年，2月20日，星期六#defineMAXSIZE100/*符號常量MAXSIZE代表隊列的最大容量100*/typedefcharElemType;/*說明新類型ElemType是字符型*/typedefstruct{ElemTypedata[MAXSIZE];intfront;intrear;}CircularQueue;

/*新類型CircularQueue是結構體*/第27頁，共32頁，2023年，2月20日，星期六

1）

構造一個空隊列VoidInitQueue(CircularQueue*q){q->front=q->rear=0;}

2）判斷隊列空intQueueEmpty(CircularQueue*q){/*隊列為空返回1，否則返回0*/if(q->front==q->rear)exit(1);elseexit(0);}第28頁，共32頁，2023年，2月20日，星期六

3）入隊voidInsertQueue(CircularQueue*q,ElemTypex){if((q->rear+1)%MAXSIZE==q->front){printf("\n隊滿，上溢！");exit(1);}q->data[q->rear]=x;/*新元素插入到隊尾*/

q->rear=(q->rear+1)%MAXSIZE;

/