当前位置:首页 >> 信息与通信 >>

常用的算法思想2


一、常用的算法思想
1. 穷举法思想
基本概念:穷举法(Exhaustive Attack method),它是一种最为直接, 最容易实现, 同时又最为耗时的一种解决问题的算法思想。 穷举法算 法的基本思想是: 在可能的解空间中穷举出每一种可能的解, 并对每 一个可能解进行判断,从中得到问题的答案。 【实例\_1】寻找[1,100]之间的素数(code\_1.

cpp) #include "stdafx.h" #include "stdio.h" #include <math.h> int Is_Prime(int i){ if (i==1) return 0; if (i==2) return 1; if(i>2 && i%2==0) return 0; int j; int t=0; for(j=3;j<=sqrt(i);j+=2) if(i%j==0) {t=1;return 0;} if(t==0) return 1; } void GetPrime(int low,int high){ /*寻找[low,high]之间的素数*/ int i; for(i=low;i<=high;i++) if(Is_Prime(i)) printf(" %d ",i); printf("\n"); } int main(int argc, char* argv[]) {

int low,high; printf("\n 请输入寻找的上、下区间\n"); scanf("%d %d",&low,&high); printf("\n 列出所有的素数\n"); GetPrime(low,high); getchar(); return 0; } 【实例\_2】TOM 的借书方案:TOM 共有 5 本书,要借给 A、B、 C 3 位同学,每人只能借 1 本书,则 TOM 可以有多少种不同的借书 方案。借书方案的解集: #include "stdafx.h" #include "stdio.h" int main(int argc, char* argv[]) { int i,j,k; printf("\n 示出所有的方案:\n"); for(i=1;i<=5;i++) for(j=1;j<=5;j++) for(k=1;k<=5;k++) if(i!=j &&j!=k&&i!=k) {printf(" (%d,%d,%d) ",i,j,k);} printf("\nHello World!\n"); return 0; }

2. 递归与分治思想
基本概念: 在解决一些比较复杂的问题, 特别是解决一些规模较大的 问题时,常常将问题分解。具体来说,就是将一个规模较大的问题分 割成规模较小的同类问题, 然后将这些小的子问题逐个加以解决, 最 终也就将整个大的问题解决。 递归的思想也是一种常见的算法思想。所谓递归算法,就是一种 直接或间接地调用原算法本身的一种算法。 在实际的算法设计中, 递

归与分治如同一对兄,经常结合在一起使用。这是因为,由分治方法 产生的子问题往往都是原问题的更小规模。 反复使用分治的手段, 可 使子问题与原问题类型一致, 但规模不断缩小, 最终使子问题比较容 易求解。 既然子问题与原问题的类型一致, 这 就具有了所谓的递归, 因此可以使用递归的方法用解决原问题的算法去解决同类的子问题。 【实例_3】计算 n 的阶乘 n ! 其实阶乘的数学定义可以用递归函数来简单地描述:

n?0 ? 1 n! ? ? ?n(n ? 1)! n ? 0
这样的函数称为递归函数, 因为该函数本身直接或间接地调用了该函 数本身。基于阶乘的递归函数的描述。就不难设计出计算出 n ! 的递 归算法 int factorial(n){ if(n==0) return 1; else return n* factorial(n-1) } 【实例_4】将一个正整数 n 表示成一系列的正整数之和:

n ? n1 ? n2 ? ? nk

(n1 ? n2 ? n2 ? 1, k ? 1)

被称做正整数的一个划分,不同的划分的个数称为该正整数 n 的划 分数。 根据正整数划分的定义, 可以总结以下规律: 设标记 P(n,m) 表 示正整数 n 的所有不同划分,最大加数不大于 m 的划分个数,可以 得出计算 P(n,m) 的递归函数式:

1 m ?1 ? ? P(n, n) n?m ? P(n, m) ? ? 1 ? P(n, n ? 1) n?m ? ? n ? m ?1 ? P(n, m? 1) ? P(n ? m, m)
程序如下: #include "stdio.h" int P(int n,int m) { if(m==1 || n == 1) return 1; if(m>n) return P(n,n); if(m==n) return 1+P(n,m-1); return P(n,m-1)+P(n-m,m); }

main() { int n,s; printf("Please input a integer for getting the number of division\n"); scanf("%d",&n); s= P(n,n); /* 输入正整数 n*/ /* 求出正整数 n 的划分数*/

printf("The number of division of %d is %d\n",n,s); getche();

}

【实例_5】递归的折半查找算法 #include "stdio.h" int bin_search(int key[],int low, int high,int k) { int mid; if(low>high) return -1; else{ mid = (low+high) / 2; if(key[mid]==k) return mid; if(k>key[mid]) return bin_search(key,mid+1,high,k); 列的后半部分查找*/ else return bin_search(key,low,mid-1,k); 序列的前半部分查找*/ } } main() { int n , i , addr; int A[10] = {2,3,5,7,8,10,12,15,19,21}; printf("The contents of the Array A[10] are\n"); for(i=0;i<10;i++) printf("%d ",A[i]); 数组 A 中的内容*/ printf("\nPlease input a interger for search\n"); scanf("%d",&n); 查找的元素*/ addr = bin_search(A,0,9,n);

/* 在序

/* 在

/*显示

/* 输入待

if(-1 != addr) /* 查找成功*/ printf("%d is at the %dth unit is array A\n ",n,addr); else printf("There is no %d in array A\n",n); /*查 找失败*/ getche(); } 练习 1:有 1、2、3、4 个数字,能组成多少个互不相同且无重复数 字的三位数?都是多少? 练习 2:一球从 100 米高度自由落下,每次落地后反跳回原高度的一 半;再落下,求它在 第 10 次落地时,共经过多少米?第 10 次反弹 多高? 练习 3:有 5 个人坐在一起,问第五个人多少岁?他说比第 4 个人大 2 岁。问第 4 个人岁数,他说比第 3 个人大 2 岁。问第三个人,又说 比第 2 人大两岁。问第 2 个人,说比第一个人大两岁。最后 问第一 个人,他说是 10 岁。请问第五个人多大?

二、数学趣题
题目 1(三色球问题) :由红、黄、绿三种颜色的球,其中红球 3 个, 黄球 3 个,绿球 6 个。现将这 12 个球混放在一个盒子中,从中任意 摸出 8 个球,编程计算摸出球的各种颜色搭配。 分析:这是一道排列组合的问题。从 12 个球中任意摸出 8 个球,求 颜色搭配的种类。 解决这类问题的一种比较简单直观的方法是应用穷 举法, 在可能的解空间中找出所有的搭配, 然后再根据约束条件加以 排除,最终筛选出正确的答案。 #include "stdio.h" /*三色球问题求解*/

