• 上机实验一 顺序表的基本操作和简单程序 西安石油大学数据结构

    上机一

    实验名称：顺序表的基本操作和简单程序

    题目：设计一个有序顺序表，实现以下操作：

    1.将元素x插入表中并保持有序；

    2.查找值为x的元素，若找到则将其删除；

    3.输出表中所有元素。

    要求：对上述每个操作各设计为一个子函数，并设计一个主函数调用各子函数，以验证所设计的有序顺序表的正确性。

    分析：

    题目分析：

    这道题要求我们设计一个有序顺序表，然后实现三个基本操作：插入、删除和输出。其中，插入和删除要求保持表的有序性。具体来说，插入是要把新元素按序插入到合适的位置，而删除是要在表中查找到指定元素并删除它。最后，输出操作需要打印所有的元素，以验证表的正确性。

    解题思路：

    1.定义一个结构体，表示顺序表，包括数据元素、当前长度和最大容量等属性。

    2.定义一个初始化函数，用于初始化顺序表。

    3.定义一个插入函数，用于将给定元素按序插入到顺序表中。

    4.定义一个查找函数，用于查找指定元素在表中的位置，并返回该位置的下标。

    5.定义一个删除函数，用于删除指定元素，并保持表的有序性。

    6.定义一个输出函数，用于按顺序打印所有元素。

    7.在主函数中，创建一个顺序表对象，并依次调用插入、删除和输出等操作函数，以验证其正确性。

    伪代码：

    1.定义结构体SeqList，表示顺序表
    struct SeqList {
    int *data; // 数据元素
    int length; // 当前长度
    int capacity; // 最大容量
    };

    2.定义初始化函数InitList
    void InitList(SeqList &L, int maxsize) {
    L.data = new int[maxsize];
    L.length = 0;
    L.capacity = maxsize;
    }

    3.定义插入函数Insert
    bool Insert(SeqList &L, int x) {
    if (L.length == L.capacity) return false; // 表满，插入失败
    int i = L.length - 1; // 从后往前查找插入位置
    while (i >= 0 && L.data[i] > x) {
    L.data[i + 1] = L.data[i];
    i–;
    }
    L.data[i + 1] = x;
    L.length++;
    return true;
    }

    4.定义查找函数Find
    int Find(SeqList L, int x) {
    int i = 0;
    while (i < L.length && L.data[i] != x) {
    i++;
    }
    return i < L.length ? i : -1;
    }

    5.定义删除函数Delete
    bool Delete(SeqList &L, int x) {
    int pos = Find(L, x);
    if (pos == -1) return false; // 找不到指定元素，删除失败
    for (int i = pos + 1; i < L.length; i++) {
    L.data[i - 1] = L.data[i];
    }
    L.length–;
    return true;
    }

    6.定义输出函数Print
    void Print(SeqList L) {
    for (int i = 0; i < L.length; i++) {
    cout << L.data[i] << " ";
    }
    cout << endl;
    }

    7.在主函数中，依次调用以上定义的函数，以实现测试。

    代码示例

    这段代码定义了一个有序顺序表的数据结构SqList，并实现了初始化、插入元素、删除元素和输出所有元素等操作。具体来说，代码分为以下几个部分：

    首先定义了MAXSIZE常量表示顺序表的最大长度，以及ElemType类型表示顺序表中元素的类型，这里假设为int类型。

    #include 
#define MAXSIZE 100

typedef int ElemType;  // 假设表中元素类型为int

