查看完整版本: C++資料結構Linked List(非vector)

論壇 › C & C++ 語言 › C++資料結構Linked List(非vector)

trtc008056 發表於 2011-9-15 09:50 PM

C++資料結構Linked List(非vector)

本帖最後由 trtc008056 於 2011-9-15 10:12 PM 編輯

開學了....一段時間
學校有上資料結構，其中有講到Linked List

之前有用C、Java寫過 Linked list

這次用C++寫寫看

請多多指教~

Node.hclass Node{
public:
        int data;
        Node* next;
};List.h#include"Node.h"
class List{
        Node* head;
public:
        void insertNode(int num);
        void deleteNode(int key);
        void displayList();
};List.cpp#include"List.h"
#include<iostream>
using namespace std;
void List::insertNode(int num){
        Node* newNode = new Node();
        newNode->next = 0;
        newNode->data = num;
        Node* previousNode = nullptr;
        Node* currentNode = head;
        while(currentNode!=nullptr && currentNode->data<num){
                previousNode = currentNode;
                currentNode = currentNode->next;
        }
        if(previousNode==nullptr){
                newNode->next = head;
                head = newNode;
        }
        else{
                newNode->next = currentNode;
                previousNode->next = newNode;
        }
}
void List::deleteNode(int key){
        Node* pickedNode = nullptr;
        Node* previousNode = nullptr;
        Node* currentNode = head;
        while(currentNode!=nullptr && currentNode->data!=key){
                previousNode = currentNode;
                currentNode = currentNode->next;
        }
        if(currentNode==nullptr){
                cout<<key<<" not found"<<endl;
        }
        else if(previousNode!=nullptr){
                pickedNode = currentNode;
                previousNode->next = currentNode->next;
                delete pickedNode;
                cout<<key<<" deleted"<<endl;
        }
        else{
                pickedNode = currentNode;
                head = currentNode->next;
                delete pickedNode;
                cout<<key<<" deleted"<<endl;
        }
}
void List::displayList(){
        Node* aList = head;
        while(aList!=nullptr){
                cout<<aList->data<<"->";
                aList = aList->next;
        }
        cout<<"null"<<endl;
}main.cpp#include"List.h"
#include<time.h>
#include<iostream>
using namespace std;
int main(){
        srand(time(NULL));
        List* linkedList = new List();
        int t;
        //隨機插入10個數字
        for(int i=0;i<10;i++){
                t = rand()%30;
                cout<<"insert "<<t<<endl;
                linkedList->insertNode(t);
                linkedList->displayList();
        }
        cout<<endl<<endl;
        //隨機移除10個數字
        for(int i=0;i<10;i++){
                t = rand()%30;
                cout<<"delete "<<t<<endl;
                linkedList->deleteNode(t);
                linkedList->displayList();
        }
        system("pause");
        return 0;
}
執行結果:
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div>