工學(xué)第三章串ppt課件(已修改)
2024-11-15 20:42 本頁面
【正文】 第 3章 特殊線性表 —棧、隊列和串 本章的基本內(nèi)容是： ⑴棧和隊列的定義及操作特性； ⑵棧和隊列的兩種存儲方法和基本運算的實現(xiàn)； ⑶串的基本概念和操作； ⑷串的常用存儲方法； ⑸串的模式匹配算法。 第 3章 特殊線性表 ——串 串的邏輯結(jié)構(gòu) 1. 串的定義 串是零個或多個字符組成的有限序列 。 空格串 ：只包含空格的串。 串的長度 ：串中所包含的字符個數(shù)。 空串 ：長度為 0的串。 空串記作 “ ” ； 非空串通常記作 ： S=“s1 s2 …… sn” 其中： S是串名；雙引號是定界符 ；雙引號引起來的部分是串 值 。 si（ 1≤ i≤ n） 是一個任意字符 。 第 3章 特殊線性表 ——串 子串： 串中任意個連續(xù)的字符組成的子序列。 主串：包 含子串的串 。 子串在主串中的位置：子串的第一個字符在主串中的序號 。 S1=ab12cd S2=“ab12 S3= S4=“φφφ ” 串的長度？ 第 3章 特殊線性表 ——串 理解串的定義有以下要點： (1)si(1≤i≤n) 是一個抽象符號 ， 代表任意字符 。 (2)si在串中出現(xiàn)的序號 i稱為該字符在串中的位置 (3)有限性：組成串的字符個數(shù)是有限的 。 (4)順序性：相鄰字符之間具有前驅(qū)后繼關(guān)系 。 (5)元素的特殊性：數(shù)據(jù)元素是字符 。 注意不是符號 ， 串的數(shù)據(jù)元素均取自某個字符集 。 第 3章 特殊線性表 ——串 串的數(shù)據(jù)對象約束為某個字符集。 微機(jī)上常用的字符集是標(biāo)準(zhǔn) ASCII碼，由 7 位二進(jìn)制數(shù)表示一個字符，總共可以表示 128 個字符。擴(kuò)展 ASCII碼由 8 位二進(jìn)制數(shù)表示一個字符，總共可以表示 256 個字符，足夠表示英語和一些特殊符號，但無法滿足國際需要。Unicode由 16 位二進(jìn)制數(shù)表示一個字符，總共可以表示 216個字符，即 6萬 5千多個字符，能夠表示世界上所有語言的所有字符，包括亞洲國家的表意字符。為了保持兼容性， Unicode字符集中的前 256個字符與擴(kuò)展 ASCII碼完全相同。 第 3章 特殊線性表 ——串 2. 串的比較 串的比較是通過組成串的 字符 之間的比較來進(jìn)行的 。 給定兩個串： X=x1x2… xn Y=y1y2… ym 則當(dāng) n=m且 x1=y1， … ， xn=ym時 ， 稱 X=Y； 當(dāng)下列條件之一成立時 ， 稱 X＜ Y： ⑴ n＜ m， 且 xi=yi（ i=1， 2， … ， n） ； ⑵ 存在某個 k≤ min(m， n)， 使得 xi=yi（ i=1， 2， … ，k1） ， xk＜ yk。 在計算機(jī)中 ， 字符編碼通常用 ASCII碼 ， 字符的比較就是ASCII碼之間的比較 。 3. 串的抽象數(shù)據(jù)類型定義 串的基本操作通常以 “ 串的整體 ” 作為操作對象。 第 3章 特殊線性表 ——串 ⑴ StrLength (s)： 求串 s的長度 。 ⑵ StrAssign (s1， s2)： 串賦值 ， 將 s2的串值賦值給串 s1。 ⑶ StrConcat (s1， s2， s)： 串的連接 ， 將串 s2放在串 s1的后面連接成一個新串 s。 ⑷ SubStr (s， i， len)： 求子串 ， 返回從串 s的第 i個字符開始取長為 len 的子串 。 第 3章 特殊線性表 ——串 ⑸ StrCmp (s1， s2)： 串比較 ， 若 s1=s2， 返回 0；若s1s2, 返回 1；若 s1s2, 返回 1。 ⑹ StrIndex (s， t)： 子串定位 ， 返回子串 t在主串 s中首次出現(xiàn)的位置 。 若 t不是 s的子串 ， 則返回 0。 ⑺ StrInsert (s， i， t)： 串插入 ， 將串 t插入到串 s的第i個位置 。 ⑻ StrDelete (s， i， len)： 串刪除 ， 刪除串 s中從第 i個字符開始連續(xù) len個字符 。 ⑼ StrRep (s， t， r)： 串替換 ， 在串 s中用串 r替換所有與串 t相等的子串 。 第 3章 特殊線性表 ——串 SubStr (s， i， len)求子串 算法示例 i n f i n i t y i = 3, len = 3 f i n i n f i n i t y i = 6, len = 4 i t y 超出 從串 s中第 i 個字符起連續(xù)取 長為 len 個字符 ,形成子串并返回。 第 3章 特殊線性表 ——串 串的存儲結(jié)構(gòu) 1. 串的順序存儲結(jié)構(gòu) 定義 ： 串的順序存儲結(jié)構(gòu)是
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1