【文章內(nèi)容簡(jiǎn)介】 每一道題目的編號(hào)、題目?jī)?nèi)容、選項(xiàng)，然后先由挑戰(zhàn)者開(kāi)始做答，但不顯示結(jié)果。接著由問(wèn)題回答人做答 ? 問(wèn)題回答人和挑戰(zhàn)者都回答完畢后，顯示題目正確答案，然后給出問(wèn)題回答人的得分，每答對(duì) 1題得 100金球，答對(duì)將和剩下的挑戰(zhàn)者繼續(xù)比賽，答錯(cuò)所得金球?qū)⒂墒Ｏ绿魬?zhàn)者刮分。 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列，是數(shù)據(jù)元素為單個(gè)字符的特殊線(xiàn)性表 串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的子串 (Substring)。包含子串的串相應(yīng)地稱(chēng)為主串。 子串的第一個(gè)字符在主串中的位置叫子串的位置。 例如 :串 s1=DavidRuff，它的長(zhǎng)度是 10，串 s2=Ruff的長(zhǎng)度是 4， s2是 s1的子串， s2的位置是 6。 認(rèn)識(shí)串 ——分析串的邏輯結(jié)構(gòu)1. 串的定義2. 串的特征串從數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)是一種特殊的線(xiàn)性表，其特殊性在于串中的數(shù)據(jù)元素是一個(gè)個(gè)的字符 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )串比較： Compare（ s） 求子串： SubString(intindex,intlen)求串的長(zhǎng)度： GetLength()串連接： Concat(s)串定位： IndexOf(s,startpos)串插入： Insert(index,s)串刪除： Delete(index,len)認(rèn)識(shí)串 ——識(shí)別串的基本操作串的基本操作有以下幾種：數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )串的靜態(tài)存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列 可用高級(jí)語(yǔ)言的字符數(shù)組來(lái)實(shí)現(xiàn)。 不同的語(yǔ)言在用數(shù)組存放字符串時(shí)，其處理方式可能有所不同。用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——用順序存儲(chǔ)結(jié)構(gòu)表示串?dāng)?shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )創(chuàng)建順序串就是利用給定的字符數(shù)組、己有的一個(gè)字符串或者給定的長(zhǎng)度，調(diào)用 SeqString類(lèi)的構(gòu)造函數(shù)，在構(gòu)造函數(shù)中執(zhí)行下面的操作：1. 創(chuàng)建順序串用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作步驟操作1 如果 給 定的參數(shù)是字符數(shù) 組 的 話(huà) ，將 創(chuàng) 建一個(gè)一 樣 大的數(shù) 組 ，并將參數(shù)數(shù) 組 中的每個(gè)字符拷 貝 到字符串的存 儲(chǔ) 空 間 里，即新創(chuàng) 建的數(shù) 組 里。2 如果 給 定的參數(shù)是 SeqString類(lèi) 的 實(shí) 例的 話(huà) ，就將參數(shù)串所在存 儲(chǔ) 空 間 的每個(gè)字符拷 貝 到新 創(chuàng) 建字符串的數(shù) 組 空 間 中。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )從主串的 index位置起找長(zhǎng)度為 len的子串，要尋找子串，需要執(zhí)行下面的步驟：： SubString(int index, int len)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作步 驟 操作1 首先確定 index和 len的合法性， index應(yīng) 限定在 0≤index≤ 主串 長(zhǎng) 度 1的范 圍 內(nèi)， len應(yīng) 限定在 0len≤ 主串 長(zhǎng) 度 index的范 圍 內(nèi) ,如果不合法的，將 null返回主 調(diào) 程序。2 創(chuàng) 建一個(gè)新的字符串，并 為 新字符串申 請(qǐng) 的數(shù) 組 空 間 ，空 間 大小 為子串的 長(zhǎng) 度 len一 樣 的大小3 在主串的 index位置開(kāi)始，將主串 len個(gè)字符拷 貝 到子串的數(shù) 組 空 間 中4 將子串返回主 調(diào) 程序數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )將主串中的每個(gè)字符與 s中的每個(gè)字符進(jìn)行比較，需要執(zhí)行下面的步驟：： Compare(SeqString s)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作步 驟 操作1 依次將 較 短字符串中的每個(gè)字符與 較長(zhǎng) 字串的每個(gè)字符比 較 ，當(dāng)被比 較 的兩個(gè)字符不相等 時(shí) ， 終 止比 較2 如果比 較 在中途退出，需 進(jìn) 一步判斷主串與字符串 S在退出比 較時(shí)所比 較 字符的大小，如果主串的字符小，返回 1，否 則 返回 13 如果比 較 是正常退出， 則 需 進(jìn) 一步判斷兩個(gè)字符串的 長(zhǎng) 度是否相等，如相等，返回 0，否 則 如果主串的 長(zhǎng) 度大于 S的 長(zhǎng) 度，返回 1，否則 返回 1。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )串連接就是將主串和字符串 s連接生成一個(gè)新的字符串，要進(jìn)行串連接，需要執(zhí)行下面的步驟： Concat(s)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作步 驟 操作1 申 請(qǐng) 一 塊連續(xù) 的可以存 儲(chǔ) 兩個(gè)字符串的空 間2 將主串中的每個(gè)字符逐個(gè)拷 貝 到 連續(xù) 空 間 的前部分3 將字符串 s逐個(gè)拷 貝 到主串的后面4 將新生成的字符串返回 給 使用者數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )在主串的 startpos位置開(kāi)始，查找子串 s在主串中首次出現(xiàn)的位置。這里使用的是 BruteForce算法，在這個(gè)算法中， s稱(chēng)為模式串。具體需執(zhí)行下面的步驟：５ .串定位： IndexOf(SeqString s, int startpos)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作步 驟 操作1 獲 取從主串 startpos位置開(kāi)始到主串最后一個(gè)字符的子串2 將主串從 startpos開(kāi)始的子串中的每個(gè)字符與 s中的每個(gè)字符比 較，若相等 則繼續(xù) 比 較 后 續(xù) 字符，否 則 從主串中子串的下一個(gè)位置開(kāi)始比 較 。依此 類(lèi) 推3 若存在模式串中的每個(gè)字符依次和主串中一個(gè) 連續(xù) 的字符序列相等， 則 匹配成功，返回模式串 s第一個(gè)字符在主串中的位置，否 則 返回 1。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )在主串的 startpos位置開(kāi)始，查找子串 s在主串中首次出現(xiàn)的位置。這里使用的是 BruteForce算法，在這個(gè)算法中， s稱(chēng)為模式串。具體需執(zhí)行下面的步驟：５ .串定位： IndexOf(SeqString s, int startpos)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作步 驟 操作1 獲 取從主串 startpos位置開(kāi)始到主串最后一個(gè)字符的子串2 將主串從 startpos開(kāi)始的子串中的每個(gè)字符與 s中的每個(gè)字符比 較，若相等 則繼續(xù) 比 較 后 續(xù) 字符，否 則 從主串中子串的下一個(gè)位置開(kāi)始比 較 。依此 類(lèi) 推3 若存在模式串中的每個(gè)字符依次和主串中一個(gè) 連續(xù) 的字符序列相等， 則 匹配成功，返回模式串 s第一個(gè)字符在主串中的位置，否 則 返回 1。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )串插入是指在主串的位置 index處插入一個(gè)串 s。如果位置符合條件，則該操作返回一個(gè)新串，新串的長(zhǎng)度是主串的長(zhǎng)度與串 s的長(zhǎng)度之和，新串的第 1部分是該串的開(kāi)始字符到第 index之間的字符，第 2部分是串 s,第 3部分是主串從 index位置字符到串串的結(jié)束位置處的字符。如果位置不符合條件，則返回一個(gè)空串 。６ .串插入： Insert(int index, SeqString s)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )串刪除是從串的第 index位置起連續(xù)的 len個(gè)字符的子串從主串中刪除掉。如果位置和長(zhǎng)度符合條件，則該操作返回一個(gè)新串，新串的長(zhǎng)度是原串的長(zhǎng)度減去 len，新串的前部分是原串的開(kāi)始到第 index個(gè)位置之間的字符，后部分是原串從第 index+len位置到原串結(jié)束的字符。如果位置和長(zhǎng)度不符合條件，則返回一個(gè)空串 。７ .串刪除： Delete(int index, int len)用順序存儲(chǔ)結(jié)構(gòu)解決串的編程問(wèn)題 ——對(duì)順序串進(jìn)行操作數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)在本章中，你已經(jīng)學(xué)到：字符串是在應(yīng)用程序中使用最頻繁的數(shù)據(jù)類(lèi)型之一。字符串簡(jiǎn)稱(chēng)串，是一種特殊的線(xiàn)性表，其特殊性在于串的數(shù)據(jù)元素是一個(gè)個(gè)的字 ；長(zhǎng)度為零的串稱(chēng)為空串（ EmptyString），它不包含任何字符。僅由一個(gè)或多個(gè)空格組成的串稱(chēng)為空白串（ BlankString）；串中任意個(gè)連續(xù)字符組成的子序列稱(chēng)為該串的子串。包含子串的串相應(yīng)地稱(chēng)為主串。通常將子串在主串中首次出現(xiàn)時(shí)，該子串首字符對(duì)應(yīng)的主串中的序號(hào)定義為子串在主串中的序號(hào)（或位置） ；串提供的基本運(yùn)算有：串比較、求子串 、求串的長(zhǎng)度 、串連接 、串定位 、串插入 、串刪除 ； 因?yàn)榇翘厥獾木€(xiàn)性表，故其存儲(chǔ)結(jié)構(gòu)與線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)類(lèi)似。只不過(guò)由于組成串的結(jié)點(diǎn)是單個(gè)字符，所以存儲(chǔ)時(shí)有一些特殊的技巧 解決數(shù)組的編程問(wèn)題數(shù)據(jù)結(jié)構(gòu) (C語(yǔ)言版 )數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )目標(biāo)在本章中 ,你將學(xué)到 :數(shù)組的定義及表示 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)特殊矩陣的壓縮存儲(chǔ) 稀疏矩陣的壓縮存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )學(xué)習(xí)情境 ——用數(shù)組解決數(shù)學(xué)魔術(shù)游戲編程 [問(wèn)題描述 ]　 　根據(jù)下面的數(shù)學(xué)魔術(shù)原理編寫(xiě)一個(gè)小游戲。有五張卡片，上面寫(xiě)著數(shù)字：卡片 1： 1， 3， 5， 7， 9， 11， 13， 15， 17， 19， 21， 23， 25， 27， 29， 31卡片 2： 2， 3， 6， 7， 10， 11， 14， 15， 18， 19， 22， 23， 26， 27， 30， 31卡片 3： 4， 5， 6， 7， 12， 13， 14， 15， 20， 21， 22， 23， 28， 29， 30， 31卡片 4： 8， 9， 10， 11， 12， 13， 14， 15， 24， 25， 26， 27， 28， 29， 30， 31卡片 5： 16， 17， 18， 19， 20， 21， 22， 23， 24， 25， 26， 27， 28， 29， 30， 31數(shù)據(jù)分布的規(guī)律是：這些卡片上的數(shù)字為 031之間的數(shù)字， 031數(shù)字可以用 5位 2進(jìn)制數(shù)表示，那五張卡片就是各代表一位。每張卡片上的數(shù)字就是代表這個(gè)數(shù)字在表示成二進(jìn)制時(shí)這一位為 1。比如數(shù)字 21表示成 5位的二進(jìn)制是10101，這 5位二進(jìn)制的第 1位（最右邊一位）和第 3位、第 5位都是 “1”，那么就是在第 5號(hào)卡片上都有這個(gè)數(shù)字。注意：卡片號(hào)必須完全猜對(duì) ,如 31也在 1,3,5這三張卡片上 ,除此之外它還在1,2上 ,這樣就不符合條件了。根據(jù)上面的陳述，實(shí)現(xiàn)下面的功能：數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )學(xué)習(xí)情境 ——用線(xiàn)性表解決學(xué)生成績(jī)表的編程[問(wèn)題描述 ](續(xù) )根據(jù)上面的陳述，實(shí)現(xiàn)下面的功能：由計(jì)算機(jī)根據(jù)數(shù)據(jù)分布的規(guī)律自動(dòng)產(chǎn)生 5張卡片上的數(shù)字；? 隨機(jī)的抽取一個(gè)數(shù)字，顯示這個(gè)數(shù)字所在的卡片號(hào)，讓用戶(hù)猜這個(gè)數(shù)字是多少；? 在用戶(hù)提交所猜數(shù)字后，給出正確與否，并亮出所猜卡片上的數(shù)字 。? 程序的界面設(shè)計(jì)圖如圖 。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )數(shù)組是由 n(n≧ 1)個(gè)相同類(lèi)型的數(shù)據(jù)元素組成的有限序列，數(shù)組中的每一個(gè)數(shù)據(jù)通常為數(shù)據(jù)元素 數(shù)組中的元素可以通過(guò)下標(biāo)隨機(jī)訪(fǎng)問(wèn)，其中下標(biāo)的個(gè)數(shù)由組數(shù)的維數(shù)決定。數(shù)組可以看作是線(xiàn)性表的推廣，一維數(shù)組為按順序存儲(chǔ)的線(xiàn)性表，二維數(shù)組為數(shù)據(jù)元素類(lèi)型為一維數(shù)組的線(xiàn)性表，三維數(shù)組為數(shù)據(jù)元素類(lèi)型為二維數(shù)組的線(xiàn)性表，依此類(lèi)推。認(rèn)識(shí)數(shù)組 ——分析數(shù)組的邏輯結(jié)構(gòu)1. 數(shù)組的定義2. 數(shù)組的特點(diǎn)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目確定。一旦定義了一個(gè)數(shù)組，其數(shù)據(jù)元素的數(shù)目不再增減；數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類(lèi)型； 數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組唯一的下標(biāo)值對(duì)應(yīng)；數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素 。數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)數(shù)組 ——識(shí)別數(shù)組的基本操作數(shù)組的基本操作有以下幾種：隨機(jī)存：給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中的值隨機(jī)?。航o定一組下標(biāo)，獲取對(duì)應(yīng)數(shù)據(jù)元素的值除了上面的操作外，在 C語(yǔ)言中，提供的對(duì)數(shù)組常用的操作還有：intLength{get。}：獲取數(shù)組元素的個(gè)數(shù)。 intRank{get。}：獲取數(shù)組的秩（維數(shù)）。staticvoidClear(Arrayarray,intindex,intlength)：將數(shù)組設(shè)置為零、 false或null，具體取決于元素類(lèi)型。 staticvoidCopy(ArraysourceArray,ArraydestinationArray,intlength)：從第一個(gè)元素開(kāi)始復(fù)制數(shù)組中的一系列元素到另一數(shù)組中。voidCopyTo(Arrayarray,intindex)：將一維數(shù)組的所有元素復(fù)制到指定的一維數(shù)組 Array中。IntGetLength(intdimension)：獲取數(shù)組指定維中的元素?cái)?shù)staticvoidSort(Arrayarray)：對(duì)整個(gè)一維數(shù)組中的元素進(jìn)行排序數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu) (C描述 )對(duì)于一維數(shù)組，可根據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址，也可根據(jù)下標(biāo)來(lái)訪(fǎng)問(wèn)一維數(shù)組中的元素 對(duì)于多維數(shù)組，需要把多維的下標(biāo)表達(dá)式轉(zhuǎn)換成一維的下標(biāo)表達(dá)式。這產(chǎn)生了兩種存儲(chǔ)方式：一種是以行序?yàn)橹餍颍ㄏ刃泻罅校┑捻樞虼娣?，另一種是以列序?yàn)橹餍颍ㄏ攘泻笮校┑捻樞虼娣?。二維數(shù)組的兩種存放方式示意圖如下所示 :認(rèn)識(shí)數(shù)組 ——用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)數(shù)組