主题：采用对折检索的思想，统计给定的x在数组a中出现的次数。 例如，122235。 2出现次数为3。
分析：采用分治(对半搜索)的思路，如果中位数为x，则计数数量1，递归搜索左子表和右子表。 如果中值小于x，则x可能位于右边的子表中，然后查找右边的子表。 如果中值大于x，x可能在左边的子表中。 找左边的子表。
函数代码：计数//x在数组a中出现的次数的函数intcount(inta[]，int start，int end，int X ) {int low，high，mid； int countmid=0，countleft=0，countright=0； low=start high=end； if (低)返回0； //递归出口//对折检索思想mid=(lowhigh )/2； if(a[mid]==x ) /比较中间) { countmid； countleft=count(a，low，mid-1，x )； //左子表中的countright=count(a，mid 1，high，x )； //找半右子表(elseif ) A[mid] )/x只出现在A[mid]的右侧，只要找右子表，countright=Count(A ) a，mid 1，high，x； //右子表else //只查找左子表countleft=count(a，low，mid-1，x )//为了调查左子表的returncountmidcountleftcountright而进行折中； )所有代码(/*主题)采用对折检索的思想，计算给定的x在数组a中出现的次数。 例如，122235。 2出现次数为3。 Project: binary_count (数据结构-半折统计) date :2018/12/26 author : frankyu基础函数： creatlist(inta[]，int n )参数数组长度n功能：创建数组函数初始化前的n个数据时间复杂度： o(n ) initlist(int X ) )参数：数组a功能：初始化时间复杂度：o(1) count ) inta (，int start，int 统计数x时间复杂度： o(n )打印列表(int n (，int n )参数：数组a的功能：遍历数组a，遍历时间复杂度：o(n ) create(inta (，int n )， int n ) )参数：数组长n功能：创建数组a的时间复杂度： o(n ) binary_count(inta )，int n )参数：调用数组a，数组长n功能：输入x 如果中值大于x，x可能在左边的子表中。 找左边的子表。 */# include cstdio # includecstdlib # include cstring # include cmath # include algorithm # include iostream # define maxsize 100 # int A[MaxSize]；/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //创建数组函数以初始化前n个数据boolcreatlist(inta[]，int n ) (if ) n0||nmaxsize ) false； //n错误的for(intI=0； in； I ) Scanf('%d '，A[i]； }return true； //x在数组a中出现的次数函数intcount(inta[]，int start，int end，int X ) {int low，high，mid； int countmid=0，countleft=0，countright=0； low=start high=end； if (低)返回0； //递归出口//对折检索思想mid=(lowhigh )/2； if(a[mid]==x ) /比较中间) { countmid； countleft=count(a，low，mid-1，x )； //左子表中的countright=count(a，mid 1，high，x )； //找半右子表(elseif ) A[mid] )/x只出现在A[mid]的右侧，只要找右子表，countright=Count(A ) a，mid 1，high，x； //右子表else //只查找左子表countleft=count(a，low，mid-1，x )//为了调查左子表的returncountmidcountleftcountright而进行折中； (/)、)、(，)、)、)、)、)、)、功能函数(、(、)、)、)、函数(、、)、函数()、函数(、、)。 for(intI=0； in； I ) {printf('%d '，A[i] )； }printf((n )； //数组函数voidcreate(inta )，int n ) {bool flag； printf ('请输入要创建的数组的长度(1) : )； scanf('%d '，n )； 请输入printf ('以%d个数)空格分隔) : )，n )； flag=creatlist(a，n )； if(flag ) {printf创建成功！ n '； 打印列表(a，n )； }else printf ('输入长度不正确！ n '； //半统计功能函数为count(inta )、int start、int end、int X ) void binary _ count (inta )、int n ) ) int X； int count； if(0==n ) printf ) '数组为空n ' )； else{printf请输入要搜索的值。 n '； scanf('%d '，x )； count=count(a，0，n-1，x )； printf('%d”在数组中出现%d次。
n '，x，count； }//菜单void menu () printf(*******1.创建2 .统计* * * * * * * * (n ) )； printf((******3.退出*********(n ) ) )； (}int main ) ) { int choice； initlist(a )； while(1) { menu )； printf ('请输入菜单编号。 n )； Scanf('%d '，choice )； if(3==choice ) break； switch(choice ) case1:create ) a、n； 黑； case2:binary_count(a，n )； 黑； default:printf ('输入错误！ n '； } } return 0； (结果截图)结果截图实现更多的数据结构(实现数据结构dddwbl版) (包括所有代码) )。
如果有问题请在下面评论。 转载请注明出处，并附上原文的链接。 谢谢你。 如有侵权，请及时联系。