本章介紹了 串 的 邏輯結構 存儲結構 及 串上的基本運算 由於在高級語言中已經提供了較全善的串處理功能因此本章的 重點 是掌握在串上實現的模式匹配算法同時這也是本章的 難點 但是從全書來講這屬於較簡單的一章內容
串及其運算( 領會 )(這些內容比較容易理解不用死記)
串 就是 字符串 是一種 特殊 的 線性表 它的每個結點僅由 一個字符 組成
空串 是指 長度為零 的串也就是串中不包含任何字符(結點)
空白串 指串中 包含 一個或多個 空格 字符的串不同與空串它的結點就是一個空格字符
在一個串中任意個連續字符組成的子序列稱為該串的 子串 包含子串的串就稱為 主串 子串在主串中的序號就是指子串在主串中首次出現的位置如A=I love you B=love則B在A中的序號為注意空格也是字符
空串 是 任意串 的 子串 任意串 是他 自身的 子串
串分為兩種 串常量 和 串變量 串常量在程序中不能改變串變量則可以
關於串的基本運算基本上在C語言中已經學過主要有
求串長strlen(char *s)
串復制strcpy(char *tochar *from)
串聯接strcat(char *tochar *from)
串比較charcmp(char *schar *s)
和字符定位strchr(char *s char c)等
這些基本運算通過練習來掌握
串的存儲結構( 簡單應用 )
串 是 特殊的線性表 (結點是字符)所以串的存儲結構與線性表的存儲結構類似
串的順序存儲結構簡稱為 順序串 順序串又可按存儲分配的不同分為 靜態存儲分配的順序串 和 動態存儲分配的順序串
靜態 的意思可簡單地理解為一個確定的存儲空間它的長度是不可變的如直接使用定長的字符數組來定義一個串它的優點是涉及串長的操作速度快因為它的最大長度是不變的
動態存儲分配 就是在定義串時不分配存儲空間直到需要使用時按所需串的長度分配存儲單元給它並且在運行中還可以根據需要變化串的長度這就是動態分配不過這樣的串仍是順序存儲的也就是說指針指向串的首地址後面的結點是連續存儲的
串的鏈式存儲 就是用 單鏈表 的方式存儲串值串的這種鏈式存儲結構簡稱為 鏈串 鏈串與單鏈表的差異只是它的結點數據域為單個字符這種存儲結構方便於串的插入和刪除操作但是空間利用率不高因為存放每一個字符要搭配一個指向下一字符的地址而地址所占空間是比較大的為了解決這種存儲密度過低的狀況可以讓一個結點存儲多個字符事實上這是順序串和鏈串的綜合(折衷)
本章的 重點 和 難點 就是串運算的實現特別是順序串上子串定位的運算
子串定位運算 又稱串的 模式匹配 或 串匹配 就是在主串中查找出子串出現的位置 這在應用中非常廣泛比如文本編輯中的查找和替換用到的就是子串定位運算的算法
在 串匹配 中將 主串 稱為 目標(串) 子串 稱為 模式(串 )我們這樣想象子串就如同一個模板(樣本)用它在目標上對比從頭往後比較凡是遇到一模一樣的那麼一段就算找到一個位置了(我們就說 從這個位置開始的 匹配成功 )用很專業的很酷的話說就是 模式在目標中出現 (我想起了警匪片裡的對話)如果這個模板對應的目標串中有不一樣的字符出現那麼這個位置就 匹配失敗
當我們用這個模子依次從目標的頭部往後移移動到的位置就叫 位移 如果每次向右移動格那麼每次的位移就加上
每次移動後要看看模板裡的字符和目標中相應的字符是否相等如果都相同這次位移就叫 有效位移 (其實就是從這個位置開始的 匹配成功 )
另外有一個 合法位移 和 不合法位移 的概念就是說移動一個位置後如果模板的最後一個字符還沒有超出目標串中最後一個字符時這個位移就是合法位移如果超出了那麼就沒有比較的意義了這時就是不合法位移
這是比較容易理解的 串匹配問題 就是找出給定模式串P在給定目標串T中 首次出現的 有效位移 或者是全部 有效位移
具體的串匹配算法也不是很難理解就是用兩個循環外循環用於進行模式的位移內循環進行模板內每個字符的比較(判斷是否有效位移)關於串匹配的時間復雜度在最壞的情況下就是目標串和模式串分別是 a ^n b 和 a ^m b 的形式就是說每一次合法位移後在內循環中都要比較m個字符才知道是不是有效位移(前面的字符都是一樣的)所以最壞的情況下時間復雜度是O((nm+)m)假如m與n同階的話則它是O(n^)
鏈串上的子串定位運算的不同之處就是位移是結點地址而不是整數理解一下算法即可
真正的應用主要還是要掌握 串的基本算法 並用它們構造出可以 解決具體問題的 簡單算法
第四章 串 復習要點
本章復習要點是
串是一種特殊的線性表它的結點僅由一個字符組成
空串與空白串的區別空串是長度為零的串空白串是指由一個或多個空格組成的串
串運算的實現中子串定位運算又稱串的模式匹配或串匹配
串匹配中一般將主串稱為目標(串)子串稱為模式(串)
本章可能出的題型多半為選擇填空等
From:http://tw.wingwit.com/Article/program/sjjg/201311/23674.html
