数据结构实验3：顺序表的基本操作

目录

一、实验目的

二、实验原理

1. 连续存储空间

2. 元素访问

3. 固定大小

4. 容量管理

5. 动态顺序表

6. 顺序表的插入

7. 顺序表的删除

?8. 顺序表的应用

三、实验内容

问题描述

代码

截图

分析?

---

一、实验目的

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. 顺序表的应用

1. 数组： 数组是一种顺序表的实现方式，它在内存中按顺序存储元素。数组适用于需要快速随机访问元素的场景，例如在数学运算、图像处理等领域。

2. 数据库： 在数据库中，表格可以被看作是一种顺序表。每一行记录都是表格中的一个元素，而每一列则对应于记录中的一个属性。数据库系统可以使用顺序表来快速检索、插入和删除记录。

3. 缓存： 缓存是一种用于提高数据访问速度的机制。顺序表可以用于实现缓存，其中最近访问的数据被存储在靠近数组的一端，以提高访问效率。

4. 文件存储： 顺序表可以用于存储文件中的数据。例如，一个文本文件的每一行可以被看作顺序表中的一个元素。

5. 图形学： 在图形学中，顺序表可以用于存储图像的像素数据。图像的每个像素可以被看作是顺序表中的一个元素，通过对这些元素的操作，可以实现图像的处理和变换。

6. 队列和栈： 虽然队列和栈通常使用链表来实现，但它们也可以通过顺序表来实现。在这种情况下，队列的元素在数组的一端进入，另一端出队，而栈则在数组的一端进出。

7. 电子表格： 电子表格软件（如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;
}

截图

分析?

这段代码并不难，稍微复杂的是链表，将会在下一篇文章中介绍