线性表

线性表：同类型数据元素 构成有序序列的线性结构
-表中元素个数称为长度
-没有元素称为空表
-表的起始位置称表头，结束位置称为表尾。
类型名称：List
数据对象集：数据表是N个元素构成的有序序列
操作集
List MakeEmpty() //初始化一个空线性表L
ElementType FinfKth(int K，List L);
int find(elementtype X,List L);

image.png

利用数组的连续存储空间顺序存放

image.png

链性存储

image.png

广义表

-线性表推广
-线性表：单元素
-广义表：元素也可以是另一个广义表
多重链表
指针域会有多个
但是包含两个指针域不一定是多重链表，比如在双向链表中不是多重链表。
多重链表用途：树、图等、
例子：矩阵
-数组的大小应该事先确定
-稀疏矩阵：0比较多 造成存储空间浪费
采用典型多重链表：十字链表
只存储非0元素项
节点的数据域：行坐标、列坐标、数值
每个节点通过两个指针域，把同行、同列穿起来

template <typename DataType>
class Node
{
public:
    Node(DataType inData):data(inData),next(nullptr) {}
public:
    DataType data;
    Node *next;
};

template <typename DataType>
class List
{
public:
    List(DataType inDummy):dummyNode(inDummy), listSize(0), lastNode(nullptr) {}
    ~List(); //析构函数，负责回收内存
    void MakeEmpty(); //清空链表
    bool IsEmpty(); //判断链表是否为空
    Node<DataType> *FindElement(DataType value); //查找一个元素并返回地址
    Node<DataType> *FindNthElement(int n); //查找第n个元素，返回地址或者nullptr
    void DeleteElement(DataType inData); //删除一个节点
    void DeleteNthElement(int n); //删除第n个节点
    void InsertElement(DataType inData, int n); //插入一个节点
    int Length(); //返回链表长度
private:
    Node<DataType> dummyNode; //哑节点
    int listSize; //保存链表长度
    Node<DataType> *lastNode; //保存最后一个节点地址
};

//清空链表
template <typename DataType>
void List<DataType>::MakeEmpty()
{
    if (listSize <= 0 || dummyNode.next == nullptr) {
        return;
    }
    Node<DataType> * tmp = nullptr;
    while (dummyNode.next != nullptr) {
        tmp = dummyNode.next;
        dummyNode.next = dummyNode.next->next;
        delete tmp;
    }
    listSize = 0; lastNode = nullptr;
    return;
}

//判断链表是否为空
template <typename DataType>
bool List<DataType>::IsEmpty()
{
    if (listSize <= 0 || dummyNode.next == nullptr) {
        return true;
    }
    return false;
}



//查找一个元素并返回地址   
    template <typename DataType>
Node<DataType> * List<DataType>::FindElement(DataType value)
{
    Node<DataType> *cycleIter = dummyNode.next;
    while (cycleIter != nullptr) {
        if (cycleIter->data == value) {
            return cycleIter;
        }
        cycleIter = cycleIter->next;
    }
    return nullptr;
}

//查找第n个常量

template <typename DataType>
Node<DataType> * List<DataType>::FindNthElement(int n)
{
    if (n <= 0) {
        return nullptr;
    }
    Node<DataType> *cycleIter = dummyNode.next;
    while (--n > 0 && cycleIter != nullptr) {
        cycleIter = cycleIter->next;
    }
    return cycleIter;
}

//删除一个节点
template <typename DataType>
void List<DataType>::DeleteElement(DataType inData)
{
    Node<DataType> *frontIter = &dummyNode;
    Node<DataType> *cycleIter = frontIter->next;
    while (cycleIter != nullptr) {
        if (cycleIter->data == inData) {
            Node<DataType> * tmp = cycleIter;
            frontIter->next = cycleIter->next;
            delete tmp; --listSize;
            return;
        }
        frontIter = frontIter->next;
        cycleIter = cycleIter->next;
    }
    return;
}

//插入一个节点
template <typename DataType>
void List<DataType>::InsertElement(DataType inData, int n)
{
    Node<DataType> *insertElement = new Node<DataType>(inData);
    if (n < 0 || n >= listSize) {
        if (lastNode == nullptr) {
            lastNode = &dummyNode;
        }
        lastNode->next = insertElement;
        lastNode = insertElement; ++listSize;
        return;
    }
    Node<DataType> *cycleIter = &dummyNode;
    while (n-- > 0 && cycleIter != nullptr) {
        cycleIter = cycleIter->next;
    }
    if (n <= 0) {
        insertElement->next = cycleIter->next;
        cycleIter->next = insertElement; ++listSize;
    }
    return;
}

//返回链表长度

template <typename DataType>
int List<DataType>::Length()
{
    return listSize;
}


//析构函数

template <typename DataType>
List<DataType>::~List()
{
    MakeEmpty();
}

int main(){
    cout <<"o"<<endl;
    system("pause");
    return 0;

}