• 线性表顺序表综合应用题P18

    线性表顺序表综合应用题P18

    第一题

    从顺序表中删除具有最小值的元素（假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

    核心代码

    bool deleteMin(SqList &L,int &min) {
    if (L.length == 0) return false;
    min = L.data[0];	 //记录最小数值
    int index = 0;  	//记录最小数值的索引
    for (int i = 1; i < L.length; i++) {	//输出最小值
        if (L.data[i] < min) {
            min = L.data[i];
            index = i;
        }
    }
    L.data[index] = L.data[L.length-1];		//用最后一个元素替换最小值
    L.length--;
    return true;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 13:53
 * @ClassName: test01
 * @Description:从顺序表中删除具有最小值的元素（假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
 */
#include "stdio.h"

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

bool deleteMin(SqList &L,int &min) {
    if (L.length == 0) return false;
    min = L.data[0]; //记录最小数值
    int index = 0;  //记录最小数值的索引
    //输出最小值
    for (int i = 1; i < L.length; i++) {
        if (L.data[i] < min) {
            min = L.data[i];
            index = i;
        }
    }
    printf("最小值data[%d]为: %d\n", index, min);
    //用最后一个元素替换最小值
    L.data[index] = L.data[L.length-1];
    L.length--;
    /*if (index==L.length-1) L.length--;  //判断最小值是否为最后一个值
    else {
        L.data[index] = L.data[L.length-1];
        L.length--;
    }*/
    return true;

}

int main() {
    SqList L;
    InitList(L);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 5; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    //执行
    int min = -1;
    deleteMin(L, min);

    printf("执行后：\n");
    printf("最小值为: %d\n",min);
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises01.exe
22 5 1 6 9
执行前：
data[0]=22
data[1]=5
data[2]=1
data[3]=6
data[4]=9
最小值data[2]为: 1
执行后：
最小值为: 1
data[0]=22
data[1]=5
data[2]=9
data[3]=6

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    第二题

    设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

    核心代码

    void reverseList(SqList &L) {
    int num = L.length / 2;
    for (int i = 0, j = L.length - 1; i < num; i++, j--) {
        int temp = L.data[i];   //定义一个临时变量, 交换值
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 15:09
 * @ClassName: test02
 * @Description: 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
 */
#include "stdio.h"

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

void reverseList(SqList &L) {
    int num = L.length / 2;
    for (int i = 0, j = L.length - 1; i < num; i++, j--) {
        int temp = L.data[i];   //定义一个临时变量, 交换值
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
}

int main() {
    SqList L;
    InitList(L);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 6; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    //执行
    reverseList(L);

    printf("执行后：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises02.exe
1 6 5 4 9 8
执行前：
data[0]=1
data[1]=6
data[2]=5
data[3]=4
data[4]=9
data[5]=8
执行后：
data[0]=8
data[1]=9
data[2]=4
data[3]=5
data[4]=6
data[5]=1

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    第三题

    对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

    核心代码

    void deleteList(SqList &L, int x) {
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (x != L.data[i]) {
            L.data[k++] = L.data[i];    //将不等于x的元素移动到下标k的位置
        }
    }
    L.length = k;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 15:56
 * @ClassName: test03
 * @Description: 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
 */
#include "stdio.h"

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

//可以  但是时间复杂度不是O(n)
/*void deleteList(SqList &L, int x) {
    for (int i = 0; i < L.length; i++) {
        if (x == L.data[i]) {
            for (int j = i; j < L.length; j++) {
                L.data[j] = L.data[j+1];
            }
            L.length--;
        }
    }
}*/
void deleteList(SqList &L, int x) {
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (x != L.data[i]) {
            L.data[k++] = L.data[i];    //将不等于x的元素移动到下标k的位置
        }
    }
    L.length = k;
}

int main() {
    SqList L;
    InitList(L);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 8; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    //执行
    deleteList(L, 5);

    printf("执行后：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises03.exe
5 6 5 2 8 5 5 4 9
执行前：
data[0]=5
data[1]=6
data[2]=5
data[3]=2
data[4]=8
data[5]=5
data[6]=5
data[7]=4
执行后：
data[0]=6
data[1]=2
data[2]=8
data[3]=4

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    第四题

    从有序顺序表中删除其值在给定值s与t之间(要求s <t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

    核心代码

    bool deleteList(SqList &L, int min, int max) {
    if (min >= max) return false;
    if (L.length == 0) return false;
    int i, j;
    for (i = 0; i < L.length && L.data[i] < min; i++);//找出第一个小于min的数
    if (i >= L.length) return false;
    for (j = i; j < L.length && L.data[j] <= max; j++);//找出第一个大于max的数
    for (; j < L.length; i++, j++) {    //前移, 补充前面被删除的元素
        L.data[i] = L.data[j];
    }
    L.length = i;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 16:37
 * @ClassName: test04
 * @Description: 从有序顺序表中删除其值在给定值s与t之间(要求s <t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
 */
#include "stdio.h"

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

//有序顺序表
bool deleteList(SqList &L, int min, int max) {
    if (min >= max) return false;
    if (L.length == 0) return false;
    int i, j;
    for (i = 0; i < L.length && L.data[i] < min; i++);//找出第一个小于min的数
    if (i >= L.length) return false;
    for (j = i; j < L.length && L.data[j] <= max; j++);//找出第一个大于max的数
    for (; j < L.length; i++, j++) {    //前移, 补充前面被删除的元素
        L.data[i] = L.data[j];
    }
    L.length = i;
    return true;
}

int main() {
    SqList L;
    InitList(L);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 8; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    //执行
    deleteList(L, 3, 6);

    printf("执行后：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises04.exe
1 2 3 4 5 6 7 8
执行前：
data[0]=1
data[1]=2
data[2]=3
data[3]=4
data[4]=5
data[5]=6
data[6]=7
data[7]=8
执行后：
data[0]=1
data[1]=2
data[2]=7
data[3]=8

Process finished with exit code 0


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    第五题

    从顺序表中删除其值在给定值s与t之间(包含s和t，要求s <t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

    核心代码

    //无序顺序表可以这样做
bool deleteList(SqList &L, int min, int max) {
    if (min >= max) return false;
    if (L.length == 0) return false;
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] < min || L.data[i] > max) {
            L.data[k++] = L.data[i];    //将不等于x的元素移动到下标k的位置
        }
    }
    L.length = k;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 18:22
 * @ClassName: test05
 * @Description: 从顺序表中删除其值在给定值s与t之间(包含s和t，要求s <t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
 */

#include "stdio.h"

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

//无序顺序表可以这样做
bool deleteList(SqList &L, int min, int max) {
    if (min >= max) return false;
    if (L.length == 0) return false;
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] < min || L.data[i] > max) {
            L.data[k++] = L.data[i];    //将不等于x的元素移动到下标k的位置
        }
    }
    L.length = k;
    return true;
}

int main() {
    SqList L;
    InitList(L);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 8; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    //执行
    deleteList(L, 3, 6);

    printf("执行后：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises05.exe
3 5 6 2 8 7 4 9
执行前：
data[0]=3
data[1]=5
data[2]=6
data[3]=2
data[4]=8
data[5]=7
data[6]=4
data[7]=9
执行后：
data[0]=2
data[1]=8
data[2]=7
data[3]=9

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    第六题

    从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

    核心代码

    bool deleteListSame(SqList &L) {
    if (L.length == 0)return false;
    int i, j;   //i存储第一个不同的值, j作为工作指针
    for (i = 0, j = 1; j < L.length; j++)
        if (L.data[i] != L.data[j]) //查找下个元素与上个元素值不同的元素
            L.data[++i] = L.data[j];
    L.length = i + 1;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 18:27
 * @ClassName: test06
 * @Description: 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
 */

#include "stdio.h"

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

bool deleteListSame(SqList &L) {
    if (L.length == 0)return false;
    int i, j;   //i存储第一个不同的值, j作为工作指针
    for (i = 0, j = 1; j < L.length; j++)
        if (L.data[i] != L.data[j]) //查找下个元素与上个元素值不同的元素
            L.data[++i] = L.data[j];
    L.length = i + 1;
    return true;
}

int main() {
    SqList L;
    InitList(L);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 8; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    //执行
    deleteListSame(L);

    printf("执行后：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises06.exe
1 1 2 33 5 44 6 6
执行前：
data[0]=1
data[1]=1
data[2]=2
data[3]=33
data[4]=5
data[5]=44
data[6]=6
data[7]=6
执行后：
data[0]=1
data[1]=2
data[2]=33
data[3]=5
data[4]=44
data[5]=6

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    第七题

    将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

    核心代码

    bool Merge(SqList L, SqList R, SqList &H) {
    if (L.length + R.length > MaxSize) return false;
    int i = 0, j = 0, k = 0;
    while (i < L.length && j < R.length) {  //两两比较, 小的存入新的表
        if (L.data[i] <= R.data[j])
            H.data[k++] = L.data[i++];
        else
            H.data[k++] = R.data[j++];
    }
    while (i < L.length) H.data[k++] = L.data[i++]; //剩下一个没有比完的顺序表
    while (j < R.length) H.data[k++] = R.data[j++];
    H.length = k;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 18:50
 * @ClassName: test07
 * @Description: 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
 */
#include "stdio.h"

#define MaxSize 20
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;        //将所有数据元素设置为默认初始值
    L.length = 0;            //顺序表初始长度为0 ！！！！这步很重要！！！！
}

bool Merge(SqList L, SqList R, SqList &H) {
    if (L.length + R.length > MaxSize) return false;
    int i = 0, j = 0, k = 0;
    while (i < L.length && j < R.length) {  //两两比较, 小的存入新的表
        if (L.data[i] <= R.data[j])
            H.data[k++] = L.data[i++];
        else
            H.data[k++] = R.data[j++];
    }
    while (i < L.length) H.data[k++] = L.data[i++]; //剩下一个没有比完的顺序表
    while (j < R.length) H.data[k++] = R.data[j++];
    H.length = k;
    return true;
}

int main() {
    SqList L, R, H;
    InitList(L);
    InitList(R);
    InitList(H);
    //赋初始值  设置顺序表前5个元素的值
    int num;
    for (int i = 0; i < 7; i++) {
        scanf("%d", &num);
        L.data[i] = num;
        L.length++;
    }
    for (int i = 0; i < 5; i++) {
        scanf("%d", &num);
        R.data[i] = num;
        R.length++;
    }
    printf("执行前：\n");
    for (int i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }
    for (int i = 0; i < R.length; i++) {
        printf("data[%d]=%d\n", i, R.data[i]);
    }

    //执行
    Merge(L, R, H);

    printf("执行后：\n");
    for (int i = 0; i < H.length; i++) {
        printf("data[%d]=%d\n", i, H.data[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises07.exe
1 2 3 4 5 6 7
1 2 3 4 5
执行前：
data[0]=1
data[1]=2
data[2]=3
data[3]=4
data[4]=5
data[5]=6
data[6]=7
data[0]=1
data[1]=2
data[2]=3
data[3]=4
data[4]=5
执行后：
data[0]=1
data[1]=1
data[2]=2
data[3]=2
data[4]=3
data[5]=3
data[6]=4
data[7]=4
data[8]=5
data[9]=5
data[10]=6
data[11]=7

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    第八题

    已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3…, am)和(b1, b2, b3.…, bn)编写一个函数，将数组中两个顺序表的位置互换，即将(b1, b2, b3,…, bn)放在(a1, a2, a3,…, am)的前面。

    思想: 算法思想:先将数组A[m+n]中的全部元素(a1,a2,a3.…“, am, b1, b2, b3,…, bn)原地逆置为(bn, bn-l,bn-2.…”, b1, am am-l,am-2, a1),再对前n个元素和后m个元素分别使用逆置算法，即可得到(b1,b2,b3,…, bn, a1, a2, a3,…, am)，从而实现顺序表的位置互换。

    核心代码1

    void Reverse(int Array[], int left, int right, int arraySize) {
    int mid = (left + right) / 2;
    for (int i = 0; i <= mid - left; i++) {
        int temp = Array[left + i];
        Array[left + i] = Array[right - i];
        Array[right - i] = temp;
    }
    printf("打印输出交换后的结果");
    for (int i = 0; i < arraySize; i++) {
        printf("%d\t", Array[i]);
    }
    printf("\n");
}

void Exchange(int Array[], int m, int n, int arraySize) {
    Reverse(Array, 0, m + n - 1, arraySize);
    Reverse(Array, 0, n - 1, arraySize);
    Reverse(Array, n, m + n - 1, arraySize);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 21:03
 * @ClassName: test08
 * @Description: 已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3…, am)和(b1, b2, b3.…, bn)编写一个函数，
 *              将数组中两个顺序表的位置互换，即将(b1, b2, b3,…, bn)放在(a1, a2, a3,…, am)的前面。
 */
#include "stdio.h"

void Reverse(int Array[], int left, int right, int arraySize) {
    int mid = (left + right) / 2;
    for (int i = 0; i <= mid - left; i++) {
        int temp = Array[left + i];
        Array[left + i] = Array[right - i];
        Array[right - i] = temp;
    }
    printf("打印输出交换后的结果");
    for (int i = 0; i < arraySize; i++) {
        printf("%d\t", Array[i]);
    }
    printf("\n");
}

void Exchange(int Array[], int m, int n, int arraySize) {
    Reverse(Array, 0, m + n - 1, arraySize);
    Reverse(Array, 0, n - 1, arraySize);
    Reverse(Array, n, m + n - 1, arraySize);
}


int main() {
    int Array[10] = {11, 12, 13, 14, 15, 21, 22, 23, 24};
    Exchange(Array, 5, 4, 9);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises08.exe
打印输出交换后的结果24	23	22	21	15	14	13	12	11	
打印输出交换后的结果21	22	23	24	15	14	13	12	11	
打印输出交换后的结果21	22	23	24	11	12	13	14	15	

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    思想: 将一半存入一个临时的数组中

    核心代码2

    void Reverse(int Array[], int left, int right, int arraySize) {
    int temp[left], t1 = left, t2 = right;
    for (int i = 0; i < left; i++) {	//将左半部分的线性表复制到临时的temp数组中
        temp[i] = Array[i];
    }

    for (int i = 0; i < right; i++) {	//将右半部分的线性表复制到Array数组的首位
        Array[i] = Array[t1++];
    }

    for (int i = 0; i < left; i++) {	//将临时temp数组中也就是左半部分线性表跟在右半部分的后面
        Array[t2++] = temp[i];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    完整代码

    /**
 * @Author JiaHaoHao
 * @Date 2022/06/27 21:34
 * @ClassName: test09
 * @Description: 已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3…, am)和(b1, b2, b3.…, bn)编写一个函数，
 *              将数组中两个顺序表的位置互换，即将(b1, b2, b3,…, bn)放在(a1, a2, a3,…, am)的前面。
 */
#include "stdio.h"

void Reverse(int Array[], int left, int right, int arraySize) {
    int temp[left], t1 = left, t2 = right;
    for (int i = 0; i < left; i++) {
        temp[i] = Array[i];
    }
    printf("temp打印结果");
    for (int i = 0; i < left; i++) {
        printf("%d\t", temp[i]);
    }
    printf("\n");

    /*for (int i = left; i < arraySize; i++) {
        int j = 0;
        Array[j++] = Array[i];
    }*/

    for (int i = 0; i < right; i++) {
        Array[i] = Array[t1++];
    }

    printf("打印输出交换后的结果");
    for (int i = 0; i < arraySize; i++) {
        printf("%d\t", Array[i]);
    }
    printf("\n");


    for (int i = 0; i < left; i++) {
        Array[t2++] = temp[i];
    }

    printf("打印输出交换后的结果");
    for (int i = 0; i < arraySize; i++) {
        printf("%d\t", Array[i]);
    }
    printf("\n");
}

int main() {
    int Array[10] = {11, 12, 13, 14, 15, 21, 22, 23, 24};
    Reverse(Array, 5, 4, 9);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    运行结果

    C:\Users\User\Desktop\dataStructure\cmake-build-debug\exercises09.exe
temp打印结果11	12	13	14	15	
打印输出交换后的结果21	22	23	24	15	21	22	23	24	
打印输出交换后的结果21	22	23	24	11	12	13	14	15	

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
  • 相关阅读:
    MySQL-七种SQL优化
    计算机网络常见概念
    elasticsearch快速应用于SpringBoot
    LVS负载均衡集群
    Verilog实战学习到RiscV - 4 ： ICEStick 评估板计数器
    38、HTML进阶——SVG
    Tomcat部署及优化
    web3.0时代分布式网络协议的异同
    golang的问题2
    数据库&SQL
  • 原文地址：https://blog.csdn.net/qq_46036214/article/details/125493532