線性表：同類型數(shù)據(jù)元素 構成有序序列的線性結構
-表中元素個數(shù)稱為長度
-沒有元素稱為空表
-表的起始位置稱表頭，結束位置稱為表尾。
類型名稱：List
數(shù)據(jù)對象集：數(shù)據(jù)表是N個元素構成的有序序列
操作集
List MakeEmpty() //初始化一個空線性表L
ElementType FinfKth(int K，List L);
int find(elementtype X,List L);

image.png

利用數(shù)組的連續(xù)存儲空間順序存放

image.png

鏈性存儲

image.png

廣義表

-線性表推廣
-線性表：單元素
-廣義表：元素也可以是另一個廣義表
多重鏈表
指針域會有多個
但是包含兩個指針域不一定是多重鏈表，比如在雙向鏈表中不是多重鏈表。
多重鏈表用途：樹、圖等、
例子：矩陣
-數(shù)組的大小應該事先確定
-稀疏矩陣：0比較多 造成存儲空間浪費
采用典型多重鏈表：十字鏈表
只存儲非0元素項
節(jié)點的數(shù)據(jù)域：行坐標、列坐標、數(shù)值
每個節(jié)點通過兩個指針域，把同行、同列穿起來

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(); //析構函數(shù)，負責回收內(nèi)存
    void MakeEmpty(); //清空鏈表
    bool IsEmpty(); //判斷鏈表是否為空
    Node<DataType> *FindElement(DataType value); //查找一個元素并返回地址
    Node<DataType> *FindNthElement(int n); //查找第n個元素，返回地址或者nullptr
    void DeleteElement(DataType inData); //刪除一個節(jié)點
    void DeleteNthElement(int n); //刪除第n個節(jié)點
    void InsertElement(DataType inData, int n); //插入一個節(jié)點
    int Length(); //返回鏈表長度
private:
    Node<DataType> dummyNode; //啞節(jié)點
    int listSize; //保存鏈表長度
    Node<DataType> *lastNode; //保存最后一個節(jié)點地址
};

//清空鏈表
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;
}

//刪除一個節(jié)點
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;
}

//插入一個節(jié)點
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;
}


//析構函數(shù)

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

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

}