CHUPCCA

解題報告

0%

AOJ ALDS1_3_C - Doubly Linked List

發表於 更新於 分類於 Disqus：

雙向鏈結串列

題目網址

題意:

寫一個具備以下功能的Doubly Linked List:
insert x: 加入一個元素x在list的最前面.
delete x: 刪除一個元素x. 如果沒有找到，不必做任何動作.
deleteFirst: 刪除list第一個元素.
deleteLast: 刪除list最後一個元素.

思路:

節點
1
2
3
4
5
6
7
struct Node{
	int data;
    // 上一個節點
	Node* prev;
    // 下一個節點
	Node* next;
};

首先我們要先宣告一個結構分別為資料,上個節點和下一個節點。

新增數字
1
2
3
4
5
6
7
8
void insertNode(int x){
    Node* tmpNode = motherNode->next;
    motherNode->next = new Node();
    motherNode->next->data = x;
    motherNode->next->next = tmpNode;
    motherNode->next->prev = motherNode;
    tmpNode->prev = motherNode->next;
};

先新增一個新節點然後將資料放入後，與主節點做連接。

刪除數字
1
2
3
4
5
6
7
8
9
10
11
void deleteNode(int x){
    Node* tmpNode = motherNode->next;
    while(tmpNode != motherNode && tmpNode->data != x){
        tmpNode = tmpNode->next;
    }
    if(tmpNode != motherNode){	
        tmpNode->prev->next = tmpNode->next;
        tmpNode->next->prev = tmpNode->prev;
        delete tmpNode;
    }
};

逐一檢查節點資料是否為x，如果找到了就將next與prev的節點換成下一個位置的，然後刪除節點。

刪除最前面的
1
2
3
4
5
6
void deleteFirst(){
    Node* tmpNode = motherNode->next;
    motherNode->next = motherNode->next->next;
    motherNode->next->prev = motherNode;
    delete tmpNode;	
};

將最前面的節點交換後與主節點連接，然後再將他刪除。

刪除最後面的
1
2
3
4
5
6
void deleteLast(){
    Node* tmpNode = motherNode->prev;
    motherNode->prev = motherNode->prev->prev;
    motherNode->prev->next = motherNode;
    delete tmpNode; 
};

將最後面的節點交換後與主節點連接，然後再將他刪除。

程式碼: