本文已經過時, 最新文章請點擊 :《【資料結構-重構】順序表 (向量)》

在写文章之前, 本来想着用图去表达可能更加清晰, 结果让我撞到了 SVG. 突然感觉 SVG 真的是为所欲为

下面这张图是后面要用的图, 准确的来说不算图, 因为这是用 HTML 代码写的. 当然, WordPress 默认的文本编辑器不支持这些代码, 这里用了 <iframe> 标签载入了一个小页面

有兴趣的话可以去 https://https://data-structure.jonny.vip/old/vector/vector_description.html 看一下源代码

入正题之前, 要说明一下. 数据结构的代码都是以 C++ 为基础的, 主要是结构体、指针和面向对象的代码

入正题 : 顺序表

顺序表在编程当中的模型为一维数组, 不过通常说的顺序表第一个元素是从 1 开始计数的, 数组的元素索引是从 0 开始的. 除了这里有些不一样, 其他操作几乎一样

可以看最上面那个图, 除了第一个元素没有前驱和最后一个元素没有后继之外, 中间的每一个元素都有且仅有一个属于自己的前驱和后继. 例如键盘上的一排按键就可以把它看作一个顺序表

在数学中, 线性表可以看作是一个行矩阵, 因此线性表可以记作 (a1, a2, ..., an), 这里 n 大于等于 0. 数学里仅支持线性表里面放数组, 编程中可以在线性表中放任何元素, 包括数字、字母和符号等. 不过根据线性表的特点, 一个线性表只支持一个数据类型

线性表有三个特点 :

• 同一性 : 就是上面说的一个线性表中的所有元素都必须是同一个数据类型
• 有穷性 : 线性表是有最大长度和元素长度的, 并且元素长度不能超过最大长度
• 有序性 : 用离散数学的表示方法即相邻的数据元素之间存在序偶关系 <ai, ai + 1>

1. 插入表

从上图可以看出, 可以看出插入表的某一个位置, 其实就是从该位置开始把原来该位置上的元素以及该元素之后的元素往后移动一个位置, 再将要插入的元素插入

不过期间需要判断线性表是否已经满了. 最简单的插入是对空表的插入, 直接插入第一个元素不需要移动

2. 删除表

删除是相对插入的, 从上图可以看到删除就是把要删除的位置对应的元素清空, 然后将后面的元素往前面移动就可以了

实际上数组中并不是这样的, 目前为止我还没有办法直接去删除. 但是类中有一个变量统计数组已经存在的元素的个数, 所以只要把这个变数 - 1 也可以达到相同的效果, 并不需要去删除

3. 初始化顺序表

接下来的操作都是非常简单和基础的操作

因为线性表在编程中, 我把它定义为一个类, 所以有类的构造方法, 参数传递是线性表的最大长度

方法中对指针一维数组按照最大长度进行初始化

4. 长度计算

类中还有另外一个变量就是统计已经存在的元素个数, 这个计数的变数就是长度, 直接返回即可

5. 获得某个元素

用户输入的肯定是正常的位置顺序, 但是数组的索引是从 0 开始的, 所以需要把用户输入的位置顺序 - 1, 然后直接返回具体的元素值

6. 元素定位

元素定位分成两种 :

• 定位第一个元素 : 只要遍历线性表, 并且返回第一个元素的位置就可以了
• 定位所有元素 : 这个需要遍历线性表 n 次, 这里的 n 代表这个元素出现的次数, 最后可以用数组计入位置, 直接返回一个指针数组就可以了

当然这里的位置同样是数组的索引, 所以输出的时候要 + 1 才是正常的顺序

7. 摧毁表

直接删除指针数组就可以了, 摧毁了就没意思了, 所以我没写

可以用 goto 语句或者 flag 布尔标志写多一层循环

8. 清空表

这个也很简单, 首先将类中的长度计数变数清零, 然后释放指针数组的内存, 之后按照最大长度重新声明指针数组

9. 还有就是判断线性表是否为空和是否为满

• 判断是否为空只要判断长度计数变数是否为 0
• 判断是否为满只要判断长度计数变数是否等于最大长度变数

下面给出源代码, 有错误欢迎指出

分成三个文件, 其中一个是 Class 源文件, 分为 .hpp 文件和 .cpp 文件, 另外一个是 main 函数文件

main.cpp :

#include "LinearList.hpp"

using namespace LinearList;

void menu();