main() { int red,yellow,green; printf("red yellow green\n"); for(red=0;red<=3;red++) /*红色:0,1,2,3*/ for(yellow=0;yellow<=3;yellow++) /*黄色:0,1,2,3*/ for(green=2;green<=6;green++)/*绿色:2,3,4,5,6*/ if(red+yellow+green == 8) printf("%d %d %d\n",red,yellow,green); } 题目 2(百钱买百鸡问题) :我国古代数学家张丘建在《算经》一书 中曾提出过著名的“百钱买百鸡”问题。该问题叙述如下:鸡翁一, 值钱五;鸡母一,值钱三;鸡雏三,值钱一;百钱买百鸡,则翁、母、 雏各几何?请编写 C 程序,解决“百钱买百鸡”问题。 #include <string.h> #include <stdio.h> int accord(int i,int j,int k) ; void main() { int i,j,k; printf("The possible plans for buying 100 fowls with 100 yuan are:\n\n"); for(i=0;i<=100;i++) for(j=0;j<=100;j++) for(k=0;k<=100;k++) if(accord(i,j,k)) printf("cock=%d,hen=%d,chicken=%d\n",i,j,k); getchar(); } int accord(int i,int j,int k) { if(5*i+3*j+k/3==100&&k%3==0&&i+j+k==100)

/*显然 k

必为 3 的整数倍*/ return 1; 鸡要求返回 1*/ else

/*符合百千百

return 0; /* 不符合百千 百鸡要求返回 0*/ } 题目 3(爱因斯坦的阶梯问题)爱因斯坦曾出过这样一道有趣的数学 题:有一个长阶梯,若每步上 2 阶,最后剩 1 阶;若每步上 3 阶,最 后剩 2 阶;若每步上 5 阶,最后剩 4 阶;若每步上 6 阶,最后剩 5 阶;只有每步上 7 阶,最后刚好一阶也不剩。请问该阶梯至少有多少 阶。编写一个 C 程序解决该问题。 #include <string.h> #include <stdio.h> void main() { int x=7,i,res,flag=0; for(i=1;i<=100;i++) /*将循环次数定为 100*/ { if((x%2==1)&&(x%3==2)&&(x%5==4)&&(x%6==5) ) /* 如果 x 符合题目叙述的要求*/ { res=x; flag=1; break; /* 跳出循环,不再进行比较*/ } x=7*(i+1); } if(1==flag) printf("The result of Einstein's question is %d",res); /* 输 出答案*/ else printf("In this rage cannot get result\n "); /* 在程序限定的范围内找不到答案*/

} 题目 4(寻找水仙花数) :如果一个 3 位数等于其各位数字的立方和, 则称这个数为水仙花数。例如:407=43+03+73,因此 407 就是一个水 仙花数。编写一个程序,找出全部的水仙花数。 分析: 水仙花数是三位数, 只要应用穷举法穷举出 100~999 闭区间中的每一 个数字(正整数) ,然后对每一个正整数进行判断,看它是不是水仙 花数,如果是水仙花数,则将该数输出,如果不是水仙花数,则不输 出该数。 int IsNarcissus(int a); void Narcissus(); void main() { printf("The Narcissus numbers below are\n"); Narcissus(); getche(); } void Narcissus() { /*寻找 100-999 之间的水仙花数*/ int i; for(i=100;i<=999;i++) if(IsNarcissus(i)) printf("%d ",i); } int IsNarcissus(int a) { /*判断是否是水仙花数,是则返回 1,不是返回 0*/ int sum=0,tmp; tmp=a; while(tmp>0) { sum=sum+(tmp%10)* (tmp%10)*(tmp%10); tmp=tmp/10; } if(sum==a) return 1; /*a 是水仙花数*/

else return 0; /* a 不是水仙花数*/ } 题目 5(猴子吃桃问题)有一只猴子第一天摘下若干个桃子,当即吃 掉了一半,又多吃了一个;第二天又将剩下的桃子吃掉一半,又多吃 一个; 按照这样的吃法每天都吃前一天剩下的桃子的一半又一个。 到 了第十天,就只剩下一个桃子。问题:这只猴子第一天摘了多少个桃 子。 #include"stdio.h" main() { int sum = 1,i; /*sum 初始值为 1,表示第十天的桃子数*/ for(i=9;i>=1;i--) sum = (sum + 1) * 2 ; /*每次循环都得出第 i 天的桃子数*/ printf("The number of peach are %d\n",sum); getche(); } 题目 6 (兔子产仔问题) 13 世纪意大利数学家斐波那契他的 《算盘书》 中提出这样一个问题:有人想知道一年内一对兔子可繁殖成多少对, 便筑了一道围墙把一对新生的兔子关在里面。 已知一对两个月大的兔 子以后每一个月都可以生一对小兔子, 而一对新生的兔子出生两个月 后才可以生小兔子(例如:1 月份出生,3 月份才可产仔) 。假如一年 内没有发生死亡,则一年内共能繁殖成多少对? #include "stdio.h" Fibonacci(n){ /*递归函数*/ if (n==1 || n==2) return 1; else return Fibonacci(n-1) + Fibonacci(n-2);/* 递 归 调 用 函 数 Fibonacci */ } main() { printf("There are %d pairs of rabbits 1 year later",Fibonacci(12)); getche(); }

题目 7(常胜将军)现有 21 根火柴,两人轮流取,每人每次可以取 走 1 至 4 根,不可多取,也不能不取,谁取最后一楰火柴谁输。请编 写一个程序进行人机对弈,要求人先取,计算机后取;计算机一方为 “常胜将军” 。 #include "stdio.h" main() { int computer , people , spare = 21; printf(" -----------------------------------------\n"); printf(" -------- 你不能战胜我,不信试试 --------\n"); printf(" -----------------------------------------\n\n"); printf("Game begin:\n\n"); while(1) { printf(" ---------目 前 还 有 火 柴 %d 根 ----------\n",spare); printf("People:") ; scanf("%d",&people); if(people<1 || people>4 || people>spare) {printf("你违规了,你取的火柴数有问题!\n\n");continue;} spare = spare - people; if(spare == 0){printf("\nComputer win! Game Over!\n"); break;} computer = 5 - people; spare = spare - computer; printf("Computer:%d \n",computer); if(spare == 0){printf("\nPeople win! Game Over!\n"); break;} } }

练习 1(分解质因数) :根据数论的知识可知任何一个合数都可以写 成几个质数相乘的形式, 这几个质数都叫做这个合数的质因数。 例如 24=2*2*2*3。把一个合数写成几个质数相乘的形式表示,叫做分解

质因数。对于一个质数,它的质因数可定义为它本身。编写一个程序 实现分解质因数。 (5.13) 练习 2(最大公约数和最小公倍数) :编写一个程序计算两个正整数 的最大公约数和最小公倍数。 (5.2) 练习 3(谁在说谎) :三个嫌疑犯在法官面前各执一词,甲说:乙在 说谎;乙说:丙在说谎;丙说:甲乙两人都在说谎。法官为了难,甲 乙丙三人到底谁在说谎,谁说的是真话?编写一个程序实现。 (5.23) 题目 8(连续整数固定和问题)编写一个程序,找出一个数的全部的 连续整数固定和。所谓一个数 n 的连续整数固定和,就是指存在 a1,a2,…,an,其中 ai+1 比 ai 大 1,使得 a1+a2+…+an=n。这样 a1,a2,…,an 称为 n 的一个连续整数固定和。例如 27 的全部的连续整数固定和有 3 组:2+3+…+7=27;8+9+10=27;13+14=27。本题就是要找出任意 输入的整数 n 的全部的连续整数固定和。 #include "stdio.h" void cntnsIntSum(int n) { int i,sum=0,j; for(i=1;i<n;i++) { j = i-1; while(sum<n) { j++; sum = sum + j; } if(sum == n) { printf("%d+...+%d = %d\n",i,j,n); } sum = 0; } } main()

