【正文】 算機中表示的值不同；且這個集合是有窮集合 ，是數(shù)學意義上的無窮集合的一個子集 ） ， 在這個集合上可以進行的操作有加 、 減 、 乘 、 整除和求模等算術(shù)運算以及等于 、 不等于 、 大于 、 小于 、 大于等于和小于等于等關(guān)系運算 。如整型 、 實型 、 布爾型和字符型等 ， 其值不可再分解 。 數(shù)據(jù)類型的特征 ?類型決定了變量或表達式所有可能取值的全體成員集合 。 ?一種類型的值及其在該類型上規(guī)定的基本操作的性質(zhì)可由一組公理來闡明 。 ?數(shù)據(jù)結(jié)構(gòu)包含以下三個方面的內(nèi)容： ?數(shù)據(jù)的邏輯結(jié)構(gòu) ?數(shù)據(jù)的存儲結(jié)構(gòu) ? 數(shù)據(jù)的運算及實現(xiàn) 數(shù)據(jù)的邏輯結(jié)構(gòu) ?數(shù)據(jù)的 邏輯結(jié)構(gòu) 是指數(shù)據(jù)元素之間的邏輯關(guān)系 。 ?主要的存儲方式有 順序存儲 和 鏈式存儲 兩種 ， 此外還有 索引存儲 和 散列存儲 等其它方式 。 數(shù)據(jù)的運算及實現(xiàn) ?數(shù)據(jù)的 運算及實現(xiàn) 。 ?運算的實現(xiàn)依賴于所選取的存儲結(jié)構(gòu) ， 也依賴于所選用的程序設(shè)計語言 。 非線性結(jié)構(gòu) ——樹型結(jié)構(gòu) ?在非線性結(jié)構(gòu)中 ， D中數(shù)據(jù)元素之間不存在一對一的次序關(guān)系 。 ?在圖型結(jié)構(gòu)中 ， D中數(shù)據(jù)元素之間的關(guān)系是多對多的網(wǎng)狀關(guān)系 。 ?集合是數(shù)據(jù)元素關(guān)系極為松散的一種結(jié)構(gòu) 。 ?主要用于線性數(shù)據(jù)結(jié)構(gòu)的存儲 ， 對于非線性結(jié)構(gòu)進行線性化處理后也可實現(xiàn)順序存儲 。 其他的存儲表示方式 ?存儲表示方式還有 索引存儲 方式和 散列存儲 方式 ，通常是為了檢索的方便所采用的存儲表示方法 。 ?各種數(shù)據(jù)結(jié)構(gòu) ， 分別提供了不同類型的數(shù)據(jù)在作為計算機程序數(shù)據(jù)時的組織 、 管理 、 存儲 、 運算和處理的方法和技術(shù) 。 數(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ì)的細節(jié) 。 抽象數(shù)據(jù)類型（續(xù)） ?抽象數(shù)據(jù)類型 （ Abstract Data Type簡記為 ADT） 是指一個數(shù)據(jù)模型以及定義在該數(shù)據(jù)模型上的一組操作 。 抽象數(shù)據(jù)類型的定義 ?抽象數(shù)據(jù)類型的定義 ， 僅取決于它的一組邏輯特性 ， 而與它在計算機內(nèi)部如何表示和實現(xiàn)無關(guān) 。 抽象數(shù)據(jù)類型（續(xù)） ?抽象數(shù)據(jù)類型是算法設(shè)計和程序設(shè)計中的重要概念 ， 這個概念明確地把數(shù)據(jù)結(jié)構(gòu)與作用在該結(jié)構(gòu)上的運算緊密地聯(lián)系起來 。 抽象數(shù)據(jù)類型（續(xù)） ?抽象數(shù)據(jù)類型的設(shè)計和實現(xiàn)不可能象基本數(shù)據(jù)類型那樣可以規(guī)范 、 內(nèi)置和一勞永逸 。 ?在程序中引入數(shù)組的充分理由是： ?為了求解問題有引入數(shù)組的必要性 ， 如需要記住一組值等； ?基于問題求解算法的效率考慮 ， 引入數(shù)組可使算法效率更高； ?基于概念上或運算處理上的自然 、 簡單和方便性方面考慮需要引入數(shù)組 。 ?數(shù)組元素的下標具有上下界約束且下標有序 ， 下標與數(shù)組元素的對應(yīng)關(guān)系使得數(shù)組元素可以隨機訪問 。通常只有賦值和讀取數(shù)組元素兩種操作： ?賦值：給定一組下標 ， 把指定值 （ 如初始值 、 修改值 、運算值等 ） 存入相應(yīng)的數(shù)組元素中； ?讀?。航o定一組下標 ， 讀取相應(yīng)的數(shù)組元素 （ 通常是為了使用其值或打印輸出等目的 ） 。 i++) {對 A的第 i個元素執(zhí)行某個指定的操作 } ?當數(shù)組的下標為一個時 ， 稱之為 一維數(shù)組 ?當數(shù)組的下標為兩個或兩個以上時 ， 稱之為 二維數(shù)組 或 多維數(shù)組 。 ?對于二維數(shù)組和多維數(shù)組 。 ?若選定一種約定 ， 則每個數(shù)組元素相對于存儲區(qū)域起始地址的位置也就隨之確定了 。 ?若以 行為主序 優(yōu)先存儲 ， 考慮數(shù)組元素 aij的地址計算公式 。 但是在有些情況下 ， 如特殊矩陣和稀疏矩陣 ， 采用二維數(shù)組的存儲方式會浪費大量存儲空間 。 ?對角矩陣的 特點 是除了主對角線上的元素外其余元素都為零 。 ?對三對角矩陣的壓縮存儲方法是 ， 按行為主序優(yōu)先存儲方法把非零區(qū)的三對角元素依次順序存儲到一片連續(xù)的存儲空間中 。 ?其映像關(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個存儲分配的元素 。 ?由于對稱矩陣中元素關(guān)于主對角線對稱 ， 因此只需要存儲其上三角中的元素或下三角中的元素 ， 使對稱元素共享同一存儲空間 。 ?本節(jié)著重討論串的存儲結(jié)構(gòu)以及主要運算的實現(xiàn) ，如順序存儲分配的三種方式 、 堆式存儲分配策略以及在 “ 向量存儲 ， 定長結(jié)構(gòu) ” 基礎(chǔ)上幾種串運算的實現(xiàn)算法 ， 并簡要介紹漢字串的概念 。 ?要注意空串與空格串的區(qū)別 ， 空格串中有一個或多個空格字符 ， 串的長度大于零 。 ?串結(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 }。 把串變量 t的值復(fù)制到串變量 s中 。 返回值為串 s中字符的個數(shù) （ 串長 ） 。 ?SubString(t,s,i,len)：求子串 。 ?下面四種其它的串運算都有著重要的應(yīng)用： ?StrInsert(s,i,t)： 串插入 。 運算的結(jié)果是從 s串中刪去自第 i個字符起的 len 個字符后得到的新串 。 其中要求子串 t為非空串 。 ?在高級程序設(shè)計語言中 ， 大都為字符串設(shè)立了專門的數(shù)據(jù)類型 。 ?如串 s=“data structure ”的緊縮存儲如下： ?其中字符串長度 18存儲在開始處 ， “ ” 表示空格字符 ，共占用五個存儲單元 。 串的長度不顯式存儲 ，由串中字符占存儲單元的數(shù)目來隱式確定 。 ?每個地址對應(yīng)一個字節(jié) ， 一個字節(jié)正好存放一個字符 。 定長順序存儲結(jié)構(gòu)的運算實現(xiàn) ?為了方便討論 ， 我們把串的類型說明改寫成如下形式： define STRINGLEN 81 struct string {int len。 {int i=0。amp。 （ 1） ?按假設(shè)的串類型說明 ， 由于有串長域 len故可直接返回其值即可 。 ?所以改寫算法為： int StrLength(s) STRING *s。 ?在實現(xiàn)串的聯(lián)接運算時 ， 要注意兩串 s和 t聯(lián)接后的結(jié)果串 L超過定長的問題 ， 即： slen+tlen=STRINGLEN時結(jié)果串超過定長 STRINGLEN， 此時算法中輸出相應(yīng)提示信息 。 else {for(i=0。tch[j]!=’\0’。} } （續(xù)） ?該算法的時間開銷主要在于復(fù)制兩個串中字符到結(jié)果串中 ， 其復(fù)制字符個數(shù)為兩個串的長度之和 ， 故其時間復(fù)雜度為 O(slen+tlen)。 ?當 i0或 i≥s len時 ， 子串開始位置非法； ?當 len0或 lensleni時 ， 子串的長度非法 。 {int j。jlen。 串 串的基本概念 串的定長順序存儲及運算實現(xiàn) 模式匹配 串的堆式動態(tài)存儲及運算實現(xiàn) 漢字串 模式匹配 ?子串的定位操作通常稱作 模式匹配 ， 子串 t稱作 模式 ，在主串 s中確定 t的位置的過程稱作 匹配過程 。 {int n,m,i,bool。 /*求模式串 t的長度于 m*/ i=0。(bool0)) {SubString(l,s,i,m)。 else return 1。 ?在許多應(yīng)用場合如文本編輯等 ， 匹配效率也較高 。 ?該算法可以在 O(n+m)的時間數(shù)量級上完成串的模式匹配運算 。 同理 ， 在第一趟匹配中出現(xiàn)字符不等時 ， 僅需將模式串向右滑動兩個字符位置進行 i=j=0時的字符比較 。 ?模式 t中的每一個 tj都對應(yīng)一個 k值 ， 這個 k值表示當在 tj處失配時模式 t應(yīng)向右滑動的字符數(shù) ， 它僅依賴于模式 t而與主串 s無關(guān) 。 if((tlen==0)||(slentlen)) return 1。amp。 if(jtlen) return itlen。 j=1。 next[i]=j。 ?需要說明的是 ， 算法 index的時間復(fù)雜度雖然是O(m*n)， 但在一般情況下其實際執(zhí)行時間近似于O(m+n)， 所以至今仍被采用 。 ?采用定長順序存儲在多數(shù)串的串長較小時其空間利用率低 ， 且使某些運算如串聯(lián)接和串置換等受到限制或產(chǎn)生錯誤結(jié)果 。 ?設(shè)整形變量 free指示該空間中尚未分配區(qū)間的開始地址（ 初始值為 1） 。 ?所有的串名存儲映像構(gòu)成了一張為系統(tǒng)中所有串名和串值之間建立一一對應(yīng)關(guān)系的映像表 （ 或符號表 ） 。 /*定義串類型標識符為 STRING*/ char store[MAXSIZE]。 ?其算法描述如下： void StrAssign(s,chars) STRING *s。 /*為統(tǒng)計字符串常量中的字符個數(shù)初始化 */ while(chars[i]!=’\0’) /*統(tǒng)計 chars中字符個數(shù) */ i++。i++) /*逐字符賦值 */ store[free+i]=chars[i]。 /*修改堆中的指示器變量 free的值 */ } } 堆式動態(tài)存儲的 串復(fù)制 算法 ? 該運算把堆中的串 t復(fù)制到 s中去 。itlength。 free=free+tlength。 {STRING *p。 /*修改 l的存儲映像中的串長 */ } ? 注意 ， 為什么算法中沒有修改 l的開始位置 ？ 又為什么未見修改堆中指示器變量 free的語句 ？ 這是因為第一個串復(fù)制語句已使 l的開始位置到位 ， 而第二個串復(fù)制語句已使 free的值指向尚未分配區(qū)的開始位置 ， 故只需修改串長即可 。 {if((i0)||(len0)||(lenslengthi)) printf(“所給子串的位置或長度有錯誤 \n”)。 ?無論是西文還是漢字 ， 計算機系統(tǒng)均應(yīng)具有輸入 、 加工處理和輸出的功能 ， 并能在不同的系統(tǒng)之間進行信息交換 。 ?當向計算機輸入西文信息時 ， 只要在鍵盤上按不同的鍵就可產(chǎn)生不同的輸入代碼 ， 這些輸入碼集可以簡單地等同于機內(nèi)碼集 。 電報碼是以 ASCII字符集的子集 C={0,1,2… 9}為基集 ， 由四個 0~9的數(shù)字字符構(gòu)成一個漢字機內(nèi)碼 。 ?國標交換碼規(guī)定由兩個字節(jié)構(gòu)成一個漢字交換碼 ， 每個字節(jié)都用七位 ， 最高位均為 0。 ?區(qū)位碼中 ， 每個漢字對應(yīng)四個十進制數(shù)字 ， 前兩位是區(qū)號共 94個區(qū) ， 每區(qū) 94位 。 ?目前應(yīng)用較為廣泛的是采用國標碼和區(qū)位碼進行代碼標識 ，形成兩字節(jié)漢字機內(nèi)碼 。 但是這種機內(nèi)碼的編輯性較差 ， 占用字節(jié)量大；一般用在要求較高的軟件系統(tǒng)中或傳輸過程中作為系統(tǒng)的輔助漢字機內(nèi)碼