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

news/2024/10/18 6:07:01/

上机一

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

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

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 100typedef int ElemType;  // 假设表中元素类型为inttypedef 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 100typedef int ElemType;  // 假设表中元素类型为inttypedef 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 100typedef int ElemType;  // 假设表中元素类型为inttypedef 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，实现了顺序表的初始化操作。

  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，并调用了上述定义的函数进行插入、删除和输出操作，以验证函数的正确性。首先使用插入函数将一些元素按序插入到顺序表中，然后使用输出函数打印出插入元素后的有序表。接着使用删除函数删除指定元素，并再次使用输出函数打印出删除元素后的有序表。最终，程序执行完毕。

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

在这里插入图片描述


http://www.ppmy.cn/news/1132012.html

相关文章

【C++历险记】国庆专辑---探索多态迷宫的代码之旅！

【C++历险记】国庆专辑---探索多态迷宫的代码之旅！

本篇目录 一、什么是多态&#xff1f;二、多态的定义及其实现2.1多态构成的条件2.2虚函数2.3虚函数的重写2.3.1析构函数的重写 2.4C11 override 和 final2.5重载、覆盖(重写)、隐藏(重定义)的对比2.6为什么不能是子类的指针或者引用呢&#xff1f;2.7为什么不能是父类对象呢&am…
阅读更多...
Java基础---第十篇

Java基础---第十篇

系列文章目录 文章目录 系列文章目录一、说说Java 中 IO 流二、 Java IO与 NIO的区别（补充）三、java反射的作用于原理一、说说Java 中 IO 流 Java 中 IO 流分为几种? 按照流的流向分，可以分为输入流和输出流； 按照操作单元划分，可以划分为字节流和字符流； 按照流的角色…
阅读更多...
【笔试强训day02】倒置字符串 排序子序列

【笔试强训day02】倒置字符串 排序子序列

​&#x1f47b;内容专栏&#xff1a; 笔试强训集锦 &#x1f428;本文概括&#xff1a;C笔试强训day02。 &#x1f43c;本文作者&#xff1a; 阿四啊 &#x1f438;发布时间&#xff1a;2023.10.1 二、day02 1.倒置字符串 题目描述&#xff1a; 将一句话的单词进行倒置&…
阅读更多...
网络安全——自学(黑客)方法

网络安全——自学(黑客)方法

如果你想自学网络安全&#xff0c;首先你必须了解什么是网络安全&#xff01;&#xff0c;什么是黑客&#xff01;&#xff01; 1.无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防两面性&#xff0c;例如 Web 安全技术&#xff0c;既有 Web 渗透2.也有 Web 防…
阅读更多...
CocosCreator3.8研究笔记（二十四）CocosCreator 动画系统-动画编辑器实操-关键帧实现动态水印动画效果

CocosCreator3.8研究笔记（二十四）CocosCreator 动画系统-动画编辑器实操-关键帧实现动态水印动画效果

上一篇&#xff0c;我们介绍了动画编辑器相关功能面板说明&#xff0c;感兴趣的朋友可以前往阅读&#xff1a; CocosCreator3.8研究笔记&#xff08;二十三&#xff09;CocosCreator 动画系统-动画编辑器相关功能面板说明。 熟悉了动画编辑器的基础操作&#xff0c;那么再使用动…
阅读更多...
PgSQL-内核特性-TupleTableSlotOps

PgSQL-内核特性-TupleTableSlotOps

PgSQL-内核特性-TupleTableSlotOps 执行器中表达式结果、函数结果、投影结果等&#xff0c;各种结果都需要以元组的形式返回&#xff0c;所以PgSQL引入了一种通用格式保存数据&#xff1a;TupleTableSlot。PgSQL执行器将记录存储到“元组表”中在各个算子之间进行传递&#xff…
阅读更多...
剖析华为云Astro Platform技术价值与使用体验

剖析华为云Astro Platform技术价值与使用体验

面对企业IT专业人员紧缺的挑战&#xff0c;华为云Astro低代码平台提供创新解决方案。让非编程专业人士能快速构建、部署应用&#xff0c;缓解开发资源压力&#xff0c;并高度整合技术架构&#xff0c;强化项目沟通协作。使每个参与其中的角色都找到自己的位置&#xff0c;携手全…
阅读更多...
工信部：杭州亚运会开幕式首创 5G 超密组网方案，场馆网络无缝覆盖

工信部：杭州亚运会开幕式首创 5G 超密组网方案，场馆网络无缝覆盖

“工信 V 报”今日发布消息称&#xff0c;工信部经过精心统筹、周密部署&#xff0c;举全系统之力圆满完成了杭州亚运会开幕式各项保障任务。 据介绍&#xff0c;亚运会的指挥调度、安全保卫、通信网络、计时记分、电视转播等系统顺畅运行&#xff0c;对无线电安全、信息通信服…
阅读更多...
最新文章

Copyright @ 2022~2023