{ int n; printf("Please input a integer\n"); scanf("%d",&n); cntnsIntSum(n); getchar(); } 题目 9(具有特殊性质的数)有这样一个 4 位数 abcd,它具有这样的 2 性质 abcd ? ? ab ? cd ? , 其中 ab 和 cd 为两个 2 位数, 求这个 4 位数 abcd。 #include "stdio.h" void func() { int a,b,c,d; for(a=1;a<=9;a++) for(b=0;b<=9;b++) for(c=0;c<=9;c++) for(d=0;d<=9;d++) { if(a*1000+b*100+c*10+d == ((a*10+b) +(c*10+d))* ((a*10+b) +(c*10+d))) printf("%d%d%d%d\t",a,b,c,d); } } main() { printf("There are following numbers according with the condition\n"); func(); getche(); } 题目 10(验证角谷猜想) 角谷猜想的内容为:任意给定一个自然数,若它为偶数则除以 2,若

它为奇数则乘 3 加 1,得到一个新的自然数,按照这样的计算方法计 算下去,若干次后得到的结果必然为 1。编写程序对角谷猜想的正确 性加以验证。 #include "stdio.h" proveJiaoGu(int n) { int count=1; while(n!=1 && count<=1000){ /*阈值设为 1000*/ if(n%2==0) /*n 为偶数*/ { printf("%d/2=%d\n",n,n/2); n = n/2; } else { printf("%d*3+1=%d\n",n,n*3+1); /*n 为奇数*/ n=n*3+1; } count++; } if(count<1000 && n==1) printf("This natural number is according to JiaoGu Guess\n"); } main() { int n; printf("Please input a number to verify\n"); scanf("%d",&n); printf("-------- Step of Verification---------\n");

proveJiaoGu(n); getchar(); } 题目 11(验证四方定理) 四方定理是数论中的重要定理, 它可以叙述为: 所有自然数至多只要 4 个数的平方和就可以表示,编写一个程序验证四方定理。 #include "stdio.h" #include "math.h" int mode_1(N) /*判断自然数 N 是否可以表示成为 N=a2 的 形式*/ { if((int)sqrt(N)*(int)sqrt(N)==N) { printf("%d*%d=%d\n",(int)sqrt(N),(int)sqrt(N),N); return 1; } else return 0; } int mode_2(N) /*判断自然数 N 是否可以表示成 N=a2+b2 的 形式*/ { int x,y; for(x=1;x<sqrt(N);x++) for(y=x;y<sqrt(N);y++) { if(x*x+y*y == N) { printf("%d^2+%d^2=%d\n",x,y,N); return 1; } } return 0;

} int mode_3(N) /* 判 断 自 然 数 N 是 否 可 以 表 示 成 N=a2+b2+c2 的形式*/ { int x,y,z; for(x=1;x<sqrt(N);x++) for(y=x;y<sqrt(N);y++) for(z=y;z<sqrt(N);z++) { if(x*x+y*y+z*z == N) { printf("%d^2+%d^2+%d^2=%d\n",x,y,z,N); return 1; } } return 0; } int mode_4(N) /* 判 断 自 然 数 N 是 否 可 以 表 示 成 N=a2+b2+c2+d2 的形式*/ { int x,y,z,t; for(x=1;x<sqrt(N);x++) for(y=x;y<sqrt(N);y++) for(z=y;z<sqrt(N);z++) for(t=z;t<sqrt(N);t++) { if(x*x+y*y+z*z+t*t == N) { printf("%d^2+%d^2+%d^2+%d^2=%d\n",x,y,z,t,N); return 1; } }

return 0; } void proveFourSquares(int N) { if(mode_1(N)) printf("It has verified Four Squares"); else if(mode_2(N)) printf("It has verified Four Squares"); else if(mode_3(N)) printf("It has verified Four Squares"); else if(mode_4(N)) printf("It has verified Four Squares"); } main() { int N; printf("Please input a natural number\n"); scanf("%d",&N); printf("-------- Step of Verification---------\n"); proveFourSquares(N); //getche(); } 题目 12(递归法寻找最小值) 编写一个程序, 要求从一个整数序列中找出最小的元素, 并用递归的 方法实现。 题目分析: 在一个整数序列中找出最小值, 最常用的方法是扫描整个序列, 记录 下最小的元素并返回。 但是这里要求用递归的方法实现, 因此必须构 造这个问题递归解。 #include "stdio.h" int getMin(int array[],int n) {

int val1,val2,val3; if(n == 1) return array[0]; if(n%2 == 0) { val1 = getMin(array, n/2); val2 = getMin(array+n/2, n/2); if(val1<val2) return val1; else return val2; } if(n%2 != 0) { val1 = getMin(array, n/2); val2 = getMin(array+n/2+1,n/2); val3 = array[n/2]; if(val1<val2) { if(val1<val3) return val1; else return val3; } else { if(val2<val3) return val2; else return val3; } } } main() { int array[9]={11,13,23,56,8,23,11,23,111},val; /* 测 试的数组,其中元素 8 为最小值*/ val = getMin(array,9); /* 调 用 递 归 函 数 getMin 获得最小值*/ printf("%d",val);

printf("The minum element of this array is %d \n",val); } 题目 13(寻找同构数) 正整数 n 若是它平方数的尾部,则称 n 为同构数。例如,6 是其平方 数 36 的尾部, 76 是其平方数 5776 的尾部, 因此 6 与 76 都是同构数。 编写一个程序,找出 1000 以内的同构数。 题目分析: 本题最直观的解法是使用穷举法,在 1~1000 的正整数中进行搜索, 判断每一个数是否是同构数, 如果是则将其输出, 如果不是则跳过此 数,继续向下寻找,直到判断完这 999 个数为止 #include "stdio.h" int func(int i) { int j; for(j=10;j<1000;j=j*10) { if(i/j == 0) break; } if((i*i)%j == i) return 1; else return 0; } void gettonggou() { int i; for(i=1;i<=1000;i++) { if(func(i)) printf("%d ",i); } } main()

