雙向連結清單

2017-08-28 20:46:09

writer：pprp

雙向連結清單比單連結清單每個節點還多了一個 pre 可以從目前節點找到上一個節點，操作比較友善，

但是由于指針較多，容易亂，是以寫代碼的時候要畫圖

代碼及解釋&測試如下：

/*
@theme: 雙連結清單
@writer:pprp
@start:19:13
@end:20:17
@declare:有兩個指針比較好操作，但是也比較亂
@date:2017/8/28
*/

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int data;
    node * pre;
    node * next;
};

class LinkList
{
private:
    node *head;
    node *tail;
    int len;
public:
    LinkList();
    //建構節點
    node * makeNode();
    //添加節點到尾端
    bool push(int data);
    //彈出最後一個節點
    int pop();
    //通過index來查找元素
    int FindAt(int index);
    //插入元素到指定位置
    bool Insert(int index, int data);
    //周遊列印
    void display(bool tag);
};

LinkList :: LinkList()
{
    head = makeNode();
    tail = head;
    len = 0;
}

//建構節點
node * LinkList::makeNode()
{
    node * newNode = new node();
    return newNode;
}
//添加節點到尾端
//test:ok
bool LinkList::push(int data)
{
    //mine
    node * newNode = new node();
    newNode->data = data;
    newNode->pre = tail;
    tail->next = newNode;
    tail = newNode;
    len++;
    return true;
}
//彈出最後一個節點
//test:ok
int LinkList::pop()
{
    int ans;
    node * tmp = tail;
    tail = tail->pre;
    ans = tmp->data;
    delete(tmp);
    tail->next = NULL;
    tmp = NULL;
    len--;
    return ans;
}

//通過index來查找元素
//test:ok
int LinkList::FindAt(int index)
{
    if(index < 1 || index > len)
        return 0;
    int data = 0;
    node * it = head;
    for(int i = 0 ; i < index ; i++)
    {
        it = it->next;
    }
    data = it->data;
    return data;
}

//插入元素到指定位置
//test:ok
bool LinkList::Insert(int index, int data)
{
    if(index < 1 || index > len)
        return false;
    node *it = head;
    for(int i = 0 ; i < index ; i++)
        it = it ->next;
    node * newNode = new node();
    newNode->data = data;
    it = it->pre;
    newNode->next = it->next;
    it->next = newNode;
    newNode->pre =  it;
    it = newNode->next;
    it->pre = newNode;
    len++;

    return true;
}

//周遊列印,tag = 1 正向周遊，tag = 0 方向周遊
//test :ok
void LinkList::display(bool tag)
{
    if(tag == 1) //--ok
    {
        node * it = head->next;
        while(it)
        {
            cout << it->data <<" ";
            it = it->next;
        }
        cout << endl;
    }
    else  //-- ok
    {
        node * it = tail;
        while(it!=head) //條件修改為head
        {
            cout << it->data << " ";
            it = it->pre;
        }
        cout << endl;
    }
}

int main()
{
    LinkList *p = new LinkList();
    for(int i = 0 ; i < 10 ; i++)
    {
//        srand((int)time(NULL) + i);
//        p->push(rand()%100);
        p->push(i+1);
    }

    p->display(true);
    cout << "-----" << endl;
    p->display(false);

    cout << p->pop() << endl;
    
    p->display(true);
    cout << "-----" << endl;
    p->display(false);
    
    cout << p->FindAt(5) << endl;

    p->Insert(5,817);
    
    p->display(true);
    cout << "-----" << endl;
    p->display(false);   


    return 0;
}      

代碼改變世界