c风格字符串操作与算法库简单运用

1、C风格字符串操作与算法库简单运用,计44班 黄斐 刘弘,字符串的本质,什么是字符串？ 指针数组？char strXX; 不仅仅如此。字符串 = 指针 + 内容。 常见的字符串有以下几种形式:char strXX; 字符数组char* pstr=XX;字符指针，并指向某内容XXXX 常量字符串,字符串的本质,字符串的本质,指针 指针是用来表示字符串的。指针永远指向字符串第一个字符的位置。我们操作、使用字符串一般都用指针来表示。 内容 字符串的内容是一块连续内存上的字符型数据。 如何决定长度？ 内容最后会加一个0,即0来标识字符串的结束。,热身训练,热身训练,热身训练,如果还有疑问请参考，徐老师给

2、出的课件 W07讨论(4)数组指针函数,字符串的参数传递,字符串虽然有以上三种表示方法，三种方式均可以作为参数传入函数。 但函数中传入的字符串都会变成字符指针+内容的形式。,字符串的参数传递,因为是指针+内容的形式，所以可以给指针赋值。,字符串的参数传递,如果函数内要修改字符串内容，编译能够通过。 但会根据内容是否为常量，在运行时报错。,字符串的参数传递,strlen原理,设计一个函数，传入一个字符串，求该字符串长度。 前面已经介绍过，0是标志着字符串结束的标志，所以据此可以设计函数。,我们所用的strlen库函数就是这样实现的。 所以每次统计长度都需要扫描整个字符串，每次调用的复杂度都是O(

3、n)的。,strcpy原理,设计一个函数，传入两个字符串，将后一个字符串复制到前一个字符串。 注意复制时,一定要连第二个字符串的0也复制进去。,注意do while结构和i+。 a能接受的类型只有字符数组或指向变量内容的字符指针。 b可以是任意字符串形式。,交换两个字符串,在程序中如何交换两个字符串。 使用辅助数组，复制数组内容进行交换。,一次交换需要3次strcpy。 操作次数为2*len(a)+len(b)。,交换两个字符串,交换指针？ 我们知道数组名是不能交换的，能交换的只有第二种指针+内容类型。,一次交换只需要3次赋值。 操作次数为3。,扩展：对字符串进行排序,使用指针交换，而不是内容

4、交换。,扩展：对字符串进行排序,不用复制内容，速度更快。 最灵活的使用方式：指向字符数组的指针。这样不仅内容可以修改，指针也可以修改。 注意：指向同一内容的指针，只要修改其中一个，另一个也会改变。,说完了字符串的指针操作，让我们看看数组,int a=1,2,3,4,5; cout a+1 endl; cout *(a+1) endl; cout 这两句话一样吗？,问题：怎样让我写的算法可以应用于不同的数组？,比如我想写一个排序的函数，让它既能给a数组排序，又能给b数组排序 这个函数的功能还是不够强，我想让我的排序能给a数组中任意一段区间排序。 甚至，我想讲我的排序函数应用于不同的类型，既能是i

5、nt类型，又能是char类型 如何实现？,实现方法,前两点可以用地址来实现，用序列起始点和结束点的地址来代替具体的变量，第三点则可以引入比较函数或重载操作符来实现。 如果我要给a0到an(不包括an)的数排序，那么a0的地址为a，an的地址为a + n。 比较函数为 T cmp( const T x, const T y); 那么我只要调用sort(a, a + n, cmp); 即可。,我要如何具体实现这样的函数呢？,由于可能涉及到类、模板等内容，暂时先不讲具体实现。不过c+的库函数已经帮我们实现了这样想法。 除了sort还有其他几十个函数，都被放在algorithm库中。 调用该库需加入头

