字符串排序回溯计算概论习题课ppt课件.ppt
《字符串排序回溯计算概论习题课ppt课件.ppt》由会员分享,可在线阅读,更多相关《字符串排序回溯计算概论习题课ppt课件.ppt(65页珍藏版)》请在三一文库上搜索。
1、字符串, 排序, (回溯) 计算概论习题课,高圣亮 2007-11-27 ,字符串处理in c&c+ 提纲,概论 字符串处理中经常用到的功能 功能的三种实现方法: C风格字符数组遍历 C风格库函数 C+风格库(字符串类) 与字符串处理相关的两个重要问题 字符串的输入和输出 字符数组与指针的关系,字符串处理in c&c+ 概论,存在形式 c:以null结尾的字符数组 c+:类,对象 特点 c+的方法更直观 c的方法实现效率更高 c/c+字符串表达方式的的相互转化 string s(“example”); s.c_str();,字符串处理in c&c+常用功能,赋值 判断一个字符串的长度 比较两个
2、字符串(如何界定比较?) 字符串的拼接 查找(获得)/添加/删除/替换 (特定位置的)一个特定字串/一段区间 查找/添加/删除/替换 一个特定字符/一个索引位置的字符,字符串处理in c&c+ 功能的三种实现,以获得一个字符串的长度为例: C风格字符数组遍历 #include #include int length(char*); int main () char szInput256; printf (“Enter a sentence: ”); gets (szInput); printf (“The sentence entered is %u characters long.n”,le
3、ngth(szInput);/strlen() int length(char* s) int count=0; while(*s+!=0) count+; return count; ,字符串处理in c&c+ 功能的三种实现,2. c风格处理 strlen()函数 返回从给定指针到终结的0中间的字符个数 3. c+风格处理 size(),length()成员函数返回整个字符串的长度 #include #include using namespace std; int main() string s; getline(cin,s); int n=s.size(); int m=s.lengt
4、h(); /length()是size()的别名 coutn“ “mendl; return 0; ,字符串处理in c&c+ 功能的三种实现,以字符串的比较功能看c+实现比c实现的直观 C风格 #include int main() char* sa=“test“; char sb80; scanf(“%s”, sb); if (!strcmp(sa,sb) printf(“Right!n“); else printf(“Guess again!n“); ,字符串处理in c&c+ 功能的三种实现,字符串的比较 C+风格 = != = #include #include using name
5、space std; int main() string s; char cs80; gets(cs); getline(cin,s); if (cs=s) cout s) cout “ s endl; else cout cs s endl; ,字符串处理in c&c+ 功能的三种实现,以字符串的拼接功能看c+实现比c实现的普适(重载机制) 可用于string 与字符数组和单个字符的拼接 #include #include #include using namespace std; int main() string s; s = “changed“; char b20=“yes“; s =
6、 s + b; cout s endl b endl; ,字符串处理in c&c+ 功能的三种实现,以字符串的赋值看c+实现比c实现的内存透明性 string s1=“yes”; s2=“no”; s2=s1; #include #include int main () char str1=“Sample string“; char str240; char str340; strcpy (str2,str1); strcpy (str3,“copy successful“); printf (“str1: %snstr2: %snstr3: %sn“,str1,str2,str3); 需要特
7、别注意溢出的函数 strcpy strcat,字符串处理in c&c+ 功能的三种实现,查找(获得)/添加/删除/替换 (特定位置的)一个特定字串/一段区间 查找/添加/删除/替换 一个特定字符/一个索引位置的字符 strchr(),strstr(),strpbrk(). find(), insert(),replace(),erase(),append(). 讨论:Do we need to reinvent the wheel?,字符串处理in c&c+ 两个问题,1. 字符串的输入和输出 字符串往往对应于行或词 行适用函数 gets, fgets puts, fputs 其中gets有溢
8、出危险 fgets对字符串结尾的n予以保留 puts,fputs功能相似,都是削掉0,加上n getline, cin.getline 词适用函数 scanf, printf cin, cout 综合 istringstream,字符串处理in c&c+ 两个问题,2. 字符数组与指针的关系常量和变量 对数组不能使用增量运算符,因为增量运算符意味着重新赋值; 不能对指针指向的常量字符串进行修改; 字符指针可以重新赋值;字符数组不能; 字符数组可以通过它改变其中元素,字符指针不能; 可以将数组指定给指针,反之不能. #include int main(void) char sz1=“I Love
9、 You ,LP”; char *sz2 =“I Love You ,LG”; / 此时“I Love You, LG”表示常量字符串 int i; /指针和数组都可以使用数组符号 for (i=0;i6 ;i+ ) putchar(sz1i); putchar(n); for (i=0;i6 ;i+ ) putchar(sz2i); putchar(n); ,字符串处理in c&c+ 两个问题,/指针和数组都可以使用指针加法 for (i=0;i6 ;i+ ) putchar(*(sz1+i); putchar(n); for (i=0;i6 ;i+ ) putchar(*(sz2+i);
10、putchar(n); /但是只有指针可以使用增量运算符 while (*(sz2)!=0) putchar(*(sz2+); putchar(n); /对数组使用增量运算符会发生错误 /*while (*(sz1)!=0) putchar(*(sz1+); putchar(n); */,字符串处理in c&c+ 两个问题,/可以改变字符数组变量中的任意字母 sz11=t; puts(sz1); /不能对指针指向的字符串作此种修改,这样修改之后数据就乱了 /sz21=t; /puts(sz2); /可以将数组指定给指针(实际上是将数组的首地址指定给该指针),反之则不行 sz2=sz1; whi
11、le (*(sz2)!=0) putchar(*(sz2+); putchar(n);,POJ 2689,大小写字母互换 Description 把一个字符串中所有出现的大写字母都替换成小写字母,同时把小写字母替换成大写字母。 Input 输入一行:待互换的字符串。 Output 输出一行:完成互换的字符串(字符串长度小于80)。 Sample Input If so, you already have a Google Account. You can sign in on the right. Sample Output iF SO, YOU ALREADY HAVE A gOOGLE a
12、CCOUNT. yOU CAN SIGN IN ON THE RIGHT.,POJ 2689,#include #include using namespace std; int main() string s; getline(cin, s); for(int i=0; i=A ,POJ 2690,Description 对一个字符串中的所有单词,如果单词的首字母不是大写字母,则把单词的首字母变成大写字母。在字符串中,单词之间通过空白符分隔,空白符包括:空格( )、制表符(t)、回车符(r)、换行符(n)。 Input 输入一行:待处理的字符串(长度小于80)。 Output 输出一行:转换
13、后的字符串。 Sample Input if so, you already have a google account. you can sign in on the right. Sample Output If So, You Already Have A Google Account. You Can Sign In On The Right.,POJ 2690,#include #include using namespace std; int main() string s,t; getline(cin,s); int i=0; bool head=true; while(i!=s
14、.size() if(si=97 ,POJ 2880,句中最长的单词 Description 输入一个英文句子,长度不超过40个字符。编写程序,输出句子中最长的一个单词。 Input 长度不超过40的字符串 Output 句中最长的单词 Sample Input This is a test sentence Sample Output sentence Hint 1.输入只有一个句子,不需使用while 2.若句尾有标点,则标点和最后一个单词可看成是一个单词,可以不用作额外判断 3.假设句中最长的单词只有一个,#include #include #include using namespac
15、e std; int main() string s,w,re; int big=0; getline(cin,s); istringstream stream(s); while(streamw) if(w.size()big) big=w.size(); re=w; coutreendl; ,POJ 2880,POJ 2927,Description 判断一行字符串中的数字出现的个数。 Input 输入只有一行。输入一个字符串,该字符串中可以包含&$#*任何符号以及空格。输入以回车结束。 Output 有多行。输出该字符串中每个出现过的数字,然后在冒号“:”后面输出该数字出现的次数。按数字
16、大小,从小到大的顺序输出。一行输出一个数字及其出现次数。没有出现过的数字不输出。 Sample Input ldksfj857ld*&%&%00000 138*0055end Sample Output 0:5 5:1 7:1 8:1 0:2 1:1 3:1 5:2 8:1,#include int main() char s200; while(fgets(s,200,stdin) int a10=0; char* p=s; while(*p!=n) if(*p=0 ,POJ 2927,排序,内排序和外排序 时空代价分析 三种O(n2)级别的排序及代码实现 插入排序 冒泡排序 选择排序 Sh
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 字符串 排序 回溯 计算 概论 习题 ppt 课件
链接地址:https://www.31doc.com/p-2730527.html