AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

2023-10-12 343
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 上机实验一 顺序表的基本操作和简单程序 西安石油大学数据结构

上机一

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

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

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 <stdio.h>
#define MAXSIZE 100
typedef int ElemType;  // 假设表中元素类型为int
typedef struct {
    ElemType data[MAXSIZE];  // 存放表中元素的数组
    int length;              // 当前表长
} SqList;

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

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

然后是有序插入元素的函数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;
}

接下来是删除元素的函数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;
}

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

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

在主函数中，先初始化一个有序顺序表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;
}

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

#include <stdio.h>
#include <stdlib.h>
// 定义顺序表结构体
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;
}

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

##　示例代码：

#include <stdio.h>
#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;
}

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

讲解

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

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

#include <stdio.h>
#define MAXSIZE 100
typedef int ElemType;  // 假设表中元素类型为int
typedef struct {
    ElemType data[MAXSIZE];  // 存放表中元素的数组
    int length;              // 当前表长
} SqList;

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

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

然后是有序插入元素的函数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;
}

接下来是删除元素的函数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;
}

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

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

在主函数中，先初始化一个有序顺序表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. 初始化函数InitList(SeqList &L, int maxsize)
  • 参数：L为要初始化的顺序表对象，maxsize为最大容量
  • 功能：通过动态内存分配为顺序表分配一定大小的数组，并将长度和容量初始化为0和maxsize，实现了顺序表的初始化操作。
  1. 插入函数Insert(SeqList &L, int x)
  • 参数：L为目标顺序表对象，x为要插入的元素
  • 返回值：布尔类型，表示插入是否成功
  • 功能：将元素x按照从小到大的顺序插入到顺序表中。首先判断顺序表是否已满，若已满则插入失败；若未满，则从后往前遍历顺序表，找到合适的插入位置，并将比x大的元素向后移动一位，最后将x插入到空出来的位置。
  1. 查找函数Find(SeqList L, int x)
  • 参数：L为目标顺序表对象，x为要查找的元素
  • 返回值：整型，表示元素在表中的位置下标，若找不到则返回-1
  • 功能：在顺序表中查找指定元素x的位置。从表头开始遍历，逐个比较元素的值，直到找到与x相等的元素或遍历到表尾。若找到则返回其位置下标，否则返回-1。
  1. 删除函数Delete(SeqList &L, int x)
  • 参数：L为目标顺序表对象，x为要删除的元素
  • 返回值：布尔类型，表示删除是否成功
  • 功能：在顺序表中查找指定元素x，若找到则删除该元素并保持有序性。首先调用查找函数找到元素x的位置，若找不到则删除失败；若找到，则将该位置后面的元素依次向前移动一位，最后将长度减1，实现了删除操作。
  1. 输出函数Print(SeqList L)
  • 参数：L为目标顺序表对象
  • 功能：按照顺序打印出顺序表中所有的元素。使用循环遍历顺序表中的元素，并逐个输出，以空格分隔。

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

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

关键词：
数据结构顺序表
程序数据结构
数据结构实验
顺序表数据结构
数据结构基本操作
时雨h
目录
相关文章
XIAZHI
|
3月前
|
存储 算法 编译器
数据结构实验之矩阵的运算器（二维数组）
本实验旨在通过团队合作，掌握数组和矩阵相关运算的代码实现，包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中，成员们需分工协作，解决编程难题，最终实现一个功能完备的矩阵计算器。通过本实验，不仅锻炼了编程能力，还加深了对数学概念的理解，同时培养了团队合作精神。
XIAZHI
88 4
XIAZHI
|
3月前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术，通过创建文本文件、实现单词计数与定位功能，最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单，以增强对字符串处理的理解与应用能力。
XIAZHI
81 4
XIAZHI
|
3月前
|
算法
数据结构实验之最长公共子序列
本实验旨在通过编程实践帮助学生理解串的基本概念及求解最长公共子序列的算法。实验内容包括使用动态规划方法设计并实现算法，以找出给定两序列的最大公共子序列。示例代码展示了如何通过构建状态矩阵和回溯路径来找到解决方案。实验总结指出，`memset()`函数用于内存初始化，且对于特定输入，程序能正确输出最长公共子序列之一。
XIAZHI
75 4
XIAZHI
|
3月前
|
算法
数据结构实验之操作系统打印机管理器问题
本实验旨在通过实现操作系统中的打印机管理器问题，掌握队列的基本操作如入队、出队等，利用队列的先进先出特性解决先申请先打印的问题。实验包括队列的初始化、入队、出队、打印队列内容等功能，并通过菜单式界面进行交互。实验结果显示基本功能可正常执行，但在连续操作时存在执行失败的情况，需进一步优化。
XIAZHI
63 4
XIAZHI
|
3月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
81 4
RossyYan
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
本文档介绍了线性表的基本运算任务，涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法，并提供了测试说明和通关代码。 主要内容包括： - **任务描述**：实现顺序表的基本运算。 - **相关知识**：介绍线性表的基本概念及操作，如初始化、销毁、判定是否为空表等。 - **具体操作**：详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法，并附有代码示例。 - **测试说明**：提供测试输入和预期输出，确保代码正确性。 - **通关代码**：给出完整的C++代码实现，帮助完成任务。 文档
RossyYan
41 5
三三是该溜子
|
2月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
55 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
3月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
99 5
土木林森
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
99 1
XIAZHI
|
3月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
128 4

热门文章

最新文章

  • 1
    C 408—《数据结构》易错考点200题（含解析）
  • 2
    C 408—《数据结构》算法题基础篇—链表（下）
  • 3
    C 408—《数据结构》算法题基础篇—链表（上）
  • 4
    C 408—《数据结构》图、查找、排序专题考点（含解析）
  • 5
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
  • 6
    数据结构（C语言）之对归并排序的介绍与理解
  • 7
    c语言及数据结构实现简单贪吃蛇小游戏
  • 8
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
  • 9
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 10
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
  • 1
    c语言及数据结构实现简单贪吃蛇小游戏
    28
  • 2
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
    25
  • 3
    C 408—《数据结构》算法题基础篇—链表（下）
    79
  • 4
    C 408—《数据结构》算法题基础篇—链表（上）
    72
  • 5
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
    58
  • 6
    C 408—《数据结构》图、查找、排序专题考点（含解析）
    69
  • 7
    C 408—《数据结构》易错考点200题（含解析）
    92
  • 8
    数据结构（C语言）之对归并排序的介绍与理解
    36
  • 9
    Go语言中的map数据结构是如何实现的？
    55
  • 10
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
    142

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄
    • 下一篇
    阿里云oss简介和如何对接使用