6、文件 #include 这些函数支持多种数据类型，并且除了swap等对单个元素进行操作的函数外，它们一般与sort类似，在调用时都是访问地址。,algorithm库有哪些函数呢？,sort, lower_bound, upper_bound, make_heap, push_heap, 函数太多(见附录)，大家课后自己研究。 先来看一个简单的演示程序。,到底有什么具体应用呢？ 让我们先看一道题目吧。,跳蚤市场,在跳蚤市场人们能够买到便宜货。有些人想出售货物，有些人则想购买货物。 我们考虑一个简单的问题，对于同一种货物，假设它们的质量相同，那么人们一定会以更低的价格来购买。 现在有N个人先后来到

7、市场买卖同一种货物，每个人或者要卖出一件货物，或者要买入几件货物。每个卖货的人会把要卖的货物寄存在市场中，只有比他后到的买家才能购买他的货物。如果货源不足，买家会放弃购买，而不是等待下一个卖家或是只购买一部分。,跳蚤市场,现在按顺序给你这N个人以及他们的目的，请你输出每一个买家的购买结果。 输入格式 第一行为N。 第二到N+1行每行两个整数x和y。若x为0，表示买家，则y表示他想买入y件货物；若x为1，表示卖家，则y表示他想以y元的价格出售货物。,跳蚤市场,输出格式 按顺序输出每个买家的结果，若交易失败，则只输出一行一个字符串“Fail.”表示购买失败，否则输出y行每行一个整数，从小到大以此为

8、他买入的每件货物的价格。 数据范围 50%的数据N10,000； 100%的数据N1,000,000。,跳蚤市场,样例输入 7 1 13 0 2 1 12 1 15 0 1 1 11 0 2,样例输出 Fail. 12 11 13,解题思路,N10,000的算法：当买家要进行购买时，对当前所有要卖出的货物从小到大进行排序。或者每当卖家出售货物时对出售的序列进行插入排序。 编写起来较容易。 N1,000,000的算法：用一个小根堆维护当前的所有要出售物品的价格，每次从堆顶弹出元素给买家。 编写起来较复杂。,怎样既让程序既快又简单？,调用algorithm库！ 关于堆的函数： 建堆：make_he

9、ap() 插入元素：push_heap() 弹出堆顶元素：pop_heap() 有了这三样 ： 数组=堆,#include #include using namespace std; int a1000010; /用一个数组存储堆中元素 bool comp(const int x, const int y) return x y; /比较函数，用于规定堆为小根堆，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,

10、 a + m, comp); else if (m = y) while (y-) pop_heap(a, a + m, comp); cout a-m endl; /堆顶元素弹出至尾部 else cout Fail.n; return 0; ,小结,本题通过巧妙地使用algorithm库中的几个函数将一道以编写与调试为主的题目变成了一道以设计算法为主的题目。,不过瘾？ 再来一道。,NOIP2007 统计数字,某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输

11、出统计结果。 输入文件包含n+1行： 第1行是整数n，表示自然数的个数。 第2n+1行每行一个自然数。 输出文件包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。,NOIP2007 统计数字,数据范围: 40%的数据满足：1=n=1,000 80%的数据满足：1=n=50,000 100%的数据满足：1=n=200,000，每个数均不超过1 500 000 000（1.5*109）,解题思路,枚举每个不同的数，统计出现次数？ 排序，然后让后从小到大找过来？ 看看用算法库如何方便地实现。 二分查找？ lo

12、wer_bound 二分查找，返回第一个大于等于某个数的地址 upper_bound 二分查找，返回第一个大于某个数的地址 如何去重？ 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, ？处的答案为： upper_bound(a , a + n, bi) - lower_bound(a , a + n, bi)(白色字体),总结,算法库并不是我们想象中的万能的，它只能解决一些简单基本的操作。 我们在运用算法库的时候，要灵活运用，根据我们要解决的问题选择合适的函数，切不可刻意去套用。 算法库确实能为我们的编程带来极大的方便，这给了我们更多思考算法的时间，减小了用程序具体实现的难度，为我们解决更复杂的问题创造了可能。