【正文】 ial Storage Structure） 。 ?主要用于線性數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ) ， 對(duì)于非線性結(jié)構(gòu)進(jìn)行線性化處理后也可實(shí)現(xiàn)順序存儲(chǔ) 。 ?鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是一種基本的存儲(chǔ)表示方法 ， 通常借助于程序設(shè)計(jì)語言中的指針來實(shí)現(xiàn) 。 其他的存儲(chǔ)表示方式 ?存儲(chǔ)表示方式還有 索引存儲(chǔ) 方式和 散列存儲(chǔ) 方式 ，通常是為了檢索的方便所采用的存儲(chǔ)表示方法 。 ?選擇何種存儲(chǔ)結(jié)構(gòu)要依具體問題的要求而定 ， 既要考慮問題表示和運(yùn)算的方便性 ， 也還會(huì)考慮到實(shí)現(xiàn)算法的時(shí)間和空間效率要求 。 ?各種數(shù)據(jù)結(jié)構(gòu) ， 分別提供了不同類型的數(shù)據(jù)在作為計(jì)算機(jī)程序數(shù)據(jù)時(shí)的組織 、 管理 、 存儲(chǔ) 、 運(yùn)算和處理的方法和技術(shù) 。 如各種基本類型 ， 數(shù)組 、字符串等 ?有些數(shù)據(jù)結(jié)構(gòu) ， 在程序設(shè)計(jì)語言中沒有實(shí)現(xiàn) ， 要靠程序設(shè)計(jì)人員利用語言中提供的某些設(shè)施去實(shí)現(xiàn)或模擬實(shí)現(xiàn) ，如棧 、 隊(duì)列 、 樹 、 二叉樹 、 圖 、 網(wǎng)絡(luò)等 。 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 、 數(shù)據(jù)元素與數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)的基本概念 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型 ?抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西 ， 忽略掉非本質(zhì)的細(xì)節(jié) 。 ?用戶在使用數(shù)據(jù)類型時(shí) ， 既不需要了解該數(shù)據(jù)類型在計(jì)算機(jī)內(nèi)部是如何表示的 ， 也不需要知道其操作是如何實(shí)現(xiàn)的 ，只須集中精力考慮所要求解的問題應(yīng)該如何去解決 。 抽象數(shù)據(jù)類型（續(xù)） ?抽象數(shù)據(jù)類型 （ Abstract Data Type簡(jiǎn)記為 ADT） 是指一個(gè)數(shù)據(jù)模型以及定義在該數(shù)據(jù)模型上的一組操作 。 ?當(dāng)數(shù)據(jù)模型表現(xiàn)為一個(gè)數(shù)據(jù)結(jié)構(gòu)時(shí) ， 抽象數(shù)據(jù)類型就是這個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在這個(gè)數(shù)據(jù)結(jié)構(gòu)上的一組運(yùn)算；這種情況是我們討論和學(xué)習(xí)抽象數(shù)據(jù)類型概念的基礎(chǔ) ， 也是數(shù)據(jù)結(jié)構(gòu)課程對(duì)抽象數(shù)據(jù)類型定義的根本要求 。 抽象數(shù)據(jù)類型的定義 ?抽象數(shù)據(jù)類型的定義 ， 僅取決于它的一組邏輯特性 ， 而與它在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān) 。 ?抽象數(shù)據(jù)類型可以通過已有的數(shù)據(jù)類型來表示和實(shí)現(xiàn) ， 利用已有的數(shù)據(jù)類型來說明新的結(jié)構(gòu) ，利用已經(jīng)實(shí)現(xiàn)了的操作來完成新的操作 。 抽象數(shù)據(jù)類型（續(xù)） ?抽象數(shù)據(jù)類型是算法設(shè)計(jì)和程序設(shè)計(jì)中的重要概念 ， 這個(gè)概念明確地把數(shù)據(jù)結(jié)構(gòu)與作用在該結(jié)構(gòu)上的運(yùn)算緊密地聯(lián)系起來 。 ?需要指出的是 ， 基本數(shù)據(jù)類型已隱含著數(shù)據(jù)結(jié)構(gòu)和定義在該結(jié)構(gòu)上的運(yùn)算的統(tǒng)一 ， 只是當(dāng)時(shí)尚未形成抽象數(shù)據(jù)類型的概念罷了 。 抽象數(shù)據(jù)類型（續(xù)） ?抽象數(shù)據(jù)類型的設(shè)計(jì)和實(shí)現(xiàn)不可能象基本數(shù)據(jù)類型那樣可以規(guī)范 、 內(nèi)置和一勞永逸 。 ?另一方面 ， 把抽象數(shù)據(jù)類型的實(shí)現(xiàn)作為私有部分封裝在其實(shí)現(xiàn)模塊內(nèi) ， 讓使用者看不到 ， 也不能直接操作該類型所存儲(chǔ)的數(shù)據(jù) ， 只能通過界面中的服務(wù)來訪問這些數(shù)據(jù) 。 ?在程序中引入數(shù)組的充分理由是： ?為了求解問題有引入數(shù)組的必要性 ， 如需要記住一組值等； ?基于問題求解算法的效率考慮 ， 引入數(shù)組可使算法效率更高； ?基于概念上或運(yùn)算處理上的自然 、 簡(jiǎn)單和方便性方面考慮需要引入數(shù)組 。 ?數(shù)組結(jié)構(gòu)的 特點(diǎn) 是： ?數(shù)組元素的個(gè)數(shù)固定 ， 元素間的邏輯關(guān)系由數(shù)組元素的序號(hào) （ 即數(shù)組的下標(biāo) ） 來體現(xiàn) 。 ?數(shù)組元素的下標(biāo)具有上下界約束且下標(biāo)有序 ， 下標(biāo)與數(shù)組元素的對(duì)應(yīng)關(guān)系使得數(shù)組元素可以隨機(jī)訪問 。 也可以說數(shù)組是由數(shù)組元素和下標(biāo)構(gòu)成的有序?qū)Y(jié)構(gòu) ， 結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素都與一組下標(biāo)有關(guān) 。通常只有賦值和讀取數(shù)組元素兩種操作： ?賦值：給定一組下標(biāo) ， 把指定值 （ 如初始值 、 修改值 、運(yùn)算值等 ） 存入相應(yīng)的數(shù)組元素中； ?讀取：給定一組下標(biāo) ， 讀取相應(yīng)的數(shù)組元素 （ 通常是為了使用其值或打印輸出等目的 ） 。 ?如在 C語言中 ， int A[8]就說明了一個(gè)一維整型數(shù)組 A；進(jìn)而就可以對(duì) A施加不同的操作 ， 一般方法是利用循環(huán)控制變量值的變化 ， 從下標(biāo)下界到上界之間 （ 或相反次序 ）訪問相應(yīng)的數(shù)組元素 ， 其一般格式是 for(i=0。 i++) {對(duì) A的第 i個(gè)元素執(zhí)行某個(gè)指定的操作 } ?當(dāng)數(shù)組的下標(biāo)為一個(gè)時(shí) ， 稱之為 一維數(shù)組 ?當(dāng)數(shù)組的下標(biāo)為兩個(gè)或兩個(gè)以上時(shí) ， 稱之為 二維數(shù)組 或 多維數(shù)組 。 ?數(shù)組的線性的 、 均勻的結(jié)構(gòu)和計(jì)算機(jī)內(nèi)存單元的一維結(jié)構(gòu) ， 決定了對(duì)數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)是最佳選擇 。 ?對(duì)于二維數(shù)組和多維數(shù)組 。 二維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)舉例 ?二維數(shù)組可以把它看作是由每一行元素作為一個(gè)元素構(gòu)成的一維數(shù)組 （ 行為主序 ） ， ?二維數(shù)組也可以看作是由每一列元素作為一個(gè)元素構(gòu)成的一維數(shù)組 （ 列為主序 ） 。 ?若選定一種約定 ， 則每個(gè)數(shù)組元素相對(duì)于存儲(chǔ)區(qū)域起始地址的位置也就隨之確定了 。 a11 a12 ┄ a1n a21 a22 ┄ a2n ┄ ┄ am1 am2 ┄ amn 第 1行 第 2行 第 m行 列為主序的優(yōu)先存儲(chǔ)策略 ?列為主序 的優(yōu)先存儲(chǔ)策略是將數(shù)組元素按列優(yōu)先關(guān)系排列 ， 第 j+1列中的元素緊跟在第 j列中元素的后面；同一列中的元素以行下標(biāo)次序排列 。 ?若以 行為主序 優(yōu)先存儲(chǔ) ， 考慮數(shù)組元素 aij的地址計(jì)算公式 。 ?對(duì)于一般情況下的數(shù)組 A[c1‥ d1,c2‥ d2] ?在 行為主序 之下 aij的地址計(jì)算公式為 loc(aij)= loc(a11)+((ic1)*(d2c2+1)+jc2)*e ?在 列為主序 之下 aij的地址計(jì)算公式為 loc(aij)= loc(a11)+((ic2)*(d1c1+1)+ic1)*e 數(shù)組 數(shù)組及其運(yùn)算 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 特殊矩陣的壓縮存儲(chǔ) 特殊矩陣的壓縮存儲(chǔ) ?在科學(xué)計(jì)算和工程應(yīng)用中 ， 常常要用到矩陣的概念 。 但是在有些情況下 ， 如特殊矩陣和稀疏矩陣 ， 采用二維數(shù)組的存儲(chǔ)方式會(huì)浪費(fèi)大量存儲(chǔ)空間 。 ?所謂 壓縮存儲(chǔ) ， 是指為多個(gè)值相同的元素只分配一個(gè)元素的存儲(chǔ)空間 ， 對(duì)零元素不分配存儲(chǔ)空間 。 ?對(duì)角矩陣的 特點(diǎn) 是除了主對(duì)角線上的元素外其余元素都為零 。 其非零元素壓縮存儲(chǔ)位置 k與矩陣下標(biāo)的對(duì)應(yīng)關(guān)系為 k=i或 k=j， 通過這個(gè)關(guān)系可對(duì)矩陣中的非零元素隨機(jī)存取 。 ?對(duì)三對(duì)角矩陣的壓縮存儲(chǔ)方法是 ， 按行為主序優(yōu)先存儲(chǔ)方法把非零區(qū)的三對(duì)角元素依次順序存儲(chǔ)到一片連續(xù)的存儲(chǔ)空間中 。 故有 k=2*( i1)+ j 三對(duì)角矩陣的壓縮存儲(chǔ)圖示 壓縮存儲(chǔ) ?上三角矩陣是指矩陣的主對(duì)角線以下的所有元素均為同一常數(shù)c或零的 n階矩陣 。 ?其映像關(guān)系為 ， 若 ij， aij處于下三角區(qū) ， 值必為常數(shù) c， 存儲(chǔ)分配在 n*(n+1)/2+1處；若 i≤j ， aij處在上三角區(qū) ， 在前 i1行共存儲(chǔ)的元素?cái)?shù)為 n+(n1)+… +(ni+2)=(i1)*(2ni+2)/2個(gè) ，在第 i行它是第 ji+1個(gè) ， 故 aij為第 (i1)*(2ni+2)/2+ ji+1=(i1)*(2ni)/2+j個(gè)存儲(chǔ)分配的元素 。 ?處在下三角的元素 aij， 其前 i1行共有 i*(i1)/2個(gè)元素 ， 在第 i行它處于第 j個(gè)位置 ， 即 aij處于存儲(chǔ)分配區(qū)的第 i*(i1)/2+j個(gè) 。 ?由于對(duì)稱矩陣中元素關(guān)于主對(duì)角線對(duì)稱 ， 因此只需要存儲(chǔ)其上三角中的元素或下三角中的元素 ， 使對(duì)稱元素共享同一存儲(chǔ)空間 。 第 2章 常用數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)組 串 串 ?所謂串 ， 就是我們?cè)诟呒?jí)語言程序設(shè)計(jì)課程中學(xué)習(xí)和使用過的字符串 ， 是大家熟知的概念 。 ?本節(jié)著重討論串的存儲(chǔ)結(jié)構(gòu)以及主要運(yùn)算的實(shí)現(xiàn) ，如順序存儲(chǔ)分配的三種方式 、 堆式存儲(chǔ)分配策略以及在 “ 向量存儲(chǔ) ， 定長(zhǎng)結(jié)構(gòu) ” 基礎(chǔ)上幾種串運(yùn)算的實(shí)現(xiàn)算法 ， 并簡(jiǎn)要介紹漢字串的概念 。 記作 : s=“a1a2… an” (n≥ 0) 其中： s是串名 ， 用雙引號(hào)括起來的字符序列是串的值 （ 不含雙引號(hào) ） ； ai（ 1≤i≤n ） 是相應(yīng)程序設(shè)計(jì)語言中允許使用的字符集中的任意字符； n為串中的字符個(gè)數(shù) ， 稱作 串的長(zhǎng)度 。 ?要注意空串與空格串的區(qū)別 ， 空格串中有一個(gè)或多個(gè)空格字符 ， 串的長(zhǎng)度大于零 。字符在串中的序號(hào)稱作該字符在串中的位置 ， 子串在主串中的位置用子串的第一個(gè)字符在主串中的位置來表示 。 ?串結(jié)構(gòu)的形式化定義為 string=(D,R) 其中： D={ ai︱ ai∈character ， i=1,2… n， n≥ 0}, R={ ai1 ai︱ ai1,ai∈D ， i=1,2… n }。 把字符串常量 chars的值賦給串變量 s。 把串變量 t的值復(fù)制到串變量 s中 。 若 st返回值 0， 若 s=t返回值 =0，若 st 返回值 0。 返回值為串 s中字符的個(gè)數(shù) （ 串長(zhǎng) ） 。 把串 t的值緊接著串 s的值之后形成的新串值存入串變量 l中返回 。 ?SubString(t,s,i,len)：求子串 。 該運(yùn)算要求1≤i≤StrLength(s)+ 1且 0≤len≤StrLength(s) i +1。 ?下面四種其它的串運(yùn)算都有著重要的應(yīng)用： ?StrInsert(s,i,t)： 串插入 。 其中 ，1≤ i≤ StrLength(s)+1。 運(yùn)算的結(jié)果是從 s串中刪去自第 i個(gè)字符起的 len 個(gè)字符后得到的新串 。 ?StrIndex(s,t)： 子串定位 。 其中要求子串 t為非空串 。 運(yùn)算的結(jié)果是以串 v替換所有在串 s中出現(xiàn)的和非空串 t相等的不重疊的子串后得到的新串 。 ?在高級(jí)程序設(shè)計(jì)語言中 ， 大都為字符串設(shè)立了專門的數(shù)據(jù)類型 。 用雙引號(hào)括起來的字符序列為字符串常量 ， 也可以用宏定義 define來定義字符串常量的標(biāo)識(shí)符 ， 如 define CITY shanghai ?對(duì)于字符串變量 ， C語言的說明為一維字符型數(shù)組 ， 如 static char C[100]； ?為字符串分配一個(gè)固定長(zhǎng)度的一組地址連續(xù)的存儲(chǔ)單元的存儲(chǔ)分配方法稱之為 定長(zhǎng)順序存儲(chǔ)分配 。 ?如串 s=“data structure ”的緊縮存儲(chǔ)如下： ?其中字符串長(zhǎng)度 18存儲(chǔ)在開始處 ， “ ” 表示空格字符 ，共占用五個(gè)存儲(chǔ)單元 。 這種存儲(chǔ)方式的優(yōu)點(diǎn)是充分地利用了空間 ， 然而四個(gè)字符一個(gè)地址運(yùn)算不太方便 。 串的長(zhǎng)度不顯式存儲(chǔ) ，由串中字符占存儲(chǔ)單元的數(shù)目來隱式確定 。 ?例如對(duì)串 s=“data structure ”的非緊縮存儲(chǔ)如右圖所示 。 ?每個(gè)地址對(duì)應(yīng)一個(gè)字節(jié) ， 一個(gè)字節(jié)正好存放一個(gè)字符 。 ?這種存儲(chǔ)方式既不浪費(fèi)空間 ， 又使串中每個(gè)字符與惟一地址對(duì)應(yīng)方便了運(yùn)算 ， 對(duì)于按字節(jié)編址的計(jì)算機(jī)而言是非常合適的 。 定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)的運(yùn)算實(shí)現(xiàn) ?為了方便討論 ， 我們把串的類型說明改寫成如下形式： define STRINGLEN 81 struct string {int len。 ?由于串賦值和串復(fù)制在高級(jí)程序設(shè)計(jì)語言中是通過賦值語句來完成的 ， 所以在這里只討論其余四種基本運(yùn)算 ， 即串比較 、 求串長(zhǎng) 、 串聯(lián)接和求子串運(yùn)算 。 {int i=0。amp。amp。 return sch[i]tch[i]。 （ 1） ?按假設(shè)的串類型說明 ， 由于有串長(zhǎng)域 len故可直接返回其值即可 。 {return slen。 ?所以改寫算法為： int StrLength(s) STRING *s。 /*初始化數(shù)組下標(biāo)和串長(zhǎng)域 len*/ slen=0。