1）选择排序
选择排序思想：
选择排序（Selection sort）是一种简单直观的排序算法。
工作原理：首先在未排序序列中找到最小元素，存放到排序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。依次类推，直到所有元素均排序完毕。
选择排序代码实现：
void xuanZe(int nums[],int len){
int temp;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len-1;j++){
if(nums[i]>nums[j]){
temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
}
}
void main(){
int nums[10]={15,32,14,18,45,75,34,74,44,77};
printf("排序前：");
for(int i=0;i<10;i++){
printf("%d\t",nums[i]);
}
xuanZe(nums,10);
printf("排序后：");
for(int i=0;i<10;i++){
printf("%d\t",nums[i]);
}
}
2)折半查找思想
基本思路：
在有序列表中，取中间元素作为比较对象，若给定值与中间元素的要查找的数相等，则查找成功；若给定值小于中间元素的要查找的数，则在中间元素的左半区继续查找；
若给定值大于中间元素的要查找的数，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。
实现步骤：
a、low=1;high=length;//设置初始区间
b、当low>high时，返回查找失败信息//表空，查找失败
c、当low≤high,mid=(low+high)/2; //取中点
①、若key<arr[mid],high=mid-1; 转b //查找在左半区进行
②、若key>arr[mid],low=mid+1; 转b //查找在右半区进行
③、若key=arr[mid],返回数据元素在表中位置 //查找成功
注：折半查找前提：在一个有序数组中查找。
例如：key=45;
0 1 2 3 4
12 45 66 110 200
l m h
循环：mid=(l+h)/2; 如上：m=（0+4）/2;
key(值是45)<a[mid](值是66)
h=m-1;
key(值是45)>a[mid](值是12)
l=m+1;
key(值是45)=a[mid](值是45)-->查找到
3）折半查找的代码实现
a、测试练习1
//使用折半查找来查找一个数
//arr是数组
//len是数组长度
//key是要查找的数（关键字）
//return 返回要查找的数的位置，如果查找不到，返回 -1
int searchItem(int arr[],int len,int key){
int low=0,high=len-1,mid;
while(low<=high){
mid=(low+high)/2;
if(key>arr[mid]){
low=mid+1;
}else if(key<arr[mid]){
high=mid-1;
}else{
return mid;
}
}
//如果查找不到，返回-1
return -1;
}
int main(){
int arr[]={3,4,12,20,21,23,28,45,67,100};
//查找key值=20
int loc=searchItem(arr,10,20);
printf("loc = %d\n",loc);
}
b、测试练习2
//输入一组有序数据，使用折半查找法插入一个数据，返回要插入数据的位置，假设插入45
//3,4,12,20,21,23,28,45,67,100
int InsertItemLoc(int arr[],int len,int key){
int low=0,high=len-1,mid;
while(low<=high){
mid=(low+high)/2;
if(key>arr[mid]){
low=mid+1;
}else if(key<arr[mid]){
high=mid-1;
}else{
return mid+1;
}
}
//如果查找不到，返回low
return low;
}
int main(){
int arr[]={3,4,12,20,21,23,28,45,67,100};
//查找key值=20
int loc=InsertItemLoc(arr,10,45);
printf("loc = %d\n",loc);
}
4)二维数组定义
a、二维数组的应用：俄罗斯方块、五子棋、象棋等
所谓多维数组就是二维和大于二维的数组，在C语言中并不直接支持多维数组，包括二维数组。多维数组的声明是使用一维数组的嵌套声明实现的。一个一维数组的每个元素又被声明为一维数组，从而构成二维数组，可以说二维数组是特殊的一维数组。
b、二维数组的定义
类型说明符 数组名[常量表达式1][常量表达式2]
其中常量表达式1表示第一维下标的长度，常量表达式2表示第二维下标的长度。
例如：int[3][4];
声明了一个三行四列的数组，数组名为a，其下标变量的类型为整型，该数组的下标变量共有3*4个。
c、二维数组定义的注意事项
①数组名不能和变量名同名；
②数组的长度可以是常量表达式；
③数组长度可以使用宏定义 #define M 3 int arr[M+3][6]
④二维数组第一维可以省略，第二维不可以省略
5）二维数组初始化
a、定义的同时初始化
①完全初始化
法一：int arr[3][2]={{1,4},{2,6},{5,3}};//分段初始化
法二：int arr[3][2]={1,4,6,8,5,4};//连续赋值
法三：int arr[][3]={{1,2,3},{2,3,4},{2,6,4}};//可以省略第一维
法四：int arr[][2]={1,2,4,3,6,4,7,5};
②部分初始化
int arr[2][3]={1};//默认初始化为{{1,0,0}，{0,0,0}}
int arr[2][3]={{1},{2}};//默认初始化为{{1,0,0},{2,0,0}}
int arr[2][3]={1,2,3,4};////默认初始化为{1,2,3,4,0,0}
b、先定义，后初始化
int a[3][4];
a[0][0]=1;
a[0][1]=2;
...
a[0][4]=1;
a[1][0]=1;
a[1][1]=1;
...
a[1][4]=1;
a[3][0]=1;
a[3][1]=1;
...
a[3][4]=1;
6）二维数组遍历
a、二维数组的元素也称为双下标变量，其表示形式为：
数组名[第一维下标][第二维下标]
其中下标应为整型常量或整型表达式。
7）二维数组存储
①二维数组在概念上是二维的，即是说其下标在两个方向上变化，下标变量在数组中的位置也处于一个平面之中，而不是像一维数组只是一个向量。但是，实际的硬件存储器却是连续编址的，也就是说存储器单元式按照一维线性排列的。
如何在一维存储器中存放二维数组：
a、按行排列，即放完一行之后顺次放入第二行；
b、按列排序，即放完一列之后再顺次放入第二列。
②存储方式；
a、计算机会给二维数组分配一块连续的存储空间；
b、数组名代表数组的首地址，从首地址位置依序存入第一行，第二行....
c、每一行存储方式，从行首地址开始，依次存储行的第一个元素、第二个元素...
d、每个元素占用相同的字节数（取决于数组类型）
e、并且数组中元素之间的地址是连续的。
③注：在C语言中，二维数组是按照行排列的。即，先存放第一行，再存放第二行。
|
|
收藏
淘帖
踩
