c風格字符串操作與算法庫簡單運用

1、C風格字符串操作與算法庫簡單運用計44班 黃斐 劉弘編輯課件字符串的本質(zhì)什么是字符串？指針數(shù)組？char strXX;不僅僅如此。字符串 = 指針 + 內(nèi)容。常見的字符串有以下幾種形式:char strXX; 字符數(shù)組char* pstr=XX;字符指針，并指向某內(nèi)容XXXX 常量字符串編輯課件字符串的本質(zhì)指針內(nèi)容字符數(shù)組常量。數(shù)組名，即str。變量。字符數(shù)組中所存內(nèi)容。字符指針+內(nèi)容變量。指針變量名，即pstr。可以是變量或者常量。指針所指內(nèi)容。常量字符串常量。隱式存在，即整個“XX”本身。常量。在一塊只讀內(nèi)存上，即XX的內(nèi)容。編輯課件字符串的本質(zhì)指針指針是用來表示字符串的。指針永遠指向字符

2、串第一個字符的位置。我們操作、使用字符串一般都用指針來表示。內(nèi)容字符串的內(nèi)容是一塊連續(xù)內(nèi)存上的字符型數(shù)據(jù)。如何決定長度？內(nèi)容最后會加一個0,即0來標識字符串的結(jié)束。編輯課件熱身訓練編輯課件熱身訓練編輯課件熱身訓練如果還有疑問請參考，徐老師給出的課件W07討論(4)數(shù)組指針函數(shù)編輯課件字符串的參數(shù)傳遞字符串雖然有以上三種表示方法，三種方式均可以作為參數(shù)傳入函數(shù)。但函數(shù)中傳入的字符串都會變成字符指針+內(nèi)容的形式。編輯課件字符串的參數(shù)傳遞因為是指針+內(nèi)容的形式，所以可以給指針賦值。編輯課件字符串的參數(shù)傳遞如果函數(shù)內(nèi)要修改字符串內(nèi)容，編譯能夠通過。但會根據(jù)內(nèi)容是否為常量，在運行時報錯。編輯課件字符串的

3、參數(shù)傳遞傳入類型參數(shù)類型字符數(shù)組變量指針+變量內(nèi)容指針+內(nèi)容變量指針+內(nèi)容（可不可變同前）字符串常量變量指針+常量內(nèi)容編輯課件strlen原理設計一個函數(shù)，傳入一個字符串，求該字符串長度。前面已經(jīng)介紹過，0是標志著字符串結(jié)束的標志，所以據(jù)此可以設計函數(shù)。我們所用的strlen庫函數(shù)就是這樣實現(xiàn)的。所以每次統(tǒng)計長度都需要掃描整個字符串，每次調(diào)用的復雜度都是O(n)的。編輯課件strcpy原理設計一個函數(shù)，傳入兩個字符串，將后一個字符串復制到前一個字符串。注意復制時,一定要連第二個字符串的0也復制進去。注意do while結(jié)構(gòu)和i+。a能接受的類型只有字符數(shù)組或指向變量內(nèi)容的字符指針。b可以是任意

4、字符串形式。編輯課件交換兩個字符串在程序中如何交換兩個字符串。使用輔助數(shù)組，復制數(shù)組內(nèi)容進行交換。一次交換需要3次strcpy。操作次數(shù)為2*len(a)+len(b)。編輯課件交換兩個字符串交換指針？我們知道數(shù)組名是不能交換的，能交換的只有第二種指針+內(nèi)容類型。一次交換只需要3次賦值。操作次數(shù)為3。編輯課件擴展：對字符串進行排序使用指針交換，而不是內(nèi)容交換。編輯課件擴展：對字符串進行排序不用復制內(nèi)容，速度更快。最靈活的使用方式：指向字符數(shù)組的指針。這樣不僅內(nèi)容可以修改，指針也可以修改。注意：指向同一內(nèi)容的指針，只要修改其中一個，另一個也會改變。編輯課件說完了字符串的指針操作，讓我們看看數(shù)組i

5、nt a=1,2,3,4,5;cout a+1 endl;cout *(a+1) endl;cout &a1 endl;這三句話的結(jié)果分別是什么？scanf(”%d”, &a1);scanf(”%d”, a + 1);這兩句話一樣嗎？編輯課件問題：怎樣讓我寫的算法可以應用于不同的數(shù)組？比如我想寫一個排序的函數(shù)，讓它既能給a數(shù)組排序，又能給b數(shù)組排序這個函數(shù)的功能還是不夠強，我想讓我的排序能給a數(shù)組中任意一段區(qū)間排序。甚至，我想講我的排序函數(shù)應用于不同的類型，既能是int類型，又能是char類型如何實現(xiàn)？編輯課件實現(xiàn)方法前兩點可以用地址來實現(xiàn)，用序列起始點和結(jié)束點的地址來代替具體的變量，第三點則

6、可以引入比較函數(shù)或重載操作符來實現(xiàn)。如果我要給a0到an(不包括an)的數(shù)排序，那么a0的地址為a，an的地址為a + n。比較函數(shù)為 T cmp( const T x, const T y);那么我只要調(diào)用sort(a, a + n, cmp); 即可。編輯課件我要如何具體實現(xiàn)這樣的函數(shù)呢？由于可能涉及到類、模板等內(nèi)容，暫時先不講具體實現(xiàn)。不過c+的庫函數(shù)已經(jīng)幫我們實現(xiàn)了這樣想法。除了sort還有其他幾十個函數(shù)，都被放在algorithm庫中。調(diào)用該庫需加入頭文件 #include 這些函數(shù)支持多種數(shù)據(jù)類型，并且除了swap等對單個元素進行操作的函數(shù)外，它們一般與sort類似，在調(diào)用時都是訪