typedef struct {
    ElemType data[MAXSIZE];  // 存放表中元素的数组
    int length;              // 当前表长
} SqList;

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

    接着实现了初始化有序顺序表的函数InitList，将length赋值为0。

    void InitList(SqList *L) {
    L->length = 0;
}

    • 1
    • 2
    • 3

    然后是有序插入元素的函数InsertElement，先判断顺序表是否已满，若已满则返回0表示插入失败；否则在合适的位置插入元素，并将length加1，最终返回1表示插入成功。

    int InsertElement(SqList *L, ElemType x) {
    if (L->length == MAXSIZE)  // 表满
        return 0;
    int i, j;
    for (i = 0; i < L->length && L->data[i] < x; i++);
    for (j = L->length - 1; j >= i; j--)
        L->data[j+1] = L->data[j];
    L->data[i] = x;
    L->length++;
    return 1;
}

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

    接下来是删除元素的函数DeleteElement，先判断顺序表是否为空，若为空则返回0表示删除失败；否则在顺序表中查找值为x的元素，若找到则删除并将length减1，最终返回1表示删除成功。

    int DeleteElement(SqList *L, ElemType x) {
    if (L->length == 0)  // 空表
        return 0;
    int i, j;
    for (i = 0; i < L->length && L->data[i] < x; i++);
    if (i >= L->length || L->data[i] > x)  // 未找到
        return 0;
    for (j = i; j < L->length - 1; j++)
        L->data[j] = L->data[j+1];
    L->length--;
    return 1;
}

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

    最后是输出所有元素的函数PrintList，遍历顺序表中所有元素，逐个输出，并在最后加上换行符。

    void PrintList(SqList L) {
    int i;
    for (i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");
}

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

    在主函数中，先初始化一个有序顺序表L，然后插入4个元素，并输出顺序表中所有元素。接着删除元素4并输出，然后尝试删除一个不存在的元素5并输出，最后再次输出顺序表中所有元素。

    int main() {
    SqList L;
    InitList(&L);
    InsertElement(&L, 3);
    InsertElement(&L, 1);
    InsertElement(&L, 4);
    InsertElement(&L, 2);
    printf("Insert 3, 1, 4, 2 in order: ");
    PrintList(L);
    DeleteElement(&L, 4);
    printf("Delete 4: ");
    PrintList(L);
    DeleteElement(&L, 5);
    printf("Delete 5: ");
    PrintList(L);
    printf("All elements: ");
    PrintList(L);
    return 0;
}

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

    下面是一个基于顺序表的有序操作的示例程序：

    #include 
#include 

// 定义顺序表结构体
typedef struct {
    int *data;      // 存储数据的数组
    int length;     // 顺序表长度
    int capacity;   // 数组最大容量
} ArrayList;

// 初始化顺序表
void init_list(ArrayList *list, int capacity) {
    list->data = (int *) malloc(sizeof(int) * capacity);
    list->length = 0;
    list->capacity = capacity;
}

// 插入元素并保持有序
void insert(ArrayList *list, int x) {
    int i = 0;
    while (i < list->length && list->data[i] < x) {
        i++;
    }

    for (int j = list->length; j > i; j--) {
        list->data[j] = list->data[j - 1];
    }

    list->data[i] = x;
    list->length++;
}

// 查找值为x的元素并删除
void delete(ArrayList *list, int x) {
    int i;
    for (i = 0; i < list->length; i++) {
        if (list->data[i] == x) {
            break;
        }
    }

    if (i == list->length) {
        printf("未找到该元素！\n");
    } else {
        for (int j = i; j < list->length - 1; j++) {
            list->data[j] = list->data[j + 1];
        }
        list->length--;
        printf("删除成功！\n");
    }
}

// 输出表中所有元素
void print_all(ArrayList *list) {
    for (int i = 0; i < list->length; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    ArrayList list;
    int capacity, num;

    printf("请输入顺序表的容量：");
    scanf("%d", &capacity);

    init_list(&list, capacity);

    printf("请输入一组有序整数序列（以空格分隔）：");
    for (int i = 0; i < capacity; i++) {
        scanf("%d", &num);
        insert(&list, num);
    }

    printf("插入后的有序列表：");
    print_all(&list);

    printf("请输入要删除的元素：");
    scanf("%d", &num);
    delete(&list, num);

    printf("删除后的有序列表：");
    print_all(&list);

    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
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88

    你可以将以上代码保存为一个.c文件，并编译运行来验证顺序表的正确性。在程序运行过程中，首先输入顺序表的容量，然后输入一组有序整数序列，程序会依次将其插入顺序表中，并输出插入后的列表。然后输入要删除的元素，程序会在顺序表中查找并删除该元素，并输出删除后的列表。

    ##　示例代码：

    #include 
#define MAXSIZE 100

typedef int ElemType;  // 假设表中元素类型为int

typedef struct {
    ElemType data[MAXSIZE];  // 存放表中元素的数组
    int length;              // 当前表长
} SqList;

// 初始化有序顺序表
void InitList(SqList *L) {
    L->length = 0;
}

// 在有序顺序表中插入元素并保持有序
int InsertElement(SqList *L, ElemType x) {
    if (L->length == MAXSIZE)  // 表满
        return 0;
    int i, j;
    for (i = 0; i < L->length && L->data[i] < x; i++);
    for (j = L->length - 1; j >= i; j--)
        L->data[j+1] = L->data[j];
    L->data[i] = x;
    L->length++;
    return 1;
}

// 在有序顺序表中查找值为x的元素并删除
int DeleteElement(SqList *L, ElemType x) {
    if (L->length == 0)  // 空表
        return 0;
    int i, j;
    for (i = 0; i < L->length && L->data[i] < x; i++);
    if (i >= L->length || L->data[i] > x)  // 未找到
        return 0;
    for (j = i; j < L->length - 1; j++)
        L->data[j] = L->data[j+1];
    L->length--;
    return 1;
}

// 输出有序顺序表中所有元素
void PrintList(SqList L) {
    int i;
    for (i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");
}

// 主函数进行各子函数的测试
int main() {
    SqList L;
    InitList(&L);
    InsertElement(&L, 3);
    InsertElement(&L, 1);
    InsertElement(&L, 4);
    InsertElement(&L, 2);
    printf("Insert 3, 1, 4, 2 in order: ");
    PrintList(L);
    DeleteElement(&L, 4);
    printf("Delete 4: ");
    PrintList(L);
    DeleteElement(&L, 5);
    printf("Delete 5: ");
    PrintList(L);
    printf("All elements: ");
    PrintList(L);
    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

    在主函数中，测试完删除元素操作后，我添加了一个输出表中所有元素的代码行：printf("All elements: "); PrintList(L);。这样就可以在测试完整个程序后，输出有序顺序表中的所有元素了。

    讲解

    这段代码定义了一个有序顺序表的数据结构SqList，并实现了初始化、插入元素、删除元素和输出所有元素等操作。具体来说，代码分为以下几个部分：

    首先定义了MAXSIZE常量表示顺序表的最大长度，以及ElemType类型表示顺序表中元素的类型，这里假设为int类型。

    #include 
#define MAXSIZE 100

typedef int ElemType;  // 假设表中元素类型为int

typedef struct {
    ElemType data[MAXSIZE];  // 存放表中元素的数组
    int length;              // 当前表长
} SqList;

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

    接着实现了初始化有序顺序表的函数InitList，将length赋值为0。

    void InitList(SqList *L) {
    L->length = 0;
}

    • 1
    • 2
    • 3

    然后是有序插入元素的函数InsertElement，先判断顺序表是否已满，若已满则返回0表示插入失败；否则在合适的位置插入元素，并将length加1，最终返回1表示插入成功。

    int InsertElement(SqList *L, ElemType x) {
    if (L->length == MAXSIZE)  // 表满
        return 0;
    int i, j;
    for (i = 0; i < L->length && L->data[i] < x; i++);
    for (j = L->length - 1; j >= i; j--)
        L->data[j+1] = L->data[j];
    L->data[i] = x;
    L->length++;
    return 1;
}

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

    接下来是删除元素的函数DeleteElement，先判断顺序表是否为空，若为空则返回0表示删除失败；否则在顺序表中查找值为x的元素，若找到则删除并将length减1，最终返回1表示删除成功。

    int DeleteElement(SqList *L, ElemType x) {
    if (L->length == 0)  // 空表
        return 0;
    int i, j;
    for (i = 0; i < L->length && L->data[i] < x; i++);
    if (i >= L->length || L->data[i] > x)  // 未找到
        return 0;
    for (j = i; j < L->length - 1; j++)
        L->data[j] = L->data[j+1];
    L->length--;
    return 1;
}

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

    最后是输出所有元素的函数PrintList，遍历顺序表中所有元素，逐个输出，并在最后加上换行符。

    void PrintList(SqList L) {
    int i;
    for (i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");
}

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

    在主函数中，先初始化一个有序顺序表L，然后插入4个元素，并输出顺序表中所有元素。接着删除元素4并输出，然后尝试删除一个不存在的元素5并输出，最后再次输出顺序表中所有元素。

    int main() {
    SqList L;
    InitList(&L);
    InsertElement(&L, 3);
    InsertElement(&L, 1);
    InsertElement(&L, 4);
    InsertElement(&L, 2);
    printf("Insert 3, 1, 4, 2 in order: ");
    PrintList(L);
    DeleteElement(&L, 4);
    printf("Delete 4: ");
    PrintList(L);
    DeleteElement(&L, 5);
    printf("Delete 5: ");
    PrintList(L);
    printf("All elements: ");
    PrintList(L);
    return 0;
}

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

    详细分析每个函数的实现

    1. 初始化函数 InitList(SeqList &L, int maxsize)

      • 参数：L为要初始化的顺序表对象，maxsize为最大容量
      • 功能：通过动态内存分配为顺序表分配一定大小的数组，并将长度和容量初始化为0和maxsize，实现了顺序表的初始化操作。

    2. 插入函数 Insert(SeqList &L, int x)

      • 参数：L为目标顺序表对象，x为要插入的元素
      • 返回值：布尔类型，表示插入是否成功
      • 功能：将元素x按照从小到大的顺序插入到顺序表中。首先判断顺序表是否已满，若已满则插入失败；若未满，则从后往前遍历顺序表，找到合适的插入位置，并将比x大的元素向后移动一位，最后将x插入到空出来的位置。

    3. 查找函数 Find(SeqList L, int x)

      • 参数：L为目标顺序表对象，x为要查找的元素
      • 返回值：整型，表示元素在表中的位置下标，若找不到则返回-1
      • 功能：在顺序表中查找指定元素x的位置。从表头开始遍历，逐个比较元素的值，直到找到与x相等的元素或遍历到表尾。若找到则返回其位置下标，否则返回-1。

    4. 删除函数 Delete(SeqList &L, int x)

      • 参数：L为目标顺序表对象，x为要删除的元素
      • 返回值：布尔类型，表示删除是否成功
      • 功能：在顺序表中查找指定元素x，若找到则删除该元素并保持有序性。首先调用查找函数找到元素x的位置，若找不到则删除失败；若找到，则将该位置后面的元素依次向前移动一位，最后将长度减1，实现了删除操作。

    5. 输出函数 Print(SeqList L)

      • 参数：L为目标顺序表对象
      • 功能：按照顺序打印出顺序表中所有的元素。使用循环遍历顺序表中的元素，并逐个输出，以空格分隔。

    在主函数中，我们创建了一个顺序表对象L，并调用了上述定义的函数进行插入、删除和输出操作，以验证函数的正确性。首先使用插入函数将一些元素按序插入到顺序表中，然后使用输出函数打印出插入元素后的有序表。接着使用删除函数删除指定元素，并再次使用输出函数打印出删除元素后的有序表。最终，程序执行完毕。

    这样，我们就实现了一个有序顺序表，并通过插入、删除和输出操作验证了其正确性。

    在这里插入图片描述

  • 相关阅读:
    vue中el-button防止重复点击
    Mysql索引详解（图文并茂）
    github访问不进去，浏览器证书不安全，访问失败，证书失效，证书颁发者为VMware，谷歌浏览器小bug
    Unity --- 射线检测
    Spring Data REST 敏感信息泄露漏洞
    linux下的文件重命名
    MySQL用户管理
    不小心删除了docker/overlay2怎么办？
    cv2.dnn.readNetFromONNX读取yolov8的onnx报错解决过程
    windows部署python项目(以Flask为例)到docker，通过脚本一键生成dockerfile并构建镜像启动容器
  • 原文地址：https://blog.csdn.net/shaozheng0503/article/details/133375605