線性表及其順序存儲(chǔ)結(jié)構(gòu)

線性表及其順序存儲(chǔ)結(jié)構(gòu)第一頁(yè)，共三十二頁(yè)，編輯于2023年，星期三第二頁(yè)，共三十二頁(yè)，編輯于2023年，星期三2.2.1線性表及其運(yùn)算1、概念線性表（簡(jiǎn)稱表）：零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度?！らL(zhǎng)度等于零時(shí)稱為空表，通常記為：L＝()；·非空表通常記為：L＝(a1，a2，……，an)。理解線性表的定義有以下要點(diǎn)：⑴序列——順序性：元素具有線性順序，第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其他每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。⑵有限——有限性：元素個(gè)數(shù)有限，在計(jì)算機(jī)中處理的對(duì)象都是有限的。⑶相同類型——相同性：元素取自于同一個(gè)數(shù)據(jù)對(duì)象，這意味著每個(gè)元素占用相同數(shù)量的存儲(chǔ)單元。⑷元素類型不確定——抽象性：數(shù)據(jù)元素的類型是抽象的、不具體的，需要根據(jù)具體問(wèn)題確定。第三頁(yè)，共三十二頁(yè)，編輯于2023年，星期三順序表用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表(a1，a2，……，an)的順序存儲(chǔ)示意圖如圖2.5所示。由于線性表中每個(gè)數(shù)據(jù)元素的類型相同，可以用C++語(yǔ)言中的一維數(shù)組來(lái)實(shí)現(xiàn)順序表，也就是把線性表中相鄰的元素存儲(chǔ)在數(shù)組中相鄰的位置，如圖2.6所示第四頁(yè)，共三十二頁(yè)，編輯于2023年，星期三在稍微復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素還可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。例如，某班的學(xué)生情況登記表是一個(gè)復(fù)雜的線性表，表中每一個(gè)學(xué)生的情況就組成了線性表中的每一個(gè)元素，每一個(gè)數(shù)據(jù)元素包括學(xué)號(hào)、姓名、性別、入學(xué)成績(jī)4個(gè)數(shù)據(jù)項(xiàng)。

第五頁(yè)，共三十二頁(yè)，編輯于2023年，星期三2、線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表。

線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：①線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；②

線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

第六頁(yè)，共三十二頁(yè)，編輯于2023年，星期三假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址（即首地址）為ADR(a1)，每一個(gè)數(shù)據(jù)元素占k個(gè)字節(jié)，則線性表中第i個(gè)元素ai在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為：ADR(ai)=ADR(a1)+(i-1)k第七頁(yè)，共三十二頁(yè)，編輯于2023年，星期三長(zhǎng)度為n的線性表在計(jì)算機(jī)中的順序存儲(chǔ)結(jié)構(gòu)第八頁(yè)，共三十二頁(yè)，編輯于2023年，星期三在程序設(shè)計(jì)語(yǔ)言中，通常定義一個(gè)一維數(shù)組來(lái)表示線性表的順序存儲(chǔ)空間。應(yīng)注意數(shù)組的基本類型要與線性表中數(shù)據(jù)元素的類型相同。數(shù)組需要根據(jù)情況預(yù)設(shè)足夠的大小，同時(shí)還需要一個(gè)變量指出線性表在數(shù)組中的當(dāng)前狀況，如元素個(gè)數(shù)或最后一個(gè)元素在數(shù)組中的位置等。這兩方面的信息共同描述一個(gè)順序表，可將它們封裝在一起。對(duì)C語(yǔ)言，順序表可定義如下：

第九頁(yè)，共三十二頁(yè)，編輯于2023年，星期三對(duì)C語(yǔ)言，順序表可定義如下：#defineMaxLength50typedefintElemType;typedefstruct

{ElemTypelist[MaxLength];intlength;}SeqList;

今后使用此定義時(shí)，MaxLength及ElemType要根據(jù)實(shí)際問(wèn)題的需要可重新選定。

第十頁(yè)，共三十二頁(yè)，編輯于2023年，星期三3、順序表的基本運(yùn)算

1.順序表的插入操作接口voidInsert(inti,Tx)：在線性表的第i（1≤i≤n+1）個(gè)位置上插入一個(gè)新元素x。插入前：(a1，…，ai-1，ai，…，an)，插入后：(a1，…，ai-1，x，ai，…，an)，順序表在插入前后的狀態(tài)對(duì)比如圖2.12所示。第十一頁(yè)，共三十二頁(yè)，編輯于2023年，星期三插入操作要點(diǎn)：

·順序存儲(chǔ)要求邏輯上相鄰的元素存儲(chǔ)在數(shù)組中相鄰的單元。

·注意元素移動(dòng)的方向——后移一個(gè)單元。

·從最后一個(gè)元素開(kāi)始移動(dòng)，直至第i個(gè)元素。

分析邊界條件：

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

·如果元素的插入位置不合理，則引發(fā)位置異常。第十二頁(yè)，共三十二頁(yè)，編輯于2023年，星期三C語(yǔ)言描述

template<classT>

voidSeqList::Insert(inti,Tx)

{

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

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

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

data[j]=data[j-1];//注意第j個(gè)元素存儲(chǔ)在數(shù)組下標(biāo)為j-1處

data[i-1]=x;

length++;}第十三頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

2.順序表的刪除

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

第十四頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

刪除操作要點(diǎn)：

·元素移動(dòng)的方向——前移一個(gè)單元；

·從第i+1個(gè)元素開(kāi)始移動(dòng)，直至最后一個(gè)元素；

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

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

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

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

3.取出被刪元素；

4.將第i+1個(gè)元素直至最后一個(gè)元素分別向前移動(dòng)一個(gè)位置；

