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

1、C风格字符串操作与算法库简单运用计44班 黄斐 刘弘编辑课件字符串的本质什么是字符串？指针数组？char strXX;不仅仅如此。字符串 = 指针 + 内容。常见的字符串有以下几种形式:char strXX; 字符数组char* pstr=XX;字符指针，并指向某内容XXXX 常量字符串编辑课件字符串的本质指针内容字符数组常量。数组名，即str。变量。字符数组中所存内容。字符指针+内容变量。指针变量名，即pstr。可以是变量或者常量。指针所指内容。常量字符串常量。隐式存在，即整个“XX”本身。常量。在一块只读内存上，即XX的内容。编辑课件字符串的本质指针指针是用来表示字符串的。指针永远指向字符

2、串第一个字符的位置。我们操作、使用字符串一般都用指针来表示。内容字符串的内容是一块连续内存上的字符型数据。如何决定长度？内容最后会加一个0,即0来标识字符串的结束。编辑课件热身训练编辑课件热身训练编辑课件热身训练如果还有疑问请参考，徐老师给出的课件W07讨论(4)数组指针函数编辑课件字符串的参数传递字符串虽然有以上三种表示方法，三种方式均可以作为参数传入函数。但函数中传入的字符串都会变成字符指针+内容的形式。编辑课件字符串的参数传递因为是指针+内容的形式，所以可以给指针赋值。编辑课件字符串的参数传递如果函数内要修改字符串内容，编译能够通过。但会根据内容是否为常量，在运行时报错。编辑课件字符串的

3、参数传递传入类型参数类型字符数组变量指针+变量内容指针+内容变量指针+内容（可不可变同前）字符串常量变量指针+常量内容编辑课件strlen原理设计一个函数，传入一个字符串，求该字符串长度。前面已经介绍过，0是标志着字符串结束的标志，所以据此可以设计函数。我们所用的strlen库函数就是这样实现的。所以每次统计长度都需要扫描整个字符串，每次调用的复杂度都是O(n)的。编辑课件strcpy原理设计一个函数，传入两个字符串，将后一个字符串复制到前一个字符串。注意复制时,一定要连第二个字符串的0也复制进去。注意do while结构和i+。a能接受的类型只有字符数组或指向变量内容的字符指针。b可以是任意

4、字符串形式。编辑课件交换两个字符串在程序中如何交换两个字符串。使用辅助数组，复制数组内容进行交换。一次交换需要3次strcpy。操作次数为2*len(a)+len(b)。编辑课件交换两个字符串交换指针？我们知道数组名是不能交换的，能交换的只有第二种指针+内容类型。一次交换只需要3次赋值。操作次数为3。编辑课件扩展：对字符串进行排序使用指针交换，而不是内容交换。编辑课件扩展：对字符串进行排序不用复制内容，速度更快。最灵活的使用方式：指向字符数组的指针。这样不仅内容可以修改，指针也可以修改。注意：指向同一内容的指针，只要修改其中一个，另一个也会改变。编辑课件说完了字符串的指针操作，让我们看看数组i

5、nt a=1,2,3,4,5;cout a+1 endl;cout *(a+1) endl;cout &a1 endl;这三句话的结果分别是什么？scanf(”%d”, &a1);scanf(”%d”, a + 1);这两句话一样吗？编辑课件问题：怎样让我写的算法可以应用于不同的数组？比如我想写一个排序的函数，让它既能给a数组排序，又能给b数组排序这个函数的功能还是不够强，我想让我的排序能给a数组中任意一段区间排序。甚至，我想讲我的排序函数应用于不同的类型，既能是int类型，又能是char类型如何实现？编辑课件实现方法前两点可以用地址来实现，用序列起始点和结束点的地址来代替具体的变量，第三点则

