1:  /*

2:  @@

3:  Author: justinzhang

4:  Email:  uestczhangchao@gmail.com

5:  Time:   2012-9-1 20:37:37

6:  desc:   double list related code

7:  */

8:  #include 
     

9:  #include 
     

10:  #include 
     

11:  using namespace std;

12:   

13:  template 
     

14:  class doublelist

15:  {

16:  public:

17:      static const int TERMINAL = 111;

18:      doublelist
     
      * get_next()
     

19:      {

20:          return next;

21:      }

22:      void set_next(doublelist
     
      * ne)
     

23:      {

24:          this->next = ne;

25:      }

26:   

27:      doublelist
     
      * get_prev()
     

28:      {

29:          return prev;

30:      }

31:      void set_prev(doublelist
     
      * prev)
     

32:      {

33:          this->prev = prev;

34:      }

35:   

36:      type get_data()

37:      {

38:          return data;

39:      }

40:      void set_data(const type &data)

41:      {

42:          this->data = data;

43:      }

44:      doublelist
     
       * create_doublelist();
     

45:      void show_doublelist(doublelist
     
       *phead);
     

46:      doublelist
     
       * create_doublelist_with_vector(vector
      
        data);
      
     

47:  private:

48:      doublelist
     
       * next;
     

49:      doublelist
     
       * prev;
     

50:      type data;

51:  };

52:   

53:  template
     
       doublelist
      
       * doublelist
       
        :: create_doublelist()
       
      
     

54:  {

55:      doublelist
     
       *phead = new doublelist
      
       ();
      
     

56:      assert(phead);

57:      phead->next = phead;

58:      phead->prev = phead;

59:      phead->data = TERMINAL;

60:      doublelist
     
       *preal_head = phead;
     

61:   

62:      type tmp_data;

63:      doublelist
     
       *node = NULL;
     

64:      cout << "input list data, end with " << TERMINAL << "!" << endl;

65:      while(1)

66:      {

67:          cin>> tmp_data;

68:          if(tmp_data == TERMINAL)

69:              break;

70:          node = new doublelist
     
      ();
     

71:          assert(node);

72:          node->data = tmp_data;

73:          phead->next = node;

74:          node->prev = phead;

75:          node->next = NULL;

76:          phead = node;

77:      }

78:      /* the following two statements make the list become circular link list*/

79:      node->next = preal_head;

80:      preal_head->prev = node;

81:      return preal_head;

82:  }

83:   

84:  template 
     
       void doublelist
      
       ::show_doublelist(doublelist
       
         *phead)
       
      
     

85:  {

86:      doublelist
     
       * cur = phead;
     

87:      /* if the cur pointer points to the head pointer, it means the end of the list;

88:         you can draw a draft graph to help you understatnd it;

89:      */

90:      while(cur->next!=phead)

91:      {

92:          cur = cur->next;

93:          cout << cur->data << endl;

94:      }

95:  }

96:   

97:  template 
     
       doublelist
      
        * doublelist
       
        ::create_doublelist_with_vector(vector
        
          data)
        
       
      
     

98:  {

99:      int i = 0;

100:      doublelist
     
       *ptmp_head = new doublelist
      
       ();
      
     

101:      assert(ptmp_head);

102:      ptmp_head->next = ptmp_head;

103:      ptmp_head->prev = ptmp_head;

104:      doublelist
     
       *phead = ptmp_head;
     

105:      doublelist
     
       *node = NULL;
     

106:      for(i = 0; i < data.size(); i++)

107:      {

108:          node = new doublelist
     
      ();
     

109:          assert(node);

110:          node->data = data[i];

111:          ptmp_head->next = node;

112:          node->prev = ptmp_head;

113:          ptmp_head = node;

114:          node->next = NULL;

115:      }

116:   

117:      /* make it become circular doble link list */

118:      phead->prev = node;

119:      node->next = phead;

120:      return phead;

121:  }

122:   

123:  int main()

124:  {

125:      doublelist
     
       dlist;
     

126:      //doublelist
     
       *dl1 = dlist.create_doublelist();
     

127:      //dlist.show_doublelist(dl1);

128:   

129:      /* test create_doublelist_with_vector */

130:      doublelist
     
       int_dlist;
     

131:      vector
     
       vec;
     

132:      for(int i=0; i<10; i++)

133:          vec.push_back(i+1);

134:      doublelist
     
      * pint_dlist = int_dlist.create_doublelist_with_vector(vec);
     

135:      int_dlist.show_doublelist(pint_dlist);

136:   

137:      return 0;

138:  }