int main(int argc, char *argv[]) {
    int maxNumber;
    cout << "Please enter the max number of the list : ";
    cin >> maxNumber;
    SequentialList *list;
    list = new SequentialList(maxNumber);
    int choose;
    int data, position;
    int location, *locationArray, length;
    long long int getData;
    do {
        system("clear");
        list->showList();
        cout << "--------------------------------------------------------" << endl;
        menu();
        cin >> choose;
        switch(choose) {
            case 1 :
                cout << "Please enter the data you want to insert : ";
                cin >> data;
                cout << "Please enter the position you want to insert : ";
                cin >> position;
                list->insertData(position, data);
                break;
            case 2 :
                cout << "Please enter the position that is what you want to get : ";
                cin >> position;
                getData = list->getData(position);
                if(getData != INT64_MIN) {
                    cout << "Data : " << getData << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to delete : ";
                cin >> data;
                list->deleteByElementDate(data);
                break;
            case 4 :
                cout << "please enter the position you want to delete : ";
                cin >> position;
                list->deleteByPositionData(position);
                break;
            case 5 :
                cout << "Please enter the data you want to locate : ";
                cin >> data;
                location = list->locate(data);
                cout << "The data's location : " << location << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 6 :
                cout << "Please enter the data you want to locate : ";
                cin >> data;
                locationArray = list->locateAll(data);
                if(locationArray == NULL) {
                    break;
                }
                length = locationArray[0];
                cout << "The data's location :\t";
                for(int i = 1; i < length; i++) {
                    cout << locationArray[i] + 1 << "\t";
                }
                cout << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 7 :
                list->cleanData();
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 8 :
                cout << "The list's length : " << list->listLength() << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 9 :
                delete []locationArray;
                delete list;
                cout << "Press any key to exit!" << endl;
                getchar();
                getchar();
                exit(0);
            default :
                break;
        }
    }while(choose != 9);
}
void menu() {
    cout << "1. Insert data." << endl;
    cout << "2. Get data by position." << endl;
    cout << "3. Delete data by element." << endl;
    cout << "4. Delete data by position." << endl;
    cout << "5. Locate data (It will only return first data's position)." << endl;
    cout << "6. Locate all data." << endl;
    cout << "7. Clean all data." << endl;
    cout << "8. Get the number of the list." << endl;
    cout << "9. Exit." << endl;
    cout << "Please enter your choose : ";
}

LinearList.hpp :

这个文件有必要说明一下, 这里我运用了命名空间

arr 就是对应的一维指针数组, 代表线性表

number 是长度计数

maxSize 是最大长度

具体函数都可以由名称猜出具体用途, 旁边也有注释

#ifndef LINEARLIST_LINEARLIST_HPP
#define LINEARLIST_LINEARLIST_HPP

#include <iostream>
#include <cstdlib>

namespace LinearList {
    using std::cout;
    using std::cin;
    using std::endl;
    class SequentialList {
    private:
        int *arr;
        int number;
        static int maxSize;
        bool isEmpty();     //To judge whether the array is empty
        bool isFull();      //To judge whether the array is full
        int locateThenChange(int *tempArray, int data);     //Return the first element from the temp array by the data user entered and change that element
    public:
        SequentialList(int number);
        ~SequentialList();
        int listLength();       //Return the number of the array
        long long int getData(int position);        //Get the data from the array by position
        void insertData(int position, int data);        //Insert element to array
        void deleteByPositionData(int position);        //Delete the element from the array by position
        void deleteByElementDate(int data);     //Delete element from the array by position
        int locate(int data);       //Locate the first element from the array by the data user entered
        int *locateAll(int data);       //Locate all elements from the array by the data user entered
        void cleanData();       //Clean the array's all elements
        void showList();        //Show the array's all elements
    };
}

#endif //LINEARLIST_LINEARLIST_HPP

LinearList.hpp :

#include "LinearList.hpp"

using namespace LinearList;
int SequentialList::maxSize = -1;
SequentialList::SequentialList(int number) {
    arr = new int[number];
    maxSize = number;
    number = 0;
}
SequentialList::~SequentialList() {
    delete []arr;
}
bool SequentialList::isEmpty() {
    if(!number) {
        return true;
    }
    return false;
}
bool SequentialList::isFull() {
    if(number == maxSize) {
        return true;
    }
    return false;
}
int SequentialList::listLength() {
    return number;
}
long long int SequentialList::getData(int position) {
    if(position > number || position <= 0) {
        cout << "Errant position!" << endl;
        return INT64_MIN;
    }
    return (long long int)arr[position - 1];
}
void SequentialList::insertData(int position, int data) {
    if(isFull()) {
        cout << "The list is full!" << endl;
        return;
    }
    if(position > number + 1 || position <= 0) {
        cout << "Errant position!" << endl;
        return;
    }
    for(int i = number; i > position - 1; i--) {
        arr[i] = arr[i - 1];
    }
    arr[position - 1] = data;
    number++;
    cout << "Insert success!" << endl;
}
void SequentialList::deleteByPositionData(int position) {
    if(position > number || position <= 0) {
        cout << "The position you entered hasn't been initted!" << endl;
        return;
    }
    for(int i = position - 1; i < number; i++) {
        arr[i] = arr[i + 1];
    }
    number--;
    cout << "Delete success!" << endl;
}
void SequentialList::deleteByElementDate(int data) {
    int position = locate(data);
    if(position == -1) {
        cout << "Cannot find the element you entered!" << endl;
        return;
    }
    while(position != -1) {
        for(int i = position; i < number; i++) {
            arr[i] = arr[i + 1];
        }
        number--;
        position = locate(data);
    }
    cout << "Delete success!" << endl;
}
int SequentialList::locate(int data) {
    for(int i = 0; i < number; i++) {
        if(arr[i] == data) {
            return i + 1;
        }
    }
    return -1;
}
int SequentialList::locateThenChange(int *tempArray, int data) {
    for(int i = 0; i < number; i++) {
        if(data == tempArray[i]) {
            tempArray[i] = data + 1;
            return i;
        }
    }
    return -1;
}
int *SequentialList::locateAll(int data) {
    int count = 1;
    int *location;
    location = new int[number];
    location[0] = 0;
    int *tempArray;
    tempArray = new int[number];
    for(int i = 0; i < number; i++) {
        tempArray[i] = arr[i];
    }
    int position = locateThenChange(tempArray, data);
    if(position == -1) {
        cout << "Cannot find the element you entered!";
        return NULL;
    }
    while(position != -1) {
        location[count] = position;
        count++;
        location[0] = count;
        position = locateThenChange(tempArray, data);
    }
    delete []tempArray;
    return location;
}
void SequentialList::cleanData() {
    delete []arr;
    arr = new int[number];
    number = 0;
    cout << "Clean Success!" << endl;
}
void SequentialList::showList() {
    cout << "Index : " << "\t";
    for(int i = 0; i < number; i++) {
        cout << i + 1 << "\t";
    }
    cout << endl;
    cout << "Element : " << "\t";
    for(int i = 0; i < number; i++) {
        cout << arr[i] << "\t";
    }
    cout << endl;
}