{ printf("The Tonggoushu bellow 1000 are\n"); gettonggou(); printf("\n"); } 题目 14(验证尼科彻斯定理) 尼科彻斯定理可以叙述为: 任何一个整数的立方都可以表示成一串连 续奇数的和。这里要注意,这些奇数一定是要连续的,例如 1,3,5, 7,9…。 题目分析: 要验证尼科彻斯定理的正确性,实质上就是要对任意输入的整数 N, 找出一串连续的奇数,使得这串连续的奇数的和等于 N3。因此本题 可以换一种叙述的方式: 对任意输入的整数 N, 找出一串连续的奇数 i, i+2, i+4, … , i+2n,使得,其中 n 是未知量。 因为这里要求奇数序列是连续的, 所以可以采用设定奇数序列起点的 办法扫描奇数空间,找出符合要求的一串奇数序列。 #include "stdio.h" void Nicoqish(int N) { int i,j,sum = 0; for(i=1;i<N*N*N;i=i+2) /*i 为起点*/ for(j=i;j<N*N*N;j=j+2) /*j 控制从 i 向后顺次累加*/ { sum = sum + j; if(sum == N*N*N) { printf("%d=%d+%d...+%d\n",N*N*N,i,i+2,j); return; } if(sum>N*N*N) { sum = 0; break; } }

} main() { int N; printf("Please input a integer to verify Nicoqish Law\n"); scanf("%d",&N); Nicoqish(N); getche(); } 练习 1(渔夫捕鱼问题) : A、B、C、D、E 五渔夫夜间合伙捕鱼,凌晨时都疲倦不堪,各自在 河边的树丛中找地方睡着了。待日上三竿,渔夫 A 第一个醒来,他 将鱼分作五份,把多余的一条扔回河中,拿自己的一份回家去了。渔 夫 B 第二个醒来,也将鱼分作五份,扔掉多余的一条,拿走自己的 一份,接着 C、D、E 依次醒来,也都按同样的办法分鱼,问五渔夫 至少合伙捕了多少条鱼?试编程序算出。 练习 2(渔夫捕鱼问题) : A、B、C、D、E 五渔夫夜间合伙捕鱼,凌晨时都疲倦不堪,各自在 河边的树丛中找地方睡着了。待日上三竿,渔夫 A 第一个醒来,他 将鱼分作五份,把多余的一条扔回河中,拿自己的一份回家去了。渔 夫 B 第二个醒来,也将鱼分作五份,扔掉多余的一条,拿走自己的 一份,接着 C、D、E 依次醒来,也都按同样的办法分鱼,问五渔夫 至少合伙捕了多少条鱼?试编程序算出。 练习 3(递归法求幂) : 请编写一个递归算法,计算 mn。 一般情况下计算 mn 时多采用循环连乘的方法, 即把 m 连乘 n 次。 这 种方法的效率是很低的。 现在介绍一种更为有效的算法来计算整数的 幂——递归法。

三、数据结构趣题
题目 14(顺序表的就地逆置) 编写一个函数, 实现顺序表的就地逆置, 也就是说利用原表的存储空 间将顺序表(a1,a2,…an)逆置为(an,an-1,…a1)。 本题主要考查顺序表线性

结构的应用。顺序表的基本操作包括顺序表的创建,插入数据,删除 数据等。 但是在实际的应用中, 对顺序表的操作并不仅限于上述这几 种操作。因此学习顺序表也不能仅限于学懂前面所讲的几种操作而 已,应当灵活掌握顺序表结构,并能够熟练地操纵顺序表。 #include "stdio.h" # define MAXSIZE 100 typedef struct{ int * base; int length; }sqlist ; reverseSQ(sqlist *l){ int low = 0 , high = l->length - 1; int buf , i; for(i=0;i<l->length/2;i++) { buf = l->base[low] ; l->base[low] = l->base[high]; l->base[high] = buf; low++; high--; } } main() { sqlist l; int a , i = 0; /*创建一个顺序表*/ l.base = (int *)malloc(sizeof(int)*MAXSIZE); l.length = 0; /*输入数据*/ printf("Please input below 10 integer into the sqlist\n") ; printf("Type -1 for stopping input\n"); scanf("%d",&a);

while(a != -999 && i< MAXSIZE) { l.base[i] = a; l.length++; i++; scanf("%d",&a); } /*输出原顺序表中的数据*/ printf("The contents of the sqlist are\n"); for(i=0;i<l.length;i++) printf("%d ",l.base[i]); printf("\n"); reverseSQ(&l); /*就地逆置顺序表*/

/*输出逆置后的顺序表中的数据*/ printf("The contents of the reversed sqlist are\n"); for(i=0;i<l.length;i++) printf("%d ",l.base[i]); getche(); } 题目 15(动态数列排序) 编写一个 C 程序,实现这样的功能:从键盘输入任意个整数,以 0 作为结束标志, 对这个整数序列从小到大排序, 并输出排序后的结果。 要实现动态数列排序首先要选择好数据的存储结构。如果采取静 态的线性存储结构, 例如数组, 静态顺序表等就无法实现动态数列排 序的功能。因为静态线性存储结构的内存空间开辟在内存的静态区, 它是在程序编译时就分配好了的, 因此无法在程序运行时改变空间的 大小, 也就无法实现动态数列排序的功能。 因此可以选择动态的顺序 表或者链表作为数据的存储结构。 /******************************************Dynamic Sort*************************************************/ #include <string.h>

#include <stdio.h> #include <malloc.h> /*定义 int 为 ElemType 类型*/ typedef int ElemType; /*定义链表的结点类型*/ typedef struct node{ ElemType data; /*数据域*/ struct node *next; /*指针域*/ }LNode,*LinkList; /*创建一个长度为 n 的链表,并输入数据*/ LinkList GreatLinkList(int n){ LinkList p,r,list=NULL; ElemType e; int i; for(i=1;i<=n;i++){ scanf("%d",&e); p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=NULL; if(!list) list=p; else r->next=p; r=p; } return list; } /*向链表中插入结点*/ void insertList(LinkList list,LinkList q,ElemType e){ LinkList p; p=( LinkList)malloc(sizeof(LNode)); p->data=e;

if(!list){ list=p; p->next=NULL; } else{ p->next=q->next; q->next=p; } }

/*基于链表的冒泡排序算法*/ void Sort(LinkList q) { LNode *p=q; int t,i,j,k=0; while(p) {k++; p=p->next;} p=q; for(i=0;i<k-1;i++) { for(j=0;j<k-i-1;j++) { if(p->data>p->next->data) { t=p->data; p->data=p->next->data; p->next->data=t; } p=p->next; } p=q; } }

/*打印出排序后的新链表中的内容*/ void Print(LinkList q) { while(q) { printf("%d ",q->data); q=q->next; } } /*主函数*/ main() { ElemType e; LinkList l,q; /*定义一个链表 l*/ printf("Please input some integer digit and type -999 for end\n"); q=l=GreatLinkList(1); /*创建一个链表结点,q 和 l 指向该结点 */ scanf("%d",&e); while(e!=-999) /*循环地输入数据,同时插入新生 成的结点*/ { insertList(l,q,e) ; q=q->next; scanf("%d",&e); } Sort(l); Print(l); getchar(); } 题目 16(约瑟夫环) 编号为 1,2,3…,n 的 n 个人按顺时针方向围坐一圈,每个人手中 持有一个密码。开始时任选一个正整数作为报数的上限 m,从第一 个人开始按顺时针方向自 1 开始顺序报数,报到 m 停止。报 m 的人 出列,将他的手中的密码作为新的报数上限 m,从他在顺时针方向

上的下一个人开始重新从 1 报数, 如此循环报数下去, 求最后剩下的 那个人的最初编号是多少。

#include "stdio.h" /*链表结点定义*/ typedef struct node{ int number; /*编号*/ int psw; /*个人密码*/ struct node *next; } LNode,*LinkList;

