雙向鏈結串列

題意:

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

思路:

節點

struct Node{
	int data;
    // 上一個節點
	Node* prev;
    // 下一個節點
	Node* next;
};

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

新增數字

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;
};

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

刪除數字

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的節點換成下一個位置的，然後刪除節點。

刪除最前面的

void deleteFirst(){
    Node* tmpNode = motherNode->next;
    motherNode->next = motherNode->next->next;
    motherNode->next->prev = motherNode;
    delete tmpNode;	
};

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

刪除最後面的

void deleteLast(){
    Node* tmpNode = motherNode->prev;
    motherNode->prev = motherNode->prev->prev;
    motherNode->prev->next = motherNode;
    delete tmpNode; 
};

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

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <string>

	using namespace std;

	enum Cmd {
	insertx,
	deletex,
	deleteFirst,
	deleteLast
	};

	struct Node{
	int data;
	// 上一個節點
	Node* prev;
	// 下一個節點
	Node* next;
	};

	class ConnectedList{
	public:
	ConnectedList(){
	motherNode = new Node();
	motherNode->data = -1;
	motherNode->prev = motherNode;
	motherNode->next = motherNode;
	};
	~ConnectedList(){
	Node* tmpNode = motherNode->next;
	Node* nextNode;
	while(tmpNode != motherNode){
	nextNode = tmpNode->next;
	delete tmpNode;
	tmpNode = nextNode;
	}
	delete motherNode;
	};
	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;
	};
	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;
	}
	};

	void deleteFirst(){
	Node* tmpNode = motherNode->next;
	motherNode->next = motherNode->next->next;
	motherNode->next->prev = motherNode;
	delete tmpNode;
	};

	void deleteLast(){
	Node* tmpNode = motherNode->prev;
	motherNode->prev = motherNode->prev->prev;
	motherNode->prev->next = motherNode;
	delete tmpNode;
	};

	void showList(){
	Node* tmpNode = motherNode->next;
	int i = 0;
	while(tmpNode != motherNode){
	if(i++){
	printf(" %d",tmpNode->data);
	}else{
	printf("%d",tmpNode->data);
	}
	tmpNode = tmpNode->next;
	}
	printf("\n");
	}

	private:
	Node* motherNode;
	};

	int main()
	{
	ConnectedList list;
	Cmd doubly;
	string s;
	int n, x;

	cin >> n;

	for(int i = 0; i < n; i++){
	cin >> s;
	if(s == "insert") {
	cin >> x;
	doubly = insertx;
	}else if(s == "delete") {
	cin >> x;
	doubly = deletex;
	}else if(s == "deleteFirst") {
	doubly = deleteFirst;
	}else if(s == "deleteLast") {
	doubly = deleteLast;
	}
	switch (doubly)
	{
	case 0:
	list.insertNode(x);
	break;
	case 1:
	list.deleteNode(x);
	break;
	case 2:
	list.deleteFirst();
	break;
	case 3:
	list.deleteLast();
	break;
	default:
	break;
	}
	}
	list.showList();
	return 0;
	}

view raw DoublyLinkedList.cpp hosted with ❤ by GitHub

CHUPCCA

AOJ ALDS1_3_C - Doubly Linked List