用XOR的概念，實作doubly linked list。

XOR的意思:如果 i=10110，j=01100，i XOR j=11010。
作業規定:
利用課本提供的方法，實作doubly linked list
每個node的structure包含一個data，一個link。

作業輸出和輸入的範例如下:
Choice 1)insert 2)show list : 1
input sequence : 1 2 6 9 3 15
Choice 1)insert 2)show list : 2
Left to Right : 1 2 6 9 3 15
...

瀏覽完整內容，請先 註冊 或 登入會員

小弟想到解決的方法了，謝謝看過問題的各位。

m0neypig

Let's assume we have 4 nodes A, B, C and D,
where A is head(left most), D is tail (right most):

Node                 A        B         C       D
Link pointer     0^B    A^C    B^D   D^0
...

瀏覽完整內容，請先 註冊 或 登入會員

m0neypig

Since I am so bored  (= =;)
and this problem is quite interesting, I attach my solution to this problem in C++.
The code is wrapped up in a hurry so please take it easy on me.
(and there are a lot of error handlings undone..)

1. #include <string>
   
2. #include <iostream>
   
3. #include <sstream>
   
4. 
   
5. // those macro are bad... but i'm lazy
   
6. #define PRINT_CMD cout << "Choice [1]insert [2]show list [3]exit: "
   
7. #define PRINT_ERR1 cout << "Unrecognized options, please enter 1, 2 or 3\n"
   
8. #define PRINT_ERR2 cout << "Please insert the number first...\n"
   
9. 
   
10. using namespace std;
    
11. 
    
12. class Node
    
13. {
    
14. private:
    
15.         int mLink;
    
16.         int mVal;
    
17. 
    
18. public:
    
19.         Node(int val):mVal(val), mLink(0){}
    
20.         ~Node(){};
    
21. 
    
22.         // append the value to the right hand side of the list
    
23.         // and return the right most node we just create
    
24.         // precondition: we are in the most right hand side!
    
25.         Node * append(int val)
    
26.         {
    
27.                 Node * node  = new Node(val);
    
28.                 mLink = mLink ^ (int)node;
    
29.                 node->mLink = (int)this ^ 0;
    
30.                 return node;
    
31.         }
    
32. 
    
33.         static void iterate(Node * list)
    
34.         {
    
35.                 Node * pre = 0;
    
36.                 Node * cur = list;
    
37. 
    
38.                 while(cur->mLink != (int)pre){
    
39.                         cout << cur->mVal << " " ;
    
40.                         Node * temp = cur;
    
41.                         cur = (Node *)( (int)pre ^ cur->mLink);
    
42.                         pre = temp;
    
43.                 }
    
44.                 cout << cur->mVal << endl;
    
45.         }
    
46. 
    
47.         static void releaseResource(Node * list)
    
48.         {
    
49.                 if(list == NULL) return;
    
50.                 Node * pre = 0;
    
51.                 Node * cur = list;
    
52.                 while(cur->mLink != (int)pre){
    
53.                         Node * temp = cur;
    
54.                         cur = (Node *)( (int)pre ^ cur->mLink);
    
55.                         delete pre;
    
56.                         pre = temp;
    
57.                 }
    
58.                 delete pre;
    
59.                 delete cur;
    
60.         }
    
61. };//class Node
    
62. 
    
63. int main()
    
64. {
    
65.     Node * leftMost = NULL;
    
66.     Node * rightMost = NULL;
    
67. 
    
68.     string line;
    
69.     PRINT_CMD;
    
70.    
    
71.     while ( getline(std::cin, line))
    
72.     {
    
73.         if(line.compare("1")==0){
    
74.             if( getline(std::cin, line) ){
    
75.                 istringstream iss (line,istringstream::in);
    
76.                 int val;
    
77.                 bool firstTime = true;
    
78.                 while(iss >> val){
    
79.                     if(firstTime){
    
80.                         leftMost = new Node(val);
    
81.                         rightMost = leftMost;
    
82.                         firstTime= false;
    
83.                     }
    
84.                     else
    
85.                         rightMost = rightMost->append(val);
    
86.                 }
    
87.             }
    
88.         }
    
89.         else if(line.compare("2")==0){
    
90.             if(leftMost==NULL){
    
91.                 PRINT_ERR2;
    
92.                 PRINT_CMD;
    
93.                 continue;
    
94.             }
    
95.             cout << "Left to Right :";
    
96.             Node::iterate(leftMost);
    
97.             cout << "Right to Left:";
    
98.             Node::iterate(rightMost);
    
99.         }
    
100.         else if(line.compare("3")==0) {
     
101.             Node::releaseResource(leftMost);
     
102.             break;
     
103.         }
     
104.         else{
     
105.             PRINT_ERR1;
     
106.         }
     
107.         PRINT_CMD;
     
108.     }
     
109.     return 0;
     
110. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

Thank you for your exposition. (^O^)