void insertList(LinkList list,LinkList q,int e1,int e2){ LinkList p; p=( LinkList)malloc(sizeof(LNode)); p->number = e1; p->psw = e2; if(!list){ list=p; p->next=NULL; } else{ p->next=q->next; q->next=p; }

}

CreatJoseph(LinkList jsp , int n) { LinkList q = NULL , list = NULL; int i , e2; printf("Please input the password for people in the Joseph circle\n"); for(i=0;i<n;i++){ scanf("%d",&e2); insertList(list,q,i+1,e2); /*向 q 指向的结点后面插入新的结 点*/ if(i == 0) q = list; /*第一次之生成头结点, q 也指向头结点 */ else q = q->next; /*q 指向下一结点*/ } q->next = list; /*形成循环链表*/ jsp = list; //返回 }

exJoseph(LinkList jsp, int m) { LinkList p ,q; int i; q = p = jsp ; while(q->next != p) q=q->next; /*q 指向 p 的前一个结点*/ printf("The order of a column is\n") ; while(p->next != p){ for(i=0;i<m-1;i++) { /*p 指向要删除的结点,q 指向 p 的前一个 结点*/

q = p; p = p->next; } q->next = p->next; printf("%d ",p->number); m = p->psw; free(p); p = q->next; } printf("\nThe last person in the circle is %d\n",p->number); 印出最后留在队中的人的编号*/ }

/*打

main() { LinkList jsp; int n , m; printf("Please input number of the people in the Joseph circle\n"); scanf("%d",&n) ; CreatJoseph(jsp, n); printf("Please input the first maximum number\n"); scanf("%d",&m) ; exJoseph(jsp,m) ; getche(); }

练习 1(约瑟夫环问题) :用顺序表实现 题目 17(二进制/八进制转换器) 编写一个程序,要求从终端输入一串 0/1 表示的二进制数,输出它的 八进制表示形式。

#include "stdio.h" #include "math.h" #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef char ElemType; typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; void initStack(sqStack *s) { /*内存中开辟一段连续空间作为栈空间, 首地址赋值给 s->base*/ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); /*分配空间失败*/ s->top = s->base; /*最开始,栈顶就是栈底*/ s->stacksize = STACK_INIT_SIZE; /* 最 大 容 量 为 STACK_INIT_SIZE */ } void Push(sqStack *s, ElemType e){ if(s->top - s->base >= s->stacksize){

/*栈满,追加空间*/ s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT)*sizeof(ElemType)); if(!s->base) exit(0); /*存储分配失败*/ s->top = s->base + s->stacksize; s->stacksize = s->stacksize + STACKINCREMENT; /*设置栈的最 大容量*/ } *(s->top) = e; /*放入数据*/ s->top++; } void Pop(sqStack *s , ElemType *e){ if(s->top == s->base) return; *e = *--(s->top); } int StackLen(sqStack s){ return (s.top - s.base) ; } main() { ElemType c; sqStack s1; sqStack s2; int len,i,j,sum = 0; initStack(&s1); /*创建一个栈 s1,用来存放二进制字符串*/ printf("Please input a binary number and type '#' for end\n"); /*输入 0/1 字符表示的二进制数,以#结束*/ scanf("%c",&c); while(c!='#') { if(c=='0' || c=='1') Push(&s1,c);

scanf("%c",&c); } initStack(&s2); /*创建一个栈 s2,用来存放八进制字符串*/ len = StackLen(s1); /*得到栈中的元素个数,即二进制数的长度 */ for(i=0;i<len;i=i+3){ for(j=0;j<3;j++){ Pop(&s1,&c); /*取出栈顶元素*/ sum = sum + (c-48) * pow(2,j); /*转换为八进制数*/ if(s1.base == s1.top) break; } Push(&s2,sum+48) ; /*将八进制数以字符形式压入栈 中*/ sum = 0; } printf("The Octal form is \n") ; while(s2.base != s2.top ){ /*输出八进制栈的内容*/ Pop(&s2,&c); printf("%c",c); } getchar(); } 题目 18(回文字符串的判定) 有一种字符序列正读和反读都相同,这种字符序列被称为“回文” 。 例如: “abba”就是回文。编写一个程序,从键盘输入一个任意长度 的字符串,以@作为结束标志,判断该字符串是否是回文。

#include "stdio.h" #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10

typedef char ElemType; typedef struct QNode{ ElemType data; struct QNode *next; } QNode , *QueuePtr;

/*将 char 类型定义为 ElemType*/ /*定义队列结点类*/

typedef struct{ /*定义一个链队列*/ QueuePtr front; /*队头指针*/ QueuePtr rear; /*队尾指针*/ }LinkQueue; typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; /*定义一个栈类型*/

initQueue(LinkQueue *q){ /*初始化一个空队列*/ q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)); /*创建一个 头 结 点 , 队 头 队 尾 指 针

指向该结点*/ if( !q->front) exit(0); /*创建头结点失败*/ q->front->next = NULL; /*头结点指针域置 NULL*/ } EnQueue(LinkQueue *q, ElemType e){ /*入队列操作*/ QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); /*创建一个队列元素结点 */ if( !q->front) exit(0); /*创建头结点失败*/ p->data = e; /*将元素 e 入队列*/ p->next = NULL; /*修改队尾指针*/ q->rear ->next = p; q->rear = p; } DeQueue(LinkQueue *q, ElemType *e){ /*如果队列 q 不为空,删除 q 的队头元素,用 e 返回其值*/ QueuePtr p; if(q->front == q->rear) return; /*队列为空,返回*/ p = q->front->next; *e = p->data; q->front->next = p->next; if(q->rear == p) q->rear = q->front; /*如果队头就是队尾, 则修改 队尾指针*/ free(p); } initStack(sqStack *s) { /*内存中开辟一段连续空间作为栈空间, 首地址赋值给 s->base*/ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); /*分配空间失败*/ s->top = s->base; /*最开始,栈顶就是栈底*/ s->stacksize = STACK_INIT_SIZE; /* 最 大 容 量 为 STACK_INIT_SIZE */

} Push(sqStack *s, ElemType e){ /*入栈操作*/ if(s->top - s->base >= s->stacksize){ /*栈满,追加空间*/ s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT)*sizeof(ElemType)); if(!s->base) exit(0); /*存储分配失败*/ s->top = s->base + s->stacksize; s->stacksize = s->stacksize + STACKINCREMENT; /*设置栈的最 大容量*/ } *(s->top) = e; /*放入数据*/ s->top++; } Pop(sqStack *s , ElemType *e){ /*出栈操作*/ if(s->top == s->base) return; /*将栈顶元素弹出*/ *e = *--(s->top); /*修改栈顶指针*/ } int StackLen(sqStack s){ return (s.top - s.base) ; } /*获得栈 s 的大小*/

