【文章內(nèi)容簡介】 j個非零元素 ， 此式也正好符合第一行的兩個非零元素的情況 。 故有 k=2*( i1)+ j 三對角矩陣的壓縮存儲圖示 壓縮存儲 ?上三角矩陣是指矩陣的主對角線以下的所有元素均為同一常數(shù)c或零的 n階矩陣 。 ?對上三角矩陣的壓縮存儲方法是 ， 對處于下三角 （ 不含主對角線 ） 的常數(shù) c， 在最后分配一個元素空間；對處于上三角 （ 含主對角線 ） 的每個元素按行為主序優(yōu)先存儲方法依次順序存儲分配空間 ， 需要 n*(n+1)/2個元素空間；共需要 n*(n+1)/2+1個元素空間 。 ?其映像關(guān)系為 ， 若 ij， aij處于下三角區(qū) ， 值必為常數(shù) c， 存儲分配在 n*(n+1)/2+1處；若 i≤j ， aij處在上三角區(qū) ， 在前 i1行共存儲的元素數(shù)為 n+(n1)+… +(ni+2)=(i1)*(2ni+2)/2個 ，在第 i行它是第 ji+1個 ， 故 aij為第 (i1)*(2ni+2)/2+ ji+1=(i1)*(2ni)/2+j個存儲分配的元素 。 所以有 上三角矩陣的壓縮存儲圖示 壓縮存儲 ?下三角矩陣與上三角矩陣對應(yīng) ， 其常數(shù)在上三角區(qū)（ 不含主對角線 ） ， 壓縮存儲方法也類似 ， 以行為主序存儲下三角部分 。 ?處在下三角的元素 aij， 其前 i1行共有 i*(i1)/2個元素 ， 在第 i行它處于第 j個位置 ， 即 aij處于存儲分配區(qū)的第 i*(i1)/2+j個 。 于是我們有 下三角矩陣的壓縮存儲圖示 壓縮存儲 矩陣的壓縮存儲 ?在 n階矩陣中 ， 若元素滿足 aij=aji則稱之為對稱矩陣 。 ?由于對稱矩陣中元素關(guān)于主對角線對稱 ， 因此只需要存儲其上三角中的元素或下三角中的元素 ， 使對稱元素共享同一存儲空間 。 ?假如只存儲下三角中的元素 ， 則需存儲元素總數(shù)為n*(n+1)/2個 ， 按行為主序順序存儲 ， 其映像關(guān)系為 ?也可以給出一個統(tǒng)一的對應(yīng)關(guān)系為 k= I*(I1)/2+J 其中 ， I=max(i,j)， J=min(i,j)。 第 2章 常用數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)組 串 串 ?所謂串 ， 就是我們在高級語言程序設(shè)計課程中學(xué)習(xí)和使用過的字符串 ， 是大家熟知的概念 。 ?串是許多軟件系統(tǒng)的操作對象 ， 如字符編輯系統(tǒng) 、情報檢索系統(tǒng) 、 詞法分析系統(tǒng) 、 符號處理系統(tǒng) 、 語言翻譯系統(tǒng)等 ， 有著十分廣泛的應(yīng)用 。 ?本節(jié)著重討論串的存儲結(jié)構(gòu)以及主要運算的實現(xiàn) ，如順序存儲分配的三種方式 、 堆式存儲分配策略以及在 “ 向量存儲 ， 定長結(jié)構(gòu) ” 基礎(chǔ)上幾種串運算的實現(xiàn)算法 ， 并簡要介紹漢字串的概念 。 串 串的基本概念 串的定長順序存儲及運算實現(xiàn) 模式匹配 串的堆式動態(tài)存儲及運算實現(xiàn) 漢字串 串的基本概念 ?串 （ String） 是由零個或多個字符組成的有限序列 。 記作 : s=“a1a2… an” (n≥ 0) 其中： s是串名 ， 用雙引號括起來的字符序列是串的值 （ 不含雙引號 ） ； ai（ 1≤i≤n ） 是相應(yīng)程序設(shè)計語言中允許使用的字符集中的任意字符； n為串中的字符個數(shù) ， 稱作 串的長度 。 ?零個字符的串稱作 空串 ， 它的長度為零 ， 串內(nèi)無任何字符 。 ?要注意空串與空格串的區(qū)別 ， 空格串中有一個或多個空格字符 ， 串的長度大于零 。 串的基本概念（續(xù)） ?串中任意多個連續(xù)字符組成的子序列稱作該串的 子串 （ Substring） ， 包含子串的串稱作該子串的 主串 。字符在串中的序號稱作該字符在串中的位置 ， 子串在主串中的位置用子串的第一個字符在主串中的位置來表示 。 ?兩個串相等是指這兩個串的值相等 ， 即兩個串長度相等且對應(yīng)字符都相同時才相等 。 ?串結(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 }。 串的基本運算（六種） ?StrAssign(s,chars)：串賦值 。 把字符串常量 chars的值賦給串變量 s。 ?StrCopy(s,t)：串復(fù)制 。 把串變量 t的值復(fù)制到串變量 s中 。 ?StrCompare(s,t)：串比較 。 若 st返回值 0， 若 s=t返回值 =0，若 st 返回值 0。 ?StrLenth(s)：求串長 。 返回值為串 s中字符的個數(shù) （ 串長 ） 。 ?StrConcat(l,s,t)：串聯(lián)接 。 把串 t的值緊接著串 s的值之后形成的新串值存入串變量 l中返回 。 例如 ， 若 s=“baodao”，t=“taiwan”， 則 l=“baodaotaiwan”。 ?SubString(t,s,i,len)：求子串 。 把串 s 中第 i個字符開始的長度為 len的字符序列存入串變量 t中返回 。 該運算要求1≤i≤StrLength(s)+ 1且 0≤len≤StrLength(s) i +1。 串的其它運算（四種） ?其它的串運算都可以由這六種基本運算來實現(xiàn) 。 ?下面四種其它的串運算都有著重要的應(yīng)用： ?StrInsert(s,i,t)： 串插入 。 運算的結(jié)果是把 t串插入到 s串中第 i 個 字 符 之 前 得 到 的 新 串 。 其中 ，1≤ i≤ StrLength(s)+1。 ?StrDelete(s,i,len)： 串刪除 。 運算的結(jié)果是從 s串中刪去自第 i個字符起的 len 個字符后得到的新串 。 其中 ，1≤ i≤ StrLength(s)， 0≤ len≤ StrLength(s) i +1。 ?StrIndex(s,t)： 子串定位 。 若在主串 s中存在等于 t的子串 ， 則返回 t在 s中首次出現(xiàn)的位置 ， 否則返回值為 1。 其中要求子串 t為非空串 。 ?StrReplace(s,t,v)： 子串替換 。 運算的結(jié)果是以串 v替換所有在串 s中出現(xiàn)的和非空串 t相等的不重疊的子串后得到的新串 。 串 串的基本概念 串的定長順序存儲及運算實現(xiàn) 模式匹配 串的堆式動態(tài)存儲及運算實現(xiàn) 漢字串 串的定長順序存儲 ?當(dāng)一維數(shù)組的基類型是字符類型 ， 形成的字符數(shù)組即字符串或串 。 ?在高級程序設(shè)計語言中 ， 大都為字符串設(shè)立了專門的數(shù)據(jù)類型 。 ?在 C語言中 ， 有串常量和串變量的概念 。 用雙引號括起來的字符序列為字符串常量 ， 也可以用宏定義 define來定義字符串常量的標(biāo)識符 ， 如 define CITY shanghai ?對于字符串變量 ， C語言的說明為一維字符型數(shù)組 ， 如 static char C[100]； ?為字符串分配一個固定長度的一組地址連續(xù)的存儲單元的存儲分配方法稱之為 定長順序存儲分配 。 定長順序存儲 ——緊縮方式 ?計算機按 字 編址 、 每個單元存放四個字符 。 ?如串 s=“data structure ”的緊縮存儲如下： ?其中字符串長度 18存儲在開始處 ， “ ” 表示空格字符 ，共占用五個存儲單元 。 ?緊縮方式對串長是顯式地直接存儲 ， 字符依次順序放在連續(xù)的幾個單元中 。 這種存儲方式的優(yōu)點是充分地利用了空間 ， 然而四個字符一個地址運算不太方便 。 定長順序存儲 ——非緊縮方式 ?計算機按 字 編址 ， 每個單元存放一個字符 。 串的長度不顯式存儲 ，由串中字符占存儲單元的數(shù)目來隱式確定 。 ?非緊縮存儲方式方便了串運算 ，但存儲空間沒有得到有效利用 。 ?例如對串 s=“data structure ”的非緊縮存儲如右圖所示 。 定長順序存儲 —單字節(jié)存儲方式 ?計算機按 字節(jié) 編址 ， 每個字節(jié)存放一個字符 。 ?每個地址對應(yīng)一個字節(jié) ， 一個字節(jié)正好存放一個字符 。 這時的串長度也不必存儲 ，由串占用的字節(jié)數(shù)隱式確定；也可用特殊字符作為串的結(jié)束標(biāo)志 ， 如用 “ \0”作結(jié)束標(biāo)志 。 ?這種存儲方式既不浪費空間 ， 又使串中每個字符與惟一地址對應(yīng)方便了運算 ， 對于按字節(jié)編址的計算機而言是非常合適的 。 ?例如對串 s=“data structure ”的 單字節(jié)存儲方式 如右圖所示 。 定長順序存儲結(jié)構(gòu)的運算實現(xiàn) ?為了方便討論 ， 我們把串的類型說明改寫成如下形式： define STRINGLEN 81 struct string {int len。 static char ch[STRINGLEN]； } typedef struct string STRING； ?并假定串尾以 “ \0”作結(jié)束標(biāo)志 。 ?由于串賦值和串復(fù)制在高級程序設(shè)計語言中是通過賦值語句來完成的 ， 所以在這里只討論其余四種基本運算 ， 即串比較 、 求串長 、 串聯(lián)接和求子串運算 。 int StrCompare(s,t) /*串的比較 ， 若 st返回值 0， 若 s=t返回值 =0， 否則返回值 0*/ STRING *s,*t。 {int i=0。 while((sch[i]=tch[i])amp。amp。(sch[i]!=’\0’)amp。amp。(tch[i]!=’\0’)) i++。 return sch[i]tch[i]。 } ?該算法的主要時間開銷在于兩串相等時的逐個字符比較 ， 比較次數(shù)為字符串的長度 ， 所以在 最壞情況下 的時間復(fù)雜度為O(min{slen,tlen})；在 最好情況下 是當(dāng)兩串的第一個字符不等時 ， 只需要 O(1)的時間 ， 與問題規(guī)模即串的長度無關(guān) 。 （ 1） ?按假設(shè)的串類型說明 ， 由于有串長域 len故可直接返回其值即可 。 ?算法描述如下： int StrLength(s)/*求串長即串 s中字符的個數(shù) */ STRING *s。 {return slen。} /*直接返回串長域的值即可 */ （ 2） ?在 C語言中是沒有設(shè)串長域的 ， 需要對一維字符數(shù)組中的字符個數(shù)統(tǒng)計結(jié)果 。 ?所以改寫算法為： int StrLength(s) STRING *s。 {int i=0。 /*初始化數(shù)組下標(biāo)和串長域 len*/ slen=0。 while(sch[i]!=’\0’) slen++； return slen； } ?該算法的主要時間開銷在于逐個字符統(tǒng)計串長度的循環(huán) ， 其時間復(fù)雜度為 O(slen)。 ?在實現(xiàn)串的聯(lián)接運算時 ， 要注意兩串 s和 t聯(lián)接后的結(jié)果串 L超過定長的問題 ， 即： slen+tlen=STRINGLEN時結(jié)果串超過定長 STRINGLEN， 此時算法中輸出相應(yīng)提示信息 。 ?其算法描述如下： void StrConcat(l,s,t) STRING *l,*s,*t。 {int i,j。 if(slen+tlenSTRINGLEN) printf(“結(jié)果串 L的長度超過串的定長 STRINGLEN!\n”)。 else {for(i=0。sch[i]!=’\0’。i++) lch[i]=sch[i]。 for(j=0。tch[j]!=’\0’。j++)