5.表長(zhǎng)減1，返回被刪元素值；第十五頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

C語(yǔ)言描述

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;

}第十六頁(yè)，共三十二頁(yè)，編輯于2023年，星期三2.2.3隊(duì)列及其基本運(yùn)算

1.什么是隊(duì)列

隊(duì)列（queue）是一種只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入（入隊(duì)）的一端稱為隊(duì)尾（rear），允許刪除（出隊(duì)）的一端稱為隊(duì)頭（front）。不含元素的隊(duì)列稱為空隊(duì)列。第十七頁(yè)，共三十二頁(yè)，編輯于2023年，星期三退出隊(duì)列時(shí)，也只能按a1,a2,a3,…,an的順序出隊(duì)。這和日常生活中的排隊(duì)是一致的。出隊(duì)列←a1a2a3…an←入隊(duì)列↑↑隊(duì)頭隊(duì)尾

隊(duì)列示意圖在隊(duì)列中，最先插入的元素，將最先能夠被刪除。反之，最后插入的元素，將最后才能被刪除。因此，隊(duì)列又稱為“先進(jìn)先出”或后進(jìn)后出的線性表。第十八頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

2.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列。順序隊(duì)列通常用一個(gè)一維數(shù)組來(lái)存放隊(duì)列中的數(shù)據(jù)元素。此外，還需設(shè)置兩個(gè)整形變量front和rear作為隊(duì)頭指示器和隊(duì)尾指示器，分別指示隊(duì)頭和隊(duì)尾元素在向量空間中的位置。第十九頁(yè)，共三十二頁(yè)，編輯于2023年，星期三我們約定在隊(duì)列初始化時(shí)，這兩個(gè)指示器均置0值。入隊(duì)時(shí)，將新元素插入到rear所指位置后，再將rear的值加1；出隊(duì)時(shí)，刪除front所指位置的元素后，再將front的值加1并返回被刪元素。由此可見(jiàn)，當(dāng)隊(duì)頭和隊(duì)尾指示器值相等時(shí)，隊(duì)列為空。

在非空隊(duì)列里，front始終指向隊(duì)頭元素，而rear始終指向隊(duì)尾元素的下一位置。在隊(duì)列中，隊(duì)尾指示器rear與隊(duì)頭指示器front共同反映了隊(duì)列中元素動(dòng)態(tài)變化的情況。第二十頁(yè)，共三十二頁(yè)，編輯于2023年，星期三假設(shè)給隊(duì)列分配的最大存儲(chǔ)空間為4。在圖(b)所示滿隊(duì)列狀態(tài)下，如果還有新元素請(qǐng)求入隊(duì)，則會(huì)出現(xiàn)“上溢”錯(cuò)誤。

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

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

ABCD

BCD

第二十一頁(yè)，共三十二頁(yè)，編輯于2023年，星期三在圖(c)所示狀態(tài)下，如果還有新元素請(qǐng)求入隊(duì)，這時(shí)，雖然隊(duì)列的實(shí)際可用空間沒(méi)有占滿，但由于尾指針已超越存儲(chǔ)空間的上界，故不能做入隊(duì)操作，否則會(huì)出現(xiàn)“假上溢”的錯(cuò)誤；在圖(d)所示狀態(tài)下，如果還要進(jìn)行出隊(duì)操作，由于這時(shí)隊(duì)列已空，隊(duì)列的頭、尾指針均已超越存儲(chǔ)空間的上界，故不能進(jìn)行出隊(duì)操作，否則會(huì)出現(xiàn)“下溢”的錯(cuò)誤。第二十二頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

3.循環(huán)隊(duì)列及其運(yùn)算為避免發(fā)生順序隊(duì)列的“假上溢”現(xiàn)象，充分利用隊(duì)列的存儲(chǔ)空間，可以將順序隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用，我們稱這樣的隊(duì)列為循環(huán)隊(duì)列。第二十三頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

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

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

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

A3021CBDA3021CB

3021

3021

第二十四頁(yè)，共三十二頁(yè)，編輯于2023年，星期三在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭、尾指針仍要加1，只不過(guò)當(dāng)頭尾指針指向上界時(shí)，其加1的操作結(jié)果是指向下界0。假設(shè)當(dāng)前循環(huán)隊(duì)列最多能容納MAXSIZE個(gè)元素，這種循環(huán)意義下的加1操作可表示為：

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

第二十五頁(yè)，共三十二頁(yè)，編輯于2023年，星期三在循環(huán)隊(duì)列中，僅依據(jù)頭尾指針相等，是無(wú)法判斷隊(duì)列是“空”還是“滿”。要解決這個(gè)問(wèn)題，常用的方法是：少用一個(gè)元素空間，約定入隊(duì)前，若尾指針加1后等于頭指針，則認(rèn)為隊(duì)列滿（rear所指單元始終為空）。第二十六頁(yè)，共三十二頁(yè)，編輯于2023年，星期三#defineMAXSIZE100/*符號(hào)常量MAXSIZE代表隊(duì)列的最大容量100*/typedefcharElemType;/*說(shuō)明新類型ElemType是字符型*/typedefstruct{ElemTypedata[MAXSIZE];intfront;intrear;}CircularQueue;

/*新類型CircularQueue是結(jié)構(gòu)體*/第二十七頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

1）

構(gòu)造一個(gè)空隊(duì)列VoidInitQueue(CircularQueue*q){q->front=q->rear=0;}

2）判斷隊(duì)列空intQueueEmpty(CircularQueue*q){/*隊(duì)列為空返回1，否則返回0*/if(q->front==q->rear)exit(1);elseexit(0);}第二十八頁(yè)，共三十二頁(yè)，編輯于2023年，星期三

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

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

/*