main() { sqStack s; LinkQueue q; ElemType e,r1,r2; int flag = 1, i, len; initQueue(&q); /*初始化一个队列*/ initStack(&s); /*初始化一个栈*/ printf("Please input a string ,type '@' for end\n");

scanf("%c",&e); while(e != '@'){ Push(&s,e); EnQueue(&q,e); scanf("%c",&e); }

/*输入待判断的字符序列*/

len = StackLen(s)/2; /*获得字符序列的长度*/ for(i=0;i<len;i++) { Pop(&s,&r1); /*出栈操作,由 r1 将栈顶元素返回*/ DeQueue(&q,&r2); /*出队列操作,由 r2 将队头元素返回*/ if(r1 != r2) { flag = 0; break;} } if(flag == 1)printf("It is a circle string.\n"); else printf("It is not a circle string.\n") ; getche(); } 题目 19(括号匹配) 假设表达式中只允许两种括号: 圆括号和方括号, 它们可以任意的嵌 套,例如[()[()]]都是合法的。但是要求括号必须成对出现,像[( ] )或 者( [ ) ]的形式都是非法的。编写一个程序,从终端输入一组括号, 以字符‘#’作为结束标志,判断输入的括号是否匹配合法。 #include "stdio.h" #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef char ElemType; typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; /*将 char 类型定义为 ElemType*/ /*定义一个栈类型*/

initStack(sqStack *s) { /*内存中开辟一段连续空间作为栈空间, 首地址赋值给 s->base*/ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); /*分配空间失败*/ s->top = s->base; /*最开始,栈顶就是栈底*/ s->stacksize = STACK_INIT_SIZE; /* 最 大 容 量 为 STACK_INIT_SIZE */ } Push(sqStack *s, ElemType e){ /*入栈操作*/ if(s->top - s->base >= s->stacksize){ /*栈满,追加空间*/ s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT)*sizeof(ElemType)); if(!s->base) exit(0); /*存储分配失败*/ s->top = s->base + s->stacksize; s->stacksize = s->stacksize + STACKINCREMENT; /*设置栈的最 大容量*/ } *(s->top) = e; /*放入数据*/ s->top++; } Pop(sqStack *s , ElemType *e){ /*出栈操作*/ if(s->top == s->base) return; /*将栈顶元素弹出*/ *e = *--(s->top); /*修改栈顶指针*/ } int StackLen(sqStack s){ return (s.top - s.base) ; } /*获得栈 s 的大小*/

int match(char e,char c){ if(e=='(' && c==')')return 1; if(e=='[' && c==']')return 1; return 0; } main() { sqStack s; char c , e ; initStack( &s ) ; /*初始化一个空栈*/ scanf("%c",&c); /*输入第一个字符*/ while(c!='#'){ /*'#'为输入的结束标志*/ if(!StackLen(s)) Push(&s,c); /*如果栈为空,则说明输入的是第一个字 符,因此保存在栈中*/ else { Pop(&s,&e); /*取出栈顶元素*/ if(!match(e,c)){ /*将输入的元素与取出的栈顶进行比 较,如果匹配不成功*/ Push(&s,e); /*先将原栈顶元素重新入栈*/ Push(&s,c); /*再将输入的括号字符入栈*/ } } scanf("%c",&c); /*输入下一个字符*/ } if(!StackLen(s)) printf("The brackets are matched\n"); /*如果栈 s 为空,则括号完全匹配*/ else printf("The brackets are not matched\n"); /*如果栈 s 不为 空,则括号不完全匹配*/ getchar(); }

练习(动态双向链表的应用) 设有一个双向循环链表,每个结点中除了有 prior,data 和 next 三个 域外还有一个访问频度域 freq。 在该双向链表启用之前, 频度域 freq 的值全部初始化为 0,每当对链表进行一次访问时,被访问的结点的 频度域 freq 就自动增加 1, 同时调整链表中结点之间的次序, 使其按 照访问频度非递增的次序顺序排列, 以便始终保持被访问的结点总是 靠近表头结点。编写一个程序实现上述功能。

#include "stdafx.h" #include "stdio.h" #include<iostream> #include<stdlib.h> using namespace std; typedef struct node{ int data; int freq; struct node *prior; struct node *next; }dbLNode,*dbLinkList; /*创建一个双向链表,返回它的头指针*/ dbLinkList GreatdbLinkList(int n){ dbLinkList p,r,list=NULL; int e; int i; list = (dbLinkList)malloc(sizeof(dbLNode)); /* 创建头结点 head, 头结点中不存放内容*/ list->next = list->prior = NULL; for(i=1;i<=n;i++){ scanf("%d",&e);

p = (dbLinkList)malloc(sizeof(dbLNode)); p->data = e; p->freq = 0; p->next = NULL; p->prior = NULL; if(!list->next) { list->next = p; /*第一个结点*/ p->prior = list; } else{ r->next = p; /*双向连接下面的结点*/ p->prior = r; } r = p; } return list; } /*访问双向链表中指定的结点,并调整结点次序*/ visit(dbLinkList &l,int x){ dbLinkList p = l, q, r, s; p = p->next; /*p 指向第一个结点*/ while(p->data != x && p!=NULL)p = p->next; if(p == NULL) {printf("Input error!\n");return;} p->freq ++; printf("Visiting this node\n"); while((p->prior)!=l && p->freq > p->prior->freq) { /*实现双向链表结点的交换*/ q = p->prior; r = p->next; s = p->prior->prior; p->prior = q->prior; p->next = q;

q->prior = p; q->next = r; r->prior = q; s->next = p; } } TransdbLinkList(dbLinkList l) { /*遍历整个双向链表,并打印出每个结点中的数据和访问频度*/ l = l->next; while(l!=NULL){ printf("(data:%d ,freq:%d)--> ",l->data,l->freq); l = l->next; } printf("X\n\n"); } main() { dbLinkList l; int d; printf("Input five integer to creat a doubly link list\n"); l = GreatdbLinkList(5); TransdbLinkList(l); printf("Please input the data that you want to vist\n"); scanf("%d",&d); while(d!=0){ visit(l,d); TransdbLinkList(l); scanf("%d",&d); }

getchar(); }

题目 20(判断完全二叉树) 题目要求: 完全二叉树的定义是这样的:深度为 k 的,有 n 个结点的二叉树, 当且仅当其每一个结点都与深度为 k 的满二叉树的中编号为 1~n 的 结点相对应,则它被称为完全二叉树。所谓满二叉树就是:深度为 k 且有 2k-1 个结点的二叉树。其中,结点的编号约定为:编号从根结 点起从上至下,自左向右地顺序编号。

#include "stdafx.h" #include "stdafx.h" #include<stdio.h> #include<iostream> #include<stdlib.h> using namespace std; typedef struct BiTNode{ char data; /*结点的数据域*/ struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/ } BiTNode , *BiTree; /*创建一棵二叉树*/ CreatBiTree(BiTree &T , int *level1 , int level2){

char c; scanf("%c",&c); if(c == ' ') T = NULL; else{ T = (BiTNode * )malloc(sizeof(BiTNode)); 建根结点*/ T->data = c; 结点中输入数据*/

/* 创 /* 向根

if(*level1<level2) {*level1 = level2;}

CreatBiTree((T->lchild),(level1),level2+1); 左子树*/ CreatBiTree((T->rchild),(level1),level2+1); 右子树*/ } }

