#include "linearList.h"
using namespace std;
//顺序表初始化
sequenceList::sequenceList(const int& a, const int& b, float arr[])//顺序表容量，初始化数组长度，初始化数组
{
    maxCapcity = a;
    myList = new float[maxCapcity];
    curNumberOfItem = b;
    for (int i = 0;i < b;i++)
    {
        *(myList + i) = arr[i];
    }
}
//析构函数
sequenceList::~sequenceList()
{
    delete[]myList;
}
//添加元素顺序表尾，成功返回true，失败返回false
bool sequenceList::addItem(const float& num)
{
    if (curNumberOfItem + 1 > maxCapcity) return false;
    *(myList + curNumberOfItem ) = num;
    curNumberOfItem++;
    return true;
}
bool sequenceList::insertItem(const int& index, const float&num)//插入元素到index位置，成功返回true，失败返回false
{
    if (index<0 || index>curNumberOfItem ) return false;
    float* q = &(myList[index]);
    for (float* p = &(myList[curNumberOfItem - 1]);p >= q;p--) *(p + 1) = *p;//将元素后移
    *q = num;
    curNumberOfItem++;
    return true;
}
//删除元素，返回删除位置，找不到返回-1
int sequenceList::deleteItem(const float& data)
{
    int index = 0;
    while (index < curNumberOfItem && myList[index] != data) index++;
    if (myList[index] != data) return -1;
    float* p = &(myList[index]);
    float* q = myList + curNumberOfItem - 1;//q是表尾元素地址
    for (++p;p <= q;++p) *(p - 1) = *p;
    curNumberOfItem--;
    return index;
}
//查找元素（按值找）返回找到位置，找不到返回 - 1
int sequenceList::locate(const float& data)
{
    for (int i = 0;i < curNumberOfItem;i++)
    {
        if (myList[i] == data) return i;
    }
    return -1;
}
//查找元素（按序号找）成功返回true，值放在val中，失败返回false
bool sequenceList::locate(const int&index, float&val)
{
    if (index < 0 || index >= curNumberOfItem) return false;
    val = myList[index];
    return true;
}
void sequenceList::reverse()
{
    for (int i = 0;i < (curNumberOfItem / 2);i++)
    {
        swap(myList[i], myList[curNumberOfItem - i - 1]);
    }
}
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}
//链表初始化
listNode::~listNode()
{

}
linkList::linkList(const int& a, float arr[])
{
    this->firstNode = this->curNode = this->lastNode = new listNode;
    this->listSize = a;
    for (int i = 0;i < a;i++)
    {
        this->lastNode->next = new listNode;
        this->lastNode->next->data = arr[i];
        this->lastNode = this->lastNode->next;
    }
}
linkList::linkList()
{
    this->listSize = 0;
    firstNode = lastNode = new listNode;
    curNode = NULL;
}
//删除链表
linkList::~linkList()
{
    listNode* p ;
    while (firstNode->next != NULL)
    {
        p = firstNode->next;
        delete (firstNode);
        firstNode = p;
    }
    delete(firstNode);
}
bool linkList::headInsertItem(const float& a)
{
    listNode* p = new listNode;
    if (p == NULL)return false;
    p->data = a;
    p->next = this->firstNode->next;
    this->firstNode->next = p;
    this->listSize++;
    return true;
};//按值头插

bool linkList::tailInsertItem(const float& a)
{
    listNode* p = new listNode(a, NULL);
    if (p == NULL)return false;
    this->lastNode->next = p;
    this->lastNode = p;
    this->listSize++;
    return true;
};          //按值尾插


int linkList::insertItem(const int& index, const float& a)
{
    if (index<0 || index>this->listSize) return -1;
    this->curNode = this->firstNode;
    for (int i = 0;i < index;i++)
    {
        curNode = curNode->next;
    }
    listNode* p = new listNode(a, NULL);
    p->next = curNode->next;
    curNode->next = p;
    this->listSize++;
    return index;
};    //插入特定位置

int linkList::deleteItem(const float& a)
{
    int index = 0;
    this->curNode = this->firstNode->next;
    listNode* p = this->firstNode;
    while (this->curNode->data != a && index < this->listSize)
    {
        this->curNode = this->curNode->next;
        p = p->next;
        index++;
    }
    if (curNode->data == a)
    {
        p->next = this->curNode->next;
        p = this->curNode;
        curNode = curNode->next;
        delete p;
        this->listSize--;
        return index;
    }
    return -1;
};               //按值删除

bool linkList::locate(const int& a, float& val)
{
    if (a<0 || a>this->listSize - 1) return false;
    this->curNode = this->firstNode->next;
    for (int i = 0;i < a;i++) this->curNode = this->curNode->next;
    val = this->curNode->data;
    return true;
};            //按位查找

int linkList::locate(const float& a)
{
    int index = -1;
    this->curNode = this->firstNode;
    while (this->curNode->data != a && index < this->listSize-1)
    {
        this->curNode = this->curNode->next;
        index++;
    }
    if (curNode->data == a) return index;
    return -1;
};                   //按值查找
//排序
void linkList::ascendingOrder()
{
    int ci = listSize;
    listNode* P = firstNode;
    listNode* p1;
    listNode* p2;
    for (int i = 0;i < ci - 1;i++)
    {
        P = firstNode->next;
        for (int j = 0;j < ci - i - 1;j++)
        {
            p1 = P;p2 = P->next;
            if (p1->data > p2->data)
            {
                float tem = p1->data;
                p1->data = p2->data;
                p2->data = tem;
            }
            P = P->next;
        }
    }
}
//翻转
void linkList::reverse()
{
    listNode* p = this->firstNode->next;
    this->lastNode = p;
    this->firstNode->next = NULL;
    while (p != NULL)
    {
        this->curNode = p;
        p = p->next;
        this->curNode->next= this->firstNode->next;
        this->firstNode->next = this->curNode;
    }
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}
int linkList::size()
{
    return this->listSize;
}
void merge(linkList&A, linkList&B)
{
    int len = B.size();
    B.curNode = B.firstNode->next;
    for (int i = 0;i < len;i++)
    {
        A.headInsertItem(B.curNode->data);
        B.curNode = B.curNode->next;
    }
    A.ascendingOrder();
    A.reverse();
}