7、問地址。編輯課件algorithm庫有哪些函數(shù)呢？sort, lower_bound, upper_bound, make_heap, push_heap, 函數(shù)太多(見附錄)，大家課后自己研究。先來看一個簡單的演示程序。編輯課件到底有什么具體應用呢？讓我們先看一道題目吧。編輯課件跳蚤市場在跳蚤市場人們能夠買到便宜貨。有些人想出售貨物，有些人則想購買貨物。我們考慮一個簡單的問題，對于同一種貨物，假設它們的質(zhì)量相同，那么人們一定會以更低的價格來購買?，F(xiàn)在有N個人先后來到市場買賣同一種貨物，每個人或者要賣出一件貨物，或者要買入幾件貨物。每個賣貨的人會把要賣的貨物寄存在市場中，只有比他后到的買家才能

8、購買他的貨物。如果貨源不足，買家會放棄購買，而不是等待下一個賣家或是只購買一部分。編輯課件跳蚤市場現(xiàn)在按順序給你這N個人以及他們的目的，請你輸出每一個買家的購買結(jié)果。輸入格式第一行為N。第二到N+1行每行兩個整數(shù)x和y。若x為0，表示買家，則y表示他想買入y件貨物；若x為1，表示賣家，則y表示他想以y元的價格出售貨物。編輯課件跳蚤市場輸出格式按順序輸出每個買家的結(jié)果，若交易失敗，則只輸出一行一個字符串“Fail.”表示購買失敗，否則輸出y行每行一個整數(shù)，從小到大以此為他買入的每件貨物的價格。數(shù)據(jù)范圍50%的數(shù)據(jù)N10,000；100%的數(shù)據(jù)N1,000,000。編輯課件跳蚤市場樣例輸入71 1

9、30 21 121 150 11 110 2樣例輸出Fail.121113編輯課件解題思路N10,000的算法：當買家要進行購買時，對當前所有要賣出的貨物從小到大進行排序。或者每當賣家出售貨物時對出售的序列進行插入排序。編寫起來較容易。N1,000,000的算法：用一個小根堆維護當前的所有要出售物品的價格，每次從堆頂彈出元素給買家。編寫起來較復雜。編輯課件怎樣既讓程序既快又簡單？調(diào)用algorithm庫！關(guān)于堆的函數(shù)：建堆：make_heap() 插入元素：push_heap()彈出堆頂元素：pop_heap()有了這三樣 ： 數(shù)組=堆編輯課件#include#includeusing nam

10、espace std;int a1000010; /用一個數(shù)組存儲堆中元素bool comp(const int x, const int y)return x y;/比較函數(shù)，用于規(guī)定堆為小根堆，make_heap默認為大根堆編輯課件int main()int n, m = 0;cin n;while(n-)int x, y;cin x y;if (x) am+ = y; /將y置于堆尾用于插入push_heap(a, a + m, comp); else if (m = y) while (y-) pop_heap(a, a + m, comp); cout a-m endl; /堆頂元素

11、彈出至尾部 else cout Fail.n;return 0;編輯課件小結(jié)本題通過巧妙地使用algorithm庫中的幾個函數(shù)將一道以編寫與調(diào)試為主的題目變成了一道以設計算法為主的題目。不過癮？再來一道。編輯課件NOIP2007 統(tǒng)計數(shù)字某次科研調(diào)查時得到了n個自然數(shù)，每個數(shù)均不超過1500000000（1.5*109）。已知不相同的數(shù)不超過10000個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計結(jié)果。輸入文件包含n+1行： 第1行是整數(shù)n，表示自然數(shù)的個數(shù)。 第2n+1行每行一個自然數(shù)。 輸出文件包含m行（m為n個自然數(shù)中不相同數(shù)的個數(shù)），按照自然數(shù)從小到大的順

12、序輸出。每行輸出兩個整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個空格隔開。編輯課件NOIP2007 統(tǒng)計數(shù)字count.incount.out82424510021002 34 25 1100 2數(shù)據(jù)范圍:40%的數(shù)據(jù)滿足：1=n=1,00080%的數(shù)據(jù)滿足：1=n=50,000100%的數(shù)據(jù)滿足：1=n=200,000，每個數(shù)均不超過1 500 000 000（1.5*109）編輯課件解題思路枚舉每個不同的數(shù)，統(tǒng)計出現(xiàn)次數(shù)？排序，然后讓后從小到大找過來？看看用算法庫如何方便地實現(xiàn)。二分查找？lower_bound 二分查找，返回第一個大于等于某個數(shù)的地址upper_bound 二分查找，返

13、回第一個大于某個數(shù)的地址如何去重？unique_copy 將一個有序序列去重后存入另一個序列編輯課件#include#include#define N 200010#define rep(i,n) for(int i=0;i(n);i+)using namespace std;int aN, bN;int main()int n; scanf(%d, &n);rep(i,n) scanf(%d, a + i);sort(a, a + n);int m = unique_copy(a , a + n, b) - b;/將a0到an-1去重后放入b數(shù)組rep(i,m) printf(“%d %dn”, bi, ？);return 0;？處的答案為： upper_bound(a , a + n, bi) - lower_bound(a , a + n, bi)(白色字體)編輯課件總結(jié)算法庫并不是我們想象中的萬能的，它只能解決一些簡單基本的操作。我們在運用算法庫的時候，要靈活運用，根據(jù)我們要解決的問題選擇合適的函數(shù)，切不可刻意去套用。算法庫確實能為我們的編程帶來極大的方便，這給了我們更多思考算法的時間，減小了用程序具體實現(xiàn)的