目录
一、数组元素查找
二、插入数组元素
三、删除数组元素
四、数组排序
一、数组元素查找
查找算法是为了获得待查询元素在数组中是否存在在，如果存在其具体位置的信息。
最简单的方法就是从第一个元素开始依次与待查找的元素进行比较，如果相等就查找成功，输出元素及对应下标; 如果与所有元素都比较结束仍没有相等的元素，则输出“元素不存在”的提示信息。
【例】从键盘上输入n(≤n≤10)个整数作为数组a的元素值，再读人一个待查找的整数x，在a数组中查找入 如果存在输出它的下标，否则提示:"Not present! "
#include
#define SIZE 10
int find(int a[],int n,int x); /*函数声明*/
int main()
{
int array[SIZE], i = 0, n, x;
int pos;
do
{
printf("Please input n(1<=n<=%d):", SIZE);
scanf("%d", &n);
} while (n<1 || n>SIZE); /*保证读入的n满足1≤n≤SIZE*/
printf("Please input %d elements:", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]); /*读入数组元素*/
printf("Please input x be searched:");
scanf("%d", &x); /*读入待查找数据*/
pos = find(array, n, x); /*调用函数完成查找*/
if (pos < n)
printf("value=%d,index=%d\n", x, pos);
else
printf("Not present!\n");
return 0;
}
/*函数功能:完成一维数组的查找算法
函数参数：3个形式参数分别对应于待查找的数组、数组的有效元素个数以及
待查找的值
函数返回值：返回查询结果，若查询成功，返回数组元素所在下标，不成功
则返回数组长度值n*/
int find(int a[], int n, int x)
{
int i = 0;
while (i < n) /*循环条件为:如果未找到且未搜索完元素*/
{
if (x == a[i]) /*如果查找成功，i的值正好是元素下标*/
break;
i++;
}
return i;
}
二、插入数组元素
插入是指在原有序列中插入一个新的值。有的时候是指定位置的插入，更多情况下是向有序 数组中插入一个数组元素，使得插入后的数组仍保持原序。
插入算法的一般步骤如下：
1、定位:即确定新元素的插入位置。在给定插入位置的插入算法中该步骤可以省略;但是如果是向有序数组中插入，则首先必须寻找待插入的位置，即得到新元素插入的下标 i 。
2、移位:插入位置有两种，一种是在已有的任一数据元素的前面插入;第二种在数组的最后位置插入，这种情况下不需要移位。如果数组原来有 n个元素，则共有 n+1 个可能的插入位置。 对于第一种位置的情况，需要移位，方法是:将下标为n-1的元素到下标为 i 的元素依次做赋值给后一个元素的操作，这样下标 i 位置上的元素事实上已经复制到了下标为 i+1 的位置上，因此可以被待插入元素所覆盖。
3、插入：在下标为 i 的位置上插入新元素，即做一次赋值操作，将待插入数据赋值给下标为 i 的数组元素。
【例】整型数组a中的元素值已经按照非递减有序排列（非严格的递增，相邻两数可以相等），再读入一个待插入的整数x，将x插入数组中。使a数组中的元素仍然保持非递减有序排列。
#include
#define SIZE 7
void print(int a, int n);
void insert(int a[], int n, int x);
int main()
{
int array[SIZE] = {12, 23, 34, 45, 56, 67};
/*用6个递增数值初始化数组元素*/
int x;
print(array ,SIZE - 1); /*输出插入前数组元素*/
printf("Please input x be inserted:\n");
scanf("%d", &x); /*读人待插入的值x*/
insert(array ,SIZE - 1,x ); /*插入*/
print(array, SIZE); /*输出插入后数组元素,长度加1*/
return 0;
}
/*函数功能: 完成一维数组的输出
函数参数: 两个形式参数分别表示待输出的数组、实际输出的元素个数
函数返回值:无返回值*/
void print(int a[], int n)
{
int i;
printf("The array is:\n");
for (i = 0; i < n; i++)
printf("%5d", a[i]);
printf("\n");
}
/*函数功能: 完成一维数组的插入算法
函数参数:3个形式参数分别对应于待指入的数组、现有元素个数、待插入元素
函数返回值:无返回值*/
void insert(int a[], int n, int x)
{
int i, j;
for (i = 0; i < n && a[i] < x; i++);
//注意，该语句到这里就已经结束了，因为已经有了一个；
/*定位 : 查找待插入的位置i，循环停止时的i就是*/
for (j = n - 1; j >= i; j--) /*移位:用递诚循环移位，使下标元素可被覆盖*/
a[j + 1] = a[j];
a[i] = x; /*插入:数组的i下标元索值赋值为插入的x*/
}
三、删除数组元素
内存空间中的数据只能修改，不能“擦除”。所谓“删除”其实是通过将需要删除的元素“覆盖”完成的，也就是将待删除元素后面的元素依次赋值给前一个元素。
删除算法的一般步骤如下。
①定位:即确定待删除元素的下标。此步骤通过循环将数组中的元素与待删除的值x做是否相等的比较，找到相等元素后停止循环，此时的下标i就是待删除的位置。当然，也可能比较完所有元素后不存在值等于x的元素，则表示不能执行删除操作，不进行下面的②和③两步。 ② 移位:如果待删除的元素下标为i，则通过一个递增型循环，从i下标开始一直到n-2下标依次将元素前移(形如:a[j]=a[j+1])，从而达到覆盖下标i原有值的效果。 ③ 个数减1:第②步结束之后，下标n-2和下标 n-1两个位置上的元素为同一个值，即原来的最后一个元素有两个副本。此时，只能通过将有效元素个数n的值减1的方式，使得下标n-1的元素变成一个多余的不再被访问的元素，从而达到删除的最终效果。 下面通过例子来演示删除数组元素的完整过程。 【例】整型数组a中有若干个元素，再读入一个待删除的整数x，删除数组中第1个等于 x 的元素，如果x不是数组中的元素，则显示:"can not delete x!"。
#include
#define SIZE 5
/*函数功能: 完成一维数组的输出
函数参数: 两个形式参数分别表示待输出的数组、实际输出的元素个数
函数返回值:无返回值*/
void print(int a[], int n)
{
int i;
printf("The array is:\n");
for (i = 0; i < n; i++)
printf("%5d", a[i]);
printf("\n");
}
/*函数功能: 完成从一维数组中删除特定元素
函数参数:3个形式参数分别对应于待删除的数组、现有元素个数、待删除的元素值
函数返回值:返回删除是否成功的标志，1表示成功，0表示待删除元素不存在*/
int delArray(int a[], int n, int x)
{
int i, j;
int flag = 1;/*是否找到待删除元素的标志位，1找到，0未找到*/
for (i = 0; i < n && a[i] != x; i++);
/*定位 : 查找待删除元素x是否存在，此处循环体为空语句*/
if (i == n)/*循环停止时如果i==n，则说明元素不存在*/
flag = 0;
else
{
for (j = i; j < n - 1; j++)/* 前移，覆盖i下标元素*/
a[j] = a[j + 1];
}
return flag;
}
int main()
{
int array[SIZE] = { 12, 23, 34, 45, 12 };
/*初始化数组元素*/
int x;
print(array, SIZE); /*输出删除前的数组元素*/
printf("Please input x be inserted:\n");
scanf("%d", &x); /*读入待删除的值x*/
if (delArray(array, SIZE, x)) /*调用delArray函数删除元素x*/
print(array, SIZE - 1);
else
printf("can not delete x!\n");/*否则给出未删除的提示信息*/
return 0;
}
当然，这个程序有它的局限性，只能实现删除第1个值等于x的元素，如果存在多个与x值相同的元素要怎么改进方法呢？
【分析与解答】例题中的删除函数delArray在找到待删除的值为x的元素后，将后面的数组元素依次向前覆盖一次，数组有效长度减1。如果数组中存在多个值为x的元素，即找到第一个值为x的元素，完成覆盖后、应在该元素所在位置开始继续上述的查找、删除过程，直到所有元素全部遍历。参考程序如下:
#define _CRT_SECURE_NO_WARNINGS
#include
#define SIZE 10
/*函数功能: 完成一维数组的输出
函数参数: 2个形式参数分别表示待输出的数组、实际输出的元素个数
函数返回值:无返回值*/
void print(int a[], int n)
{
int i;
printf("The array is:\n");
for (i = 0; i < n; i++)
printf("%5d", a[i]);
printf("\n");
}
/*函数功能: 完成从一维数组中删除特定元素
函数参数: 3个形式参数分别对应于待删除的数组、现有元素个数、待删除的元素值
函数返回值:返回删除的个数
*/
int delArray2(int a[], int n, int x)
{
int i, j;
int count = 0; /*存储删除的个数*/
for (i = 0; i < n - count; i++) //每删除一个数x.数组有效长度会减少一个* /
{
if (a[i] == x)
{
count++;
for (j = i; j < n - count; j++) /*找到删除的x，把后续数组元素向前覆盖一个*/
a[j] = a[j + 1];
i--; /*前移的位置减1*/
}
}
return count;
}
int main()
{
int array[SIZE] = { 23,45,23,12,56,23,67,13,65,23 };
int x, count;
print(array, SIZE); /*输出删除前的数组*/
printf("Please input x be deleted:\n");
scanf("%d", &x);
count = delArray2(array, SIZE, x); /*调用 delArray删除元素 x，并返回删除的个数*/
if (count)
print(array, SIZE - count); /*如果成功，输出删除后的数组元素*/
else
printf("can notdelet x!\n");
return 0;
}
四、数组排序
排序可以用很多种方法实现，我们先来介绍其中的一种——冒泡排序。
冒泡排序的算法思想是:
在排序过程中对元素进行两两比较,越小的元素会经由交换慢慢“浮”到数组的前面(低下标处)，像气泡一样慢慢浮起，由此得名。假设对长度为n的数组进行冒泡排序，算法可以描述如下：
①第1趟冒泡:从数组n-1下标的元素到0下标元素遍历，比较相邻元素对，如果后一个元素小于前一个元素，则交换。第一趟结束时，最小元素“浮起”到达0下标位置。 ②第2趟冒泡:从数组n-1下标的元素到1下标元素遍历(因为0下标的已是最小元素，已经到位，无需再参加比较)，比较相邻元素对，如果后一个元素小于前一个元素，则交换。第二趟结束时，本趟最小元素到达1下标位置。 依此类推，最多n-1趟冒泡(n是元素个数)，便可以完成排序。
【例】从键盘上输入n(1≤n<10)个整数，用冒泡法将元素按从小到大的顺序排房，然后输出排序后元素。
#include
#define SIZE 10
/*函数功能: 完成一维数组的输出
函数参数:表示待输出的数组、实际输出的元素个数
函数返回值:无返回值*/
void print(int a[], int n)
{
int i;
printf("The array is:\n");
for (i = 0; i < n; i++)
printf("%5d", a[i]);
printf("\n");
}
/*函数功能: 完成一维数组的冒泡排序算法
函数参数:两个参数分别是待排序数组及当前元素个数
函数返回值:无返回值*/
void BubbleSort(int a[], int n)
{
int i, j, temp;
for (i = 0; i < n - 1; i++) /*共进行n-1趟排序*/
for (j = n - 1; j > i; j--) /*递减循环，从后往前比较*/
if (a[j] < a[j - 1]) /*两两比较，若后一个元素小则交换该组相邻元素*/
{
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
int main()
{
int array[SIZE], i = 0, n;
do
{
printf("Please input n(1<=n<=%d):", SIZE);
scanf("%d", &n);
} while (n<1 || n>SIZE); /*保证读入的n满足1≤n≤SIZE*/
printf("Please input %d elements:", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]); /*读入数组元素*/
BubbleSort(array, n); /*调用函数完成排序*/
print(array, n);
return 0;
}
当然，这个冒泡排序还可以更简化，上面这种方法是最容易理解的，写得最详细的，但是它的局限性就在于每次比较都要遍历整个数组，一共要遍历n-1趟，这样会使得整个代码的效率变得极低。
我们可以在这个代码的基础上可以这样优化：
1、将遍历的趟数减到最少，即增加一些代码，用来判断后续数据是否已经是顺序排好了，如果后续数据已然有序，那么我们可以直接退出排序，不必再进行遍历；
2、在1的基础上，再次简化代码，遍历数据时增加一个记忆点，使得下一次遍历的数据可以从记忆点开始，不用从头再来。
这两个优化后的冒泡排序的实现过程我已经写在另一篇关于排序方法的博客里了，链接如下：
https://mp.csdn.net/mp_blog/creation/editor/129907696
相关文章
发表评论