1966年Bohm和Jacpini用数学方法证明了只用三类控制结构和任意数量的布尔型标志变量就能表示任何算法(或函数),这三类控制结构是:
1 顺序结构
2 选择结构(例如,if-else,switch)
3 循环结构(例如,whuile,for,do)
这三种控制结构的一个特点就是只有一个入口和出口,是对goto语句随意跳转的一种约束或限制。
不管是选择还是循环,本质上都是一种跳转,在计算机的底层,分支选择与循环是通过比较与跳转命令来实现的。
在汇编语言中,比较命令是cmp,跳转命令是jmp\jg\jge等。
指令序列顺序存储在内存的代码区,用地址表示每一条指令,指令跳转就是直接跳到代码区某一地址对应的指令去执行。
而比较命令cmp在计算机内部是通过一个减法操作来实现,减法的结果可以是一个正数、负数或0,存储到标志寄存器中,根据标志寄存器中的值(状态)来进行跳转。
这三种控制结构的顺序和选择结构相对容易理解,理解循环结构要复杂一些。
可以通过goto如何实现重复操作去理解while循环,通过while循环去理解for循环:
#include <stdio.h>
int accumuByGoto(int n)
{
int sum=0,i=0; // 迭代变量i初始化
label:
i ; // 迭代变量i更新
sum =i;
if(i<n) // 包含不的条件判断
goto label;
return sum;
}
int accumuByWhile(int n)
{
int i=1,sum=0; // 循环变量初始化
while(i<=100) // 包含循环变量的条件判断
{
sum =i;
i ; // 循环变量更新
}
return sum;
}
int accumuByFor(int n)
{
int sum = 0;
for(int i=1;i<=100;i ) // 包含循环变量的三个表达式集中到了一起
sum = i;
return sum;
}
int main()
{
printf("%d ",accumuByGoto(100));
printf("%d ",accumuByWhile(100));
printf("%d ",accumuByFor(100));
getchar();
return 0;
}
循环应用场合最多的就是遍历数组,链表去做排序或查找操作等。
1 单循环及应用场合
#include <stdio.h>
int func(char s[],int c) // 在字符串在删除某一指定字符
{
char *q=s;
for(; *q; q )
if(*q != c)
*(s )=*q;
*s='\0';
}
void main()
{
static char str[]="Turbo c and borland c ";
char ch;
printf(" The string before delete is %s.\n",str);
printf(" Please input the char to delete : ");
scanf("%c",&ch);
func(str,ch);
printf(" The string after delete is %s.\n",str);
printf(" Press any key to quit...");
getchar();
return;
}
数组名是数组全部元素的基点,索引的改变相当于就是这个指针的移动。
一趟循环找出两个最值:
#include <stdio.h>
#include <stdlib.h>
const int minm = -32767;
const int maxm = 32767;
int maxmin[2]={0};
int* findMax(int data[],int count,int *arr) // 一趟循环找出两个最值
{
int i;
int maxn = data[0];
int maxn2 = minm;
for (i=1;i<count;i )
{
if(data[i] > maxn)
{
maxn2 = maxn; // maxn2是maxn的接替者
maxn = data[i]; // maxn更新为最新近的最大值
}
else
{
if(data[i]>maxn2)
maxn2 = data[i]; // maxn2如果比最新比较的值要小,也要更新
}
}
arr = maxmin; // 只是指针指向
arr[0] = maxn;
arr[1] = maxn2;
printf("%d,%d\n",arr[0],arr[1]);
return arr;
}
int* findMin(int data[],int count,int *arr)
{
int i;
int minn = data[0];
int minn2 = maxm;
for (i=1;i<count;i )
{
if(data[i] < minn)
{
minn2 = minn;
minn = data[i];
}
else
{
if(data[i]<minn2)
minn2 = data[i];
}
}
arr = maxmin;
arr[0] = minn;
arr[1] = minn2;
printf("%d,%d\n",arr[0],arr[1]);
return arr;
}
int main()
{
int arr[] = {12,5,6,7,7,8,98,3,458,53,1};
int len = sizeof(arr)/sizeof(arr[0]);
findMax(arr,len,maxmin);
findMin(arr,len,maxmin);
system("pause");
return 0;
}
遍历链表:
struct Node
{
int data;
struct Node* next;
};
void printList(struct Node* headNode)
{
struct Node* pMove = headNode->next;
while (pMove) // 节点是否为空
{
printf("%d->", pMove->data);
pMove = pMove->next; // 链表指针移动
}
printf("\n");
}
不同于数组索引的移动,链表是以头节点为基准,每个节点通过节点的指针域去找到下一个节点的。
2 双循环相对于单循环,双循环的理解要困难一些。假设有一个n*m的双循环(外循环执行n次,内循环执行m次),简单的理解就是外循环的迭代变量迭代一次,内循环的迭代变量迭代m次(跑一圈后回到外循环),当外循环变量迭代n次(外循环跑一圈 )后,双循环退出(当然也可以通过break提前退出)。
双循环用得最多的场合就是一维数组排序了。
我们知道,对于冒泡排序来说,一次从一个线性结构中冒出一个最值需要一个循环,自然,数组全部元素的处理就需要再在外面套一个循环了。
#include<stdio.h>
#include<stdlib.h>
int main(){
int i,j;
char a[10] = {'e','b','a','d','f','i','c','g','j','h'};
char t;
printf("原数组中的字符是:\n");
for(i=0; i<10; i )
{
printf("%c ",a[i]);
}
for(i=0; i< 9; i )
{
for(j=0;j<9-i; j )
{
if(a[j]>a[j 1])
{
t=a[j];
a[j]=a[j 1];
a[j 1] = t;
}
}
}
printf("\n按升序排序后的字符是:\n");
for(i=0; i<10; i )
{
printf("%c ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
/*
原数组中的字符是:
e b a d f i c g j h
按升序排序后的字符是:
a b c d e f g h i j
*/
链表的排序是同样的思想:
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* next;
};
struct Node* createList()
{
struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
headNode->next = NULL;
return headNode;
}
struct Node* createNode(int data)
{
struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
headNode->data = data;
headNode->next = NULL;
return headNode;
}
void insertNodeByHead(struct Node* headNode, int data)
{
struct Node* newNode = createNode(data); // 1 新建节点
newNode->next = headNode->next; // 连(新节点的指针域连上头节点的下一个节点)
headNode->next = newNode; // 断(头节点的指针域连上新节点)
}
void printList(struct Node* headNode)
{
struct Node* pMove = headNode->next;
while (pMove)
{
printf("%d->", pMove->data);
pMove = pMove->next;
}
printf("\n");
}
void BubbleSort(struct Node* headNode)
{
struct Node* firstNode = headNode->next;
struct Node* secondNode = headNode;
while (firstNode != NULL)
{
while (firstNode->next != NULL)
{
if (firstNode->data > firstNode->next->data)
{
int temp = firstNode->data;
firstNode->data = firstNode->next->data;
firstNode->next->data = temp;
}
firstNode = firstNode->next;
}
//减少排序次数
firstNode = secondNode->next;
secondNode = firstNode;
}
}
int main()
{
struct Node* list = createList();
insertNodeByHead(list, 3);
insertNodeByHead(list, 1);
insertNodeByHead(list, 2);
insertNodeByHead(list, 5);
printList(list);
BubbleSort(list);
printList(list);
system("pause");
return 0;
}
一维数组找一个最值需要单循环,一维数组排序需要双循环,二维数组排序则需要再在外套一个循环,需要三重循环。
#include <stdio.h>
jsValue(int arr[][9],int rows)
{
int size = 9;
int i,j,r;
for(r=0;r<rows;r )
{
for(i=0;i<size;i )
for(j=0;j<size-i-1;j )
if(arr[r][j]>arr[r][j 1])
{
int t=arr[r][j];
arr[r][j]=arr[r][j 1];
arr[r][j 1]=t;
}
}
}
main()
{
int a[10][9]={
{6,8,9,1,2,5,4,7,3},
{3,5,8,9,1,2,6,4,7},
{8,2,1,9,3,5,4,6,7},
{3,5,1,2,9,8,6,7,4},
{4,7,8,9,1,2,5,3,6},
{4,7,3,5,1,2,6,8,9},
{9,1,3,5,8,6,2,4,7},
{2,6,1,9,8,3,5,7,4},
{5,3,7,9,1,8,2,6,4},
{7,1,3,2,5,8,9,4,6},
};
int i,j;
jsValue(a,10);
for(i=0;i<10;i ){
for(j=0;j<9;j ) {
printf("%d",a[i][j]);
if(j<=7)printf(",");
}
printf("\n");
}
getchar();
}
在枚举算法中,都极有可能使用4重及更多重循环了。
现有苹果、桔子、香蕉、菠萝、梨5种水果用来做水果拼盘,每个水果拼盘一定有3个水果,且这3个水果的种类不同,问可以制作出多少种水果拼盘?
使用枚举类型定义变量x、y、z,其中,x、y、z 是5 种水果中的任一种,设定由水果x、y、z 制作一种水果拼盘,并满足x≠y≠z。使用三重循环语句来组合它们,使用穷举法来计算总共有多少种水果拼盘可以制作。
#include <stdio.h> // 排列问题,非组合问题
void main()
{
enum fruit {apple, orange, banana, pineapple, pear};/* 定义枚举结构*/
enum fruit x,y,z,pri; /* 定义枚举变量*/
int n=0,loop;
for(x=apple;x<=pear;x )
for(y=apple;y<=pear;y )
if(x!=y)
{
for(z=apple;z<=pear;z ) // 三个东西的组合需要三重循环
if((z!=x)&&(z!=y))
{
n=n 1;
printf("\n %-4d",n);
for(loop=1;loop<=3;loop ) // 组合顺序不同,也是不同的排列
{
switch(loop)
{
case 1:pri=x;break;
case 2:pri=y;break;
case 3:pri=z;break;
default: break;
}
switch(pri)
{
case apple: printf(" %-9s","apple"); break;
case orange: printf(" %-9s","orange");break;
case banana: printf(" %-9s","banana");break;
case pineapple: printf(" %-9s","pineapple");break;
case pear: printf(" %-9s","pear"); break;
default: break;
}
}
}
}
printf("\n\n There are %d kinds of fruit plates.\n",n);
puts(" Press any key to quit...");
getch();
return;
}
-End-
,