/*递归地创建 /*递归地创建

int JusticCompleteBiTree(BiTree T,int level ,int n,int flag){ if(!T){ return 1; } if(level == n) { if(T->lchild == NULL && T->rchild != NULL) return 0; if(flag == 0){/*同层的前面的结点无空指针*/ if(T->rchild == NULL) flag = 1; /*出现空指针*/ } else if(flag == 1){ /*同层的前面的结点有空指针*/ if(T->lchild!=NULL || T->rchild!=NULL) return 0;

} } if(level != n &&level !=n+1) { if(T->lchild == NULL || T->rchild == NULL) return 0; } if(!JusticCompleteBiTree(T->lchild,level+1,n,flag)) return 0; if(!JusticCompleteBiTree(T->rchild,level+1,n,flag)) return 0; return 1; }

main() { BiTree T; int level1 = 0; printf("Please type some character to creat a binary tree\n"); CreatBiTree(T, &level1,0); if(JusticCompleteBiTree(T,0,level1-1,0)) printf("It is a complete binary tree\n"); else printf("It is NOT a complete binary tree\n"); getchar();

} 题目 21(动画模拟创建二叉树) 题目要求:编写一个 C 程序,要求在 C 程序图形界面下动态模拟显 示二叉树的先序创建过程。

typedef struct BiTNode{

char data; /*结点的数据域*/ struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/ } BiTNode , *BiTree; /*创建一棵二叉树*/ CreatBiTree(BiTree &T , int *level1 , int level2){ char c; scanf("%c",&c); if(c == ' ') T = NULL; else{ T = (BiTNode * )malloc(sizeof(BiTNode)); 建根结点*/ T->data = c; 结点中输入数据*/

/*创 /* 向根

if(*level1<level2) {*level1 = level2;}

CreatBiTree((T->lchild),(level1),level2+1); 左子树*/ CreatBiTree((T->rchild),(level1),level2+1); 右子树*/ } }

/*递归地创建 /*递归地创建

printTree(BiTree T,int x,int y){ char e[2] = {'\0','\0'}; if(T){ /*递归结束条件,T 为空*/ { /*画出一个结点,程序暂停 2 秒*/ e[0] = T->data ; circle(x,y,8) ; settextstyle(DEFAULT_FONT,HORIZ_DIR,2);

outtextxy(x,y,e); sleep(2); } if(printTree(T->lchild,x-(200-y),y+20)) /*先序遍历 T 的左子 树*/ line(x,y,x-(200-y),y+20); if(printTree(T->rchild,x+(200-y),y+20)) /*先序遍历 T 的右子 数*/ line(x,y,x+(200-y),y+20) return 1; } return 0; }
(x,y)

;

y+20

x-(200-y)

x+(200-y)

main() { BiTree T = NULL; int y = 100 ,x = 350; /*设置二叉树根结点坐标*/ int GraphDriver = DETECT; int GraphMode; int color; color = RED; initgraph( &GraphDriver, &GraphMode, "\\tc\\bgi" ); /* 初始化 图形系统,驱动文件"\\tc\\bgi"的路径不能设置错误*/ setcolor(color); /*设置图形颜色:红色*/

CreatBiTree(&T); /*创建二叉树*/ printTree(T,x,y); /*动态显示二叉树创建过程*/ getchar(); closegraph(); printf("ddddd"); system("pause>>nul"); getchar(); } 题目 22(打印符号三角形) 题目要求: 规定这样一种形状的三角形,如图 7-36 所示为一个符号三角形: + + + + + + + + + + + + - + + #include "stdio.h" typedef struct QNode{ char data; struct QNode *next; } QNode , *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; /*定义队列结点类*/

/* 定义一个链队列*/ /*队头指针*/ /*队尾指针*/

initQueue(LinkQueue *q){ /*初始化一个空队列*/ q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)); /*创建一个 头 结 点 , 队 头 队 尾 指 针 指向该结点*/

if( !q->front) exit(0); q->front->next = NULL; }

/*创建头结点失败*/ /*头结点指针域置 NULL*/

EnQueue(LinkQueue *q, char e){ /*入队列操作*/ QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); /*创建一个队列元素结 点*/ if( !q->front) exit(0); /* 创建头结点失败*/ p->data = e; /* 将元素 e 入队列*/ p->next = NULL; /*修改队尾指针*/ q->rear ->next = p; q->rear = p; } DeQueue(LinkQueue *q, char *e){ /*如果队列 q 不为空,删除 q 的队头元素,用 e 返回其值*/ QueuePtr p; if(q->front == q->rear) return; /*队列为空,返回*/ p = q->front->next; *e = p->data; q->front->next = p->next; if(q->rear == p) q->rear = q->front; /*如果队头就是队尾, 则修改 队尾指针*/ free(p); }

printTriangle(int n){ LinkQueue q; char e,a,b ; int i,j; initQueue(&q); /*初始化队列*/ printf("Input the the charecter(+/-) of the row.1\n"); for(i=0;i<n;i++){ /*输入第一行的符号,并入队列*/ scanf("%c",&e); EnQueue(&q,e);

} printf("The charecter triangle is like\n"); for(i=0;i<n;i++){ /*控制符号三角的行数*/ for(j=0;j<i;j++) printf(" "); /*控制输出格式,打印成倒三角 形状*/ DeQueue(&q,&a); /*出队列,打印每行的第一个符 号*/ printf("%c ",a); for(j=0;j<n-i-1;j++) /*控制输出每一行,第 i 行输出 n-i 个符号*/ { DeQueue(&q,&b); /*出队列*/ printf("%c ",b); if(a == b) EnQueue(&q,'+'); /*向队尾插入新元素*/ else EnQueue(&q,'-'); a = b; } printf("\n"); /*控制输出格式,打印成倒三角形状*/ } } main() { int n; printf("Please input the number of '+' or '-' of the row.1 \n"); scanf("%d",&n); getchar(); printTriangle(n); getchar(); }

题目 23(递归函数的非递归求解) 题目要求:

已知 n 是大于等于 0 的整数,请编写非递归的程序计算下列递归函 数 f(n)。

n?0 ? n ?1 f (n) ? ? ? n / 2? ?) n ? 0 ?nf ( ?

#include "stdio.h" #include "math.h" #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef int ElemType; typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; /*初始化栈*/ void initStack(sqStack *s) { /*内存中开辟一段连续空间作为栈空间, 首地址赋值给 s->base*/ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); /*分配空间失败*/ s->top = s->base; /*最开始,栈顶就是栈底*/ s->stacksize = STACK_INIT_SIZE; /* 最 大 容 量 为 STACK_INIT_SIZE */ } /*入栈操作,将 e 压入栈中*/ void Push(sqStack *s, ElemType e){ if(s->top - s->base >= s->stacksize){

/*栈满,追加空间*/ s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT)*sizeof(ElemType)); if(!s->base) exit(0); 配失败*/ s->top = s->base + s->stacksize; s->stacksize = s->stacksize + STACKINCREMENT; 置栈的最大容量*/ } *(s->top) = e; /*放入数据*/ s->top++; } /*出栈操作,用 e 将栈顶元素返回*/ void Pop(sqStack *s , ElemType *e){ if(s->top == s->base) return; *e = *--(s->top); } int f(int n) { int r = 1, e; sqStack stack; initStack(&stack); /*初始化栈*/ while(n!=0){ Push(&stack,n); /*保存现场 n*/ n = n/2; } while(stack.top!=stack.base) { Pop(&stack,&e); r = r * e; } return r; }

/* 存储分

/*设

main() { printf("The result for conversion of recursion to non recursion is\n"); printf("f(5)=%d \n",f(5)); getche(); } 练习 1. (任意长度整数加法) 题目要求: 编写一个程序实现任意长度 的整数加法。 #include "stdio.h" #include "math.h" #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 /*定义堆栈*/ typedef char ElemType; typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; /*初始化栈*/ void initStack(sqStack *s) { /*内存中开辟一段连续空间作为栈空间, 首地址赋值给 s->base*/ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); /*分配空间失败*/ s->top = s->base; /*最开始,栈顶就是栈底*/ s->stacksize = STACK_INIT_SIZE; /* 最 大 容 量 为 STACK_INIT_SIZE */ } /*入栈操作,将 e 压入栈中*/ void Push(sqStack *s, ElemType e){ if(s->top - s->base >= s->stacksize){ /*栈满,追加空间*/ s->base = (ElemType *)realloc(s->base, (s->stacksize +

STACKINCREMENT)*sizeof(ElemType)); if(!s->base) exit(0); /*存储分配失败*/ s->top = s->base + s->stacksize; s->stacksize = s->stacksize + STACKINCREMENT; /* 设 置 栈 的最大容量*/ } *(s->top) = e; /*放入数据*/ s->top++; } /*出栈操作,用 e 将栈顶元素返回*/ void Pop(sqStack *s , ElemType *e){ if(s->top == s->base) return; *e = *--(s->top); } /*计算堆栈 s 当前的长度*/ int StackLen(sqStack s){ return (s.top - s.base) ; } void ADD(sqStack *s1,sqStack *s2,sqStack *s3) { char a1,a2,a3,c=0; /*a1,a2 分别存放从堆栈 s1,s2 中取出 的(数据)元素, a3=a1+a2,c 中存放进位*/ while(StackLen(*s1)!=0 && StackLen(*s2)!=0) { Pop(s1,&a1); /*取出 s1 栈的栈顶元素给 a1*/ Pop(s2,&a2); /*取出 s2 栈的栈顶元素给 a2*/ a3 = (a1-48) + (a2-48) + c + 48; /*相加*/ if(a3>'9') { a3 = a3 - '9' + 47; /*产生进位的情况*/ c = 1; } else

c = 0; Push(s3,a3); } if(StackLen(*s1)!=0) { while(StackLen(*s1)!=0) { Pop(s1,&a1); a1*/ a3 = a1 + c ; if(a3>'9') { a3 = a3 - '9' + 47; c = 1; } else c = 0; Push(s3,a3); } } else if(StackLen(*s2)!=0) { while(StackLen(*s2)!=0) { Pop(s2,&a2); a1*/ a3 = a2 + c; if(a3>'9') { a3 = a3 - '9' + 47; c = 1; } else c = 0; Push(s3,a3); }

/*不产生进位*/ /*将结果入栈 s3*/ /*栈 s1 不为空的情况*/

/*取出 s1 栈的栈顶元素给 /*与进位标志 c 相加*/

/*产生进位的情况*/

/*不产生进位*/ /*将结果入栈 s3*/

/*栈 s1 不为空的情况*/

/*取出 s1 栈的栈顶元素给 /*与进位标志 c 相加*/

/*产生进位的情况*/

/*不产生进位*/ /*栈 s1 不为空的情况*/

} if(c==1) Push(s3,'1'); 入栈 s3*/ }

/*如果最后有进位,将字符’ 1’

main() { char e; sqStack s1,s2,s3; initStack(&s1); /*初始化堆栈 s1, 存放加数 */ initStack(&s2); /*初始化堆栈 s2, 存放加数 */ initStack(&s3); /*初始化堆栈 s3, 存放结果 */ printf("Please input the first integer\n"); /* 输入第一个任意长整 数,按”#”结尾*/ scanf("%c",&e); while(e!='#') { Push(&s1,e); /*将加数 (字符串) 入栈 s1*/ scanf("%c",&e); } getchar(); /*接收回车符*/ printf("Please input the second integer\n"); /* 输 入 第 二 个 任 意 长整数,按”#”结尾*/ scanf("%c",&e); while(e!='#') { Push(&s2,e); /*将加数 (字符串) 入栈 s2*/ scanf("%c",&e); } ADD(&s1,&s2,&s3); /* 加法运算,将结果存 放在 s3 中*/ printf("The result is\n");

while(StackLen(s3)!=0) */ { Pop(&s3,&e); printf("%c",e); } getchar(); }

/*输出结果,打印在屏幕上


相关文章:
常用的算法思想2
常用的算法思想2_教学案例/设计_教学研究_教育专区。算法 一、常用的算法思想 1. 穷举法思想基本概念:穷举法(Exhaustive Attack method),它是一种最为直接, 最...
算法分析与设计常见算法思想
算法分析与设计常见算法思想_数学_自然科学_专业资料。算法导论复习——常见算法思想 PPT2-1: 1. 堆排序(选择类排序,不稳定) (1)初始化操作:将 R[1..n]构...
算法的基本思想2
算法的基本思想2_数学_高中教育_教育专区。编制人:杨俊红 审核人:梁小军 日期:2014-2-24 编号:12 班级: 姓名: 组别: 评价: 使用说明 算法的基本思想 2 算法...
常用的十大算法
常用的十大算法_工学_高等教育_教育专区。数学建模常用的十大算法==转 1. 蒙特卡罗...事实上,网格算法、蒙特卡罗算法、模拟退火都用 了这个思想。 2.9 数值分析...
五大常用算法
五大常用算法之一: 五大常用算法之一:分治算法 分治算法 一、基本概念 在计算机...此特征反映了递归思想的 第二条特征是应用分治法的前提 应用; 、 第三条特征...
算法的基本思想2
算法的基本思想 2 教学目标 1.正确理解算法的概念,掌握算法的基本特点。 2.通过算法的学习,体会设计算法的基本思路。 3.通过有趣的实例了解算法这一概念的同时,...
2.1.1算法的基本思想(2)
用上面的歌诀来算《孙子算经》中的问题,便得到算式: 2×70+3×21+2×15=233, 233-105×2=23, 即所求物品最少是 23 件。 (2).算法设计思想: ?m ?...
几种常用的最短路径算法
简述几种常用的最短路径算法摘要:随着社会的发展,最短路径问题在现实生活中占据...3.2 算法描述 3.2.1 算法思想原理 Floyd 算法是一个经典的动态规划算法。用...
§2.1.2算法的基本思想(学生版)
算法的思想(2) 第 2 页共 5 页 ★★★3. 写出用二分法求解多项式方程 f (x) =0 在区间 [a , b] 的一种常用方法。 三、拓展延伸 ★★★1. 写出求...
数学解题方法谈:常用的算法思想
2页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 数学解题方法谈:常用的算法思想 高中数学解题方法谈高中数学...
更多相关标签:
常用算法思想 | 常用算法 | 算法思想 | 贪心算法的基本思想 | grid search算法思想 | dijkstra算法思想 | k means算法思想 | smote算法思想 |