数据结构实验3：顺序表的基本操作
发布时间：2024年01月09日
目录
一、实验目的
1、 熟练掌握顺序表结构体的实现。
2、 熟练掌握顺序表的存储结构上实现基本操 作：查找、插入和删除算法。
二、实验原理
1. 连续存储空间
顺序表的元素在内存中是连续存储的，这意味着每个元素占据相邻的内存位置。这种特性使得顺序表可以通过数组等数据结构来实现。
2. 元素访问
由于元素在内存中是连续存储的，所以可以通过下标或者偏移量直接访问任意位置的元素。这使得顺序表具有O(1)的时间复杂度，即在常数时间内能够完成元素的访问操作。
3. 固定大小
顺序表的大小在创建时通常是固定的，即在存储空间分配后不会改变。这意味着在插入或删除元素时可能需要移动其他元素，导致相应的时间复杂度为O(n)。
4. 容量管理
顺序表有一个容量的概念，表示其最大可容纳的元素个数。当元素数量超过容量时，可能需要进行扩容操作，即重新分配更大的存储空间，并将原有元素复制到新的空间中。
5. 动态顺序表
为了解决固定大小的问题，可以采用动态顺序表，即在需要时动态地调整存储空间的大小。这通常通过扩容和缩小的方式来实现，以适应不同的需求。
#include <iostream>
using namespace std;
#define INITIAL_CAPACITY 10
typedef struct {
int* elements; // 存储线性表元素的数组
int size; // 当前存储的元素数量
int capacity; // 当前分配的存储空间容量
} DynamicArrayList;
// 初始化动态顺序表
void initDynamicArrayList(DynamicArrayList* list) {
list->elements = (int*)malloc(INITIAL_CAPACITY * sizeof(int));
if (list->elements == NULL) {
cout << "内存分配错误" << endl;
exit(EXIT_FAILURE);
}
list->size = 0;
list->capacity = INITIAL_CAPACITY;
}
// 获取当前存储的元素数量
int size(DynamicArrayList* list) {
return list->size;
}
// 获取当前分配的存储空间容量
int capacity(DynamicArrayList* list) {
return list->capacity;
}
// 判断动态顺序表是否为空
int isEmpty(DynamicArrayList* list) {
return list->size == 0;
}
// 获取指定索引位置的元素值
int get(DynamicArrayList* list, int index) {
if (index < 0 || index >= list->size) {
cout << "访问溢出" << endl;
exit(EXIT_FAILURE);
}
return list->elements[index];
}
// 设置指定索引位置的元素值
void set(DynamicArrayList* list, int index, int value) {
if (index < 0 || index >= list->size) {
cout << "访问溢出" << endl;
exit(EXIT_FAILURE);
}
list->elements[index] = value;
}
// 在动态顺序表末尾添加元素
void add(DynamicArrayList* list, int value) {
if (list->size == list->capacity) {
// 如果存储空间已满，进行扩容操作
list->capacity *= 2;
list->elements = (int*)realloc(list->elements, list->capacity * sizeof(int));
if (list->elements == NULL) {
cout << "内存分配错误" << endl;
exit(EXIT_FAILURE);
}
}
list->elements[list->size++] = value;
}
// 释放动态顺序表的内存
void freeDynamicArrayList(DynamicArrayList* list) {
free(list->elements);
list->size = 0;
list->capacity = 0;
}
int main() {
DynamicArrayList list;
initDynamicArrayList(&list);
// 示例操作
add(&list, 10);
add(&list, 20);
add(&list, 30);
cout << "顺序表的大小为：" << size(&list) << endl;
cout<<"顺序表的容量为：" <<capacity(&list)<<endl;
cout<<"顺序表的第二个元素为："<<get(&list, 1)<<endl;
set(&list, 1, 25);
cout << "顺序表的第二个元素为：" << get(&list, 1);
freeDynamicArrayList(&list);
return 0;
}
结果为
?
切记 大小≠容量
大小是有多少个元素，容量是指最多可以存储多少个元素
6. 顺序表的插入
将新元素插入到指定位置，并调整原有元素的位置以保持顺序表的有序性。
void Insert(ArrayList* list,int index,int value) {
if ((index < 0) || (index >= MAX_SIZE)) {//访问越界
cout << "访问越界" << endl;
return;
}
else if(list->size==MAX_SIZE){//数组已满
cout << "顺序表已满，无法插入" << endl;
return;
}
else {
for (int i = list->size - 1; i >= index; i--) {//index后的元素后移
list->elements[i + 1] = list->elements[i];
}
list->elements[index] = value;
list->size++;
}
}7. 顺序表的删除
将指定位置的元素移除，并调整顺序表中其他元素的位置，以保持有序表的结构?。
void Delete(ArrayList* list, int index) {
if ((index < 0) || (index >=list->size)) {//访问越界
cout << "访问越界" << endl;
return;
}
else {
for (int i = index; i <list->size; i++) {//index后的元素前移
list->elements[i] = list->elements[i+1];
}
list->size--;
}
}?8. 顺序表的应用
数组： 数组是一种顺序表的实现方式，它在内存中按顺序存储元素。数组适用于需要快速随机访问元素的场景，例如在数学运算、图像处理等领域。
数据库： 在数据库中，表格可以被看作是一种顺序表。每一行记录都是表格中的一个元素，而每一列则对应于记录中的一个属性。数据库系统可以使用顺序表来快速检索、插入和删除记录。
缓存： 缓存是一种用于提高数据访问速度的机制。顺序表可以用于实现缓存，其中最近访问的数据被存储在靠近数组的一端，以提高访问效率。
文件存储： 顺序表可以用于存储文件中的数据。例如，一个文本文件的每一行可以被看作顺序表中的一个元素。
图形学： 在图形学中，顺序表可以用于存储图像的像素数据。图像的每个像素可以被看作是顺序表中的一个元素，通过对这些元素的操作，可以实现图像的处理和变换。
队列和栈： 虽然队列和栈通常使用链表来实现，但它们也可以通过顺序表来实现。在这种情况下，队列的元素在数组的一端进入，另一端出队，而栈则在数组的一端进出。
电子表格： 电子表格软件（如Microsoft Excel、Google Sheets等）中的表格可以被视为一种顺序表。每个单元格中的数据可以被看作是顺序表中的一个元素，通过公式和函数可以对这些元素进行操作。
三、实验内容
问题描述
1、 初始化顺序表 L；
2、 依次在 L 尾部插入元素-1,21,13,24,8；
3、 输出顺序表 L;
4、 输出顺序表 L 长度；
5、 判断顺序表 L 是否为空；
6、 输出顺序表 L 的第 3 个元素；
7、 输出元素 24 的位置；
8、 在 L 的第 4 个元素前插入元素 0；
9、 输出顺序表 L;
10、 删除 L 的第 5 个元素；
11、 输出顺序表 L。
代码
#include <iostream>
using namespace std;
#define MAX_SIZE 100
typedef struct ArrayList {
int elements[MAX_SIZE]; // 存储线性表元素的数组
int size; // 当前存储的元素数量
};
//顺序表的初始化
void Initial_List(ArrayList* list) {
list->size = 0;
}
//插入元素
void Insert(ArrayList* list,int index,int value) {
if ((index < 0) || (index >= MAX_SIZE)) {//访问越界
cout << "访问越界" << endl;
return;
}
else if(list->size==MAX_SIZE){//数组已满
cout << "顺序表已满，无法插入" << endl;
return;
}
else {
for (int i = list->size - 1; i >= index; i--) {//index后的元素后移
list->elements[i + 1] = list->elements[i];
}
list->elements[index] = value;
list->size++;
}
}
void Delete(ArrayList* list, int index) {
if ((index < 0) || (index >=list->size)) {//访问越界
cout << "访问越界" << endl;
return;
}
else {
for (int i = index; i <list->size; i++) {//index后的元素前移
list->elements[i] = list->elements[i+1];
}
list->size--;
}
}
//返回某个元素的索引位置，默认返回第一个
int find_index(ArrayList* list, int value) {
for (int i = 0; i < list->size; i++) {
if (list->elements[i] == value) {
return i;
break;
}
}
return -1;
}
//判断顺序表是否为空
int IsEmpty(ArrayList* list) {
if (list->size == 0) {//若是空，则返回1
return 1;
}
else {
return 0;
}
}
int main() {
ArrayList L;
int data[5] = { -1,21,13,24,8 };
Initial_List(&L);//初始化顺序表L
//尾部插入
for (int i = 0; i < 5; i++) {
Insert(&L, L.size, data[i]);
}
//输出顺序表
cout << "顺序表为：";
for (int i = 0; i < L.size; i++) {
cout << L.elements[i]<<" ";
}
cout << endl;
cout << "顺序表的长度为：" << L.size<<endl;
if (IsEmpty(&L) == 1) {
cout << "顺序表为空" << endl;
}
else {
cout << "顺序表不为空" << endl;
}
cout << "顺序表的第三个元素为：" << L.elements[2] << endl;
if ((find_index(&L, 24)) != -1) {
cout<<"元素24的位置为："<< find_index(&L, 24)<<endl;
}
else {
cout<<"元素24不在顺序表中"<<endl;
}
//在第四个元素前插入0
Insert(&L,3,0);
//输出顺序表
cout << "顺序表为：";
for (int i = 0; i < L.size; i++) {
cout << L.elements[i] << " ";
}
cout << endl;
Delete(&L, 4);
//输出顺序表
cout << "顺序表为：";
for (int i = 0; i < L.size; i++) {
cout << L.elements[i] << " ";
}
return 0;
}
截图
分析?
这段代码并不难，稍微复杂的是链表，将会在下一篇文章中介绍
文章来源:https://blog.csdn.net/weixin_58628068/article/details/135479669
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 死锁产生的条件是什么？？？如何进行死锁判断？？？
- 扩展 GDB - 高亮显示反汇编中的 call 语句
- VMware Visio OmniGraffle模板和图标
- LeetCode //C - 2095. Delete the Middle Node of a Linked List
- c++ 经典服务器开源项目 Tinywebserver学习笔记
- C#，归并排序算法（Merge Sort Algorithm）的源代码及数据可视化
- 最新热门商用GPT4.0带MJ绘画去授权版本自定义三方接口(开心版)-YISHEN源码
- 【Database】什么是数据库？常见的数据库类型有哪些？
- Django笔记（一）：环境部署
- 关于jdk11新特性流操作的研究