程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 若何用C++完成雙向輪回鏈表

若何用C++完成雙向輪回鏈表

編輯:關於C++

若何用C++完成雙向輪回鏈表。本站提示廣大學習愛好者:(若何用C++完成雙向輪回鏈表)文章只能為提供參考,不一定能成為您想要的結果。以下是若何用C++完成雙向輪回鏈表正文


雙向輪回鏈表,即每一個節點都具有一前一後兩個指針且頭尾互鏈的鏈表。各類鏈表的簡略差別以下:
單向鏈表:根本鏈表;
單向輪回鏈表:分歧於單向鏈表以 NULL 斷定鏈表的尾部,單向輪回鏈表的尾部鏈接到表頭,是以當迭代操作到表頭前等於尾部;
雙向鏈表:比單向鏈表多出指向前一個節點的指針,但現實上應用雙向鏈表時很少應用不輪回的;
雙向輪回鏈表:絕對於單向輪回鏈表,雙向輪回鏈表可從頭部反向迭代,這在鏈表長度很年夜且須要獲得、拔出或刪除接近鏈表尾部元素的時刻非常高效。單向輪回列表只能從表頭正向迭代,履行的時光年夜於從反向迭代。
node.h

/*
* 節點類型。三個成員分離是:指向前一個節點的指針,元素自己,指向後一個節點的指針。
*/
class Node {
public:
    int element;
    Node *next;
    Node *previous;
    Node(int element, Node *next, Node *previous) {
        this->element = element;
        this->next = next;
        this->previous = previous;
    }
};
linkedlist.h:
#include "node.h“
struct LinkedList {
    LinkedList();
    void addFirst(int);
    void addLast(int);
    void add(int index, int element);
    int getFirst();
    int getLast();
    int get(int);
    int removeFirst();
    int removeLast();
    int remove(int);
    void iterate();
private:
    Node *header;
    int size;
};
linkedlist.cpp:
#include "linkedlist.h"
#include <iostream>
using std::cout;
/*
* 結構辦法。
* 生成一個空的節點介於表頭和表尾之間,初始前後指針都指向本身。
*/
LinkedList::LinkedList() {
    header = new Node(NULL, NULL, NULL);
    header->next = header;
    header->previous = header;
    size = 0;
}
/*
* 在鏈表頭部添加一個元素。
* 生成一個新的節點,向前指向空節點,向後指向本來空節點的下一個節點,即本來的第一個節點。
* 空節點向後指向此節點,本來的第一個節點向前指向此節點。
*/
void LinkedList::addFirst(int i) {
    header->next = new Node(i, header->next, header);
    header->next->next->previous = header->next;
    ++size;
}
/*
* 在鏈表最初添加一個元素。
* 生成一個新的節點,向前指向本來空節點的前一個節點,即本來的最初一個節點,向後指向空節點。
* 本來的最初一個節點向後指向此節點,空節點向前指向此節點。
*/
void LinkedList::addLast(int i) {
    header->previous = new Node(i, header, header->previous);
    header->previous->previous->next = header->previous;
    ++size;
}
/*
* 在指定的索引前拔出一個元素。0 <= 索引 <= 鏈表長度。
* 假如索引值小於鏈表長度的一半,向後(正向)迭代獲得索引值地位的節點,反之則向前(反向)。
* 生成一個新的節點,向前指向本來這個地位的節點的前一個節點,向後指向本來這個地位的節點。
* 本來這個地位的節點的前一個節點向後指向此節點,本來這個地位的節點向前指向此節點。
* (在指定的索引刪除一個元素完成辦法相似)
*/
void LinkedList::add(int index, int i) {
    if(index > size || index < 0) {
        cout << "Exception in add(): Index out of bound." << '\n';
    return;
    }
    Node *entry;
    if(index < size / 2) {
        entry = header->next;
        for(int i = 0; i < index; ++i)
            entry = entry->next;
    }
    else {
        entry = header;
        for(int i = size; i > index; --i)
            entry = entry->previous;
    }
    entry->previous->next = new Node(i, entry, entry->previous);
    entry->previous = entry->previous->next;
    ++size;
}
/*
* 獲得鏈表第一個元素。
* 空節點向後指向的節點等於第一個元素。
*/
int LinkedList::getFirst() {
    if(!size)
        cout << "Exception in getFirst(): List is empty." << '\n';
    return header->next->element;
}
/*
* 獲得鏈表最初一個元素。
* 空節點向前指向的節點等於最初一個元素。
*/
int LinkedList::getLast() {
    if(!size)
        cout << "Exception in getLast(): List is empty." << '\n';
    return header->previous->element;
}
/*
* 刪除並前往鏈表第一個元素。
* 鏈表第二個節點向前指向空節點,空節點向後指向第二個節點。
*/
int LinkedList::removeFirst() {
    int remove = header->next->element;
    header->next->next->previous = header;
    header->next = header->next->next;
    --size;
    return remove;
}
/*
* 刪除並前往鏈表最初一個元素。
* 鏈表倒數第二個節點向後指向空節點,空節點向前指向倒數第二個節點。
*/
int LinkedList::removeLast() {
    int remove = header->previous->element;
    header->previous->previous->next = header;
    header->previous = header->previous->previous;
    --size;
    return remove;
}
/*
* 用來輸入一切元素的迭代辦法。
*/
void LinkedList::iterate() {
    if(!size) {
        cout << "Exception in iterate(): List is empty." << '\n';
        return;
    }
    for(Node *entry = header->next; entry != header; entry = entry->next)
        cout << entry->element << " ";
    cout << '\n';
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved