数组与排序算法（4.27）

一  一维数组的初始化

 

数组初始化指的在数组定义的时候，给数组赋值,如果一个数组已经定义了，接下来不能在以初始化的形式给数组赋值

 

初始化形式:

 

数据类型  数组名[数组元素个数] = {一个元素值，第二个元素的值,....};

 

int a[5] = {1,2,3,4,5};//a[0]=1,a[1] = 2,a[2] = 3,a[3] = 4,a[4] = 5

int a[5] = {1};//a[0] = 1,a[1] = 0,a[2] = 0,a[3] = 0,a[4] = 0

注意:如果只是对数组的前一部分成员初始化，未初始化的成员默认为0

 

------------------------------------------------------------------

int a[5];

a[5] = {1,2,3,4,5};//错误

------------------------------------------------------------------

 

 

数据类型  数组名[ ] = {一个元素值，第二个元素的值,....};

特点:编译器会根据初始化的数据个数，来决定数组的元素个数

 

int a[] = {1,2,3,4,5};//a[0] = 1,a[1] = 2,a[2] = 3,a[3] = 4,a[4]=5

 

------------------------------------------------------------------

int a[] = {};//错误

------------------------------------------------------------------

 

练习:

定义一个字符数组a，将它初始化为abcdefgh,

定义一个字符数组b, 将它初始化为xjjkabcd789,

 

然后，找出两个数组相同的字符，存放在字符数组c中,最后输出字符数组c

 

#include <stdio.h>

int main()
{
    int i;
    int j;
    int count = 0;
    unsigned char c[256];
    unsigned char a[] = {'a','b','c','d','e','f','g','h'};
    unsigned char b[] = {'x','j','j','k','a','b','c','d','7','8','9'};

    for(i = 0;i < sizeof(a)/sizeof(a[0]);i ++)
    {
        for(j = 0;j < sizeof(b)/sizeof(b[0]);j ++)
        {
            if(a[i] == b[j])
            {
                //c[count] = a[i];
                //count ++;
                c[count ++] = a[i];
            }
        }
    }

    for(i = 0;i < count;i ++)
    {
        printf("%c ",c[i]);
    }
    printf("");

    return 0;
}

 

二 字符数组和字符串 

 

字符数组：是一个char/unsigned char的数组，一般用来存放字符

 

注意:字符数组只能存放字符=>错误 ,也可以用来存放整数[char/unsigned char 为小整型]

 

例如:

char buf[5];

 

---------------------------------------------------------------------------------------

 

字符串 : 是一组字符的集合体，它的最后一个字符一定为'\0'字符,在C语言中表式方法: "多个字符"

 

例如: 

'a'[1byte] 和 "a"[2byte:'a' + '\0']

 

 

字符串输入和输出:'%s'

char buf[1024];

 

输入:

scanf("%s",buf);

注意:空格或回车键或tab键是输入的分割符

 

输出:

printf("用户提示信息%s\n",buf);

注意:当你以 %s 形式输出字符数组的时候，一定要确保数组中有'\0'字符，否则输出乱码

 

练习:解决scanf("%s")的空格字符问题?

自己实现字符串的输入

 

#include <stdio.h>

int main()
{
    int i = 0;
    int j = 0;
    char  bak[1024];
    char buf[1024];

    //h
    for(i = 0;i < sizeof(buf)/sizeof(buf[0]) - 1;i ++)
    {
        scanf("%c",&buf[i]);
        if(buf[i] == '\n')
            break;

    }
    buf[i] = '\0';

#if 0
    错误:不一定输入了1024个字符
    for(i = 0;i < sizeof(buf)/sizeof(buf[0]);i ++)
    {
        printf("%c ",buf[i]);
    }
    printf("\n");
#endif

    printf("%s\n",buf);

#if 0
    这是将整个数组的内容拷贝，而不是将字符串拷贝
    输入的字符不一定有1024个
    for(i = 0;i < sizeof(buf);i ++)
    {
        bak[i] = buf[i];
    }
#endif
    for(j = 0;j <= i;j ++)
    {
        bak[j] = buf[j];
    }
    printf("bak : %s\n",bak);

    for(i = 0;buf[i] != '\0';i ++)
    {
        bak[i] = buf[i];
    }
    bak[i] = '\0';
    printf("bak : %s\n",bak);

    return 0;
}

int i = 0;

char buf[5];

 

//hello  word回车符

for(i = 0;i < sizeof(buf)/sizeof(buf[0]);i ++)

{

scanf("%c",&buf[i]);

if(buf[i] == '\n')

break;

}

 

//此时数组中是否有'\0'字符?

//此时数组中：hello word\n,希望的是hello word\0

buf[i] = '\0';//buf[5] = '\0',buf 数组越界 

 

======================================================================================================

int i = 0;

char buf[5];

 

//hello  word回车符

for(i = 0;i < sizeof(buf)/sizeof(buf[0]) - 1;i++)//最多只能读取4个字符，还需要留一个空间存放'\0'

{

scanf("%c",&buf[i]);

if(buf[i] == '\n')

break;

}

 

//此时数组中是否有'\0'字符?

//此时数组中：hello word\n,希望的是hello word\0

buf[i] = '\0';//'\n' -> '\0'

 

任务:输入字符串到字符数组a中，当用户输入回车符结束输入,将字符数组a中的字符串拷贝到字符数组b

     输出字符数组b [printf("%s\n",b);]

 

例如:

输入的是hello   word回车

 

=======================================================================================================

练习:

char a[] = "hello word";//char a[] = {"hello word"};

char b[1024];

 

给数组b输入字符串，然后将数组a的内容拼接在b数组后面,然后输出数组b

例如:

给b输入的字符串是xyz hij ,拼接之后是:xyz hijhello word 

 

最后统计字符数组b中字符的个数(不包括'\0')

 

#include <stdio.h>

int main()
{
    int i;
    int j;
    int count;
    char b[1024];
    char a[] = "hello word";

    for(i = 0;i < sizeof(b)/sizeof(b[0]) - 1;i ++)
    {
        scanf("%c",&b[i]);
        if(b[i] == '\n')
            break;
    }
    b[i] = '\0';

    printf("b : %s\n",b);

    for(j = 0;a[j] != '\0';j ++)
    {
        b[i] = a[j];
        i ++;
    }
    b[i] = '\0';

    printf("b : %s\n",b);

    for(i = 0,count = 0;b[i] != '\0'; i ++)
    {
        count ++;
    }
    printf("count = %d\n",count);

    return 0;
}

三 冒泡排序和选择排序

 

//冒泡排序

//排序的次数:n个元素需要排n-1次

//排序的过程:第一个和第二个比较，如果第一个大于第二个,则交换,后面依次进行

//每次排序结束的时候，最大数沉底

//每排一次，需要参加比较的元素就少一个[大的数据沉底，不需要参与比较]

#include <stdio.h>

int main()
{
    int count;
    int temp;
    int i = 0;
    int j = 0;
    int a[] = {10,25,8,6,10,22};

    //冒泡排序
    //排序的次数:n个元素需要排n-1次
    //排序的过程:第一个和第二个比较，如果第一个大于第二个,则交换,后面依次进行
    //每次排序结束的时候，最大数沉底
    //每排一次，需要参加比较的元素就少一个[大的数据沉底，不需要参与比较]
    for(i = 0;i < sizeof(a)/sizeof(a[0]) - 1;i ++)
    {
        for(j = 0,count = 0;j < sizeof(a)/sizeof(a[0]) - i - 1;j ++)
        {
            if(a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                count ++;
            }
        }

        if(count == 0)
        {
            printf("i = %d\n",i);
            break;
        }
    }

    for(i = 0;i < sizeof(a)/sizeof(a[0]);i ++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    return 0;
}

for(i = 0;i < sizeof(a)/sizeof(a[0]) - 1;i ++)//控制排序的次数

{

for(j = 0,flag = 0;j < sizeof(a)/sizeof(a[0]) - i - 1;j ++)//控制排序的过程

{

if(a[j] > a[j + 1])

{

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

flag = 1;

}

}

 

if(flag == 0)

{

printf("i = %d\n",i);

break;

}

}

----------------------------------------------------------------------------------------------

 

//选择排序

//假设第i(i从0开始)个元素的是最小的，并且用k记录其下标

//论证假设是否成立:

//   从第i + 1个元素开始，依次比较a[k]的值，判断它是否是最小的，如果不是则更新k的值

//   ,让k记录最小元素的下标 

//

//论证结束后:判断k的值是否改变(k 和i比较),不相等则表示假设不成立，然后交换a[i]和a[k]

//

#include <stdio.h>

int main()
{
    int temp;
    int i,j,k;
    int a[] = {10,20,8,45,7};
    int n = sizeof(a)/sizeof(a[0]);

    //选择排序
    //假设第i(i从0开始)个元素的是最小的，并且用k记录其下标
    //论证假设是否成立:
    // 从第i + 1个元素开始，依次比较a[k]的值，判断它是否是最小的，如果不是则更新k的值
    // ,让k记录最小元素的下标
    //
    //论证结束后:判断k的值是否改变(k 和i比较),不相等则表示假设不成立，然后交换a[i]和a[k]
    //
    for(i = 0;i < n;i ++)
    {
        k = i;

        for(j = i + 1;j < n;j ++)
        {
            if(a[k] > a[j]){
                k = j;
            }
        }

        if(k != i){
            temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }

    for(i = 0;i < n;i ++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    return 0;
}

for(i =  0;i < n;i ++)

{

k = i;

 

for(j = i  + 1;j < n;j ++)

{

if(a[k] > a[j]){

k = j;

}

}

 

if(k != i){

temp = a[k];

a[k] = a[i];

a[i] = temp;

}

}

 

练习:输入一个字符串，然后将字符串中的字符从大到小排列，然后输出这个字符串

练习:输入10个整数，然后分别用冒泡排序(结果:从小到大)和选择排序(结果:从大到小)进行排序

 

 

四  二维数组

 

 

1.定义 

数据类型  数组名[行数][列数];

 

例如:

int  a[3][2];

 

<1>元素个数: 行数 x 列数

<2>数组大小: 元素个数 x 元素的大小 =  行数  x 列数  x 元素的大小  = sizeof(数组名)

<3>成员表示: a[0][0] => 第0行第0个元素  , a[0][1] => 第0行第一个元素 , a[0][2] =>越界

<4>最后一个元素:a[行数 -1][列数-1]

<5>在内存中存放的原则:按行优先存放 

<6>数组名表示数组的起始地址 

 

练习:

1.定义整型 三行三列的二维数组,给它输入值，然后输出对角线元素的值

2.输入行号，则输出对应行元素的值

3.输入列号，则输出对应列元素的值

 

#include <stdio.h>

int main()
{
    int line;
    int column;
    int i = 0;
    int j = 0;
    int a[3][3];

    for(i = 0;i < 3;i ++)
    {
        for(j = 0;j < 3;j ++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    for(i = 0;i < 3;i ++)
    {
        for(j = 0;j < 3;j ++)
        {
            if(i == j || i + j == 2)
            {
                printf("%d ",a[i][j]);
            }
        }
    }
    printf("\n");

again_line:
    printf("Input a line : ");
    scanf("%d",&line);
    if(line < 1 || line > 3)
    {
        printf("Invalid line ,must[1 -3],again!\n");
        goto again_line;
    }

    for(i = 0;i < 3;i ++)
    {
        printf("%d ",a[line - 1][i]);
    }
    printf("\n");

again_column:
    printf("Input a column: ");
    scanf("%d",&column);
    if(column < 1 || column > 3)
    {
        printf("Invalid column ,must[1 -3],again!\n");
        goto again_column;
    }

    for(i = 0;i < 3;i ++)
    {
        printf("%d\n",a[i][column - 1]);
    }

    return 0;
}

 

晚间练习

打印杨辉三角形前10行。（提示：定义数组a[10][10]）

1

1    1

1    2    1

1    3    3    1

1    4    6    4    1

1    5   10   10    5    1

1    6   15   20   15    6    1

1    7   21   35   35   21    7    1

1    8   28   56   70   56   28    8    1

1    9   36   84  126  126   84   36    9    1

#include <stdio.h>

int main()
{
    int i,j;
    int a[10][10] = {0};


#if 0
    for(i = 0;i < 10;i ++)
    {
        a[i][0] = 1;
    }
#endif
//    a[0][0] = 1;

    for(i = 0;i < 10;i ++)
    {
        a[i][0] = 1;

        for(j = 1; j <= i;j ++)
        {
            a[i][j] = a[i-1][j-1] + a[i-1][j];
            //a[2][1] = a[1][0] + a[1][1]
        }
    }

    for(i = 0;i < 10;i ++)
    {
        for(j = 0;j <= i;j ++)
        {
            printf("%-3d ",a[i][j]);
        }
        printf("\n");
    }

    return 0;
}