[工学]数组2011.ppt

C/C++ 课程设计安排 数组/函数 指针/链表 测试1 封装、继承、多态 STL 测试2 MFC 报告 C/C++ 基础——OPP 数据类型 运算符与表达式 基本结构 数组 函数 指针 结构体 一维数组应用实例1 自学其他排序算法 选择排序、插入排序、希尔排序、堆排序等。 （1）了解3种排序算法的原理并实现； （2）测试比较它们的性能 （比较数据与交换数据的次数）； （3）用递归函数实现某种排序算法。 直接插入排序 基本思想： 假定前面m 个元素已经排序； 取第(m+1) 个元素，插入到前面的适当位置； 一直重复，到m=n 为止。 （初始情况下，m = 1） 存储结构与算法优化 顺序存储结构： 二分插入算法，减少比较次数。 链式存储结构： 减少移动次数。 二分法插入排序 特点： 在直接插入排序的基础上减少比较的次数， 即在插入Ri时改用二分法比较找插入位置， 便得到二分法插入排序。 限制： 必须采用顺序存储方式。 判定素数 筛选法求素数 const int MAX= 100; for(int i=0; iMAX+1; i++) isPrime[i]=true; isPrime[0]=isPrime[1]=false; //1和0不是素数 for( i=2; i n; i++) { //素数的整数倍不是素数，从而筛选掉所有不是素数的数 if(isPrime[i]) for(int j=2*i; j m; j=j+i) isPrime[j]=false; } for( i = 2 ; iMAX+1; i++) if( isPrime[i]) cout i endl; 集合计算 用数组存储集合中的数据，设计函数实现如下有关集合的操作 （1）向已有整数集合中添加元素，若该值已经存在则不添加； （2）实现两个集合的合并操作：属于A或属于B的元素为元素的集合称为A与B的并（集），记作A∪B（或B∪A），即A∪B={x|x∈A,或x∈B} （3）实现两个集合的相交操作：属于A且属于B的元素为元素的集合称为A与B的交（集），记作A∩B（或B∩A），即A∩B={x|x∈A,且x∈B} 字符串查找 编写查找字串的算法，在一个段文字中有哪些信誉好的足球投注网站某个词出现的频率，字符串忽略大小写字符。 （1）int substring(char str[], char substr[])； 返回字串substr在字符串str中出现的位置，若没有查找到该串返回-1，若有多个该字串则返回第一次出现str的位置. （2）int substring(char str[], int beg, int end,char substr[])； 返回字串substr在字符串str的某个区域（[beg,end]）中出现的次数,例如，对于char text[] = “This is a test.”查询从第一个字符到第10个字符中字串 “is”出现的次数，函数substring(test,1,9,“is”)返回2。 字符串练习 编程实现大数（超过232 的数）的 四则运算。 把一个10进制的整数m( 0m 216)转换成n进制数（n = 2, 8或16 ），在主函数中输入m和n值，在主函数中输出转换后的序列 。 设计三连旗的游戏 可以实现两个玩家博弈，也可以选择玩家与程序对弈。人工智能AI算法使得程序按最合理的方式落子，经过若干次博弈后统计电脑获胜的概率。 大连理工大学软件学院 C函数库中提供一些用来处理字符串的函数： puts 输出字符串 gets 输入字符串 (使用时注意前边加: #include stdio.h) strcat 字符串连接 strcpy 字符串复制 strcmp 字符串比较 strlen 字符串长度 strlwr 将字符串中的大写字符转换为小写字符 strupr 将字符串中的小写字符转换为大写字符(使用时注意前边加: #include string.h) 字符串处理函数 大连理工大学软件学院 (1) puts(字符数组) ~ 将一个字符串输出到终端并换行。 (2) gets(字符数组) ~ 输入一个字符串到字符数组， 返回的函数值为该字符数组的起始地址。 可以输入带空格或跳格的字符串,用scanf的%s格式不行. main() { char str[ ]=?book?; puts(str); } 其作用与printf(“%s\n”,str) 等效 main() { cha