【正文】 1 第 3章 順序存儲結(jié)構(gòu)的表、堆棧和隊列 數(shù)據(jù)結(jié)構(gòu)（ C++） 2 目錄 順序存儲結(jié)構(gòu) 表和順序表 堆棧和順序堆棧 隊列和順序隊列 優(yōu)先級隊列和順序優(yōu)先級隊列 3 線性表的邏輯結(jié)構(gòu)： 1． 線性表的定義 線性表（ linear list）是 n（ n≥0）個數(shù)據(jù)元素 a1， a2， …a n組成的有限序列。其中 n 稱為數(shù)據(jù)元素的個數(shù)或線性表的長度，當(dāng) n=0時稱為空表， n0時稱為非空表。通常將非空的線性表記為（ a1， a2， …,a n），其中的數(shù)據(jù)元素 ai（ 1≤i≤n）是一個抽象的符號，其具體含義在不同情況下是不同的，即它的數(shù)據(jù)類型可以根據(jù)具體情況而定，本書中，我們將它的類型設(shè)定為 elemtype，表示某一種具體的已知數(shù)據(jù)類型。 4 2． 線性表的特征 從線性表的定義可以看出線性表的特征： （ 1 ）有且僅有一個開始結(jié)點 (表頭結(jié)點 )a1，它沒有直接前驅(qū)，只有一個直接后繼 。 （ 2）有且僅有一個終端結(jié)點 (表尾結(jié)點 )an，它沒有直接后繼，只有一個直接前驅(qū) 。 （ 3） 其它結(jié)點都有一個直接前驅(qū)和直接后繼； （ 4）元素之間為一對一的線性關(guān)系。 5 線性表是一種典型的線性結(jié)構(gòu) ， 用二元組表示為： linear_list=(A,R) 其中 A={ai ∣ 1≤i≤n,n≥0,ai∈ elemtype} R={r} r={ai,ai+1 ∣ 1≤i≤n1} 對應(yīng)的邏輯結(jié)構(gòu)圖如圖所示。 a 1 a 2 …… a n 線性表邏輯結(jié)構(gòu)示意圖 6 順序存儲結(jié)構(gòu) 計算機(jī)所處理的所有的數(shù)據(jù)都要存儲在內(nèi)存中。計算機(jī)高級語言系統(tǒng)對數(shù)據(jù)的存儲結(jié)構(gòu)有四種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、間接地址和仿真指針。其中，順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)是兩種最基本和最常用的存儲結(jié)構(gòu)。本節(jié)討論順序存儲結(jié)構(gòu)，其余三種存儲結(jié)構(gòu)依次在 、 節(jié)和 。 7 順序存儲結(jié)構(gòu)是計算機(jī)中的一種最基本和最主要的數(shù)據(jù)存儲結(jié)構(gòu) 。 在順序存儲結(jié)構(gòu)中 ，用戶向系統(tǒng)申請一塊地址連續(xù)的有限空間用于存儲數(shù)據(jù)元素集合 ， 這樣 ， 任意兩個在邏輯上相鄰的數(shù)據(jù)元素在物理上也必然相鄰 。 在 C++中 ，向系統(tǒng)申請一塊地址連續(xù)的有限空間的方法是使用數(shù)組 。 數(shù)組有靜態(tài)數(shù)組和動態(tài)數(shù)組兩種 。不論是靜態(tài)數(shù)組還是動態(tài)數(shù)組 ， 其功能都是向系統(tǒng)申請一塊地址連續(xù)的有限空間 ， 只是使用的方法不同 。 8 C++中靜態(tài)數(shù)組向系統(tǒng)申請一塊地址連續(xù)的有限空間的方法是使用數(shù)組定義語句 []。 當(dāng)程序運行超出該靜態(tài)數(shù)組定義的范圍時 ， 系統(tǒng)自動回收該靜態(tài)數(shù)組的地址空間 。 一個靜態(tài)數(shù)組定義的例子如下： ＃ include const int MaxSize=100。 void main(void) { int i。 int temp[MaxSize]。 //靜態(tài)申請 MaxSize個整型元素的存儲空間 9 for(i=0。i6。i++) { temp[i]=i+1。 printf (“temp[%d]=%d ＼ n”,i,temp[i])。 //C函數(shù)輸出 //cout“temp[”i“]”temp[i]endl。C++ 輸出 } } 10 當(dāng)程序運行退出主函數(shù)時，系統(tǒng)將自動回收分配給靜態(tài)數(shù)組 temp的地址空間。 C++中動態(tài)數(shù)組向系統(tǒng)申請一塊地址連續(xù)的有限空間的方法是使用動態(tài)存儲分配函數(shù)。動態(tài)數(shù)組存儲空間的回收方法是當(dāng)不再需要該動態(tài)數(shù)組時，使用動態(tài)存儲釋放函數(shù)。 C++中動態(tài)存儲分配函數(shù)用 new，動態(tài)存儲釋放函數(shù)用 delete。 new能自動計算要分配類型的空間大小并自動返回正確的指針類型。 delete能自動釋放由 new分配的存儲空間。 11 new的語法格式是：名字指針 =new類型名 (初始化值 )。 其中 ， 初始化值可為空 。 new分配動態(tài)數(shù)組的語法格式是：名字指針 =new類型名 [N]。 其中 ， N必須是有確定值的整數(shù)型常量或變量 。 delete的語法格式是： delete名字指針 delete釋放動態(tài)數(shù)組的語法格式是：delete []名字指針上例的動態(tài)數(shù)組定義的例子如下： 12 ＃ include ＃ include void main(void) { int i,*temp。 const int MaxSize=100。 temp=new int[MaxSize]。 //動態(tài)申請 MaxSize 13 for(i=0。i6。i++) { temp[i]=i+1。 // couti=itemp[i]= temp[i]endl。 } delete []temp。// } 14 從上例可見 ， 靜態(tài)數(shù)組存儲空間的申請和釋放由系統(tǒng)自動完成 ， 動態(tài)數(shù)組存儲空間的申請和釋放由用戶通過調(diào)用系統(tǒng)函數(shù)完成 。 設(shè)要存儲的數(shù)據(jù)元素為 a0,a1,a2,a3,a4,a5，順序存儲結(jié)構(gòu)（不論是用靜態(tài)數(shù)組還是用動態(tài)數(shù)組）向系統(tǒng)申請了 MaxSize個 ai數(shù)據(jù)類型的存儲空間， size為數(shù)組的當(dāng)前數(shù)組元素個數(shù)。其內(nèi)存結(jié)構(gòu)示意圖如圖 3―1 所示。 15 圖 3―1 順序存儲結(jié)構(gòu)內(nèi)存結(jié)構(gòu)示意圖 16 表和順序表 表 （ List） 是一種可在任意位置進(jìn)行插入和刪除操作的由 n（ n≥0） 個相同類型數(shù)據(jù)元素組成的線性結(jié)構(gòu) ， n是表的長度 ， n=0的表稱作空表 。 從數(shù)據(jù)元素之間的邏輯關(guān)系來劃分 ， 數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種 。 線性結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系為除第一個元素和最后一個元素外 ， 每個數(shù)據(jù)元素都只有一個前驅(qū)元素和一個后繼元素 。 表是最簡單的一種線性結(jié)構(gòu) 。 17 對表的操作方法主要有初始化構(gòu)造表 、 在表的某一位置插入一個元素 、 在表的某一位置刪除一個元素 、 定位某個數(shù)據(jù)元素在表中的存儲位置 、 取表中某個存儲位置的數(shù)據(jù)元素 、 判表是否為空等 。 用順序存儲結(jié)構(gòu)存儲的表稱作順序表 （ SequentList） 。 順序表中任意數(shù)據(jù)元素的存取和訪問可通過它的位置指針 （ 即數(shù)組下標(biāo) ）來進(jìn)行 。 18 順序表的數(shù)據(jù)結(jié)構(gòu)和函數(shù)定義 綜合前面的討論可知 ， 一個順序表涉及的數(shù)據(jù)成員包括數(shù)組 、 數(shù)組的最大元素個數(shù)和當(dāng)前數(shù)組元素的個數(shù) 。 順序表的操作方法和前面討論的表的操作方法相同 ， 主要有初始化構(gòu)造表 、 在表的某一位置插入一個元素 、 在表的某一位置刪除一個元素 、 定位某個數(shù)據(jù)元素在表中的存儲位置 、 取表中某個存儲位置的數(shù)據(jù)元素 、 判表是否為空等 。 使用靜態(tài)數(shù)組方法的順序表的數(shù)據(jù)結(jié)構(gòu)定義如下： 19 const int MaxListSize=100。 ∥ MaxListSize是問題要求的元素數(shù)目的 struct SequentList { elemtype data[MaxListSize]。 //抽象類型 elemtype定義的數(shù)組 int size。//數(shù)據(jù)元素個數(shù) } 20 存儲地址 內(nèi)存排列 位置序號 a0 a1 a2 … ai … an … 0 1 2 … i … n … M a x Li s t S i z e 1 b b+ d … b+ ( i 1) d ? b+(n 1) d 圖 3 2 順序存儲結(jié)構(gòu)示意圖 21 int ListSize(L) //返回元素的個數(shù) size int ListEmpty(L) //表空返回 1；否則返回 int Find (amp。 L, elemtype item) //返回元素 item elemtype GetData(L,int pos)。 //返回位置 pos void Insert(amp。L, elemtype item, int pos)。 //在位置 pos插入元素 item elemtype Delete(amp。L,int pos)。 //刪除位置 pos的元素并返回 void ClearList(amp。L)。 // 22 順序表的函數(shù)實現(xiàn) 順序表數(shù)據(jù)結(jié)構(gòu) SequentList的實現(xiàn)如下： //返回順序表的數(shù)據(jù)元素個數(shù) size int ListSize(SequentList L) { return 。 } //判順序表空否 ， 為空返回 1；不空返回 0 int ListEmpty(SequentList L) { if(==0) return 1。 else return 0。 } 23 //定位元素 item的位置 ， 返回值為 item在順序表中的位置；返回值為 1 int Find(SequentList L, elemtype item) { if(==0) return 1。 int i=0。 while(iamp。amp。item!=[i]) i++。 //尋找 item if(i) return i。 else return 1。 } 24 //返回順序表中位置 pos上的元素 。 elemtype GetData(SequentList L,int pos) { if(pos0‖pos) //取的元素序號必須在 0至 size1 { cerr參數(shù) pos越界出錯 !endl。 exit(1)。/