怎样搭建网站,网站备案查询工具,吕梁营销型网站建设费用,淄博做网站跟优化简介#xff1a;40个问题#xff0c;有难有易#xff0c;均使用递归完成#xff0c;需要C/C的指针、字符串、数组、链表等基础知识作为基础。
1、数字出现的次数
由键盘录入一个正整数#xff0c;求该整数中每个数字出现的次数。 输入#xff1a;19931003 输出#xf…简介40个问题有难有易均使用递归完成需要C/C的指针、字符串、数组、链表等基础知识作为基础。
1、数字出现的次数
由键盘录入一个正整数求该整数中每个数字出现的次数。 输入19931003 输出 0 2 1 2 3 2 9 2
#includeiostream
#includecstring
using namespace std;void shine(long long number)
{static char array[10]{0};if(number0){for(int i0;i10;i){if(array[i]0){continue;}couti\t(int)array[i]endl;}memset(array,0,10*sizeof(char));return;}array[number%10];shine(number/10);
}int main()
{long long x;while(true){cinx;if(x-1){break;}shine(x);}return 0;
}2、翻转整数
由键盘输入一个整数(或正或负),翻转该整数将其输出。 输入5201319 输出9131025
输入-1314025 输出-5204131
#includeiostream
using namespace std;long long reverseNumber0(long long number)//number为正整数
{static long long result0;if(number9){numberresult*10number;result0;//千万不能忽略这一步return number;}resultresult*10number%10;return reverseNumber0(number/10);
}long long reverseNumber(long long number)
{return number0?reverseNumber0(number):-reverseNumber0(-number);//number翻转后的数字的正负单独处理
}int main()
{long long x;cinx;coutreverseNumber(x);return 0;
}
3、偶数数字
由键盘输入一个整数n(n0 and n1000000)求该整数n中有多少个偶数数字。 输入131952025 输出3
#includeiostream
using namespace std;int total(long long number)
{if(number9){return number%20?1:0;}return (number%10%20?1:0)total(number/10);
}int main()
{long long number;cinnumber;couttotal(number);
}
4、奇数之和
由键盘输入一个整数n(n0 and n1000000)求整数n中出现的奇数之和。 如 n1003n中出现的奇数有1、3那么所求的奇数之和为4。 n1949n中出现的奇数有1、9那么所求的奇数之和为19。
#includeiostream
using namespace std;int summate(int x)
{if(x9){return x%2?x:0;}int temporaryx%10;return (temporary%2?temporary:0)summate(x/10);
}int main()
{int x;cinx;coutsummate(x)endl;return 0;
}
5、555555555555555555555…(x5,n6)
输入正整数x、n,其中x表示其中的数字(x9)n表示数字所达到的最高位数(n10),输出结果。 输入 5 6 输出 617280
输入 9 9 输出 1111111101
#includeiostream
using namespace std;
long long shine(int x,int n)
{if(n1){return x;}return xshine(x*10x%10,n-1);
}int main()
{int x,n;cinxn;coutshine(x,n);return 0;
}
6、反向输出
输入整数n(n0)之后输入n个正整数按照n个正整数的输入顺序反向输出一次。 输入 6 13 19 9 26 10 3 输出 3 10 26 9 19 13
数组版
#includeiostream
using namespace std;void input(int * array,int length)//倒着存进数组
{if(length0){return;}input(array1,length-1);cin*array;
}void traverse(int * array,int length)//遍历数组
{if(length1){cout*arrayendl;return;}cout*array ;traverse(array1,length-1);
}int main()
{int length;cinlength;int array[length];input(array,length);traverse(array,length);return 0;
}
单链表版
#includeiostream
using namespace std;typedef struct node
{int data;struct node * next;
}Node;Node * input(int x);//录入x个数据存储在带表头单链表中返回表头结点
void traverseBack(Node * head);//倒序遍历单链表
void destroy(Node * head);//销毁单链表int main()
{int x;cinx;Node * headinput(x);traverseBack(head);destroy(head);return 0;
}
Node * input(int x)
{if(x0){Node * headnew Node;//创建表头结点head-nextNULL;head-data-1;//表头结点的数据标记return head;}Node * predecessornew Node;predecessor-nextNULL;cinpredecessor-data;
//-----------------------------------------------Node * headinput(x-1);predecessor-nexthead-next;head-nextpredecessor;
//-----------------------------------------------头插法return head;
}void traverseBack(Node * head)
{if(head-nextNULL)//到达尾结点 递归结束{return;}traverseBack(head-next);if(head-data!-1)//非表头结点{couthead-next-data ;}else//表头结点{couthead-next-dataendl;}
}void destroy(Node * head)
{if(headNULL){return;}Node * successorhead-next;//存储当前结点的后继结点指针delete head;//销毁当前结点destroy(successor);//将后续结点指针传递到下一层进行处理
}
7、1的个数
输入正整数n(n1)求出n对应的二进制数字x中1的个数。 如 n100x 110 0100,x中1的个数为3 n9999,x 10 0111 0000 1111, x中0的个数为8
输入100 输出3
#includeiostream
#includecstring
using namespace std;long convert(long number)
{if(number0){return 0;}return number%2convert(number/2);
}int main()
{long number;while(true){cinnumber;if(number1){break;}coutconvert(number)endl;}return 0;
}
8、0的个数
输入正整数n(n1)求出n对应的二进制数字x中0的个数。 如 n150x 10010110,x中0的个数为4 n9999,x 10 0111 0000 1111, x中0的个数为6
输入150 输出4
输入9999 输出6
#includeiostream
#includecstring
using namespace std;long convert(long number)
{if(number1){return 0;}return (number%20?1:0)convert(number/2);
}int main()
{long number;while(true){cinnumber;if(number1){break;}coutconvert(number)endl;}return 0;
}
9、十进制转二进制
输入正整数n(n1 and n100000)求出n对应的二进制数字。
输入6 输出110
直接输出版
#includeiostreamusing namespace std;void toBinary(long x)
{if(x0)//递归最后一层{return;}int temporaryx%2;//前进时存储x除以2取余的值toBinary(x/2);couttemporary;//回归时输出x除以2取余的值
}int main()
{int n;cinn;toBinary(n);//函数中缺少换行coutendl;//在此加上return 0;
}数组版
#includeiostream
#includecstring
using namespace std;char * transform(long long x)
{static int length0;//十进制数转换成二进制数后的长度、也是递归的层数(从1开始)static int index0;//在函数回归时数组所使用的下标length;if(x0)//到达递归的最后一层{char * resultnew char[length];//数组的长度刚刚好的样子没有浪费result[length-1]\0;
//-------------------------------------------------------两者在递归最后一层必须归零length0;index0;
//-------------------------------------------------------return result;}char * resulttransform(x/2);result[index]x%20;//将长整型数据变成字符型数据存入数组return result;
}void traverse(char * source)//遍历字符串
{if(*source0){coutendl;return;}cout*source;traverse(source1);
}int main()
{long long x;while(true){cinx;if(x1 || x100000){coutinvalid valueendl;break;}traverse(transform(x));}return 0;
}
单链表版
#includeiostream
using namespace std;struct Node
{char data;Node * next;Node(char data,Node * next):data(data),next(next){}
};Node * toBinary(long x)//把正整数x转换为二进制数之后存储在单链表中返回表头结点指针
{if(x0){Node * headnew Node(-1,nullptr);//创建表头结点,为区别出表头结点将表头结点的值置为-1return head;//返回表头结点指针 }int temporaryx%2;//将x除以2取余的值临时存储在变量temporary中Node * headtoBinary(x/2);
//---------------------------------------------单链表头插法Node * pnew Node(temporary0,nullptr);p-nexthead-next;head-nextp;
//---------------------------------------------单链表头插法 return head;
}void traverse(Node * head)//反向遍历带表头单链表
{if(head-nextnullptr)//到达尾结点即递归的最后一层{return;}traverse(head-next);couthead-next-data;if(head-data-1)//到达表头结点{coutendl;}
}int main()
{long x;while(true){cinx;if(x1 || x100000){coutinvalid valueendl;break;}traverse(toBinary(x));}return 0;
}10、最长的连续1
输入正整数n(n1 and n100000)求出n对应的二进制数字x中连续1的最大长度。 如 n1949,x111 1001 1101,x中连续的1有三组,第一组是111 1,第二组是111, 第三组是1最长是的1111长度为4。 n500,x111110100,x中连续的1有两组,第一组是11111,第二组是1, 最长是的11111长度为5。 n 888,x 11 0111 1000,x中的连续1有两组,第一组是11,第二组是1111,最长是的1111长度为4。 n 1918,x 111 0111 1110,x中的连续1有两组,第一组是111,第二组是111111,最长是的111111长度为6。
输入1993 输出5
简易版
#includeiostream
using namespace std;int getLength(long number)
{static int length0;//存储每组连续1的长度static int lengthMaximum-1;//存储连续1的最大长度if(number0){//递归的最后一层numberlengthMaximumlength?lengthMaximum:length;
//--------------------------------------------------------------变量值需及时还原length0;lengthMaximum-1;
//--------------------------------------------------------------变量值需及时还原return number;}if(number%21)//number除以2取余为1,length就进行累加{length;}else//一旦number除以2取余为0且length0,说明一组连续1的length累加结束{if(length0){lengthMaximumlengthMaximumlength?length:lengthMaximum;length0;}}return getLength(number/2);
}int main()
{long x;while(true){cinx;if(!(x1 x100000)){break;}coutgetLength(x)endl;}return 0;
}
困难版
#include iostreamusing namespace std;int longestContinuousOne(int number);//求整数n的二进制表示中连续1的最大长度int main()
{long x;while(true){cinx;if(!(x1 x100000)){break;}coutlongestContinuousOne(x)endl;}return 0;
}int longestContinuousOne(int number)
{static int counter0;//计算连续1长度的变量if(number0)//到达递归边界开始回归{numbercounter;counter0;/*某段连续1的长度在number%2为1时长度counter自增在number%2为0时将counter的值存储在temporary中counter置为0,等待下一段连续1的长度统计最后一段连续1的长度不会经过number%2为0这个条件的判断所以在递归边界处将counter的值存储在number中返回number*/return number;}if(number%21)//整数n对2取余为1则counter自增{counter;}else//整数n对2取余为0{if(counter0)//且counter大于0某一段连续1的长度已经统计完毕{int temporarycounter;//存储counter的值counter0;//将counter置为0待统计下一段连续1的长度int lengthlongestContinuousOne(number/2);//递归调用返回长度较大的一段连续1的长度return lengthtemporary?length:temporary;//将返回的length与temporary比较返回较大的那个值}}return longestContinuousOne(number/2);
}11、变成数组
输入正整数n(n10 and n987654321)将n的每位数字从高位到低存储到数组再遍历数组数组元素之间用逗号隔开。
输入13192520 输出1,3,1,9,2,5,2,0
#includeiostream
using namespace std;char * transform(long long number)//正整数的数字们转变成数组元素返回数组首字节指针
{static int length0;//既计算number的长度也作数组的下标static char * beginnullptr;//存储数组首字节指针length;if(number0){//到达递归的最后一层char * arraynew char[length];//确定number的长度length后创建数组array[length-1]\0;//length比number的实际长度要大1是为了存储\0beginarray;//存储数组首字节指针length0;return array;}char temporarynumber%100;//整型数据转成字符型数据char * arraytransform(number/10);*begintemporary;return array;
}void traverse(char * source)//遍历字符数组
{if(*(source1)0){cout*sourceendl;return;}cout*source,;traverse(source1);
}int main()
{long long number;while(true){cinnumber;if(number10 || number987654321){break;}traverse(transform(number));}return 0;
}
12、变成单链表
输入正整数n(n10 and n987654321)将n的每位数字存储到单链表中再遍历单链表结点之间用箭头-隔开。
输入13192520 输出1-3-1-9-2-5-2-0
#includeiostreamusing namespace std;struct Node
{short data;Node * next;Node(short data,Node * next):data(data),next(next){}
};Node * transform(long long x)
{if(x0){Node * headnew Node(-1,nullptr);//表头结点的值置为-1,是为区别出表头结点和数据结点return head;}Node * pnew Node(x%10,nullptr);Node * headtransform(x/10);
//-------------------------------单链表头插法 p-nexthead-next;head-nextp;
//-------------------------------单链表头插法 return head;
}void traverseReversely(Node * head)//反向遍历单链表
{if(head-nextnullptr)//递归最后一层到达倒数第二个结点{return;}traverseReversely(head-next);if(head-data!-1){couthead-next-data-;}else{couthead-next-dataendl;}
}int main()
{long long number;while(true){cinnumber;if(number10 || number987654321){break;}traverseReversely(transform(number));}return 0;
}13、水仙花数(再三斟酌)
水仙花数是指一个 n 位数n≥3其各位数字的 n 次幂之和等于该数本身。 如 3^3 7^3 1^3 371 3至9位的水仙花数均以列出请编程求出100到999999999之间的水仙花数。 3位的水仙花数153 370 371 407 4位的水仙花数1634 8208 9474 5位的水仙花数54748 92727 93084 6位的水仙花数548834 7位的水仙花数1741725 4210818 9800817 9926315 8位的水仙花数24678050 24678051 88593477 9位的水仙花数146511208 472335975 534494836 912985153
简单明了版
运行时间实在是感人肺腑
#includeiostream
using namespace std;long long isDaffodil0(long long number)//求n位数number各位数字的 n 次幂之和
{static int length0;//存储正整数的长度static int length0;//存储正整数的长度在回归时使用length;if(number0)//number得0时进入递归的最后一层{length0length-1;//number的长度length多算了一次所以length减1length0;//必须在这里归零return 0;}int portionisDaffodil0(number/10);long long power1;int xnumber%10;for(int i0;ilength0;i){powerpower*x;}return powerportion;
}bool isDaffodil(long long number)
{return isDaffodil0(number)number?true:false;//n位数number各位数字的 n 次幂之和是否等于该数本身
}int main()
{for(int i100;i999999999;i){if(isDaffodil(i)){coutiendl;}}return 0;
}
优化提升版
#includeiostream
#includecstring
using namespace std;long long isDaffodil0(long long number)//求n位数number各位数字的 n 次幂之和
{static int length0;//存储正整数的长度static int length0;//存储正整数的长度在回归时使用接收length的值static long array[10]{0};//10号元素存储数字的长度length;if(number0)//number得0时进入递归的最后一层{length0length-1;//number的长度length多算了一次所以length减1length0;//必须在这里归零if(array[10]!length0){//10号元素的长度与本次的length0不相等说明number的长度变化了memset(array,0,sizeof(array));//数组清零array[10]length0;//10号元素重新赋值}return 0;}int portionisDaffodil0(number/10);int xnumber%10;if(x0 || x1)//0的n次方还是01的n次方还是1{return xportion;}if(array[10]length0 array[x]!0){//10号元素的长度与本次的length0相等并且数组中存储了x的n次方return array[x]portion;}array[x]1;for(int i0;ilength0;i){array[x]array[x]*x;}//x不为0也不为1,数组中也没有存储x的n次方单独计算一次return array[x]portion;
}bool isDaffodil(long long number)
{return isDaffodil0(number)number?true:false;//n位数number各位数字的 n 次幂之和是否等于该数本身
}int main()
{couti am excellentendl;for(int i100;i999999999;i){if(isDaffodil(i)){coutiendl;}}return 0;
}
14、完数
一个数如果恰好等于它的因子之和这个数就称为 完数 。例如:6123求1至10000以内的所有完数。 1至10000以内的所有完数6、28、496、8128
#includeiostreamusing namespace std;int isPerfectNumber0(int x,int begin,int end)
{if(beginend){return 0;}int temporary(x%begin0?begin:0);return temporaryisPerfectNumber0(x,begin1,end);
}bool isPerfectNumber(int x)
{/*x只要1到x/2范围内的整数进行取余运算即可只要一次取余运算结果为0,那么x就找到一个因子就将因子存储在临时变量中只要一次取余运算结果不为0,那么x就没找到因子,就将0存储在临时变量中 之后对这些临时变量进行累加运算累加和等于x,那么x就为完数反之则反*/return xisPerfectNumber0(x,1,x/2);
}int main()
{long long number;for(int i1;i10000;i){if(isPerfectNumber(i)){coutiendl;}}return 0;
}15、回文数
回文数是指正读和反读都相同的数例如:252、858 求1到100000000(这是一亿)之间的回文数。 要求每行输出五个数数与数之间用’\t’隔开。
#includeiostream
using namespace std;long long isPalindromeNumber0(long long number)//将number逆序组装成一个新整数
{static long long x0;if(number9){//递归的最后一层numberx*10number;x0;//静态变量x在最后一层必须要归零return number;}xx*10number%10;return isPalindromeNumber0(number/10);
}bool isPalindromeNumber(long long number)
{return numberisPalindromeNumber0(number);
}int main()
{int counter0;for(int i1;i100000000;i){if(isPalindromeNumber(i)){if(counter5){coutiendl;counter0;continue;}couti\t;counter;}}return 0;
}
16、16、123…N
输入正整数N(N1 and N1000)求出1、2、3、…、N的和。
输入3 输出6
输入10 输出55
#includeiostream
using namespace std;long long summate(long long begin,long long end)
{if(beginend){return begin;}return beginsummate(begin1,end);
}int main()
{long long begin1;long long end;while(true){cinend;if(end1 || end1000){break;}coutsummate(begin,end)endl;}return 0;
}
17、反转数组
输入正整数N(N1)再输入N个整数将其存储在数组中最后遍历反转后的数组数与数之间用逗号隔开。
输入 6 9 10 26 3 13 19 输出 19,13,3,26,10,9
首尾交换法
#includeiostream
using namespace std;void input(int * array,int length)//为数组输入数据
{if(length0){return;}cin*array;input(array1,length-1);
}void traverse(int * array,int length)//遍历数组数组元素之间用逗号隔开
{if(length1){cout*arrayendl;return;}cout*array,;traverse(array1,length-1);
}void reverse(int * array,int length)//反转数组
{if(length0 || length1){return;}int temporaryarray[0];array[0]array[length-1];array[length-1]temporary;reverse(array1,length-2);
}
int main()
{int length;cinlength;int array[length]{0};input(array,length);//为数组输入数据coutbefore reversing:endl;traverse(array,length);//遍历数组coutafter reversing:endl;reverse(array,length);//反转数组元素traverse(array,length);//遍历数组return 0;
}
逆序赋值法1
#includeiostream
using namespace std;void input(int * array,int length)//给数组录入数据
{if(length0){return;}cin0[array];input(array1,length-1);
}void traverse(int * array,int length)//遍历数组
{if(length1){coutarray[0]endl;return;}coutarray[0],;traverse(array1,length-1);
}void reverse(int * array,int length)//反转数组
{static int * beginarray;//存储数组的首字节指针if(length0){beginnullptr;return;}if(beginnullptr){beginarray;}int temporaryarray[length-1];//从后向前存储每个元素的值int * pbegin;//从前向后存储数组每个元素的首字节指针即temporary要存储的位置reverse(array,length-1);*ptemporary;
}int main()
{int length;int * arraynullptr;while(true){cinlength;if(length0){break;}arraynew int[length];input(array,length);//为数组输入数据reverse(array,length);//反转数组元素traverse(array,length);//遍历数组if(array!nullptr){delete[] array;}}return 0;
}逆序赋值法2
#includeiostream
using namespace std;void input(int * array,int length);//为数组录入数据
void traverse(int * array,int length);//遍历数组
void reverse(int * array,int begin,int end);//反转数组int main()
{int length;int * array;while(true){cinlength;if(length0){break;}arraynew int[length];input(array,length);reverse(array,0,length-1);traverse(array,length);}return 0;
}void input(int * array,int length)
{if(length0){return;}cin0[array];input(array1,length-1);
}void traverse(int * array,in length)
{if(length1){cout*arrayendl;return;}cout*array,;traverse(array1,length-1);
}void reverse(int * array,int begin,int end)
{if(beginend){return;}int indexend-begin;//将元素下标从高到低存储到变量中index中int temporaryarray[begin];//按从低到高的下标顺序读取元素的值并存储在变量中reverse(array,begin1,end);array[index]temporary;//回归时按从低到高的下标顺序重新给数组元素赋值/*若有数组 int array[8],那么数组下标分别为 0,1,2,3,4,5,6,7令begin0,end7,在递归过程中begin处于递增状态,end保持不变indexend-begin7-07indexend-begin7-16indexend-begin7-25indexend-begin7-34indexend-begin7-43indexend-begin7-52indexend-begin7-61indexend-begin7-70temporary在递归过程中存储array[0]、array[1]、array[2]、array[3]、array[4]、array[5]、array[6]、array[7]的值。在回归过程中将temporary的值赋给array[index]temporary依次为 array[7]、array[6]、array[5]、array[4]、array[3]、array[2]、array[1]、array[0]array[index]依次为array[0]、array[1]、array[2]、array[3]、array[4]、array[5]、array[6]、array[7]array[0]装载array[7]的值array[1]装载array[6]的值array[2]装载array[5]的值*/
}18、时间转换1
输入秒数n(n0),将其转换为时分秒的格式输出。 如
秒数时分秒10030:16:431200:2:0252013197000:21:59987654321274348:25:21
输入120 输出0:2:0
#includeiostream
using namespace std;void convert(long long time)
{static int base3600;if(base1){//递归的最后一层base3600;//base的值必须置为3600couttimeendl;return;}couttime/base:;timetime%base;basebase/60;convert(time);
/*
起始的基数base是3600秒数除以base得到小时数秒数对base取余得到剩余秒数
基数base变成60剩余秒数除以60得到分数剩余秒数对base取余得到剩余秒数
基数base变成1剩余秒数无须再做除法、取余运算了
*/
}
int main()
{long long time;while(true){cintime;if(time0){break;}convert(time);}return 0;
}19、时间转换2
我们假定一年为360天一个月为30天。输入天数N以Y-M-D的格式输出。 Y是年数、M是月数、D是天数。 如
天数年-月-天2520131970003-7-2910032-9-1312003-4-0108000300-0-0722620-0-26
输入1200 输出3-4-0
#includeiostream
using namespace std;void convert(int day)
{static int base360;if(base2){coutdayendl;base360;return;}coutday/base-;dayday%base;basebase/12;convert(day);
}int main()
{int day;while(true){cinday;if(day0){break;}convert(day);}return 0;
}20、N个祝福
输入整数n(0n10)输出n个“祝福”。 注输出中用\t作为间隔符
简单版
输入 3 输出 祝福 3 祝福 2 祝福 1
#includeiostream
using namespace std;void wish(int times)
{if(times0){return;}cout祝福\ttimesendl;wish(times-1);
}
int main() {int times;cintimes;wish(times);return 0;
}
困难版
输入 3 输出 祝福 1 祝福 2 祝福 3
#includeiostream
using namespace std;void wish(int times)
{if(times0){return;}wish(times-1);cout祝福\ttimesendl;
}int main()
{int times;cintimes;wish(times);return 0;
}
复杂版
输入 3 输出 祝福 3 祝福 2 祝福 1 祝福 1 祝福 2 祝福 3
#includeiostream
using namespace std;void wish(int times)
{if(times0){return;}cout祝福\ttimesendl;wish(times-1);cout祝福\ttimesendl;}int main()
{int times;cintimes;wish(times);return 0;
}21、数组与单链表的转换1(头插法)
输入n(n0)个整数存储在数组中将数组中的数据按原有顺序复制到带表头的单链表中再遍历单链表。 输入 8 9 10 26 3 13 20 19 25 输出 9-10-26-3-13-20-19-25
#includeiostream
using namespace std;typedef struct node
{int data;struct node * next;
}Node,*NodePointer;NodePointer arrayToLinkedList(int * array,int length)
{if(length0){Node * headnew Node;head-nextNULL;return head;}Node * pnew Node;p-data*array;Node * headarrayToLinkedList(array1,length-1);p-nexthead-next;//头插法head-nextp;//头插法return head;
}void traverseLinkedList(Node * head)
{if(head-next-nextNULL){couthead-next-dataendl;return;}couthead-next-data-;traverseLinkedList(head-next);
}void input(int * array,int length)
{if(length0){return;}cin*array;input(array1,length-1);
}int main()
{int length;cinlength;int array[length];input(array,length);NodePointer headarrayToLinkedList(array,length);traverseLinkedList(head);return 0;
}
22、数组与单链表的转换2(尾插法)
输入n(n0)个整数存储在数组中将数组中的数据按相反顺序复制到带表头的单链表中再遍历单链表。
输入 5 3 10 26 9 18 输出 18-9-26-10-3
回归时使用尾插法
#includeiostream
using namespace std;typedef struct node
{int data;struct node * next;
}Node,*NodePointer;NodePointer arrayToLinkedList(int * array,int length)
{static NodePointer tailNULL;if(length0){Node * headnew Node;head-nextNULL;tailhead;return head;}Node * pnew Node;p-data*array;p-nextNULL;Node * headarrayToLinkedList(array1,length-1);tail-nextp;//尾插法tailp; //尾插法return head;
}void traverseLinkedList(Node * head)//遍历单链表
{if(head-next-nextNULL)//到达倒数第二个结点即递归的最后一层{couthead-next-dataendl;return;}couthead-next-data-;traverseLinkedList(head-next);
}void input(int * array,int length)//为数组录入数据
{if(length0){return;}cin*array;input(array1,length-1);
}int main()
{int length;cinlength;int array[length];input(array,length);Node * headarrayToLinkedList(array,length);traverseLinkedList(head);return 0;
}前进时使用尾插法
#includeiostream
using namespace std;typedef struct node
{struct node * next;int data;
}Node,*NodePointer;Node * arrayToLinkedList(int * array,int length)
{static NodePointer tailNULL;if(length0){Node * headnew Node;head-nexttail;tailNULL;return head;}Node * pnew Node;p-data*array;//尾插法p-nexttail;//尾插法tailp;//尾插法return arrayToLinkedList(array1,length-1);
}void traverseLinkedList(Node * head)
{if(head-next-nextNULL){couthead-next-dataendl;return;}couthead-next-data-;traverseLinkedList(head-next);
}void input(int * array,int length)
{if(length0){return;}cin*array;input(array1,length-1);
}int main()
{int length;cinlength;int array[length];input(array,length);Node * headarrayToLinkedList(array,length);traverseLinkedList(head);return 0;
}
23、整数与单链表之求和(再三斟酌)
输入两个整数n1、n2计算两者的和。 (0n1999999999999999999990n299999999999999999999)。 不要数9的个数了这是20个9。
输入 99999999999999999999 9 输出 100000000000000000008
输入 9876 6789 输出 16665
输入 99999999999999999999 99999999999999999999 输出 199999999999999999998
#includeiostream
#includecstring
using namespace std;
typedef struct node
{char data;struct node * next;
}Node;void reverse(char * source)//反转字符串
{if(*source0 || *(source1)0){return;}int lengthstrlen(source);char temporary*source;*sourcesource[length-1];source[length-1]\0;reverse(source1);source[length-1]temporary;
}Node * summate(char * s1,char * s2)//大数求和
{static int carry0;//处理加法中的进位Node * pNULL;if(*s10 *s20){//递归的最后一层Node * headnew Node;head-nextNULL;head-data-1;//因为计算的是两个正整数的和所以把表头结点的数据域置为-1作为表头结点的判断依据if(carry!0){pnew Node;p-datacarry;p-nexthead-next;head-nextp;carry0;}return head;}if(*s1!0 *s2!0){pnew Node;p-data(*s1-0)(*s2-0)carry;carryp-data/10;p-data%10; }else{pnew Node;p-data(*s10?*s2-0:*s1-0)carry;carryp-data/10;p-datap-data%10;}Node * headsummate(*s10?s1:s11,*s20?s2:s21);p-nexthead-next;//回归的时候用头插法把单链表串起来低位在前高位在后head-nextp;return head;
}void traverse(Node * head)
{if(head-next-nextNULL){cout(int)head-next-data;return;}traverse(head-next);cout(int)head-next-data;if(head-data-1)//判断是否到达了表头结点{coutendl;}
}int main()
{char s1[1024];char s2[1024];Node * head;while(true){cin.getline(s1,1024);cin.getline(s2,1024);if(strcmp(s1,-1)0 || strcmp(s2,-1)0){break;}reverse(s1);reverse(s2);headsummate(s1,s2);traverse(head);}return 0;
}
24、整数与单链表之阶乘(再三斟酌)
输入一个整数n求n的阶乘。
基础版阶乘(0n10)
输入5 输出120
输入10 输出3628800
#includeiostream
using namespace std;
long getFactorial(int number)
{if(number2 || number1){return number;}return number*getFactorial(number-1);
}int main()
{int number;while(true){cinnumber;if(number1 number10){coutgetFactorial(number)endl;}else{break;}}return 0;
}
升级版阶乘(0n100)
输入20 输出2432902008176640000
输入30 输出265252859812191058636308480000000 #includeiostream
using namespace std;typedef struct node{int data;struct node * next;
}Node;void multiply0(Node * head,int x);//使用单链表进行乘法运算
void multiply(Node * head,int x);//单链表是否为空分两种情况处理乘法运算
void traverse(Node * head);//遍历单链表
Node * makeFactorial(int x);//大数阶乘,返回表头结点指针
void destroy(Node * head);//销毁单链表int main()
{long x;Node * headNULL;while(true){cinx;if(x0){break;}head makeFactorial(x);traverse(head);//(倒序)遍历单链表destroy(head);//销毁单链表}return 0;
}void traverse(Node * head)
{if(headNULL){return;}traverse(head-next);head-data-1?coutendl:couthead-data;
}Node * makeFactorial(int x)
{if(x1){Node * headnew Node;head-nextNULL;head-data-1;return head;}Node * headmakeFactorial(x-1);multiply(head,x);return head;
}void multiply(Node * head,int x)
{if(head-nextNULL)//若单链表的表头结点指针域为空{while(x0){Node * pnew Node;p-nextNULL;p-datax%10;head-nextp;headp;xx/10;}}else//若单链表的表头结点指针域不为空{multiply0(head-next,x);//表头结点不参与乘法运算}
}void multiply0(Node * head,int x)
{static int carry0;//存储乘法运算产生的进位static Node * predecessorNULL;//存储结点的前驱结点指针if(headNULL)//在递归最后一层处理遗留的进位{Node * p;while(carry0)//处理进位{pnew Node;p-datacarry%10;p-nextNULL;predecessor-nextp;predecessorp;carry/10;//整型变量carry在递归最后一层也要归零这里在循环中处理掉了}predecessorNULL;//指针变量归零return;}
//--------------------------------------------首结点到尾结点都与x进行了乘法运算int resulthead-data*xcarry;head-dataresult%10;carryresult/10;
//--------------------------------------------首结点到尾结点都与x进行了乘法运算predecessorhead;//存储当前结点指针实则存储下一结点的前驱结点指针multiply0(head-next,x);
}void destroy(Node * head)//销毁单链表
{if(headNULL){return;}destroy(head-next);//cout销毁单链表其中结点\thead-dataendl;delete head;
}
25、双向循环链表之约瑟夫环(再三斟酌)
n个小朋友围成一圈从第一个小朋友自1开始顺序报数,数到淘汰数x的小朋友出圈再由下一个小朋友重新从 1开始报数数到淘汰数 x的小朋友再出圈依次类推直到剩下一个小朋友求该小朋友的编号m。 输入n和x,求m。
测试数据
人数淘汰数最后一人编号103485938100558568768706519098355829
输入10 3 输出4 #includeiostreamusing namespace std;
typedef struct node {int data;struct node *prior;struct node *next;
} Node;//按照number的大小生成number个结点生成带表头的双向循环链表,结点的数据依次为1、2、3...
Node *generate(int number);
//传入尾结点指针遍历双向循环链表
void traverse(Node *tail);
//销毁双向循环链表
void destroy(Node * tail);
//约瑟夫环自1报数并移除结点
Node * remove(Node *head, int target);int main() {int number;int target;Node *tail NULL;while (true) {cin number;cin target;if (number 0 || target0) {break;}tail generate(number);//traverse(tail);tailremove(tail-next,target);couttail-dataendl;destroy(tail);}return 0;
}Node * remove(Node *head, int target)
{static int counter 0;//用于报数存储每次报到的数if (head-next-next head head-prior-priorhead)//递归最后一层{//只剩表头结点、一个数据结点那么指针变量head是指向表头结点、还是指向尾结点呢依淘汰数target而定counter 0;return head-data-1?head-next:head;//返回尾结点指针}if (head-data ! -1)//非表头结点才报数遇表头结点不报数{counter;//报数if (counter target) //报到指定的淘汰数{counter 0;//归零下次报数自1开始head-prior-next head-next;//当前结点的前驱结点后指针域指向当前结点的后继结点head-next-prior head-prior;//当前结点的后继结点前指针域指向当前结点的前驱结点Node *p head;//存储当前结点的指针head head-prior;//存储当前结点的前驱结点指针delete p;//释放当前结点}}remove(head-next, target);
}void destroy(Node * tail)
{if(tail-data-1)//递归最后一层到达表头结点{delete tail;return;}Node * ptail-prior;delete tail;destroy(p);
}void traverse(Node *tail) {if (tail-data -1) {return;}traverse(tail-prior);if (tail-next-data -1) {//判断是否为尾结点尾结点的后继结点为表头结点而表头结点的数据为-1cout tail-data endl;} else {cout tail-data -;}
}Node *generate(int number) {if (number 0) {//递归最后一层Node *head new Node;head-data -1;head-next NULL;head-prior NULL;return head;}Node *successor new Node;//创建新结点successor-data number;Node *predecessor generate(number - 1);if (predecessor-next NULL predecessor-prior NULL)//表头结点{//递归倒数第二层predecessor-next successor;predecessor-prior successor;successor-prior predecessor;successor-next predecessor;} else//非表头结点,做追加尾结点操作{successor-prior predecessor;//新结点的前指针域指向尾结点successor-next predecessor-next;//新结点的后指针域指向表头结点predecessor-next successor;//原先的尾结点后指针域指向新结点}return successor;//返回最新的尾结点指针
}
26、隔壁是偶数
输入整数n(n0 and n16)再输入n个正整数。在n个正整数中若某些数的隔壁均是偶数请依次输出换行。第一个正整数与最后一个正整数无须考虑。
输入 10 13 19 10 9 26 3 25 20 88 18 输出 9 88
输入 6 13 25 19 20 15 10 输出 15
顺序表版
#includeiostreamusing namespace std;void input(int *array, int length);//给定数组首字符指针、数组长度录入数据
void neighborNumber(int *array, int length);//求出隔壁为偶数的数int main() {int length;cin length;int *array new int[length];input(array, length);neighborNumber(array, length);return 0;
}void neighborNumber(int *array, int length) {if (length 2)//首元素和尾元素不考虑所以长度length减去2{return;}neighborNumber(array, length - 1);/*假设length8,那么可能满足条件的元素所在的下标依次为1、2、3、4、5、6下标为0、7的元素是不满足条件的所以不参与条件判断函数向下递归的时候,length在每一层的值分别为8、7、6、5、4、3、2(这里的2出现在最后一层)length的值与我们所需的元素下标是不符的,经过推算得知length-2是符合的如8、7、6、5、4、36、5、4、3、2、1*///coutarray[length-2]---;if (array[length - 2 - 1] % 2 0 array[length - 2 1] % 2 0) {cout array[length - 2] endl;}}void input(int *array, int length) {if (length 0) {return;}cin *array;input(array 1, length - 1);
}/*
10
13 19 10 9 26 3 25 20 88 189
88
----------------------------------
5
98 150 88 900 20150
88
900
----------------------------------
6
13 25 19 20 15 1015
----------------------------------
15
82 19 10 9 26 3 28 20 10 18 13 87 10 3 5819
9
3
20
10
3*/
双链表版
#includeiostreamusing namespace std;
struct Node {int data;Node * prior;Node * next;Node():data(),prior(),next(){}//空参构造函数Node(int data, Node * prior,Node * next) : data(data), prior(prior),next(next) {}
};Node * input(int length);//根据长度生成相应个结点的带表头双向链表,返回表头结点指针
void neighborNumber(Node * head);求出隔壁为偶数的数int main()
{int length;cinlength;Node * headinput(length);neighborNumber(head);return 0;
}Node * input(int length)//根据长度生成相应个结点的带表头双向链表,返回表头结点指针
{if(length0){Node * headnew Node(-1,NULL,NULL);return head;}Node * pnew Node;cinp-data;Node * head input(length-1);if(head-priorNULL head-next!NULL)//非空双链表{//双链表头插法插入结点p-priorhead;p-nexthead-next;head-next-priorp;head-nextp;}else//空双链表只有表头结点{//双链表头插法插入结点p-priorhead;p-nexthead-next;head-nextp;}return head;
}void neighborNumber(Node * head)
{if(head-nextNULL)//尾结点不进行筛选在递归的最后一层将尾结点作为结束条件{return;}if(head-prior!NULL head-prior-prior!NULL)//表头结点、首结点不进行筛选{if(head-prior-data%20 head-next-data%20){couthead-dataendl;}}neighborNumber(head-next);
}
27、字符串的长度
输入一字符串求其长度。需手写函数不得另外调用函数。
输入YouAreMyFire 输出12
#includeiostream
using namespace std;int lengthOfString(char * source)//求字符串长度
{if(*source){return 1lengthOfString(source1);}return 0;
}int main()
{char string[1024];cin.getline(string,1024);coutlengthOfString(string);return 0;
}
28、英文语句中单词的个数
输入一英文语句求语句中有多少个单词。
输入Hello!I’m Lisa. How are you doing? 输出8
#includeiostream
#includecstring
using namespace std;int count(char * string);//统计英文语句中单词的个数
bool isLetter(char target);//判断字符是否为字母int main()
{char string[1024]{0};while(true){cin.getline(string,1024);coutcount(string)endl;if(strcmp(string,exit)0 || strcmp(string,quit)0){break;}}return 0;
}int count(char * string)//统计英文语句中单词的个数
{if(*string0)//到达字符结束符{//递归最后一层return 0;}if(isLetter(string[0]) !isLetter(string[1])){//当前字符为字母而后继字符非字母表明出现了一个单词return 1count(string1);}return 0count(string1);//未出现单词
}bool isLetter(char target)//判断字符是否为字母
{return (targeta targetz)||(targetA targetZ);
}29、每个字母出现的次数
输入一单词求单词中每个字母出现的次数。 注输出时按字母顺序来并且小写字母排在前大写字母排在后。
输入Pepper
输出 e 2 p 2 r 1 P 1
#includeiostream
#includecstring
using namespace std;void shine(char * source)
{static int letter[52]{0};/*下标0~25的空间存储各小写字母的出现次数下标26~51的空间存储各大写字母的出现次数*/if(*source\0){//递归最后一层输出结果for(int i0;i52;i){if(i26 letter[i]0){cout(char)(ai)\tletter[i]endl;}else if(i26 letter[i]0){cout(char)(Ai-26)\tletter[i]endl;}}memset(letter,0,52*sizeof(int));//数组清零return;}letter[(*sourcea *sourcez)?*source-a:*source-A26];/*推算字母所对应的下标若为小写字母*source-a可以推算出下标0,1,2,,,25若为大写字母*source-A26可以推算出下标26,27,,,51*/shine(source1);
}int main()
{char string[1024]{0};while(true){cin.getline(source,1024);if(strcmp(string,exit)0 || strcmp(string,quit)0){break;}shine(source);}return 0;
}
30、字符串中出现多少个数字
输入一字符串求字符串中有多少个数字。
输入 1319 YouAreMyFire 1314 2520 输出 12
#includeiostream
using namespace std;int shine(char * source)
{if(*source0){return 0;}return ((*source0 *source9)?1:0)shine(source1);
}int main()
{char source[1024]{0};cin.getline(source,1024);coutshine(source)endl;return 0;
}
31、字符串中有多少个字母
输入一字符串求字符串中有多少个字母。
输入We Are Astronaut.Go ahead! 输出21
#includeiostream
using namespace std;int shine(char * source)
{if(*source0){return 0;}int counter((*sourcea *sourcez) || (*sourceA *sourceZ))?1:0;return countershine(source1);
}int main()
{char array[1024]{0};cin.getline(array,1024);coutshine(array);return 0;
}
32、英文语句中每个单词的长度
输入一英文语句按照单词的输入顺序求出每个单词的长度重复的单词算多个单词。
输入Never give up 输出 Never 5 give 4 up 2
#includeiostream
#includecstring
using namespace std;void shine(char * begin);//字符串中每个单词的长度
bool isLetter(char target);//当前字符是否为字母int main()
{char source[1024]{0};while(true){cin.getline(source,1024);if(strcmp(source,exit)0 || strcmp(source,quit)0){break;}shine(source);}return 0;
}void shine(char * begin)//字符串中每个单词的长度
{static int counter0;if(*begin0){return;}if(isLetter(*begin)){cout*begin;counter;}if(isLetter(begin[0]) !isLetter(begin[1])){cout counterendl;counter0;}shine(begin1);
}bool isLetter(char target)//当前字符是否为字母
{return (targetA targetZ)||(targeta targetz);
}33、字符串中最长的单词
输入一英文句子按照单词的输入顺序求出最长的单词以及长度。
输入 exceptional,gorgeous,transcendent and diligent life 输出 transcendent 12
#includeiostream
#includecstring
using namespace std;struct Node
{char * source;short length;Node * next;Node(char * source,short length,Node * next){this-sourcesource;this-lengthlength;this-nextnext;}
};//单链表结点bool isLetter(char target);//判断字符是否为字母
Node * extract(char * source);//将字符串中所有单词、单词长度存储到无表头单链表
void traverse(Node * predecessor);//遍历无表头单链表 仅测试用
Node * getMaximum(Node * predecessor);//取出最长单词所在的结点的指针int main()
{char source[1024]{0};Node * predecessornullptr;Node * resultnullptr;while(true){cin.getline(source,1024);if(strcmp(source,exit)0 || strcmp(source,quit)0){break;}predecessorextract(source);resultgetMaximum(predecessor);for(char * beginresult-source;isLetter(*begin);begin){cout*begin;}cout\tresult-lengthendl;}return 0;
}bool isLetter(char target)
{return (targetA targetZ)||(targeta targetz);
}Node * extract(char * source)
{static short length0;if(*source0){length0;//return nullptr;}if(isLetter(*source))//碰到字母统计一次长度length{length;}if(isLetter(source[0]) !isLetter(source[1])){/*碰到字母,且字母后面不是字母表明一个单词的拼写完成将单词的首字母指针、单词的长度存储进单链表结点中长度length归零对下一个单词的长度进行统计*/Node * pnew Node(source-length1,length,nullptr);length0;Node * successorextract(source1);p-nextsuccessor;//无表头结点的单链表头插法return p;} //这里的非字母字符没有进行处理return extract(source1);
}void traverse(Node * predecessor)
{if(predecessornullptr){return;}for(char * chpredecessor-source;isLetter(*ch);ch){cout*ch;}coutendl;traverse(predecessor-next);
}Node * getMaximum(Node * predecessor)
{if(predecessor-nextnullptr){return predecessor;}Node * successorgetMaximum(predecessor-next);return predecessor-lengthsuccessor-length?predecessor:successor;
}34、翻转字符串
输入一字符串按照原有顺序逆序输出。 输入 31 U evoL I 输出 I Love U 13
首尾交换(再三斟酌)
#includeiostream
#includecstring
using namespace std;int lengthOfString(char * source);//求字符串长度
void reverse(char * source);//反转字符串int main()
{char source[1024]{0};int lengthsizeof(source)/sizeof(char);while(true){cin.getline(source,length);if(strcmp(source,quit)0 || strcmp(source,exit)0){break;}reverse(source);coutsourceendl;}return 0;
}
int lengthOfString(char * source)//求字符串长度
{if(*source0){return 0;}return 1lengthOfString(source1);
}void reverse(char * source)//反转字符串
{if(lengthOfString(source)1 || lengthOfString(source)0){return;}int lengthlengthOfString(source);char temporarysource[length-1];source[length-1]\0;reverse(source1);/*将尾字符置为\0整型变量length在下一次递归中就会少一个1指针变量source的累加整型变量length在下一次递归中就会再少一个1length越来越小直至length1(字符串长度为奇数)或length0字符串长度为偶数看着有点复杂其实是首尾交换*/source[length-1]source[0];source[0]temporary;
}逆序赋值法(再三斟酌)
将数组每个元素中的值依次读取并一字排开再将数组每个元素的指针反向一字排开最后把值重新赋给对应的元素。
#includeiostream
#includecstring
using namespace std;void reverse(char * source);//反转字符串
void reverse0(char * source,short begin,short end);//反转字符串的核心int main()
{char source[1024]{0};while(true){cinsource;if(strcmp(source,exit)0 || strcmp(source,quit)0){break;}reverse(source);coutsourceendl;}return 0;
}
void reverse(char * source)//反转字符串
{if(strlen(source)1){return;}int lengthstrlen(source);reverse0(source,0,length-1);
}
void reverse0(char * source,short begin,short end)//反转字符串的核心
{
/* 没有数组首尾元素之间的交换直接将数组指针倒转把字符存储在指针所指向的数组元素中beginend分别是所要操作的数组元素的首尾下标给begin、end传递参数时要注意beginend,begin0endstrlen(source)positionend-begin的计算由来假充需要操作的数组元素下标为01234567则begin0end7变量begin在递归过程中是不断累加的变量end递归过程中是不变的0号元素存储到7号元素中positionend-begin7-071号元素存储到6号元素中positionend-begin7-162号元素存储到5号元素中positionend-begin7-253号元素存储到4号元素中positionend-begin7-344号元素存储到3号元素中positionend-begin7-435号元素存储到2号元素中positionend-begin7-526号元素存储到1号元素中positionend-begin7-617号元素存储到0号元素中, positionend-begin7-70故positionend-begin
*/if(beginend){return;}int positionend-begin;//当前字符将要存储的数组空间下标char tempsource[begin];//存储当前字符reverse0(source,begin1,end);source[position]temp;//回归时将当前字符存储到指定的数组空间中
}
35、翻转字符串中的单词1
输入一字符串字符串由若干个单词、空格组成按照单词在字符串中的原有顺序逆序输出单词与单词之间用空格隔开。 输入Fire My Are You 输出You Are My Fire
注在本题中使用了带表头单链表先将每个单词的首字节指针存储在结点的数据域中再逆序遍历单链表即完成要求。
#includeiostream
#includecstring
using namespace std;struct Node
{char * source;Node * next;Node(char * source,Node * next):source(source),next(next){}
};bool isLetter(char target);//判断字符是否为字母
Node * extract(char * source);//将字符串中的单词提取出来形成带表头单链表
void traverseReversely(Node * head);//逆序遍历带表头单链表
void traverse(char * source);//遍历字符串中的单词单词的结束符为空格或\0
void destroy(Node * head);//销毁带表头单链表
int main()
{char source[1024]{0};while(true){cin.getline(source,1024);//不能写成 cinsourceif(strcmp(source,exit)0 || strcmp(source,quit)0){break;}Node * headextract(source);traverseReversely(head);destroy(head);}return 0;
}Node * extract(char * source)//将字符串中的单词提取出来形成带表头单链表
{static int length0;if(*source\0){//到达递归最后一层length0;//静态变量length在递归最后一层必须归零以便在程序运行过程中保证数据的正确性Node * headnew Node(nullptr,nullptr);//生成表头结点return head;//返回表头结点指针}if(isLetter(*source)){length;}if(isLetter(*source) (source[1] || source[1]\0)){//完成一个单词的拼写Node * pnew Node(source-length1,nullptr);//创建单链表结点将单词所在空间的首字节指针存储其中length0;//为计算下一个单词的长度单词的长度length归零Node * headextract(source1);//返回表头结点指针p-nexthead-next;//单链表头插法head-nextp;//单链表头插法return head;}return extract(source1);
}void traverseReversely(Node * head)//逆序遍历带表头单链表
{if(head-nextnullptr) {//递归最后一层每个结点的数据都由其前驱结点进行处理所以尾结点自然成为递归边界return;}traverseReversely(head-next);traverse(head-next-source);/*for(char * sourcehead-next-source;*source! *source!\0;source){cout*source;}*/if(head-source!nullptr)//回归时遇到数据结点{cout ;}else//回归到表头结点{coutendl;}
}void traverse(char * source)//遍历字符串字符串的结束符为空格或\0
{if(*source || *source\0){return;}cout*source;traverse(source1);
}bool isLetter(char target)//判断字符是否为字母
{return (targeta targetz) || (targetA targetZ);
}void destroy(Node * head)//销毁带表头单链表
{if(headnullptr){return;}destroy(head-next);delete head;
}36、翻转字符串中的单词2
输入一字符串字符串由若干个单词、空格、逗号、句号等等字符组成按照单词在字符串中的原有顺序逆序输出每输出一个单词进行一次换行。 输入 Hello,I am Hannah. 输出 Hannah am I Hello
指针版
#includeiostream
#includecstring
using namespace std;void extract(char * source);//找出字符串中所有的单词并以原有顺序逆序输出
bool isLetter(char target);//判断字符是否为字母
void traverse(char * source);//遍历单词结束条件为遇到非字母字符
int main()
{char source[1024]{0};while(true){cin.getline(source,1024);if(strcmp(source,exit)0 || strcmp(source,quit)0){break;}extract(source);}return 0;
}void extract(char * source)
{static int length0; //计算单词长度的变量if(*source\0)//递归结束条件{length0;return;}if(isLetter(*source)){length;}if(isLetter(source[0]) !isLetter(source[1]))//一个单词拼写完毕{char * beginsource-length1;//单词的起始指针length0;//计算单词长度的变量length清零以便计算下一个单词的长度extract(source1);traverse(begin);//回归时再遍历单词return;//这个return不能少否则会导致递归方向错误}extract(source1);
}bool isLetter(char target)
{return (targeta targetz) || (targetA targetZ);
}void traverse(char * source)//遍历单词结束条件为遇到非字母字符
{if(!isLetter(*source)){coutendl;return;}cout*source;traverse(source1);
}单链表版
#include iostream
#includecstring
using namespace std;struct Node
{char * begin;Node * next;Node(char * begin,Node * next):begin(begin),next(next){}
};Node * extract(char * source);//将所有的单词的首字母指针存储在带表头的单链表中返回表头结点指针
bool isLetter(char target);//判断字符是否为字母
void traverseLinkedList(Node * head);//遍历带表头单链表
void traverseString(char * source);//遍历单词结束条件为遇到非字母字符
int main()
{char source[1024]{0};Node * head;while(true){cin.getline(source,1024);if(strcmp(source,exit)0 || strcmp(source,quit)0){break;}headextract(source);traverseLinkedList(head);}return 0;
}Node * extract(char * source)
{static int length0; //计算单词长度的变量if(*source\0)//递归结束条件{length0;Node * headnew Node(nullptr,nullptr);return head;}if(isLetter(*source)){length;}if(isLetter(source[0]) !isLetter(source[1]))//一个单词拼写完毕{Node * pnew Node(source-length1,nullptr);//把单词首字母指针存储在结点中length0;//计算单词长度的变量length清零以便计算下一个单词的长度Node * headextract(source1);p-nexthead-next;//带表头单链表头插法head-nextp;//带表头单链表头插法return head;}return extract(source1);
}bool isLetter(char target)//判断字符是否为字母
{return (targeta targetz) || (targetA targetZ);
}void traverseLinkedList(Node * head)//遍历带表头单链表
{if(head-nextnullptr)//尾结点的数据由其前驱结点进行输出所以到达尾结点时递归结束{//递归最后一层return;}traverseLinkedList(head-next);traverseString(head-next-begin);
}void traverseString(char * source)//遍历单词
{if(!isLetter(*source))//遇到非字母字符到达递归边界{coutendl;return;}cout*source;traverseString(source1);
}37、删除字符串中的字符
输入任意字符串再给定一个字符将该字符从字符串中移除最后将处理后的字符串输出。 输入 U9Are9My9Love 9 输出 UAreMyLove
静态变量完成递归操作
#includeiostream
using namespace std;void remove(char * source,char target);//删除字符串所有的target字符int main()
{char source[1024]{0};char target;while(true){cin.getline(source,1024);cin.get(target);remove(source,target);coutsourceendl;cin.get();//接收上一行的回车符}return 0;
}void remove(char * source,char target)//删除字符串所有的target字符
{static char * beginsource;if(*source\0){*begin*source;beginnullptr;//将begin置空便于在程序运行过程中对该函数的再次调用return;}if(beginnullptr){beginsource;}if(*source!target){*begin*source;begin;}remove(source1,target);
}添加函数、形式参数完成递归操作
#includeiostream
using namespace std;void remove(char * source,char target);//删除字符串所有的target字符
void remove0(char * source,char * destination,char target);//删除字符串所有的target字符int main()
{char source[1024]{0};char target;while(true){cin.getline(source,1024);cin.get(target);remove(source,target);coutsourceendl;cin.get();//接收上一行的回车符}return 0;
}void remove(char * source,char target)//删除字符串所有的target字符
{char * destinationsource;remove0(source,destination,target);
}
void remove0(char * source,char * destination,char target)//删除字符串所有的target字符
{//将一个字符数组当成两个字符数组来处理if(*source\0){//递归最后一层*destination*source;return;}if(*source!target){*destination*source;remove0(source1,destination1,target);}else{remove0(source1,destination,target);}
}38、字符串中的数1
任意输入一个字符串其中有整数(0)、其它字符。从字符串中筛选出整数并依次输出每输出一个整数进行一次换行。 如字符串”How1319Gorgeous2520!1015”中的整数有1319、2520、1015
输入 How1319Gorgeous2520!1015
输出 1319 2520 1015
#includeiostream
using namespace std;bool isNumber(char target);//判断字符是否为数字
void extract(char * begin);//筛选出字符串中的整数(0)int main()
{char * beginnew char[1024];cin.getline(begin,1024);extract(begin);return 0;
}void extract(char * begin)//筛选出字符串中的整数(0)
{if(*begin0){return;}if(isNumber(*begin)){cout*begin;}if(isNumber(*begin) !isNumber(*(begin1))){coutendl;}extract(begin1);
}bool isNumber(char target)//判断字符是否为数字
{return target0 target9;
}39、字符串中的数2
任意输入一个字符串其中有整数(0n123456789)、其它字符。从字符串中筛选出整数并依次输出两两之间用加号隔开。再将这些整数求和输出结果。
输入 How1319Gorgeous2520!60
输出 1319252060 3899
输入 You1Are9The10Champion500
输出 1910500 520
#includeiostream
#includecstring
using namespace std;struct Node
{int data;Node * next;Node(int data,Node * nextnullptr):data(data),next(next){}
};//单链表结点Node * extract(char * source);//提取字符串中的整数并将其存储到带表头单链表返回表头结点指针
bool isDigit(char target);//判断字符是否为数字
int traverseAndSummate(Node * head);//遍历单链表并求和,返回求和结果
int main()
{char source[1024]{0};while(true){cin.getline(source,1024);if(strcmp(source,0)0){break;}Node * headextract(source);traverseAndSummate(head);}return 0;
}Node * extract(char * source)
{static int integer0;//存储整数if(*source\0){integer0;//将integer置为0保证函数在程序运行中的数据正确性Node * headnew Node(-1,nullptr);//创建表头结点return head;}if(isDigit(*source))//遇到数字字符将其转换为整数并将其存储到integer中{integerinteger*10*source-0;}if(isDigit(source[0]) !isDigit(source[1])){//遇到数字字符且下一个字符不是数字字符将integer存储到单链表中Node * pnew Node(integer,nullptr);integer0;//将integer置为0为提取下一个整数做准备Node * headextract(source1);p-nexthead-next;//单链表头插法head-nextp;//单链表头插法return head; }return extract(source1);
}int traverseAndSummate(Node * head)//遍历单链表并求和
{if(head-nextnullptr)//到达最后一个结点即递归边界开始回归{return head-data;//返回尾结点的值}if(head-next-next!nullptr)//递归未到达倒数第二个结点{couthead-next-data ;}else//递归到达倒数第二个结点{couthead-next-dataendl;}int sumtraverseAndSummate(head-next);if(head-data!-1){//未回归到第一个结点return sumhead-data;}else{//回归到第一个结点即递归第一层coutsumendl;return sum;}
}bool isDigit(char target)//判断字符是否为数字
{return target0 target9;
}40、字符串中的数3
任意输入一个字符串其中有整数(0n123456789)、其它字符。从字符串中筛选出所有整数输出这些整数升序排序的结果、降序排序的结果。 如字符串“13I’m19Here15The25DawnIs20Coming10”中的整数有13、19、15、25、20、10升序排序后的结果为10、13、15、19、20、25降序排序的结果为25、20、19、15、13、10
注此题目中使用双链表完成此题涉及到的双链表操作有插入排序、正反遍历、销毁链表这些操作都是使用递归完成。
输入 13I’m19Here15The25DawnIs20Coming10 输出 10 13 15 19 20 25 25 20 19 15 13 10
输入 How1319Gorgeous2520!61Happy1925AmI 输出 61 1319 1925 2520 2520 1925 1319 61
输入 What 2090 creature 5010!2025I’m9095 1949shocked.9125 输出 1949 2025 2090 5010 9095 9125 9125 9095 5010 2090 2025 1949
#includeiostream
#includecstring
using namespace std;struct Node
{int data;Node * prior;Node * next;Node(int data,Node * priornullptr,Node * nextnullptr):data(data),prior(prior),next(next){}
};Node * extract(char * source);//从字符串中提取整数并将其存储到带表头双链表中返回双链表表头结点指针
bool isDigit(char target);//判断字符是否为数字字符
void traverse(Node * head);//正向、反向遍历双链表并输出
void insert(Node * head,Node * p);//寻找新结点的插入位置并插入新结点使双链表按升序排列
void destroy(Node * head);//销毁带表头双链表
int main()
{char source[1024]{0};Node * headnullptr;while(true){cin.getline(source,1024);if(strcmp(source,0)0){break;}headextract(source);traverse(head);destroy(head);}return 0;
}Node * extract(char * source)
{static int x0;//用于存储整数if(*source\0)//到达字符串末尾即递归边界{x0;//将x置为0保证函数在程序运行中多次调用下的数据正确性Node * headnew Node(-1,nullptr,nullptr);//创建双链表表头结点return head;}if(isDigit(*source))//遇到数字字符{xx*10*source-0;//将其转换为整数并将其存储到x中}if(isDigit(source[0]) !isDigit(source[1]))//遇到数字字符且下一个字符不是数字字符{Node * pnew Node(x,nullptr,nullptr);//将x存储到双链表结点中x0;//将x置为0为提取下一个整数做准备Node * headextract(source1);if(head-priornullptr head-nextnullptr)//表头结点的前后指针域为空即遇到空双链表{//递归的倒数第二层p-priorhead;//新结点的前指针域指向表头结点p-nexthead-next;//新结点的后指针域置为空(其实表头结点的后指针域在此时也为空)head-nextp;//表头结点的后指针域指向新结点}else{insert(head,p);//寻找新结点的插入位置并插入新结点}return head;//返回表头结点指针}return extract(source1);
}void insert(Node * head,Node * p)//寻找新结点的插入位置并插入新结点使双链表按升序排列
{if(head-datap-data)//找到一个插入位置,该位置位于表头结点之后尾结点之前{p-priorhead-prior;p-nexthead;head-prior-nextp;head-priorp;return;}if(head-nextnullptr)//找到另一个插入位置该位置位于尾结点之后{p-priorhead;p-nexthead-next;head-nextp;return;}/*上面两个if语句的顺序不能颠倒否则会出现错误在表头结点之后尾结点之前没有找到新结点插入的位置才会到尾结点后面追加新结点两个if语句都是递归边界在表头结点之后尾结点之前找到新结点插入的位置时插入新结点终止递归在尾结点之前没有找到新结点插入的位置就在尾结点后面追加新结点终止递归这里把表头结点也当作了一个数据结点进行了排序而表头结点的数据域为-1始终排在第一位不影响排序结果使用到的算法是插入排序*/insert(head-next,p);
}void traverse(Node * head)//正向、反向遍历双链表
{if(headnullptr || head-nextnullptr){return;}head-next-next!nullptr?couthead-next-data :couthead-next-dataendl; traverse(head-next);head-prior!nullptr?couthead-next-data :couthead-next-dataendl;
}bool isDigit(char target)//判断字符是否为数字
{return target0 target9;
}void destroy(Node * head)//销毁带表头双向链表
{if(headnullptr){return;}destroy(head-next);delete head;
}