6、可以引入比较函数或重载操作符来实现。如果我要给a0到an(不包括an)的数排序，那么a0的地址为a，an的地址为a + n。比较函数为 T cmp( const T x, const T y);那么我只要调用sort(a, a + n, cmp); 即可。编辑课件我要如何具体实现这样的函数呢？由于可能涉及到类、模板等内容，暂时先不讲具体实现。不过c+的库函数已经帮我们实现了这样想法。除了sort还有其他几十个函数，都被放在algorithm库中。调用该库需加入头文件 #include 这些函数支持多种数据类型，并且除了swap等对单个元素进行操作的函数外，它们一般与sort类似，在调用时都是访

7、问地址。编辑课件algorithm库有哪些函数呢？sort, lower_bound, upper_bound, make_heap, push_heap, 函数太多(见附录)，大家课后自己研究。先来看一个简单的演示程序。编辑课件到底有什么具体应用呢？让我们先看一道题目吧。编辑课件跳蚤市场在跳蚤市场人们能够买到便宜货。有些人想出售货物，有些人则想购买货物。我们考虑一个简单的问题，对于同一种货物，假设它们的质量相同，那么人们一定会以更低的价格来购买。现在有N个人先后来到市场买卖同一种货物，每个人或者要卖出一件货物，或者要买入几件货物。每个卖货的人会把要卖的货物寄存在市场中，只有比他后到的买家才能

8、购买他的货物。如果货源不足，买家会放弃购买，而不是等待下一个卖家或是只购买一部分。编辑课件跳蚤市场现在按顺序给你这N个人以及他们的目的，请你输出每一个买家的购买结果。输入格式第一行为N。第二到N+1行每行两个整数x和y。若x为0，表示买家，则y表示他想买入y件货物；若x为1，表示卖家，则y表示他想以y元的价格出售货物。编辑课件跳蚤市场输出格式按顺序输出每个买家的结果，若交易失败，则只输出一行一个字符串“Fail.”表示购买失败，否则输出y行每行一个整数，从小到大以此为他买入的每件货物的价格。数据范围50%的数据N10,000；100%的数据N1,000,000。编辑课件跳蚤市场样例输入71 1

9、30 21 121 150 11 110 2样例输出Fail.121113编辑课件解题思路N10,000的算法：当买家要进行购买时，对当前所有要卖出的货物从小到大进行排序。或者每当卖家出售货物时对出售的序列进行插入排序。编写起来较容易。N1,000,000的算法：用一个小根堆维护当前的所有要出售物品的价格，每次从堆顶弹出元素给买家。编写起来较复杂。编辑课件怎样既让程序既快又简单？调用algorithm库！关于堆的函数：建堆：make_heap() 插入元素：push_heap()弹出堆顶元素：pop_heap()有了这三样 ： 数组=堆编辑课件#include#includeusing nam

10、espace 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, 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;编辑课件小结本题通过巧妙地使用algorithm库中的几个函数将一道以编写与调试为主的题目变成了一道以设计算法为主的题目。不过瘾？再来一道。编辑课件NOIP2007 统计数字某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。输入文件包含n+1行： 第1行是整数n，表示自然数的个数。 第2n+1行每行一个自然数。 输出文件包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺

12、序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。编辑课件NOIP2007 统计数字count.incount.out82424510021002 34 25 1100 2数据范围:40%的数据满足：1=n=1,00080%的数据满足：1=n=50,000100%的数据满足：1=n=200,000，每个数均不超过1 500 000 000（1.5*109）编辑课件解题思路枚举每个不同的数，统计出现次数？排序，然后让后从小到大找过来？看看用算法库如何方便地实现。二分查找？lower_bound 二分查找，返回第一个大于等于某个数的地址upper_bound 二分查找，返

13、回第一个大于某个数的地址如何去重？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数组rep(i,m) printf(“%d %dn”, bi, ？);return 0;？处的答案为： upper_bound(a , a + n, bi) - lower_bound(a , a + n, bi)(白色字体)编辑课件总结算法库并不是我们想象中的万能的，它只能解决一些简单基本的操作。我们在运用算法库的时候，要灵活运用，根据我们要解决的问题选择合适的函数，切不可刻意去套用。算法库确实能为我们的编程带来极大的方便，这给了我们更多思考算法的时间，减小了用程序具体实现的