算法與數據結構第2章常用數據結構ppt(編輯修改稿)

　

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