C++ 顺序表实现

线性表就是字面上的意思，

顺序表是线性表基于数组的一种实现，

“顺序”这个名字怎么来的并不清楚，可以勉强解释为“存储地址是连续、顺序的”。

另外两种线性表实现分别是“基于链表”和“散列存储”。

顺序表可以是动态的，也可以是静态的，

“静态”就是一开始就知道表容量，并且这个容量在之后无法被更改；

“动态”就是能够动态的改变表的容量，实现上基于动态内存分配。

基于数组的静态版本：

#ifndef SEQLIST_H

#define SEQLIST_H

const int MAX_SIZE  = ;

template <class T>

class SeqList {

private:

    T node[MAX_SIZE];

    int size = ;

public:

    int getSize() const { return size; }

    bool add(const T& x);

    bool insert(int i, const T& x);

    bool remove(int i);

    int search(T& x);

    T& getNode(int i);

};    

#endif

template <class T>

bool SeqList<T>::add(const T& x) {

    if (size <= MAX_SIZE) {

        ++size;

        node[size-] = x;

        return true;

    }

    return false;

}

template <class T>

bool SeqList<T>::insert(int i, const T& x) {

    if (size <= MAX_SIZE && i >=  && i <= size) {

        ++size;

        for (int k = size-; k != i; --k) {

            node[k] = node[k-];

        }

        node[i] = x;

        return true;

    }

    return false;

}

template <class T>

bool SeqList<T>::remove(int i) {

    if (i >=  && i <= size) {

        for (int k = i; k != size; ++k) {

            node[k] = node[k+];

        }

        --size;

        return true;

    }

    return false;

}

template <class T>

int SeqList<T>::search(T& x) {

    for (int i = ; i != size; ++i) {

        if (node[i] == x) return i;

    }

    return -;

}

template <class T>

T& SeqList<T>::getNode(int i){

    if (i >=  && i < size) {

        return node[i];

    }

};



#ifndef STUDENT_H

#define STUDENT_H

#include <string>

#include <stdio.h>

struct Student {

    int no = ;

    std::string name;

    std::string grade;

    double goal = 0.0;

    Student() = default;

    Student(int arg1, const std::string& arg2,

        const std::string& arg3, double arg4): no(arg1), name(arg2), grade(arg3), goal(arg4) {}

    void display() const {

        printf("%d %s %s %.2f\n", no, name.c_str(), grade.c_str(), goal);

    }

    bool operator==(const Student &c1) {

        if (c1.name == this->name || c1.no == this->no && c1.grade == this->grade) return true;

        return false;

    }

};

#endif

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <string>

using namespace std;

int main()

{

    SeqList<Student> list;

    Student s1(, "张三", "", );

    Student s2(, "李四", "", );

    Student s3(, "王五", "", );

    Student s4(, "马六", "", );

    Student s5(, "黄荣", "", );

    list.add(s1);

    list.add(s2);

    printf("step-a\n");

    for (int i = ; i != list.getSize(); ++i) {

        list.getNode(i).display();

    }

    list.insert(, s3);

    list.insert(, s4);

    list.insert(, s5);

    printf("step-b\n");

    for (int i = ; i != list.getSize(); ++i) {

        list.getNode(i).display();

    }

    list.remove();

    list.remove();

    printf("step-c\n");

    for (int i = ; i != list.getSize(); ++i) {

        list.getNode(i).display();

    }    

    printf("step-d\n");

    if (list.search(s5) == -) {

        printf("不存在\n");

    } else {

        s5.display();

    }

    Student s6(, "郭靖", "", );

    if (list.search(s6) == -) {

        printf("不存在\n");

    } else {

        s6.display();

    }

    printf("step-e\n");

    for (int i = ; i != list.getSize(); ++i) {

        list.getNode(i).display();

    }

    printf("step-f\n");

    system("pause");

    while (true) {

        system("cls");

        cout << "#####WINDOWS##EDITION#####################" << endl;

        for (int i = ; i != list.getSize(); ++i) {

            list.getNode(i).display();

        }

        cout << "########################MAXSIZE=512#########" << endl;

        cout << "请选择您的操作1增2删3改4查:" << endl;

        int order = ;

        cin >> order;

        if (order <  || order > ) {

            cout << "无效命令!\n" << endl;

        } else {

            switch (order) {

                case : {

                    cout << "请输入学生的学号和姓名:" << endl;

                    int no = ;

                    string name;

                    cin >> no >> name;

                    cout << "请输入学生的学级和分数:" << endl;

                    string grade;

                    double goal = 0.0;

                    cin >> grade >> goal;

                    Student s(no, name, grade, goal);

                    list.add(s);

                    break;

                }

                case : {

                    cout << "请输入学生座号:" << endl;

                    int num;

                    cin >> num;

                    if (!list.remove(num)) {

                        cout << "不好意思，这个学生不存在" << endl;

                    }

                    break;

                }

                case : {

                    cout << "请输入需要修改的学生的座号:" << endl;

                    int num;

                    cin >> num;

                    cout << "您要修改的是" << list.getNode(num).name << "...,请输入新数据以覆盖原始数据:" << endl;

                    cin >> list.getNode(num).no

                        >> list.getNode(num).name

                        >> list.getNode(num).grade

                        >> list.getNode(num).goal;

                    break;

                }

                case : {

                    cout << "请输入需要查找的学生姓名:" << endl;

                    string name;

                    cin >> name;

                    Student s;

                    s.name = name;

                    if (list.search(s) == -) {

                        cout << "抱歉，没找到这名同学。" << endl;

                    } else {

                        cout << "该同学信息如下：" << endl;

                        list.getNode((list.search(s))).display();

                    }

                    break;

                }

            }

        }

        system("pause");

    }

    return ;

}

常量成员函数的设置有些小问题待修改。。

巴特西

C++ 顺序表实现

最新文章

热门文章